MIT OCW, Discrete Stochastic Processes 01日目

Robert Gallager. 6.262 Discrete Stochastic Processes. Spring 2011. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

Lecture videoを要約していく.

• • Lecture 1
    • モデルを作るときに現れる重要な問題
      • 1. – 完全なモデルは存在しない
      • 2. – その数学的モデルの解が現実で意味を持つか
    • Stochastic Processとは？
      • このコースで学ぶprocessたち
    • Kormogorovの公理
    • Eventの独立性
    • Random Variable
  • Lecture 2. 確率論の復習
    • Expectations
      • example: indicator random variable
    • multiple random variables
      • IID random variables
      • Sample Average
    • The Bernoulli Process
  • Assignment 1. Problem set 1.
    • • Exercise 1.3
      • Exercise 1.9
      • Exercise 1.13
      • Exercise 1.20
      • Exercise 1.26

Lecture 1

well-posed problemを解くのは簡単だが,現実にある現象をモデル化してwell-posed problemに落とし込むのは難しい. このコースでは現実世界での確率と確率の理論を学んだ後discrete processがなんであるかを学び,数あるdiscrete processの内いくつかを学ぶ.
確率論がどこで役に立つか–どこでも役に立つのだが,いくつか例を挙げる
Kormogrovの確率の公理がどのように役に立っているか
確率論の復習

モデルを作るときに現れる重要な問題

1. – 完全なモデルは存在しない

完璧なモデルというのは存在しないが,現実の問題をより詳細に記述するモデル–より複雑なモデルを構築することは出来る. 一方モデルが複雑になるほど理解しづらくなってしまうので,モデルの複雑さと理解のしやすさの間でバランスを取ることが重要になってくる. Whiteheadの警句 “Seek simplicity and distrust it.” は,我々は単純なモデルを正しいと思い込みがちなので,単純なモデルがうまく言っているように見えても,よく検証しなければならないと主張する.

2. – その数学的モデルの解が現実で意味を持つか

確率のモデルの正当性はKormogorvの確率の公理に従っているかで決まる.

Stochastic Processとは？

確率モデルの一種で,sample pointが時間を変数とする関数であるものをstochastic process(確率過程)という. このときあるsample pointは時刻を添字とする確率変数の列の,その時刻における1点の現れと考えることが出来る. この確率変数列の全ての元が離散確率変数であるとき特にdiscrete stochastic processという.

このコースで学ぶprocessたち

• counting process
• Poisson process
• renewal process
• Markov process
• random walkとmartingale

以下はほとんどFundamentals of probabilityでやったが,念の為復習

Kormogorovの公理

$\Omega$はある集合で,$\mathcal{F} \subset 2^{\Omega}$がeventの集合
$\Leftrightarrow$

(1) $\Omega \in \mathcal{F}$
(2) $A_1, A_2, ...\in \mathcal{F} \Rightarrow \cup A_i \in \mathcal{F}$
(3) $A \in \mathcal{F} \Rightarrow A^C \in \mathcal{F}$
つまり$\mathcal{F}$が$\Omega$の$\sigma$-algebraであるということ.

$P$が$\mathcal{F}$に確率を割り当てる($(\Omega, \mathcal{F})$のprobability measureである)
$\Leftrightarrow$

(1) $P(\Omega)=1$
(2) $A \in \mathcal{F} \Rightarrow P(A) \geq 0$
(3) $\{A_i\} \subset \mathcal{F}$が互いに素なら$P(\cup A_i) = \sum P(A_i)$

Eventの独立性

$A_1, A_2 \in \mathcal{F}$がindependent
$\Leftrightarrow P(A_1 \cap A_2) = P(A_1) P(A_2)$

仮に$A_1\in \mathcal{F_1}$が赤いサイコロをふって出る目が1であるというeventで,$A_2 \in \mathcal{F_2}$が白いサイコロをふって出る目が1であるというeventとすると,$A_1 \cap A_2$というのは$(\Omega_1 \times \Omega_2,\mathcal{F_1} \times \mathcal{F}_2, P_1\times P_2)$という新しいprobability spaceがあらわれて,例えば$\Omega_1 \times \Omega_2$は単に$\{1, ... 6\}^2$といデカルト積(とりあえずサイコロの場合はそう).
一方ふるサイコロが両方とも白いとき(区別できないとき)には話は複雑になる.$\Omega_1 \times \Omega_2 = \{(1,1), (1,2), ...,(1,6), (2, 2), (2, 3), ...,(2, 6), (3,3),...,(6,6) \}$となって,$|\Omega_1\times\Omega_2|=21$これはサイコロが区別できるときとは異なる集合である. これは2つのeventを，区別できない状況で組み合わせるときに，組み合わせたeventの確率をどう評価するかという重要な問題の最も簡単な例と言える. この話題はまたあとで扱う.

