mxbob468 said:
Well I didn't make it up on my own? I got the term from
here.
OK, but I have read numerous papers and books about Markov chains over many decades and have never before seen or heard that term. It appears the author may be making up his/her own nomenclature. Anyway, let's continue.
This is in fact exactly what I have.
This part I don't understand. My understanding is that stationary/steady-state distributions are joint distributions ie vectors whose entries sum to 1. Are you saying that if I start in some state wp1 then over time my joint distribution will evolve into some, possibility different, joint distribution and that's what you're calling the steady-state? That makes sense of course but I don't see how it helps me find the joint distribution (ie row vector by which I left multiply my transition matrix) that is invariant under the transition (in this instance where I have 3 different classes).
Why is the bolded part true?
The quantity f(i,j) = probability that j is visited eventually, starting from i. If j' and j are in the same closed class, then (with probability 1) j is eventually visited if and only if j' is eventually visited, so f(i,j) = f(i,j').I'm not sure I understand what you mean by steady-state probability here.
A steady-state probability distribution ##\pi_i = (\pi_{i,j},j=1,2,\ldots,n)## (for starting state i) is one that satisfies
\pi_{i,j} = \sum_{k} \pi_{i,k} P_{kj},
which can be written as
\mathbf{p}_i = \mathbf{p}_i \mathbf{P}
where ##\mathbf{p}_i = (\pi_{i,1},\pi_{i,2}, \ldots, \pi_{i,n})## is a row-vector, and ##\mathbf{P}## is the one-step transition matrix. When there is a single closed class (possibly several transient classes) the steady-state vector is the same for all starting states so we can drop the i subscript and just write ##(\pi_1, \pi_2, \ldots, \pi_n)##. Note that a steady-state exists, even for a periodic chain (even though a limiting distribution does not). I will show you an example of this below.
I'm sure that's the case.
The quantities ##f_{i,j} = f(i,j) \equiv \Pr\{ \exists\: t \geq 1: \: X_t = j|X_0= i\}## are the "visit" probabilities to state j; they can be obtained from the first-passage distributions, as follows. Let ##T_{i,j}## be the (possibly defective random variable), which is the first time that state j is reached, starting from state i. (The random variable ##T## is defective if ##\Pr(T < \infty) < 1##.) In other words, let
T_{i,j} = \cases{ \text{smallest }n \text{ such that }X_n = j ,& \text{ if such }n\text{ exists} \\<br />
\infty & \text{ otherwise} }
The first-passage probability distribution from i to j is
f_{i,j}(n) = \Pr \{ T_{i,j} = n \}, n = 1,2, \ldots
and the attainment or visit probability is
f_{i,j} = \Pr \{ T_{i,j} < \infty \} = \sum_{n=1}^{\infty} f_{i,j}(n).
These satisfy the linear equations
f_{i,j} = p_{i,j} + \sum_{k: k \neq j} p_{i,k} f_{k,j}, \forall \: i \neq j
For fixed terminal state j these are linear equations in ##f_{1,j}, f_{2,j} \ldots, f_{j-1,j}, f_{j+1,j}, \ldots, f_{n,j}##.
Note that those linear equations do not have a unique solution. The simple solution ##f_{i,j} = 1 \, \forall i,j## always satisfies the equations, but is not always the solution that respects the probabilistic definitions. To get unique solutions consistent with probabilistic meanings we need to use additional information about the class structure of the MC. For example, if state j is transient and state i is persistent, you cannot get ever get from i to j, so f(i,j) = 0. If i and j are in different closed classes, then f(i,j) = 0. If i and j are in the same closed class then f(i,j) = 1. (These come from theorems about the T_{i,j}, not from the linear equations.) Finally, as I said already, if j and j' are in the same closed class then f(i,j) = f(i,j'); this follows most easily from "j is attained if and only if j' is attained", but it can also be proved from the linear equations.
Let's bring this all together in an example:
\mathbf{P} = \pmatrix{1/8 & 3/8 & 1/4 & 0 & 1/ 8& 1/8\\<br />
5/16 & 3/16 & 1/16 & 1/8 & 3/16 & 1/8 \\<br />
0 & 0 & 1/4 & 3/4 & 0 & 0\\<br />
0 & 0 & 1/2 & 1/2 & 0 & 0 \\<br />
0 & 0 & 0 & 0 & 0 & 1 \\<br />
0 & 0 & 0 & 0 & 1 & 0}
Class T1 ={1,2} is transient, while classes C2 = {3,4} and C3 = {5,6} are persistent (closed). Class C2 is "ergodic", so the 2x2 submatrix on rows/columns 3,4 has a limiting distribution ##(\pi_3,\pi_4) = (2/5,3/5)##. Class C3 is periodic, so its submatrix (on rows/columns 5,6) does not have a limit; however, it has a stationary (long-run) distribution ##(\pi_5,\pi_6) = (1/2,1/2)##. This makes sense, since if we start in class C3 then in the long run we spend 50% of the time in each of states 5 and 6. If P_3 is the submatrix of rows/colums 5,6, we have ##(\pi_5,\pi_6) = (\pi_5, \pi_6) P_3##.
Using a computer algebra program such as Maple we can quite easily get a closed-form expression for the matrix ##\mathbf{P}^n##; some of its elements will be different for even or odd n, because of the periodic states 5 and 6. Anyway, we have
\mathbf{P}_e \equiv \lim_{n \to \infty} \mathbf{P}^{2n} =<br />
\pmatrix{0 & 0 & 7/38 & 21/76 & 69/247 & 257/988 \\<br />
0 & 0 & 31/190 & 93/380 & 66/247 & 321/988 \\<br />
0 & 0 & 2/5 & 3/5 & 0 & 0 \\<br />
0 & 0 & 2/5 & 3/5 & 0 & 0 \\<br />
0 & 0 & 0 & 0 & 1 & 0 \\<br />
0 & 0 & 0 & 0 & 0 & 1 }
and
\mathbf{P}_o \equiv \lim_{n \to \infty} \mathbf{P}^{2n+1} = \pmatrix{0 & 0 & 7/38 & 21/76 & 257/988 & 69/247 \\<br />
0 & 0 & 31/190 & 93/380 & 321/988 & 66/247 \\<br />
0 & 0 & 2/5 & 3/5 & 0 & 0 \\<br />
0 & 0 & 2/5 & 3/5 & 0 & 0 \\<br />
0 & 0 & 0 & 0 & 1 & 0 \\<br />
0 & 0 & 0 & 0 & 0 & 1 }
The steady-state matrix is
\mathbf{Q} = \frac{1}{2} \mathbf{P}_e + \frac{1}{2} \mathbf{P}_o <br />
=\pmatrix{0 & 0 & 7/38 & 21/76 & 41/152 & 41/152 \\<br />
0 & 0 & 31/190 & 93/380 & 45/152 & 45/152 \\<br />
0 & 0 & 2/5 & 3/5 & 0 & 0 \\<br />
0 & 0 & 2/5 & 3/5 & 0 & 0 \\<br />
0 & 0 & 0 & 0 & 1/2 & 1/2 \\<br />
0 & 0 & 0 & 0 & 1/2 & 1/2 }
You can verify directly that ##\mathbf{Q} = \mathbf{Q \, P}##.
So, how on Earth would we get the elements of Q without using a computer algebra package to raise P to high powers? Note first that the elements of Q in rows/columns 3..6 are exactly as stated before: we have solutions of the equations
q_3 = q_3 P_{3,3} + q_4 P_{4,3}\\ q_4 = q_3 P_{3,4} + q_4 P_{4,4}
etc. For the transient states we have
f_{13} = f_{14} = 35/76, \: f_{23} = f_{24} = 31/76 \\<br />
f_{15} = f_{16} = 41/76, \: f_{25} = f_{26} = 45/76.
We can get these from the previous equations. For example,
f_{13} = (1/4) + (1/8)\,f_{13}+(3/8)\, f_{14}\\<br />
f_{14} = 0 + (1/4) \, f_{34} + (1/8)\,f_{13}+(3/8)\, f_{14}\\<br />
f_{23} = (1/16) + (1/8) \, f_{34} + (5/16)\,f_{23} + (3/16) \, f_{24}\\<br />
f_{24} = (1/8) + (1/16) \, f_{43} + (5/16)\,f_{23} + (3/16) \, f_{24}
Since we know ##f_{34} = f_{43} = 1## the ##f_{13}, f_{14}## equations are exactly the same, as are the ##f_{23}, f_{24}## equations. That establishes ##f_{13} = f_{14}## and ##f_{23} = f_{24}## if you do not believe it already. Similarly, ##f_{15} = f_{16}, f_{25} = f_{26}## follows from the equations and using ##f_{56} = f_{65} = 1##.
Finally, for transient starting states we have ##q_{1,1} = q_{1,2} = q_{2,1} = q_{2,2} = 0## because states 1 and 2 are transient, so will eventually be "left" and so will not be occupied for any positive long-run fraction of time. In addition we have
q_{1,3} = f_{13} q_{3,3}, \;q_{1,4} = f_{14}q_{4,4}
etc. You can demonstrate this directly from the numerical results, but it is also simple to see from probabilistic considerations: the expected long-run fraction of time we are in state 3 equals the probability we get to class C2, times the long-run fraction of time we are in state 3, given we are in class C2. When translated, that gives the result stated already.
OK, that's enough for now.
