14
$\begingroup$

When we consider Queueing theory scenarios where individuals arrive to a serving node and queue up, usually a Poisson process is used to model the arrival times. These scenarios come up in network routing problems. I'd appreciate an intuitive explanation as to why a Poisson process is best suited to model the arrivals.

$\endgroup$

migrated from math.stackexchange.com Nov 23 '11 at 11:56

This question came from our site for people studying math at any level and professionals in related fields.

15
$\begingroup$

The Poisson process involves a "memoryless" waiting time until the arrival of the next customer. Suppose the average time from one customer to the next is $\theta$. A memoryless continuous probability distribution until the next arrival is one in which the probability of waiting an additional minute, or second, or hour, etc., until the next arrival, does not depend on how long you've been waiting since the last one. That you've already waited five minutes since the last arrival does not make it more likely that a customer will arrive in the next minute, than it would be if you'd only waited 10 seconds since the last arrival.

This automatically implies that the waiting time $T$ until the next arrival satisfies $\Pr(T>t) = e^{-t/\theta}$, i.e., it's an exponential distribution.

And that in turn can be shown to imply that the number $X$ of customers arriving during any time interval of length $t$ satisfies $\Pr(X=x) = \dfrac{e^{-t/\theta} (t/\theta)^x}{x!}$, i.e. it has a Poisson distribution with expected value $t/\theta$. Moreover, it implies that the numbers of customers arriving in non-overlapping time intervals are probabilistically independent.

So memorylessness of waiting times leads to the Poisson process.

$\endgroup$
  • $\begingroup$ Whatever the theorems may say, it is an experimental fact that —in normal situations— arrivals are memoryless. You cannot prove that the number of costumers arriving in some period nothing, really. $\endgroup$ – Mariano Suárez-Alvarez Nov 23 '11 at 4:36
  • $\begingroup$ The intention of the question was not to ask for a formal proof. Many a times, observations are made which lead to a theorem and then intuition is 'developed' to fit the observations and thus help cement the theorem in popular understanding. I was looking for something similar. Have edited my question to include the same. $\endgroup$ – Vighnesh Nov 23 '11 at 17:58
  • $\begingroup$ thanks for the answer. I did not quite follow how the memory less arrivals leads to $\Pr(T>t) = e^{-t/\theta}$. Could you please elaborate or cite a reference that talks about this in detail. Thanks. $\endgroup$ – Vighnesh Nov 23 '11 at 18:04
  • 4
    $\begingroup$ Memorylessness says $\Pr(T>t+s\mid T>t) = \Pr(T>s)$. That's the same as $\Pr(T>t+s\text{ and }T>t) = \Pr(T>s)$. The event $[T>t+s\text{ and }T>t]$ is the same as the event $T>t+s$. Hence the conditional probability is $\Pr(T>t+s)/\Pr(T>t)$. Memorylessness says this is the same as $\Pr(T>s)$. Hence we have $\Pr(T>t+s)=\Pr(T>t)\Pr(T>s)$. A monotone function $g$ that satisfies $g(t+s)=g(t)g(s)$ is an exponential function. And monotocity follows from the fact that $\Pr(T>t+s)$ must be less than $\Pr(T>t)$ because the former event implies, but is not implied by, the latter. $\endgroup$ – Michael Hardy Nov 25 '11 at 5:17
  • $\begingroup$ Shouldn't it be $\Pr(T>t) = 1/\theta*e^{-t/\theta}$? $\endgroup$ – vonjd Sep 3 '14 at 14:13
4
$\begingroup$

Pretty much any intro to queuing theory or stochastic processes book will cover this, e.g., Ross, Stochastic Processes, or the Kleinrock, Queuing Theory.

For an outline of a proof that memoryless arrivals lead to an exponential dist'n:

Let G(x) = P(X > x) = 1 - F(x). Now, if the distribution is memoryless,

G(s+t) = G(s)G(t)

i.e., the probability that x > s+t = the probability that it is greater than s, and that, now that it is greater than s, it's greater than (s+t). The memoryless property means that the second (conditional) probability is equal to the probability that a different r.v. with the same distribution > t.

To quote Ross:

"The only solutions of the above equation that satisfy any sort of reasonable conditions, (such as monotonicity, right or left continuity, or even measurability), are of the form:"

G(x) = exp(-ax) for some suitable value of a.

and we are at the Exponential distribution.

$\endgroup$
  • 3
    $\begingroup$ Robert Gallager's DRAFT OF STOCHASTIC PROCESSES: THEORY FOR APPLICATIONS (rle.mit.edu/rgallager/notes.htm) is a good free alternative for an introduction to stochastic processes including a discussion of the Poisson process $\endgroup$ – Martin Van der Linden Sep 17 '13 at 20:41
  • $\begingroup$ Robert Gallager's RAFT OF STOCHASTIC PROCESSES: THEORY FOR APPLICATIONS $\endgroup$ – Martin Van der Linden Sep 17 '13 at 20:42

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.