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:
- a white ball is picked and no color changes
- a white ball is picked and color changes (black balls + 1)
If there are 1 black ball in the urn. There are these outcomes:
-
a black ball is picked and color changes
Thus, \(P_{10}=\mathbb P(\text{pick black ball and changes color})\). Since picking and changing color are independent, \(P_{10}=\mathbb P(\text{pick black})\mathbb P(\text{change color})\). Which is \(\frac{1}{4}\times a\).
-
Similarly, using the steps for the black ball above, the probability of picking the white ball and changing color is just \(\frac{3}{4}\times a\).
-
Picking any colored ball and not change color contributes to the same transition.
- For picking a black ball and not change color, the probability is
... - Picking a white ball and not change color, the probability is
...
The sum of the two above adds up to \(1-a\).
- For picking a black ball and not change color, the probability is
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
- State machine is irreducible if and only if all states are recurrent
- 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
- All states in a communicating class has the same period
- 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.
- 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.