# Poisson Process & Exponential Distribution

## Poisson Process 機率函數推導

:::info
The number of occurrences in some time interval to be a Poisson random variable is equivalent to assuming the time between successive occurrences to be an exponentially distributed random variable (If an only if)
:::

首先定義一些機率與其性質：

$$\begin{cases} Pr(there's\ an\ arrival\ between\ T\ and\ T + \Delta t) = \lambda * \Delta t + o(\Delta t) \\ Pr(more\ than\ one\ arrival\ between\ T\ and\ T + \Delta t) = o(\Delta t) \\ \frac{lim_{\Delta t \to 0}\ o(\Delta t)}{\Delta t} = 0 \end{cases}$$

我們的目標是求出 $P_n(t)$，即是在 $t$ 單位時間內有 $n$ 個 arrival 的機率。

### 推導

$P_n(t + \Delta t)$ 為在 $t + \Delta t$ 單位時間內有 $n$ 個 arrival 的機率，這 $n$ 個 arrival 分布在 $t$ 與 $\Delta t$ 的情況總共有 $n+1$ 種，描述如下：

1. 在 $t$ 時間內有 $n$ 個 arrival
2. 在 $t$ 時間內有 $n-1$ 個 arrival, 在 $\Delta t$ 時間內有 $1$ 個 arrival
3. 在 $t$ 時間內有 $n-2$ 個 arrival, 在 $\Delta t$ 時間內有 $2$ 個 arrival
4. 在 $t$ 時間內有 $n-3$ 個 arrival, 在 $\Delta t$ 時間內有 $3$ 個 arrival
5. $\cdots \cdots$

以此類推，其中從第三項開始一直到第 $n+1$ 項，根據上面定義的機率，可由 $o(\Delta t)$ 表示（因為 $o(\Delta t)$ 代表在 $\Delta t$ 單位時間內有超過 $2$ 以上的 arrival），因此我們可推導出：

$$\begin{cases} P_n(t + \Delta t) = P_n(t)[1 - \lambda * \Delta t - o(\Delta t)] + P_{n-1}(t)[\lambda * \Delta t + o(\Delta t)] + o(t) \\ P_0(t + \Delta t) = P_0(t)[1 - \lambda * \Delta t - o(\Delta t)] \end{cases}$$

將式子整理：

$$\begin{cases} P_n(t + \Delta t) - P_n(t) = - \lambda P_n(t) \Delta t + \lambda P_{n-1}(t)\Delta t + o(\Delta t)(1 + P_{n-1}(t) - P_n(t)) \\ P_0(t + \Delta t) - P_0(t) = - \lambda P_0(t) \Delta t + o(\Delta t)(1 - P_0(t)) \end{cases}$$

同除 $\Delta t$，再取極限：

$$\begin{cases} lim_{\Delta t \to 0} \frac{P_n(t + \Delta t) - P_n(t)}{\Delta t} = - \lambda P_n(t) + \lambda P_{n-1}(t) \\ lim_{\Delta t \to 0} \frac{P_0(t + \Delta t) - P_0(t)}{\Delta t} = - \lambda P_0(t) \end{cases}$$

$$\Rightarrow \begin{cases} P_n'(t) = - \lambda P_n(t) + \lambda P_{n-1}(t) \\ P_0'(t) = - \lambda P_0(t) \end{cases}$$

解微分方程:

$$\begin{cases} P_0(t) = Ce^{-\lambda t} = e^{-\lambda t}(\because P_0(0) = 1) \\ P_1(t) =\lambda t e^{-\lambda t} \\ P_n(t) =\frac{(\lambda t)^n e^{-\lambda t} }{n!} \end{cases}$$

:::info

微分方程不會解的請參考微積分課本，這裡僅簡單介紹解的過程。

when solving $P_1(t), P_2(t)...$, use the following technique, take $P_1(t)$ for example:

$P_1'(t) = - \lambda P_1(t) + \lambda P_0(t) = - \lambda P_1(t) + \lambda e^{-\lambda t}$

$P_1'(t) + \lambda P_1(t) = \lambda e^{-\lambda t}$

let $p(t) = \lambda, q(t) = \lambda e^{-\lambda t}, u(t) = e^{\int p(t) dt} = e^{\lambda t}$

solve: $(u(t)P_1(t))' = u(t)q(t)$, which is $u(t)P_1(t) = \int u(t)q(t) dt$

Then we get $P_1(t) = u(t)^{-1} \int u(t)q(t) dt$
:::

$$P_n(t) =\frac{(\lambda t)^n e^{-\lambda t} }{n!}$$ 即是 Poisson random variable 的 PMF。

證明完成，有興趣更深入了解 Poisson 分佈的同學可參考[這裡](https://en.wikipedia.org/wiki/Poisson_distribution)。

## Markovian Property(Memoryless) of Exponential Distribution

suppose service times are exponentially distributed. This property states that the probability that a customer currently in service has t units of remaining service is independent of how long it has already been in service.

$$Pr(T \le t_1 | T \ge t_0) = Pr( 0 \le T \le t_1 - t_0)$$

proof:

$$\begin{align} Pr(T \le t_1 | T \ge t_0) &= \frac{Pr(T \le t_1 \cap T \ge t_0)}{Pr(T \ge t_0)} \\ &= \frac{Pr(T \ge t_1 \cup T \le t_0)'}{Pr(T \ge t_0)} \\ &= \frac{1 - Pr(T \ge t_1 \cup T \le t_0)}{Pr(T \ge t_0)} \\ &= \frac{1 - (Pr(T \ge t_1) + Pr(T \le t_0) - Pr(T \ge t_1 \cap T \le t_0))}{Pr(T \ge t_0)} \\ &= \frac{1 - (e^{-\lambda t_1} + (1 - e^{-\lambda t_0}) - 0)}{e^{-\lambda t_0}} \\ &= \frac{e^{-\lambda t_0} - e^{-\lambda t_1}} {e^{-\lambda t_0}}\\ &= 1 - e^{-\lambda (t_1 - t_0)} \end{align}$$

> 圖中斜線部分，就是memoryless 的意思。

## Random Split of a Poisson Process

給定一個 Poisson Process (Poisson($\lambda t$))：在一段長度為 $t$ 的時間中，有 $l$ 個 arriva。在 $l$個 arrival中隨機選 $j$ 個(每個arrival 被選中的機率皆為 $P_k$)。欲證明這 $j$ 個 arrival 也是一個 Poisson Process，證明如下：

$$Pr(j\ 個\ arrival\ 在全部\ l\ 個\ arrival\ 中被選中)$$

透過條件機率可表示成：

$$Pr(l\ 個\ arrival) \cdot Pr(l\ 個\ arrival\ 中選\ j\ 個\ arrival) \\ = \sum_{l = j}^{\infty} \frac{(\lambda t)^l e^{-\lambda t}}{l!} \cdot {l \choose j}(P_k)^j(1-P_k)^{l-j}$$

做變數代換，令 $l = a + j$：

$$\sum_{a = 0}^{\infty} \frac{(\lambda)^{a+j} e^{-\lambda t}}{(a+j)!} \cdot {a+j \choose j}(P_k)^j(1-P_k)^{a}$$

將式子裡面跟 $a$ 有關的整理在一起，其他可提出sigma外：

$$\frac{e^{-\lambda t} (P_k)^j (\lambda t)^j}{j!} \cdot \sum_{a=0}^{\infty} \frac{(\lambda t)^{a}（1-P_k)^a}{a!} \\ = \frac{e^{-\lambda t} (P_k)^j (\lambda t)^j}{j!}\cdot e^{\lambda t \cdot (1-P_k)} \\ = \frac{e^{-\lambda t P_k} \cdot (\lambda t P_k)^j}{j!}$$

上式即是 $Poisson(\lambda t P_k)$ 的 pdf form。數學背後的含義為：本來是 $Poisson(\lambda t)$，經過機率為 $P_k$的 random split之後變成 $Poisson(\lambda t P_k)$。

## Aggregation of Poisson Process

$Poisson(\lambda_1) + Poisson(\lambda_2) + Poisson(\lambda_3) = Poisson(\lambda_1 + \lambda_2 + \lambda_3)$

pf: 待補

## Forward Recurrence Time & Backward Recurrence Time in Poisson Process


假設今天有兩個觀察者，一個是在時間點 $t_0$ 時進來系統的隨機觀察者，另一個是在系統內的固定觀察者。固定觀察者對時間長度 T 觀察到的期望值（假設是下一班公車來的時間期望值）會是 $E[T] = \frac{1}{\lambda}$，而隨機觀察者對時間長度 T 觀察到的卻會$E[B] + E[F] = \frac{2}{\lambda}$，為什麼會出現不同的觀察結果？

簡短的答案：因為是從不同角度去對這個系統做觀察，所以當然會得到不一樣的結果，想像今天你是公車系統的監測工程師，你觀察到的是只有 10% 公車站牌的負載量過大，其他 90% 的公車站牌都沒有什麼乘客在等待，但是從乘客的角度來看，有 90% 的乘客都擠在那 10%的公車站牌準備搭公車，兩者對公車等待時間的感受一定是不一樣的。

詳細證明：

假設在整段被觀察的時間軸內，有 $m$ 段長度不等的時間段，而我們關注的是時間段 $T = n\Delta t$（任意長度，$\Delta t$ 為單位時間），定義 $X_n$ 為 $T$ 出現在任一長度時間段的機率，也就是一個任一長度的時間段對於全部時間段總數的比例。

舉例來說若總共有長度分別為 $8, 5, 17, 5, 15$ 五個時間段，則對長度為 $5$ 的這個時間段，它的 $X_n$就是 $\frac{2}{5}$。

所以說一個隨機觀察者觀察到的時間段的長度為 $T = n\Delta t$的機率為

$$\frac{(mX_n) \cdot n\Delta t}{\sum_j (m X_j) \cdot j\Delta t} \\ = \frac{X_n\cdot n \Delta t}{E(T)}$$

我們想要求得一個隨機觀察者觀察到的時間段的長度的期望值，即 $E(len(observed\ interval\ by\ random\ observer))$，對應上圖就是求 $E(B) + E(F)$，而上面已經推導出$T = n\Delta t$的機率，故所求等於：

$$\sum n\Delta t \cdot\frac{X_n\cdot n \Delta t}{E(T)} \\ = \sum \frac{(n\Delta t)^2 \cdot X_n}{E[T]} \\ = \frac{E[T^2]}{E[T]}$$

$\because Var(T) = (\frac{1}{\lambda})^2 = E[T^2] - (E[T])^2$ （T 為 exponential random variable)

$\therefore (\frac{1}{\lambda})^2 = E[T^2] - (\frac{1}{\lambda})^2$

$\therefore E[T^2] = 2\cdot (\frac{1}{\lambda})^2$

故 $E(len(observed\ interval\ by\ random\ observer)) = \frac{E[T^2]}{E[T]} = \frac{2} {\lambda} = 2 \cdot E[T]$

## Non-homogeneous Poisson Process

## Poisson Batch Arrival Process