Monthly Archives: December 2017

Probability problems using Markov chains

Posted on by
Reply

This post highlights certain basic probability problems that are quite easy to do using the concept of Markov chains. Some of these problems are easy to state but may be calculation intensive (if not using Markov chains). But the solutions using Markov chains involve raising a matrix to a power or finding the inverse of a matrix. The concept of Markov chains is a good framework to organize these problems. Interestingly some of these problems are classic problems in probability (tossing coins, rolling dice, occupancy problem, coupon collector problem).

The problems listed here are to highlight the discussion in a companion blog on stochastic processes (links are given below in appropriate places).

Problem 1
A fair coin is tossed repeatedly until the appearance of 4 consecutive heads. Determine the mean number of tosses required.

Problem 2
A fair coin is tossed repeatedly until the appearance of 4 consecutive heads.

  • Find the probability that it takes at most 9 flips to get a run of 4 consecutive heads.
  • Find the probability that it takes at exactly 9 flips to get a run of 4 consecutive heads.

Problem 3
A fair die is rolled until each face has appeared at least once. What is the expected number of rolls to achieve this?

Problem 4
Balls are thrown into 6 cells (one ball at a time) until all 6 cells are occupied. On average, how many balls have to be thrown until all 6 cells are occupied?

Problem 5
Balls are thrown into 6 cells (one ball at a time). After throwing 8 balls into 6 cells, what is the probability that exactly k of the 6 cells are occupied where k=1,2,3,4,5,6?

Problem 6
A maze is divided into 9 areas as shown below.

Area 1 = initial position of the mouse

A mouse is placed in area 1 initially. Suppose that areas 3, 7 and 9 contain food and that the other areas in the maze do not contain food. Further suppose that the mouse moves through the areas in the maze at random. That is, whenever the mouse is in an area that has w exits, the next move is to one of these w areas with probability 1/w.

  • Find the probability that after the 5 moves, the mouse is one area from a food source.
  • Find the probability that after the 7 moves, the mouse has not found food and is in area 6 or area 8 after the 7th move.
  • Find the probability that it takes at most 8 moves for the mouse to find food.
  • Find the probability that it takes exactly 8 moves for the mouse to find food.

Problem 7
Consider the maze that is described in Problem 6. Assuming that the mouse is initially placed in Area 1, what is the expected number of moves in order for the mouse to find food?

Problem 8
Consider the maze that is described in Problem 6. Assuming that the mouse is initially placed in Area 1, what is the probability that the first area of food reached by the mouse is Area 9?

Discussion

Problem 1 and Problem 2 has a natural interpretation as a Markov chain. In this case the chain consists of 5 states – 0, H, HH, HHH, HHHH. As the coin is tossed repeatedly, the chain moves through these 5 states. One characteristic of a Markov chain is that the probability of moving from one state to the next depends the current state (the last state visited) but not on the states prior to the current state, i.e. it only remembers the last state and not the states before the last state.

Before any toss is made, the state is 0. Suppose the first toss is Head. The second toss could be Head (the Markov chain then moves to state HH) or could be Tail (the chain then moves to state 0). Suppose the second toss turns out to be a Tail. Then the next toss could be a Head (the chain then moves to the state H) or could be a Tail (the chain continues to stay at state 0). A good framework is to describe such movements in a matrix called transition probability matrix.

    \mathbf{P} = \bordermatrix{ & 0 & \text{1=H} & \text{2=HH} & \text{3=HHH} & \text{4=HHHH} \cr 0 & 0.5 & 0.5 & 0 & 0 & 0 \cr 1 & 0.5 & 0 & 0.5 & 0 & 0 \cr 2 & 0.5 & 0 & 0 & 0.5 & 0 \cr 3 & 0.5 & 0 & 0 & 0 & 0.5 \cr 4 & 0 & 0 & 0 & 0 & 1 \cr } \qquad

To answer Problem 2, just raise this matrix to the 9th power (see here). Problem 1 is more involved (see Example 2 in this post).

The listed problems are based on discussion in three different posts. Here’s the links.

Problem Link
1 See Example 2 in this link
2 See Example 2 in this Link
3 See Example 3 in this link
4 Problem 4 is identical to Problem 3. The setting of Problem 4 is an occupancy problem. It can also be solved as a coupon collector problem.
5 Problem 5 is the occupancy problem discussed in this link
6 See Example 3 in this Link
7 Follow the method discussed in this link
8 Follow the method discussed in this link

Another advantage of using Markov chains for these problems is that the method scales up quite easily. For example, for the occupancy problem (Problems 3, 4 and 5), if the number of cells is higher than 6, it is quite easy and natural to scale up the transition probability matrix to include additional states. Then proceed with the same method.

There is a learning curve at first. But once the concept of Markov chains is understood, the probability problems described here or other similar problems can be tackled quite easily and routinely. For a basic discussion of Markov chains, see the early posts in this companion blog.

Dan Ma probability

Daniel Ma probability

Dan Ma Math

Daniel Ma mathmeatics

\copyright 2017 – Dan Ma