# A beginning look at transition probabilities

The previous post introduces the notion of Markov chains, more specifically discrete Markov chains. This and the next post focus on calculating transition probabilities.

Suppose that $\left\{X_n: n \ge 0 \right\}$ is a Markov chain with transition probability matrix $\mathbf{P}$. Elements of $\mathbf{P}$ are the one-step transition probabilities $P_{ij}$. As the Markov process moves through the states over time, the probabilities in the matrix $\mathbf{P}$ shows how likely the process will transition to state $j$ in the next time period if the process is currently in state $i$. Elements of $\mathbf{P}$ are conditional probabilities:

$(1) \ \ \ \ \ P_{ij}=P[X_{n+1}=j \lvert X_n=i]$

The transition probabilities described in (1) are independent of the time period $n$. These are called stationary transition probabilities. Markov chains with stationary transition probabilities are called stationary Markov chains or time-homogeneous Markov chains. One immediate goal is to develop the $n$-step transition probabilities $P_{ij}^n$ from the one-step transition probabilities $P_{ij}$. This is to be developed in the next post. This post focuses on basic calculations with $P_{ij}$.

Examples of Conditional Probabilities

We use examples to demonstrate conditional probabilities that can be calculated from the one-step transition probabilities $P_{ij}$. The calculation is based on the following transition probability matrix.

$\mathbf{P} = \bordermatrix{ & 0 & 1 & 2 \cr 0 & 0.6 & 0.2 & 0.2 \cr 1 & 0.3 & 0.5 & 0.2 \cr 2 & 0.4 & 0.3 & 0.3 \cr } \qquad$

Example 1
Determine the following conditional probabilities:

• $P[X_1=0, X_2=1 \lvert X_0=0]$
• $P[X_2=0, X_3=1 \lvert X_1=0]$
• $P[X_1=2, X_2=1,X_3=0 \lvert X_0=1]$

Note that the first two are identical since the transition probabilities are stationary. To calculate the first and third probabilities, it is a matter of linking up the one-step transition probabilities from one state to the next.

\displaystyle \begin{aligned} P[X_1=0, X_2=1 \lvert X_0=0]&=P[X_1=0 \lvert X_0=0] \times P[X_2=1 \lvert X_1=0] \\&=P_{00} \times P_{01} \\&=0.6 \times 0.2=0.12 \end{aligned}

$\displaystyle P[X_2=0, X_3=1 \lvert X_1=0]=P[X_1=0, X_2=1 \lvert X_0=0]=0.12$

\displaystyle \begin{aligned} P[X_1=2, X_2=1,X_3=0 \lvert X_0=1]&=P[X_1=2 \lvert X_0=1] \times P[X_2=1 \lvert X_1=2] \times P[X_3=0 \lvert X_2=1] \\&=P_{12} \times P_{21} \times P_{10} \\&=0.2 \times 0.3 \times 0.3=0.018 \end{aligned}

Example 2
Example 1 shows that the probability of a chain moving from along a path conditional on a starting state is simply the product of the transition probabilities on that path. We now calculate unconditional probability of a path. For this to be possible, we need to assume a distribution for the initial state.

Assume that $P[X_0=0]=0.4$, $P[X_0=1]=0.3$ and $P[X_0=2]=0.3$. Determine the following unconditional probabilities:

• $P[X_0=0,X_1=0,X_2=1]$
• $P[X_1=0,X_2=0,X_3=1]$
• $P[X_0=1,X_1=2, X_2=1,X_3=0]$

To calculate these unconditional probabilities, we multiply the transition probabilities on the path along with the probability of the first state in the path.

\displaystyle \begin{aligned} P[X_0=0,X_1=0,X_2=1]&=P[X_0=0] \times P[X_1=0 \lvert X_0=0] \times P[X_2=1 \lvert X_1=0] \\&=P[X_0=0] \times P_{00} \times P_{01} \\&=0.4 \times 0.6 \times 0.2=0.048 \end{aligned}

