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)!}$$

MIT OCW, Machine Learning 02日目 SVM

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

The Support Vector Machine

大きなgeometric marginがあって線形分離できるという仮定のもとで,有限回の繰り返しでそのようなlinear classifierを与えられることを見た.Support Vector Machine(SVM)は繰り返しでなく直接そのようなlinear classifierを与える. まず,正しく線形分離を行うclassifierを見つけて(fig.1a),それからgeometric marginが最大になるように$\theta$を調節する(fig.1b).このような解は一意である.

figure 1

より形式的には,geometric marginを最大化する最適化問題となる. すなわち,$y_t\theta^T\mathbf{x}_t\geq \gamma$がすべてのtraining dataに成立するという制約条件のもとで,$\gamma_{geom}=\gamma/\|\theta\|$を最大化する. $\gamma_{geom}$を最大化する代わりに,逆数$\|\theta\|/\gamma$か$\frac{1}{2}(\|\theta\|/\gamma)^2$を最小化する問題とすることもできる.
$y_t\theta^T \mathbf{x}_t \geq \gamma$の両辺を$\gamma$で割って
$$\text{minimize } \frac{1}{2}\|\theta/\gamma\|^2 \text{ subject to }y_t(\theta/\gamma)^T \mathbf{x}_t \geq 1 \text{ for all } t= 1,...,n$$
となる.この問題の解は$\gamma$と$\theta$のそれぞれの値を与えず,$\theta$の定数倍によって得られるdecision boundaryは変わらないから,$\gamma=1$としてよい.以上から,結局
$$\text{minimize } \frac{1}{2}\|\theta|^2 \text{ subject to }y_t(\theta/)^T \mathbf{x}_t \geq 1 \text{ for all } t= 1,...,n$$
という最適化問題を解くことになる. この最適化問題はstandard SVM formであり,quadratic programming problem(目的関数が線形制約のもとのパラメータの二次関数)である. この解として得られるgeometric marginは$1/\|\hat{\theta}\|$である. decision boundaryとgeometric marginは$\gamma=1$という設定によって変化していない.

General Formulation, Offset Parameters

パラメータにoffset term $\theta_0$を加えることで,decision boundaryが必ずしも原点を通らなくとも良くなる. このときclassifierは
$$f(\mathbf{x}; \theta, \theta_0) = sign(\theta^T \mathbf{x}+\theta_0)$$
separating hyperplaneは$\theta^T\mathbf{x}+\theta_0=0$なる$\mathbf{x}$の集合である.$\theta_0$の導入によって,原点を通るlinear classifierよりも大きなmarginを取れるようになることが有る. $\theta_0$の導入によって最適化問題は
$$\text{minimize } \frac{1}{2}\|\theta|^2 \text{ subject to }y_t(\theta^T \mathbf{x}_t+\theta_0) \geq 1 \text{ for all } t= 1,...,n$$
となる.$\theta_0$は制約項においてだけ考慮する. $\theta_0$はまさしくgeometric marginを最大化するためにのみ導入されるのである.

Properties of the Maximum Margin Linear Classifier

Benefits

解はtraining dataが与えられるたびに一意に決まり,geometric marginが最大になるようにboundaryを引くから,データのノイズに対して頑強である. さらに,marginの上のexampleたち(support vectors)のみによってパラメータは決まる(これが利点であるか否かを言うには,classifierの良さをより形式的に測る方法を議論する.).

training examplesのみが与えられたときのclassifierの性能をはcross-validationによって計量される. これは単純に,training dataのある部分集合だけを使ってclassifierを訓練し,そのclassifierが選ばれなかったtraing examplesに対する成績を計測していくのである. leave-one-out cross-validationはそのような方法の一つで,traing dataから1つだけexampleを取り出して訓練を行い,取り出されたexampleを正しく判別できたか否かをたしかめ,これをtraing data全てに繰り返す. 右肩に$-i$を置くことで$i$番目のexampleを取り出して訓練したときのパラメーターを表すとすると,
$$\text{leave-one-out CV error } = \frac{1}{n} \sum_{i=1}^n \text{Loss} \left(y_i, f(\mathbf{x}_i; \theta^{-i}, \theta_0^{-i}) \right)$$
である.ただし$\text{Loss}(y, y') = \begin{cases} 1 \ \ (y\neq y') \\ 0 \ \ \text{otherwise} \end{cases}$ とする. leave-one-out CV errorが低いとよくgeneralizeできていると考えられるが,保証されているわけではない.
maximum margin linear classifierにおいて,あるexampleを除いて訓練を行ってそのexampleを判別し損ねるというのは,そのexampleがsupport vectorであるときであって,
$$\text{leave-one-out CV error} \leq \frac{number of support vectors}{n}$$
である. よって,support vectorが少ないほどよい.これを解のsparse(疎)性質という.

Problems

たった一つのexampleであっても,labelが間違っていると完全にmaximum margin classifierを変化させてしまう.

Allowing Misclassified Examples, Relaxation

labelを間違えることはよく有ることだから,これに弱いというのは致命的なので,mislabelに強くする工夫が必要である. うまく判別できないデータが与えられたとして,それがmislabelによるのか,あるいは線形分離不可能だからなのかを知ることは困難である. どちらにせよ, traing exampleに対する正確性と,未知のexampleに対する正確性にはトレードオフの関係が有ることを肝に銘じなければならない.
maximum margin classifierをmislabelに頑強にする最も単純な方法の一つにslack variableの導入が有る. それぞれのexampleに対して,どれほどmarginの内側に来てしまうかを計量し,それのtraing dataの和を小さくするようにobjective functionに付け加えるのである.形式的には
$$\text{minimize} \frac{1}{2}\|\theta\|^2 + C \sum_{t=1}^n \xi_t$$
$$\text{subject to } y_t(\theta^T \mathbf{x}_t+\theta_0) \geq 1-\xi_t \text{ and } \xi_t \geq 0 \text{ for all } t = 1, ... n$$

