Suppose that the times between successive arrivals of customers at a single-server station are independent random variables having a common distribution F. Suppose that when a customer arrives, he or she either immediately enters service if the server is free or else joins the end of the waiting line if the server is busy with another customer. When the server completes work on a customer, that customer leaves the system and the next waiting customer, if there are any, enters service. Let Xn denote the number of customers in the system immediately before the nth arrival, and let Yn denote the number of customers that remain in the system when the nth customer departs. The successive service times of customers are independent random variables (which are also independent of the interarrival times) having a common distribution G.
(a) If F is the exponential distribution with rate λ, which, if any, of the processes {Xn}, {Yn} is a Markov chain?
(b) If G is the exponential distribution with rate μ, which, if any, of the processes {Xn}, {Yn} is a Markov chain?
(c) Give the transition probabilities of any Markov chains in parts (a) and (b).