HW problems 8.4 and 8.5, Mathematics 504 CSUF, spring 2008

by Nasser Abbasi

\clearpage

Problem 8.4


p_8_4_large.png

Part(i)


p_8_4_one.png
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
Note_1 .

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 MATH with corresponding one step probability transitions of MATH. (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 MATH 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 MATH, $i=1\cdots r$

  2. $f\left( x\right) $ $<$ all of MATH, $i=1\cdots r$

  3. $f\left( x\right) $ $=$ all of MATH, $i=1\cdots r$

Consider case (1)
: Since MATH for some $i$, then for this specific $y_{i}$, MATH where $k<1$, hence MATH 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 MATH (if more if found, it will not change the argument). Now we add all the probabilities MATH and we found that this sum is MATH where the $a$ is for that vertex which had MATH. 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 MATH 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
p_8_4_two.png
Now we consider case (2)
. In this case since MATH for each $i$, then MATH., then the sum of the probabilities of transitions from $x$ is MATHand we do not need to compensate by adding MATH to make up for the deficit. However since now MATH 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 MATH, 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 MATH for $i=1\cdots r.$ In other words, $f\left( x\right) $ is CONSTANT. In this case MATH $,$then the sum of the probabilities of transitions from $x$ is MATHand we do not need to compensate by adding MATH 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 MATH, 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 MATHThis diagram helps me remember these formulas


p_8_4_three.png

Now if the chain the time reversible as well, then MATH,
p_8_4_four.png
Then the balance equation (1) becomesMATHHence we need to show that the equation above holds to show the chain is time reversible.

Let the LHS of (2) be MATH and let RHS of (2) be MATH. Then we will show that LHS=RHS for the following 3 cases:

  1. MATH

  2. MATH

  3. MATH

Case(1): Since MATH let these be some value, say $z$MATH and MATH We see that (3) is the same as (4), hence

LHS=RHS for case (1)
.

case(2): MATHMATH andMATH Hence we see that (5) is the same as (6). Hence

RHS=LHS for case(2)
.

case (3):MATHMATH andMATH 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.

Problem 8.5


p_8_5_large.png

Part(a)

The following is the Hastings-Metrpolois algorithm implementation.

This algorithm generates a time-reversible M.C. (referred to as $p$ in the lecture notes) given an irreducible M.C. (called $q$ or the original chain) and given a stationary distribution $\pi$ for that chain.


p_8_5_algorithm_box.png

Input: $f\left( x\right) $ defined over the states $x,$ and MATH which represents the number of edges connected to $x$

  1. For each state $x$ calculate MATH and for each state $x$ calculate $edge(x)$

  2. compute MATH whenever MATH else set MATH

  3. Select a state $x$ by random to start from.

  4. Let $n=1$ and let $X_{1}=x$

  5. Let $S$ be the set of all states that can be reached in one step from $x$. These will be the states $y$ in which MATH

  6. Select a state $y$ from $S$ by random (using a uniform MATH random number generator)

  7. Calculate MATH

  8. Generate a random number $u$ from MATH

  9. Let $n=n+1$

  10. Compare $u$ to MATH.

  11. IF MATH THEN $X_{n}=y$ (select the new state) ELSE $X_{n}=X_{n-1}$ (stay in same state) ENDIF

  12. Let $x=X_{n}$

  13. If $n>$ some Max number of iterations or if we reached some convergence limit Then go to 15

  14. GOTO 5

  15. Algorithm is complete. Now generate the time reversible MC as follows

    1. Scan the state path generate $X_{n}\,\ $and count how many times state $x$ switches to state $y$ in one step

    2. Do the above for all the states $x$

    3. Divide the above number by the total number of steps made to generate MATH

Since the problem now asks to implement Hastings-Metropolis, then I used the data given at the end of the problem and implemented the above simulation using that data Note_2 . Please see appendix for code and final $P$ matrix generated.

Part (a1)

This is similar the problem 8.4 part(I). To show that the $p$ (final M.C.) is irreducible, we need to show that there exist no closed proper subsets. Since the graph $G$ is connected, then we just need to show whenever there is an edge between vertex $x$ and $y$ then there corresponds in the chain representation of the final $p$ matrix a non-zero MATH and also a non-zero MATH. This will insure that the each state can transition to each other state, just as each vertex can be visited from each other vertex (since it is a connected graph).

Let us consider any 2 vertices say $x,y$ with a direct edge between them (this is the only case we need to consider due to the argument above). We need to show the resulting MATH and MATH are non-zero

Consider MATH first. Since MATH HenceMATH Then it is clear that whenever there is an edge between $x,y$ then MATH since both $f\left( x\right) $ and $f\left( y\right) $ are positive (not zero) and also edge(x) and edge(y) are non-zero as well. Hence we see that MATH. Similar argument shows that MATH.

This shows that M.C. represented by $P$ is irreducible
.

Part (a2)

The condition for regular chain $P$ is that there exist at least one state $x$ such that MATHFrom (1) above we can decide under what conditions this will occur.

Consider a vertex $x$ with MATH edges from it connected to vertices MATH. Then from (1) we see that MATH The condition for having MATH is that MATH, since this will cause MATH to be some quantity less than $\frac {1}{r}$ and so when summing over all $r$ there will be a deficit in the sum and we have to compensate for it to make it $1$ by adding MATH. But for MATH to be less than ONE means that

MATH

Hence the condition for finding an Aperiodic state is finding a vertex $x$ such that the above holds
for one of the vertices $y_{i}$ this vertex is directly connected to. For example, if $y_{i}$ had the same number of edges from it as does $x$, then the condition will be that MATH. And if $y_{i}$ has less or more edges from it than $x$ has, then we need the ratio MATH to be less than MATH.

The above is the same as saying MATHmust be constant for the $p$ not to be regular
.

Part(A3)

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 MATH Now if the chain the time reversible as well, then MATH, Then the balance equation (1) becomesMATH

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

There are 3 cases to consider:

  1. MATH

  2. MATH

  3. MATH

For case (1), LHS of equation (3) simplifies to MATH and the RHS of (3) simplifies to MATH, but since MATH, then LHS=RHS.

Hence balance equation (3) is satisfied for case (1).

For case(2), LHS of (3) simplifies MATH and RHS of (3) simplifies to MATHthen LHS=RHS.

Hence balance equation (3) is satisfied for case (2)
.

For case (3), LHS of (3) simplifies MATH and RHS of (3) simplifies to MATHthen LHS=RHS.

Hence balance equation (3) is satisfied for case (3)
.

Hence in all 3 cases we showed the balance equation is satisfied.

Hence M.C. is time reversible
.

Part(b)

A small program written to construct the $P$ matrix directly following instructions on page 8.4 of lecture notes. The following is the resulting $P$ matrix


p_matrix.png

Now to check that the final chain $P$ is regular, it was raised to some high power to check that all entries in the $P^{m}>0$. This is the result


p_matrix_raise.png

The above verifies that the final matrix $p$ is regular.

Using the Hastings-Metropolis simulation algorithm, the convergence to the above matrix was slow. Had to make 2 million observation to be within 3 decimal points from the above. Here is the $P$ matrix generated from Hastings algorithm for $N=2,000,000$


p_matrix_hastings.png

Appendix (Implementation of part(a) and part(b))

The graph for part(a) and part(b) is the following


p_8_5_graph.png