(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 S1, S2, S3, ... 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 S1. What is the probability Pwin(S1) of winning such a game.
As an example, let's take the following rules to the game:
- S1: Heads brings you to S2, tails brings you to S3
- S2: Heads brings you to S3, tails brings you to L
- S3: 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:
- Pwin(S3) = 0.5 * 0% + 0.5 * 100% = 50%
- Pwin(S2) = 0.5 * Pwin(S3) + 0.5 * 0% = 25%
- Pwin(S1) = 0.5 * Pwin(S2) + 0.5 * Pwin(S3) = 37.5%
The problem comes in when I, for example, replace the last rule with this:
- S3: Heads brings you back to S1, tails brings you to W
Notice, how this creates a circular reference where Pwin(S3) depends on Pwin(S1) and vice versa.
I need an algorithm that a computer can perform automatically to solve for Pwin(S1) 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?
It sounds like you're talking about a Markov chain, in which case you're looking for the probability of winning in the steady-state distribution.
As Wikipedia explains, a (discrete) Markov chain is a directed state graph equipped with a probability distribution on the out-edges of each vertex. We can use these models to understand flow on the graph in a probabilistic way. One way to visualize this is to imagine one or more random "walkers" moving on the graph according to the distributions.
A critical ingredient of the guarantees we are about to examine is the Markov property, which essentially says that a random walker has no memory. Instead their behavior is determined entirely by the (fixed) transition distribution of the state node they're standing on.
One could imagine an initial distribution of a great many random walkers on a graph, who are allowed to walk for an unbounded amount of time. When the graph is suitable, the Markov property guarantees that the distribution of walkers "levels out" and converges on a single steady-state distribution, regardless of the initial distribution. By calculating this steady-state distribution, one can ask questions of it such as "What is the probability of a random walker being in state
X?"Your problem appears to fit the requirements of a Markov model (particularly, the absorbing variant as you noticed.) In that formulation "winning" becomes arrival at a certain set of states. You can therefore calculate the odds of winning by first calculating the steady-state distribution and then asking it the probability of being in the winning states.