Let's revisit Kobayashi, Chapter 2.

Let's look the following:

The rows . The columns , so .

Which states are unstable? .

Which states are closed? .

: Once in these states, can't get out of them; can go back and forth between 2 and 5, but not to the other states.

: Absorbing state.

These sets then are . There are two .

Since this Q has , it is .

Ergodic: for a Markov chain to be ergodic, it must be irreducible and aperiodic and all states must be positive-recurrent. Therefore, this Q is not ergodic because it is reducible!

Example 2 - this is Example 2.9.4.

Stochastic?

Doubly Stochastic?

Absorbing state(s)?

Transient state(s)?

Irreducible? .

Remember, f_ij⁽ⁿ⁾ is the probability that starting i, at time zero, the system is in state j for the first time at time n.

Can we get a stationary distribution (p ) for this Q?

Stochastic?

Doubly Stochastic?

Absorbing state(s)?

Transient state(s)?

Recurrent state(s)?

Irreducible?

Aperiodic?

Ergodic?

What do we notice about f_ii?

f_ii = å f_ii⁽ⁿ⁾, for n = 1 to infinity.

If f_ii = 1, then state i is called a recurrent state, and if f_ii < 1, it is called a transient state.

We see for f₁₁ = 1/4 + 1/16 + 5/64 + … > 1/4 + 1/16 + 1/64 + …

Does this sum to one?

If we rewrite this as:

f₁₁ > 1/4 + (1/4)(1/4) + (1/4)(1/4)² + …

then we can assume that the next term is [1/4](1/4)³; we are multiplying the previous term by 1/4. This sequence is an infinite geometric series (from Algebra 2 or Trigonometry) and it approaches a limit, or converges to a limit, so it is also called a convergent series.

The sum of an infinite convergent series is:

In our series above, a₁ is the first term, 1/4, and r is 1/4. So the sequence is a₁, a₁r, a₁r², …

So,

S = a₁/(1 - r) = (1/4)/(1-1/4) = (1/4)/(3/4) = (1/4)*(4/3) = 1/3.

With the information that we have, we see that state 1 is a transient state. Note that f₂₁ has the same numbers.

We see:

f₂₂ = 1/4 + 1/2 + 1/8 + 1/16 + ….

Rewrite this as:

f₂₂ = 1/2 + [(1/4) + (1/4)(1/2) + (1/4)(1/2)² + ….]

Note that the terms after the "1/2 +" constitute another infinite convergent series. The sum is:

S = a₁/(1 - r) = (1/4)/(1-1/2) = (1/4)/(1/2) = (1/4)*(2/1) = 1/2.

Then we add this to the 1/2 we left out:

f₂₂ = .

So we see that state 2 is .

We see:

f₃₃ = 1/2 + 1/4 + 1/16 + 1/16 + ….

Note that as n gets larger from this point, i.e., n = 5, n = 6, etc., we will be multiplying the previous term by the self-loop on state 2, which is 1/4. So, this last 1/16 will be the starting term for the infinite convergence series.

f₃₃ = 1/2 + 1/4 + 1/16 + [(1/16) + (1/16)(1/4) + (1/16)(1/4)² + ….]

f₃₃ = 13/16 + [(1/16) + (1/16)(1/4) + (1/16)(1/4)² + ….]

Note that the terms after the "13/16 +" constitute another infinite convergent series. The sum is:

S = a₁/(1 - r) = (1/16)/(1-1/4) = (1/16)/(3/4) = (1/16)*(4/3) = 1/12.

Then we add this to the 13/16 we left out:

f₃₃ = 13/16 + 1/12 = 156/192 + 16/192 = .

So we see that state 3 is .

A recurrent state i is null-recurrent if the expected recurrence time m _ii is infinite, and positive-recurrent if m _ii < ¥ .

For state 2, we know f₂₂ = 1, so we can use Kobayashi equation 2.246 on page 88.

m _ii = q_ii + å _{k¹ j} q_ik (m _ki + 1)

So,

m ₂₂ = q₂₂ + å _{k¹ j} q_2k (m _k2 + 1)

m ₂₂ = 1/4 + {q₂₁ (m ₁₂ + 1)} + {q₂₃ (m ₃₂ + 1)}

m ₂₂ = 1/4 + (1/4) (m ₁₂ + 1) + (1/2) (m ₃₂ + 1)

Well then, what about the other f_ij? Don't we need to know these too? Two of them, m ₁₂ and m ₃₂!

We know right off the bat that:

f₁₂ = 1

because q₁₂ = 1. So, we know that m ₁₂ is less than infinity.

