Aja viide. Aja lugu.

Kravchuk polynomials or Krawtchouk polynomials (also written using several other transliterations of the Ukrainian surname Кравчу́к) are discrete orthogonal polynomials associated with the binomial distribution, introduced by Mykhailo Kravchuk (1929). The first few polynomials are (for q = 2):

{\mathcal {K}}_{0}(x;n)=1,

{\mathcal {K}}_{1}(x;n)=-2x+n,

{\mathcal {K}}_{2}(x;n)=2x^{2}-2nx+{\binom {n}{2}},

{\mathcal {K}}_{3}(x;n)=-{\frac {4}{3}}x^{3}+2nx^{2}-(n^{2}-n+{\frac {2}{3}})x+{\binom {n}{3}}.

The Kravchuk polynomials are a special case of the Meixner polynomials of the first kind.

Definition

For any prime power q and positive integer n, define the Kravchuk polynomial ${\begin{aligned}{\mathcal {K}}_{k}(x;n,q)={\mathcal {K}}_{k}(x)={}&\sum _{j=0}^{k}(-1)^{j}(q-1)^{k-j}{\binom {x}{j}}{\binom {n-x}{k-j}}\\={}&\sum _{j=0}^{k}(-1)^{j}(q-1)^{k-j}{\frac {x^{\underline {j}}}{j!}}{\frac {(n-x)^{\underline {k-j}}}{(k-j)!}}\end{aligned}}$ for $k=0,1,\ldots ,n$ . In the second line, the factors depending on $x$ have been rewritten in terms of falling factorials, to aid readers uncomfortable with non-integer arguments of binomial coefficients.

Properties

The Kravchuk polynomial has the following alternative expressions:

{\mathcal {K}}_{k}(x;n,q)=\sum _{j=0}^{k}(-q)^{j}(q-1)^{k-j}{\binom {n-j}{k-j}}{\binom {x}{j}}.

{\mathcal {K}}_{k}(x;n,q)=\sum _{j=0}^{k}(-1)^{j}q^{k-j}{\binom {n-k+j}{j}}{\binom {n-x}{k-j}}.

Note that there is more that merely recombination of material from the two binomial coefficients separating these from the above definition. In these formulae, only one term of the sum has degree $k$ , whereas in the definition all terms have degree $k$ .

Symmetry relations

For integers $i,k\geq 0$ , we have that

{\begin{aligned}(q-1)^{i}{n \choose i}{\mathcal {K}}_{k}(i;n,q)=(q-1)^{k}{n \choose k}{\mathcal {K}}_{i}(k;n,q).\end{aligned}}

Orthogonality relations

For non-negative integers r, s,

\sum _{i=0}^{n}{\binom {n}{i}}(q-1)^{i}{\mathcal {K}}_{r}(i;n,q){\mathcal {K}}_{s}(i;n,q)=q^{n}(q-1)^{r}{\binom {n}{r}}\delta _{r,s}.

Generating function

The generating series of Kravchuk polynomials is given as below. Here $z$ is a formal variable.

{\begin{aligned}(1+(q-1)z)^{n-x}(1-z)^{x}&=\sum _{k=0}^{\infty }{\mathcal {K}}_{k}(x;n,q){z^{k}}.\end{aligned}}

Three term recurrence

The Kravchuk polynomials satisfy the three-term recurrence relation

{\begin{aligned}x{\mathcal {K}}_{k}(x;n,q)=-q(n-k){\mathcal {K}}_{k+1}(x;n,q)+(q(n-k)+k(1-q)){\mathcal {K}}_{k}(x;n,q)-k(1-q){\mathcal {K}}_{k-1}(x;n,q).\end{aligned}}

References

Kravchuk, M. (1929), "Sur une généralisation des polynomes d'Hermite.", Comptes Rendus Mathématique (in French), 189: 620–622, JFM 55.0799.01
Koornwinder, Tom H.; Wong, Roderick S. C.; Koekoek, Roelof; Swarttouw, René F. (2010), "Hahn Class: Definitions", in Olver, Frank W. J.; Lozier, Daniel M.; Boisvert, Ronald F.; Clark, Charles W. (eds.), NIST Handbook of Mathematical Functions, Cambridge University Press, ISBN 978-0-521-19225-5, MR 2723248.
Nikiforov, A. F.; Suslov, S. K.; Uvarov, V. B. (1991), Classical Orthogonal Polynomials of a Discrete Variable, Springer Series in Computational Physics, Berlin: Springer-Verlag, ISBN 3-540-51123-7, MR 1149380.
Levenshtein, Vladimir I. (1995), "Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces", IEEE Transactions on Information Theory, 41 (5): 1303–1321, doi:10.1109/18.412678, MR 1366326.
MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, North-Holland, ISBN 0-444-85193-3

External links

Aja viide. Aja lugu.

Värsked postitused

Most Used Categories

Soomes tuleb 30 kraadi külma

Allikad: Zelenski andis Trumpile korvi

Eesti Laulu finaali laval näeb jääd ja väga erilisi tuleleeke

Ostapenko sai viiendat korda järjest Swiatekist jagu

Soome välisminister: USA-l on pea sassis

USA asepresident nahutas Euroopat ja ütles, et suurim oht pole Venemaa ega Hiina, vaid Euroopa ise

5 statistilist fakti, mis näitavad, kui hea on Soome mobiilimängude valdkond

Alexander Lott: mida tooks territoriaalmere piiri laiendamine Soome lahes?

Meedia: Läti peaminister võib viia ellu valitsusremondi

MEEDIAVALVUR: algab „sõjalise erioperatsiooni“ teine etapp nimega „SÕDA“

Definition