0
$\begingroup$

I'm a little bit confused about the terms of arrival and service processes in queuing systems. I know about Kendall's notation but it is often explained slightly different in literature.

As far as I know, M stands for Markov property which means the following:

1) At any time the system is in one of a number of states.

2) Changes of state in the future are not influenced by history.

3) Only a single state change occurs in a time interval.

On Wikipedia the M at the arrival process is described with "Poisson process (or random) arrival process (i.e., exponential inter-arrival times)." This is related to the Poisson distribution, right?!

My professor defined the Poisson process like this. Sounds similar to the above three points.

For the M at the service time distribution on Wikipedia the descriotion is "Exponential service time.".

Sometimes M means Poisson distribution, sometimes it means Exponential distribution. Isn't that confusing?

So my question is: How do these terms match, what specifically are the differences between

  • Markov property
  • Poisson process / distribution
  • Exponential distribution

and why do different authors mix these terms?

Thanks in advance!

$\endgroup$

1 Answer 1

0
$\begingroup$

The exponential distribution

Let's start with the exponential distribution, and why we might want to label exponential random variables as "Markovian."

The critical feature of an exponential random variable $X \sim \mathsf{Exp}(\lambda)$ is that it is memoryless, which has the following interpretation: Suppose you arrive at the cash register and one customer is currently being served. Moreover, suppose that the customer service time is exponentially distributed at a rate of one customer every two minutes. On average, how long will you have to wait before being served?

If you arrived at the exact moment when their service began, then the expected waiting time (i.e., the mean of the random variable) would be two minutes. But since we don't know when the customer began service, this would seem to be a tricky question. Presumably, that would have an effect on how long you will have to wait. However, because the exponential distribution is memoryless, it turns out to have no effect at all. In other words, your expected waiting time, given that the first customer is in the middle of service, is still two minutes.

Formally, let $t > 0$. Then $$ P(X < s + t \mid X \geq s) = P(X < t). $$ This justifies calling the exponential service time of a queue Markovian. When you arrives in the system, You don't need to worry about all prior service time information. You simply need to observe the present state of the system, and this will you them everything you need to know about your expected service time.

The Poisson process

Now we can move on to the Poisson arrivals, and why calling this process "Markovian" follows from the exact reasoning from before.

Note: A Poisson process is a different object from a Poisson distribution. It's important to keep the two separate, though we shall see how they are related.

There are a couple of important ways to characterize a Poisson process, but here I will discuss the more intuitive approach for the context of queuing. Suppose we want to track the number of events which occur from a certain phenomenon. The example you should have in mind is tracking the number of arrivals into our queuing system. We will denote the number of events by time $t \geq 0$ as $N(t)$. If the events are randomly distributed, then this is an example of a counting process, a type of stochastic process. Since the events are random, you can't know the exact value of $N(t)$ for a given $t$. That is, $N(t)$ itself is a random variable for each $t$.

A Poisson process is a special kind of counting process $\newcommand{\set}[1]{\{#1\}} \set{N(t) : t \geq 0}$ in which the times between consecutive recorded events are independent and identically distributed exponential random variables. In other words, let $S_n$ denote the time at which the $n$th customer arrives into the system. Then $S_n$ can be decomposed into a sum of independent exponential random variables $X_j \sim \mathsf{Exp}(\lambda)$ like so: $$ S_n = \sum_{j=1}^{n} X_j. $$ Thus the first arrival $S_1$ is simply $X_1$, but now the second arrival $S_2$, which occurs after $S_1$, is separated by another exponentially distributed waiting time: $S_2 = S_1 + X_2$, or equivalently $S_2 = X_1 + X_2$.

Because the Poisson process is constructed from these independent exponential random variables, we can describe the process as memoryless. How? Suppose we observe that the $(n-1)$th customer has already arrived in the system. How long, on average, will it take before the $n$th customer will arrive? Well, because the $n$th interarrival time is exponentially distributed, the interarrival itself is memoryless. Regardless of when we started observing the system, we know that the expected time for the $n$th customer to arrive after we began our observation is still $\frac{1}{\lambda}$.

The bottom line: If you are the cashier's manager, and arrive to see three customers in line, you already know everything needed to estimate when the fourth customer will arrive. This is why we call the arrival process Markovian.


The way a Poisson distribution sneaks into the mechanics of the Poisson process is in how $N(t)$ (remember this is a random variable!) is distributed. In fact, $N(t) \sim \mathsf{Poisson}(\lambda t)$.

$\endgroup$
5
  • $\begingroup$ Thanks for your answer which gave me a little understanding! But nevertheless confusing... $\endgroup$
    – lukasl1991
    May 12, 2018 at 17:02
  • $\begingroup$ @lukasl1991, can you point to anything specifically that you would like me to clarify? I'd be happy to. $\endgroup$ May 14, 2018 at 15:01
  • 1
    $\begingroup$ Is the equation P(X<s+t∣X≥s)=P(X>t) really correct? If you take the one from en.wikipedia.org/wiki/Memorylessness#Discrete_memorylessness and substitute m by s and n by t, the right hand sides of both equations are equal, but the left hand sides are not?! $\endgroup$
    – lukasl1991
    May 18, 2018 at 9:42
  • $\begingroup$ Excellent catch! No, the $>$ should be a $<$, which is very important here. I edited it above. $\endgroup$ May 25, 2018 at 15:36
  • $\begingroup$ Thanks for that detailed explanation! $\endgroup$
    – lukasl1991
    May 30, 2018 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.