Exponential Distributions, Part 3 - Queues Just Don't Remember

In Part 1 and Part 2, we have looked at some characteristics of exponential distributions, particularly the Erlang distributions.  In this article we tackle another attribute of an exponential queue.

Exponential Attribute #3 - The Memoryless Property

Or, Always Press the Reset Button When You Arrive

Queues are just line-ups, so how can a queue possess a memory?  
As it turns out, some queues and systems do have a memory, but not all.  It is actually quite intuitive that all queues should have a memory.  We expect that what happened before you got in line should affect what happens after you arrive.  However, queues that are memoryless are not affected by what happened before you arrive.  That behaviour is counter-intuitive, at least at first glance.

What is a "Memoryless" Queue?

A memoryless queue refers to the property that what happened before you arrived in the queue will have no affect on the timing of the next event after you arrive.  Why does this matter?

Let's create a fictional example of waiting for a taxi cab to pass by on a street corner to take you to your next meeting.  You arrive at a random time and taxis are passing that corner at random intervals.  How long will you expect to wait for the next taxi on average?

If some data is collected at that corner over a period of days, let's assume the data shows the taxi intervals follow a normal distribution (bell curve) with an average interval of 5 minutes.  When you arrive on the corner, sometimes you will have just missed a taxi and would expect to wait a full 5 minutes for the next one.  At other times, you might arrive 5 minutes after the last taxi and would expect to wait a very short time for the next one.  On average therefore, you would expect to wait 1/2 of the average interval time, or 2.5 minutes.  Further, if there was a hotdog vendor on that corner who paid more attention to taxis than to his customers, you could ask him how long ago the last taxi passed.  If it was 5 minutes ago, then you would expect to wait only a short time, whereas if the last taxi passed seconds ago, you would expect to wait about 5 minutes.  In other words, the memory of the previous event in the system affects your expected wait time.  That is intuitive.

However, now assume the data instead showed that taxi intervals on that corner follow an Erlang distribution with an average interval of 5 minutes.  How long would you expect to wait for a taxi now?  It turns out the correct answer is 5 minutes -- not half the average interval, but the average interval itself.  Further, it doesn't matter what the hotdog vendor tells you about the last taxi to pass by.  Whether it was 5 seconds ago or 10 minutes ago, the expected average wait time for you will be 5 minutes from when you arrive.  It is like the queue has no memory -- it doesn't matter what happened before you arrived, the expected wait time clock resets itself.  How could this be?  Surely it cannot be true.  It appears counter-intuitive.

The easiest way to demonstrate this is with a non-queue example.  Imagine a factory that manufactures pipe. One machine extrudes pipe continuously and an automated saw immediately cuts the pipe into either 1 meter or 9 meter lengths, depending on the next customer order in the computer system.  Effectively the order of pipe lengths is random, but on average the machine produces 50% short pieces and 50% long pieces each shift.  The pipe continues moving along the assembly line at a constant speed where a robotic arm randomly selects pieces of pipe for quality control testing.  An arm shoots out and knocks the pipe that happens to be passing by at that moment into a bin.  The arm is programmed to randomly activate a certain number of times per shift.

At the end of each shift, what proportion of long and short pieces of pipe would you expect to find in the bin?  Even though that machine produces half short and half long pipes, that will not be the composition in the bin.  Because the long pieces of pipe take 9 times longer to pass the robotic arm, the odds are 9 times greater that a long piece will be selected.  Therefore you would expect 90% of the pipes in the bin to be long ones.

It is the same principle with memoryless queues.  Even though a long interval between taxi cabs is rare, the odds are greater that you will happen to arrive while one of those long intervals is occurring.  That increases the expected wait time, and it turns out to increase it exactly to the mean value.  Even if that last taxi came 8 minutes ago, you can still expect to wait 5 more minutes.  You could just be in one of those rare but long duration intervals.

And that is what it means for a queue to be memoryless.  Whatever happened before you arrived is irrelevant -- the clock resets when you get there.