となる.$\xi_t$がslack variableである. example $\mathbf{x}_t$がmarginを内側にはみ出るとき$\xi_t > 0$となって,objective functionに$C\xi_t$を加え,$1/2\|\theta\|^2$の最少化を阻害し,未知のdataに対する頑強さを減じる. $C$を小さくするとよりmislabelに強いが未知のexampleに弱く,$C$を大きくするとmislabelに弱いが未知のexampleに強くなる.$C$が極端に大きくなると,slack variableを考えないのと同じことになる.

MIT OCW, Fundamentals of Probability 19日目 大数の法則と中心極限定理

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 18. Laws Of Large Numbers

• Lecture 18. Laws Of Large Numbers
  • 1. Useful Inequations
    • • Markov Inequality
      • Chevbyshev Inequality
  • 2. The Weak Law of Large Numbers
    • • Proposition 19-1
      • Theorem 18-1 The Weak Law of Large Numbers (証明略)
      • Theorem 19-1 The Strong Law of Large Numbers
    • 18-3 The Central Limit Theorem (中心極限定理)
      • Theorem 18-2 Central Limit Theorem, CLT
  • 19-2. The Chernoff Bound
    • 19-2.1 Upper Bound
      • Theorem 19-2 (Chernooff Upper Bound) (証明略)
      • Example
    • 19-2.2 Lower Bound
      • Assumption 19-1.
      • Theorem 19-3 (Chernoff Lower Bound)

1. Useful Inequations

Markov Inequality

$X$が非負なrandom variableなら
$$P(X \geq a) \leq E[X]/a$$

proof.

$$I_{\{X\geq a\}} \leq X/a$$
が必ず成立する.両辺のexpectationを考えれば直ちに成立.

Chevbyshev Inequality

$$P(|X - E[X]| \geq \epsilon) \leq var[X]/\epsilon^2$$

proof.

Markov inequalityで,$X = |X-E[X]|$, $a = \epsilon^2$とすれば直ちに成立.

2. The Weak Law of Large Numbers

expectationは無限回の試行の結果の平均と考えることが出来る. “有限回の試行の結果の平均(sample mean)はexpectationに近づく”ということの定式化がlaw of large numbers (大数の法則)である.
大数の弱法則と大数の強法則があり,後者は前者を導く.大数の強法則を僅かに弱くして証明し,弱法則をも導く.まずalmost sure convergenceの証明に使う補題を示す.

Proposition 19-1

$\{X_n\}$をrandom variableの列とする.独立性は仮定しない.
(i) $\sum E[|X_n|^s] < \infty, s>0 \Rightarrow X_n \rightarrow^\text{a.s.} 0$
(ii) $\forall \epsilon>0, \sum P(|X_n|>\epsilon) < \infty \Rightarrow X_n \rightarrow^\text{a.s.} 0$

proof.

(i)
$\sum_{n=1}^\infty E[|X_n|^s] =E[\sum_{n=1}^\infty |X_n|^s <\infty$がmonotone conergence theoremから成立し,ゆえに$\sum_{n=1}^\infty |X_n|^s$というrandom variableは確率1で有限. したがって$|X_n|^s \rightarrow^\text{a.s.} 0$であり,$X_n \rightarrow^\text{a.s.} 0$.
(ii)
任意の$k \in \mathbb{N}$を取って$\epsilon = 1/k$とする. Borel-Cantelli lemmaから$P(\{|X_n| > 1/k \text{ i.o.}\})=0$すなわち$\{|X_n|>1/k\}$というeventは確率1で有限回のみ起こる. したがって$P(\limsup X_n > 1/k) = 0$が任意の$k$に成立する.$\{\limsup |X_n|>1/k\}$は単調で$P(\{\limsup X_n > 0\})=0$に収束する.よって$X_n \rightarrow^\text{a.s.}0$

Theorem 18-1 The Weak Law of Large Numbers (証明略)

$\{X_n\}$がi.i.d.で$E[|X_1|] < \infty$ならば,$S_n = \sum_{i=1}^n X_i$とすると
$$\frac{S_n}{n} \rightarrow^\text{i.p.} E[X_1]$$

Theorem 19-1 The Strong Law of Large Numbers

Theorem 18-1の仮定のもとで
$$\frac{S_n}{n} \rightarrow^\text{a.s.} E[X_1]$$

proof.

$E[X^4] < \infty$を前提に加える. このとき$E[|X|] <\infty$. $|X| \leq 1+x^4$から
$$E[|X|] \leq 1 + E[X^4] < \infty$$
$E[X] = 0$を仮定し,$E[\sum (X_1 + \cdots X_n)^4/n^4] < \infty$を示す.
まず
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] = \frac{1}{n^4} \sum_{i_1=1}^n \sum_{i_2=1}^n \sum_{i_3=1}^n \sum_{i_4=1}^n E[X_{i_1}X_{i_2}X_{i_3}X_{i_4}]$$
であって,i.i.d.だから,random variableたちの少なくとも１つが他のすべてのrandom variableと異なるとき$E[X_{i_1}X_{i_2}X_{i_3}X_{i_4}] = 0$. したがって,上の式で$0$出ない項は$E[X_i^4]$あるいは$E[X_i^2X_j^2] \ (i \neq j)$という形をしている. $E[X_i^4]$となる$i$は$n$通りで,$E[X_i^2X_j^2] \ (i \neq j)$となる$i, j$の組み合わせは$3n(n-1)$通りある.以上から
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] = \frac{nE[X_1^4] + 3n(n-1)E[X_1^2 X_2^2]}{n^4}$$
が成立する.$xy \leq (x^2 + y^2)/2$に$x=X_1^2, y=X_2^2$を代入して$X_1^2X_2^2 \leq X_1^4+X_2^4$,expectationをとって$E[X_2^4] = E[X_1^4]$を考えれば$E[X_1^2X_2^2] \leq E[X_1^4]$が成立する.ゆえに
$$E\left[\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] \leq \frac{3n^2 E[X_1^4]}{n^4}=\frac{3E[X_1^4]}{n^2}$$
したがって
$$E\left[\sum_{n=1}^\infty\frac{(X_1 + \cdots +X_n)^4}{n^4} \right] \leq 3E[X_1^4]\sum_{n=1}^\infty \frac{1}{n^2} < \infty$$
ゆえに$(X_1 + \cdots + X_n)^4/ n^4$は確率1で$0$に収束し,$(X_1 + \cdots +X_n)/n$もそうである.これがStrong law of large numbersの主張するところだった.
$E[X_i] \neq 0$である場合,$(X_1 + \cdots + X_n - nE[X_1])/n$が$0$にa.s.収束することは$(X_1 + \cdots + X_n) / n$が$E[X_1]$にa.s.収束することだから,成立.

