Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Picking n numbers at random
Replies: 8   Last Post: Mar 13, 2012 2:06 AM

 Messages: [ Previous | Next ]
 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.

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

Date Subject Author
3/11/12 Jose Carlos Santos
3/11/12 Frederick Williams
3/11/12 bert
3/11/12 Jose Carlos Santos
3/11/12 quasi
3/11/12 quasi
3/11/12 Jose Carlos Santos
3/13/12 Ray Koopman
3/12/12 Tim Little