To calculate the second probability, we need to first compute $P[X_1=0]$. This can be done by conditioning on the initial state $X_0$.

\displaystyle \begin{aligned} P[X_1=0]&=P[X_0=0] \times P_{00}+ P[X_0=1] \times P_{10} +P[X_0=2] \times P_{20} \\&=0.4 \times 0.6 +0.3 \times 0.3+0.3 \times 0.4=0.45 \end{aligned}

\displaystyle \begin{aligned} P[X_1=0,X_2=0,X_3=1]&=P[X_1=0] \times P[X_2=0 \lvert X_1=0] \times P[X_3=1 \lvert X_2=0]\\&=P[X_1=0] \times P_{00} \times P_{01} \\&=0.45 \times 0.6 \times 0.2 \\&=0.054 \end{aligned}

The following gives the third probability.

\displaystyle \begin{aligned} P[X_0=1,X_1=2, X_2=1,X_3=0]&=P[X_0=1] \times P[X_1=2 \lvert X_0=1] \times P[X_2=1 \lvert X_1=2] \times P[X_3=0 \lvert X_2=1] \\&=P[X_0=1] \times P_{12} \times P_{21} \times P_{10} \\&=0.4 \times 0.2 \times 0.3 \times 0.3 \\&=0.0072 \end{aligned}

Note that each unconditional probability in this example is obtained by multiplying the corresponding conditional probability in Example 1 with the probability of the conditioned event.

Example 3
Sometimes we know for certain that the Markov chain starts in a given state. Then the unconditional probability of a path is simply the conditional probability of that path (conditioned on the initial state). Determine the three probabilities in Example 2 given that the chain starts in state 0 in the first two probabilities and the chain starts in state 1 in the third probability. The probabilities are:

• $P[X_0=0,X_1=0,X_2=1]$
• $P[X_1=0,X_2=0,X_3=1]$
• $P[X_0=1,X_1=2, X_2=1,X_3=0]$

For the first probability, $P[X_0=0,X_1=0,X_2=1]=P[X_0=0] \times P[X_1=0,X_2=1 \lvert X_0=0]$. With $P[X_0=0]=1$, $P[X_0=0,X_1=0,X_2=1]=P[X_1=0,X_2=1 \lvert X_0=0]=0.12$, the answer from Example 1.

For the second probability, we need to first calculate $P[X_1=0]$. Since $P[X_0=0]=1$, $P[X_1=0]=P[X_0=0] \times P_{00}=0.6$. Thus $P[X_1=0,X_2=0,X_3=1]=P[X_1=0] \times P_{00} \times P_{01}=0.6 \times 0.6 \times 0.2=0.072$, which is 0.6 times the corresponding conditional probability in Example 1.

Similarly, the third probability is

\displaystyle \begin{aligned} P[X_0=1,X_1=2, X_2=1,X_3=0]&=P[X_1=2, X_2=1,X_3=0 \lvert X_0=1] \\& =0.018\end{aligned}

Conditional Probabilities of Paths in Markov Chains

The conditional probabilities in the above examples are not difficult to do as long as the basic idea of conditional probabilities and the Markov property are understood. First, the idea of conditional probability. The idea is that the probability of the intersection of two events can be obtained by conditioning on one of the events. For example, given two events $A$ and $B$, we have

$(2a) \ \ \ \ \ P[A \cap B]=P[A] \times P[B \lvert A]$

$\displaystyle (2b) \ \ \ \ \ P[B \lvert A]=\frac{P[A \cap B]}{P[A]}$

The probability of the intersection of two events is the product of a conditional probability of one event given another event times the probability of the event being conditioned. Relation (2b) is the probability of the event $B$ given that event $A$ has occurred. Of course, the conditioned event has to have positive probability, i.e. $P[A]>0$.

Suppose that the event $A$ is $X=x$, the discrete random variable $X$ taking on the value $x$ and that the event $B$ is $Y=y$. Then we have the following relations.

