4.11.1 Problem 8.4

Part(i)

M.C. is irreducible if there exist no proper closed subset in the state space.  Since we are given that the graph \(G\) is connected, then this means it is possible to visit each vertex from any other vertex in the graph. But does a connected graph implies no proper closed subset of the corresponding M.C.? The answer is YES. If we view each vertex as state, we just need to show that for each edge in \(G\) between 2 vertices \(x,y\), there corresponds a probability of transition from state \(x\) to \(y\) which is not zero, and also a probability of transition from state \(y\) to \(x\) which is also not zero. By showing this, we conclude that the M.C. will switch (in some number of steps) to any state from any other state, which implies there is no closed subset, hence \(P\) is irreducible.

But from the definition of \(p(x,y)\) we see that if there is an edge \((x,y)\) then \(p(x,y)\) exist and is not zero, and \(p(y,x)\) exist and is not zero (since \(r\) is finite). This completes the proof.

Part(ii)

A finite M.C. is regular when, for some integer \(m\), \(P^{m}\) contains only positive elements.

This implies that the one step transition matrix \(P\) must have at least one entry along the diagonal \(P_{ii}\) that is none-zero (If all elements along the diagonal are zero, then \(P^{m}\) will always contain at least one zero element no matter how large \(m\) is). But a diagonal element not being zero is the same as saying that at least one state must be aperiodic (if \(P_{ii}>0\) then the period is one).

Hence the condition for the M.C. to be regular is that at least one state must be aperiodic

².

To proof that the above chain is regular, we then need to show that at least one state is aperiodic.

This is the proof

:

Since at most a vertex can have \(r\) edges, then we can find a vertex \(x\) with \(r\) edges connecting it to vertices \(y_{1},y_{2},\cdots ,y_{r}\) with corresponding one step probability transitions of \(p\left ( x,y_{1}\right ) ,p\left ( x,y_{2}\right ) ,\cdots ,p\left ( x,y_{r}\right ) \). (If we can’t find such a vertex, the argument will apply to any other vertex, just replace \(r\) with the number of edges on that vertex and the argument will still apply).

Now let us consider \(f\left ( x\right ) \) and compare it to each of the \(f\left ( y_{i}\right ) \) where the \(y_{i}\) is the vertex with direct edge from \(x\). There are 2 cases to consider:

1. \(f\left ( x\right ) >\) at least one of the \(f\left ( y_{i}\right ) \), \(i=1\cdots r\)
2. \(f\left ( x\right ) \) \(<\) all of \(f\left ( y_{i}\right ) \), \(i=1\cdots r\)
3. \(f\left ( x\right ) \) \(=\) all of \(f\left ( y_{i}\right ) \), \(i=1\cdots r\)

Consider case (1): Since \(f\left ( x\right ) >f\left ( y_{i}\right ) \) for some \(i\), then for this specific \(y_{i}\), \(\ p\left ( x,y_{i}\right ) =\frac {1}{r}\min \left \{ 1,\frac {f\left ( y\right ) }{f\left ( x\right ) }\right \} =\frac {1}{r}k\) where \(k<1\), hence \(p\left ( x,y_{i}\right ) =a\) where \(a<\frac {1}{r}\). Lets assume there was only one \(y_{i}\) such that the above is true. I.e. at least one of the vertices connected to \(x\) had \(f\left ( y_{i}\right ) <f\left ( x\right ) \) (if more if found, it will not change the argument). Now we add all the probabilities \(p\left ( x,y_{i}\right ) \) and we found that this sum is \(\overset {(r-1)\ vertices}{\overbrace {\frac {1}{r}+\frac {1}{r}+\cdots +\frac {1}{r}}}+a\) where the \(a\) is for that vertex which had \(f\left ( y_{i}\right ) <f\left ( x\right ) \). Now since \(a<\frac {1}{r}\) then this sum will be LESS THAN ONE. But the sum of the one step probability transition from each state must be \(1\), hence to compensate, we must then have \(p\left ( x,x\right ) \) added to make up for the difference. Hence we showed that under case (1) we can find \(p_{ii}\) which is not zero. This diagram illustrate this case

Now we consider case (2).

In this case since \(f\left ( x\right ) <f\left ( y_{i}\right ) \) for each \(i\), then \(p\left ( x,y_{i}\right ) =\frac {1}{r}\min \left \{ 1,\frac {f\left ( y_{i}\right ) }{f\left ( x\right ) }\right \} =\frac {1}{r}\)., then the sum of the probabilities of transitions from \(x\) is \(\overset {r\ vertices}{\overbrace {\frac {1}{r}+\frac {1}{r}+\cdots +\frac {1}{r}}}=1\)and we do not need to compensate by adding \(p\left ( x,x\right ) \) to make up for the deficit. However since now \(f\left ( y_{i}\right ) >f\left ( x\right ) \) then if we view \(y_{i}\) as the \(x\) vertex and the \(x\) vertex as the \(y\),  and consider the probability transitions out of \(y_{i}\), then we are back to case (1) above. Hence in case (2) as well ,we can find a state in which \(p\left ( x,x\right ) >0\), Hence the chain is aperiodic, and since it is irreducible, then it is regular in this case as well.

Now consider case (3):

