Give an example of a $2\times 2$ regular transition matrix $T$ and an initial state probability vector $x$ such that all the entries in $T^{1000}$x is still different from the steady state vector we get in the long run. (Question is about Markov Chains).
I have tried several different $2\times 2$ transition matrices with a probability vector such as $(0.7,0.3)$ but $T^{1000}$x always equals the steady state vector. I want such a transition matrix so that $T^{1000}$x is different from the steady state vector at the first decimal point.
1 Answer
Intuitively, we should choose a Markov chain which is close to one which fails to approach its steady state. For instance, consider $$ T = \pmatrix{10^{-n} & 1 - 10^{-n}\\1 - 10^{-n} & 10^{-n}} = (1 - 10^{-n}) \pmatrix{0&1\\1&0} + 10^{-n} \pmatrix{1&0\\0&1}\\ = \frac 12 \pmatrix{1&1\\1&-1} \pmatrix{1&0\\0&2 \cdot 10^{-n} - 1}\pmatrix{1&1\\1&-1} $$ with $n \geq 1$. The limit as $n \to \infty$ is periodic, which means that it won't approach its steady state. However, for any $n$, this Markov chain has steady state $(0.5,0.5)$. The thousandth power of this matrix will be $$ T^{1000} = \frac 12 \pmatrix{1&1\\1&-1} \pmatrix{1&0\\0&[2 \cdot 10^{-n} - 1]^{1000}}\pmatrix{1&1\\1&-1} $$ It suffices to select $n$ such that $|2 \cdot 10^{-n} - 1|^{1000} \geq 0.1$. That is, $$ (1 - 2 \cdot 10^{-n})^{1000} \geq 0.1 \implies\\ (1 - 2 \cdot 10^{-n}) \geq 0.9977 $$ It should suffice to take $n \geq 3$. That is, $$ T = \pmatrix{0.001 & 0.999\\0.999 & 0.001} $$ should do the job. In particular, use the probability vector $(1,0)$.