$(3a) \ \ \ \ \ P[X=x,Y=y]=P[X=x] \times P[Y=y \lvert X=x]$

$\displaystyle (3b) \ \ \ \ \ P[Y=y \lvert X=x]=\frac{P[X=x,Y=y]}{P[X=x]}$

We can also write the conditional probability of $X=x$ conditioning on the event $Y=y$. Suppose we have a path in a Markov chain, $X_0=x_0,X_1=x_1,X_2=x_2,\cdots,X_n=x_n$. This is the event that the chain starts in state $x_0$ initially, then move to state $x_1$ in time 1 and so on and at time $n$ the chain is in state $x_0$. Conditioning on the initial state, consider the following conditional probability.

$\displaystyle (4) \ \ \ \ \ P[X_1=x_1,X_2=x_2,\cdots,X_n=x_n \lvert X_0=x_0]=\frac{P[X_0=x_0,X_1=x_1,X_2=x_2,\cdots,X_n=x_n]}{P[X_0=x_0]}$

Relation (4) can be further simplified since the random variables $X_0=x_0,X_1=x_1,X_2=x_2,\cdots,X_n=x_n$ satisfy the Markov property.

\displaystyle \begin{aligned} (5) \ \ \ \ \ P[X_1=x_1,X_2=x_2,\cdots,X_n=x_n \lvert X_0=x_0]&=P[X_1=x_1 \lvert X_0=x_0] \times P[X_2=x_2 \lvert X_1=x_1] \\& \ \ \ \times \cdots \times P[X_n=x_n \lvert X_{n-1}=x_{n-1}] \\&=P_{x_0,x_1} \times P_{x_1,x_2} \times \cdots \times P_{x_{n-1},x_n} \end{aligned}

Relation (5) says that the probability of a path in a Markov chain conditioning on the initial state is simply the product of the transition probabilities along the path. This is derived using the Markov property. Relation (5) can be established by an induction argument on the subscript $n$, i.e. the length of a path.

Clearly $P[X_1=j \lvert X_0=i]=P_{ij}$. This is the fundamental assumption in Markov chains. Now consider $P[X_1=j,X_2=k \lvert X_0=i]$.

\displaystyle \begin{aligned} P[X_1=j,X_2=k \lvert X_0=i]&=\frac{P[X_0=i,X_1=j,X_2=k]}{P[X_0=i]} \\&=\frac{P[X_0=i,X_1=j,X_2=k]}{P[X_0=i,X_1=j]} \times \frac{P[X_0=i,X_1=j]}{P[X_0=i]} \\&=P[X_2=k \lvert X_0=i,X_1=j] \times P[X_1=j \lvert X_0=i] \\&=P[X_2=k \lvert X_1=j] \times P[X_1=j \lvert X_0=i] \\&=P_{jk} \times P_{ij} \\&=P_{ij} \times P_{jk} \end{aligned}

Note that $P[X_2=k \lvert X_0=i,X_1=j]=P[X_2=k \lvert X_1=j]$ in the above derivation. This is Markov property in action since the probability of the future state depends only on the state immediately preceding it. Now that relation (5) is true for a path of length 2, the following shows how it is derived for length 3.

\displaystyle \begin{aligned} P[X_1=j,X_2=k,X_3=l \lvert X_0=i]&=\frac{P[X_0=i,X_1=j,X_2=k,X_3=l]}{P[X_0=i]} \\&=\frac{P[X_0=i,X_1=j,X_2=k,X_3=l]}{P[X_0=i,X_1=j,X_2=k]} \times \frac{P[X_0=i,X_1=j,X_2=k]}{P[X_0=i]} \\&=P[X_3=l \lvert X_0=i,X_1=j,X_2=k] \times P[X_1=j,X_2=k \lvert X_0=i] \\&=P[X_3=l \lvert X_2=k] \times P[X_1=j,X_2=k \lvert X_0=i] \\&=P_{ij} \times P_{jk} \times P_{kl} \end{aligned}

