The problem is to find the following limit:

$$\lim_{n \to +\infty}\sum\limits_{k=n}^{3n} \binom{k-1}{n-1} \left(\dfrac{1}{3}\right)^n \left(\dfrac{2}{3}\right)^{k-n}$$

I see that it looks similarly to the formula from the binomial theorem, but don't get how we can make use of it.

Any ideas would be greatly appreciated.

  • $\begingroup$ AFAIK, there is no standard way to use the $C_i^j$ symbol. By $C_{k-1}^{n-1}$, do you mean the number of ways to choose $k-1$ things from $n-1$ things? If so, note that all terms other than the first one in the sum are zero. If you mean the reverse, note that each term in the sum is non-negative, so the sum itself is at least $\binom{3n-1}{n-1} 2^{2n}/3^n$ (which is the very last term), which goes to infinity with $n$. $\endgroup$ – stochasticboy321 Apr 10 '17 at 3:35
  • 1
    $\begingroup$ @stochasticboy321 I meant the latter one (edited the question accordingly). But the upper bound you provided is not correct - in denominator there should be $3^{3n}$. $\endgroup$ – Ramil Apr 10 '17 at 3:59
  • $\begingroup$ I would suggest trying to find a combinatorial interpretation for the sum - an individual term is, for instance, $\frac nk$ times the probability of rolling exactly $n$ 1s in $k$ rolls of a 3-sided die. $\endgroup$ – Steven Stadnicki Apr 10 '17 at 6:14

The sum over all integers is $$ \begin{align} \sum_{k=n}^\infty\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n} &=\left(\frac13\right)^n\sum_{k=n}^\infty(-1)^{k-n}\binom{-n}{k-n}\left(\frac23\right)^{k-n}\\ &=\left(\frac13\right)^n\sum_{k=0}^\infty\binom{-n}{k}\left(-\frac23\right)^k\\ &=\left(\frac13\right)^n\left(\frac13\right)^{-n}\\[9pt] &=1\tag{1} \end{align} $$ Furthermore, $$ \frac{\binom{k}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n+1}}{\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n}}=\frac23\frac{k}{k-n+1}\tag{2} $$ which is $1$ when $k\approx3n$. That is, the summand is at its maximum near $k\approx3n$. By the method of Laplace, the sum to the maximum tends to one half the total sum, so we get that $$ \bbox[5px,border:2px solid #C0A000]{\lim_{n\to\infty}\sum_{k=n}^{3n}\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n}=\frac12}\tag{3} $$

Application of Laplace's Method

Let $$ f_n(k)=\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n}\tag{4} $$ From $(3)$, we can derive that for $k-3n=O\!\left(\sqrt{n}\right)$, $$ \begin{align} \log(f_n(k+1))-\log(f_n(k)) &=\log\left(\frac23\frac{k}{k-n+1}\right)\\ &=\log\left(\frac{1+\frac{k-3n}{3n}}{1+\frac1{6n}+\frac{k-3n}{2n}}\right)\\ &=\log\left(1-\frac{k-3n}{6n}\right)+O\!\left(\frac1n\right)\\ &=-\frac{k-3n}{6n}+O\!\left(\frac1n\right)\tag{5} \end{align} $$ From $(5)$, we get that $$ f_n(k)=c\,e^{-\frac{(k-3n)^2}{12n}+O\left(\frac1{\sqrt{n}}\right)}\tag{6} $$ Since the sum for all $k$ of $f_n(k)$ is $1$, we get $$ f_n(k)=\frac1{\sqrt{12\pi n}}\,e^{-\frac{(k-3n)^2}{12n}}+O\!\left(\frac1n\right)\tag{7} $$ Since $(7)$ is symmetric about $k=3n$, the sum for $k\lt3n$ will be approximately the same as the sum for $k\gt3n$. Thus, the sum for $k\lt3n$ will be approximately $\frac12$.

  • $\begingroup$ Very nice! (+1) Could you provide a reference regarding the methods of stationary phase? $\endgroup$ – Markus Scheuer Apr 10 '17 at 15:51
  • $\begingroup$ @MarkusScheuer: actually, since the exponent is real, it should be Laplace's Method. That is, since $\frac23\frac{k}{k-n+1}=\frac{2(k-3n)+6n}{3(k-3n)+6n+1}\approx1-\frac{k-3n}{6n}$, we have $\binom{k-1}{n-1}\left(\frac13\right)^n\left(\frac23\right)^{k-n}\approx\frac1{\sqrt{12\pi n}}e^{-\frac{(k-3n)^2}{12n}}$ when $k\approx3n$. $\endgroup$ – robjohn Apr 10 '17 at 17:38
  • $\begingroup$ I see. Thanks a lot for the info. Best regards, $\endgroup$ – Markus Scheuer Apr 10 '17 at 18:38
  • $\begingroup$ Stationary Phase and Laplace's Method are related by a rotation in the complex plane. I sometimes cite one instead of the other. Note that I did add a link to my answer. $\endgroup$ – robjohn Apr 10 '17 at 23:47
  • $\begingroup$ Great, instructive elaboration! Many thanks! :-) $\endgroup$ – Markus Scheuer Apr 11 '17 at 5:34

Consider $\{\xi_i, i \in \mathbb{N}\}$ -- iid $\mathrm{Geom}\left(\frac13\right)$ variables ($\xi_i \geq 1$).

$$ \Pr\left(\sum\limits_{i = 1}^n \xi_i \leq 3n \right) = \sum\limits_{k = n}^{3n}\Pr\left(\sum\limits_{i = 1}^n \xi_i = k \right) = \sum\limits_{k = n}^{3n} \binom{k - 1}{n - 1}\left(\frac13\right)^n \left(\frac23\right)^{k - n} $$ It is so because we iterate from $n$ to $3n$ (these are the all possible variants for the sum of $n$ geometric variables). Then there are $\binom{k - 1}{n - 1}$ variants to have the needed sum (stars and bars method) and the probability of each variant is really obvious because all of the variables have $1/3$ in pmf and other sum in exponent is overall $k - n$.

So, our answer is (remember that $\mathsf{E}\xi_i = 3$)

$$ \lim\limits_{n \to +\infty} \Pr\left(\sum\limits_{i = 1}^n \xi_i \leq 3n \right) = \lim\limits_{n \to +\infty} \Pr\left(\sum\limits_{i = 1}^n (\xi_i - \mathsf{E}\xi_i) \leq 0 \right) = \lim\limits_{n \to +\infty}\Pr\left(\frac{\sum\limits_{i = 1}^n(\xi_i - \mathsf{E}\xi_i)}{\sqrt{n\mathsf{D}\xi_1}} \leq 0 \right) $$

The equation under the probability converges in distribution (due to central limit theorem) to $X \sim \mathcal{N}(0, 1)$ and obviously the limit is $1/2$ because $\Pr(X \leq 0) = \frac12$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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