HW problems 8.4 and 8.5, Mathematics 504 CSUF, spring 2008
by Nasser Abbasi
\clearpage
M.C.
is irreducible if there exist no proper closed subset in the state space.
Since we are given that the graph
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
between 2 vertices
,
there corresponds a probability of transition from state
to
which is not zero, and also a probability of transition from state
to
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
is irreducible.
But from the definition of
we see that if there is an edge
then
exist and is not zero, and
exist and is not zero (since
is finite). This completes the proof.
A finite M.C. is regular when, for some integer
,
contains only positive elements.
This implies that the one step transition matrix
must have at least one entry along the diagonal
that is none-zero (If all elements along the diagonal are zero, then
will always contain at least one zero element no matter how large
is). But a diagonal element not being zero is the same as saying that at least
one state must be aperiodic (if
then the period is one).
To proof that the above chain is regular, we then need to show that at least one state is aperiodic.
Since at most a vertex can have
edges, then we can find a vertex
with
edges connecting it to vertices
with corresponding one step probability transitions of
.
(If we can't find such a vertex, the argument will apply to any other vertex,
just replace
with the number of edges on that vertex and the argument will still apply).
Now let us consider
and compare it to each of the
where the
is the vertex with direct edge from
.
There are 2 cases to consider:
at least one of the
,
all of
,
all of
,
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
This
diagram helps me remember these formulas
Now if the chain the time reversible as well, then
,
Then
the balance equation (1)
becomesHence
we need to show that the equation above holds to show the chain is time
reversible.
Let the LHS of (2) be
and let RHS of (2) be
.
Then we will show that LHS=RHS for the following 3 cases:
Case(1): Since
let these be some value, say
and
We see that (3) is the same as (4), hence
case(2):
and
Hence we see that (5) is the same as (6). Hence
case
(3):
and
We see that (7) is the same as (8), hence
The following is the Hastings-Metrpolois algorithm implementation.
This algorithm generates a time-reversible M.C. (referred to as
in the lecture notes) given an irreducible M.C. (called
or the original chain) and given a stationary distribution
for that chain.
Input:
defined over the states
and
which represents the number of edges connected to
For each state
calculate
and for each state
calculate
compute
whenever
else set
Select a state
by random to start from.
Let
and let
Let
be the set of all states that can be reached in one step from
.
These will be the states
in which
Select a state
from
by random (using a uniform
random number generator)
Calculate
Generate a random number
from
Let
Compare
to
.
IF
THEN
(select the new state) ELSE
(stay in same state) ENDIF
Let
If
some Max number of iterations or if we reached some convergence limit Then go
to 15
GOTO 5
Algorithm is complete. Now generate the time reversible MC as follows
Scan the state path generate
and
count how many times state
switches to state
in one step
Do the above for all the states
Divide the above number by the total number of steps made to generate
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
matrix generated.
This is similar the problem 8.4 part(I). To show that the
(final M.C.) is irreducible, we need to show that there exist no closed proper
subsets. Since the graph
is connected, then we just need to show whenever there is an edge between
vertex
and
then there corresponds in the chain representation of the final
matrix a non-zero
and also a non-zero
.
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
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
and
are non-zero
Consider
first. Since
Hence
Then it is clear that whenever there is an edge between
then
since both
and
are positive (not zero) and also edge(x) and edge(y) are non-zero as well.
Hence we see that
.
Similar argument shows that
.
The condition for regular chain
is that there exist at least one state
such that
From
(1) above we can decide under what conditions this will occur.
Consider a vertex
with
edges from it connected to vertices
.
Then from (1) we see that
The condition for having
is that
,
since this will cause
to be some quantity less than
and so when summing over all
there will be a deficit in the sum and we have to compensate for it to make it
by adding
.
But for
to be less than ONE means that
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
Now if the chain the time reversible as well, then
,
Then the balance equation (1)
becomes
Hence we need to show that the equation (3) above holds to show the chain is time reversible.
There are 3 cases to consider:
For case (1), LHS of equation (3) simplifies to
and the RHS of (3) simplifies to
,
but since
,
then LHS=RHS.
For case(2), LHS of (3) simplifies
and RHS of (3) simplifies to
then
LHS=RHS.
For case (3), LHS of (3) simplifies
and RHS of (3) simplifies to
then
LHS=RHS.
Hence in all 3 cases we showed the balance equation is satisfied.
A small program written to construct the
matrix directly following instructions on page 8.4 of lecture notes. The
following is the resulting
matrix
Now to check that the final chain
is regular, it was raised to some high power to check that all entries in the
.
This is the result
The above verifies that the final matrix
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
matrix generated from Hastings algorithm for
The graph for part(a) and part(b) is the following