Note that going from the third line to the fourth line the Markov property is used. Relation (5) for length 2 is used at the end. The inductive proof keeps going and relation (5) is true for any path of arbitrary length.

The conditional probability in (4) by itself may not be special. With the additional assumption of Markov property, the conditional probability can be made to be a “chain” of one-step transition probabilities.

Using the idea of (3a), the unconditional probability of a path is:

\displaystyle \begin{aligned} (6) \ \ \ \ \ P[X_0=x_0,X_1=x_1,X_2=x_2,\cdots,X_n=x_n]&=P[X_0=x_0] \times P_{x_0,x_1} \\& \ \ \times P_{x_1,x_2} \times \cdots \times P_{x_{n-1},x_n} \end{aligned}

Relation (6) says that the unconditional probability of a path in a Markov chain is simply the conditional probability of the path conditioning on the initial state times the probability of the initial state.

More Examples

The earlier examples demonstrate relation (5) and relation (6). We now work a few more examples.

Example 4
There is a slightly different way to look at one unconditional probability $P[X_1=0,X_2=0,X_3=1]$ in Example 2. The first state in this path is $X_1=0$. We can condition on the initial state $X_0$.

$\displaystyle P[X_1=0,X_2=0,X_3=1]=\sum \limits_{k=0}^2 P[X_0=k,X_1=0,X_2=0,X_3=1]$

Then every one of the unconditional probability within the summation sign can be computed according to the idea in (6). Note that Example 2 gives the distribution of the initial state.

\displaystyle \begin{aligned} P[X_1=0,X_2=0,X_3=1]&=P[X_0=0,X_1=0,X_2=0,X_3=1]+ \\& \ \ P[X_0=1,X_1=0,X_2=0,X_3=1]+P[X_0=2,X_1=0,X_2=0,X_3=1] \\&=P[X_0=0] \times P_{00} \times P_{00} \times P_{01} +\\&\ \ P[X_0=1] \times P_{10} \times P_{00} \times P_{01}+P[X_0=2] \times P_{20} \times P_{00} \times P_{01} \\&=0.4 \times 0.6 \times 0.6 \times 0.2+\\&\ \ 0.3 \times 0.3 \times 0.6 \times 0.2 + 0.3 \times 0.4 \times 0.6 \times 0.2\\&=0.054 \end{aligned}

In calculating probabilities in a Markov chain, conditioning on the first step is a useful technique that will be used often in the subsequent posts.

Example 5
Consider a Markov chain with the following transition probability matrix.

$\mathbf{P} = \bordermatrix{ & 0 & 1 & 2 & 3 \cr 0 & 0.5 & 0.2 & 0.2 & 0.1 \cr 1 & 0.3 & 0.3 & 0.2 & 0.2 \cr 2 & 0.3 & 0.2 & 0.2 & 0.3 \cr 3 & 0 & 0 & 0 & 1 } \qquad$

State 3 is called an absorbing state since $P_{33}=1$. In other words, when the chain reaches state 3, it will never leave. Suppose that initially the Markov chain is in state 0 50% of the time, in state 1 30% of the time and in state 2 20% of the time. Calculate the probability $P[X_1=0,X_2=1,X_3=0,X_4=2]$.

We can condition on the initial state as in Example 4.

\displaystyle \begin{aligned} P[X_1=0,X_2=1,X_3=0,X_4=2]&=\sum \limits_{k=0}^2 P[X_0=k,X_1=0,X_2=1,X_3=0,X_4=2] \\&=P[X_0=0,X_1=0,X_2=1,X_3=0,X_4=2]+ \\&\ \ P[X_0=1,X_1=0,X_2=1,X_3=0,X_4=2]+\\&\ \ P[X_0=2,X_1=0,X_2=1,X_3=0,X_4=2] \\&=P[X_0=0] \times P_{00} \times P_{01} \times P_{10} \times P_{02}+ \\& \ \ P[X_0=1] \times P_{10} \times P_{01} \times P_{10} \times P_{02}+\\&\ \ P[X_0=2] \times P_{20} \times P_{01} \times P_{10} \times P_{02} \\&=0.0048\end{aligned}

