M/G/1 Queue as a Markov Renewal Process: One step transition probabilities

104 Views Asked by At

Seeking help on this interesting problem! any input is welcome and appreciated

Background

From many texts, we know that for an M/G/1 queue, denote $I_n$ as the number of customers in the system immediately after the nth service completion and $r_n = T_n-T_{n-1}$ where $T_n$ is the nth service completion time. This duo ${(I_n,r_n)}$ forms a Markov renewal sequence.

Then, the transition probability matrix $Q$ with entries $Q_{ii'}(t) = P(I_n = i', r_n\leq t | I_{n-1} = i)$ like in the following matrix $$ Q(t)=\left|\begin{array}{cccccc} B_{0}(t) & B_{1}(t) & B_{2}(t) & B_{3}(t) & B_{4}(t) & \cdots \\ A_{0}(t) & A_{1}(t) & A_{2}(t) & A_{3}(t) & A_{4}(t) & \cdots \\ 0 & A_{0}(t) & A_{1}(t) & A_{2}(t) & A_{3}(t) & \cdots \\ 0 & 0 & A_{0}(t) & A_{1}(t) & A_{2}(t) & \cdots \\ \cdot & \cdot & \cdot & \cdot & \cdot & \\ \cdot & \cdot & \cdot & \cdot & \cdot & \end{array}\right| $$

where $H(u)$ is the service time CDF, $A_{\nu}(x)=\int_{0}^{x} e^{-\lambda \mathrm{s}} \frac{(\lambda u)^{\nu}}{\nu !} d H(u), \text { for } \nu \geq 0, x \geq 0,$ $B_{\nu}(x)=\int_{0}^{x} \lambda e^{-\lambda \mu} A_{\nu}(x-u) d u$.

Observation on matrix Q(t)

It is not stochastic since the rows do not add up to 1 when $t$ is finite. When $t$ is infinite, this matrix is the same as the (stochastic) transition matrix of the imbedded DTMC of M/G/1 queue.

Question My question is that, suppose we know the interdeparture time $r_n = T_n - T_{n-1},$ what exactly is the probability $P(I_n=i'|I_{n-1}=i,r_n)$? Intuitively, suppose we know how long two departures are apart? What's the distribution of the system size at the next departure?

Any input is highly appreciated! Thank you all!