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).

  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ What does N large mean? I'm dealing with Ns between 10 and 100, usually. Would the simplification still apply? $\endgroup$ – Tudor Timi Nov 27 '14 at 16:13
  • $\begingroup$ 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)$. $\endgroup$ – Did Nov 27 '14 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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