Example 6
This is Example 1 in this previous post.

When a binary digit, 0 or 1, is transmitted through a communication system, it passes through several stages. At each stage, there is a probability $p$ that the digit is transmitted in error. Let $X_n$ be the digit that is the output at the $n$th stage. Then $\left\{X_n: n \ge 0 \right\}$ is a two-state Markov chain with the following transition probability matrix.

$\mathbf{P} = \bordermatrix{ & 0 & \text{ } & 1 \cr 0 & 1-p & \text{ } & p \cr \text{ } & \text{ } & \text{ } &\text{ } \cr 1 & p & \text{ } & 1-p \cr }$

Determine the following:

• If the digit to be sent is 0, determine the probability that no error occurs up to the second stage.
• If the digit to be sent is 0, determine the probability that a correct message is received at stage 2 through stage 4.

The first probability is $P[X_1=0,X_2=0 \lvert X_0=0]$. This is $P_{00} \times P_{00}=(1-p)^2$. To calculate the second probability, we can condition on the state in time 1. We first calculate $P[X_1=0]$ and $P[X_1=1]$. Since we know for certain that the initial state is 0, $P[X_1=0]=P_{00}=1-p$ and $P[X_1=1]=P_{01}=p$.

\displaystyle \begin{aligned} P[X_2=0,X_3=0,X_4=0]&=P[X_1=0,X_2=0,X_3=0,X_4=0]+P[X_1=1,X_2=0,X_3=0,X_4=0] \\&=P[X_2=0,X_3=0,X_4=0 \lvert X_1=0] \times P[X_1=0]+ \\&\ \ P[X_2=0,X_3=0,X_4=0 \lvert X_1=1] \times P[X_1=1] \\&=P_{00} \times P_{00} \times P_{00} \times (1-p)+ \\&\ \ P_{10} \times P_{00} \times P_{00} \times p\\&=(1-p)^4+p^2 \times (1-p)^2 \end{aligned}

Remarks

The calculation in this post involves very basic calculation with one-step transition probabilities, i.e. the elements of the transition probability matrix given in a Markov chain. The $n$-step transition probabilities are key to the development of the theory of Markov chains. The next post begins the discussion of Chapman-Kolmogorov equations.

Practice problems are in this companion blog.

$\text{ }$

$\text{ }$

$\text{ }$

$\copyright$ 2017 – Dan Ma

# Introducing Markov Chains

This post continues the discussion of the previous two posts – the previous post that looks at random walks informally through graphs and the previous post that defines random walks more formally. This post introduces the notion of Markov chains.

Stochastic Process

A stochastic process is a collection of random variables $\left\{X_t: t \in T \right\}$. Each element of the collection is a random variable $X_t$. The index $t$ is often regarded as time. Thus we refer to $X_t$ the state of the process at time $t$. Thus a stochastic process is a family of random variables that describes the evolution through time of some physical process.

The set $T$ is called the index set of the stochastic process. When $T$ is a countable set, e.g. $T=\left\{0,1,2,3,\cdots \right\}$, the stochastic process is said to be a discrete-time process. When the index set $T$ is an interval of the real number line, the stochastic process is said to be a continuous-time process. For example, $\left\{X_n: n=0,1,2,\cdots \right\}$ is a discrete-time stochastic process indexed by the non-negative integers whereas $\left\{X_t: t \ge 0 \right\}$ is a continuous-time stochastic process indexed by the non-negative real numbers. The state space of a stochastic process is defined as the set of all possible values that can be taken by the random variables $X_t$.

In the present discussion, we focus on discrete-time stochastic processes $\left\{X_n: n=0,1,2,\cdots \right\}$ where the state space $S$ is finite or countably infinite. When the state space is finite, the process is said to be a finite-state stochastic process.

