Absorbing Markov Chains

Computational Economics

Author

Florian Oswald

Published

April 2, 2025

This elaborates on Bogumił’s blog post about the problem of generating a sequence of coin tosses. We will add some theory to his simulation study.

Problem Statement

To recap, we have two players Alice (A) and Bob (B), and each is equipped with fair coin. Each plays a game whereby they toss the coin, and record the outcome as either heads (H) or tails (T). An example of a sequence after 9 coin tosses for each player could look like this:

toss: 123456789
A:    TTHHHTHTH
B:    THTTHTHHT

Alice and Bob have different ways of winning this game. A wins if the sequence HT occurs, and B wins if the sequence HH occurs. Following the above example, A would have won after toss number 6. B had to wait until toss number 8 complete his winning sequence HH, hence he lost this particular contest.

Questions

  1. In expectation, who is more likely to win this game? Suppose we performed a very large number of contests like the one illustrated above.
  2. How many coin tosses does Alice have to perform, on average, until her winning sequence shows up?
  3. How many tosses does Bob have to perform until his winning sequence appears?

Simulations

Let us follow in Bogumił’s foot steps and re-propose the simulation study he did on his blog.

Who is more likely to win this game? We will later work out the probability that each will win, but we can easily to a simulation study following a frequentist approach: just count how many times each player wins!

Let’s create a function which will simulate us tossing an imaginary coin until one of both players wins. The function should return the initial of the winning player.

function whowins()
    t1 = rand(('H', 'T'))  # toss number 1 
    while true  # keep going until we get a valid sequence.
        t2 = rand(('H', 'T'))  # toss number 2 
        if t1 == 'T'  # invalid first toss for both.
            t1 = t2   # reassign t2 to t1 and keep going
        else  # t1 is 'H' ! t2 now decides the winner!
            return t2 == 'H' ? "B" : "A"
        end
    end
end
whowins (generic function with 1 method)

You should try it out a few times to convince yourself it’s working.

Simulating the Expected Probability of Winning

Now, lets see how often each of them wins if we repeat this contest many times over:

using Random, FreqTables
Random.seed!(10101)

freqtable( [whowins() for _ in 1:100_000_000] )
2-element Named Vector{Int64}
Dim1  │ 
──────┼─────────
A     │ 50003096
B     │ 49996904

Ok, that would tell us that if we were to have them play a close to infinite number of times, each would win pretty much exactly half the games.

Simulating expected number of steps till winning

This is fairly easy to simulate, given our above code.

function count_alice()
    t1 = rand(('H', 'T'))  # toss number 1 
    tosses = 1  # counter
    while true  # keep going until we get a winner: HT
        t2 = rand(('H', 'T'))  # toss number 2 
        tosses += 1 
        # if sequence is correct, return, else re-do
        t1 == 'H' && t2 == 'T' && return tosses

        # if did not return above, keep going
        t1 = t2
    end
end
count_alice (generic function with 1 method)

You should try to implement count_bob() yourself now.

Code 
function count_bob()
    t1 = rand(('H', 'T'))  # toss number 1 
    tosses = 1  # counter
    while true  # keep going until we get a winner: HH
        t2 = rand(('H', 'T'))  # toss number 2 
        tosses += 1 
        # if sequence is correct, return, else re-do
        t1 == 'H' && t2 == 'H' && return tosses

        # if did not return above, keep going
        t1 = t2
    end
end
count_bob (generic function with 1 method)
Note
  • Do you expect the count_* functions to return the same number each time you call them, or not?
  • If not, which function seems to return smaller numbers on average?

The last one is an easy question to answer with a simulation study again, isn’t it? This time it’s not about counting who wins how many times, however, but rather…🤔

Code 
using Statistics  # for mean()

(
    Alice = mean( [count_alice() for _ in 1:100_000_000] ),
    Bob = mean( [count_bob() for _ in 1:100_000_000] )
)
(Alice = 3.99997351, Bob = 5.99957595)

…wait, this is surprising, not? Alice has to toss 4 times on average, while Bob has to wait for 6 tosses until his winning sequence comes up? How come?

Markov Chains

Let us quickly remember some basics about finite state markov chains. The quantecon project has a great lecture about this topic, if you want to know more.

  1. A stochastic (or markov) matrix is a matrix \(P\) of size \((n,n)\) with non-negative entries.
  2. All rows sum to one - we can think of each row as the probability mass function of \(n\) potential outcomes.

