Math Is Fun Forum

swarm

Member

Registered: 2008-08-24

Posts: 2

random draw probability

(edited for clarification)

I happened upon an interesting problem, and solved it, however I believe there must be an easier way to do it.  I'll present the problem and then my solution, and maybe someone can enlighten me of a simpler way.

4 balls labeled 1,2,3,4 are in a bin, and are drawn one at a time with replacement (meaning each draw is independent and has the same possible outcomes).  When all four numbers have appeared at least once, "success" has occured.  What is the probability of success after N number of draws?  For instance, for N=4 draws it is just (1 * 3/4 * 1/2 * 1/4) . 

In other words, come up with a function that takes an integer N and returns the percentage chance that all numbers have made an appearance by draw N.

I solve this problem with a matrix A:

0  0   0   0   0
1 .25  0  0   0
0 .75 .5  0   0
0  0   .5 .75 0
0  0   0  .25 1

If you raise A to the N, and then multiply it by the vector [ 1 0 0 0 0], the resulting vector will be the probabilities to be in each state, with the final value in the vector being the "finished" state (a.k.a. all numbers have appeared).

Is there a simple way to do this problem?  It doesn't seem like it should require linear algebra.. but I haven't been able to figure out another way.

Thanks a lot!

Last edited by swarm (2008-08-27 06:42:08)

krassi_holmz

Real Member

Registered: 2005-12-02

Posts: 1,905

Re: random draw probability

What does "with a replacement" means? Is it you take a ball, observe it and put it back, or what?

---

IPBLE:  Increasing Performance By Lowering Expectations.

swarm

Member

Registered: 2008-08-24

Posts: 2

Re: random draw probability

Yes, it just means the numbers can occur any amount of times.   Like a random number generator, same concept.  A sequence could be:

4 4 1 2 3 4 2 3 1  and so on

John E. Franklin

Member

Registered: 2005-08-29

Posts: 3,588

Re: random draw probability

Hmmm....  You got me thinking hard for a long time.
I gotta figure out a way to get rid of the duplicates in my generality.
I'll get back to you if I figure out something.

---

igloo myrtilles fourmis