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 P_{1}[n] and P_{2}[n] denote the probability of being in states 1 and 2 respectively after the nth draw, we begin with P_{1}[0] = 1 and P_{2}[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 closedform expression for the nth probability vector P[n] = M^{n} 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 oddnumbered 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 oddnumbered 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 lefthand 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. 
