MIT OCW, Fundamentals of Probability 20日目 確率過程I

David Gamarnik, and John Tsitsiklis. 6.436J Fundamentals of Probability. Fall 2008. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture 20. The Bernoulli and Poisson Processes

stochastic process(確率過程)の議論をする準備ができた.
discrete-time stochastic processは共通したprobability space $(\Omega, \mathcal{F}, P)$上のrandom variableの列$\{X_n\}$である. あるいは,$n, \omega$を引数に取る関数$X$で,任意の$n$に$X_n:\omega \mapsto X_n(\omega)$というrandom variableということであって,また$\omega \in \Omega$を固定したときには$n$の関数(“time function”,とか “sample path”, “trajectory”という)と見ることも出来る.

1. The Bernoulli Process

Bernoulli processでは$X_n\sim Ber(p)$で,全てがi.i.d.である.$S_n = X_1 +...+X_n$とすると,$S_n\sim bin(n,p)$であって
$$p_{S_n}(k) = \left(\begin{array}{} n \\ k\end{array} \right) p^k(1-p)^{n-k},\ E[S_n]=np \ var(S_n)=np(1-p)$$
である.ただし$p_{S_n}$はPMFとする.
また$T_1$を最初に試行が成功するまでの試行数とすると,$T_n \sim geom(p)$であって,
$$p_{T_1}(k) = (1-p)^{k-1}p, E[T_1] = 1/p$$
である.

1.1 Stationarity and Memorylessness

Bernoulli processには特有の構造が有る.

Bernoulli process $\{X_n\}$を考える.ある自然数$m$を固定して,$Y_n = X_{m+n}$とすると,$\{Y_n\}$は$\{X_n\}$と同じdistributionを持ったBernoulli processである. より厳密には,$(Y_1, ..., Y_k)$は$(X_1, ...,X_k)$と同じdistributionを持っている.この性質をstationarity(定常)性という.
また,より強い性質も成り立つ.$X_1, ..., X_m$の値が与えられても,$\{Y_n\}$は変化しない.形式的には
$$\begin{aligned}P((X_{n+1}, X_{n+2},...) \in A|X_1, ...,X_n) &=_{(1)} P((X_{n+1}, X_{n+2}, ...) \in A) \\ &=_{(2)} P((X_1,X_2, ...) \in A)\end{aligned}$$
である.(1)の等式をmemoryless(無記憶)性という.(2)の等号はstationarity propertyの言い換えである.

1.2 Stopping Times

1.1では観測を始める時刻を$m$に固定して議論したが,観測を始める時間がまた確率的に決まる場合を考える.$N$は非負整数値をとるrandom variableとして,$\{Y_n\}$を$Y_n = X_{N+n}$を議論する. $\{Y_n\}$は一般に$\{X_n\}$と同じパラメータのBernoulli processではない. 例えば$N= \min\{n|X_{n+1}=1\}$とすると$P(Y_1=1)=P(X_{N+1}=1)=1 \neq p$である.この不等号は$N$を$X_{N+1}$の実現値が決まってから,すなわち”未来を見て”決めたことに起因している.
一方$N$がcausallyに決まるとき,つまり過去か現在のprocessのみから決まるとき,形式的には

Definition 20-1

$N$がstopping timeである
$\Leftrightarrow$ 任意の$n$について,$\{N=n\}$というeventが起きるか否かが,$X_1, ...,X_n$の顕れに寄ってのみ決まる
またこのとき,任意の$n$に$h_n$という関数があって,
$$I_{N=n} = h_n(X_1, ..., X_n)$$
が成立する.

として,$N$がstopping timeであるときにはmemorylessnessより強い性質を持つ.
$$\begin{aligned} P((X_{N+1}, X_{N+2},...)\in A|N=n, X_1, ...,X_n) &= P((X_{n+1}, X_{n+2}, ...)\in A) \\&= P((X_1, X_2, ...) \in A)\end{aligned}$$
したがって$N$がstopping timeであれば$\{Y_n\}$はまたBernoulli processである.

