2
$\begingroup$

Suppose there are two games.

  1. Toss a fair coin $n$ times and win if all tosses are heads.

  2. Toss a fair $n$-sided die $n$ times and win if all tosses are different.

When $n$ is large ($n\rightarrow\infty$), which game gives a better chance of winning ?


I've done some calculations but some of part my calculation bothers me.

Here is what I got:

$P(Win\:\:Game\:1) = \dfrac{1}{2^n}$

$P(Win\:\:Game\:2) = \dfrac{n!}{n^n}$

But as $n$ goes to infinity, all of two equations goes to 0. Then how can we compare the chances of winning?

  • 4
    Look at the ratio of the probabilities.2011-12-10

1 Answers 1

2

As André suggested, look at $\frac{\mathbb{P}(\text{Win Game 2})}{\mathbb{P}(\text{Win Game 1})}=\frac{n!/n^n}{2^n}=\frac{2^n n!}{n^n}\,.$ Specifically, look at its limit as $n\to\infty$. If you know Stirling’s approximation, this limit is very easy to evaluate. If not, you can still evaluate it with techniques from elementary calculus, though the factorial requires a little ingenuity.

All those products suggest taking logs and looking at $\ln\left(\frac{2^n n!}{n^n}\right)=\ln n!+n(\ln 2-\ln n)=\sum_{k=1}^n\ln k+n\ln 2-n\ln n\;.$

The summation is a bit annoying, but we can use the fact that $\ln k\le\int_k^{k+1}\ln x dx$ for $k\ge 1$ to get $\sum_{k=1}^n\ln k\le\int_1^{n+1}\ln x\, dx=[x\ln x-x]_1^{n+1}=(n+1)\ln(n+1)-n$ and therefore

$\begin{align*} \ln\left(\frac{2^n n!}{n^n}\right)&\le(n+1)\ln(n+1)-n+n\ln 2-n\ln n\\ &=\Big((n+1)\ln(n+1)-n\ln n\Big)-n(1-\ln 2)\\ &=\Big((n+1)\ln(n+1)-n\ln(n+1)\Big)+\Big(n\ln(n+1)-n\ln n\Big)-n(1-\ln 2)\\ &=\ln(n+1)+n\Big(\ln(n+1)-\ln n\Big)-n(1-\ln 2)\\ &=\ln(n+1)+n\ln\left(1+\frac1n\right)-n(1-\ln 2)\;. \end{align*}$

The limit of this expression as $n\to\infty$ can be evaluated by first-semester calculus techniques, and you can use it to get $\lim_{n\to\infty}\frac{2^n n!}{n^n}\;.$