Basic Proof of Properties of Kravchuk Polynomials

Question

Fix $n$ and consider the family of polynomials $$ K_s(\ell) = \sum_{k=0}^s(-1)^k\binom{\ell}{k}\binom{n-\ell}{s-k} \quad \text{defined for} \quad 0 \leq s \leq n $$

They are called Kravchuk (or Krawtchouk) polynomials.

They are used in a paper I am trying to understand.

The key properties of the polynomials that are used are that if you define the inner product $$ \langle f, g \rangle = \mathbf{E}_{k \leftarrow Bin(n,\frac{1}{2})}\big[f(k)g(k)\big] $$ where $Bin(n,\frac{1}{2})$ is the binomial distribution, on the vector space of functions $\mathbb R^{\{0,1,\ldots,n\}}$ then $$ \langle K_s, K_r\rangle = \begin{cases} \binom{n}{s} & r=s\\ 0 & r \neq s\end{cases} $$ so that they form an orthogonal basis, and $$ \binom{n}{r}K_s(r) = \binom{n}{s}K_r(s) $$ which allows some computations to be simplified.

However, there seem to be no simple proofs of these facts anywhere; any proof I have found proves this as a special case of some much more general theory and it is too complicated for me to understand. Can someone give a basic proof of these identities?

Answer 1

First, we give a probabilistic interpretation of $K_s(\ell)$.

Let $A$ be a fixed subset of $\{1,\dots,n\}$ with size $\ell$.

Let $B$ be a randomly chosen subset of $\{1,\dots,n\}$, uniformly chosen from subsets of size $s$.

Then $$ K_s(\ell)=\binom{n}s \mathbb E\left[(-1)^{|A\cap B|}\right]\tag{1} $$ This follows by computing $E\left[(-1)^{|A\cap B|}\right]$. A similar computation proves that $$ \langle K_s,K_r\rangle =\binom{n}s\binom{n}r\mathbb E\left[(-1)^{|A\cap B|}(-1)^{|A\cap C|}\right],\tag{2} $$ where

• $A$ is randomly chosen from all subsets of $\{1,\dots,n\}$,
• $B$ is randomly chosen from all subsets of $\{1,\dots,n\}$ of size $s$, and
• $C$ is randomly chosen from all subsets of $\{1,\dots,n\}$ of size $r$,

all independently of each other. Now, imagine you first choosen $B$ and $C$ randomly, and then choose $A$. There are two things that can happen:

• $B$ and $C$ are different sets. In this case, it is not hard to show the conditional expectation of $E\left[(-1)^{|A\cap B|}(-1)^{|A\cap C|}\right]$ given $B$ and $C$ is zero. Indeed, choosing any element $x$ of the symmetric difference $B\Delta C$, then flipping whether or not $x\in A$ will flip the sign of $E\left[(-1)^{|A\cap B|}(-1)^{|A\cap C|}\right]$.

• $B$ and $C$ are the same set, which is only possible when $r=s$. This happens with probability $1/\binom{n}s$, and in these cases, $E\left[(-1)^{|A\cap B|}(-1)^{|A\cap C|}\right]=1$ surely.

The preceding two bullets, combined with $(2)$, imply that $\langle K_s,K_r\rangle$ is zero when $r\neq s$, and $\binom{n}s$ when they are equal.

The same interpretation proves $$\frac{K_s(r)}{\binom{n}{s}}=\frac{K_r(s)}{\binom{n}r}$$

Both sides are equal to $\mathbb E\left[(-1)^{|A\cap B|}\right]$, where $|A|=r$ and $|B|=s$. The only difference is whether $A$ is fixed and $B$ is random, or the other way around, but this makes no difference to the expectation.