$E[X^4]<\infty$の仮定を外した場合の証明は省略する.

18-3 The Central Limit Theorem (中心極限定理)

Theorem 18-2 Central Limit Theorem, CLT

$X_1, ...$がi.i.d.で,そのexpectationとvarianceをそれぞれ$\mu< \infty, \sigma^2<\infty$とする.$S_n = X_1 + \cdots +X_n$とすると,
$$\frac{S_n - n\mu}{\sigma\sqrt{n}}$$
が$N(0, 1)$にdistribution convergenceする.

proof.

簡単のため$\mu = 0, \sigma^2 = 1$とする. 1,2次のmomentが有限であることから,$\phi_{X_1}(t)$は$0$において２回微分可能である.
$$\phi_X(t) = 1 - t^2/2 + o(t^2)$$
と書ける.$S_n /\sqrt{n}$のcharacteristic functionは
$$(\phi_X(t/\sqrt{n}))^n = (1 - t^2/2n + o(t^2/n))^n$$
という形をしていて,$t$を固定して$n\rightarrow \infty$の極限は$e^{-t^2/2}$である.これは$N(0,1)$のcharacteristic function$\phi_Z$に等しい.$\phi_{S_n /\sqrt{n}}(t) \rightarrow \phi_Z(t) \forall t$から,たしかにdistribution convergenceが言えた.

CLTは$S_n/$のPDFはCDFについて何も言っていないが,以下の2つの命題が成り立つ.
(a)

$\int|\phi_{X_1}(t)|^r dt < \infty$が成立する$r$があるとき,$S_n$は$n\geq r$で連続で
$(S_n-\mu_n)/(\sigma\sqrt{n})$のPDF$f_n$は$N(0,1)$のPDFに一様収束($\Rightarrow$各点収束)する.すなわち
$$\lim_n \sup_z |f_n(z) - \frac{1}{\sqrt{2\pi}} e^{-z^2/2}|=0$$
である.

(b)

$a, h$を定数,$k$を整数として,$X_i$が$a+hk$という値を取り,$E[X]=0, var[X]=1$とする. $z=(na+kh)/\sqrt{n}$という形の$z$に,
$$\lim \frac{\sqrt{n}}{h} P(S_n=z) = \frac{1}{2\pi}e^{-z^2/2}$$
である.

19-2. The Chernoff Bound

$X, X_1, ...$はi.i.d.で,$S_n = X_1 +\cdots X_n$とする.$E[X]=0$とする. (weak) law of large numbers から, $P(S_n \geq na) \rightarrow 0$が任意の$a>0$で成立.この収束を上下から押さえる関数を与えたい.

19-2.1 Upper Bound

$M(s) = E[e^{sX}]$として,$M(s) <\infty$が$s \in [0, c], c>0$で成り立つとする.
$M_{S_n}(s) = E[e^{s(X_1 +\cdots +X_n)}]=(M(s))^n$. 任意の$s>0$にMarkov inequalityを使って,
$$P(S_n \geq na) = P(e^{sS_n}\geq e^{nsa})\leq e^{nsa}E[e^{sS_n}] = e^{-nsa}(M(s))^n$$
($c <s$では右辺が$\infty$になってしまうが不等号自体は成立する)
$P(S_n \geq a)$が$n$とともに指数的に減少することがわかったが,$s$を操作してより狭い境界を与える.

Theorem 19-2 (Chernooff Upper Bound) (証明略)

ある$s>0, a>0$で$E[e^{sX}] < \infty$ならば,
$$P(S_n\geq na) \leq \exp[n\underline{\sup_{s\geq 0} (sa-\log M(s))}_{\phi(a)}]$$

