Поліноми Кравчука

Поліноми Кравчука ( М. П. Кравчук, 1929) належать до класичних ортогональних поліномів дискретної змінної на рівномірній сітці, для яких співвідношення ортогональності являє собою не інтеграл, а ряд або скінченну суму: $\sum\limits^N_{x=0}k^{(p)}_n(x)k^{(p)}_m(x) \sigma(x)= d_n^2,\delta_{m,n}$ .

Тут $\sigma(x)=\binom{N}{x} p^x q^{N-x}$ — вагова функція, $d_n=\sqrt{\binom{N}{n}(pq)^n}$ — квадратична норма, $0<p<1, \quad 0<q<1, \quad p+q=1$ . Для $p=q=1\left/2\right.$ вагова функція з точністю до постійного множника $1\left/ 2^N\right.$ зводиться до біноміального коефіцієнта.

Рекурентне співвідношення для цих поліномів має вигляд $(n+1)k^{(p)}_{n+1}(x)+pq\left(N-n+1\right)k^{(p)}_{n-1}(x)= \bigl[ x+n(p-q)-pN \bigr]k^{(p)}_n (x)$ .

Шляхом нескладних перетворень його можна привести до вигляду

$f_{n+1}\frac{k^{(p)}_{n+1}(x)}{d_{n+1}}+f_{n}\frac{k^{(p)}_{n-1}(x)}{d_{n-1}}= \left( rx+\varepsilon n+\Delta \right)\frac{k^{(p)}_n (x)}{d_n}$ ,

де

$f_n=\sqrt{\frac{n(N+1-n)}{N}},\quad r=\frac{1}{\sqrt{pqN}},\quad \varepsilon=r(p-q),\quad \Delta=-rpN.$

Поліноми Кравчука можуть бути виражені через гіпергеометричну функцію Гауса:

$k^{(p)}_n(x)=(-1)^n \binom{N}{n} p^n {}_2 F_1(-n,-x;-N;1/p)$

В границі при $N\to\infty$ поліноми Кравчука переходять у Поліноми Ерміта:

$\lim\limits_{N\to\infty} \left(2/Npq\right)^{n/2}n! ;k_n^{(p)} \left( Np + \sqrt{2Npq},x \right) = H_n(x)$

Перші чотири поліноми для найпростішого випадку $p=q=1/2$ :

$\mathcal{K}_0(x, N) = 1$
$\mathcal{K}_1(x, N) = -2x + N$
$\mathcal{K}_2(x, N) = 2x^2 - 2Nx + {N\choose 2}$
$\mathcal{K}_3(x, N) = -\frac{4}{3}x^3 + 2Nx^2 - \left(N^2 - N + \frac{2}{3}\right)x + {N \choose 3}$