# Given a probability distribution, how many times do I have to repeat an experiment so see a certain outcome

My question concerns random number generation under certain constraints. I assume that the random number generator is good enough to generate uniformly distributed numbers. This means that each number has the probability 1/N to occur. How many times should I repeat the experiment (generating a random number) such that it's is very likely that a see a certain number.

I think there was a theorem that could give me a value, given a certain bound on how certain I want to be that the event happened (i.e. if I want to be 50% certain that it appears I run it x times, if I want to be 99% certain I run it y times, with x < y).

• For uniform distributions I found out that the formula is x = log (p) / log ((N-1)/N), where x is the number of trials I need to get a p certainty level for a uniform distribution of N elements. – Tudor Timi Nov 26 '14 at 14:17

If each result is independent of the others, the probability to see some given result of probability $p$ at least once in $n$ results is $$1-(1-p)^n.$$ If $p=1/N$ with $N$ large, after $n\approx cN$ results, this is roughly $$1-\mathrm e^{-c}.$$ Thus, to get the result with probability at least $x$, one needs a number of results roughly $$-\log(1-x)\cdot N.$$ For $x=50\%$, this is $0.69\cdot N$. For $x=90\%$, this is $2.30\cdot N$. And so on.
• What does N large mean? I'm dealing with Ns between 10 and 100, usually. Would the simplification still apply? – Tudor Timi Nov 27 '14 at 16:13
• Exact formula: $$n=\log(1-x)/\log(1-1/N).$$ For $N=10$, this yields a factor $9.49$ instead of $10$, for $N=100$, $99.5$ instead of $100$, when $N\to\infty$, $N-\frac12+o(1)$. – Did Nov 27 '14 at 17:53