Difficult to comprehend markov chain and its characteristics

Question

If $Y_n$ is a sequence of independent random variables with $P(Y_n=0)=2/3,P(Y_n=1)=1/6,P(Y_n=2)=1/6$ and $X_n$ with $X_0=0$ is defined as

$$X_{n+1}= \left\{ \begin{array}{lr} X_n-Y_n & : &X_n=3\\ X_n-1+Y_n &: &1\leq X_n\leq2\\ Y_n & : &X_n=0 \end{array} \right.$$

I don't understand this markov chain. What is its state space and what is the transition matrix? Also: how do I find its invariant distribution when I have the transition matrix?

Answer 1

The state space is $\{0,1,2,3\}$. When at state $0$, the next state has the distribution $\mathcal{Y}$ which is the distribution of $Y_n$. When at state $1$, the next state also has the distribution $\mathcal{Y}$, while at state $2$, it has the distribution $\mathcal{Y}+1$. Finally, at state $3$, it has distribution $3-\mathcal{Y}$. All in all, we obtain the following transition matrix (depending on your convention, this might be the transpose of the transition matrix): $$ \begin{pmatrix} 2/3 & 2/3 & ? & ? \\ 1/6 & 1/6 & ? & ? \\ 1/6 & 1/6 & ? & ? \\ 0 & 0 & ? & ? \end{pmatrix} $$ I'll let you figure out the other half of the matrix. Given the transition matrix, the invariant distribution is an eigenvector corresponding to the eigenvalue $1$ (and is additionally a distribution). Sometimes the invariant distribution is not unique, though in this case it is.

Answer 2

First work out the state space. It's built into the setup that the state space contains $\{ 0,1,2,3 \}$, and in fact it doesn't contain anything else, as you can check by checking that if $X_n \in \{ 0,1,2,3 \}$ then no matter what $Y_n$ is, you will have $X_{n+1} \in \{ 0,1,2,3 \}$.

From there just build the transition matrix case by case. (Here I use the convention that $P_{ij}$ is the probability to go from $i$ to $j$; sometimes the reverse convention is used.) The first row will be the transition probabilities for when $X_n$ is currently $0$. These are just the probabilities for $Y_n$, i.e. $2/3,1/6,1/6,0$ (since $Y_n$ is never $3$). The second row is the transition probabilities for when $X_n$ is currently $1$. And so on.

To find the invariant distribution, you have to solve the linear system $\pi = \pi P$ where $P$ is the transition probability matrix and $\pi$ is the invariant distribution (written as a row vector), and then normalize it into a probability distribution. This can be done by row reduction; numerically it is usually better to use an eigenvalue routine (since singular matrices are "bad" numerically speaking).