Mathematicians: please help!


I am still stuck with a problem with the M/G/1 queue: not quite the same as my original problem (discussed here) as I understand that now – but the next stage really – involving some manipulation of Laplace transforms.

I won’t post all the details here, because you can read them here instead and, if this sort of thing matters to you (and why wouldn’t it?) pick up the bounty I am offering on the maths Stack Exchange.

Puzzle about an M/G/1 queue


I am deeply puzzled by a question about the behaviour of an M/G/1 queue – i.e., a queue with a Markovian distribution of arrival times, a General distribution of service times and 1 server. I have asked about this on the Math Stackexchange (and there’s now a bounty on the question if you’d like to answer it there – but as I am getting nowhere with it, I thought I’d ask it here too.

(This is related to getting a more rigorous presentation on thrashing into my PhD thesis.)

Considering an M/G/1 queue with Poisson arrivals of rate λ – this comes from Cox and Miller’s (1965) “The Theory of Stochastic Processes” (pp 240 – 241) and also Cox and Isham’s 1986 paper “The Virtual Waiting-Time and Related Processes“.

My question is what is the difference between (using the authors’ notation) p_0 and p(0,t)? The context is explained below…

In the 1965 book (the 1986 paper presents the differentials of the same equations), X(t) is the “virtual waiting time” of a process and the book writes of “a discrete probability p_0(t) that X(t)=0, i.e., that the system is empty, and a density p(x,t) for X(t)>0“.

The system consumes virtual waiting time in unit time, i.e., if X(t)\leq\Delta t and there are no arrivals in time \Delta t then X(t + \Delta t) = 0.

The distribution function of X(t) is then given by:
F(x,t)=p_0(t)+\int_{0}^{\infty}p(z,t)dz

They then state:
p(x, t+ \Delta t) = p(x + \Delta t, t)(1 - \lambda \Delta t) +p_0(t)b(x)\lambda\Delta t + \int_{0}^{x}p(x - y, t)b(y)dy\lambda\Delta t + o(\Delta t)

I get all this – the first term on the RHS is a run-down of X(t)>0 with no arrivals, the second is adding b(x) of service time when the system is empty at t and the third, convolution-like, term is adding b(y) of service time from an arrival when it’s not empty at t. (The fourth accounts for their being more than one arrival in \Delta t but it tends to zero much faster than \Delta t so drops out as \Delta t approaches the limit.)

And … and this is where I have the problems …

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

The first term of the RHS seems clear – the probability that the system is empty at t multiplied by the probability there will be no arrivals in \Delta t, but the second is not clear to me at all.

I assume this term accounts for the probability of the system “emptying” during \Delta t but I don’t see how that works, is anyone able to explain?

In other words, how does p(0,t)\Delta t(1 - \lambda\Delta t) represent this draining? Presumably (1 - \lambda\Delta t) again represents the possibility of zero arrivals in \Delta t, so how does p(0, t)\Delta t represent the X(t) \leq \Delta t situation?

If we take the equilibrium situation where p_0(t) = p_0 and p(x, t) = p(x) then, if we differentiate and as p^{\prime}_0 = 0, we get p_0 = \lambda p(0) – so, again, what does p(0) represent?

Poisson distribution puzzle


I asked this on math.stackexchange but have yet to get an answer, so will try here too…

In their monograph “Queues“, Cox and Smith state (paraphrased – this is p5):

In interval (t,t+Δt) the probability of no arrivals in a completely random process is 1−αΔt+o(Δt), for one arrival αΔt+o(Δt) and for more than one arrival o(Δt) where α is the mean rate of arrival.

I cannot follow this… here is my thinking – we take N to be the probability of no arrivals, W to be the probability of one arrival, Z to be the probability of more than one arrival, and A to be the probability of any arrivals.

So 1=N+W+Z=N+A

By my understanding of Cox and Smith:

1=1−αΔt+o(Δt)+αΔt+o(Δt)+o(Δt) =1+3o(Δt) which is surely nonsense.

So, what have I got wrong here?