We also assume that the state space $S$ consists of integers. Thus $S$ is either $\mathbb{N}=\left\{0,1,2,3,\cdots \right\}$ (the natural numbers) or $\mathbb{Z}=\left\{\cdots,-3,-2,-1,0,1,2,3,\cdots \right\}$ (the integers), or some subset of $\mathbb{N}$ or $\mathbb{Z}$.

If we know nothing about $X_n$ other than the fact that they are random variables, then there is not much we can say about the stochastic process $\left\{X_n: n=0,1,2,\cdots \right\}$. To make the discussion more meaningful, it is necessary to impose some additional structure on these random variables.

The simplest structure we can assume is that the random variables $X_n$ are independent random variables. This would be a good model for phenomena that can be regarded as random experiments in which the future states of the process are independent of past and present states. However, in many situations the assumption of independence is often unjustified. In many stochastic processes that arise in practice, past and present states can influence the future states.

Markov Chains

We consider stochastic processes that possess the following property: the future states of the process (conditional on both past and present states) depends only upon the present state, not on the past states leading up to the present state. This property is called the Markov property. Any stochastic process that possesses the Markov property is called a Markov chain. More specifically, to satisfy the Markov property, given the present state $X_n$ and the past states $X_{n-1},X_{n-2},\cdots,X_2,X_1,X_0$, the conditional distribution of the future state $X_{n+1}$ depends only on the present state $X_n$. Even more specifically, to satisfy the Markov property, the process must satisfy the following requirement:

$\displaystyle (1) \ \ \ \ P[X_{n+1}=j \lvert X_n=i,X_{n-1}=x_{n-1},\cdots,X_0=x_0]=P[X_{n+1}=j \lvert X_n=i]$

for all possible states $x_0,x_1, \cdots,x_{n-1},i,j$ and all non-negative integers $n$. Thus under the Markov property, the conditional distribution of the future state $X_{n+1}$ depends only on the present state $X_n$ and that all the states preceding the present state have no influence on the future state.

The conditional probabilities $P[X_{n+1}=j \lvert X_n=i]$ in (1) are called transition probabilities of the Markov chain. In the present discussion, we consider only the Markov chains in which the transition probabilities $P[X_{n+1}=j \lvert X_n=i]$ are independent of the current period $n$. Such Markov chains are called time-homogeneous Markov chains or stationary Markov chains. So the additional assumption of time-homogeneity means that the probability of transitioning into state $j$ from state $i$ is identical regardless of where the process is in the time scale (at the beginning in the process or later in the process).

With the transition probability $P[X_{n+1}=j \lvert X_n=i]$ independent of $n$, we can denote this probability by the states $i$ and $j$ only:

$\displaystyle (2) \ \ \ \ P_{ij}=P[X_{n+1}=j \lvert X_n=i]$

The probability $P_{ij}$ represents the probability that the process, starting in state $i$, will enter into state $j$ in the next period. Since the process must transition into one of the states in the state space in the next time period, $P_{ij}$, with $i$ fixed and $j$ varying, must represent a probability distribution. Thus $P_{i0}+ P_{i1}+\cdots=1$. Here we assume that the state space is the set of all non-negative integers.

The probabilities $P_{ij}$ are called one-step transition probabilities since they give the probabilities of transitioning from one state to another state in one period of time. The one-step transition probabilities are usually expressed in a matrix or a transition diagram. The following shows what a transition probability matrix looks like.

$\mathbf{P}= \left[\begin{array}{cccccc} P_{0,0} & P_{0,1} & P_{0,2} & \cdots & P_{0,m} \\ P_{1,0} & P_{1,1} & P_{1,2} & \cdots & P_{1,m} \\ P_{2,0} & P_{2,1} & P_{2,2} & \cdots & P_{2,m} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ P_{m,0} & P_{m,1} & P_{m,2} & \cdots & P_{m,m} \\ \end{array}\right]$

