Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Look at the ratio of the probabilities. –  André Nicolas Dec 10 '11 at 0:20

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.