In this case \(f\left ( x\right ) =f\left ( y_{i}\right ) \) for \(i=1\cdots r.\) In other words, \(f\left ( x\right ) \) is CONSTANT. In this case \(p\left ( x,y_{i}\right ) =\frac {1}{r}\min \left \{ 1,\frac {f\left ( y_{i}\right ) }{f\left ( x\right ) }\right \} =\frac {1}{r}\) \(,\)then the sum of the probabilities of transitions from \(x\) is \(\overset {r\ vertices}{\overbrace {\frac {1}{r}+\frac {1}{r}+\cdots +\frac {1}{r}}}=1\)and we do not need to compensate by adding \(p\left ( x,x\right ) \) to make up for the deficit. This will be true for any node. Therefore, it is not possible to find at least one node with the probabilities attached to edges leaving it is less than one. Hence there are no state with \(p\left ( x,x\right ) >0\), hence in this case, the chain is not aperiodic, and hence the chain is NOT regular.

Conclusion: Condition for chain not to be regular is that \(f\left ( x\right ) \) be constant.

Part(iii)

Since the chain is irreducible, then there is a reverse Markov chain (proof is on page 8.1 and 8.2 of lecture notes). Hence for an irreducible chain the balance equations hold

\begin{equation} r\left ( x,y\right ) =\frac {\pi \left ( y\right ) p\left ( y,x\right ) }{\pi \left ( x\right ) }\tag {1}\end{equation}

This diagram helps me remember these formulas

Now if the chain the time reversible as well, then \(r\left ( x,y\right ) =p\left ( x,y\right ) \),

Then the balance equation (1) becomes

\begin{equation} \pi \left ( x\right ) p\left ( x,y\right ) =\pi \left ( y\right ) p\left ( y,x\right ) \tag {2}\end{equation}

Hence we need to show that the equation above holds to show the chain is time reversible.

Let the LHS of (2) be \(\pi \left ( x\right ) p\left ( x,y\right ) \) and let RHS of (2) be \(\pi \left ( y\right ) p\left ( y,x\right ) \). Then we will show that LHS=RHS for the following 3 cases:

1. \(f\left ( x\right ) =f\left ( y\right ) \)
2. \(f\left ( x\right ) <f\left ( y\right ) \)
3. \(f\left ( x\right ) >f\left ( y\right ) \)

Case(1): Since \(f\left ( x\right ) =f\left ( y\right ) \) let these be some value, say \(z\)

\begin{align} LHS & =\pi \left ( x\right ) p\left ( x,y\right ) \nonumber \\ & =\frac {f\left ( x\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\left ( \frac {1}{r}\min \left \{ 1,\frac {f\left ( y\right ) }{f\left ( x\right ) }\right \} \right ) \nonumber \\ & =\frac {z}{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\frac {1}{r} \tag {3}\end{align}

and

\begin{align} RHS & =\pi \left ( y\right ) p\left ( y,x\right ) \nonumber \\ & =\frac {f\left ( y\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\left ( \frac {1}{r}\min \left \{ 1,\frac {f\left ( x\right ) }{f\left ( y\right ) }\right \} \right ) \nonumber \\ & =\frac {z}{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\frac {1}{r} \tag {4}\end{align}

We see that (3) is the same as (4), hence  LHS=RHS for case (1).

case(2): \(f\left ( x\right ) <f\left ( y\right ) \)

\begin{align} LHS & =\pi \left ( x\right ) p\left ( x,y\right ) \nonumber \\ & =\frac {f\left ( x\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\left ( \frac {1}{r}\min \left \{ 1,\frac {f\left ( y\right ) }{f\left ( x\right ) }\right \} \right ) \nonumber \\ & =\frac {f\left ( x\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\frac {1}{r} \tag {5}\end{align}

and

\begin{align} RHS & =\pi \left ( y\right ) p\left ( y,x\right ) \nonumber \\ & =\frac {f\left ( y\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\left ( \frac {1}{r}\min \left \{ 1,\frac {f\left ( x\right ) }{f\left ( y\right ) }\right \} \right ) \nonumber \\ & =\frac {f\left ( y\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\frac {1}{r}\frac {f\left ( x\right ) }{f\left ( y\right ) }\nonumber \\ & =\frac {f\left ( x\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\frac {1}{r} \tag {6}\end{align}

Hence we see that (5) is the same as (6). Hence RHS=LHS for case(2).

case (3):\(f\left ( x\right ) >f\left ( y\right ) \)

\begin{align} LHS & =\pi \left ( x\right ) p\left ( x,y\right ) \nonumber \\ & =\frac {f\left ( x\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\left ( \frac {1}{r}\min \left \{ 1,\frac {f\left ( y\right ) }{f\left ( x\right ) }\right \} \right ) \nonumber \\ & =\frac {f\left ( x\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\frac {1}{r}\frac {f\left ( y\right ) }{f\left ( x\right ) }\nonumber \\ & =\frac {f\left ( y\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\frac {1}{r} \tag {7}\end{align}

and

\begin{align} RHS & =\pi \left ( y\right ) p\left ( y,x\right ) \nonumber \\ & =\frac {f\left ( y\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\left ( \frac {1}{r}\min \left \{ 1,\frac {f\left ( x\right ) }{f\left ( y\right ) }\right \} \right ) \nonumber \\ & =\frac {f\left ( y\right ) }{{\displaystyle \sum \limits _{v\in V}} f\left ( v\right ) }\frac {1}{r} \tag {8}\end{align}

We see that (7) is the same as (8), hence LHS=RHS for case (3) as well.

Hence we showed the balance equation for the time reversible condition is satisfied. QED.

²In addition, since we showed in part (i) that this chain is an irreducible chain, hence each state communicate with each other state, hence all states must be of the same type since all states are in the same communication class (Theorem 5.3.2). Then if one state is aperiodic, then the all states that communicate with it must also be aperiod (to be of the same type). Hence in an irreduible chain, if one state is aperiodic, then all states are aperiodic as well.