Random Variable

$X: \Omega \rightarrow \mathbb{R}$が$(\Omega, \mathcal{F}, P)$のrandom variable(r.v., 確率変数)
$\Leftrightarrow \forall r \in \mathbb{R}, \{\omega| X(\omega) \leq r\}\in\mathcal{F} \Leftrightarrow X$は$(\mathcal{F}, \mathcal{B})$-可測$\Leftrightarrow \forall B \in \mathcal{B}. X^{-1}(B)\in \mathcal{F}$

また,$F_X(x) = P(\{\omega| X(\omega) \leq x\})$を$X$のdistributinoという.

Lecture 2. 確率論の復習

Expectations

$X$のexpectation(期待値) $\bar{X} = E[X]$を
$$\begin{aligned} E[X] &= \sum_i a_i p_X(a_i) \ \ \ &\text{for discrete } X \\ E[X] &= \int x f_X (x) dx &\text{for continuous } X \\ E[X] &= \int F^C_X (x) dx &\text{for arbitrary nonegative } X \\ E[X] &= \int^0_{-\infty} F_X(x) dx + \int^\infty_0 F^C_X(x)dx & \text{for arbitrary } X \end{aligned}$$
と定める(上の二つが定義,下の二つが定義から導かれる公式)．
4番目の式の片方の項が$-\infty$,もう一方が$\infty$の場合を考えれば,expectationが定義できないrandom variableが存在することがわかる. 普通$|E[X]|< \infty$のときのみ,$E[X]$が存在するという.
また,$X$のstandard deviation(標準偏差) を$\sigma_X = \sqrt{E[|X-E[X]|^2]}$と定める.
上から3番目の式を,discreteの場合に直感的に正当化する.

figure 1.
fig.1のそれぞれの四角形の面積が$\sum_{i \in \{1,2,3,4\}} a_{i} p_X(a_i)$の各項を表している.$a_0=0$として,$x \in [a_{i-1}, a_{i}]$の$x$軸に垂直な直線と,四角形の重複する部分の長さは$1-F_X(a_i)=F_X^C(A_i)$だから,四角形の面積の和は$\sum_{i \in \{1,2,3,4\}} F^C_X(a_i)$と一致する.

example: indicator random variable

$A \in \mathcal{F}$のindicator random variable $I_A : \Omega \ni \omega \mapsto \begin{cases} 1 \ \ (\omega \in A) \\ 0 \ \ (\omega \notin A) \end{cases}$
について$PI_A (0) = 1 - Pr(A), PI_A(1) = Pr(A)$だから,$E[I_A]=Pr(A)$
$\sigma_{I_A}=\sqrt{Pr(A) (1-Pr(A))^2+(1-Pr(A))(0-Pr(A))^2}=\sqrt{Pr(A)(1-Pr(A))}$

multiple random variables

random variables $X, Y$についてjoint distribution function
$F_{XY} (x, y) = Pr(\{\omega| X(\omega) \leq x\} \cap \{\omega|X(\omega) \leq y\})$が定義できる.これはrandom variableの集合$\{X_i\}$でも動揺に定義できて,$X=(X_1,...,X_n)$がindependentなら
$$F_X(x_1, ..., x_n) = \prod_{m=1}^n F_{X_m}(x_m) \ \ \forall x_1, ...,x_n$$
である.

discrete rv’s $X, Y$について
$$p_{X|Y}(x|y) = \frac{p_{XY}(x,y)}{p_Y(y)} \ \ (\text{if } p_Y(y)\neq0)$$
をconditional probabilityという. $X,Y$がindependentなら

IID random variables

$X_1, ..., X_n$がindependent and identically distributed(IID)
$\Leftrightarrow \forall x_1,...,x_n F_X(x_1,...,x_n)=\prod_{k=1}^n F_{X_1}(x_k)$かつ$\forall x.F_{X_i}(x)=F_{X_1}(x)$
$\Omega=\mathbb{R}$で,その上のr.v. $X$があるとき,i.i.d.として並べて$\mathbb{R}^n$上のr.v. $(X_1,...,X_n)$を考えることが出来る(extended modelという).
($\Omega$がなんであっても$\Omega^n$を考えればいいような気がするが・・・・)

