1.2 Exponential and Poisson Distribution

In this section, we make a model for the arrival process that is the most useful for queueing and inventory systems.¹¹In queueing systems, an arrival is often called customer or job, while in inventory systems it is called demand. In particular, we show how the exponential and gamma distributions relate to the Poisson distribution, and we use the memoryless property of job inter-arrival times as our point of departure.

We start with two examples to illustrate why it is reasonable to model the time between two events as memoryless. For instance, assume an hour ago a patient with a broken arm arrived at the first aid of a hospital. What can we say about the time the next patient with a broken arm will arrive? In other words, does the information that an hour ago a broken arm arrived help to make a better prediction of the next? Similarly, suppose that the average time between the sales of some shirt in a clothing store is 5 minutes. The shop owner informs us that no shirt has been sold in the past 7 minutes. Surely, this knowledge does not imply that the next shirt will necessarily be sold within the next minute.

Let us formalize this. If a person does not tell us anything about the past, we write \(\P{X>t}\) for the probability that no event occurs before time \(t\). However, if the person tells us at time \(s\) there was no arrival during \([0,s]\), we write \(\P{X>s+t\given X>s}\) for the probability that there will not be an arrival for an additional amount of time \(t\). If we believe that the information \(\{X>s\}\) is immaterial to predicting the lifetime of \(X\) after \(s\), then necessarily \(\P{X > s+t \given X>s} = \P{X>t}\).

The next theorem is fundamental.

Note that for \(X\sim \Exp{\lambda}\), the following properties hold:⁶⁶See Exercise 6 for details.

If we have a sequence of inter-arrival times \(\{X_{i}\}_{i=1}^{\infty}\), then we construct arrival times according to the recursive rule

When inter-arrival times \(\{X_{k}\}\) are iid⁷⁷iid := independent and identically distributed. rvs and distributed as the common rv⁸⁸Henceforth, we write \(X_{k}\) iid \(\sim X\), or \(X_{k}\) iid \(\sim \Exp{\lambda}\). \(X\sim \Exp{\lambda}\), it is clear that the density of the first arrival time is

where we add the last term to see how a pattern emerges. Using convolution, for the second arrival time,

With induction it is straightforward to extend the pattern and prove that \(A_{k} \sim \Gamm{\lambda, k}\), i.e.,

When the arrival times ⁹⁹Arrival times are not the same as inter-arrival times. are gamma distributed, the cdf of the number \(N(t)\) of jobs arriving during \([0, t]\) follows readily by observing that

that is, to have precisely \(k\) arrivals during \([0, t]\), the arrival time \(A_{k}\) of job \(k\) must lie in \([0, t]\), but job \(k+1\) must arrive after \(t\). Using the cdf of \(A_{k}\) and integration by parts,

Combining this with (1.2.4), we find

that is, \(N(t) \sim \Pois{\lambda t}\), i.e., Poisson distributed with parameter \(\lambda t\). It is simple to see from (1.2.5) that¹⁰¹⁰See Exercise 8 for details.

Interestingly, we can use (1.2.4) and (1.2.5) to derive the pdf of \(A_{k}\) from the Poisson distribution. From (1.2.5), \(\P{N(t) = 0} = e^{-\lambda t}\) when \(k=0\), and as \(A_0=0\) by definition, the RHS¹¹¹¹RHS := right hand side, LHS := left hand side. of (1.2.4) becomes \(1-\P{A_1\leq t}\). Consequently, \(\P{A_{1}\leq t} = 1 - e^{-\lambda t}\), and by differentiating this, the pdf is seen to be \(f_{A_1}(t) = \lambda e^{-\lambda t}\). For \(k\geq 1\), take the derivative with respect to \(t\) of (1.2.4) to see that \(\d \P{N(t)=k}/\d t = f_{A_{k}}(t) - f_{A_{k+1}}(t)\). It then follows from (1.2.5) that

With recursion, we retrieve (1.2.3).

The family of rvs \(N_\lambda=\{N(t), t\geq 0\}\) is a Poisson process¹²¹²A random process is a much more complicated mathematical object than a rv: a process is a (possibly uncountable) set of rvs indexed by time, not just one rv. with arrival rate \(\lambda\). Once we have \(N_{\lambda}\), we can define \(N(s, t] := N(t)-N(s)\) as the number of customers that arrive in a general time period \((s, t]\).¹³¹³Note that \([0,t]\) is closed at both ends, but \((s,t</span>\) is open at the left.]

It is important to know that \(N_\lambda\) has stationary and independent increments. Stationarity means that the distributions of the number of arrivals are the same for all intervals of equal length, that is, \(N(s,t]\) has the same probability distribution as \(N(u, v]\) if \(t-s = v-u\). Independence means, roughly speaking, that knowing that \(N(s,t]= n\) does not help to make any predictions about the value of \(N(u, v]\) if the intervals \((s,t]\) and \((u, v]\) do not overlap.

