Lecture 10. Expectation Continued

이 포스팅은 Harvard에서 진행된 Joe Blitzstein의 Statics 110 강좌를 기반으로 작성되었습니다.

• 강의 및 자료 링크

Linearity 증명

Let $T = X + Y$, show $E(T) = E(X) + E(Y)$

평균을 구하는 두 가지 방법:
(1) 전부 더해서 나누는 방법
(2) 그룹으로 묶어 가중평균을 구하는 방법

\[\begin{align*} E(X) &= \sum_x{xP(X=x)} = \sum_s{X(s)P\{s\}} \\ E(T) &= \sum_s{(X+Y)(s)P(\{s\})} = \sum_s(X(s)+Y(s))P(\{s\}) \\ &= \sum_sX(s)P(\{s\}) + \sum_sY(s)P(\{s\}) \end{align*}\]

Similarly, $E(cX) = cE(X)$ if $c$ is constant.
극한적인 상황을 가정하여, $X=Y$(종속)라면?
Then, $E(X+Y) = E(2X) = 2E(X) = E(X)+E(Y)$

Negative Binomial Distribution

Definition

parameters $r$, $p$
story indep. $Bern(p)$ trials, #. of failures before the $r$-th success.
PMF $\displaystyle P(X=n) = \binom{n+r-1}{r-1}p^r(1-p)^n, \ n=0, 1, 2, \dots$
성공과 실패가 나열되어 있을 때, 마지막은 항상 ‘성공’으로 끝나야 하고($r$-th success), 그 이전 시행들 중 $r-1$의 성공과 $n$개의 실패는 어떤 순서로 나열되어 있어도 상관 없다.

Expectation

Note: $r=1$일 때, negative binomial distribution은 geometric distribution과 동일하다.

\[\begin{align*} E(X) &= E(X_1 + \dots + X_r), \ X_j \ \text{is number of failures btween (j-1)st and j-th successes;} X_j \sim Geom(p) \\ &= E(X_1) + \dots + E(X_r) \\ &= r \cdot \frac{q}{p} \end{align*}\]

First Success

$X \sim FS(p)$: 첫 번째 성공까지 걸린 횟수
Let $Y = X-1$, then $Y \sim Geom(p)$
$\displaystyle E(X) = E(Y) + 1 = \frac{q}{p} + 1 = \frac{1}{p}$

[Example 1] Putnam

random permutation of $1, 2, \dots, n$, where $n \geqslant 2$,
find #. of local maxima (Ex. “3” / 2 / 1 / 4 / “7” / 5 / “6” → 3)

Let $I_j$ be indicator r.v. of position $j$ having a local max, $1 \leqslant j \leqslant n$.

\[\begin{align*} E(I_j + \dots + I_n) &= E(I_1) + \dots + E(I_n) \\ &= \frac{n-2}{3} + \frac{2}{2} \\ &= \frac{n+1}{3} \end{align*}\]

세 가지 숫자를 나열하는 경우의 수는 6, 그 중 가장 큰 수가 가운데에 올 경우의 수는 2 즉, 확률은 $\frac{1}{3}$

[Example 2] St. Petersberg Paradox

Get $2^X$ dollars, where $X$ is #. of flips of fair coin until first $H$, including the success.

Let $Y = 2^X$ (받는 돈), find $E(Y)$.

\[\begin{align*} E(Y) &= \sum_{k=1}^\infty 2^k \cdot \frac{1}{2^k} \\ &= \sum_{k=1}^\infty 1 \\ &= 1+1+1+ \dots \\ &= \infty \ \text{?} \end{align*}\]

상한 금액이 정해지지 않았담면, 받을 수 있는 금액의 기댓값은 무한대가 되어버린다.

If bounded at 1 trillion(= $2^{40}$), then,
$\displaystyle \sum_{k=1}^{40} 2^k \cdot \frac{1}{2^k} = 40$
받을 수 있는 총 금액을 1조 달러로 제한한다면, 기댓값은 고작 40달러밖에 되지 않는다.
즉, 수학적으로 공정한 가격은 무한대이지만, 현실적인 기댓값은 터무니없이 작기 때문에 아무도 이 게임에 큰 돈을 내지 않을 것이고, 이를 역설이라고 한다.

즉, 평균의 지수를 함부로 옮겨서는 안 된다.

\[\infty = E(2^X) \neq 2^{E(X)} = 4\]