$s=0$では$sa-\log M(s) = 0 - \log 1 = 0$
また
$$\frac{d}{ds} (sa-\log M(s))|_{s=0} = a - \frac{1}{M(s)} \frac{d}{ds} M(s)|_{s=0}=a - 1E[X] = a> 0$$
$sa-\log M(s)$は$s=0$で$0$をとり,微分係数は正だから,十分小さい$s>$で正の値を取る. $\phi(a)>0$であって,$a>0$を固定すると$P(S_n \geq na)$は$n$によって指数的に減少する.

Example

$X \sim N(0, 1)$について,$M(s) = e^{s^2/2}$. したがって$sa - \log M(s)=sa-s^2/2$ これの最小値は$\phi(a) = a^2/2$.これは
$$P(X \geq a) \leq e^{-a^2/2}$$
を与える.

19-2.2 Lower Bound

Assumption 19-1.

(i) $\forall s \ M(s) = E[^sX] < \infty$
(ii) random variable $X$はcontinuous で, PDFは$f_X$
(iii) $X$は有限の上限,下限を持たない.すなわち$0 < F_X(x) < 1, \forall x\in \mathbb{R}$

Theorem 19-3 (Chernoff Lower Bound)

Assumption 1のもとで,任意の$a > 0$に
$$\lim_{n\rightarrow \infty} \frac{1}{n} \log P(S_n \geq na) = -\phi(a)$$

MIT OCW, Fundamentals of Probability 18日目 確率変数の収束の関係性

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 17. Convergence of Random Variables

• Lecture 17. Convergence of Random Variables
  • 3. The Hierarchy of Convergence Concepts
    • • Theorem 17-2
    • 3.1 Convergence Almost Surely Versus in Probability
    • 3.2 Convergence in Probability Versus in Distribution
    • 3.3 Convergence in Distributuion Versus Characteristic Functions
      • Theorem 17-3 Countinuity of inverse transfroms (証明略)
      • Theorem 17-4 Continuity of inverse transforms (証明略)

3. The Hierarchy of Convergence Concepts

Theorem 17-2

$$[X_n \rightarrow^{\text{a.s.}} X] \Rightarrow [X_n \rightarrow^{\text{i.p.}} X] \Rightarrow [X_n \rightarrow^\text{d}X] \Rightarrow [\phi_{X_n}(t) \rightarrow \phi_X(t), \forall t]$$
最初の２つの矢印の両辺では,すべてが同じprobability space上のrandom variableと仮定している.

proof.

(a) $[X_n \rightarrow^{\text{a.s.}} X] \Rightarrow [X_n \rightarrow^\text{i.p.} X]$
$\epsilon > 0$を固定して,$Y_n = \epsilon I_{\{|X_n-X|\geq \epsilon\}}$とする.$X_n \rightarrow^{\text{i.p.}} X$ならば$Y_n \rightarrow^\text{a.s.} 0$であって,$Y_n$が定数$\epsilon$で抑えられることを考えればDCTより
$\lim_n E[Y_n] =\lim_n\int_{\Omega} \epsilon I_{\{|X_n-X|\geq \epsilon\}} = \int_\Omega \lim_n \epsilon I_{|X_n-X|\geq \epsilon\}} 0$ (測度1で$\lim Y_n(\omega) =0$)
一方で$E[Y_n] = \epsilon P(|X_n-X| \geq \epsilon)$から,$P(|X_n-X|\geq \epsilon) \rightarrow 0$が任意の$\epsilon$に言えて,したがって$X_n \rightarrow^{\text{i.p.}} X$

(b) $[X_n \rightarrow^{\text{i.p.}} X] \Rightarrow [X_n \rightarrow^\text{d} X]$ (略)
(c) $[X_n \rightarrow^d X] \Rightarrow [\phi_{X_n}(t) \rightarrow \phi_X(t), \forall t]$
$X_n \rightarrow^d X$のもとで,Theorem 17-1から,あるprobability space上の$Y, \{Y_n\}$が有って,$Y_n \rightarrow^{\text{a.s.}} Y$である. 任意の$t \in \mathbb{R}$に
$$\lim \phi_{X_n} (t) = \lim \phi_{Y_n} (t) = \lim E[e^{itY_n}] =_{(1)} E[\lim e^{it Y_n}]=E[e^{itY}] = \phi_Y(t) = \phi_X(t)$$
(1): DCTと$Y_n \rightarrow^\text{a.s.}Y$ (Lec. 16, 4(f))

それぞれの矢印の逆命題を議論する.

3.1 Convergence Almost Surely Versus in Probability

$[X_n \rightarrow^\text{d} X] \nRightarrow [X_n \rightarrow^\text{i.p.}X]$
$X_n(\Omega)=\{0, 1\}, P(X_n = 1) = 1/n$,また$\{X_n\}$はindependentとする.このとき$X_n\rightarrow^\text{i.p.} 0$である.一方Borel-cantelliの補題から,$P(\{X_n = 1, \text{i.o.}\})=1$ ($\ \ \sum 1/n = \infty$) ゆえにほとんどすべての$\omega$で$X_n(\omega)$は$0$に収束しない.
しかし,より弱い命題は成立する.すなわち,$X_n \rightarrow^\text{i.p.} X$のときには,部分列$\{X_{n_k}\}$があって,$\lim_k X_{n_k} =X \ \ \text{a.s.}$である. (証明略)
例えば上の例で$n_k = k^2$とすると$X_{n_k} \rightarrow^\text{i.p.} 0$であって,Borel-Cantelliの補題から$P(\{X_n=1, \text{i.o.}\})=0$ $(\sum 1/n^2 < \infty)$だから,たしかに$X_n \rightarrow^\text{a.s.} X$.

