# Probability about two types of games.

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?

-
Look at the ratio of the probabilities. –  André Nicolas Dec 10 '11 at 0:20

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}\;.$$