# M/G/1 queue and Pollaczek-Khintchine formula

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!

## 1 Answer

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$.