You're playing a game. You start with a box with one black marble and one white marble, and you sample twice with replacement. If you select the white marble both times, you win. If you select the black marble either time, you add another black marble and try again. On each round, you sample twice with replacement, winning if you select the white marble twice, otherwise adding another black marble and moving on to the next round.

What is the probability that you eventually win? Equivalently, if P(n) is the probability that you win on or before round n, what is the limit of P(n) as n -> infinity?

On each round, the probability of picking the white marble twice is 1/n^2, where n is the number of marbles.

For the sake of convenience, let me redefine P(n) as the probability that you win on or before the round consisting of n marbles (which would be round n-1 as defined by the problem).

P(n) = Prod_{i=2šn} (i^2-1)/(i^2)

Now we cancel terms using the fact that (i^2-1) = (i+1)(i-1)

P(n) =

1*3  *  2*4  *  3*5  *  ...  * (n-1)*(n+1)
-----------------------------------------------   =
2*2  *  3*3  *  4*4  *  ...  *       n*n

1     *  2     *  3     *  ...  * (n-1)*(n+1)
---------------------------------------------   =
2*2  *     3  *     4  *  ...  *          n

1     *  1     *  1     *  ...  *   1*(n+1)
--------------------------------------------   =
2     *     1  *     1  *  ...  *       n

(n+1)
-----
 2n

So Lim_{nš ‡} P(n) = Lim_{nš ‡} (n+1)/2n which is 1/2.

Posted by Avin on 2004-11-01 14:01:17