L24.7 Generic Convergence Questions

TL;DR

In Markov chains, the long-term convergence of probabilities and the vanishing effect of the initial state are not always true, as demonstrated by certain examples.

Transcript

We have observed in the simple example from the previous clip that when the Markov chain initially starts in state one, the probability that it finds itself in state one after a long period of time converges to a constant value, in our case, 2/7. In addition, if the Markov chain initially starts in state two, the probability that it finds itself in... Read More

Key Insights

• ⛓️ Convergence of probabilities in Markov chains is not guaranteed for all chains, especially those with a periodic structure.
• 🖤 The alternation between probabilities is a sign of lack of convergence.
• ⌛ Certain Markov chains have a lasting impact of the initial state on the probabilities, where the influence does not vanish over time.
• ⛓️ Unreachable states in a Markov chain can affect the importance of the initial state.
• 🟰 Symmetry in probabilities can result in the equal likelihood of transitioning towards different states.
• 🥹 Long-term convergence and vanishing initial state effect are properties that hold for "nice" Markov chains but not universally.
• ⛓️ Periodicity in a Markov chain can disrupt convergence.

Questions & Answers

Q: Does the probability of a Markov chain converging to a constant value always happen?

No, convergence is not guaranteed for all Markov chains. Some chains, like those with a periodic structure, do not converge. In these cases, the probabilities alternate between values.

Q: Is the importance of the initial state always negligible in the long run?

No, the influence of the initial state may not vanish in some cases. In Markov chains where certain states are unreachable from others, the initial state does have a lasting impact on the probabilities.

Q: Can you provide an example where convergence fails in a Markov chain?

Consider a simple Markov chain where being in state two means you will never be in state two at the next transition. Eventually, you will return to state two, but the probabilities alternate between 0 and 1, and convergence fails.

Q: What happens in a Markov chain where starting in state one leads to staying there forever?

In such a case, if you start in state one, there is no way to escape. Therefore, the probability of being in state one always remains 1. The influence of the initial state never diminishes in this example.

Summary & Key Takeaways

• When a Markov chain starts in state one, the probability of it being in state one after a long time converges to 2/7. The same convergence happens when it starts in state two.

• However, this convergence is not always true. Some Markov chains, like the one with a periodic structure, do not converge.

• In certain cases, the importance of the initial state does not vanish over time, as shown by a Markov chain where starting in state one leads to staying there forever.