quasi
Posts:
9,088
Registered:
7/15/05
|
|
Re: Picking n numbers at random
Posted:
Mar 11, 2012 3:29 PM
|
|
On Sun, 11 Mar 2012 17:41:40 +0000, José Carlos Santos
<jcsantos@fc.up.pt> wrote:
>Let _n_ be an integer greater than 1. Suppose that you pick a
>number at random from 1 to _n_ and that you do that again and
>again, your goal being to have picked each number from
>1 to _n_ at least once. How many times do you have to pick a
>number at random in order that your chance of success becomes
>50% at least?
Fix a positive integer n.
Let p(m,k) be the probability of getting at least one occurrence
of all n values in m attempts if exactly k out of the n values
have not yet occurred.
With this formulation, your problem can be interpreted as asking
for the least value of m such that p(m,n) >= 1/2.
The function p satisfies the recursion
p(m,k) = (k/n) p(m-1,k-1) + ((n-k)/n) p(m-1,k)
together with the boundary conditions
p(m,0) = 1 for all m
p(m,k) = 0 if m < k
Also, to shorten the calculation, you also have
p(k,k) = 1/C(n,k)
p(m,1) = 1 - ((n-1)/n)^m
I doubt hat you can solve the recursion symbolically, although
you might be able to use the recursion to get asymptotic bounds.
For an exact numerical solution, the recursion is workable as
long as n is not too big.
For small values of n, say n < 8, it's not unreasonable to work
through the recursion numerically by hand.
For medium values of n, say n < 10^8, you could solve the
recursion numerically using a computer.
As an alternative to solving the recursion, you could set up a
computer simulation.
quasi
|
|
