From Arrivals During Service to a Transition Matrix
In an M/G/1 queue, arrivals follow a Poisson process, but service times may have any distribution. At departure epochs, the queue length evolves by counting how many arrivals occurred during the service just completed. The service time is random, so the arrival count is generally a mixture of Poisson distributions rather than a Poisson random variable with a fixed parameter. Finding that mixture gives every entry of the embedded chain’s transition matrix.
Assume the arrival process is Poisson with rate \(\lambda>0\). Service times \(B_1,B_2,\ldots\) are independent and identically distributed, strictly positive and finite almost surely, and independent of the arrival process. The queue has one server, unlimited waiting space, and serves customers whenever any are present. Write \(X_n\) for the number of customers in the system immediately after the \(n\)th departure. Its state space is \(S=\{0,1,2,\ldots\}\). The process is defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\); \(\mathcal{F}_n\) denotes the history of the queue through the \(n\)th departure.
When \(X_n=i\ge1\), one of those customers begins service immediately after the departure. If \(A_{n+1}\) arrivals occur during that service, then \(X_{n+1}=i-1+A_{n+1}\). When \(X_n=0\), the server waits for the next arrival, who begins service; the number remaining at the next departure is then \(A_{n+1}\), the arrivals during that service. Thus, in both cases,
The idle time when the system is empty is not part of the service interval. In particular, the customer whose arrival ends that idle time is in service, not counted in \(A_{n+1}\).
Why the Mixture Gives a Probability Distribution
The formula conditions on the service duration: first fix \(B=t\), compute the Poisson probability of \(k\) arrivals in an interval of length \(t\), and then average over the distribution of \(B\). Because \(B\) is finite almost surely, this conditional Poisson distribution is defined almost surely.
Proposition (mixed Poisson probabilities). The values \(a_k\) are nonnegative and sum to \(1\).
Proof. The integrand \(e^{-\lambda B}(\lambda B)^k/k!\) is nonnegative, so \(a_k\ge0\). Since all terms are nonnegative, the sum and expectation can be interchanged. For each finite value \(B=t\), the Poisson probabilities sum to \(1\). Therefore $$ \sum_{k=0}^{\infty}a_k =\mathbb{E}\!\left[\sum_{k=0}^{\infty}e^{-\lambda B}\frac{(\lambda B)^k}{k!}\right] =\mathbb{E}[1]=1. $$ Thus \((a_k)\) is a probability distribution. \(\square\)
Proof. Given the history through departure \(n\), the next service duration has the service-time distribution and is independent of that history. Arrivals during that service have the mixed Poisson probabilities \(a_k\): the Poisson process has independent increments, and the service time is independent of arrivals. The recursion shows that if \(X_n=0\), the next state is \(A_{n+1}\), giving \(p_{0j}=a_j\). If \(X_n=i\ge1\), then \(X_{n+1}=i-1+A_{n+1}\). This equals \(j\) exactly when \(A_{n+1}=j-i+1\), which is possible only when \(j\ge i-1\). This proves the displayed entries and shows the conditional distribution of \(X_{n+1}\) given the history depends on that history only through \(X_n\), the Markov property. For row \(i=0\), the sum is \(\sum_{j\ge0}a_j=1\). For row \(i\ge1\), the nonzero entries are \(a_0,a_1,\ldots\), in order from column \(i-1\) onward, so their sum is also \(1\). \(\square\)
The matrix is infinite because the queue can contain any nonnegative number of customers. Its structure is simple: row \(0\) is the arrival-count distribution, row \(1\) is the same distribution, and each later row is shifted one column farther to the right. The transition matrix uses row-stochastic convention: its entries are probabilities of moving from the current state \(i\) to the next state \(j\).
Worked Calculations
Worked Example: Exponential Service
Suppose the service time is exponential with rate \(\mu=2\), and arrivals have rate \(\lambda=1\). The density of \(B\) is \(2e^{-2t}\) for \(t>0\). For each \(k\ge0\), conditioning on \(B\) gives $$ a_k=\int_0^\infty 2e^{-2t}e^{-t}\frac{t^k}{k!}\,dt =\frac{2}{k!}\int_0^\infty t^k e^{-3t}\,dt. $$
For \(c>0\), integration by parts gives \(\int_0^\infty e^{-ct}\,dt=1/c\), and, for \(k\ge1\), \(\int_0^\infty t^k e^{-ct}\,dt=(k/c)\int_0^\infty t^{k-1}e^{-ct}\,dt\). Repeating this identity yields \(k!/c^{k+1}\). Substituting \(c=3\) therefore gives $$ a_k=\frac{2}{3^{k+1}}=\frac23\left(\frac13\right)^k. $$
In particular, substituting \(k=0,1,2,3\) gives \(a_0=\tfrac23\), \(a_1=\tfrac29\), \(a_2=\tfrac2{27}\), and \(a_3=\tfrac2{81}\). The row sum is checked using the full geometric series: $$ \sum_{k=0}^{\infty}a_k =\frac23\sum_{k=0}^{\infty}\left(\frac13\right)^k =\frac23\cdot\frac{1}{1-\frac13}=1. $$
Using the transition formula, the first four rows, with columns \(0,1,2,3,\ldots\), are $$ P= \begin{bmatrix} \tfrac23&\tfrac29&\tfrac2{27}&\tfrac2{81}&\cdots\\ \tfrac23&\tfrac29&\tfrac2{27}&\tfrac2{81}&\cdots\\ 0&\tfrac23&\tfrac29&\tfrac2{27}&\cdots\\ 0&0&\tfrac23&\tfrac29&\cdots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{bmatrix}. $$ Each displayed row continues with the remaining terms of the same geometric sequence, so each full row sums to \(1\). For example, from state \(2\), the next state is \(1\) if no arrivals occur during service, with probability \(a_0=\tfrac23\); it is \(2\) if one arrival occurs, with probability \(a_1=\tfrac29\).
Check: State \(2\) evolves to \(1+A\). The probabilities shown for next states \(1\) and \(2\) are therefore \(a_0=\tfrac23\) and \(a_1=\tfrac29\), as required by the recursion.
Worked Example: Deterministic Service
Suppose each service lasts exactly one time unit and the arrival rate is \(\lambda=1\). Then \(B=1\) with probability \(1\), so the mixed Poisson formula gives, for every \(k\ge0\), $$ a_k=e^{-1}\frac{1^k}{k!}=\frac{e^{-1}}{k!}. $$
Substituting \(k=0,1,2,3\) gives \(a_0=e^{-1}\), \(a_1=e^{-1}\), \(a_2=e^{-1}/2\), and \(a_3=e^{-1}/6\). The full row sum is $$ \sum_{k=0}^{\infty}a_k=e^{-1}\sum_{k=0}^{\infty}\frac{1}{k!}=e^{-1}e=1. $$
The first rows, again with columns \(0,1,2,3,\ldots\), are $$ P= \begin{bmatrix} e^{-1}&e^{-1}&\tfrac{e^{-1}}2&\tfrac{e^{-1}}6&\cdots\\ e^{-1}&e^{-1}&\tfrac{e^{-1}}2&\tfrac{e^{-1}}6&\cdots\\ 0&e^{-1}&e^{-1}&\tfrac{e^{-1}}2&\cdots\\ 0&0&e^{-1}&e^{-1}&\cdots\\ \vdots&\vdots&\vdots&\vdots&\ddots \end{bmatrix}. $$ The omitted entries continue according to \(a_k=e^{-1}/k!\); the zero entries in row \(i\ge1\) are exactly the columns below \(i-1\). Consequently every full row sums to \(1\). From state \(2\), for instance, next state \(1\) requires zero arrivals during the one-unit service and has probability \(e^{-1}\); next state \(2\) requires one arrival and also has probability \(e^{-1}\).
Check: The row for state \(2\) begins with a zero in column \(0\), because the two customers present before service leave at least one customer after the departure. Its next entry is \(a_0=e^{-1}\), corresponding to next state \(1\).
Worked Example: A Two-Point Service-Time Distribution
Let \(\lambda=1\), and suppose \(B=1\) or \(B=2\), each with probability \(\tfrac12\). Applying the mixed Poisson formula separately at the two possible service durations gives $$ a_k=\frac12\frac{e^{-1}}{k!} +\frac12 e^{-2}\frac{2^k}{k!}. $$
For \(k=0\), substitution gives \(a_0=\tfrac12(e^{-1}+e^{-2})\). For \(k=1\), it gives \(a_1=\tfrac12(e^{-1}+2e^{-2})\). For \(k=2\), the second Poisson term is \(e^{-2}2^2/2!=2e^{-2}\), so \(a_2=\tfrac12(e^{-1}/2+2e^{-2})\). Each \(a_k\) is nonnegative, and the full sum is $$ \sum_{k=0}^{\infty}a_k =\frac12\sum_{k=0}^{\infty}\frac{e^{-1}}{k!} +\frac12\sum_{k=0}^{\infty}e^{-2}\frac{2^k}{k!} =\frac12(1)+\frac12(1)=1. $$
For example, from state \(2\), the transition probabilities to states \(1,2,3\) are respectively \(a_0,a_1,a_2\), since the recursion gives \(X_{n+1}=1+A_{n+1}\). Substituting the values just calculated gives \(p_{2,1}=\tfrac12(e^{-1}+e^{-2})\), \(p_{2,2}=\tfrac12(e^{-1}+2e^{-2})\), and \(p_{2,3}=\tfrac12(e^{-1}/2+2e^{-2})\).
Check: The entire row for state \(2\) consists of zero in column \(0\), followed by \(a_0,a_1,a_2,\ldots\). Its sum is \(\sum_{k\ge0}a_k=1\), as verified above.
A Common Mistake: Using the Mean Service Time
A random service time does not generally produce a Poisson arrival count with parameter \(\lambda\mathbb{E}[B]\). For the two-point example, \(\mathbb{E}[B]=\tfrac12(1)+\tfrac12(2)=\tfrac32\). Treating arrivals during service as Poisson with mean \(\tfrac32\) would give probability \(e^{-3/2}\) of zero arrivals. The correct probability is \(a_0=\tfrac12(e^{-1}+e^{-2})\). These are not equal: their difference is positive because $$ \frac{e^{-1}+e^{-2}}{2}-e^{-3/2} =\frac12\left(e^{-1/2}-e^{-1}\right)^2>0. $$
The error comes from averaging the service duration before calculating the conditional probability. The zero-arrival probability is the expectation \(\mathbb{E}[e^{-\lambda B}]\), not \(e^{-\lambda\mathbb{E}[B]}\). The mixed Poisson formula keeps the service-time variability in every arrival-count probability. This matters when constructing the transition matrix: an incorrect \(a_k\) changes the entire corresponding row of the embedded chain.
To compute a departure-epoch transition matrix in practice, first identify the number of arrivals during a single service, then find its mixed Poisson probabilities, and finally place those probabilities in rows according to the recursion. Always check that the \(a_k\) sum to \(1\); the row shifts then guarantee that every transition-matrix row also sums to \(1\). This computation provides the transition structure, without making any claim here about whether the chain has a stationary distribution or converges to one.
Check Your Understanding
Use the mixed Poisson probabilities and the departure-epoch recursion to answer these questions.
- If the service time is a fixed value \(b>0\), write \(a_k\) and verify that the probabilities sum to \(1\).
- For a general service-time distribution, what is the probability of moving from state \(i\ge1\) to state \(i-1\)? Explain which arrival count this transition represents.
- For exponential service with rate \(\mu\), derive \(a_k=\frac{\mu\lambda^k}{(\lambda+\mu)^{k+1}}\) from the integral formula.
- In the two-point example, explain why the probability of no arrivals is not obtained by simply substituting the mean service time into a Poisson formula.
- Explain why row \(i\ge1\) has zero entries in columns \(j<i-1\), and why its nonzero entries sum to \(1\).