M/G/1 queue and Pollaczek-Khintchine formula

Question

My question is about the interpretation of symbols used in a description of the derivation of the Pollaczek-Khintchine formula, as outlined on pp 240 - 242 of Cox and Miller's "The theory of stochastic processes"

In the book they write of the "Takács process" but I think a more modern description would be of a M/G/1 queue - arrivals are exponentially distributed with Poisson parameter $\lambda$ while service times have a general distribution and there is one server (eg this is a typical model of a request to a hard disk with one head, or so I read).

The waiting time (for the customer at the end of the queue to complete service) is $X(t)$. When $X(t)=0$ the system is empty and when an arrival occurs $X(t)$ jumps up by the amount of time taken to serve that customer, which is distributed randomly according to $b(x)$, otherwise $X(t)$ is reduced in unit time i.e. by $\Delta t$ in $\Delta t$.

So the distribution formula for $X(t)$ is:

$$F(x,t)=p_o(t) +\int_{0}^{x}p(z,t)dz$$

Where $p_o(t)$ is "the discrete probability ... that $X(t)=0$ i.e., that the system is empty, and a density $p(x,t)$ for $X(t)>0$".

Where I struggle is with this:

$$p_0(t + \Delta t) = p_0(t)(1-\lambda\Delta t) + p(0,t)\Delta t(1 - \lambda\Delta t) +o(t)$$

The first term on the RHS seems clear enough - the probability that the system is empty at $t$ multiplied by the probability there will be no arrivals in $\Delta t$. But what does the second term mean? And what is $p(0,t)\Delta t$: this term presumably represents the probability of "draining" the system - ie that $X(t) \leq \Delta t$ -and is then multiplied by the probability of there being no arrivals in $\Delta t$ - but how is that "drainable" probability represented by $p(0,t)\Delta t$?

Naïvely I thought $p(0, t)$ was the same as $p_0(t)$ but if we differentiate the equilibrium condition, i.e., where $p(x, t) = p(x)$ and $P_0(t) = p_0$ we can see that $p(0) = \lambda p_0$ (as $p^{\prime}_0(t) = 0$ at equilibrium).

This has been driving me mad for days, so I'd love it if someone can put me out of my misery!

Answer 1

What you are struggling with is part of the derivation of the Takacs integrodifferential equation.

The derivation of the expression you are trying to understand starts with:

$$P_w(t+\Delta t) = (1-\lambda \Delta t)P_{w+\Delta t}(t) + \dots$$

where the $w$ represents a generic waiting time. This expression says that (part of) the probability that the waiting time is $\leq w$ at time $t + \Delta t$ (denoted by $P_w(t + \Delta t)$) is equal to the probability that the waiting time be $\leq w + \Delta t$ at time $t$ (denoted by $P_{w+\Delta t}(t)$) and no arrivals during $\Delta t$. (There's another term for the case where arrivals do occur, but that's not part of the expression you're dealing with - it's part of the $\dots$.) I use a capital $P$ as we are dealing with cumulative distribution functions, which are typically denoted by capital letters.

Now we need to tackle the expression $P_{w+\Delta t}(t)$, because it's in terms of $w + \Delta t$, but we want everything in terms of just $w$. For $w=0$, $P$ has a jump of magnitude $P_0(t)$, and for $w > 0$, $P$ is continuous. We can construct a Taylor expansion:

$$P_{w+\Delta t}(t) = P_w(t) + {\partial P_w(t) \over \partial w}\Delta t + o(\Delta t)$$

Due to the jump at $w=0$, $P_w(t)$ is not continuous at $w=0$, however, it is continuous to the right. We can define the derivative at $0$ to be the right-hand derivative, which does exist at $w=0$ (it's equal to $\lim_{w \downarrow 0}(P_w(t)-P_0(t))/w$.)

Notationally, we define:

$$ {\partial P_w(t) \over \partial w} = p(w,t)$$

and substituting results in:

$$P_w(t+\Delta t) = (1-\lambda \Delta t)[P_w(t) + p(w,t)\Delta t]\dots$$

In your case, you're dealing with equations where $w$ has been set equal to $0$. Substituting gives us your original equation.

So, $p(0,t)$ is the right hand derivative of the cumulative distribution of waiting time at time $t$, evaluated at waiting time $= 0$.