HW problem 5.7 Math 504. Spring 2008. CSUF

by Nasser Abbasi

Problems


problem_6_3_and_6_5.png

Problem 6.3

Part(A)

Let $I_{n}$ be an indicator variable defined asMATH Hence MATH Now we see that MATH Now, let $b_{ij}$ be entry in matrix $B$ where MATH, then the above can be written asMATH Which is the same as writingMATH When $i=j$, then MATH otherwise it is $0$. HenceMATH Let the set of transient states be $T$, and using chapman-kolmogorov, the above can be written asMATH But MATH is multiplying the $i^{th}$ row of the $Q$ matrix by the $j^{th}$ column of the $Q$ matrix. which is the $\left( i,j\right) $ entry of the matrix $Q^{2}$, and MATH is multiplying the $i^{th}$ row of the $Q^{2}$ matrix we just obtained, by the $j^{th}$ column of the $Q$ matrix, which is the $\left( i,j\right) $ entry of the matrix $Q^{3}$. Continue this way, we obtain that MATH is the entry $i,j$ in matrix $Q^{4}$ and so on.

Hence we see that $b_{ij}$ is the $\left( i,j\right) $ entry of a matrix resulting from MATH QED.

Part(B) From part(A), we obtained that MATH is the $\left( i,j\right) $ entry in the matrix resulting from the sum MATH. Since this is a $Q$ matrix, then we know its elements will all go to zero an $n$ gets very large, so this is a convergent sum, hence MATH.MATH Therefore

MATH is the $\left( i,j\right) $ entry in the matrix MATH
Problem 6.5

Part(A) I solve this part in 2 ways, first by conditioning on next state, as required, and then by the counting method explained in the lecture.

by conditioning on next state. Let $I$ be the set of all states. ThenMATH But by Markov property, chain state on next step depends only on current state. Hence MATH and also since MATH then (1) can be written asMATH Now, when $X_{1}=j$, then MATH since chain already in state $j$ after one step. Therefore (2) can be rewritten asMATH But MATH is the same as writing MATH , so the above becomesMATH Using the notation shown in the problem, the above becomes MATH QED.

Now solve part(a) using first a counting argument, and using the following diagram as a guide
6_dot_5.png
Then we write (letting MATH and MATH)MATH But MATH hence the above becomesMATH
Part(B) We start from the result of part (A) which isMATH Multiply both sides by $w_{i}$ and obtainMATH Sum over all possible states $i$ and obtainMATH But MATH and MATH, hence (2) becomesMATH Now, since MATH is the stationary state vector, then it satisfies the following relationMATH Where $P$ is the one step probability transition matrix. The solution to the above is given byMATH Where $k$ is any state. Using (4) into RHS of (3), we can rewrite (3) asMATH Now looking at the LHS, we see that the first sum labeled $A$ counts for all the $w^{\prime}s$ and the second sum labeled $B$ also counts for all the $w^{\prime}s$ except for the $j$ term. Hence if we subtract $B$ from $A$, only the term $m_{jj}w_{j}$ will survive. Hence (5) becomesMATH orMATH QED.
Part (C)

If we wait for the chain to arrive at its steady state (i.e. we the chain probability state vector does not change, or $w=wP$), then we observe the chain from that point on, for a long period of time, say $T$. The number of times the chain will be in state $j$ during this time $T$ is then given by $w_{j}T$, since $w_{j}$ is the probability of the chain being in state $j$. So, to find the average number of time units (steps) it took for the chain for go from state $j$ back to state $j$ we need to divide $T$ by the number of times the chain was in state $j$ during this time, which we just found as $w_{j}T$

Hence MATH

Intuitively this makes sense. Since the smaller the probability that the chain will be in state $j$ we would expect the time between the events that the chain is in state $j$ to become larger, So the relation should be an inverse one, as was found. QED