Why do these expressions tend to zero?

Question

1. In a chapter on Markov chains, it is claimed that $\binom {2n}{n} p^n(1-p)^n$ (where $p$ is a probability) tends to $0$ as $n$ tends to $\infty$. But why is this so?

2. It is also claimed that for an unrestricted simple random walk where the only possible steps are $+1$ or $-1$, all n-step transition probabilities tend to $0$ as $n$ tends to $\infty$. Again, why is this so?

Answer 1

1. We can show that ${2n \choose n}p^n(1-p)^n \rightarrow 0$ as $n \rightarrow \infty$ by the ratio test. Let $a_n = {2n \choose n}p^n(1-p)^n$, then $$ \lim_{n \rightarrow \infty}\frac{a_{n+1}}{a_n} = \lim_{n \rightarrow \infty} p(1-p) \frac{(2n+2)(2n+1)} {(n+1)^2} = 4p(1-p) $$ Since $p$ is a probability, $4p(1-p) \leqslant 1$, if $p \neq \frac{1}{2}$, we're done and the ratio test is successful. If $p = \frac{1}{2}$, the ratio test is inconclusive, and this actually gets very tricky indeed. I'm not sure how to resolve that.

2. This second part is, naturally, closely related to the first, but we must also assume that $p \notin \{0,1\}$. Suppose we take $t$ steps from our starting point $x_0$. Let $X_t$ be the random variable representing the state at time $t$. If we make $i$ upward steps, then our final resting place is $x_0 + i - (t-i) = x_0 + 2i - t$. The number of upward steps we make is distributed binomially, so we can show that $$ \mathbb{P}(X_t = x_0 - t + 2i) = \begin{cases} {t \choose i}p^i(1-p)^{t-i} & \mbox{for $i \in \{0,1,...,t\}$} \\ 0 & \mbox{otherwise} \end{cases} $$ We now adapt the argument from part 1. Fix an $i$ and let $t$ tend to infinity. We can assume that $i<t$. Let $a_t = {t \choose i}p^i(1-p)^{t-i}$, then $$ \lim_{t \rightarrow \infty}\frac{a_{t+1}}{a_t} = \lim_{t \rightarrow \infty} (1-p) \frac{t+1} {t+1-i} = (1-p) $$ Since $0< p < 1$, $|(1-p)| < 1$, and these probabilities again tend to 0.

In the edge cases where either $p=0$ or $p=1$, the random walk just runs off in some direction or other, and we know its exact location after $t$ steps. The probabilities become Kronecker deltas, which trivially tend to 0.

Answer 2

We will use the result

if $\lim_{n\to \infty} \frac{a_{n+1}}{a_n}=a $ and $|a|<1$, then $\lim_{n\to \infty}{a_n}=0$.

Let

$$ a_n = \binom {2n}{n} p^n(1-p)^n \implies \frac{a_{n+1}}{a_n}= {\frac { 2p(1-p)\left( 2\,n+1 \right) }{(n+1)}}. $$

Taking the limit of the last expression

$$ \lim_{n\to \infty} \frac{a_{n+1}}{a_n}= 4 p(1-p).$$

Now, note that, $f(p)=4p(1-p)<1$ for $0<p<1$ and $p\neq \frac{1}{2}$. It is clear that $p=\frac{1}{2}$ is a special case since $\lim_{n\to \infty} \frac{a_{n+1}}{a_n} = 1$.

Answer 3

Using the asymptotic expansion (either via Stirling or Catalan number $C_n$): $$\binom {2n}{n} = 4^n \left(\frac{1}{\sqrt{n \pi}}+ O\left(n^{-\frac{3}{2}}\right)\right)$$ you get with $p(1-p) \le \frac{1}{4}$ for $0\le p\le 1$ an asymptotic estimate for your expression $$\binom {2n}{n} p^n(1-p)^n = \binom {2n}{n} \left(p(1-p)\right)^n \le \frac{1}{\sqrt{n \pi}}$$

Answer 4

Since $p(1-p)\le \frac14$ it suffices to show ${2n\choose n}4^{-n}\to 0$. This is the probability of getting exactly $n$ tails with a fair coin in $2n$ tosses. The probability of $n+k$ tails is ${2n\choose n+k}4^{-n}={2n\choose n}4^{-n}\cdot \frac{n(n-1)\cdots(n-k+1)}{(n+1)(n+2)\cdots (n+k)}$. For fixed $k$ the fraction on the right tends to $1$ as $n\to\infty$, hence for sufficiently big $n$, we have If $n$ is big enough, ${2n\choose n+k}4^{-n}>\frac12 {2n\choose n}4^{-n}$. From this we find by adding probabilities that for any $k$ that $(1+\frac k2){2n\choose n}4^{-n}<1$ for $n$ big enough.