ELEC 321

Tutorial 12

Updated 2019-04-09

Suppose we have the Markov chains \(X_n\). The Markov property is \(\mathbb P(X_{n+1}\vert X_n, X_{n+1},\dotsc)=\mathbb P(X_{n+1}\vert X_n)\).

For homogeneous MC, the initial probability distribution is \(p_i(0)=\mathbb P(X_0=i)\), and that \(\sum_i p_i=1\).

Chapman-Kolmogrov Equation

\[\begin{align} p(n)=(\mathbb p_1(n)\dotsc p_s(n))\\ p(n+1)=p(n)p\\ p(n)=p(0)p^n \end{align}\]

Example

There exists 2 white balls and 2 black balls. At each time, one ball is drawn and the color is flipped with probability \(a\), and not flipped with probability 1-\(a\). Ball is placed back into the urn.

Let \(X_n\) be the number of black balls in the urn.

a. Is \(X_n\) a Markov chain?

There are five possible outcomes for \(X_n\): \(X_n\in\{0,1,2,3,4\}\). Let \(X_n=k\), so \(k\) is the number of black balls. Then

\[X_{n+1}=\begin{cases} k,&\text{if white or black ball is taken but no color change}\\ k+1 & \text{if white ball is taken and color changes}\\ k-1 & \text{if black ball is taken and color changes} \end{cases}\]

Since we have shown that \(X_{n+1}\) only depends on the last value, \(k=X_n\). Then \(X_n\) is a Markov chain.

b. Find the transition matrix

Let the rows be the number of black balls the transition is ‘from’ and the column be the number of black balls the transition is going ‘to’.

If there are 0 black balls to begin with. Then there are two cases:

If there are 1 black ball in the urn. There are these outcomes:

Using the same arguments for the other states, we come to the final matrix:

\[\begin{bmatrix} 1-a &a & 0&0&0\\ \frac a4 & 1-a & \frac{3a}{4} & 0 &0\\ 0 & \frac{a}{2} & 1-a & \frac{a}{2} & 0\\ 0 & 0 & \frac{3a}{4} & 1-a & \frac{a}{4}\\ 0 & 0 & 0 & a & 1-a \end{bmatrix}\]

Classes of State

Accessibility: State \(j\) is accessible from \(i\) if and only if \(\exists n \in \mathbb N, p_{ij}>0\)

Communicating State: States \(i\) and \(j\) communicate if and only if \(i\) is accessible from \(j\) and \(j\) is accessible from \(i\).

Communicating Class: The set of all communicating states.

Irreducible: A state is irreducible if and only if all states in the state space belongs to a single communicating class.

Recurrence: The state \(i\) is recurring if and only if the probability of visiting state \(i\) is 1.

​ To check, consider: \(\sum_{n=1}^\infty p_{ii}(n)=\infty\)

Transient: The state \(i\) is transient if and only if the probability of visiting state \(i\) is less than 1.

​ To check, consider: \(\sum_{n=1}^\infty p_{ii}(n)<\infty\)

Properties

  1. State machine is irreducible if and only if all states are recurrent
  2. All states in a communicating class are either transient or recurring (if one state in a communicating class is transient, all of the states in the same class are)

Example

Given transition matrix

\[P=\begin{bmatrix} 0 & 1 & 0\\ 0.5 & 0 & 0.5\\ 1 & 0 &0 \end{bmatrix}\]

Let’s draw the state diagram.

Since 1 is accessible from 0 and 0 is accessible from 1, then \(1,0\in \mathcal C\). Since 2 is also accessible from any of the states and any state is accessible from 2 given some time, we see that \(2\in\mathcal C\) also.

Thus \(\mathcal C=\{0,1,2\}\).

Example

Given transition matrix

\[P=\begin{bmatrix} 1 & 0 &0\\ 0&0&1\\ 0&1&0 \end{bmatrix}\]

We see that 0 is not communicating with any state but itself, and that 1 and 2 are communicating amongst each other. Thus we have two communicating classes: \(\mathcal C_1=\{0\},\mathcal C_2=\{1,2\}\).

We see that both communicating classes are recurrent.

Example

Given transition matrix

\[P=\begin{bmatrix} 0.5 & 0.5 &0\\ 0&1&0\\ 0.5&0&0.5 \end{bmatrix}\]

We see that none of the states are communicating except for themselves:

\[\mathcal C_1=\{0\},\quad\mathcal C_2=\{1\},\quad\mathcal C_3=\{2\}\]