Here is an example of a valid markov matrix:

\[P = \left[\begin{array}{cc} 0.2 & 0.8 \\ 0.9 & 0.1 \end{array}\right] \tag{1}\]

A markov chain adds a set \(S = {s_1, s_2, \dots, s_n}\) of states to this setup, where \(S\) is called the state space. The definition of a markov chain \({X_t}\) on \(S\) is then:

Markov Chain Definition

The sequence of random variables \(\{X_t\}\) defined on space \(S\) is called a markov chain if it possesses the markov property:

\[ \Pr \{X_{t+1} = s | X_t\} = \Pr \{X_{t+1} = s | X_t, X_{t-1}, \dots\} \]

meaning that it is enough to condition on the previous realization in order to know the probability of the next value of the chain taking on value \(s\). All relevant information is contained in the last observed value, there is no extra information in conditioning on the entire history of the sequence \(\{X_t\}\).

Going back to the above \(P\) in Equation 1, suppose we define the states S = {Employed, Unemployed}, and assuming that the first row and column of \(P\) represents state Employed, let us draw a DAG to represent this setting:

graph LR
    Employed --> |0.2| Employed
    Employed --> |0.8| Unemployed  
    Unemployed --> |0.9| Employed  
    Unemployed --> |0.1| Unemployed

Transitions in a fictitious labor market. 👉 Can you describe in words how this market works?

Absorbing Markov Chains

Now, back to Alice and Bob. Their game can be represented as a special type of a markov chain, that is absorbing state markov chain - there is at least one state, from which you can no longer transition away. For both of our players, this would be the state which represents their winning sequence of coin tosses (i.e. either HH or HT). In a different application, the absorbing state could model anything which represents that a player leaves the system.

Let’s now calculate why the above simulation brought up that Bob has to wait for 6 tosses on average for his sequence HH, when Alice only needed to wait for 4 tosses for HT.

The Absorbing Transition Matrix \(P_a\)

In this setting we have \(t\) transient states (i.e. states from which you can escape), and \(r\) absorbing states - once you enter such a state, you stay there, in other words, the chain ends.

We have to re-write our transition matrix for this case. It will look as follows:

\[P_a = \left[\begin{array}{cc} Q & R \\ \mathbf{0} & \mathbf{I}_r \end{array}\right] \tag{2}\]

where

  1. \(Q\) is the \((t,t)\) transition matrix of transient states
  2. \(R\) is a \((t,r)\) matrix of transition probabilities from transient state \(t\) into absorbing state \(r\)
  3. \(\mathbf{0}\) is an \((r,t)\) matrix of zeros, and
  4. \(\mathbf{I}_r\) is the \((r,r)\) identity matrix.

Let’s work this out for Alice now. Imagine that we want to fill out each of her 2 empty slots for strings with either H or T. Remember that her winning sequence was HT. It’s easiest to model Alice in three possible states:

  1. State e: She has an empty sequence, {}. She is waiting to fill this with two valid strings.
  2. State H: Her sequence has H in first position, i.e. looks like {H}. This is great, because if the next coin toss yields a T, she wins! If she gets another H, no problem, she stays at state {H} (we can just throw away the previous H in the sequence!).
  3. State HT: She wins the game.

So, we define the following transient states for her:

  1. e: empty sequence i.e {}
  2. H: the string sequence containing only H, i.e. {H}

Next, we define the absorbing state for her:

  1. HT: upon tossing T after a H, i.e completing the sequence {HT}, the game ends.
Observations
  • In this example we have t=2 transient states
  • T in first position is not a valid sequence for Alice. Whilst we could think of {T} as a transient state, it is easier to think that we go back to e and start again if we hit T in the first toss.
  • There is a single absorbing state, {HT}, i.e. r=1.

The situation for Alice is as follows:

graph LR
    e((e)) --> |0.5| e
    e((e)) --> |0.5| H
    H      --> |0.5| H
    H      --> |0.5| HT

Absorbing Markov Chain of Alice

Notice how we assume that if your first toss is invalid (i.e. a T), you stay with your empty sequence. Next, here is the transition matrix \(Q_a\) for her transient states {e,H} (putting e in the first row/column), and the (2,1) matrix of transitions from transient into absorbing state, \(R_a\):

