Practice Problem Set 5 – Absorbing Markov Chains – Additional Problems

This post is the second installment of practice problems on absorbing Markov chains (here is the first problem set).

The practice problems are to reinforce the concepts of fundamental matrix, discussed here and here.

The last 3 problems in this set are to reinforce the problem of the last step before absorption (discussed 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 5-A
A game is played as follows. An urn always has at least one ball. At each step, a fair die is rolled. If 4, 5 or 6 is rolled, a ball is added to the urn. If 2 or 3 is rolled, no ball is added to the urn. If 1 is rolled, then the player loses the game. The player wins the game when the urn has 5 balls.

  • If initially the urn has 1 ball, determine the number of steps that are expected to be made in playing the game.
  • If initially the urn has 1 ball, determine the the probability that the player wins the game.

\text{ }

Practice Problem 5-B
Two urns (A and B) contain a total of 6 balls. At each step, an urn is selected by rolling a fair die. If 5 or 6 is rolled, then urn B is chosen. If 1, 2, 3 or 4 is rolled, then urn A is chosen. A ball is then taken from the chosen urn 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 loses the game.

\text{ }

Practice Problem 5-C
Two urns (A and B) contain a total of 6 balls. At each step, an urn is selected according to their weights. More specifically, if urn A has k balls and urn B has 6-k balls, then urn A is chosen with probability k/6 and urn B is chosen with probability 1-k/6. A ball is then taken from the chosen urn and put into the other urn. 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 loses the game.

\text{ }

Practice Problem 5-D
A manager assigns tasks one at a time at random to ten workers. Determine, on average, the number of tasks the manager must assign until six of the workers are occupied with tasks.

\text{ }

Practice Problem 5-E
Five fair coins are tossed. The coins randomly fall heads or tails. At each subsequent step, all the coins that fall tails are picked up and tossed again until all coins show heads. Determine the expected number of tosses.

\text{ }

Practice Problem 5-F
Consider the following diagram of a maze where area 1 has an electric shock and area 7 is a food source.

A maze with food and shock

When a mouse is placed in this maze, it moves to the adjacent areas at random. In other words, if there are k exits, it moves into one of these areas with probability 1/k. However, when the mouse is in area 7 or area 1, it stays there and does not leave.

If the mouse is placed in area 5 initially,

  • determine the expected number of steps before the mouse is in area 1 or area 7,
  • determine the probability that the mouse will find food.

\text{ }

Practice Problem 5-G
Consider the following diagram of a maze with two food sources (area 4 and area 6).

A maze with two food sources

When a mouse is placed in this maze, it moves to the adjacent areas at random. In other words, if there are k exits, it moves into one of these areas with probability 1/k. However, when the mouse is an area with food, it stays there and does not leave.

When the mouse is placed in area 1 initially,

  • determine the expected number of steps before the mouse reaches a food source,
  • determine the probability that the mouse will find food in area 4.

\text{ }

Practice Problem 5-H
A Markov chain is associated with the following transition probability matrix.

    \mathbf{P} =       \bordermatrix{ & 0 & 1 & 2 & 3 & 4 \cr        0 & 1 & 0 & 0  & 0  & 0 \cr        1 & 0.3 & 0.2 & 0.2 & 0.2  & 0.1 \cr        2 & 0.2 & 0.2 & 0.2 & 0.1  & 0.3 \cr        3 & 0.2 & 0.1 & 0.1 & 0.2 & 0.4  \cr        4 & 0 & 0 & 0 & 0 & 1  \cr   } \qquad
  • Compute the fundamental matrix of this absorbing Markov chain.
  • Regardless of the initial state, eventually the process will enter state 0 or state 4. Determine the probability of the process entering state 0 or state 4 from state i where i=1,2,3 given that the process starts in state 3.

\text{ }

Practice Problem 5-I
For the Markov chain in Problem 5-E, determine the probability that the last toss involves only one coin.

\text{ }

Practice Problem 5-J
For the Markov chain in Problem 5-G, determine the probability that the mouse enters a food area from area i where i=1,3,5 given that the mouse is placed in area 1 at the beginning.

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Answers

Practice Problem 5-A

  • \displaystyle \frac{525}{128}=4.1
  • \text{ }

  • \displaystyle \frac{81}{256}=0.32

\text{ }

Practice Problem 5-B

  • 6

\text{ }

Practice Problem 5-C

  • \displaystyle 36
  • \text{ }

  • \displaystyle \frac{7}{13}=0.54

\text{ }

Practice Problem 5-D

  • \displaystyle \frac{2131}{252}=8.5

\text{ }

Practice Problem 5-E

  • \displaystyle \frac{2470}{651}=3.8

\text{ }

Practice Problem 5-F

  • 8
  • \displaystyle \frac{2}{3}

\text{ }

Practice Problem 5-G

  • \displaystyle \frac{28}{10}=2.8
  • \text{ }

  • \displaystyle \frac{2.5}{10}=0.25

\text{ }

Practice Problem 5-H

  • given initial state is 3, the probability of entering from an absorbing state from state 1 is \displaystyle \frac{0.8}{9}
  • given initial state is 3, the probability of entering from an absorbing state from state 2 is \displaystyle \frac{1}{9}
  • given initial state is 3, the probability of entering from an absorbing state from state 1 is \displaystyle \frac{7.2}{9}=0.8

\text{ }

Practice Problem 5-I

  • Given initial state is 5, the probability of entering state 0 from state 1 is \displaystyle \frac{157}{217}=0.0.7235

\text{ }

Practice Problem 5-J

  • Given initial state is 1, the probability of entering an absorbing state from state 1 is \displaystyle \frac{6.5}{10}=0.65
  • Given initial state is 1, the probability of entering an absorbing state from state 3 is \displaystyle \frac{1.5}{10}=0.15
  • Given initial state is 1, the probability of entering an absorbing state from state 5 is \displaystyle \frac{2}{10}=0.2

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 5 – Absorbing Markov Chains – Additional Problems

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

  2. Pingback: Absorbing Markov chains | Topics in Probability

  3. Pingback: Last step in an absorbing Markov chain | 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