Monthly Archives: January 2018

Practice Problem Set 3 – Chapman-Kolmogorov Equations

Posted on January 6, 2018 | 1 comment

This post presents more exercises on basic calculation of Markov chains transition probabilities. This follows the first batch of basic calculation problems. Discussion of Chapman-Kolmogorov equations is found here.

Most of the exercises here involves raising the transition probability matrix to a power. A matrix calculator will be useful (here is an online matrix calculator).

$\text{ }$

Practice Problem 3-A
Four balls labeled 1, 2, 3 and 4 are in two urns, A and B. At each step, a number is chosen at random from 1, 2, 3 and 4. The ball labeled by the randomly chosen number is taken from the urn that contains it and placed in the other urn. The process goes on indefinitely. Initially all 4 balls are in Urn B.

Determine the transition probability matrix that can be used to track the number of balls in urn A.
Determine the probability that after 4 steps, Urn A will have at least 2 balls.
Determine the probability that after 5 steps, Urn A will have at least 2 balls.

$\text{ }$

Practice Problem 3-B
A manager randomly assigns 5 tasks to 4 workers.

Determine the probability that all workers will be busy.
Determine the mean number of workers who will be busy.

$\text{ }$

Practice Problem 3-C
Suppose that an urn initially contain 4 balls, some green and some red. At each step of the experiment (consider a step as a time period), a pair of balls is randomly selected from the urn. If both balls in the selected pair are of the same color, they are put back into the urn. If the two selected balls are of opposite colors, then the red ball is put back into the urn and the green ball is removed and a red ball in put into the urn with probability 0.08 or the green ball is put back into the urn with probability 0.92.

Initially there are 3 green balls and 1 red ball in the urn.

What is the probability that after 5 time periods there are two red balls in the urn?
After 5 time periods, given that there are lat least 3 red balls in the urn, what is the probability that all balls in the urn are red?

$\text{ }$

Practice Problem 3-D
There are three urns labeled A, B and C. Each urn contains 8 letters. Urn A contains 4 A’s, 2 B’s and 2 C’s. Urn B contains 2 A’s, 4 B’s and 2 C’s. Urn C contains 2 A’s, 2 B’s and 4 C’s. At the beginning of the process, a letter is selected at random urn A. The chosen letter is noted and then returned to urn A. At each subsequent step, a letter is chosen at random from urn whose label is identical to the previous chosen letter (e.g. if the previous chosen letter is B, then use urn B). Then the chosen letter is noted and is put back into the urn.

Determine the probability that the urn in the fifth step is urn A.
Given that the urn in the fifth step is not urn A, determine the probability that urn C is used.

$\text{ }$

Practice Problem 3-E
On any given day, the weather condition in a city is either sunny, cloudy (with no rain) or rainy. The weather condition on a given day is identical to that of the previous day with probability 0.5. The weather condition on a given day is equally likely to be one of the other two weather conditions if it is different from the previous day.

Determine the transition probability matrix $\mathbf{P}$ that can be used to track the weather conditions at each day in this city.
Suppose that it is sunny today in this city. Determine the probability it will not be rainy in this city two days from now.
By observing $\mathbf{P}$ , $\mathbf{P}^2$ , $\mathbf{P}^3 \cdots$ , what is the probability that it will not be rainy in this city as more and more days have passed?

$\text{ }$

Practice Problem 3-F
A fair coin is flipped repeatedly until a run of 3 consecutive heads appear. Determine the probability 3 consecutive heads have not yet appeared after 7 tosses.

$\text{ }$

Practice Problem 3-G
A maze has eight areas as shown below.

When a mouse is placed in this maze, suppose that the mouse 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$ .

Determine the transition probability matrix $\mathbf{P}$ that can be used to track the location of the mouse after making each move, i.e. the area the mouse is in after each move.
The mouse is initially placed in area 1. Determine the probability that the mouse is in areas 6, 7 or 8 after 4 moves.
Observe the patterns of the matrices $\mathbf{P}$ , $\mathbf{P}^2$ , $\mathbf{P}^4$ , $\mathbf{P}^8$ , $\mathbf{P}^{16}$ , $\mathbf{P}^{32}$ and $\mathbf{P}^{64}$ . Conclude the probabilities of the location of the mouse after making many moves. Express the probabilities in 4 decimal places.
In the long run, what is the probability that the mouse is in areas 6, 7 or 8?

$\text{ }$