\[Q_a = \left[\begin{array}{cc} 0.5 & 0.5 \\ 0 & 0.5 \end{array}\right],\quad R_a = \left[\begin{array}{c} 0 \\ 0.5 \end{array}\right] \tag{3}\]

Let us assemble those into \(P_a(\text{Alice})\) now, and observe that this maintains the properties of stochastic matrix \(P\):

\[P_a(\text{Alice}) = \left[\begin{array}{ccc} 0.5 & 0.5 & 0 \\ 0 & 0.5 & 0.5 \\ 0 & 0 & 1 \end{array}\right] \tag{4}\]

The Fundamental Matrix \(N\)

The next piece we need is called the fundamental matrix. It will give us the expected number of visits to transient state \(j\) before we reach an absorbing state. It is obtained by iterating \(Q_a\) forward until infinity. It can be shown that it looks like this, similar to the infinite sum of a geometric series:

\[ N = \sum_{k=0}^\infty Q^k = (I - Q)^{-1} \]

So, for Alice, it looks as follows:

\[ N_a = (I - Q_a)^{-1} = \left( \left[\begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array}\right] - \left[\begin{array}{cc} 0.5 & 0.5 \\ 0 & 0.5 \end{array}\right] \right)^{-1} = \left(\left[\begin{array}{cc} 0.5 & -0.5 \\ 0 & 0.5 \end{array}\right] \right)^{-1} \]

Do we all still remember how to compute the inverse of a 2x2 matrix? I dont’t, but here is a formula 🙈

Inverse of a 2x2 matrix

For \(A = \left[\begin{array}{cc} a & b \\ c & d \end{array}\right]\) we have that the inverse matrix of \(A\) is

\[A^{-1} = \frac{1}{ad - bc} \left[\begin{array}{cc} d & -b \\ -c & a \end{array}\right]\]

With that out of the way, you can calculate that

\[ N_a = \left[\begin{array}{cc} 2 & 2 \\ 0 & 2 \end{array}\right] \tag{5}\]

We can immediately get the expected number of steps before being absorbed from this by summing across rows:

\[ N_a \mathbf{1}_t = \left[\begin{array}{c} 4 \\ 2 \end{array}\right] \tag{6}\]

So, starting in state e, the expected number of steps before reaching absorbing state HT is \(4\) for Alice. Once in state H, she expects only two more steps. Here a step is a toss of a coin.

States and Transitions for Bob?

For Bob, the situation is slightly different. Remember that Bob wins if HH comes up. For him, we have the following definition of states:

  1. State e: The empty sequence, {}. Waiting to fill this with two valid strings.
  2. State H: The sequence has H in first position, i.e. looks like {H}.
  3. State HH: He wins the game.

Notice the one big difference here: If Bob is in state {H}, and hits a T in the next toss, he is not as fortunate as Alice, who can stay in the same state. Bob’s problem is that he does not have a winning sequence that could start with T (neither does Alice, but upon hitting T while in state {H}, she wins!)

Here’s the graphs for Bob and Alice side by side:

graph LR
    e((e)) --> |0.5| e
    e((e)) --> |0.5| H
    H      --> |0.5| e
    H      --> |0.5| HH

Markov Chain of Bob

graph LR
    ea((e)) --> |0.5| ea
    ea((e)) --> |0.5| Ha[H]
    Ha[H]      --> |0.5| Ha
    Ha[H]      --> |0.5| HT

Markov Chain of Alice

The problem for Bob is the arrow going back to e if he hits a bad toss at state {H}. Let us quickly assemble the transition matrix for Bob, and compute his expected steps:

\[Q_b = \left[\begin{array}{cc} 0.5 & 0.5 \\ 0.5 & 0 \end{array}\right],\quad R_b = \left[\begin{array}{c} 0 \\ 0.5 \end{array}\right] \tag{7}\]

\[P_a(\text{Bob}) = \left[\begin{array}{ccc} 0.5 & 0.5 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 0 & 1 \end{array}\right] \tag{8}\]

With those in hand, you can easily verify that Bob will have

\[ N_b = \left[\begin{array}{cc} 4 & 2 \\ 2 & 2 \end{array}\right] \tag{9}\]

which, in turn, means that his expected steps until absorbing state, starting from either {} or {H} are given by

\[ N_b \mathbf{1}_t = \left[\begin{array}{c} 6 \\ 4 \end{array}\right] \tag{10}\]

👉 exactly as in our (Bogumił’s!) simulation experiment from the start.

© Florian Oswald, 2025