3.2 Convergence in Probability Versus in Distribution

$[X_n \rightarrow^\text{d} X] \nRightarrow [X_n \rightarrow^\text{i.p.} X]$
$X, X_n$定数でないi.i.d.とする.このとき明らかに$X_n \rightarrow^\text{d} X$であって,一方$\epsilon$を固定して$P(|X_n-X|\geq \epsilon)$は$n$に関係なく確定した非負実数値を取りうる.すなわち$X_n$は$X$にconverge in probability しない.
ただし$[X_n \rightarrow^\text{d} c] \Rightarrow [X_n \rightarrow^\text{i.p.} c]$である.(証明略)

3.3 Convergence in Distributuion Versus Characteristic Functions

最後に,Theorem 17-2の最後の矢印の逆は必ず成立する.つまり同値関係である.以下の定理は,characteristic functionが似ているrandom variableはdistributionも似ていると主張する.

Theorem 17-3 Countinuity of inverse transfroms (証明略)

$X, X_n$はrandom varirableとする.
$$[\phi_{X_n} (t) \rightarrow \phi_X(t), \forall t] \Rightarrow [X_n \rightarrow^d X]$$

さらに,
(i) characteristic functionたち$\phi_{X_n}$が$\phi_X$に各点収束し
(ii) さらにその極限があるrandom variableのcharacteristic functionである
という命題は非常に便利である.(i)のもとで(ii)が成り立つ条件をTheorem 17-4は主張する.

Theorem 17-4 Continuity of inverse transforms (証明略)

$X_n$はrandom variableで,$\phi_{X_n}$をそのcharacteristic functionとする.$\phi(t) = \lim \phi_{X_n}(t) \forall t$つまり各点収束極限を$\phi_X$とすると,以下のどちらかが成り立つ.
(i) $\phi$は$0$で非連続であり,$X_n$はconverge in distribution しない
(ii) $\phi$は$0$で連続であり,random variable $X$があって,そのcharacteristic functionは$\phi$, さらに$X_n \rightarrow^d X$である.

MIT OCW, Fundamentals of Probability 17日目 確率変数の様々な収束

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 17. Convergence of Random Variables

• Lecture 17. Convergence of Random Variables
  • 1. Definitions
    • 1.1 Almost Sure Convergence (概収束)
      • Definition 17-1
    • 1.2 Convergence in Distribution (分布収束)
      • Definition 17-2
    • 1.3 Convergence in Probability (確率収束)
      • Definition 17-3
  • 2. Convergence in Distribution
    • • Theorem 17-1 (証明略)

1. Definitions

1.1 Almost Sure Convergence (概収束)

Definition 17-1

$X_n$ が$X$にalmost surely converge (概収束)する
$\Leftrightarrow P(A)=1 \text{なる } A \subset \Omega$があって,
$$\lim_n X_n(\omega) = X(\omega) \ \ \forall \omega \in A \text{ つまり各点収束}$$
またこのとき$X_n \rightarrow^{\text{a.s.}}X$と書く.

このとき$X_n, X$は必ず同じprobability spaceのrandom variableでなければならない. さらに,$X_n$たちは一般にhighly dependentである.a.s. convergenceが現れる状況は以下の２つである.
(a)

確率的試行を何度も繰り返すとする.$n$回目の試行に,$Z_n \geq 0$というrandom variableを関連付ける(例えば$n$日目の収入). このとき$X_n = \sum_{i=1}^n Z_n$とすると$n$日目までの収入の合計であって,$X = \sum_{k=1}^\infty X_k$は生涯の収入と考えることが出来る. $X$は$\overline{\mathbb{R}}$でうまく定義されている.

(b)

あるrandom variable$Y$と,可測関数$g_n, g$によって作られる様々なrandom variable$X_n = g_n(Y), X=g(Y)$があって,$\lim_n g_n(y) = g(y)$が任意の$y \in \mathbb{R}$に成立するとき$X_n \rightarrow^{\text{a.s.}} X$である.例えば$g_n(y)=y+y^2/n \rightarrow g(y) =y$.よって
$$Y+Y^2/n \rightarrow^{\text{a.s.}} Y$$

$X_n \rightarrow^{\text{a.s.}} X$であるとき,dominated convergence theorem(優収束定理)から,
$$\phi_{X_n}(t) \rightarrow \phi_X(t)$$
である.一方
$$E[X_n] \rightarrow E[X]$$
は一般には成り立たない.例えば$U$を$[0,1]$上の一様分布として,
$$X_n = \begin{cases} n \ \ \ &\text{if } U \leq 1/n \\ 0 &\text{if } U > 1/n\end{cases}$$
とすると
$$\lim E[X_n] = \lim nP(U \leq 1/n) = 1$$
一方,$X_n \rightarrow^{\text{a.s}} 0$で,$E[X]=0$

1.2 Convergence in Distribution (分布収束)

Definition 17-2

$X, X_n$をrandom variableとし,CDFをそれぞれ$F, F_n$とする.$X_n$が$X$にconverge in distributionする
$\Leftrightarrow$
$$\forall x \in \mathbb{R}, \text{ where }F \text{ is continuous,} \ \ \ \lim_{n\rightarrow \infty} F_n(x) = F(x)$$
またこのとき$X_n \rightarrow^d X$と書く.

重要な性質として,
(a)

$P(X=x) = 0 \Leftrightarrow F$は$x$で連続

(b)

