You have a magic coin.
The first time you flip the coin it will land heads up.
The second time you flip the coin it will land tails up.
Every time you flip the coin after that, the probability that the coin will land heads up is proportional to the number of "heads up" that "run".

So for example, the probability of the third toss landing heads up is 1/2.
If the third toss is heads, then the probability of the fourth toss landing heads is 2/3, otherwise the probability of landing heads is only 1/3.
And so on.

Find the probability that the coin will land "heads up" exactly 42 times in the first 100 tosses (in a single run).

Source: NCH contest

Let's denote the probability of ending turn N with exactly H heads as P(N,H). 

You can end turn N with exactly H heads in two ways: either you end the prior turn with H-1 heads and flip a head, or you end the prior turn with H heads and you flip a tail.

First we observe that P(N,1) = P(N,N-1) = 1/2 * 2/3 * 3/4 * ... * (N-2)/(N-1) = 1/(N-1)

For all other H, such that 1 < H < N-1, we see that P(N,H) = P(N-1,H-1) * (H-1)/(N-1) + P(N-1,H)(N-1-H)/(N-1).

We know that P(3,1) = P(3,2) = 1/2.

Assume that P(N,k-1) = P(N,k) for all N and k.

Then we see that P(N,k) = P(N-1,k) * (k - 1 + N - 1 - k)/(N-1) = P(N-1,k) * (N-2)/(N-1)

So P(N,k) depends only on N and not on k.  Specifically, P(N,k) = (N-2)/(N-1) * (N-3)/(N-2) * (N-4)/(N-3) * ... * 1/2 = 1/(N-1).

For this example, we see recursively that P(100,42) = 98/99 * P(99,42)

= 98/99 * 97/98 * P(98,42) = 97/99 * P(98,42)

= 97/99 * 96/97 * P(97,42) = 96/99 * P(97,42)

= ...

= 42/99 * P(43, 42) = 42/99 * 1/42 = 1/99

Or, more directly, P(100,42) = 1/(N-1) = 1/99

Posted by tomarken on 2014-06-24 16:57:23