Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The left hand side is just 1; I think you need to fix something in the problem statement. –  lyj Jan 22 '13 at 15:45
    
@lyj, the sum is over such k which divide m. –  Guest 86 Jan 22 '13 at 15:46
    
What happens if $m>n?$ –  lab bhattacharjee Jan 22 '13 at 15:48
    
I see now. @lab, it is in the limit as $n\to \infty.$ –  lyj Jan 22 '13 at 15:48
1  
The problem may be restated as follows: prove that $\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} $ for a fixed integer $m$ and $p \in [0,1]$. –  Ron Gordon Jan 22 '13 at 16:01

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
Notice that $\left|(1-p)\times 1 + p\times\omega^k\right| < 1$ if $0 <k < m$. Hence, taking limits as $n \to \infty$ in your last equation yields the result. –  Siméon Jan 23 '13 at 9:48
    
I was thinking along those lines too, but $\lvert \omega^k - 1 \rvert$ can grow up to 2 (think $m$ even, then one of the roots is -1). –  vonbrand Jan 23 '13 at 11:12
    
$1+p(\omega^k - 1) = (1-p)\times 1 + p\times \omega^k$ is a barycenter with positive coefficients, hence lies on the line between $1$ and $\omega^k$. –  Siméon Jan 23 '13 at 11:22

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).

share|improve this answer
    
I tried something like that, but AFAICS it just leads back to the starting point. –  vonbrand Jan 23 '13 at 11:10

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}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.