# What is number coming from in $\gcd$ of Markov chain topic?

For example for [6], $d(1) = \gcd\{3, 5, 6,\, ...\} = 1$.

What do $3,5,6$ calculated from?

-
Seems to be times $k$ when $P_k(1,1)>0$ where $P_k(i,j) = \mathsf P(X_k = j|X_0 = i)$. – Ilya Jan 3 '13 at 12:08

For other readers' reference, this question refers to the Markov chain in [6] shown here:

and $d(i)$ is the $\gcd$ of those $n>0$ for which there is a path from $i$ to $i$ of length $n$.

How can you get from $1$ to $1$ in $>0$ steps?

Well you can go $1 \to 2 \to 3 \to 1$. That's $3$ steps.

Or you can go $1 \to 2 \to 3 \to 4 \to 3 \to 1$. That's $5$ steps.

Or you can go $1 \to 2 \to 3 \to 1 \to 2 \to 3 \to 1$. That's $6$ steps.

And so on.

-
Very clear understanding. I like it. – Scott Jan 3 '13 at 12:25