0

Question:

Find the smallest $n$ for which there exists a Markov chain with $n$ states such that it is periodic simultaneously with period $4$ and $6$? Put "does not exist" if such a Markov chain does not exist.

The definition of periodicity I use:

State $a$ is periodic if there exists an integer $d>1$ (called the period of $a$) such that if the probability of returning via a path of length $k$ is greater than zero for some $k$, then $d|k$.
A Markov chain having no periodic states is called a non-periodic chain.

My answer is $n = 12$, because we can create a chain as below (cycle that can be traversed in only one direction):

Markov chain

Then, every return path has a length of $12 = lcm(4,6)$.
Since $4$ and $6$ divide $12$ so both of them can be a period.
Is this a correct solution?

Michał
  • 675
  • 1
  • 12
  • Periods $4$ and $6$, what does that mean? You might say that the identity operator/matrix has period $1$, so it has period $n$, $\forall n \in \mathbb{N}$, including $4$ and $6$. If, however, period $4$ means having period $4$ but not lower and period $6$ means period $6$ and not lower, then how can you have periods $4$ and $6$ together? – Dominique Feb 13 '24 at 08:36
  • @Dominique I have added the definition of periodicity that I use to my question. I have looked at other definitions and often the period is the gcd of the lengths of all paths. Then you are right that such a chain does not exist, because the gcd cannot be $4$ and $6$ at the same time. – Michał Feb 13 '24 at 08:54

0 Answers0