Markov Chain / Probability

SYS 6005 – Homework Assignment 5
Due: 13 Nov 2021 @ 11:59 PM
Reading
• Chapter 7.
• All “starred” Problems (and Solutions) at the end of Chapter 7.
Problems to Turn In:
Instructions: Solve each of the following exercises. Give quantitative answers where required, and always
explain your reasoning.
Problem 1: (25 points)
Consider the following Markov chain. For all the parts of the problem, the process is in State 3 immediately
before the first transition.
(a) (7 points) Find the variance for J, the number of transitions up to and including the transition on
which the process leaves state 3 for the last time.
(b) (10 points) Find ⇡i for i = 1,…, 7, the probability that the process is in state i after 1010 (a large
number) transitions.
(c) (8 points) Given that the process never enters state 4, find the ⇡i’s as defined in part(b).
Problem 2: (20 points)
The Central Grounds Garage has installed a card-operated gate, which, unfortunately, is vulnerable to
absent-minded faculties. In particular, each day, a car crashes the gate with probability p, in which case
a new gate must be installed. Also, a gate that has survived for m days must be replaced as a matter of
periodic maintenance. What is the steady-state expected frequency of gate replacements?
Problem 3: (25 points)
Sam’s doctor told her to walk every morning. Her house has two doors to go out, one is at the front, and
another one is at the back. When she leaves her house for the walk or returns from the walk (independent
of one another), she is equally likely to take any of the doors. Assume that these choices are independent
across days.
1
For her walk, Sam bought five pairs of running shoes, and each pair was placed in one of the two doors at
random. When she leaves for the walk, if there is at least one pair of shoes at the door that she leaves, she
wears a pair for her walk (equally like to pick any). If there are no shoes at the door from which she leaves
to go walking, she goes walking barefooted (i.e., she is too lazy to go to the other door). When she returns,
she takes off her shoe (if she wore a shoe for that walk) immediately after the walk at whichever door she
happens to be at and enters the house. We are interested in determining the long-term proportion of time
she walks barefoot.
(a) (13 points) We consider a Markov chain states {0, 1, 2, 3, 4, 5}, where state i indicates that there
are i pair of shoes available at the front door in that morning before Sam leaves the house for walking. Find
the transition probabilities associated with the Markov chain.
(b) (12 points) Find out the steady-state probability that Sam runs barefoot.
Problem 4: (30 points)
Assume that a fair coin is tossed repeatedly, with the tosses being independent. We want to determine the
expected number of tosses necessary to first observe a head directly followed by a tail. To do so, we define
a Markov chain with states S, H, T, HT, where S is a starting state, H indicates a head on the current toss,
T indicates a tail on the current toss (without heads on the previous toss), and HT indicates heads followed
by tails over the last two tosses. This Markov chain is illustrated below:
We can find the expected number of tosses necessary to first observe a head directly followed by tails by
solving a mean first passage time problem for this Markov chain.
(a) (7 points) What is the expected number of tosses necessary to first observe a head directly followed
by tails?
(b) (7 points) Assuming we have just observed a head followed by a tail, what is the expected number
of additional tosses until we again observe a head followed directly by a tail?
Next, we want to answer the same questions for the event tails directly followed by tails. Set up a different
Markov chain from which we could calculate the expected number of tosses necessary to first observe tails
directly followed by tails.
(c) (8 points) What is the expected number of tosses necessary to first observe a tail directly followed
by a tail?
(d) (8 points) Assuming we have just observed a tail followed by a tail, what is the expected number of
additional tosses until we again observe a tail followed directly by a tail? Note that the number of additional
tosses could be as little as one if tails were to come up again.
2