Let's use the equation.

m ₁₂ = q₁₂ + å _{k¹ j} q_1k (m _k2 + 1)

m ₁₂ = 1 + {q₁₁ (m ₁₂ + 1)} + {q₁₃ (m ₃₂ + 1)}

m ₁₂ = 1 + {0 (m ₁₂ + 1)} + {0 (m ₃₂ + 1)} = 1

What about f₃₂?

f₃₂ = 1/2 + 1/4 + 1/8 + 1/16 + … = 1/2 + (1/2)(1/2) + (1/2)(1/2)² = 1

Because S = (1/2)/(1 - 1/2) = 1. Therefore, m ₃₂ is less than infinity too.

m ₃₂ = q₃₂ + å _{k¹ j} q_3k (m _k2 + 1)

m ₃₂ = 1/2 + {q₃₁ (m ₁₂ + 1)} + {q₃₃ (m ₃₂ + 1)}

m ₃₂ = 1/2 + {0 (m ₁₂ + 1)} + {1/2 (m ₃₂ + 1)}

m ₃₂ = 1/2 + 1/2 (m ₃₂ + 1)

m ₃₂ = 1/2 + (1/2)m ₃₂ + 1/2

m ₃₂ = 1 + (1/2)m ₃₂

(1/2)m ₃₂ = 1

m ₃₂ = 2

Substituting the results back into the equation above:

m ₂₂ = 1/4 + (1/4) (m ₁₂ + 1) + (1/2) (m ₃₂ + 1)

m ₂₂ = 1/4 + (1/4) (1 + 1) + (1/2) (2 + 1) = (1/4) + (1/2) + (3/2) = 9/4

So, m ₂₂ < ¥ , so state 2 is a . (A is also called a regular-recurrent state.)

Example 4 - from Example 2.9.5.

Stochastic? .

Doubly stochastic? .

Periodic? Yes. The number of transitions to return to state 1, for example, is 2, 4, 6, 8, …

So, it is periodic with period

What do we notice about f_ii?

f_ii = å f_ii⁽ⁿ⁾, for n = 1 to infinity.

If f_ii = 1, then state i is called a recurrent state, and if f_ii < 1, it is called a transient state.

We see for f₁₁ = 1/2 + 1/8 + 3/32 + ….

If we rewrite this as:

f₁₁ > 1/2 + 1/(2³) + 1/(2⁵) + …., or,

f₁₁ > 1/2 + [1/2](1/4) + [1/2](1/4)² + ….

then we can assume that the next term is [1/2](1/4)³ or 1/(2⁷); we are multiplying the previous term by 1/2², or 1/4. This sequence is an infinite geometric series, also called a convergent series.

The sum of an infinite convergent series is:

S = a₁/(1 - r), | r | < 1.

In our series above, a₁ is the first term, 1/2, and r is 1/4. So the sequence is a₁, a₁r, a₁r², …

So,

S = a₁/(1 - r) = (1/2)/(1-1/4) = (1/2)/(3/4) = (1/2)*(4/3) = 2/3.

With the information that we have, we see that state 1 is a . Note that state 4 has the same numbers, so it too is a .

We see:

f₂₂ = f₃₃ = 3/4 + 1/8 + 1/16 + ….

Rewrite this as:

