Learn / Library / Linear algebra

Short walk on a line

Linear algebraEasy

A walker on the states $1$ , $2$ and $3$ moves once per step according to the transition matrix $P = \frac{1}{2} \frac{1}{4} 0 \frac{1}{2} \frac{1}{2} \frac{1}{2} 0 \frac{1}{4} \frac{1}{2}$ , where the entry in row $i$ , column $j$ is the probability of moving from state $i$ to state $j$ . Starting in state $1$ , what is the probability of being in state $3$ after exactly $2$ steps? Give a fraction in lowest terms.

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

You need the entry in row $1$ , column $3$ of $P^{2}$ ; list the routes that contribute to it.

Solution

The entry in row $1$ , column $3$ of $P^{2}$ sums, over every middle state $k$ , the products of the entries $(1, k)$ and $(k, 3)$ of $P$ .
From state $1$ the walker can only stay at $1$ or move to $2$ , so it cannot reach $3$ in one step.
So the only route is $1 \to 2 \to 3$ , with probability $\frac{1}{2} \times \frac{1}{4} = \frac{1}{8}$ .

Answer: $\frac{1}{8}$

Next question Back to the library