4.2 Poisson Processes

Poisson Process

A Poisson process $N\sim PP(\lambda )$ for some arrival rate $\lambda >0$ is a continuous-time stochastic process $N=\{N_t{\}}_{t\ge 0}$, such that each $N_t\sim \mathrm{Pois}(\lambda t)$ is a Poisson random variable that denotes the number of arrivals at time $t$,
$N_t=\max \{n\ge 0:T_n\le t\},$
where $T_n=\sum _{i=1}^n{S}_i\sim \mathrm{Erlang}(n,\lambda )$ is the cumulative time (i.e., the sum of n Exponential, independent, and identically distributed arrival times $S_i\sim \mathrm{Exp}(\lambda )$) from $t=0$ at which the $n$-th event occurs:

\usetikzlibrary{decorations.pathreplacing}
\begin{document}
 
\large\begin{tikzpicture}[xscale=1.5, yscale=1]
 % Axes
 \draw[->] (0,0) -- (6.5,0) node[right] {$t$} node[at start, below]{$0$};
 \draw[->] (0,0) -- (0,5.5) node[above] {$N_{t}$};
 
 % Step function (Poisson process)
 \draw[very thick, red!70!black]
   (0,0) -- (0.4,0) node[midway, above, black]{$S_1$}
   -- (0.4,1) -- (1.6,1) node[midway, above, yshift=-1cm, black]{$S_2$}
   -- (1.6,2) -- (2.3,2) node[midway, above, yshift=-2cm, black, ]{$S_3$}
   -- (2.3,3) -- (4,3) node[midway, above, yshift=-3cm, black, ]{$S_4$}
   -- (4,4) -- (5.3,4) node[midway, above, yshift=-4cm, black, ]{$S_5$}
   -- (5.3,5) -- (6.5,5);
 
 % Define lines and plot for each T_i
 \foreach \x/\y/\label in {0.4/1/$T_1$, 1.6/2/$T_2$, 2.3/3/$T_3$, 4.0/4/$T_4$, 5.3/5/$T_5$} {
   \draw[dashed] (\x,-0.2) -- (\x,\y) node[at start, below] {\label};
   \filldraw[red!70!black] (\x,\y) circle (2pt);
   \draw[dashed] (-0.2,\y) -- (\x,\y);
 }
 
 % Define lines for t
 \draw[dashed] (3.4,0) -- (3.4,5) node[at start, below] {$\tau$};
 \draw[dashed] (-0.1,3) -- (3.4,3);
 
 % Arrows and labels for memoryless
 \draw[->, thick] (3.4,3) -- (3.4,5.5) node[above]{$N_{\tau+u} - N_\tau$} node[at start, below]{$0$};
 \draw[->, thick] (3.4,3) -- (6.5,3) node[right]{$u$};
 \node at (4, 2.7) {$U_{1}$};
 \node at (5.3, 2.7) {$U_{2}$};
 
 % Annotation for memoryless
 \draw [decorate, decoration={brace, amplitude=10pt, raise=-7.5pt}] (3.4,6.5) -- (6.5,6.5) node[midway, above]{Memoryless};
 
\end{tikzpicture}
 
\end{document}

The distribution of each $T_n\sim \mathrm{Erlang}(n,\lambda )$ is called the Erlang distribution, and represents the distribution of the sum of $n$ independent and identically distributed Exponential variables (in this case, the inter-arrival times) with parameter $\lambda >0$. The probability

Memorylessness memoryless property from the Poisson (through the $N_t$'s) and Exponential distribution (through the $S_i$'s). Note that the Erlang-distributed $T_n$'s are not memoryless.

The Poisson process inherits the

Rationale

At the core of Poisson Processes are the independent and identically distributed inter-arrival times $S_i$. Given that they are Exponentially distributed, we can determine the distribution of every arrival $N_t$. We proceed as follows:

Properties

(Stationary Increments) $N_{t+\tau }-N_t\sim \mathrm{Pois}(\lambda \tau )$.

(Independent Increments) All $I_t=N_t-N_{t-1}$ are mutually independent.