$X_n = 1/n$,また$X=0 \ \ \text{a.s.}$とすると$F_{X_n}(0) = P(X_n \leq 0) = 0$だが,$F_X(0) = 1$である.また,$0$で$F$は非連続だから,連続点のみを考えれば$X_n \rightarrow^d X$.より一般に,$X_n = a_n$また確率1で$X=a$で,$a_n \rightarrow 1$ならば,$X_n \rightarrow^d X$である.
よってconvergence in distributionは実数の収束とconsistent.

(c)

この定義は,random variableたちのmarginal distributionだけを考えていて,異なったprobability spaceにおけるrandom variableについても,cenvergence in distributionは定義されている.

(d)

$Y$がcontinuous random variableで,PDFが$0$において対称とする.$X_n = (-1)^n Y$とすると,$X_n$は全て同じdistributionを持っていて,$X_n \rightarrow^d Y$.しかしほとんどすべての$\omega$で,$X_n(\omega)$は$X(\omega)$に収束しない.

(e)

random variableのdistributionがparametric(例えば,$X_n=e^{\lambda_n}$であるとき)かつそのparameterが収束して,その収束先によって$X$を定義するとき$(\lambda \rightarrow \lambda, X=e^{\lambda})$,$X_n \rightarrow^d X$である.

(f)

discrete random variableの列がcontinuous random variableにconverge in distributionすることがある.例えば$Y_n$が$\{1, ..., n\}$でuniformで,$X_n = Y_n/n$とすると,$X_n$は$[0, 1]$上のuniform random variableにconverge in distributionする.

(g)

continuous random variableの列がdiscrete random variableにconverge in distributionすることがある.例えば$X_n$が$[0, 1/n]$でuniformなら$X_n \rightarrow^d 0$.

(h)

$X$と$X_n$が連続でも,$X_n \rightarrow^d X$だからといってPDFたちが連続であるとは限らない.

(i)

$X, X_n$が整数値を取って,$X_n \rightarrow^d X$ならば,PMFもまた$p_{X_n}(k)\rightarrow p_X(k)$と各点収束する.

1.3 Convergence in Probability (確率収束)

Definition 17-3

(a) 必ずしも同じprobability spaceのrandom variable列でない$\{X_n\}$が$c \in \mathbb{R}$にconverge in probabilityする
$\Leftrightarrow$
$$\forall \epsilon > 0 \ \ \ \lim_{n\rightarrow \infty} P(|X_n-c|\geq \epsilon) = 0$$
このとき$X_n \rightarrow^{\text{i.p.}} c$と書く.
(b) $X, \{X_n\}$は同じprobability spaceのrandom variableたちとする. $X_n - X \rightarrow^{\text{i.p.}} 0$であるとき,$X_n$は$X$にconverge in probabilityするといい,$X_n \rightarrow^{\text{i.p.}} X$と書く.

また重要な性質に
(b)

$X_n \rightarrow^{\text{i.p.}} c$というのは,直感的には,$n$が増加するに従ってほとんどすべてのprobability massが$c$の周りの小さな区間に集まってくるということである. 一方$n$を固定するとその小さな区間からはみ出るprobability massがあってそれはslowly decaying tailをもつ(?). このようなtailはexpected valueに大きな影響が有る. よってconvergence in probability は極限のexpected valueを知るのには役立たない.

(c)

$X_n \rightarrow^{\text{i.p.}} X, Y_n \rightarrow^{\text{i.p.}} Y$で,全てが同じprobability space上のrandom variableなら$(X_n + Y_n) \rightarrow^{\text{i.p.}} (X+Y)$である.

2. Convergence in Distribution

convergence in distributionとalmost sure convergenceの関係を詳しく見ることで,convergence in distributionの意味を把握する.

Theorem 17-1 (証明略)

$X_n \rightarrow^d X$なら,あるprobability spaceと,以下を満たすその上のrandom variable$Y, Y_n$が存在する.
(a) 任意の$n$に$X_n$と$Y_n$が同じCDFをもち,$X$と$Y$も同じCDFを持つ.
(b) $Y_n \rightarrow^{\text{a.s.}} Y$

convergence in distributionでは,random variable $X_n$たちが独立であるか否かは問題ではなく,同じprobability space上で定義されている必要もない. 一方almost sure convergenceでは,random variableたちの強いdependenceが暗示されている. Theorem 17-1はmarginal distributionの保存を言っているが,$X_n$たちの間の特別な形のdependenceを導入していて,結果almost sure convergenceが現れる.
このdependenceは$Y_n, Y$をcommon random number generatorを使って希望する分布上に定義する.例えば$U$を$[0, 1]$上のuniformly distrubutionとする.
すべてのCDFたちが連続で狭義単調増加するとき$Y_n = F^{-1}_{X_n}(U), F^{-1}_X(U)$とすると,(a)を満たしている.またこのとき$Y_n \rightarrow^{\text{a.s.}} Y$である.これはsection 1.1(b)からわかる.

MIT OCW, Fundamentals of Probability 16日目 特性関数

Lecture 16. Characteristic Functions

1. Equivalence of the Tree Definitions of the Multivariate Normal Distribution

• Lecture 16. Characteristic Functions
  • 1. Equivalence of the Tree Definitions of the Multivariate Normal Distribution
    • 1.1 The definitions
      • Definition 16-1
      • Definition 16-2
      • Definition 16-3
  • 2. Proof of Equivalence
    • • Theorem 15-1(再掲)
      • Theorem 16-1
  • 3. Whitening of a Sequence of Normal Random Variables
  • 4. Introduction to Characteristic Functions
    • • Theorem 16-2

1.1 The definitions