Practice Problem 3-H
Suppose that urn A and urn B contain a total of 4 balls, which are labeled 1, 2, 3 and 4. At each step, a number is randomly selected from the integers 1, 2, 3 and 4. The ball labeled by the selected integer is taken from the urn containing it. An urn is randomly selected. The chosen ball is then placed in the chosen urn.

Initially urn A is empty. Determine the probability that urn A is not empty after 5 steps.

$\text{ }$

Practice Problem 3-I
This is to further examine the chain in Problem 3-A. Take the transition probability matrix $\mathbf{P}$ from Problem 3-A. Use a matrix calculator to raise $\mathbf{P}$ to various powers.

Observe the patterns in the matrices $\mathbf{P}$ , $\mathbf{P}^2$ , $\mathbf{P}^3$ , $\mathbf{P}^4$ , $\mathbf{P}^5 \cdots$ . Note the periodic behavior. For example, $P_{ii}^k$ is 0 when the power $k$ is odd and is not zero when $k$ is even. In general, the entries alternate between 0 and non-zero. For example, if $P_{ij}^k$ is zero, then $P_{ij}^{k+1}$ is non-zero.
Observe the patterns in the matrices $\mathbf{P}^{10}$ , $\mathbf{P}^{20}$ , $\mathbf{P}^{30}$ , $\mathbf{P}^{40}$ , $\mathbf{P}^{50} \cdots$ . Note that there appears to be a long run behavior. Each row becomes identical as the power increases.
Observe the patterns in the matrices $\mathbf{P}^{11}$ , $\mathbf{P}^{21}$ , $\mathbf{P}^{31}$ , $\mathbf{P}^{41}$ , $\mathbf{P}^{51} \cdots$ . Note that there appears to be a long run behavior. Each row becomes identical as the power increases.

See the comments below concerning the chain discussed in this problem.

$\text{ }$

Practice Problem 3-J
This is to further examine the chain in Problem 3-H. Take the transition probability matrix $\mathbf{P}$ from Problem 3-H. Use a matrix calculator to raise $\mathbf{P}$ to various powers.

Observe the patterns in the matrices $\mathbf{P}$ , $\mathbf{P}^2$ , $\mathbf{P}^3$ , $\mathbf{P}^4$ , $\mathbf{P}^5 \cdots$ . Note that the matrix $\mathbf{P}^4$ is the first matrix in which all entries are positive.
Observe the patterns in the matrices $\mathbf{P}$ , $\mathbf{P}^2$ , $\mathbf{P}^4$ , $\mathbf{P}^8$ , $\mathbf{P}^{16}$ , $\mathbf{P}^{32}$ and $\mathbf{P}^{64}$ . Note that the long run behavior of the Markov chain exhibited in $\mathbf{P}^{64}$ . Regardless of the initial state, the process settles on the states according to a fixed probability distribution. For example, the process will be in state 0 about 6.25% of the time, in state 1 about 25% of the time, etc.

Comments on Problem 3-I and Problem 3-J

For the transition probability matrix $\mathbf{P}$ in 3-H and 3-J, all entries in $\mathbf{P}^4$ are positive whereas $\mathbf{P}^3$ still has some zero entries.

$\mathbf{P}^{4} = \bordermatrix{ & 0 & 1 & 2 & 3 & 4 \cr 0 & 85/512 & 13/32 & 21/64 & 3/32 & 3/512 \cr 1 & 13/128 & 169/512 & 3/8 & 87/512 & 3/128 \cr 2 & 7/128 & 1/4 & 25/64 & 1/4 & 7/128 \cr 3 & 3/128 & 87/512 & 3/8 & 169/512 & 13/128 \cr 4 & 3/512 & 3/32 & 21/64 & 13/32 & 85/512 \cr } \qquad$

This means that in this chain, it is possible (i.e. with positive probability) to transition from any state to any state in 4 steps. We also observe that as the power $k$ increases, $\mathbf{P}^k$ settles on a pattern, which is the long run distribution of the Markov chain. The following is the matrix raised to 64.

$\mathbf{P}^{64} = \bordermatrix{ & 0 & 1 & 2 & 3 & 4 \cr 0 & 0.0625 & 0.2500 & 0.3750 & 0.2500 & 0.0625 \cr 1 & 0.0625 & 0.2500 & 0.3750 & 0.2500 & 0.0625 \cr 2 & 0.0625 & 0.2500 & 0.3750 & 0.2500 & 0.0625 \cr 3 & 0.0625 & 0.2500 & 0.3750 & 0.2500 & 0.0625 \cr 4 & 0.0625 & 0.2500 & 0.3750 & 0.2500 & 0.0625 \cr } \qquad$

