Resolving circular references in probability-graph

Question

(Apologies, if the title is not accurate/useful, I'm not sure what else to call it... Ideas welcome...)

Let's say I have a game that consists of several states S₁, S₂, S₃, ... and coin-tosses that transition you from one state to some other state. There also is a state W where you win and a state L where you loose. Games always start in state S₁. What is the probability P_win(S₁) of winning such a game.

As an example, let's take the following rules to the game:

• S₁: Heads brings you to S₂, tails brings you to S₃
• S₂: Heads brings you to S₃, tails brings you to L
• S₃: Heads brings you to L, tails brings you to W

Now, if I need to figure out what the overall chance of winning the game is (given fair coin-tosses), I can simply start at the bottom:

• P_win(S₃) = 0.5 * 0% + 0.5 * 100% = 50%
• P_win(S₂) = 0.5 * P_win(S₃) + 0.5 * 0% = 25%
• P_win(S₁) = 0.5 * P_win(S₂) + 0.5 * P_win(S₃) = 37.5%

The problem comes in when I, for example, replace the last rule with this:

• S₃: Heads brings you back to S₁, tails brings you to W

Notice, how this creates a circular reference where P_win(S₃) depends on P_win(S₁) and vice versa.

I am looking for an algorithm that solves for P_win(S₁) for any possible rule-set for an arbitrary number of states and for "coins" that have more than 2 sides (i.e. each state transitions to a random choice among several possible following states including immediate loop-back). I might even be faced with a situation where the "coins" aren't fair, i.e. the probabilities to transition to the next states are not all equal.

I think I remember something that this can be solved with a matrix equation, but I'm not even sure what to call this problem to do a real Google search for an answer... I don't even know what tags to pick. :)

Any pointers would be much appreciated.

Given all values are probabilities that sum to 1, I have a feeling that this problem should always have one unique solution. Is that correct?

Answer 1

You're describing a Markov chain model. You'll want to set up the state transition matrix P, and then the long-run proportion of time spent in each state, π, obeys the relationship πP=π. If I recall correctly, when you have absorbing states such as "win" or "lose", π should converge to zeros for all other states and the probabilities of win/lose for those two absorbing states.