Sample Average

$S_n / n =(X_1 +...+X_n)/n$はある実数に収束して,その極限が,extended modelが現実世界における試行の繰り返しであるとするなら,その結果の平均であるというのが,大数の法則の主張である.
しかし,いかに述べる問題から,正しいモデルが作れないこともある.
1. 現実での試行の列というのは,それぞれが十分似ていなかったり，独立でなかったりして,i.i.d.でモデル化できないかもしれない.
2. もとのモデルが間違っているかもしれない.例えばコイントスが表が出る確率0.5としたが,実際には0.45かもしれない

実験によって得られる結果というのはsample pointであって,確率ではない. extended modelが現実と合致しているときにのみ大数の法則やその関連を使って分布を考えることが出来る.
また，$S_n-n\bar{X}$は平均$0$,分散$n\sigma^2$のr.v.で,$(S_n-n\bar{X})/\sqrt{n}\sigma$は平均0, 分散1. これが$n\rightarrow \infty$で$N(0,1)$に分布収束するというのがcentral limit theorem(CLT, 中心極限定理)の主張である.(characteristic functionの各点収束を示して証明した)

The Bernoulli Process

$p_Y(1)=p>0, p_Y(0)=1-p=q >0$がi.i.d.に並んだ$Y_1, ..., Y_n$があるとき,
$S_n = Y_1 + ... +Y_n$の分布を調べる.この節では$p < 1/2$と約束する.
$(Y_1,...,Y_n) = (\underline{1,...,1}_\text{k個},\underline{0,...,0}_{\text{n-k個}})$となる確率は$p^kq^{n-k}$.$k=0$で最大となり,$k$の増加とともに減少する.
また,$(Y_1,...,Y_n)$のうちちょうど$k$個が$1$,ほかが$0$である場合の数は$\left(\begin{array}{} n \\k \end{array} \right)$個で,それぞれの確率は$p^kq^{n-k}$だから,確率の和は$\left(\begin{array}{} n \\k \end{array} \right)p^kq^{n-k}$.よって
$$p_{S_n}(k) = \left(\begin{array}{} n \\k \end{array} \right)p^kq^{n-k}$$
$k$による増減は,
$$\begin{aligned} \frac{p_{S_n}(k+1)}{p_{S_n}(k)} &= \frac{n!}{(k+1)!(n-k-1)!}\frac{k!(n-k)!}{n!}\frac{p^{k+1}q^{n-k-1}}{p^kq^{n-k}} \\ &= \frac{n-k}{k+1}\frac{p}{q} \end{aligned}$$
だから,$k$の増加とともに狭義単調減少する.
さらに,
$$\frac{p_{S_n}(k+1)}{p_{S_n}(k)} = \begin{cases} < 1 \ \ &\text{for } k \geq pn \\ \sim 1 &\text{for } k < pn < k+1 \\ >1 &\text{for } k+1 < pn \end{cases}$$

(以下CLTの成立の証明が続く)

Assignment 1. Problem set 1.

Exercise 1.3

$A_1, A_2, ... \in \mathcal{F}$はdisjointで,$Pr(A_n)=2^{-n-1},\Omega=\cup A_n$とする.
(a) この過程が確率の公理に反することを示せ
(b) $Pr(\cup_{i\geq 1} A_i)=\sum_{i\geq 1}Pr(A_i)$を$Pr(\cup_{i=1}^n A_i)= \sum_{i=1}^n Pr(A_i)$で置き換えると,上の過程がその公理系を満たすことを示せ
この結果から,countable additivityがfinite additivityよりも強い概念であることがわかる.

答案.

(a)
$$\sum_{i \geq 1} Pr(A_i) = \sum_{n\geq 1} 2^{-n-1} = 1/2 \neq Pr(\cup_{i\geq 1} A_i)=Pr(\Omega)=1$$
よって示せた.
(b)
$\sum_{i=1}^n Pr(A_i)= (1/2)(1-2^{-n})<1$. これと$Pr(\Omega)=1$は矛盾しない.

Exercise 1.9

$X$はr.v.で,distributionは$F_X$とする.以下のr.v.たちのdistributionを与えよ
(a) $X$にIIDなr.v.たちの最大値のr.v.
(b) $X$にIIDなr.v.だちの最小値のr.v.
(c) (a)と(b)の差のr.v. ただし$X$はPDF $f_X$を持つとする.

答案.