(1.2.5) implies a number of useful properties of the Poisson process. With small \(o\) notation¹⁴¹⁴A function \(f(h) = o(h)\) when \(f(h)/h \to 0\) as \(h\to 0\), e.g., \(x^{2} = o(x)\)., if \(t\ll 1\),

It is important to know that the reverse of the above holds, that is, a stochastic process with stationary and independent increments and satisfying (1.2.6) is necessarily a Poisson process.¹⁵¹⁵We refer to the literature on (mathematical) probability theory for further background.

When we merge two independent Poisson processes \(N_{\lambda}\) and \(N_{\mu}\), e.g., adults and children entering a store¹⁶¹⁶Or some other feature by which you want to distinguish between customers., we obtain a new Poisson process \(N_{\lambda +\mu}\) with rate \(\lambda + \mu\). To see this, we use the above. For \(t\ll 1\),

and the rest of (1.2.6) follows similarly. So we see that we obtain the same type of equations as in (1.2.6) but with \(\lambda\) replaced by \(\lambda+\mu\). Realizing that \(N_{\lambda}\) and \(N_{\mu}\) have stationary and independent increments, it follows that \(N_{\lambda +\mu}\) is a Poisson process with rate \(\lambda+\mu\).

We can also split, or thin, a Poisson process into several substreams. For instance, consider a Poisson process \(N_\lambda\) of people passing by a shop, and suppose that some arbitrary customer decides to enter the shop as a Bernoulli distributed rv \(B\), independent of \(N_{\lambda}\), with success probability \(p\) and failure probability \(q=1-p\). Then the process of customers entering the shop is a Poisson process \(N_{\lambda p}\) with rate \(\lambda p\), because, for \(t\ll 1\), from (1.2.6),¹⁷¹⁷Why are there \(o(t)\) symbols already after the first equality signs? (Hint, it can happen that \(N(t)=2\), but both persons do not enter.)

The resulting process \(N_{\lambda p}\) has an arrival rate of \(\lambda p\) and has stationary and independent increments because \(N_{\lambda}\) is a Poisson process.

The concepts of merging and thinning are useful to analyze queueing networks. Suppose the departure stream of a machine splits into two substreams, e.g., a fraction \(p\) of the jobs moves on to another machine and the rest (\(1-p\)) of the jobs leaves the system. Then we can model the arrival stream at the second machine as a thinned stream (with probability \(p\)) of the departures of the first machine. Merging occurs where the output streams of various stations are sent to a common downstream station.

A final interesting property of the Poisson process is the distribution of arrivals over an interval \([0,t]\) given that \(N(t) = n\).

Summarizing, the Poisson process \(N_{\lambda}\) and the exponential distribution are very closely related: a counting process \(\{N_{\lambda}(t)\}\) is a Poisson process with rate \(\lambda\) if and only if the inter-arrival times \(X_{k} \iidsim \Exp{\lambda}\). Thus, if you find it reasonable to model inter-arrival times as memoryless, then the number of arrivals in an interval is necessarily Poisson distributed. Moreover, if you find it reasonable that the occurrence of an event in a small time interval is equally likely over time and independent from one interval to another, then the arrival process is Poisson, and the inter-arrival times are exponential.

\begin{algorithm}
\begin{algorithmic}[1]
\State \textbf{Input:} rate \(\lambda>0\) and integer \(k\geq1\)
\State \textbf{Output:} value \(T\)
\Procedure{GenerateGamma}{$\lambda,k$}
    \State \(T\gets0\)
    \For{\(i=1,\ldots,k\)}
        \State Draw \(U\sim\Unif{(0,1)}\)
        \State \(T\gets T-\dfrac{1}{\lambda}\log U\)
    \EndFor
    \Return \(T\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
\State \textbf{Input:} parameter \(\lambda>0\)
\State \textbf{Output:} count \(R\)
\Procedure{GeneratePoisson}{$\lambda$}
    \State \(R\gets0\)
    \State Draw \(U\sim\Unif{(0,1)}\)
    \State \(T\gets-\log U\)
    \While{\(T<\lambda\)}
        \State \(R\gets R+1\)
        \State Draw \(U\sim\Unif{(0,1)}\)
        \State \(T\gets T-\log U\)
    \EndWhile
    \Return \(R\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The exercises require pen and paper. All problems have solutions, but not all have hints.

If the somewhat heuristic derivations above do not satisfy your sense for rigor, then you should solve the next set of exercises; otherwise you can skip them.