Consider the sampled-time approximation to the M/M/1 queue in Figure 6.5.

(a) Give the steady-state probabilities for this chain (no explanations or calculations required - just the answer).

In (b)-(g) do not use reversibility and do not use Burke's theorem. Let Xn be the state of the system at time nδ and let Dn be a rv taking on the value 1 if a departure occurs between nδ and (n + 1)δ, and the value 0 if no departure occurs. Assume that the system is in steady state at time nδ.

(b) Find Pr{Xn = i, Dn = j} for i ≥ 0, j = 0, 1.

(c) Find Pr{Dn = 1}.

(d) Find Pr{Xn = i | Dn = 1} for i ≥ 0.

(e) Find Pr{Xn+1 = i | Dn = 1} and show that Xn+1 is statistically independent of Dn. Hint: Use (d); also show that Pr{Xn+1 = i} = Pr{Xn+1 = i | Dn = 1} for all i ≥ 0 is sufficient to show independence.

(f) Find Pr{Xn+1 = i, Dn+1 = j | Dn} and show that the pair of variables (Xn+1, Dn+1) is statistically independent of Dn.

(g) For each k > 1, find Pr{Xn+k = i, Dn+k = j | Dn+k-1, Dn+k-2, ... , Dn} and show that the pair (Xn+k, Dn+k) is statistically independent of (Dn+k-1, Dn+k-2, ... , Dn). Hint: Use induction on k; as a substep, find Pr{Xn+k = i | Dn+k-1 = 1, Dn+k-2, ... , Dn} and show that Xn+k is independent of Dn+k-1, Dn+k-2, ... , Dn.

(h) What do your results mean relative to Burke's theorem.

Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.