Lec.15の定義を再掲する.

Definition 16-1

$\mathbf{X}$がnondegenerate (multivariate) normal distributionをもつ
$\Leftrightarrow$
$$f_X(\mathbf{x}) = \frac{1}{\sqrt{(2\pi)^n |det V|}} \exp\left[-\frac{\mathbf{x}-\mu) V^{-1} (\mathbf{x}-\mu)^T}{2} \right]$$
と,joint PDFが書ける.ここで$\mu$は実ベクトルで,$V$はpositive definateである.

Definition 16-2

$\mathbf{X}$が(multivariate) normal distributionをもつ
$\Leftrightarrow$
$$\mathbf{X} = D\mathbf{W} + \mu$$
と,行列$D$と実ベクトル$\mu$,各要素が$N(0, 1)$に従う確率ベクトル$\mathbf{W}$で書ける.

Definition 16-3

$\mathbf{X}$が(multivariate) normal distributionをもつ
$\Leftrightarrow$ 任意の実ベクトル$\mathbf{a}$について,$\mathbf{a}^T \mathbf{X}$がnormalである.

これらの定義が同値であることを証明する.

2. Proof of Equivalence

Lec.15で, def 16-2であればdef 16-3が成立することを学んだ.

Theorem 15-1(再掲)

def 16-2の意味で$\mathbf{X} = (X_1, ..., X_n)$がmultivariate normalで,$\mu = (\mu_1, ...,\mu_n)$とすると
(d) $|D| \neq 0$であるとき,$V= DD^T = cov(X, X)$によってdef 16-1の意味でもnondegenerate multivariate normalである.

proof.

$\mu = 0$と仮定する. $X = DW$で$D^{-1}$が存在するとき,Lec.10 2-1から
$$f_X(x) = \frac{f_W(D^{-1}w)}{|\det D|}$$
と書ける.$W_i \sim N(0, 1)$でi.i.d.だから
$$f_W(\mathbb{w}) = \frac{1}{\sqrt{(2\pi)^n}}\exp \left[-\frac{1}{2} \mathbf{w^Tw} \right]$$
で,したがって
$$f_X(\mathbf{x}) = \frac{1}{\sqrt{(2\pi)^n |\det DD^T|}}\exp(-\frac{1}{2}(D^{-1})^TD^{-1}\mathbf{x})$$

そこで,

Theorem 16-1

(a) $\mathbf{X}$がdef 16-1を満たすとき, def 16-2も満たす
(b) $\mathbf{X}$がdef 16-3を満たすとき, def 16-2も満たす と示せば良い

proof.

(a)
仮定のもとで,$V$はpositive definateなので,$D^2 = V$となるsymmetricな$D$があって(Spectral Decomposition), $(\det D)^2 = \det(D^2) = \det(V) >0$から, $D$は可逆. $\mathbf{W} = D^{-1} (\mathbf{X}-\mu)$とすると,$E[\mathbf{W}]=0$で,さらに
$$\begin{aligned} cov(W, W) &= E[D^{-1}(\mathbf{X}-\mu)(\mathbf{X}-\mu)^TD^{-1}] \\ &= D^{-1}E[(\mathbf{X}-\mu)(\mathbf{X}-\mu)^T]D^{-1} \\ &=D^{-1}VD^{-1} = I \end{aligned}$$
したがって$W_i$たちはdef 16-1の意味でnormalでかつcovariance matrixが単位行列だからindependentである.
(b)
仮定のもとで,$V=cov(\mathbf{X}, \mathbf{X})$として,これは対称行列だから

3. Whitening of a Sequence of Normal Random Variables

$\mathbf{X}$がmultivariate normal vectorとして,基底変換によって$\mathbf{W} = (W_1, ..., W_n)$をつくるとき,様々な作り方が考えられるが,
$$\begin{aligned} W_1 &= X_1 \\ W_2 &= X_2 - E[X_2|X_1] \\ W_3 &=X_3 - E[X_3|X_1, X_2] \\ \vdots \\ W_n &= X_n - E[X_n | X_1, ..., X_{n-1}] \end{aligned}$$
とすることが出来る.ただし
(a) $W_i$はそれぞれ, $(X_1, ..., X_{i-1})$をもとに$X_i$から得られる新しい情報と考えることができる.$W_i$たちをinnovationsという.
(b) conditional expectationは線形写像だから,$W_i$は$X_i$の線形写像と考えることが出来る. 下三角行列$L$を使って$\mathbf{W} = L \mathbf{X}$と書ける.これは$W_i$が$X_1, ..., X_{i}$によって決定されるということであって,これを$\mathbf{X}$から$\mathbf{W}$への変換はcausalであるという.また,$L^{-1}$もまた下三角行列だから,causally invertibleという.この関係をwhitening filterと呼ぶことが有る.
(c) $W_i$たちはそれぞれ独立で,これは$E[(X-E[X|Y)])Y] = 0$から言える. またここから$W_i$と$X_1, ..., X_{i-1}$はuncorrelatedであることが言えて,さらに$W_1, ...,W_{i-1}$ともuncorrrelated.normalだからuncorrelated => independent. varianceが0でなければ,varianceが1となるように出来る.
(d) $W$のcovariance matrix $B$は対角行列で,$cov(X, X) = L^{-1}B(L^{-1})^T$. $B$を$(L^{-1}B^{1/2}) (B^{1/2} (L^{-1})^T)$と,下三角行列と上三角行列に分解することをCholesky factorizationという.

4. Introduction to Characteristic Functions