To check if state 0 is transient, we check \(\sum_{n=1}^\infty p_{00}(n) <\infty\):

\[\begin{align} p_{00}(1)&=\frac{1}{2}\\ p_{00}(2)&=\frac{1}{2}\frac{1}{2}=\frac{1}{4}\\ p_{00}(3)&=\frac{1}{8}\\ \vdots \end{align}\]

If we take the sum, it converges to \(1<\infty\). Therefore state 0 is transient.

Similarity, we could argue that state 2 is also transient.

For state 1, if we end up in state 1, the only outcome after is state 1. Therefore state 1 is recurring. We can check this by taking the summation: \(\sum_{n=1}^{\infty}p_{11}(n)=\sum_{n=1}^\infty(1)=\infty\).

Periodicity of a State

Given a Markov chain, the period \(d_i\) of a state is defined as

\[d_i=\gcd(\{n_i\in\mathbb N,i\in\mathbb N:p_{ii}(n_i)>0\})\]

Properties

  1. All states in a communicating class has the same period
  2. A state is aperiodic if there exists a class, where all states in the class have a period of 1. From property 1, we see that if one state in the class has a period of 1, then all of the other states in the same class also has a period of 1. Thus it will make the class aperiodic.
  3. Regular: a Markov chain is regular if and only if it is irreducible and aperiodic

Example

copy diagram

All states belong to the same communicating class: \(\mathcal C=\{0,1,2,3\}\) and we only need to find the period of one state to determine the period of the entire class.

Observe the period of from state 0 to state 0. We see that \(p_{00}(1)=0,p_{00}(2)=0.5,p_{00}(3)=0,p_{00}(4)=0.75\). Thus the period is \(d_0=\gcd(n=2,n=4)=2\).

Example

Given transition matrix

\[P=\begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{bmatrix}\]

We see that this is not regular because its one and only communicating class is periodic.

Long-Run Behavior

This only applies to regular Markov chains.

Doesn’t matter what the starting state is, after a long time, the probability approaches to a certain probability - the steady state probability.

Suppose we start the chain at state \(i\), then \(\mathbb P(X_n=j \vert X_o=i)=\pi_j>0\)

\(\pi\) can be obtained as a solution of \(\pi=\pi P\)

Example

Given a 2 state MC with the transition matrix

\[P=\begin{bmatrix} 1-a & a\\ b & 1-b \end{bmatrix}\]

We first check that this MC is regular, and indeed it is.

To compute the steady state probability, \(\pi=\pi P\):

\[\begin{bmatrix}\pi_1 &\pi_2\end{bmatrix}=\begin{bmatrix}\pi_1 &\pi_2\end{bmatrix}\times\begin{bmatrix}1-a & a \\ b & 1-b\end{bmatrix}\\\]

We obtain the equations and solve for \(\pi_1,\pi_2\). Alas, we get \(\pi_1=\frac{b}{a+b}\) and \(\pi_2=\frac{a}{a+b}\).

Suppose that \(p(0)=\begin{bmatrix}0.5 &0.5\end{bmatrix}\) and \(a=0.3, b=0.8\). Compute the probability at \(n=2\).

Because \(p(n)=p(0)p^n\) we have \(p(2)=\begin{bmatrix}0.5 & 0.5\end{bmatrix}\begin{bmatrix}0.7 & 0.2\\ 0.8 & 0.2\end{bmatrix}^2\).

Multiplying them out using preferred methods, we see that \(p(2)=\begin{bmatrix}0.725 & 0.275\end{bmatrix}\).

Example

Given a buffer

At \(t=0\), the buffer contains 3 packets. Assume no more packet arrives, the packets in the buffer is transmitted. Transmission is successful with probability \(p\).

Let \(Y_n\) denote the number of packets in the buffer.

a. Is \(Y_n\) a MC?

There are four outcomes: \(Y_n\in\{0,1,2,3\}\)

Let \(Y_n=k\), we see that \(Y_{n+1}\in\{k, k-1\}\), thus \(Y_{n+1}\) only depends on \(k\) and therefore \(Y_n\) is a Markov chain.

The transition matrix is

\[P=\begin{bmatrix} 1 & 0 & 0 & 0\\ p & 1-p & 0 & 0\\ 0 & p & 1-p & 0\\ 0 & 0 & p & 1-p \end{bmatrix}\]

It is not regular because all states don’t belong to a single communicating class.