1
$\begingroup$

Given an integer n, and an event n that happens with $P(\frac{1}{n})$, is the probability that e will happen in n trials bounded by any constant?

For example, if I had an n-sided fair die and a target value t, can I say with certainty that regardless of the value of n, the odds of rolling a t in n rolls are no worse than $\frac{1}{x}$ for some constant x?

2 Answers 2

6

$1-\left(\frac{n-1}n\right)^n\gt\lim\limits_{k\to\infty}1-\left(\frac{k-1}k\right)^k=1-\frac1{\mathrm e}=0.632$

  • 0
    @philosodad Thank you. Part of my problem was my incorrect assumption that my answer came first and by a large amount of time. I was wrong. So i shouldn't be very upset with you or with "did". Sorry for making such a big fuss! However "did" apparently did not appreciate that you were looking for an upper bound.2012-07-10
1

If P(e)=1/n on any trial and trials are independent then the probability that e occurs at least once in n trials is 1- probability that it does occur in n trials =1 - [(n-1)/n]$^n$. This converges to 1-exp(-1) = [exp(1)-1]/exp(1). The convergence is from above but for large enough n take the limit plus a small ε for the bound.