Understanding Markov Chains

Question

Recently, in my computer science class, we implemented a Markov Chain in Python to generate the probability of a certain word appearing after another. Syntactically, it's easy enough to understand. However, my issues arise when trying to understand it in mathematical notation.

I have constructed a Markov Chain where $$p_{1,1}=\frac13$$ $$p_{1,2}=\frac23$$ $$p_{2,1}=1$$$$p_{2,2}=0$$

I also have that $v_0=(1,0)$. From this, I'm trying to calculate the probability of being in state 1 after exactly 2 steps. My first attempt was to look at the Law Of Probability for Markov Chains, but I'm not quite aware of the explicit arguments I would input for this. Drawing out the Markov Chain is no issue; it's merely a matter of figuring out probabilities.

First, I tried to calculate the probability of being in state 1; that is,

$$P(X_t=1) \sum_{i}^{} P(X_t = 1\mid X_{t-1}=i)P(X_{t-1}=i)$$

However, I am unsure of the explicit arguments I would pass in.

Answer 1

Where you wrote $v_0=(1,0)$, I'm guessing you meant the probabilities of being initially in states $1$ and $2$ are respectively $1$ and $0$, i.e. you know you're initially in state $1$.

To be in state $1$ after two steps means either you stayed in state $1$ throughout the process or you went to state $2$ at the first step and returned to state $1$ at the second step. $$ \Pr( 1 \mapsto 1 \mapsto 1) + \Pr(1\mapsto 2\mapsto 1) = \left(\frac 1 3\cdot\frac 1 3\right) + \left(\frac 2 3 \cdot 1\right) = \frac 1 9 + \frac 2 3 = \frac 7 9. $$

Answer 2

Make a matrix $\mathbf P$ using the four $p_{ij}$'s you have. Then square the matrix (using the rules of matrix multiplication). Then element $(1,1)$ of $\mathbf P^2,$ often written as $p_{11}^{(2)},$ is the probability you seek.

This answer should match the the one provided in the 2nd Comment of @JMoravitz. The only advantage of my method is that $\mathbf P^n$ would give you the answer $p_{11}^{(n)}$ to questions such as, "Starting in state $1$, what is the probability I'll be back in state $1$ at step $n$?"

The Chapman-Kolmogorov equations can be used to show that the $n$th power of the transition matrix has the property I'm claiming.

Addendum. Long-run probability of being in state 1.

Intuitive: Imagine a round trip from state $1$ to state $2$ and then back to state $1.$ How long does an average trip take? You leave state $1$ with probability $2/3,$ so the geometric average waiting time to leave is $3/2 = 1.5$ steps. Then you spend exactly one step in state $2.$ So the average round trip takes $2.5$ steps, of which $1.5$ is spent in state $1.$ In the long run you spend $\frac{1.5}{2.5} = 3/5$ of time in state $1.$ [This method always works when there is only one possible path for a round trip, as in a 2-state Markov chain, or a sufficiently simple chain with more than two states.]

Algebraic: For this simple chain, the long-run probabilties are also the steady state probabilities. The vector $\mathbf\sigma = (\sigma_1, \sigma_2)$ is a steady state distribution if $\mathbf\sigma \mathbf P = \mathbf\sigma.$ It is easy algebra to solve the resulting equation $\frac{2}{3}\sigma_1 + \sigma_2 = \sigma_1$ along with the obvious $\sigma_1 + \sigma_2 = 1$ to get $\sigma_1 = 3/5$ and $\sigma_2 = 2/5.$ [The second equation from $\mathbf\sigma \mathbf P = \mathbf\sigma$ is $\frac{2}{3}\sigma_1 = \sigma_2,$ which is redundant. When there are two states and $\mathbf P$ is a $2 \times 2$ matrix, one of the two equations from $\mathbf\sigma \mathbf P = \mathbf\sigma$ will always be redundant.] As @JMoravitz also Commented, for chains with more states, you can use find the eigen vectors of $\mathbf P$ (with a computer if convenient), but no need for that here.