moment generating function $M_X(s)$をすでに定義したが,$s\neq 0 \Rightarrow M_X(s) = \infty$のような場合には意味を持たない(Cauchy distributionを思い出せ). そこで$s$を複素数$s=it, i=\sqrt{-1}, t \in \mathbb{R}$と考えて,
$$\phi_X(t) = E[e^{itX}]$$
と定める. $X$がPDF $f$をもつcontinuous random variableとすると,
$$\phi_X(t) = \int e^{itx} f(x) dx$$
が成立する.$e^{itX}$はcomplex-value random variableであるが,三角関数での表示を思い出せば
$$\phi_X(t) = E[\cos(tX)] + iE[\sin(tX)]$$
として計算できる.さらに
(a) $|e^{itX}| \leq 1$が任意の$t$に成立するから,$\phi_X(t)$は必ず定義されて,しかも$|\phi_X(t)|\leq 1$である.
(b) moment generating fucntionの主要な性質はcharacteristic functionと共通する.

Theorem 16-2

(a) $Y = aX + b$とすると,$\phi_Y(t) = e^{itb}\phi_X(at)$
(b) $X, Y$がindependentなら$\phi_{X+Y}(t) = \phi_X(t)\phi_Y(t)$
(c) $X, Y$がindependentで,$Z$が確率$p$で$X$に等しく,確率$1-p$で$Y$に等しいとき,
$$\phi_Z(t) = p\phi_X(t) + (1-p)\phi_Y(t)$$

(c) Inversion theorem 同じcharacteristic functionをもつrandom variableがあるとき,分布も同じ
(d) $\mathbf{X}$がmultivariateなとき$\phi_{\mathbf{X}}(\mathbf{t}) = E[e^{i\mathbf{t}^T \mathbf{X}}]$でcharacteristic functionを定めて,(c)はこれでも成立
(e) $X$がcontinuous でPDFが$f_X$とすると,
$$f_X(x) = \frac{1}{2\pi} \lim_{T \rightarrow \infty} \int^T_{-T} e^{-itx}\phi_X(t)dt$$
が$_X$が微分可能な点$x$で成立する.
(f) dominated convergence theoremを,定数関数1に支配される複素数の実部と仮部にそれぞれ使って,
$X_n \rightarrow X a.s.$がなら,任意の$t \in \mathbb{R}$に
$$\lim \phi_{X_n} (t) = \lim E[e^{itX_n}] = E [\lim e^{itX_n}] = E[e^{itX}]=\lim \phi_X(t)$$
(g) $E[|X|^k] < \infty$ならば
$$\frac{d^k}{dt^k} \phi_X(t) |_{t=0} = i^k E[X^k]$$

MIT OCW, Fundamentals of Probability 15日目 モーメント母関数2

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.
[TOC]

Lecture 14. Moment Generating Functions

2. Sum of a Random Number of Independent Random Variables

$X_1, X_2, ...$をi.i.d. なrandom variableの列とする.meanは$\mu$, varianceは$\sigma^2$とする.$N$を非負整数をとる別のrandom variableとする. $Y = \sum_{I=1}^N X_i$とし,$Y$の様々な統計量を考える.
まず
$$E[Y] = E[E[Y|N]] = E[N\mu] = E[N]E[X]$$
さらに, law of total varianceによって
$$\begin{aligned} var[Y] &= E[var(Y|N)] + var(E[Y|N]) \\ &= E[N\sigma^2] + var(N\mu) \\ &= E[N]\sigma^2 + \mu^2 var(N) \end{aligned}$$
また$E[\exp(sY) | N=n] = M^n_X(s) =\exp(n\log M_X(s))$だから,
$$M_Y(s) = \sum \exp(n\log M_X(s)) P(N=n) = M_N(\log M_X(s))$$

Example

$X_i$はexp($\lambda$)に従う独立なrandom variableとする.また$N \sim geo(p)$とすると
$$M_Y(s) = \frac{e^{\log M_X(s)}p}{1-e^{\log M_X(s)}(1-p)} = \frac{p\lambda/(\lambda-s)}{1-\lambda(1-p)/(\lambda-s)} = \frac{\lambda p}{\lambda p - s}$$
$\because M_N(s) = \sum_{n} p(1-p)^{n-1} e^{sn}$
このように,$Y_M(s)$はパラメータ$\lambda p$のexponential random variableのmoment generating functionと一致する.
cf.

$X \sim exp(\lambda)$とすると,
$M_X(s) = \int^{\infty}_0 e^{sx} \lambda e^{-\lambda x} = \lambda \int^{\infty}_0 e^{x(s-\lambda)} = \lambda[\frac{1}{s-\lambda} e^{x(s-\lambda)}]^\infty_0 = \frac{\lambda}{\lambda - s}$

inversion theoremから$Y \sim exp(\lambda p)$.exponential random variableの有限和はexponential出ないことを考えると驚くべき結果である. 後にPoisson processの視点から直感的な説明を与える.

3. Transfroms Associated wtih Joint Distributions

$X, Y$にjoint distribution(joint PDF)があるとき,$M_X(s)$と$M_Y(s)$が導ける.これはmarginal distribution の変換で，もう一方のrandom variableとの関係性を保存しない. $X, Y$の関係を保存する変換を述べる. $X_1, ..., X_n$について,$s_1, ..., s_n$を実数のパラメータとすると,associated multivariate transformを$n$変数関数
$$M_{X_1, ..., X_n}(s_1, ..., s_n) = E[e^{s_1X_1 + ... +s_nX_n)}]$$
と定める.