(Small Increments) $\mathbb{P}(N_{t+dt}-N_t=k)=\{\begin{array}{ll}1-\lambda dt+o(dt)& \text{if }k=0,\\ \lambda dt+o(dt)& \text{if }k=1,\\ o(dt)& \text{if }k\ge 2.\end{array}$

We know that $I_{t+dt}=N_{t+dt}-N_t\sim \mathrm{Pois}(\lambda dt)$. Given this, we have:
$p_{I_{t+dt}}(k)=e^{-\lambda dt}\frac{(\lambda dt{)}^k}{k!}=\{\begin{array}{ll}{e}^{-\lambda dt}& k=0,\\ \lambda dt{e}^{-\lambda dt}& k=1,\\ \frac{1}{2}(\lambda dt{)}^2{e}^{-\lambda dt}& k\ge 2.\end{array}$
When $k=0$,

(Poisson Merging) Let $N\sim \mathrm{PP}(\lambda )$ and $M\sim \mathrm{PP}(\mu )$ be mutually independent. Then, $N+M\sim \mathrm{PP}(\lambda +\mu )$.

(Poisson Splitting) Let $N\sim \mathrm{PP}(\lambda )$ and $B_1,B_2,\dots {\sim }_{\text{iid}}\mathrm{Ber}(p)$ be independent of $N$. Then, $K_t=|\{i:B_i=0,i\le N_t\}|$ and $J_t=|\{i:B_i=1,i\le N_t\}|$ such that $K\sim \mathrm{PP}(\lambda p)$, and $J\sim \mathrm{PP}(\lambda [1-p])$ are mutually independent.

In poisson splitting, each arrival to $N_t$ is routed to $K_t$ or $J_t$ according to independent Bernoulli trials, where $B_i$ determines the probability of the $i$-th arrival going to $K_t$ or $J_t$.

(Random Incidence Paradox) $\mathbb{E}[(T_{n+1}-t^{\ast })+(t^{\ast }-T_n)]=\frac{2}{\lambda }$.

Consider some random arrival time $t^{\ast }$ dividing the inter-arrival time $S_{n+1}=T_{n+1}-T_n$ into two distinct intervals, $L=t^{\ast }-T_n$ and $M=T_{n+1}-t^{\ast }$. Then, because inter-arrival times are memoryless, $L\sim \mathrm{Exp}(\lambda )$ and $M\sim \mathrm{Exp}(\lambda )$, and $L,M$ are independent of one another. By the linearity of expectation,
$\mathbb{E}[L]+\mathbb{E}[M]=1/\lambda +1/\lambda =2/\lambda .$
This is a paradox for a reason: wouldn’t $\mathbb{E}[T_{n+1}-T_n]=1/\lambda$? The answer is also yes! We can make the following rationale:

1. $\mathbb{E}[T_{n+1}-T_n]=1/\lambda$ is the expected inter-arrival time in a Poisson process.
2. $\mathbb{E}[(T_{n+1}-t^{\ast })+(t^{\ast }-T_n)]=2/\lambda$ is the expected inter-arrival time in the interval which some random $t^{\ast }$ falls into.

It turns out that this result leads us to the conclusion that since we are choosing our time $t^{\ast }$ randomly, it’s more likely it lands in a longer interval than a short one regardless of its distribution. Longer intervals have a better chance to be chosen, while shorter intervals have a lower chance. Think about that the next time you are trying to catch the next bus!

Examples

Bus Station

You are waiting for a bus at a bus station. A-line buses arrive at the station according to a Poisson process with an average arrival time of 10 minutes.

If the A-line has been running for a long time and you arrive at the bus station at a random time, what is your expected waiting time? $\text{PP}(0.1)$ is $1/0.1=10$ minutes. Therefore, on average, you will have to wait 10 minutes for the next bus.

The expected time of the Poisson Process

On average, how many minutes ago did the last A-line bus leave?

The memoryless property still applies backwards in time, so on average, the last bus arrived 10 minutes ago as well.

The bus station you are waiting at also services B- and C-line buses, and you can use the C-line to reach your destination. There is a 95% chance that the next C-line bus will arrive within 26 minutes.

You are in a rush to make it to your probability class–what is the chance that the next C-line bus will arrive within 6 minutes? $F_T(x=26)=1-e^{-26\lambda }=0.95$. Solving, we obtain $\lambda \approx 0.115$ (i.e., 8.7 minutes on average per bus). We then plug in $F_T(x=6)=1-e^{-6\cdot 0.115}\approx 0.5$.

We start by observing that

The B-line buses arrive every 5 minutes on average. However, B-line buses take you on a completely different route, and are not useful.

What is the chance that an A-line or C-line bus will arrive before a B-line bus? ${\lambda }_A=1/10$, ${\lambda }_B=23/200$, ${\lambda }_C=1/5$. We merge these 3 processes and look at the result: $\mathbb{P}(\min (T_A,T_C)<T_B)=\frac{{\lambda }_A+{\lambda }_C}{{\lambda }_A+{\lambda }_B+{\lambda }_C}\approx \mathrm{0.52.}$

Assume all three lines are independent Poisson processes, so the time until the next bus on each line is exponential with rates

Spam/Ham (Poisson Merging)

Emails to Bob gets automatically classified, and those considered to be Spam are routed to a Spam folder. Emails not classified as spam are routed to Bob’s Inbox. Regular email arrives as a Poisson Process with rate 10 msgs/hr and Spam arrives at a rate of 20 msgs/hr. A regular email is classified as spam with probability 0.05 and a spam email is classified as regular mail with probability 0.01. 

Bob checks his Inbox after a long time and selects the most recent message. What is the probability it is spam? ${\lambda }_{\text{regular}}=10\cdot (1-0.05)=9.5$ msgs/hr. Spam mails that pass the spam filter arrive at ${\lambda }_{\text{spam}}=20\cdot 0.01=0.2$ msgs/hr.

Genuine mails that pass the spam filter arrive at

As such, the probability of spam mail in Bob’s Inbox is $\frac{0.2}{9.5+0.2}=0.0206$.

What’s the probability that the top email in his spam mail is regular mail? ${\lambda }_{\text{reg, rej}}=10\cdot 0.05=0.5$ msgs/hr, whereas spam gets rejected at a rate of ${\lambda }_{\text{spam, rej}}=20\cdot (1-0.01)=19.8$ msgs/hr.

We use the logic from the previous problem: genuine mail gets rejected by the spam filter at a rate of

As such, the probability of regular mail in Bob’s spam mail is $\frac{0.5}{19.8+0.5}=0.0246$.