probability: of balls and urns

This is an unsolved problem from "Probability, a concise course, by Y A Rozanov". Very instructive in how to perform probability calculations.

There are N urns numbered 1, 2, ..., N in a row, each containing r red and b blue balls. A ball is drawn at random from the first urn and transferred to the second, then a ball is sampled from the second and transferred to the third, and so on, until you finally sample a ball from the Nth urn. The question is, what is the probability of drawing a red ball from the Nth urn?

I've heard people give all kinds of answers, but here's the correct way to solve the problem.

Start from urn #1.
What is the probability of sampling a red ball? r/(r+b).
A black ball? b/(r+b).

So either a red ball or a black ball is sampled and put into urn #2.
So urn #2 might have an extra red ball (in r/(r+b) cases), or an extra blue ball (in b/(r+b) cases).
So while sampling from urn #2, in r/(r+b) cases, you are sampling from r+1 red balls and b blue balls, and in b/(r+b) cases, you are sampling from r red balls and (b+1) blue balls.
So the probability of sampling a red ball from urn #2 becomes:
                 r/(r+b) * (r+1)/(r+b+1) + b/(r+b) * r/(r+b+1)
Simplifying, we get, p(drawing red ball from urn #2) = r/((r+b)(r+b+1)) * (r+1+b) = r/(r+b)
Wow! So regardless of the complexity of the experimental setup, the probability of drawing a red ball from urn #2 remains r/(r+b) JUST AS IT WAS FOR THE DRAW FROM URN #1!

Now, we can simply re-run the experiment thinking of urn #2 as urn #1, and urn #3 as urn #2 as above, and just keep repeating it till we reach urn #N. The probability of drawing a red ball from urn #N is therefore also r/(r+b). Interesting question.

probability: coin flipping problems

Interesting question someone posed to me recently. These appear to be favorites at interviews.

You and I each have 3 coins we toss. If you get the same number of heads as I do, I pay you $2. If we get a different number of heads, you pay me $1. Would you take the bet?

An incorrect way of solving this problem is to deduce that there are only 4 of 16 possible ways where we get the same number of heads (0H-0H, 1H-1H, 2H-2H, and 3H-3H), so the pay-off is 4/16*2 - 12/16*1 = -4/16. Which is negative so you should not take the bet.

The above reasoning is incorrect because the likelihood of each of the 16 outcomes is different, so they should not be equally weighted in the probability calculation. A more correct way of thinking about this is as below:

Consider 3 coins as 3 bits, where a zero denotes tails and a 1 denotes heads.

Then (binary numbers 0 through 7)
000 - zero heads
001 - 1 head
010 - 1 head
011 - 2 heads
100 - 1 head
101 - 2 heads
110 - 2 heads
111 - 3 heads

From this we get:
p(0 heads)=1/8
p(1 head)=3/8
p(2 heads)=3/8
p(3 heads)=1/8
Total probability = (1+3+3+1)/8=1 (check)

Now we imagine a grid - x axis is my number of heads, y axis is your number of heads. In each grid slot in the diagonals, we fill in the probability.

p(0H,0H)=1/8*1/8=1/64
p(1H,1H)=3/8*3/8=9/64
p(2H,2H)=3/8*3/8=9/64
p(3H,3H)=1/8*1/8=1/64
Total probability of equal heads = 20/64
=> Total probability of un-equal heads = 44/64.

Since 20*2<44, again, the expected value of the offered bet is negative, and so no, you should not play.

Another problem:
I have K coins, you have K+1 coins. We both toss our coins. You win if you toss more heads than me. What is the probability you win?

Easy to solve if we think using small models and build up intuition.

Consider K=2 (0, 1, or 2 heads). X axis is me, Y axis is you.

        0H  1H  2H
0H   1/2  L   L
1H   W   1/2  L
2H   W    W   1/2

So here, you win for certain in 3 cases, can win with probability 1/2 in 3 cases, and lose in 3 cases. You win the diagonal outcomes with probability 1/2 because you can cast the tie-breaker toss with your K+1st coin, which will come up heads with probability 1/2.

 If we were to extrapolate from this upwards to K coins, you see a grid of size K+1 in each direction, where you win K+1 outcomes with probability half, ((K+1)^2-(K+1))/2 outcomes with probability 1, and lose the same number of outcomes out of a total of (K+1)^2 possible outcomes.

So p(you win) = (((K+1)^2-(K+1))/2 *1 + (K+1)*1/2)/(K+1)^2.
Simplifying we get: 
Numerator=(K^2+2K+1-K-1+K+1)/2=(K^2+2K+1)/2
Denominator=(K^2+2K+1)
Which gives us an answer of 1/2. So your probability of winning is 1/2.