6
$\begingroup$

given this transition matrix of markov chain

\begin{bmatrix} \dfrac{1}{2} & \dfrac{1}{4} & \dfrac{1}{4}\\ 0 & \dfrac{1}{2} & \dfrac{1}{2} \\ 1 & 0 & 0 \end{bmatrix}

which represents transition matrix of states $a,b,c$.

$a$ has probability of $\dfrac{1}{2}$ to itself $\dfrac{1}{4}$ to $b$ $\dfrac{1}{4}$ to $c$.

b has probability $\dfrac{1}{2}$ to itself and $\dfrac{1}{2}$ to $c$

c has probability $1$ to $a$.

  1. why is state $c$ aperiodic?

I know that it is irreducible and state a is aperiodic because it has self loop so all states are aperiodic. but i can't see why states that don't have self loops are aperiodic.

if one can explain what exactly aperdicity and why state c is aperiodic from the definition of aperiodicity itself.

$\endgroup$
1
  • $\begingroup$ a followup related question [0 1,1 0] is a transition matrix with period 2.why does it have a stationary uniform distribution , after n samples I know that will be half times in state 1 and half of the times in state 2. help will be welcomed. joseph. $\endgroup$
    – joseph
    Mar 29, 2015 at 17:21

4 Answers 4

6
$\begingroup$

Definition Let $p_{ii}^{(n)}$ denote the probability of returning to state $i$ at step $n$ and let $t\in\{2, 3\dots\}$. State $i$ is said to be periodic with period $t$ iff

  • $ p_{ii}^{(n)} = 0 $ for $n \neq t, 2t, \dots$
  • $ p_{ii}^{(n)} \neq 0 $ for $n = t, 2t, \dots$

If we can not find a $t$ such that this holds, the state is said to be aperiodic.

Solution In your case it would be useful to draw a transition diagram of the matrix. You can see that if the chain starts in $c$ then returns to $c$ are possible at steps $2, 3, 4, 5, \dots$. As we can not find a $t$ such that the definition holds, $c$ is an aperiodic state.

╔═════╦═════╗
║  n  ║  p  ║
╠═════╬═════╣
║ 1   ║ 0   ║
║ 2   ║ >0  ║
║ 3   ║ >0  ║
║ ... ║ ... ║
╚═════╩═════╝
$\endgroup$
1
  • $\begingroup$ Very clear. thanks alot.I would like also to know the second part that aperiodicity in MCMC. $\endgroup$
    – joseph
    Mar 31, 2015 at 7:01
6
$\begingroup$

For an irreducible markov chain,

Aperiodic: When starting from some state i, we don't know when we will return to the same state i after some transition. We may see the state i after 1,2,3,4,5.. etc number of transition.

Periodic: When we can say that we can return to the state i after some transition with certainty. If a state is reachable after transition step of 2,4,6,8...etc. then it has periodicity of 2.

For your example, if you draw a transition diagram you can see that it is possible to arrive at each state after different transition(1,2,3,4) which means there is no period to a state or state is aperiodic.

This link also gives a good understanding of markov chain perdiocity.

$\endgroup$
5
$\begingroup$

In an irreducible chain all states belong to a single communicating class. Periodicity is a class property. This means that, if one of the states in an irreducible Markov Chain is aperiodic, say, then all the remaining states are also aperiodic. Since, $p_{aa}^{(1)}>0$, by the definition of periodicity, state a is aperiodic. As the given Markov Chain is irreducible, the rest of the states of the Markov Chain are also aperiodic.

We can also observe that, the two-step transition probability matrix(TPM) for the given chain is given by \begin{equation*} P^{(2)}=\left( \begin{array}{ccc} 0.5& 0.25& 0.25\\ 0.5& 0.25& 0.25\\ 0.5& 0.25& 0.25\\ \end{array}\right) \end{equation*} Note that, all the elements of $P^{(2)}$ are positive. This ensures that, $P^{(3)}>0, P^{(4)}>0$ and so on. The greatest common divisor of the times $2,3,4,\cdots$ is $1$. Hence, by the definition of periodicity, the period of every state is aperiodic.

$\endgroup$
0
$\begingroup$

For any state we find the possible no. Of steps in which we can return to the same state. If gcd of these nos. =1 then state is aperiodic. If gcd not equals 1 (say 'd'), then period equals 'd'.

For a self loop state it is possible to return to the state in 1,2,3,4........ steps. Gcd = 1. So the state is certainly aperiodic.

For non self loop state we find possible no. of steps and then find gcd which may be 1. This makes the state aperiodic. Here state 3 is non self loop but return to it is possible in 2,3,4,5...... steps which has gcd =1. So the state is aperiodic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.