1.3 Arrival and Interarrival Times

$Y_k = \min\{n|S_n = k\}, Y_0=0$は$k$th arrival timeといい, $k$th interarrival timeを$T_k = Y_k-Y_{k-1}$とする.
$T_1 = Y_1$はgeometricで,またstopping timeだから,$(X_{T_1+1}, X_{T_1 +2}, ...)$もまたBernoulli processである. $T_2$はもとのprocessのsecond interarrival timeだが$(X_{T_1+1}, X_{T_1 +2}, ...)$のfirst arrival timeであって,よって$T_2$はgeometricである.さらに,新しいprocessは$(X_1, ..,X_{T_1})$と独立であって,$T_2$もまた$(X_1, ...,X_{T+1})$と独立である.特に$T_2$は$T_1$とも独立である.
上の段落の議論を繰り返すと,$T_k$はi.i.d. geometricであることがわかる.結果,$Y_k$は$k$のi.i.d. geometricの和だから,$S_t=X_1 + \cdots X_t$として,
$$\begin{aligned} P(Y_k =t) &= P(S_{t-1}=k-1 \land X_t=1) = P(S_{t-1} =k-1) \cdot P(X_t=1) \\&= \left(\begin{array}{} t-1 \\ k-1\end{array} \right)p^{k-1}(1-p)^{t-k}p = \left(\begin{array}{} t-1 \\ k-1\end{array} \right)p^k(1-p)^{t-k} \end{aligned}$$
である.この$Y_k$のPMFをPascal PMFという.

1.4 Marging and Splitting of Bernoulli Processes

$\{X_n\}$と$\{Y_n\}$は独立なBernoulli processで,パラメータはそれぞれ$p, q$とする. $\{Z_n\}$を,$X_n,Y_n$の”merged” processとして,$Z_n = \max\{X_n, Y_n\}$と定義する.
$$P(Z_n = 1) = 1-P(X_n=0, Y_n=0) = 1-P(X_n=0)P(Y_n=0) = 1-(1-p)(1-q)$$
だから,$Z_n\sim Ber(p+q-pq)$であって,$\{Z_n\}$はまたBernoulli processとなる.

また,$\{Z_n\sim Ber(p)\}$というprocessを”Splitting”するprocessも考えられる.$Z_n = 1$となったらコインを投げ($Ber(q)$),その結果を記録していく仮定を考える.
形式的には$\{U_n\sim Ber(q)\}$として
$$X_n = Z_n \cdot U_n,\ Y_n = Z_n \cdot(1-U_n)$$
とする.$\{X_n\}$はパラメータ$pq$のBernoulli processであり,$\{Y_n\}$はパラメータ$p(1-q)$のBernoulli processである. $\{X_n\}, \{Y_n\}$はdependentである.特に
$P(X_n=1|Y_n=1)=0 \neq pq = P(X_n=1)$である.

2. The Poisson Process

Poisson processはBernoulli processの連続時間への近似と考えることが出来る.時刻0から観測を初めて,時刻$t$までに起きた成功の回数をrandom variableとする.つまり,$N(0)=0$とし,$N(t)$を$(0, t]$の間の成功の回数とすると,$N$はpoisson過程である.
ある$\omega$を固定して,$N(t)$を時刻$t$における$N$の現れとする.これは$t$で成功しているならその点で不連続であり,右連続である:$\lim_{\tau \downarrow t} N(\tau) = N(t)$.
Bernoulli processと同様にいくつかのrandom variableを定義する.
$$Y_0=0,\ Y_k=\min\{t|N(t)=k\},\ T_k = Y_k-Y_{k-1}$$
さらに$P(k;t) = P(N(t)=k)$とする.
$\lambda > 0$として,Poisson processは以下の性質によって定義される.
(a)

互いに素な区間たちがあって,その中で成功が起こる回数はindependentである.形式的には,
$0<t_1<...<t_k$で,$N(t_1), N(t_2)-N(t_1), ..., N(t_k)-N(t_{k-1})$はindependentである.これはBernoulli processの試行の独立性の近似である.