(a)
$\max(X_1,...,X_n) \leq x \Leftrightarrow X_1 \leq x \land ...\land X_n \leq x$から
$Pr(\max(X_1,...,X_n)\leq x ) = Pr(X_1 \leq x, ....,X_n\leq x) = Pr(X_1\leq x)...Pr(X_n\leq x)$(独立性)
よって$F_{\max{(X_1,...,X_n)}}(x) = \prod_{i=1}^n F_{X_i}(x) = F_X(x)^n$
(b)
(a)とほとんど同様に,
$F_(\min{(X_1,...,X_n)})=(1-F_X(x))^n$
(c) (模範解答)
求めるr.v. を$R$とする.
$MAX= \max(X_1,...,X_n), MIN=\min(X_1,...,X_n)$とする.
$MAX\leq x \land MIN > y \Leftrightarrow \forall i. y<X_i \leq x$から
$Pr(MAX \leq x, MIN>y) = [F_X(x)-F_Y(y)]^n$.
$$Pr(R\leq r) = \int \frac{\partial Pr(MAX \leq x, MIN >y)}{\partial x} |_{y=x-r}dx$$
$X$がPDF $f_X$を持つことから,これは$\int n f_X(x)[F_X(x)-F_X(x-r)]^{n-1}dx$である.

Exercise 1.13

$X_1,...$はPDF $f_X(x)$をもつr.v.のIIDな無限列とする. $n\geq 2$について,$X_n$をrecord-to-date,すなわち$\forall i< n. X_n > X_i$と定める. IIDの対称性を使って以下の問いに答えよ.
(a) $X_2$がrecord-to-dateである確率を求めよ.
(b) $X_n$がrecord-to-dateである確率を$n$の関数として求めよ
(c) 任意の$m$について,最初の$m$回の試行におけるrecord-to-dateの個数の期待値を求めよ. $m\rightarrow \infty$によって期待値が$\infty$に発散すると示せ.

答案.

(a) $Pr(X_1<X_2)= Pr(X_1>X_1)=1/2$
(b) $X_1 > \max(\cup\{X_i\}\backslash\{X_1\}), X_2 > \max(\cup\{X_i\}\backslash\{X_2\},..., X_n > \max(\cup \{X_i\}\backslash\{X_n\})$
のどれか一つが確立1で成立し,対称性から$Pr(X_n>X_1,...,X_{n-1})=1/n$.
(c) $\underline{1}_{\text{個数}}\cdot (\underline{1/2}_{(2)} + \underline{1/3}_{(3)} + \cdots \underline{1/m}_{m})$ ($(i)$は$X_i$がrecord-to-dateである確率)
$\sum_{i \geq 2} 1/i$が発散することは有名である.
(模範解答では$X_1$は必ずrecord-to-dateになっていた.全件否定からたしかに$X_1$はrecod-to-date)

Exercise 1.20

(a) $X, Y, Z$は確率1/2で1,確率1/2で0をとるbinary rv’sとする. $\{X,Y,Z\}$がdependentだが,それぞれ2つを選ぶとindependentになる例を挙げ,PMF $p_{XYZ}(x,y,z)$を求めよ (hint: もっとも単純な例では,ただ4つのjoint probabilityが正となる)
(b) pairwise independenceは
$$E[\prod_{i=1}^n X_i] = \prod_{i=1}^n E[X_i]$$
の十分条件か.

模範解答.

(a) $Z= (X+Y)_{mod2}$
(b) この例で, $Pr(XYZ=0)=1$.よって十分条件でない.

Exercise 1.26

r.v. $X$はcontinuousで,distributionは$F_X(x)$とする. $Y=F_X(X)$を新たなr.v.として考える.すなわち,$\omega \in \Omega$に,$X(\omega)=x$ならば$Y(\omega)=F_X(x)$ということである. $Y$は$[0, 1]$上でuniformly distributedであることを示せ.

答案.

$F_Y(y) = y\ \ (0\leq y \leq 1)$を言えば良い.
$F_Y(y) = Pr(Y\leq y) = Pr(\{\omega|Y(\omega)\leq y \})=Pr(\{\omega| F_X(X(\omega)) \leq y \})$
$F_X$の単調性から,ある$r$があって,$x \leq r \Rightarrow F_X(x)\leq y$.$r$の最大値(連続性から存在)を$F^{-1}(y)$とすると$F_Y(y) = Pr(X\leq F^{-1}_X(y)) = F_X(F^{-1}_X(y))=y$.