Using Stirling’s Formula, prove that \[{2n \choose n} \sim \frac{2^{2n}}{\sqrt{ \pi n }}\]
We know \[n! \sim \sqrt{ 2\pi n } \left( \frac{n}{e} \right)^{n}\].
Therefore \[ n! n! \sim 2 \pi n \left( \frac{n}{e} \right)^{2n}\]
Doing the same for \((2n)!\):
\[(2n)! \sim \sqrt{ 2\pi 2n } \left( \frac{ 2n }{e }\right)^{2n} = 2 \sqrt{\pi n} \left( \frac{2n}{e} \right)^{2n}\]
Finally, combining the above terms:
\[ {2n \choose n} = \frac{ 2n!}{n! n!} \sim 2 \sqrt{ \pi n } \left( \frac{ 2n }{e} \right)^{2n} \frac{1}{2\pi n} \left( \frac{e}{n}\right)^{2n}\] This simplifies to: \[{2n \choose n } \sim \frac{2^{2n}}{\sqrt{\pi n} } \] which proves the result.
Assume in the gambler’s ruin problem, \(p=q=1/2\).
Using Equation 12.7, togther with the fact that \(q_0 = 1\) and \(q_M = 0\), show that for \(0 \leq z \leq M\), \[ q_z = \frac{ M- z}{M}\]
Using Equation 12.8, let \(p \rightarrow 1/2\) show that in the limit \[ q_z = \frac{M-z}{M}\] Hint: Use L’Hopital’s rule
Denoting the probability \(q_k\) of ruin given starting wealth \(k\), equation 12.7 states:
\[ q_{k+1} - q_{k} = \left( \frac{q}{p} \right)^{k} (q_{1}-q_{0})\]
Since \(q = p = 1/2\), this identity collapses to:
\[ q_{k+1} - q_{k} = q_1 - q_0 \]
Using the telescoping sum \[(q_M - q_{M-1}) + ( q_{M-1}- q_{M-2}) + \ldots + (q_1 - q_0) = (q_1 - q_0) + ( q_1 - q_0) + \ldots + (q_1-q_0)\]
We get the identity \[\begin{align} q_M - q_0 & = M ( q_1 - q_0) \\ 0 - 1 & = M ( q_1 - 1) \\ q_1 & = 1 - \frac{1}{M} \\ \end{align} \]
A similar argument gives:
\[ q_k - q_0 = k ( q_1 - q_0) = k ( 1 - \frac{1}{M} - 1) \]
This simplifies to \[\begin{align} q_k - 1 & = & k ( \frac{1}{M}) \\ q_k & = & 1 - \frac{k}{M} \\ q_k & = & \frac{ M - k }{M} \\ \end{align} \] This completes the proof.
First we use the identity 12.8 which is equivalent to:
\[\begin{align} q_z & = 1- \frac{ (q/p)^z - 1 }{(q/p)^{M} - 1 } \\ & = 1- \displaystyle \lim_{p \to 1/2} \frac{ (\frac{ 1 - p}{p})^z - 1 }{ (\frac{ 1-p}{p} )^{M} - 1 } \text{ by substituting q=1-p}\\ \end{align} \]
By applying L’Hopital’s rule to the right hand side:
\[ \begin{align} q_z & = 1- lim_{p \to 1/2} \frac{ z \left( \frac{1- p}{p} \right)^{z-1} (-p^{-2}) }{ M \left( \frac{1- p}{p} \right)^{M-1} (-p^{-2}) } \\ q_z & = 1- \lim \frac{ z}{M} \left( \frac{ 1-p}{p} \right)^{z-M} \\ q_z & = 1- \frac{z}{M} \left( lim_{p \to 1/2} \frac{1-p}{p} \right)^{z-M} \\ q_z & = 1- \frac{z}{M} \left( \frac{ 1/2}{1/2} \right)^{z-M} \\ q_z & = 1- \frac{z}{M} \cdot 1 \\ q_z & = 1- \frac{z}{M} \\ \end{align} \] This completes the proof.