HW problem 5.7 Math 504. Spring 2008. CSUF

by Nasser Abbasi

Problem
problem_5_7.png
Answer

Part (A) First note that $Q_{0}=0$ and $Q_{1}=1$.

Let us define $\beta$ as the event MATH, then we writeMATH

But by conditioning on state of the chain at time $1$ instead of time $0$, we write Note_1 MATH

But MATH by definition, and MATH,Therefore the above becomesMATH

Since $Q_{k}=0$ and $Q_{m}=1$, we can rewrite the above as follows

MATH If we examine the sum more closely, we see it is a product of a vector and a matrix. Since if we expand for few terms we see thatMATH

Which can be written as

MATH

Let MATH and let MATH, and let MATH, then the above can be written asMATH Where $I$ is the identity matrix of order $m-1$. Now let MATH. hence

MATH

Therefore we can find $x$ (which is the $Q^{\prime}s$) if we can solve the above. i.e. if we can invert the matrix $A.$(i.e. $A$ is non-singular)

Part(B)

Now we need to show that $\left( I-B\right) $ is invertible. Recall that a Matrix $A$ is not invertible if we can find a vector $\QTR{bf}{v\neq 0}$ such that $A\QTR{bf}{v}=0$.

Let us assume that $\left( I-B\right) $ is not invertible. Hence there exist a vector MATH such that

MATH

In other wordsMATH Now we show that it is not possible to find such a vector $\QTR{bf}{v}$, showing that $\left( I-B\right) $ must therefore has an inverse.

We can always normalized the vector $\QTR{bf}{v}$ in (1) without changing this relation, hence we assume $\QTR{bf}{v}$ is normalized such that its largest component $v_{i}$ has length $1$ (we do this by dividing the vector by the largest component it had). Now (1) can be written in component form as follows


d.png

MATH

Since $\QTR{bf}{v}$ is normalized, it will have at least one component which is $1$ in value, and it can have components which are less than $1$ in value (we proof this part below). Let the set of the indices of those components of $\QTR{bf}{v}$ which are $1$ be the set $J$ and let the set of the indices of those components which are less than $1$ be the set $S$. In other wordsMATH

First, we show that the set $S$ can not be empty: Proof by contradiction. Assume $S$ is empty. Hence every element in the vector $\QTR{bf}{v}$ is $1$. Let us pick one of these elements $v_{i}=1$ such that $i$ corresponds to a row number in the matrix $B$ where this row happens to sum to a value less than MATH. Then we writeMATH

But since this row sums to less than one, then the RHS above is less than 1. Hence this is a contradiction, hence

the set $S$ can not be empty
.

Now that we showed the set $S$ is not empty, we can write (2) as a sum over the set $J$ and the set $S$ of indices. (We know the set $J$ is not empty by definition, since the vector $v$ is normalized, so it will have at least one element in the set $J$). Hence (2) becomesMATH

Let us again pick one of those $v_{i}$ components which has value $1$ (we know there is at least one of these), and try to see if this equality holds for this row $i$. So (3) becomesMATH

But all the $v_{j}$ in the set $J$ have value $1$, so the above can be simplifiedMATH Now each $v_{j}$ in the term labeled $Y$ above is less than $1$ (since it is the set $S$), so this means MATH, therefore the sum in (4) could never add to $1$ if there are values $p_{ij}$ that are non-zero when $j$ is in the set $S$. (since the sum MATH is being reduced from its original row sum). So for (4) to be satisfied, we need to have all the $p_{ij}=0$ when $j$ is in the set $S$.

Hence the sum labeled $Y$ is zero
.

What this means is that if $v_{i}=1$, then the $i^{th}$row in the matrix $B$ must have zero entries in the columns which correspond to the indices in the set $S\,.$ As shown in this diagram as an example


d2.png
In the above diagram, I showed one example of the conclusion of above argument. Of course the set $J$ the way I drawn it does not have to be 'contiguous', it could be in any pattern, as say the following


d3.png
Therefore, we see that $p_{js}=0$ when $j$ correspond to a state whose number is the same as the index value in the set $J$, and $s$ is a state whose number correspond to a state whose number is the same as the index value in the set $S.$

What this means is that it is not possible to reach states that correspond to indices in the set $J$ from states which correspond to indices in the set $S.$

Hence, once the chain is in a state in the set $J$ it is not possible to leave this set.

But this is the same as saying the matrix $B$ contains a closed subset. In other words, $B$ is reducible. However, this is not possible, since the matrix $B$ is taken from a subset of a chain which is irreducible, i.e. it contains no closed subsets, but we found at least one such subset.

Therefore, we conclude that our assumption which lead to this is invalid. Therefore, there exist no vector $\QTR{bf}{v\neq0}$ such that MATH. Hence $\left( I-B\right) $ does have an inverse. QED