f₂₂ = f₃₃ = 1/2 + 1/4 + [1/4][(1/2) + [1/4](1/2)² + ….

Note that the terms after the "1/2 +" constitute another infinite convergent series. The sum is:

S = a₁/(1 - r) = (1/4)/(1-1/2) = (1/4)/(1/2) = (1/4)*(2/1) = 1/2.

Then we add this to the 1/2 we left out:

f₂₂ = f₃₃ = 1/2 + 1/2 = 1.

So we see that states 2 and 3 are .

A recurrent state i is null-recurrent if the expected recurrence time m _ii is infinite, and positive-recurrent if m _ii < ¥ .

For states 2 and 3, we know f₂₂ = f₃₃ = 1, so we can use Kobayashi equation 2.246 on page 88.

m _ii = q_ii + å _{k¹ j} q_ik (m _ki + 1)

So,

m ₂₂ = q₂₂ + å _{k¹ j} q_2k (m _k2 + 1)

m ₂₂ = 0 + {q₂₁ (m ₁₂ + 1)} + {q₂₃ (m ₃₂ + 1)} + {q₂₄ (m ₄₂ + 1)}

m ₂₂ = (1/2) (m ₁₂ + 1) + (1/2) (m ₃₂ + 1) + 0 (m ₄₂ + 1)

m ₂₂ = (1/2) {(m ₁₂ + 1) + (m ₃₂ + 1)}

m ₂₂ = (1/2) {m ₁₂ + m ₃₂ + 2}

Well then, what about the other f_ij? Don't we need to know these too? Some of them!

We know right off the bat that:

f₁₂ = f₄₃ = 1

because q₁₂ and q₄₃ = 1. So, we know that m ₁₂ and m ₄₃ are less than infinity.

f₁₃ = f₂₃ = f₃₂ = f₄₂ = 1/2 + 1/4 + 1/8 + … = 1/2 + (1/2)(1/2) + (1/2)(1/2)² = 1

Because S = (1/2)/(1 - 1/2) = 1. Therefore, m ₁₃, m ₂₃, m ₃₂ and m ₄₂ are less than infinity too.

m ₁₂ = q₁₂ + å _{k¹ j} q_1k (m _k2 + 1)

m ₁₂ = 1 + {q₁₁ (m ₁₂ + 1)} + {q₁₃ (m ₃₂ + 1)} + {(q₁₄ (m ₄₂ + 1)}

m ₁₂ = 1 + {0 (m ₁₂ + 1)} + {0 (m ₃₂ + 1)} + {(0 (m ₄₂ + 1)} = 1

m ₃₂ = q₃₂ + å _{k¹ j} q_3k (m _k2 + 1)

m ₃₂ = 1/2 + {q₃₁ (m ₁₂ + 1)} + {q₃₃ (m ₃₂ + 1)} + {q₃₄ (m ₄₂ + 1)}

m ₃₂ = 1/2 + {0 (m ₁₂ + 1)} + {0 (m ₃₂ + 1)} + {(1/2) (m ₄₂ + 1)} = 1/2 + {(1/2) (m ₄₂ + 1)}

m ₃₂ = 1 + (1/2) m ₄₂

We know f₄₂ = 1,

m ₄₂ = q₄₂ + å _{k¹ j} q_4k (m _k2 + 1)

m ₄₂ = 1 + {q₄₁ (m ₁₂ + 1)} + {q₄₃ (m ₃₂ + 1)} + {(q₄₄ (m ₄₂ + 1)}

m ₄₂ = 1 + {0 (m ₁₂ + 1)} + {1 (m ₃₂ + 1)} + {0 (m ₄₂ + 1)}

m ₄₂ = 2 + m ₃₂

We can solve these last two equations:

m ₃₂ = 1 + (1/2) (2 + m ₃₂)

m ₃₂ = 2 + (1/2) (m ₃₂)

(1/2)m ₃₂ = 2

m ₃₂ = 4

Substituting the results back into the equation above:

m ₂₂ = (1/2) {m ₁₂ + m ₃₂ + 2}

m ₂₂ = (1/2) {1 + 4 + 2} = (1/2){7} = 7/2.

So, m ₂₂ < ¥ , so state 2 is a .

m _ii = q_ii + å _{k¹ j} q_ik (m _ki + 1)

So,

m ₃₃ = q₃₃ + å _{k¹ j} q_3k (m _k3 + 1)

m ₃₃ = 0 + {q₃₁ (m ₁₃ + 1)} + {q₃₂ (m ₂₃ + 1)} + {q₃₄ (m ₄₃ + 1)}

m ₃₃ = 0 (m ₁₃ + 1) + (1/2)(m ₂₃ + 1) + (1/2) (m ₄₃ + 1)

m ₃₃ = (1/2)(m ₂₃ + 1) + (1/2) (m ₄₃ + 1)

We know from above that f₂₃ = 1, so m ₂₃ < ¥ . So we can use the equation:

m ₂₃ = q₂₃ + å _{k¹ j} q_2k (m _k3 + 1)

m ₂₃ = 1/2 + {q₂₁ (m ₁₃ + 1)} + {q₂₂ (m ₂₃ + 1)} + {q₂₄ (m ₄₃ + 1)}

m ₂₃ = 1/2 + {(1/2) (m ₁₃ + 1)} + {0 (m ₂₃ + 1)} + {0 (m ₄₃ + 1)}

m ₂₃ = 3/2 + (1/2) m ₁₃

We know from above that f₁₃ = 1, so m ₁₃ < ¥ . So we can use the equation:

m ₁₃ = q₁₃ + å _{k¹ j} q_1k (m _k3 + 1)

m ₁₃ = 0 + {q₁₁ (m ₁₃ + 1)} + {q₁₂ (m ₂₃ + 1)} + {q₁₄ (m ₄₃ + 1)}

m ₁₃ = 0 (m ₁₃ + 1) + 1 (m ₂₃ + 1) + 0 (m ₁₄ + 1)

m ₁₃ = m ₂₃ + 1

Using these two equations, we can solve for both.

m ₁₃ = m ₂₃ + 1

m ₁₃ = 3/2 + (1/2) m ₁₃ + 1

(1/2)m ₁₃ = 5/2

m ₁₃ = 10/2 = 5

m ₂₃ = 4

We know from above that f₄₃ = 1, so m ₄₃ < ¥ . So we can use the equation:

m ₄₃ = q₄₃ + å _{k¹ j} q_4k (m _k3 + 1)

m ₄₃ = 1 + {q₄₁ (m ₁₃ + 1)} + {q₄₂ (m ₂₃ + 1)} + {q₄₄ (m ₄₃ + 1)}

m ₄₃ = 1 + 0 (m ₁₃ + 1) + 0 (m ₂₃ + 1) + 0 (m ₁₄ + 1)

m ₄₃ = 1

Using these results, we can substitute it in the equation above:

m ₃₃ = (1/2)(m ₂₃ + 1) + (1/2) (m ₄₃ + 1)

m ₃₃ = (1/2)(4 + 1) + (1/2) (1 + 1) = (5/2) + 1 = 7/2.

So, state 3 is also .

Theorem 2.9.1, page 89. In an irreducible Markov chain, all states belong to the same class: either they are all transient, all null-recurrent, or all positive-recurrent states.

Theorem 2.9.2, page 89. An irreducible Markov chain has at most one stationary distribution (p ) and one of the following:

1. The states are all transient or null states, and there is no stationary distribution.
2. All states are ergodic, and there is exists a unique stationary distribution for p _j.

Note that p _j = 1/m _ii, for i = 1, 2, …, N. (Formula 2.251, page 89)

Example 5 - Look at example 3 above again:

Finding the stationary distribution:

p ₁ = 0× p ₁ + (1/4)× p ₂ + 0× p ₃ = (1/4)× p ₂, or p ₂ = 4× p ₁

p ₂ = 1× p ₁ + (1/4)× p ₂ + (1/2)× p ₃

p ₃ = 0× p ₁ + (1/2)× p ₂ + (1/2)× p ₃ = (1/2)× p ₂ + (1/2)× p ₃

p ₃ = (1/2)× p ₂ + (1/2)× p ₃ = (1/2)× 4× p ₁ + (1/2)× p ₃

(1/2)× p ₃ = 2× p ₁

p ₃ = 4× p ₁

1 = p ₁ + p ₂ + p ₃ = p ₁ + 4× p ₁ + 4× p ₁ = 9× p ₁, or p ₁ = 1/9

p ₂ = p ₃ = 4× p ₁ = 4× (1/9) = 4/9

p = [ ]

In the work above, we found that m ₂₂ = 9/4. Using the formula 2.251,

p ₂ = 1/m ₂₂ = 1/(9/4) = 4/9.

Note that this matches what we found above!

If we worked through the other states too we would get the appropriate answers! So, even though a given state may be transient, if it belongs to an irreducible aperiodic Markov chain all states are the same - if there's a unique stationary distribution then we know they are all ergodic!

Example 6 - revisit example 4.

p ₁ = 0× p ₁ + (1/2)× p ₂ + 0× p ₃ + 0× p ₄ = (1/2)× p ₂

p ₂ = 1× p ₁ + 0× p ₂ + (1/2)× p ₃ + 0× p ₄ = 1× p ₁ + (1/2)× p ₃

p ₃ = 0× p ₁ + (1/2)× p ₂ + 0× p ₃ + 1× p ₄ = (1/2)× p ₂ + 1× p ₄

p ₄ = 0× p ₁ + 0× p ₂ + (1/2)× p ₃ + 0× p ₄ = (1/2)× p ₃

p ₃ = (1/2)× p ₂ + 1× p ₄ = (1/2)× p ₂ + 1× (1/2)× p ₃

(1/2)× p ₃ = (1/2)× p ₂

p ₃ = p ₂

p ₄ = (1/2)× p ₂

1 = p ₁ + p ₂ + p ₃ = (1/2)× p ₂ + p ₂ + p ₂ + (1/2)× p ₂ = 3× p ₂, or p ₂ = 1/3

p ₂ = p ₃ = 1/3

p ₁ = (1/2)× p ₂ = (1/2)(1/3) = 1/6

p ₄ = (1/2)× (1/3) = 1/6

p = [ ]

Why don't they match up to what we had before?