(b)

ある区間における成功の回数のdistributionは$\lambda$と区間の長さのみによって決まる.形式的には,$t_1<t_2$ならば
$$P(N(t_2)-N(t_1)=k) = P(N(t_2-t_1)=k) = P(k; t_2-t_1)$$
である.

(c)

$o_k$という関数があって,
$$\lim_{\delta \downarrow 0} \frac{o_k(\delta)}{\delta}=0$$
かつ任意の$\delta > 0$に
$$\begin{aligned} P(0;\delta) &= 1 - \lambda \delta + o_1(\delta)\\ P(1;\delta) &= \lambda \delta + o_2(\delta) \\ \sum_{k=2}^\infty P(k;\delta)&=o_3(\delta) \end{aligned}$$
である

$o_k$はテイラー展開の2次以降の項を捉えるために導入される.

2.1 The Distribution of N(t)

$\lambda$と$t>0$を固定して,$P(k;t)$のclosed form expressionを考える.$(0, t]$という区間を,同じ区間に複数の成功がないように細かく区切って,Bernoulli processで近似する.
大きな$n$を一つ選び,$\delta = t/n$とする.$[0, t]$を長さ$\delta$ごとに区切り,$n$個の”slot”をつくる. 少なくとも１つの成功があるslotにある確率は
$$p = 1-P(0;\delta) = \lambda \delta + o(\delta) = \frac{\lambda t}{n} +o(1/n)$$
である.ただし$o(\delta)/\delta \rightarrow 0$である.
$k$を固定して,以下のeventたちを定義する.

A: $(0, t]$でちょうど$k$回成功する
B: ちょうど$k$個のslotがそれぞれ1つ以上の成功をもつ
C: 少なくとも1角slotが2つ以上の成功を持つ.

$A, B$は$C$が起きない限り一致する.
$$B \subset A \cup B, \ A \subset B \cup C$$
であって
$$P(B)-P(C) \leq P(A) \leq P(B)+P(C)$$
が成立する.ここで
$$P(C) \leq n \cdot o_3(\delta) = (t/\delta) o_3(\delta)$$
右辺は$n \rightarrow \infty \Leftrightarrow \delta \rightarrow 0$で$0$に収束するから,$P(A)$は$n\rightarrow \infty$で$P(B)$に収束する.
成功があったslotの個数はbinomial distributionに従い,そのパラメータは$n=n, p = \lambda t/n+o(1/n)$であって,
$$P(B) = \left(\begin{array}{} n \\k \end{array}\right)\left(\frac{\lambda t}{n} + o(1/n) \right)^k \left(1 - \frac{\lambda t}{n} +o(1/n)\right)^{n-k}$$
が成立する. $n\rightarrow \infty$とすると,Lec.6と同様の計算で,右辺はPoisson PMFに収束し,
$$P(k;t) = \frac{(\lambda t)^k}{k!} e^{-\lambda t}$$
が成立する.これは$(t)$が$\lambda t$をパラメータとするPoisson random variableであることを示している.また$E[N(t)]=var(N(t))=\lambda t$である.

2.2 The distribution of $T_k$

Bernoulli processと同様に, interarrival times $T_k$がi.i.d. でexponentialなrandom variableであることを示す.

2.2.1 First argument