The above transition matrix is for a finite-state Markov chain with state space being $\left\{0,1,\cdots,m \right\}$. The probabilities in each row sum to 1. If the process is currently in state $i$, the row with the first index as $i$ (in this case the $(i+1)$st row) will give the probabilities of transitioning into all the states. If the state space is countably infinite, then each row would have infinitely many terms and there would be infinitely many rows.

In many situations, it is helpful to have a column label and row label to specify the states in the Markov chain. For example, a particle moves through the states 0, 1, 2, 3 and 4 according to a Markov chain described by the following transition probability matrix.

$\mathbf{P} = \bordermatrix{ & 0 & 1 & 2 & 3 & 4 \cr 0 & 0 & 0.6 & 0.2 & 0.1 & 0.1 \cr 1 & 0.5 & 0 & 0.2 & 0.2 & 0.1 \cr 2 & 0.4 & 0.2 & 0 & 0.1 & 0.3 \cr 3 & 0.2 & 0.3 & 0.2 & 0 & 0.3 \cr 4 & 0.6 & 0.2 & 0.1 & 0.1 & 0 \cr } \qquad$

In the above matrix, $P_{31}=0.3$, which means that when the Markov process is in state 3, it moves to state 1 with probability 0.3. As discussed earlier, the probabilities in a given row sum to 1, which makes sense since the probabilities in a row describes all possible moves when the process is a given state.

When it is helpful to do so, the transition probability matrices will have a row label and a column label. If the row label and column label are not given, we assume that the rows and columns are listed in ascending order (recall that the states are integers). The transition probability matrices can be displayed using square brackets or parentheses.

Examples

The key to working with Markov chains is the transition probabilities $P_{ij}$. These probabilities allow us describe the random transitions through the states over time. The remainder of this post gives several examples of Markov chains focusing on transition probability matrices.

Example 1
When a binary digit, 0 or 1, is transmitted through a communication system, it passes through several stages. At each stage, there is a probability $p$ that the digit is transmitted in error. Let $X_n$ be the digit that is the output at the $n$th stage. Then $\left\{X_n: n \ge 0 \right\}$ is a two-state Markov chain with the following transition probability matrix.

$\mathbf{P} = \bordermatrix{ & 0 & \text{ } & 1 \cr 0 & 1-p & \text{ } & p \cr \text{ } & \text{ } & \text{ } &\text{ } \cr 1 & p & \text{ } & 1-p \cr }$

Some typical problems might be:

• If the digit to be sent is 0, determine the probability that no error occurs up to the second stage.
• If the digit to be sent is 0, determine the probability that a correct message is received at stage 2.
• If the digit to be sent is 0, determine the probability that a correct message is received at stage $n$ where $n \ge 1$.

Example 2
Let’s consider the example of gambler’s ruin with finitely many states. Suppose that a gambler makes a series of one-unit bets against the house. For the gambler, the probabilities of winning and losing each bet are $p$ and $1-p$, respectively. Whenever the capital reaches zero, the gambler is in ruin and his capital remains zero thereafter. On the other hand, if the capital of the gambler increases to $m$, a large level of capital, the gambler quits playing. Let $X_n$ be the capital of the gambler after the $n$th bet. Then $\left\{ X_n: n=0,1,2,\cdots \right\}$ is a random walk, as discussed in the previous post. Since the future capital $X_{n+1}$ depends only on the current level of capital $X_n$ (up one unit or down one unit), this is also a Markov chain. The following is the transition probability matrix.

$\mathbf{P} = \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & \cdots & m \cr 0 & 1 & 0 & 0 & 0 & 0 & \cdots & 0 \cr 1 & 1-p & 0 & p & 0 & 0 & \cdots & 0 \cr 2 & 0 & 1-p & 0 & p & 0 &\cdots & 0 \cr 3 & 0 & 0 & 1-p & 0 & p &\cdots & 0 \cr \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \cr m & 0 & 0 & 0 & 0 & 0 &\cdots & 1 } \qquad$

