Fog Creek Software
Discussion Board




flipping coins

Solution using Markov chains:

Pr(H|H) = 0.0    Pr(T|H) = 1.0
Pr(H|T) = 0.5    Pr(T|T) = 0.5

So, the transition probability matrix is:

T = |0.0 1.0|
      |0.5 0.5|

Obtaining the stationary probabilities of the Markov chain gets us the solution to the problem.

Briefly:
(I - T')X = 0,      (n eqns in n variables)  (1)
sum of prob = 1  (1 eqn in n variables)          (2)
where I is the identity matrix and T' is the transpose of T.

Drop ANY 1 equation from (1) and solve with (2).

|1.0 0.0|    |0.0 0.5|    | 1.0  -0.5|
|0.0 1.0| -  |1.0 0.5| = |-1.0  0.5|

So, the equations are:
    P(H) - 0.5P(T) = 0    (1)
    - P(H) + 0.5P(T) = 0  (drop this)
    P(H) +    P(T) = 1    (2)
=> P(H) = 1/3, P(T) = 2/3

This solution allows us to easily solve a class of these
problems where the transitions may be different or
dice may be used instead of coins!

Velant Guy
Friday, July 18, 2003

I have to say I'm impressed. Not that I followed the explanation, but I'm still impressed.

David Clayworth
Friday, August 01, 2003

*  Recent Topics

*  Fog Creek Home