$$P(T_1 > t) = P(N(t)=0) =P(0;t) = e^{-\lambda t}$$
である.これはexponentila CDFだから,
$$f_{T_1}(t) = \lambda e^{-\lambda t}$$
とPDFが得られる.
$t_1, t_2 >0, \ \delta < t_2$, また$\delta$は十分小さい正数とする.このとき十分狭い区間では複数個の成功は起こらないという仮定のもとで
$$\begin{aligned} P(t_1 \leq T_1 \leq &t_1+\delta, t_2 \leq T_2 \leq t_2 +\delta)\\&\sim P(0;t_1)\cdot P(1;\delta) \cdot P(0;t_2-t_1-\delta) \cdot P(1;\delta) \\ &=e^{-\delta t_1} \lambda \delta e^{-\delta(t_2-\delta)}\lambda \delta \end{aligned}$$
両辺を$\delta^2$で割って$\delta \downarrow 0$とすれば
$$f_{T_1, T_2} (t_1, t_2) = \lambda e^{-\lambda t_1} \lambda e^{-\lambda t_2}, \ t_1, t_2 > 0$$
を得る.よって$T_1, T_2$はindependentで,同じexponential distributionをもつ. 繰り返して,$\{T_k\}$はi.i.d.で,共通したパラメータ$\lambda$をもつexponential distributionに従う.

2.2.2 Second Argument

簡単のため,$\lambda = 1$とする.$0 < s \leq t$として,
$$\begin{aligned} P(Y_1 \leq s, Y_2 \leq t) &= P(N(s) \geq 1, N(t) \geq 2) \\&=P(N(s)=1)P(N(t)-N(s)\geq 1) +P(N(s) \geq 2) \\ &=se^{-s}(1-e^{-(t-s)})+(1-e^{-s}-se^{-s}) \\&=-se^{-t}+1-e^{-s} \end{aligned}$$
両辺を微分して,
$$f_{Y_1, Y_2} (s,t) = \frac{\partial^2}{\partial t \partial s} P(Y_1 \leq s, Y_2 \leq t) = e^{-t}, \ \ 0 \leq s \leq t$$
が成立する.よって,$Y_2=t$を決めると,$Y_1$は$(0, t)$上uniformである.すなわち,2回目の成功が起きるまでの時刻,1回目の成功が起きうる時刻は同様に確からしい.
$T_1 = Y_1, T_2 = Y_2 -Y_1$とすると,
$$f_{T_1, T_2} (t_1, t_2) = f_{Y_1, Y_2}(t_1, t_1+t_2) = e^{-t_1}e^{-t_2}$$
である.

2.2.3 Alternative Definition of the Poisson Process

$T_1, T_2, ...$はi.i.d. で$\lambda$を共通のパラメータ$p$のexponential distributionをもつとする. 成功した時刻$T_1, T_1+T_2, T_1 + T_2 + T_3, ...$を記録していくとして,この定義はまたPoisson processの定義(a),(b),(c)を導く.

2.3 The Distribution of $Y_k$

$Y_k$は$k$個の$exp(\lambda)$のi.i.d.なrandom variableの和だから,PDFは畳み込みを繰り返して構成できる. PDFのもう一つの導出方法を述べる.
小さな区間で2つ以上成功する可能性を無視すると,
$$P(y\leq Y_k \leq y+\delta) = P(k-1;y)P(1;\delta) = \frac{\lambda^{k-1}}{(k-1)!} y^{k-1}e^{-\lambda y}\lambda \delta$$
両辺を$\delta$で割って$\delta \downarrow 0$とし,
$$f_{Y_k}(y) = \frac{\lambda^{k-1}}{(k-1)!}y^{k-1}e^{-\lambda y} \lambda , \ \ y>0$$
が言える.これを自由度$k$のGammaかErlang(アーラン) distributionという.
他の導出に,$y\geq 0$に,$\{Y_k \leq y\}$というeventが
$\{\text{number of arrivals in the interval [0, y] is at least k}\}$
というeventと同じであることを考えれば,CDFは
$$F_{Y_k}(y) = P(Y_k \leq y) = \sum_{n=k}^\infty P(n,y) = 1-\sum_{n=0}^{k-1}P(n, y) = 1 - \sum_{n=0}^{k-1} \frac{(\lambda y)^n e^{-\lambda y}}{n!}$$
であって,$Y_k$のPDFはこれを微分することで得られる.
$$f_{Y_k}(y) = \frac{d}{dy} F_{Y_k}(y) = \frac{\lambda^k y^{k-1}e^{-\lambda y}}{(k-1)!}$$