Practice Problem Set 4 – Absorbing Markov Chains

The practice problems in this post involving absorbing Markov chains. Such a Markov chain contains at least one absorbing state such that all non-absorbing states will eventually transition into an absorbing state (these are called transient states). Two problems are of interest. One is that the mean time spent in transient states (i.e. mean time to reach an absorbing state) given the initial state is a transient state. The other is the probability of absorption given that the process begins in a transient state. The primary tool for solving these problems is the notion of fundamental matrix, discussed here and here.

A matrix calculator will be useful for the exercises presented here, especially one that can find the inverse of a matrix (here is an online matrix calculator).

\text{ }

Practice Problem 4-A
Consider the Markov chain governed by the following transition probability matrix.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3\cr        0 & 1 & 0 & 0  & 0  \cr        1 & 0.3 & 0.3 & 0.2 & 0.2  \cr        2 & 0.2 & 0.3 & 0.3 & 0.2  \cr        3 & 0 & 0 & 0 & 1   \cr           } \qquad
  • Determine the mean time to absorption, i.e. the mean time to reach an absorbing state, given that the process begins in state 1.
  • Determine the probability that the process ends in state 0 given that the initial state is 1.
  • Determine the probability that the process ends in state 3 given that the initial state is 2.

\text{ }

Practice Problem 4-B
A Markov chain is described by the following transition probability matrix.

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

Determine the expected number of steps to reach state 3 given that the process starts in state 0.

\text{ }

Practice Problem 4-C
Consider the Markov chain with the following transition probability matrix.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 & 4 \cr        0 & 1 & 0 & 0  & 0 & 0 \cr        1 & 0.1 & 0.2 & 0.7 & 0 & 0 \cr        2 & 0.1 & 0 & 0.1 & 0.8 & 0 \cr        3 & 0.05 & 0 & 0 & 0.05  & 0.9 \cr        4 & 0 & 0 & 0 & 0  & 1 \cr   } \qquad
  • Given that the process begins in state 1, find the expected time to reach an absorbing state.
  • Given that the process begins in state 1, find the probability that the process reaches state 4.

\text{ }

Practice Problem 4-D
Two urns (A and B) contain a total of 6 balls. At each step, an urn is selected at random and a ball is chosen from the selected and put into the other urn. The game stops when one of the urns is empty. Player A wins if urn A has all the balls. Likewise player B wins if urn B has all the balls.

  • Determine the mean number of steps required in playing this game, assuming that initially urn A has 2 balls and urn B has 4 balls.
  • Assuming that initially urn A has 2 balls and urn B has 4 balls, determine the probability that Player A wins the game.

\text{ }

Practice Problem 4-E
A manager assigns tasks one at a time at random to five workers. Determine, on average, the number of tasks the manager must assign until none of the workers is idle.

\text{ }

Practice Problem 4-F
Consider the game of repeatedly tossing a fair coin until the pattern HTH appears and the game of repeatedly tossing the coin until the pattern HHH appears. Which game will take fewer steps on average?
Give an explanation of the difference.

\text{ }

Practice Problem 4-G
An urn initially contains 8 blue balls and 4 red balls. One ball is selected at random one at a time from the urn. If the selected ball is not red, the ball is put back into the urn. If the selected ball is red, it is removed from the urn. The process continues until all red balls are removed. Determine the expected number of selections in order to have all red balls removed.

\text{ }

Practice Problem 4-H
An urn initially contains 8 blue balls and 4 red balls. One ball is selected at random one at a time from the urn. If the selected ball is not red, the ball is put back into the urn. If the selected ball is red, it is removed from the urn and then a blue ball is put into the urn. The process continues until all red balls are removed. Determine the expected number of selections in order to have all red balls removed. Compare the expected value with the expected value in Problem 4-G. Give an explanation for the difference.

\text{ }

Practice Problem 4-I
An urn contains 5 balls, some red and some blue. One ball is selected at random one at a time from the urn. Each selected ball is replaced by a ball of the opposite color. The process continues until all balls in the urn are of the same color.

  • Determine the probability that the process ends with the urn containing only red balls given that initially the urn has 3 red balls and 2 blue balls.
  • Determine the expected number of selections in order for the urn to consist of balls of the same color given that initially there are 4 blue balls and 1 red ball in the urn.

\text{ }

Practice Problem 4-J
A game is played as follows. A fair coin is tossed repeatedly until either three consecutive heads appear or three consecutive tails appear. Assuming that the first toss results in a tail, determine the probability that the game ends with three consecutive heads.

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Answers

Practice Problem 4-A

  • \displaystyle \frac{90}{43}=2.1
  • \text{ }

  • \displaystyle \frac{25}{43}=0.58
  • \text{ }

  • \displaystyle \frac{20}{43}=0.47

\text{ }

Practice Problem 4-B

  • 6

\text{ }

Practice Problem 4-C

  • \displaystyle \frac{2213}{684}=3.235
  • \text{ }

  • \displaystyle \frac{126}{171}=0.7368

\text{ }

Practice Problem 4-D

  • 8
  • \text{ }

  • \displaystyle \frac{1}{3}

\text{ }

Practice Problem 4-E

  • \displaystyle \frac{137}{12}=11.4167

\text{ }

Practice Problem 4-F

  • mean number of steps to HTH = 10
  • mean number of steps to HHH = 14

\text{ }

Practice Problem 4-G

  • \displaystyle \frac{62}{3}=20.67

\text{ }

Practice Problem 4-H

  • 25

\text{ }

Practice Problem 4-I

  • \displaystyle \frac{17}{32}=0.53125
  • \text{ }

  • 15

\text{ }

Practice Problem 4-J

  • \displaystyle \frac{3}{7}=0.4286

Dan Ma math

Daniel Ma mathematics

Dan Ma Markov chains

Daniel Ma Markov chains

\copyright 2018 – Dan Ma

Advertisements

3 responses to “Practice Problem Set 4 – Absorbing Markov Chains

  1. Pingback: Practice Problem Set 5 – Absorbing Markov Chains – Additional Problems | Topics in Probability

  2. Pingback: First step analysis and fundamental matrix | Topics in Probability

  3. Pingback: Absorbing Markov chains | Topics in Probability

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s