Problem of limit with binomial coefficients

Question

I thought that the following would made a nice exercise, but I am not sure how to evaluate its difficulty since I often miss elementary solutions. How about you try answering it? It would be great to have several proofs.

Let $m$ be a positive integer and $p \in (0,1)$. Prove that $\displaystyle \lim_{n\to\infty}\underset{m\mid k}{\sum_{0 \leq k \leq n}} \binom{n}{k}p^{k}(1-p)^{n-k} = \frac{1}{m}$.

I give two proofs of this limit below, but I am still interested in elementary proofs.

---

Edit 1. As noted by @rlgordonma, the sum is $\lim_{n \rightarrow \infty} \sum_{\ell = 0}^{\lfloor \frac{n}{m} \rfloor} \binom{n}{\ell m} p^{\ell m} (1-p)^{n - \ell m} = \frac{1}{m}$. Maybe it makes things clearer like that.

---

Edit2. Thank you for your participation. I will now give two proofs of this limit (one of them being a reformulation of vonbrand's solution). In fact, I will prove a little more:

$$\forall r \in \{0,\dots,m-1\},\qquad\lim_{n\to\infty} \sum_{\substack{0 \leq k \leq n\\ k \equiv r\; [m]}} \binom{n}{k}p^k(1-p)^k = \frac{1}{m}$$

Step 1 (probabilistic interpretation).

This step is not necessary, but I think it brings a better insight. Let $X_1,X_2,\dots$ be a sequence of independent Bernoulli random variables with parameter $0 < p <1$, that is $P(X_i=1)=1-P(X_i=0)=p$.

Then $S_n = X_1 + \dots+ X_n$ is a Binomial random variable with parameters $(n,p)$, and the sum we are interested in is just: $$\sum_{\substack{0 \leq k \leq n\\ k \equiv r\; [m]}} \binom{n}{k}p^k(1-p)^k = P(S_n \equiv r\;[m]).$$ The sequence $(S_n)$ is a random walk over $\mathbb{Z}$ but since we are only interested in its residue modulo $m$ it will be better to see it as a random walk over $\mathbb{Z}/m\mathbb{Z}$ (with an abuse of notation, we will still write $S_n$ for this residue).

Step 2 (limit behaviour of the random walk). Quick version, with Markov Chains

The random walk $(S_n)$ is an irreducible (and aperiodic) Markov Chain over the finite state space $\mathbb{Z}/m\mathbb{Z}$ with transition matrix given by $Q(i,i)=1-p$ and $Q(i,i+1)=p$ for $i \in \mathbb{Z}/m\mathbb{Z}$. It admits the uniform distribution as a stationnary distribution, hence it converges to this distribution. QED

Step 2 (bis). Without Markov Chains

The following result (inversion formula for the discrete Fourier transform) is a generalization of @vonbrand's trick:

Note $S = \{0,\dots,m-1\}$ and $\omega=\exp\left(i2\pi/m\right)$. For every function $f \colon S\to \mathbb{C}$ and every $x \in S$, $$ f(x) = \sum_{k = 0}^{m-1} \widehat{f}(k)\,\omega^{kx},\qquad\text{where}\quad \widehat{f}(k) = \frac{1}{m}\sum_{x=0}^{m-1}f(x)\omega^{-kx}. $$

In particular, we have $$ E(f(S_n)) = \sum_{k=0}^{m-1}\widehat{f}(k)\,E\left[\omega^{k S_n}\right] $$ The sequence $X_1,X_2,\dots$ being i.i.d., $$ E\left[\omega^{k S_n}\right] = \left(E\left[\omega^{k X_1}\right] \right)^n = ((1-p)+p\omega^k)^n \xrightarrow[n\to\infty]{}\begin{cases}1 & \text{if } k=0\\0 & \text{else}\end{cases} $$ Hence, $\lim_{n\to\infty} E[f(S_n)] = \widehat{f}(0)$. Taking $f(x) = 1_{\{x = r\}}$ yields the result.

Answer 1

There is a nice trick to select just the terms divisible by $m$ in a series. Let $A(z) = \sum_{k} a_n z^n$. Take now $\omega$ as a primitive $m$-th root of 1, i.e., $\omega = \exp(2 \pi i / m)$. It is easily checked that $1 + \omega + \omega^2 + \ldots + \omega^{m - 1} = 0$ and also $\omega^m = 1$. Take now: $$ A(z) + A(\omega z) + \ldots + A(\omega^{m - 1} z) = \sum_{n \ge 0} a_n z^n (1 + \omega^n + \omega^{2 n} + \ldots + \omega^{(m - 1) n}) $$ But by the above, if $m \mid n$, the sum in parentesis is $m$, else it is 0, and only those terms survive.

Applying this to the specific case (no convergence problems, the sum looks infinite but is really finite): $$ S(z) = \sum_{k \ge 0} \binom{n}{k} p^k (1 - p)^{n - k} z^k = (1 - p (z - 1))^n $$ The original sum is just: $$ S_{n,m} = \sum_{\substack{k \ge 0\\m \mid n}} \binom{n}{k} p^k (1 -p)^{n - k} = \frac{1}{m} \sum_{0 \le k < m} \left(1 + p (\omega^k - 1) \right)^n $$ It looks plausible that the last sum is just 1, but I'm stumped here.

Edit: Thanks to the comment by @Ju's, I saw the light: When $k = 0$, the term is just $1^n = 1$. Otherwise, by the triangle inequality we have: $$ \lvert 1 + p (\omega^k - 1) \rvert = \lvert (1 - p) + p \omega^k \rvert < (1 - p) + p = 1 $$ The inequality is strict, because $\omega^k$ is not in the direction 1. Then: $$ \lim_{n \rightarrow \infty} \sum_{0 \le k < m} (1 + p (\omega^k - 1))^n = 1 + \lim_{n \rightarrow \infty} \sum_{1 < k < m}(1 + p \omega^k - 1))^n = 1 $$ Edit: To select terms where $n \equiv r \mod{m}$ do as above, but go: $$ A(z \omega^{m - r}) + A(z \omega^{m - r + 1}) + \ldots + A(z^{r - 1}) $$ The rest of the proof goes through just as before.

Answer 2

I present a heuristic justification now, I will work our the details later, I feel that this can be worked out exactly as in the proof of DeMoivre-Laplace theorem which goes through almost identical steps.

The needed result should follow from the normal approximation to the binomial probability mass function.

The following "local approximation" holds for a "sufficiently large" range of $k$ $$\binom{n}{k}p^{k}q^{n-k} \approx \dfrac{1}{\sqrt{2\pi npq}} \exp\left(- \frac{1}{2}\left(\dfrac{k -np}{\sqrt{n pq}}\right)^2 \right),$$ where by sufficiently large large range, I mean, the sum of terms outside this range vanishes in the limit, and the discrepancy due to the approximation also vanishes.

So our desired sum can be approximated as, $$ \sum_{ k } \binom{n}{mk}p^{mk}q^{n-mk} \approx \sum_{k} \dfrac{1}{\sqrt{2\pi npq}} \exp\left( - \frac{1}{2}\left(\dfrac{mk -np}{\sqrt{n pq}}\right)^2 \right).$$

Let $$ x_k = \dfrac{mk -np}{\sqrt{n pq} }, $$ then $$ \dfrac{ x_k - x_{k-1} } {m} = \dfrac{1}{\sqrt{ npq}}.$$

The approximation becomes a Riemann sum, $$ \frac{1}{m} \sum_{k} \frac{(x_k - x_{k-1})}{\sqrt{2\pi}} \exp \left( -\frac{x_k^2}{2} \right) \to \frac{1}{m}\int_{-\infty}^{\infty} \frac{1}{\sqrt{2\pi}}\exp \left(-\frac{x^2}{2}\right) dx = \frac{1}{m}.$$

Answer 3

Continuing vonbrand's multisection approach, we want to show that $T=\sum_{0 \le k < m} (1 + p (w^k - 1) )^n =1$, where $w$ is an $n$-th root of unity.

Summary of what follows: I get a sum for $T$ which does not appear to always be 1. However, I am entering this is case either (1) I have made an error which is fixable or (2) my result is correct and the limit of my result approaches 1 for large $n$.

Let $q = 1-p$ and $C(n, j) = n!/(j! (n-j)!)$. Then

$\begin{align} T &= \sum_{0 \le k < m} (1 + p (w^k - 1) )^n \\ & = \sum_{0 \le k < m} (1-p + p w^k )^n \\ & = \sum_{0 \le k < m} (q + p w^k )^n \\ & = \sum_{0 \le k < m} \sum_{0 \le j < n}C(n, j) q^{n-j} p^j w^{kj} \\ & = \sum_{0 \le j < n} \sum_{0 \le k < m}C(n, j) q^{n-j} p^j w^{kj} \\ & = \sum_{0 \le j < n} C(n, j) q^{n-j} p^j\sum_{0 \le k < m} w^{kj} \\ \end{align} $

The innermost sum is a geometric series: $\sum_{0 \le k < m} w^{kj} = \frac{w^{j m}-1}{w^j-1} $ when $w^j \ne 1$ and $m$ when $w^j = 1$.

$w^j = 1$ only when $j = 0$, so

$\begin{align} T &= m q^n + \sum_{0 < j < n} C(n, j) q^{n-j} p^j \frac{w^{j m}-1}{w^j-1}\\ \end{align} $.

(I'm just flailing now, so look at special cases)

If $m = 1$, then $T = 1$ by the binomial theorem.

If $m = 2$,

$\begin{align} T &= 2 q^n + \sum_{0 < j < n} C(n, j) q^{n-j} p^j \frac{w^{2j}-1}{w^j-1}\\ &= 2 q^n + \sum_{0 < j < n} C(n, j) q^{n-j} p^j (w^j+1)\\ &= 2q^n + \sum_{0 < j < n} C(n, j) q^{n-j} p^j+ \sum_{0 < j < n} C(n, j) q^{n-j} p^j w^j\\ &= \sum_{0 \le j < n} C(n, j) q^{n-j} p^j+ \sum_{0 \le j < n} C(n, j) q^{n-j} p^j w^j\\ &= (p+q)^n + (q+p w)^n \\ &= 1 + (q+p w)^n \\ \end{align} $.

For $n=2$ (where $w = -1$ - I originally said that $w = i$, my mistake),

$T = 1 + (q-p )^2 = 1 + (1-2p )^2 $,

and this is $not\ 1$ unless $p = 1/2$ (unless I have made a mistake, which I think is highly likely).