Intuitive explanation for periodicity in Markov chains

Question

Can someone explain me in a intuitive way what the periodicity of a Markov chain is?

It is defined as follows:

For all states $i$ in $S$

$d_i$=gcd$\{n \in \mathbb{N} | p_{ii}^{(n)} > 0\} =1$

Thank you for your effort!

Answer 1

First of all, your definition is not entirely correct. Here is the correct definition from wikipedia, as suggested by Cyan.

---

Periodicity (source: wikipedia)

A state i has period k if any return to state i must occur in multiples of k time steps. Formally, the period of a state is defined as

k = $gcd\{ n: \Pr(X_n = i | X_0 = i) > 0\}$

(where "gcd" is the greatest common divisor). Note that even though a state has period k, it may not be possible to reach the state in k steps. For example, suppose it is possible to return to the state in {6, 8, 10, 12, ...} time steps; k would be 2, even though 2 does not appear in this list.

If k = 1, then the state is said to be aperiodic: returns to state i can occur at irregular times. In other words, a state i is aperiodic if there exists n such that for all n' ≥ n,

$Pr(X_{n'} = i | X_0 = i) > 0.$

Otherwise (k > 1), the state is said to be periodic with period k. A Markov chain is aperiodic if every state is aperiodic.

---

My Explanation

The term periodicity describes whether something (an event, or here: the visit of a particular state) is happening at a regular time interval. Here time is measured in the number of states you visit.

First Example:

Now imagine that the clock represents a markov chain and every hour mark a state, so we got 12 states. Every state is visted by the hour hand every 12 hours (states) with probability=1, so the greatest common divisor is also 12.

So every (hour-)state is periodic with period 12.

Second example:

Imagine a graph describing a sequence of coin tosses, starting at state $start$ and state $heads$ and $tails$ representing the outcome of the last coin toss.

The transition probability is 0.5 for every pair of states (i,j), except $heads$ -> $start$ and $tails$ -> $start$ where it is 0.

Now imagine you are in state $heads$. The number of states you have to visit before you visit $heads$ again could be 1,2,3 etc.. It will happen, so the probability is greater 0, but it is not exactly predictable when. So the greatest common divisior of all possible number of visits which could occur before you visit $heads$ again is 1. This means that $heads$ is aperiodic.

The same applies for $tails$. Since it does not apply for $start$, the whole graph is not aperiodic. If we remove $start$, it would be.

Answer 2

Let $x$ be a state in some Markov chain. Consider the set $T(x)$ of all possible return times, that is, numbers $t$ such that there is a non-zero probability of returning to $x$ in exactly $t$ steps, starting from $x$. Notice that this is a purely graph-theoretic, not probabilistic notion, in the sense that, if you draw the directed graph underlying the Markov chain (and don't draw any edges corresponding to zero-probability transitions), then $T(x)$ is just the set of all lengths of directed cycles starting at $x$.

The set $T(x)$ has a remarkable property, which is that it is eventually periodic. What I mean by this is that there is some number $P$ such that past a certain point, all members of $T(x)$ are multiples of $P$, and all multiples of $P$ are in $T(x)$. So if you visualize the set $T(x)$ as dots on a line, the dots eventually become perfectly evenly spaced. The number $P$ is known as the period of $x$. When $P=1$, this just means that past a certain point, all return times to $x$ are possible, and $x$ is said to be aperiodic.

The proof that this is the case comes from the fact that $T(x)$ is closed under addition (if $t,s\in T(x)$, then $t+s\in T(x)$), and it turns out any set of positive integers closed under addition has this property. That $T(x)$ is closed under addition should be obvious if you think about it (remember that when we talk about "returning to $x$ in $t$ steps", we don't require that we never visit $x$ in between time). That sets closed under addition have this periodicity property is related to Bézout's identity. The period of $x$, as it turns out, is also equal to the GCD of $T(x)$ (because taking the GCD of an infinite set of numbers makes perfect sense, if you think about it). However, simply defining the period to be the GCD is a terrible way of doing things, pedagogically, because unless you know about this periodicity property, there's no apparent reason why the GCD should be relevant to anything.

If two states communicate, meaning it's possible to go from the first to the second and from the second to the first in some number of steps, then the two have the same period. This is easy to see. Since $x$ and $y$ communicate, it's possible to get from $x$ to $y$ in, say, $r$ steps, and from $y$ to $x$ in $s$ steps. Therefore if $t\in T(y)$, $r+t+s=t+(r+s)\in T(x)$. So if you shift $T(y)$ to the right by $r+s$, you get a subset of $T(x)$. For the same reason, if you shift $T(x)$ to the right by $r+s$, you get a subset of $T(y)$. Given that we know both of those sets are eventually evenly spaced, you can work out that this means the spacing on the two of them must be equal. Because of this, you can take a whole equivalence class of communicating states, and talk about the period of the class, and if you have an irreducible Markov chain (meaning all states communicate), then you can talk about the period of the Markov chain.

The period of an irreducible Markov chain is important because it tells you about the long-term dynamics of the chain. Imagine millions of particles all individually running through the Markov chain independently. Picture a heat-map, where states are color coded according to the amount of particles in that state. What you're picturing is really just a visualization of $\mu_0 M^t$, where $M$ is the transition matrix and $\mu_0$ the initial distribution of particles, the probability distribution of your state at time $t$ given that your starting point was chosen according to distribution $\mu_0$. If the chain is irreducible, then it turns out that this heat map will eventually stabilize over time. It will stabilize in one of two ways:

• If the chain is aperiodic, then the heat map eventually essentially stops changing. The distribution of the particles is at equilibrium.
• If the chain has period $P$, then after a while the heat map will be seen to cycle between $P$ different distributions, in a kind of "dynamic" equilibrium. The distribution of the particles washes back and forth like a pendulum, in a fixed pattern, forever.

Note that in both cases, the particles are all still moving, and indeed each particle is still independently following the Markov chain and moving completely randomly. It's only the overall distribution of particles that becomes predictable.

Above is a periodic Markov chain, with the time-$t$ distribution visualized as a heatmap (red means high, blue means low - with apologies to any colorblind readers). You can see an animated version to watch the distribution fall into its periodic dynamic equilibrium, starting with all particles concentrated in one state:

Notice that you might naively think the period of the chain is $6$, given the way it looks, but in fact it contains cycles of length both $6$ and $10$, the GCD of which is $2$, so the period of the chain is $2$, as you will see if you watch the animation.

Answer 3

To be short, periodic is when you visit each state at uniform rate, aperiodic is when you visit each state at random rate.