# Does this sequence converge? If yes, what is the limit?

Assume $\{k_n\}_{n\geq 0}$ a sequence of natural numbers such that

1. $k_0=0$,

2. $k_n\leq k_{n+1}\leq k_n+1$, and

3. $\lim_{n\rightarrow\infty} \frac{k_n}{n}=\alpha\in(0,1)$.

So $\{k_n\}$ is an increasing sequence but it difference between two successive ones is at most 1. Hence notice $k_n\leq n$ for all $n$.

Define $$x_n\equiv\left(\begin{array}{c}n\\k_n\end{array}\right)\alpha^{k_n}(1-\alpha)^{n-k_n}.$$ Does $\{x_n\}$ converge? If it converges, what is its limit?

Here is the background of this question. I come across this question while considering Bernoulli trials in probability. Assume a coin is infinitely tossed. Experiments are independent and identically distributed. The probability of Head in each experiment is $\alpha\in(0,1)$. Then let $P_n$ be the distribution of number of heads in the first $n$ trials. It is straightforward to calculate $$P_n(k)=\left(\begin{array}{c}n\\k\end{array}\right)\alpha^k(1-\alpha)^{n-k}.$$ Now, let $K_n$ be the random variable of number of heads in the first $n$ trials. So $P_n$ is just the distribution of $K_n$ and by strong law of large numbers we know $$\lim_{n\rightarrow\infty}\frac{K_n}{n}=\alpha\quad a.s.$$ Then my question is whether $\{P_n(K_n)\}_{n\geq 0}$ converges almost surely? If yes, is it possible to calculate its limit?

• I guess this sequence indeed converges almost surely to 0. – user111463 Apr 19 '15 at 21:21
• The limit is zero and $x_n\sqrt{2\pi\alpha(1-\alpha)n}\to1$. The simplest approach might be to apply Stirling formula. An indirect approach is to use the central limit theorem since $(K_n-\alpha n)/\sqrt{n}$ converges to a nondegenerate gaussian distribution. Note that, for every fixed $\alpha$, $$\lim_{n\to\infty}\sup_k{n\choose k}\alpha^k(1-\alpha)^{n-k}=0.$$ – Did Apr 19 '15 at 21:22
• Thanks! I used Stirling approximation to get 0 limit. But could you please elaborate more on the approach of using central limit theorem? it seems to me there is a gap between almost sure convergence and weak convergence. Thanks! – user111463 Apr 19 '15 at 21:27
• For every fixed $z>0$, $[K_n=k_n]\subset[|K_n-\alpha n|<z\sqrt{n}]$ for every $n$ large enough hence $$\limsup P(K_n=k_n)\leqslant \lim P(|K_n-\alpha n|<z\sqrt{n})=P(|Z|<z),$$ for some centered gaussian $Z$ with suitable variance. Finally, $\inf\limits_{z>0}P(|Z|<z)=0$ hence $$\lim P(K_n=k_n)=0.$$ – Did Apr 19 '15 at 21:30
• I see. Thank you very much. I did not realize that we can think about this question path by path. – user111463 Apr 19 '15 at 21:37