Exercise 1.16 [Mitzenmacher and Upfal's textbook]
Consider the following game, played with three six-sided dice. If the player ends with all three dice showing the same number, she wins. The player starts by rolling all three dice. After this first roll, the player can select any one, two, or all of the three dice and re-roll them. After this second roll, the player can again select any of the three dice and re-roll them one final time.
Suppose that the player has this strategy: If all three dice match, the player stops and wins. If two dice match, the player re-rolls the die that does not match; and if no dice match, the player re-rolls them all.
Now, this is how we do it. Clearly we have three cases:
Case 1: When all three dices match the same face in first rolling. So, the player stops and wins. The probability that this happens is 1/36.
Case 2: When only two dices match the same face in first rolling. So, we need to do re-roll the one that doesn't match. Thus we have probability 1/6 to win but if the second rolling doesn't match, then we re-roll it again for third and last rolling. Then we have 5/6*1/6 (This is because we wouldn't do the third rolling unless the second rolling did not match the two dices that are matched and probability that the player gets in third rolling the same face is 1/6). So, in total we have $1/6+5/6*1/6 = 11/36$.
Case 3: When all three dices did not match in the first rolling. Then the player will throw all the three dices again. Thus, we have three ways that could happen: either all match up, so we have probability that the player wins in the second rolling: (6/6*5/6*4/6)*1/36, or only two match up and we have probability to win in the second and third rolling: (6/6*5/6*4/6)*5/12*1/6. Or all three are unmatched and probability that to win in this case is: 2(6/6*5/6*4/6)*1/6. So we sum up all these probabilities in this case 3.
Now, we need to sum up all these three cases to get the probabilities that a player wins in this game.
Is that correct?