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

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

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

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

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

${\displaystyle f_{n+1}{\frac {k_{n+1}^{(p)}(x)}{d_{n+1}}}+f_{n}{\frac {k_{n-1}^{(p)}(x)}{d_{n-1}}}=\left(rx+\varepsilon n+\Delta \right){\frac {k_{n}^{(p)}(x)}{d_{n}}}}$,

де

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

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

${\displaystyle k_{n}^{(p)}(x)=(-1)^{n}{\binom {N}{n}}p^{n}{}_{2}F_{1}(-n,-x;-N;1/p)}$

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

${\displaystyle \lim \limits _{N\to \infty }\left(2/Npq\right)^{n/2}n!;k_{n}^{(p)}\left(Np+{\sqrt {2Npq}},x\right)=H_{n}(x)}$

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

• ${\displaystyle {\mathcal {K}}_{0}(x,N)=1}$
• ${\displaystyle {\mathcal {K}}_{1}(x,N)=-2x+N}$
• ${\displaystyle {\mathcal {K}}_{2}(x,N)=2x^{2}-2Nx+{N \choose 2}}$
• ${\displaystyle {\mathcal {K}}_{3}(x,N)=-{\frac {4}{3}}x^{3}+2Nx^{2}-\left(N^{2}-N+{\frac {2}{3}}\right)x+{N \choose 3}}$