0

I'm trying to understand some of the edge cases of Markov chain convergence. If we have a finite transition matrix $P$ and initial distribution $r$, then if $r, rP, rP^2, rP^3$ does not converge, what are the possibilities? Is the sequence of distributions eventually periodic? Might it be converging to a periodic sequence? Can it evolve "chaotically"?

theQman
  • 1,097
  • It will always be asymptotic to a periodic sequence, by which I mean there will be a $T \geq 1$ such that $rP^{nT+k}$ converges as $n\to\infty$ for every $k$. – Brian Moehring Apr 19 '21 at 18:20
  • How do we know this? – theQman Apr 19 '21 at 18:22
  • I'd have to find a link for the standard convergence results, but effectively it just follows by setting $T$ equal to the least common multiple of the periods of every recurrent state (this might not be the smallest such value, which depends on $r$) – Brian Moehring Apr 19 '21 at 18:36
  • Well, I can't find an exact reference for this case (I assume it's out there, but I'm not seeing it). Are you comfortable with the theorem that says "If $P$ is the transition matrix for a finite-state irreducible, aperiodic markov chain, then $\lim_{n\to\infty} rP^n = (\sum r_i) \pi$ where $\pi$ is the unique stationary distribution"? If so, I could at least give a good argument for why $rP^n$ is asymptotic (in $|\cdot|_1$) to a periodic sequence for your question. – Brian Moehring Apr 19 '21 at 21:10
  • Yes, I'm familiar with versions of that fact. – theQman Apr 20 '21 at 11:25

1 Answers1

0

A finite, time-homogeneous Markov chain will always be asymptotic to a periodic sequence, by which I mean there will be a $T > 0$ such that for any $k$ with $0 \leq k < T$, the sequence $rP^{nT+k}$ will converge.

To see this, let $T$ denote the least common multiple of the periods of the recurrent states, fix $k$, let $s := rP^k$, and let $Q := P^T$. Then we want to show that the sequence of distributions $sQ^n = rP^{nT+k}$ converges, so from this point on, I will be talking exclusively about the Markov chain with transition matrix $Q$ and initial distribution $s$. It will be helpful to let $\mathcal{C}$ denote the set of recurrent communication classes corresponding to $Q$, and let $e_i$ denote a unit mass at state $i$.

We may show that the period of every recurrent state is $1$. In particular, if $C \in \mathcal{C}$, then $Q$ restricted to $C$ is an aperiodic, irreducible, finite Markov chain, so there is a unique stationary distribution $\pi_C$ supported on $C$, and if $i \in C$ then $e_iQ^n \to \pi_C$.

Now let $L$ denote the set of transient states. For each $i \in L$ and each $C \in \mathcal{C}$, define $q(i,C)$ as the probability that a unit mass at $e_i$ will eventually end up in $C$. Then we may show $e_iQ^n \to \displaystyle\sum_{C\in \mathcal{C}}\pi_Cq(i,C).$

By linearity, we can put all of the above together as $$sQ^n = \sum_is_ie_iQ^n \to \sum_{C\in \mathcal{C}}\pi_C\left(\sum_{i\in C}s_i+ \sum_{i \in L}s_iq(i,C)\right)$$

Notes:

  1. I've led two steps with "we may show". I invite you to work out these steps, especially if you cannot see they're true.
  2. It's actually important that $\mathcal{C}$ is defined as the recurrent communication classes with respect to $Q$ rather than $P$. If $T \neq 1$, there will be some recurrent communication class $C_P$ with respect to $P$ that splits into at least two classes in $\mathcal{C},$ which means $Q$ restricted to $C_P$ wouldn't be irreducible.
  3. We may consider $$P = \left(\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1/2 & 1/2\end{array}\right)$$ and $r = \left(\begin{array}{ccc}0&0&1\end{array}\right)$ to see an example where $rP^n$ is not eventually periodic.
Brian Moehring
  • 21,088