1
$\begingroup$

Given any positive integer, how can I think of a Markov Chain (states and transition probabilities) to have that integer as the period of two of its states?

Thanks.

  • 0
    Care to accept an answer or are you trying to reproduce [this fiasco](http://math.stackexchange.com/q/23638/6179)?2011-11-27

2 Answers 2

1

To be truly stochastic, assume that the state space of the Markov chain is $S\times C_d$ where $C_d=\mathbb{Z}/d\mathbb{Z}$ is the discrete circle of size $d$. And assume that the only transitions with positive probabilities go from some state $(x,k)$ to some state $(y,k+1)$ with $x$ and $y$ in $S$ and $k$ in $C_d$. Then the period of this Markov chain is a multiple of $d$. To ensure that the period is exactly $d$, assume further that there exists an $S$-valued sequence $(x_k)$ indexed by $C_d$ (hence $x_{k+d}=x_k$ for every integer $k$) such that the transition from $(x_k,k)$ to $(x_{k+1},k+1)$ has positive probability, for every $k$ in $C_d$. (Note that every Markov chain with period $d$ may be encoded like this.)

4

Hint: No probabilities are needed. Just put them on a (directed) cycle.