M/G/1 queue as a Markov renewal process: one-step transition probabilities

Question

Seeking help on this interesting problem! any input is welcome and appreciated. I've posted on other places and decided to seek any possible help here!

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!

Answer 1

Case 1: leaving behind at least one job

Suppose first that when job $n - 1$ departs, it leaves behind at least one other job, meaning $I_{n - 1} = i \geq 1$. Then job $n$ is already in the system when job $n - 1$ departs. So when job $n$ departs, it leaves behind the number jobs $I_{n - 1}$, that job $n - 1$ left, minus itself, plus the number of jobs $A$ that arrived during its service time. That is, $$ I_n = I_{n - 1} - 1 + A. $$ We have assumed $I_{n - 1} = i \geq 1$, which means that job $n$'s service time is $r_n$. And because the Poisson arrival process is independent of job $n$'s service time, we have $A \sim \mathrm{Poisson}(\lambda r_n)$, where $\lambda$ is the arrival rate. From this, one can compute the desired $$\begin{aligned} \mathbf{P}(I_n = i' \mid I_{n - 1} = i, r_n) &= \mathbf{P}\bigl(\mathrm{Poisson}(\lambda r_n) = i' - i + 1\bigr) \\ &= \frac{e^{-\lambda r_n}(\lambda r_n)^{i' - i + 1}}{(i' - i + 1)!} \mathbf{1}(i' \geq i - 1). \end{aligned}$$ for $i \geq 1$.

Case 2: leaving behind an empty system

(Let me start by saying that this case is way easier without conditioning on $r_n$, or when conditioning on the service time of job $n$ but not the time between job $n - 1$'s departure and job $n$'s arrival. If you do that instead, you basically get the same as above, except without subtracting $1$, because $I_{n - 1}$ does not count job $n$.)

The case of $I_{n - 1} = i = 0$ is trickier, because now job $n$ arrives strictly after job $n - 1$ departs. This means job $n$ arrives to an empty system, so $$ I_n = A, $$ where $A$ is again the number of arrivals during job $n$'s service time. However, job $n$'s service time is no longer simply $r_n$. Instead, letting $S$ be job $n$'s service time and $V \sim \mathrm{Exp}(\lambda)$ be the time between job $n - 1$'s departure and job $n$'s arrival, we have $$ r_n = S + V. $$ Conditional on $S$, we have $(A \mid S) \sim \mathrm{Poisson}(\lambda S)$, because the arrival process is independent of job $n$'s service time. So it remains only to determine the distribution of $S$ conditional on the fact that $S + V = r_n$. Because $V \sim \mathrm{Exp}(\lambda)$ has density $t \mapsto \lambda e^{-\lambda t}$, we have for any (reasonable) function $f$, $$ \mathbf{E}\bigl(f(S) \bigm\vert S + V = r_n\bigr) = \frac{\int_0^{r_n} f(s) \, \lambda e^{-\lambda (r_n - s)} \, \mathrm{d}H(s)}{\int_0^{r_n} \lambda e^{-\lambda (r_n - s)} \, \mathrm{d}H(s)}. $$ The desired probability comes from plugging in $$\begin{aligned} f(s) &= \mathbf{P}\bigl(\mathrm{Poisson}(\lambda s) = i'\bigr) \\ &= \frac{e^{-\lambda s} (\lambda s)^{i'}}{i'!}. \end{aligned}$$ This yields $$\begin{aligned} \mathbf{P}(I_n = i' \mid I_{n-1} = 0, r_n) &= \frac{\int_0^{r_n} \frac{\lambda e^{-\lambda r_n} (\lambda s)^{i'}}{i'!} \, \mathrm{d}H(s)}{\int_0^{r_n} \lambda e^{-\lambda (r_n - s)} \, \mathrm{d}H(s)} \\ &= \frac{\int_0^{r_n} \frac{(\lambda s)^{i'}}{i'!} \, \mathrm{d}H(s)}{\int_0^{r_n} e^{\lambda s} \, \mathrm{d}H(s)} \\ &= \frac{\lambda^{i'} \, \mathbf{E}(S^{i'} \mid S \leq r_n)}{i'! \, \mathbf{E}(e^{\lambda S} \mid S \leq r_n)}. \end{aligned}$$