This means that regardless of the initial state, the future states can be predicted according to these probabilities, i.e. the process will be in state 0 about 6.25% of the time, in state 1 about 25% of the time, etc.

In general, if a transition probability matrix is such that all entries in $\mathbf{P}^k$ are positive for some power $k$ , then the Markov chain is said to be a regular Markov chain. One property of a regular Markov chain is that the future states can be predicted according to a long run distribution, as Problem 3-I demonstrates.

For the chain in Problem 3-A (Problem 3-I), observe that it is possible to go from any state to any state. In other words, for any states $i$ and $j$ , $P_{ij}^k$ is positive for some integer $k$ . Unlike the chain in Problem 3-H, there is no long run behavior since the transition probability $P_{ij}^k$ is alternately zero and positive. In general, any chain that satisfies the condition that it is possible to transition from any state to any state is called an ergodic Markov chain.

A chain is a regular Markov chain if there is a fixed integer $k$ such that it is possible to go from any state to any state in $k$ steps. Clearly a regular chain is an ergodic chain. The chain in Problem 3-A is an example of an ergodic chain that is not regular.

The chain in Problem 3-A is an example of an Ehrenfest chain, which is a ball-urn model for describing the exchange of gas molecules between two containers. Based on what we observe, the model in Problem 3-A is an ergodic chain but not a regular chain. The chain in Problem 3-H is an example of a modified Ehrenfest chain. As a result of the modification, it is a regular Markov chain.

$\text{ }$

Answers

Practice Problem 3-A

$\mathbf{P} = \bordermatrix{ & 0 & 1 & 2 & 3 & 4 \cr 0 & 0 & 1 & 0 & 0 & 0 \cr 1 & 0.25 & 0 & 0.75 & 0 & 0 \cr 2 & 0 & 0.5 & 0 & 0.5 & 0 \cr 3 & 0 & 0 & 0.75 & 0 & 0.25 \cr 4 & 0 & 0 & 0 & 1 & 0 \cr } \qquad$
0.84375
0.46875

$\text{ }$

Practice Problem 3-B

15/64=0.234375
781/256=3.0508

$\text{ }$

Practice Problem 3-C

0.165215802
0.041081877

$\text{ }$

Practice Problem 3-D

171/512=0.333984375
0.5

$\text{ }$

Practice Problem 3-E

$\mathbf{P} = \bordermatrix{ & S & C & R \cr S & 0.5 & 0.25 & 0.25 \cr C & 0.25 & 0.5 & 0.25 \cr R & 0.25 & 0.25 & 0.5 \cr } \qquad$
11/16=0.6875
0.6667

$\text{ }$

Practice Problem 3-F

81/128=0.6328125

$\text{ }$

Practice Problem 3-G

$\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$
29/108=0.2685
Long run probabilities can be extracted from .
Long run probability being in areas 6, 7 and 8 = 0.3333

$\text{ }$

Practice Problem 3-H

1-137/1024=0.8662

$\text{ }$

Daniel Ma mathematics

Dan Ma math

$\copyright$ 2018 – Dan Ma

1 Comment

Posted in Stochastic Processes

Tagged Chapman-Kolmogorov Equations, Markov Chains

Practice Problem Set 2 – Chapman-Kolmogorov Equations

Posted on January 2, 2018 | 3 comments

This post presents exercises on basic calculation of Markov chains transition probabilities. Some of the problems are to reinforce this post. Most of the problems involve, one way or the other, Chapman-Kolmogorov equations. Discussion of Chapman-Kolmogorov equations is found here.

The practice problems in this post requires matrix multiplication. A matrix calculator may be useful (here is an online matrix calculator).

$\text{ }$

Practice Problem 2-A
A Markov chain $X_0,X_1,X_2,\cdots$ is described by the following transition probability matrix.

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

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)$

$\text{ }$

Practice Problem 2-B
This problem uses the Markov chain in Problem 2-A. Assume that initially, the process is in state 0 about 30% of the time, in state 1 about 30% of the time and in state 2 about 40% of the time. 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)$

$\text{ }$

Practice Problem 2-C
This problem uses the Markov chain in Problem 2-A. Determine the following conditional probabilities.

$P(X_2=2 \lvert X_0=1)$
$P(X_3=1 \lvert X_0=1)$
$P(X_4=1 \lvert X_1=0)$

