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