The above is an $(m+1) \times (m+1)$ matrix. The states are of the process are $0,1,2,\cdots,m$. The states $0$ and $m$ are absorbing states since the process would stay there and not leave once the process arrive at these two states. Note that $P_{00}=1$ and $P_{mm}=1$. State 0 would be the state of ruin. State $m$ would mean the gambler becomes fabulously rich (if $m$ is large).

For the rows in between, the transition probabilities are $P_{i,i-1}=1-p$ and $P_{i,i+1}=p$. In other words, from state $i$, the process would go to state $i+1$ with probability $p$ and would go down to $i-1$ with probability $1-p$. More specifically, if $m=5$, the following is the transition probability matrix.

$\mathbf{P} = \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 \cr 0 & 1 & 0 & 0 & 0 & 0 & 0 \cr 1 & 1-p & 0 & p & 0 & 0 & 0 \cr 2 & 0 & 1-p & 0 & p & 0 & 0 \cr 3 & 0 & 0 & 1-p & 0 & p & 0 \cr 4 & 0 & 0 & 0 & 1-p & 0 & p \cr 5 & 0 & 0 & 0 & 0 & 0 & 1 } \qquad$

Assuming that the gambler has initial capital $d$ which is positive but small in comparison to $m$. For example, $d=10$ and $m=1000$. Some interesting questions are:

• If the staring capital is 10, what is the probability that the gambler’s capital will be 5 after 8 plays of the game?
• What is the probability of ruin for the gambler, i.e. reaching state 0?
• What is the mean time until reaching the absorbing states (ruin or fabulously rich)?

Example 3 (Restless Mouse)
A maze has eight areas as shown below.

The rat moves through the areas in the maze at random. That is, if an area has exits to $w$ areas, the rat moves to each of these $w$ areas with probability $1/w$. Let $X_n$ be the area the mouse is located in after the $n$th move. Then $\left\{X_n: n \ge 0 \right\}$ is a Markov chain with the following transition probability matrix.

$\mathbf{P} = \bordermatrix{ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \cr 1 & 0 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 \cr 2 & 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \cr 3 & 0 & 1/2 & 0 & 0 & 1/2 & 0 & 0 & 0 \cr 4 & 1/3 & 0 & 0 & 0 & 1/3 & 1/3 & 0 & 0 \cr 5 & 0 & 0 & 1/3 & 1/3 & 0 & 0 & 0 & 1/3 \cr 6 & 0 & 0 & 0 & 1/2 & 0 & 0 & 1/2 & 0 \cr 7 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 \cr 8 & 0 & 0 & 0 & 0 & 1/2 & 0 & 1/2 & 0 } \qquad$

Here’s some interesting questions about this Markov chain. Suppose that area 8 contains food and area 6 has a device for an electric shock.

• Given that the rat is placed in area 1 at the beginning, what is the probability that the rat will reach area 8 in 4 moves, in general in $n$ moves?
• Given that the rat is placed in area 1 at the beginning, what is the mean number of moves for the rat to reach area 8 or area 6?
• Given that the rat is placed in area 1 at the beginning, what is the probability that the rat will reach the food area before the electric shock area?

Next Steps

The concept of Markov chains has been introduced and illustrated with examples of random walks (in earlier posts) and other examples in this post. All the properties of Markov chains (in this case time-homogeneous Markov chains) are derived from the transition probability matrix. One of the most urgent tasks is to develop a way to calculation the transition probabilities. Recall that the elements of the transition probability matrix $\mathbf{P}$ are the one-step transition probabilities $P_{ij}$, which gives the probability of going from state $i$ into state $j$. The natural next step is to calculate the $n$-step transition probabilities $P^n_{ij}$, which is the probability that the process will in state $j$ in the $n$th period given the process is initially in state $i$. The next post is a beginning look at transition probabilities. The post that follows the next post is on Chapman-Kolmogorov equations, a systematic way of calculating transition probabilities using matrix multiplication.

$\text{ }$

$\text{ }$

$\text{ }$

$\copyright$ 2017 – Dan Ma