2We are modelling a single-server queue with finite waiting room, in discrete time. Up to 3 customers can be waiting in the queue at any time. At each step, there is either an arrival event (with probability), a service event (with probability) or nothing (with probability 1, where we assume+1). An arrival event causes the queue length to increase by 1, unless the queue is already full. A service event causes the queue length to decrease by 1, except when the queue is already empty.

We want to understand the effect of having one extra customer in the queue. To study this, we simulate two copies of the queue: one copy starts out empty, and the other copy starts out with one customer. Both copies evolve according to the same sequence of arrival events and service events, and we track the pair (Xn, Yn) measuring both queue lengths. This forms a Markov chain where the states are pairs, with initial state (X0, Y0) = (0,1).

For instance, if two arrival events occur, followed by one step with nothing and then three steps with service events, the sequence of states will be(0,1),(1,2),(2,3),(2,3),(1,2),(0,1),(0,0).

aWhat would you choose as the state space,S, for this chain?

bDraw the transition diagram, including the transition probabilities.

Note: the states are themselves pairs. The transition probabilities are indexed by two pairs, which we can see it as pxy,xyfor (x, y)Sand (x, y)S.

You do not need to write down the transition matrix. If you do, however, clearly indicate how the rows and columns are arranged.

cEventually, the effect of the extra customer will disappear and the two queues will have the same length (either because they both become full, or because they both become empty). We want to know how long this will take, on average. Write down a system of equations that you can use to calculate this average time.

dFor the special case=, solve this system of equations and determine the average time until the queues have the same length.

eWe also want to know the probability that, when the queues first have the same length, it is because they are both empty. Write down a system of equations that you can use to calculate this probability.

fFor the special case=, solve this system of equations and determine this probability.