Q1 (Lin. Alg.) In this problem, we model a queue using a Markov
chain. (The queue might represent, for example, customers waiting
to buy something at a shop, a web server attempting to respond to
page requests, or students waiting during oce hours.) Suppose that
a certain queue may contain 0, 1, or 2 items. It is not possible
for it to contain 3 or more items. At each time step, one of two
things can happen: (i) with probability 1/3, one item is removed
from the queue, if there is an item to remove (and otherwise
nothing happens), or (ii) with probability 2/3, one item is added
to the queue, if there is enough space (i.e. if there are not
already 2 items in the queue) (and otherwise nothing happens).
Answer the following questions: (a) Formulate a nite Markov chain
that describes this system. (4 points) (b) If the queue starts o
empty, after 4 time steps what is the probability that it is again
empty? (3 points) (c) In the long term, what is the average rate at
which items are removed from the queue? (3 points)