I am having difficulty approaching the above problem, and would like a hint. I tried doing an inclusion exclusion argument: Let $A_{i}$ be winning the game on the i'th try, then by inclusion exclusion we have, for winning at least 1 game in n tries: $$P\left(\bigcup_{i=1}^{n}A_i\right)=\frac{n}{N}-{n\choose 2}\frac{1}{N^2}+{n\choose 3}\frac{1}{N^2}+.....\pm \frac{1}{N^{n}} $$ unless I am missing something, I don't see how I could evaluate numerically the probability without knowing the value of $N$ edit: We have spent a fair amount of time on stirling's formula, so maybe this would be a way to at least make sense of the choose function portion?
Asked
Active
Viewed 94 times
6
-
6Hint: The probability of always losing is $\left(1-\frac{1}{N}\right)^n$. – André Nicolas Apr 28 '16 at 04:40
-
Boy did I over complicate that – operatorerror Apr 28 '16 at 04:41
-
1@qbert, you missed a simplification, which is not the same as complicating. Take note, computing the probability of the complementary event is often a good choice – Rolazaro Azeveires Dec 20 '16 at 21:21
1 Answers
6
using André's suggestion, we want $\left(1-\frac{1}{N}\right)^{n}\leq .5 \Rightarrow n\ln\left(1-\frac{1}{N}\right)\leq \ln(.5)\Rightarrow \frac{\ln\left(1-\frac{1}{N}\right)}{\ln(.5)}\leq n$ so for any $n\geq \left\lceil\frac{\ln(1-\frac{1}{N})}{\ln(.5}\right\rceil$ we will have a greater than 50% chance of winnning.
operatorerror
- 29,103