Assignment 2

Assignment 2 Solutions

1. Suppose a mosquito makes movements between the forehead, the left cheek, and the right cheek of an individual, which we designate as states 1, 2, 3, according to the following rules. If at some time the mosquito is sitting on the forehead, then it will definitely move to the left cheek at the next time ; if it is sitting on the left cheek, it will stay there or move to the right cheek with probability each; and if it is sitting on the right cheek, it will stay there or move to the forehead with probability each. Then the sequence of locations of the mosquito forms a three-state Markov chain.

Find its one-step and two-step transition probability matrices.

Find the equivalence classes of states of the above Markov chain.

Find the period for each of the states of this Markov chain.

Answer

Let the states be ordered as forehead, left cheek, and right cheek.

The one-step transition probability matrix is

To get the two-step matrix, multiply by itself:

All three states communicate with one another:

1. in one step,
2. in one step,
3. in one step.

So every state can reach every other state, and the whole chain has a single equivalence class:

For the period, it is enough to check one state because the chain is irreducible. For state , there is a return in 3 steps via

and also a return in 4 steps via

Thus the set of possible return times contains both and , so the period is

Hence each state has period , and the chain is aperiodic.

2. A particular machine is either in working order or broken on any particular day. If it is in working order on someday, it remains so the next day with probability 0.7, while if it is broken on someday, it stays broken the next day with probability 0.2. If it is in working order on Monday, what is the probability that it is in working order on Thursday?

Answer

Let denote working order and denote broken. The transition matrix is

From Monday to Thursday there are three transitions: Monday Tuesday Wednesday Thursday. So we need the entry of .

First,

Then

Therefore, the probability that the machine is in working order on Thursday, given that it was in working order on Monday, is

3. A paper (having two sides and ) is hanging in a room. A flea is initially sitted on a particular side of the paper. Every minute it moves from its current location/side to another side of the paper at random. If the flea started flying from side , find the probability that after four moves, it would return to side .

Answer

Since the paper has only two sides, “move to another side” means the flea must switch sides at every step. Starting from side , the path is forced:

So after four moves, the flea is certainly back on side . Therefore,

4. Consider a time-homogeneous discrete-time Markov chain with transition probability matrix and states where:

Find the equivalence classes of states of the above Markov chain. Is it an irreducible Markov chain?

Find the period for each of the states of this Markov chain. Is it an aperiodic Markov chain?

Answer

The communicating structure is easy to read from the matrix.

State is absorbing, because . So it forms its own equivalence class:

State is also absorbing, so it is another singleton class:

States and communicate with each other, because and , and neither of them can reach , , or . Hence they form the class

State can move to , , or itself, but no other state can reach . So it is also a singleton class:

Therefore, the equivalence classes are

Since there is more than one communicating class, the chain is not irreducible.

For the periods:

1. State has , so it returns in one step. Hence its period is .
2. State has , so its period is also .
3. State has a self-loop with probability , so it returns in one step. Thus its period is .
4. State also has a self-loop with probability , so its period is .
5. State has , so it returns in one step. Thus its period is .

So every state has period , and the chain is aperiodic.

5. Consider a time-homogeneous discrete-time Markov chain with transition probability matrix and states where:

Find the equivalence classes of states of the above Markov chain.

Find the period for each of the states of this Markov chain. Is it an aperiodic Markov chain?

Answer

From the matrix, states and communicate with each other:

Neither nor can reach state , and state cannot be reached back from or once the chain leaves it. So is its own communicating class.

States and communicate with each other and do not connect to the first three states, so they form another class.

Therefore the equivalence classes are

The periods are all :

1. State has , so it can return in one step.
2. State has , so it can return in one step.
3. State has , so it can return in one step.
4. State has , so it can return in one step.
5. State has , so it can return in one step.

Hence each state has period , so the chain is aperiodic.