# 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!

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