Given is markov chain - Determine the probability $f_1(n)$

Question

Given is markov chain $\left\{X_n\right\}_{n \in \mathbb{N}}$ with transition probabilities

$$M= \begin{pmatrix} 1/2 & 1/2 & 0 & 0 & 0 & 0 \\ 1/4 & 3/4 & 0 & 0 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 & 0 & 0 \\ 1/4 & 0 & 1/4 & 1/4 & 0 & 1/4 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \end{pmatrix}$$

Determine the probability $f_1(n)$ where you return to state $1$ after $n$ steps (for the first time).

I'm not sure how you can solve this because if I understood it correctly, we have $n$ steps and we are looking for a probability, so we have two unknowns...

Anyway, I think the correct way of calculating it is (don't miss the little exponent $n$ of that huge matrix!)

$$f_1(n) = \begin{pmatrix} 1/2 & 1/2 & 0 & 0 & 0 & 0 \\ 1/4 & 3/4 & 0 & 0 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 & 0 & 0 \\ 1/4 & 0 & 1/4 & 1/4 & 0 & 1/4 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \end{pmatrix}^n \cdot \begin{pmatrix} 1\\ 0\\ 0\\ 0\\ 0\\ 0 \end{pmatrix}$$

Here I'm stuck again for the same reason, I see no way of calculating the probability...? : /

Answer 1

Note that if the chain starts at state $1$ then it can return to the state in one step, i.e., $f_1(1) = 1/2$. Consider now that the chains goes to state $2$, once $X_n = 2$, the number of steps until the chain returns to state $1$ is distributed geometrically with $p=1/4$, hence $$ f_1(n) = \frac{1}{2}I\{n=1\}+\frac{1}{2}\left(\frac{3}{4} \right)^{n-2}\frac{1}{4}I\{n\ge2\} $$

Answer 2

You need this: $$ f_1(n) = \begin{pmatrix} 1, & 0, & 0, & 0, & 0, & 0 \end{pmatrix} \begin{pmatrix} 1/2 & 1/2 & 0 & 0 & 0 & 0 \\ 1/4 & 3/4 & 0 & 0 & 0 & 0 \\ 1/4 & 1/4 & 1/4 & 1/4 & 0 & 0 \\ 1/4 & 0 & 1/4 & 1/4 & 0 & 1/4 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & 0 & 1/2 & 1/2 \end{pmatrix}^n \cdot $$ What tells you it's done that way is that the rows add up to $1$ and the columns don't.

Then you can see that you have a Markov chain in which, once you're in state $1$ or state $2,$ you can never get to other states than $1$ and $2.$ And that means you only need to pay attention to the first two rows and the first two columns.