$\text{ }$

Practice Problem 2-D
This problem uses the Markov chain in Problem 2-A. Assume that initially, the process is in state 0 about 30% of the time, in state 1 about 30% of the time and in state 2 about 40% of the time. Determine $P(X_3=2)$ .

$\text{ }$

Practice Problem 2-E
Suppose that a Markov chain $X_0,X_1,X_2,\cdots$ is described by the following transition probability matrix.

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

Initially the process is in state 0. Find the probability that the process is in state 0 after 3 steps.

$\text{ }$

Practice Problem 2-F
A Markov chain cycles through states 0, 1 and 2 according to the following transition probability matrix.

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

The process starts in state 0. Calculate the probability $P(X_0=0, X_3=2,X_5=1,X_6=1)$ .

$\text{ }$

Practice Problem 2-G
A Markov chain cycles through states 0, 1, 2 and 3 according to the following transition probability matrix.

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

State 3 is an absorbing state, i.e. once the process reaches state 3, it never leaves state 3.

The process starts in state 0. Determine the probability that after 4 transitions, the process has not reached state 3.

$\text{ }$

Practice Problem 2-H
A Markov chain cycles through states 0, 1, 2, 3, 4 and 5 according to the following transition probability matrix.

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

Both states 0 and state 5 are absorbing states, meaning that the process stays there once it reaches these states.

Suppose that the process starts in state 2. Compute the probability that after $k$ moves, the process has not reached state 0 or state 5 where $k$ equals 2, 3, 4, 5 and 6.

$\text{ }$

Practice Problem 2-I
A Markov chain cycles through states 0, 1, 2 and 3 according to the following transition probability matrix.

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

The process starts in state 0. Determine the probability that after 3 moves the process will be in state 1 or state 2.

$\text{ }$

Practice Problem 2-J
A Markov chain cycles through states 0, 1, 2, 3, 4, 5 and 6 according to the following transition probability matrix.

$\displaystyle \mathbf{P} = \bordermatrix{ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \cr 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \cr \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr 1 & 0 & \frac{1}{6} & \frac{5}{6} & 0 & 0 & 0 & 0 \cr \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr 2 & 0 & 0 & \frac{2}{6} & \frac{4}{6} & 0 & 0 & 0 \cr \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr 3 & 0 & 0 & 0 & \frac{3}{6} & \frac{3}{6} & 0 & 0 \cr \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr 4 & 0 & 0 & 0 & 0 & \frac{4}{6} & \frac{2}{6} & 0 \cr \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr 5 & 0 & 0 & 0 & 0 & 0 & \frac{5}{6} & \frac{1}{6} \cr \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \cr 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \cr } \qquad$

The process starts in state 0. After the process has taken 7 steps, determine the probability that the process is in state $k$ where $k$ equals 1, 2, 3, 4, 5, and 6.

$\text{ }$

Answers

Practice Problem 2-A

0.16
0.16
0.126

$\text{ }$

Practice Problem 2-B

0.048
0.0464
0.0378

$\text{ }$

Practice Problem 2-C

0.18
0.289
0.4

$\text{ }$

Practice Problem 2-D

0.3076

$\text{ }$

Practice Problem 2-E

0.406

$\text{ }$

Practice Problem 2-F

0.05292

$\text{ }$

Practice Problem 2-G

0.4416

$\text{ }$

Practice Problem 2-H

0.75
0.625
0.5
0.40625
0.328125

$\text{ }$

Practice Problem 2-I

0.332

$\text{ }$

Practice Problem 2-J

$\displaystyle P_{01}^7=\frac{1}{46656}$

$\text{ }$

$\displaystyle P_{02}^7=\frac{315}{46656}$

$\text{ }$

$\displaystyle P_{03}^7=\frac{6020}{46656}$

$\text{ }$

$\displaystyle P_{04}^7=\frac{21000}{46656}$

$\text{ }$

$\displaystyle P_{05}^7=\frac{16800}{46656}$

$\text{ }$

$\displaystyle P_{06}^7=\frac{2520}{46656}$

$\text{ }$

Daniel Ma mathematics

Dan Ma math

3 Comments

Posted in Stochastic Processes

Tagged Chapman-Kolmogorov Equations, Markov Chains

Monthly Archives: January 2018

Practice Problem Set 3 – Chapman-Kolmogorov Equations

Practice Problem Set 2 – Chapman-Kolmogorov Equations

Archives

Categories

Recent Posts

Tags