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

          P1[n+1] = (9/11)P1[n]
          P2[n+1] = (2/11)P1[n] + (9/10)P2[n]

Letting W[n] denote the probability that the game has been won by 
someone after the nth draw, we obviously have 

               W[n] = 1 - P2[n] - P1[n]

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

                | 9/11    0  |
          M  =  |            |
                | 2/11  9/10 |

From this we also have the simple closed-form 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 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

 W[2n+1] - W[2n]  =  (1-P1[2n+1]-P2[2n+1]) - (1-P1[2n]-P2[2n])

                  =  {P1[2n] + P2[2n]} - {P1[2n+1] + P2[2n+1]}

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

           (I - M + M^2 - M^3 + M^4 - ...)P[0]

Since P[0] is just [1,0]^T, we want the sum of the left-hand column 
of the matrix

                          | 11/20     0   |
             (I+M)^-1  =  |               |
                          | -1/19   10/19 |

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

                           | 9/20     0   |
             M(I+M)^-1  =  |              |
                           | 1/19    9/19 |

which confirms that the "even" probability is, as expected,
9/20 + 1/19 = 191/380 = 0.50263...

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.