|
Markov's Marbles |
|
|
|
A container holds 2 green marbles and 9 red marbles. Two players, A and B, alternately pick a marble from the container. If it's red, the marble is replaced. If it's green, it is kept. The player who gets the second green marble wins. What are the odds of winning for the player who draws first? |
|
|
|
Problems like this can be solved by means of a simple Markov model. The game is either in State 1 (no greens have yet been drawn) or State 2 (one of the greens has been drawn and removed). In State 1, each draw has probability 2/11 of going to State 2, and 9/11 of staying in State 1. In State 2, each draw has probability 1/10 of ending the game (by drawing the second green) and 9/10 of staying in State 2. |
|
|
|
So, if we let P1[n] and P2[n] denote the probability of being in states 1 and 2 respectively after the nth draw, we begin with P1[0] = 1 and P2[0] = 0. Thereafter, the probabilities can be computed by the recurrence relation |
|
|
|
|
|
|
|
Letting W[n] denote the probability that the game has been won by someone after the nth draw, we obviously have |
|
|
|
|
|
|
|
Now, the recurrence relation can be written in matrix form as P[n] = M P[n−1] where P[n] is the column vector of probabilities and M is the transition matrix |
|
|
|
|
|
|
|
From this we also have the simple closed-form expression for the nth probability vector P[n] = Mn P[0]. |
|
|
|
We want to know the probability of winning for the player who draws first. The two players alternate, so the one who draws first will also draw 3rd and 5th and so on. Thus, the question is: What is the probability that the game will end on an odd-numbered draw? The probability of ending the game on the first draw is W[1] − W[0], and of winning on the 3rd draw is W[3] − W[2], and so on. In general, the probability of winning on the (2n+1)th draw is |
|
|
|
|
|
|
|
So, the sum of all the probabilities of ending the game on an odd-numbered draw is given by the sum of the components of the vector P[0] − P[1] + P[2] − P[3] + ..., and this equals the geometric series |
|
|
|
|
|
|
|
Since P[0] is just [1,0]T, we want the sum of the left-hand column of the matrix |
|
|
|
|
|
|
|
So the probability of a win on the odd draws is 11/20 − 1/19, which equals 189/380 = 0.49736... Of course, we could have computed the probability of a win on the even draws, simply by bumping the index up one number, i.e., multiplying by M, to give |
|
|
|
|
|
|
|
which confirms that the "even" probability is, as expected, |
|
|
|
|
|
|
|
Obviously this approach can be extended to cover any number of red and green marbles. If there are N green marbles, the transition matrix will be of size N x N. |
|
|
