HW problem 5.7 Math 504. Spring 2008. CSUF
by Nasser Abbasi
Problem
Answer
Part (A) First note that and .
Let us define as the event , then we write
But by conditioning on state of the chain at time instead of time , we write Note_1
But by definition, and ,Therefore the above becomes
Since and , we can rewrite the above as follows
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 that
Which can be written as
Let and let , and let , then the above can be written as Where is the identity matrix of order . Now let . hence
Therefore we can find (which is the ) if we can solve the above. i.e. if we can invert the matrix (i.e. is non-singular)
Now we need to show that is invertible. Recall that a Matrix is not invertible if we can find a vector such that .
Let us assume that is not invertible. Hence there exist a vector such that
In other words Now we show that it is not possible to find such a vector , showing that must therefore has an inverse.
We can always normalized the vector in (1) without changing this relation, hence we assume is normalized such that its largest component has length (we do this by dividing the vector by the largest component it had). Now (1) can be written in component form as follows
Since is normalized, it will have at least one component which is in value, and it can have components which are less than in value (we proof this part below). Let the set of the indices of those components of which are be the set and let the set of the indices of those components which are less than be the set . In other words
First, we show that the set can not be empty: Proof by contradiction. Assume is empty. Hence every element in the vector is . Let us pick one of these elements such that corresponds to a row number in the matrix where this row happens to sum to a value less than . Then we write
But since this row sums to less than one, then the RHS above is less than 1. Hence this is a contradiction, hence
Now that we showed the set is not empty, we can write (2) as a sum over the set and the set of indices. (We know the set is not empty by definition, since the vector is normalized, so it will have at least one element in the set ). Hence (2) becomes
Let us again pick one of those components which has value (we know there is at least one of these), and try to see if this equality holds for this row . So (3) becomes
But all the in the set have value , so the above can be simplified Now each in the term labeled above is less than (since it is the set ), so this means , therefore the sum in (4) could never add to if there are values that are non-zero when is in the set . (since the sum is being reduced from its original row sum). So for (4) to be satisfied, we need to have all the when is in the set .
What this means is that if , then the row in the matrix must have zero entries in the columns which correspond to the indices in the set As shown in this diagram as an example
In
the above diagram, I showed one example of the conclusion of above argument.
Of course the set
the way I drawn it does not have to be 'contiguous', it could be in any
pattern, as say the following
Therefore,
we see that
when
correspond to a state whose number is the same as the index value in the set
,
and
is a state whose number correspond to a state whose number is the same as the
index value in the set
What this means is that it is not possible to reach states that correspond to indices in the set from states which correspond to indices in the set
But this is the same as saying the matrix contains a closed subset. In other words, is reducible. However, this is not possible, since the matrix 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 such that . Hence does have an inverse. QED