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