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.
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.
