Deeper Learning

Reversible Markov Chains $i,j$ state 간 edge가 없으면 가중치 $w_{ij}$=0. i에서 j state로 $w_{ij}$에 비례하는 확률로 이동. $$ q_{ij} = \frac{w_{ij}}{\sum_kw_{ik}} $$ $s_i$는 $\sum_Kw_{ik}$에 비례 간단하게 말하면 모든 가역적 마르코프 체인을 아래 형태(가중치가 있는 Random walk)로 나타낼 수 있다. $$ P(X_{n+1}=j|X_n=i) = \frac{w_{ij}}{\sum_kw_{ik}} = q_{ij} $$ Non-reversible Markov Chains Google PageRank 모든 페이지에 중요도 점수를 주고 그에 따라 검색 결과를 노출. 점수는 참조된 페이지의 수와 그 페이..

Markov Chains States (2),(3)를 보면 특정 state에서 다른 특정 state로는 절대 갈 수 없다. 이러한 상태를 reducible이라고 하고 (1)번과 같이 그렇지 않은 상태를 irreducible이라고 부른다. 어떤 state에서 다시 해당 state로 돌아오는 확률이 1일 때, recurrent state(재귀 상태)라고 부른다. → state 수가 유한하고 irreducible한 마르코프 체인은 모든 state가 recurrent state recurrent state의 반대 개념은 transient state(일시적 상태) (2)번 예시에서 3에서 6으로 가는 루트가 생긴다면 1,2,3은 transient state. (3)번 예시에서 0이나 3에 도달하면 그 상태에 영원..

Markov Chains $X_0,X_1,...$에서 $X_n$을 discrete time n에서의 state라고 생각 Markov Property $$ P(X_{n+1}=j|X_n=i_n,X_{n-1}=i_{n-1},...X_0=i_0)\\ =P(X_{n+1}=j|X_n=i_n) = q_{ij} $$ 과거의 모든 정보가 주어졌을 때 다음 state에 대한 확률은 현재 state만 아는 경우에서의 다음 state 확률과 동일 = (과거와 미래는 현재의 상태가 주어졌을 때 조건부 독립이 성립) $q_{ij}$는 Transition probability(전이확률)로 시간과 독립(n에 독립)으로 이러한 마르코프 체인을 동질 마르코프 체인이라고 부름 그림을 보면 직관적으로 이해가 되는데, state 1, 2, ..

Chi-Square Distribution(카이제곱 분포) $V = Z_1^2+...+Z_n^2, \space Z_j \sim N(0,1){i.i.d}$일 때, $V \sim \chi^2{(n)}$. $\chi^2_{(1)}$은 $Gamma(\frac12,\frac12)$와 같은 분포, $\chi^2$는 $Gamma(\frac n 2,\frac 1 2)$와 같은 분포 t-Distribution(t-분포) $$ Z \sim N(0,1)\\V\sim \chi ^2_{(n)}\\T = \frac{Z}{\sqrt{V/n}} \sim t_n $$ 성질 Symmetric: $-T \sim t_n$. n=1이면 코시분포를 따름 n이 2이상이면 $E(T) = 0$. 정규분포와 비슷하지만 더 heavy tailed(극단..

Law of Large Numbers(큰 수의 법칙) $X_1,...,X_n$이 i.i.d 이며 평균 $\mu$, 표준편차 $\sigma^2$일 때, 표본평균 $\bar X_n = \frac1 n\sum_{j=1}^{n}X_j$라고 정의 Strong LLN: n이 무한으로 가면 1의 확률로 $\bar X_N$ 이 $\mu$로 간다. (표본평균이 모평균에 근사) Weak LLN: 모든 c>0에 대해 n이 무한으로 가면, $P(|\bar X_n - \mu| > c) \rightarrow 0$. 체비셰프 부등식을 활용한 Weak LLN 증명 $\bar X_n-\mu$가 0으로 수렴한다는 것은 알지만, $\bar X_n$ 분포에 대한 정보는 아직 알 수 없음 무한으로 가는 무언가와 곱하여 힌트를 얻을 수 있음 ..

Conditional Expected value 특정 기간동안 방문한 손님의 수를 $N$, $X_j$를 j번째 고객이 소비하는 비용이라고 하자(평균은 $\mu$, 분산은 $\sigma^2$) $N,X_1,...,X_n$은 서로 독립일 때 $X = \sum_{j=1}^NX_j$의 평균과 분산을 구하여라. $$ E(X) = \sum_{n=0}^{\inf}E(X|N=n)P(N=n) =\mu E(N) $$ Adam’s Law를 활용해도 같은 결과를 얻을 수 있다. $$ E(X) = E(E(X|N)) = E(\mu N) = \mu E(N) $$ EVE’s Law로 분산을 구해보자 $$ Var(X) = E(Var(X|N)) + Var(E(X|N)) \\ = E(N \sigma^2) + Var(\mu N) = \si..

Conditional Expectation $X \sim N(0,1), Y=X^2$이면 $E(Y|X) = E(X^2|X) = X^2 = Y \\E(X|Y) = E(X|X^2) = 0$. 바로 위 식이 0이되는 이유는 $X^2$이 $a$라고 생각해보면 $X = \pm \sqrt a$이며 따라서 $X$의 기댓값은 둘의 평균인 0이 된다. 막대 부러뜨리기 문제 길이가 1인 막대를 무작위 지점에서(Uniform) 부러뜨린다. 부러뜨려 얻은 좌측 조각을 다시 무작위 지점에서 부러뜨려 얻은 막대 조각의 길이의 기댓값은? 첫 번째로 부러뜨리는 지점을 $X$, 두 번째로 부러뜨리는 지점을 $Y$라고 하자. $$ X \sim Unif(0,1)\\Y|X \sim Unif(0,X)\\E(Y|X=x) = \frac x2\\E..

Beta Distribution & Gamma Distribution 베타분포와 감마분포의 관계 Bank-post office example 은행 대기시간을 $X \sim Gamma(a, \lambda)$, 우체국 대기시간을 $Y \sim Gamma(b,\lambda)$. $X,Y$는 독립일 때, $T = X+Y, W = \frac{X}{X+Y}$의 joint distribution을 구하여라 계산의 편의를 위해 $\lambda$를 1로 두고 시작한다. $$ f_{T,W}(t,w) = f_{X,Y}(x,y)|\frac{d(x,y)}{d(t,w)}| = \frac{1}{\Gamma(a)\Gamma(b)}x^ae^{-x}y^be^{-y}\frac1{xy}|J| $$ Jacobian을 구하고 식을 이어서 풀면..

2 Envelope Paradox $X,Y$ 두 봉투가 있고 하나의 봉투에는 다른 봉투의 2배의 돈이 들어있다. 모순 $$ E(Y) = E(X)\\E(Y) = E(Y|Y=2X)P(Y=2X)+E(Y|Y= \frac X2)P(Y= \frac X2) = \frac 12E(2X)+ \frac 12 E(\frac X2) = \frac 54 E(X) $$ 대칭성에 의해 첫 번째식이 맞고 두 번째 식은 LOTP에 의해 맞는 것 같지만 두 번째식은 틀린 식 $E(Y|Y=2X) \ne E(2X)$. 서로 독립이라는 근거가 없기 때문에 불가능. Patterns in Coin Flips 특정 패턴이 나오기 까지(HT) 얼마나 동전을 많이 던졌을까? $W_{HT}$를 HT 패턴이 나오기까지 동전을 던진 횟수를 나타내는 확률변..

Gamma Function(감마 함수) $$ \Gamma (a) = \int_0^{\inf}x^ae^{-x}\frac{dx}{x}, (a>0,\R) $$ 성질 $$ \Gamma(n) = (n-1)!\\ \Gamma(x+1) = x\Gamma(x)\\ \Gamma(1/2) =\sqrt \pi $$ Gamma Distribution(감마 분포) 모든 가능한 구간에 대해 적분값이 1이 되도록 정규화 하기 위해 간단하게 감마 함수를 감마함수로 나누면 $$ \int_0^{\inf}\frac1{\Gamma(a)}x^ae^{-x}\frac{dx}{x} = 1\\p.d.f\space f_X(x) = \frac1{\Gamma(a)}x^ae^{-x}\frac{1}{x} $$ $X \sim Gamma(a,1)$의 pdf식을..

Beta Distribution(베타분포) Uniform distribution의 일반화 버전 $Beta(a,b), a>0, b>0$. PDF $f(x) = cx^{a-1}(1-x)^{b-1}, 0

초기하분포 분산 저번 강의에 이어서 식 정리 $$ Var(X) = Var(X_1+...+X_n) = Var(X_1)+...+Var(X_n)+2\sum_{i0$임을 보이면 된다. 각 물체에 “점수”가 있다고 가정한다. 좋은 점수(평균 이상)의 점수를 가지는 object는 무조건 1개 이상 존재한다. 예시) 100명의 사람들, 15개의 위원회가 있고 한 사람이 3개에 위원회에 속해있다면 겹치는 사람이 3명보다 많은 위원회가 존재한다는것을 보여라 임의의 두 위원회에서 겹치는 사람의 기댓값을 구하자. 사람 j가 특정 위원회 2개에 동시에 속해있는 사건을 나타내는 지시확률변수 $X_j$를 설정 $$ X_j = \frac{\binom32}{\binom{100}2} \\ E(X) = E(X_1)+...+E(X_{10..

Covariance(공분산) 정의 $$ Cov(X,Y) = E((X-E(X))(Y-E(Y))) = E(XY) - E(X)E(Y) $$ 성질 $$ Cov(X,X) = Var(X)\\Cov(X,Y) = Cov(Y,X)\\Cov(X,c) = 0,(c=constant)\\Cov(cX,Y) = cConv(X,Y)\\Cov(X,Y+Z) = Cov(X+Y)+Cov(X,Z)\\Cov(X+Y,Z+W) = Cov(X,Z)+Cov(X,W)+Cov(Y,Z)+Cov(Y,W)\\Cov(\sum_{i=1}^ma_iX_i, \sum_{j=1}^nb_jY_j) = \sum_{i,j}a_ib_jCov(X_i,Y_j)\\Var(X_1+X_2) = Cov(X_1+X_2,X_1+X_2) = Cov(X_1,X_1)+2Cov(X_1,X_2)+C..

2-D LOTUS $Z_1,Z_2$가 i.i.d 표준정규분포를 따를 때, $E(|Z_1-Z_2|)$를 구하라 $X,Y$가 서로 독립이고 정규분포를 따를 때, $X+Y \sim N(\mu_1+\mu_2,\sigma_1^2+\sigma_2^2)$. $Z_1-Z_2$는 N(0,2)를 따르기 때문에 $Z = \frac{x-\mu}{\sigma}$에서 $N(0,2)=\sqrt2Z$. $$ \sqrt2 E(|Z|) = \sqrt2\int_{-\inf}^{inf}|z|\frac{1}{\sqrt{2\pi}}e^{-z^2/2}dz\\=\sqrt{\frac2\pi} $$ Multinomial Distribution(다항분포) $\vec X\sim Mult(n,\vec p), \vec p=(p_1,...,p_k), p_j ..

Joint, Conditional, Marginal Distribution joint CDF(discrete & continuous) $$ F(x,y) = P(X \le x, Y \le y) $$ joint PDF(continuous) $$ f(x,y) = \frac{d}{dxdy}F(x,y)\\P((x,y) \in A) = \int\int_Af(x,y)dxdy $$ marginal PDF of X $$ \int f(x,y)dy $$ PDF of conditional distribution Y|X 독립 $f(x,y)= \frac1\pi,(x^2+y^2\le1, 0 \space otherwise)$. 위 식에서 X의 marginal distribution을 구하면 $$ f_X(x) = \int_{-\sqr..

MGF 지수분포의 MGF $X \sim Expo(1)$. $$ M(t) = E(e^{tx}) \\ \int_0^{\inf}e^{tx}e^{-x}dx = \int_0^{\inf}e^{-x(1-t)}dx = \frac1{1-t}, (t

망각성질(무기억성, memoryless property) 이산확률분포는 기하분포, 연속확률분포에서는 지수분포가 유일 확률변수 $X$가 모두 양수이며, 연속적이고 무기억성을 가진다면 그 확률변수가 따르는 확률분포는 지수분포가 유일하다. proof) $X$의 cdf를 $F(X)$라고 하자 $$ G(X) = P(X>x) = 1 - F(x)\\G(s+t) = G(s)G(t)\space memoryless\\G(kt) = G(t)^k\\ G(1x) = G(1)^x = e^{xlnG(1)} = e^{-\lambda x} = 1-F(x) $$ 기대수명 기대수명을 구하는 방법은? 어느 날 태어난 아기들을 모두 관찰하고 특정 연도에 죽은 사람의 나이를 측정 문제는 아직 죽지 않은 사람들의 데이터가 무시됨 → 중도절단 데..

Exponential Distribution(지수분포) $X \sim Expo(\lambda)$. pdf $f_X(x) = \lambda e^{-\lambda x}$, (x >0), otherwise 0 cdf $$ F_X(x) = \int_0^x \lambda e^{-\lambda t} dt = 1-e^{-\lambda t} $$ 성질 $Y = \lambda X$이면, $Y \sim Expo(1)$. 증명은 아래와 같다 $$ P(Y \le y) = P( X \le \frac y\lambda) = 1-e^{-\lambda\frac{y}{\lambda}} = 1-e^{-y} = cdf \space of \space Expo(1) $$ Expected value (부분적분 사용) $$ E(Y) = \int_..

Coupon Collector 뽑기 상품에서 같은 확률로 등장하는 n개 종류의 장난감이 있다. 이를 모두 수집하기 위해 뽑기를 평균 몇 번 해야할까? $T_j$를 j 번째 장난감을 얻기까지의 시도 횟수라고 하자 $T =T_1+T_2+...+T_n$. $T_1$은 무엇이든 뽑으면 바로 성공이기 때문에 1이고, $T_2$는 이제 성공확률이 n/n(n-1)인 시행이 되어 기하분포로 표현이 가능 $T_2-1 \sim Geom(\frac {n-1}{n})$. 일반화한 식은 $$ T_j -1 \sim Geom(\frac{n-(j-1)}{n}) \\ E(T) = E(T_1)+...+E(T_n) = 1+\frac{n}{n-1} + ... + \frac n1 \\ =n(1+\frac 12 + ... + \frac 1n)..

표준정규분포 표준정규분포에서 기함수의 성질을 이용하면 $E(X) =0, E(X^2) = 1 , E(X^3) = 0$. 일반정규분포 $X \sim \mu + \sigma Z$ 라고 하면 $X \sim N(\mu, \sigma^2)$ 을 따른다 기댓값은 선형성에 의해 $E(X) = E(\mu) + \sigma(E(Z)) = \mu$. 분산의 성질 $$ Var(X) = E((X-E(X))^2) = E(X^2) - (E(X))^2 \\Var(X+c) = Var(X)\\Var(cX) = c^2Var(X)\\Var(X+Y) \ne Var(X) + Var(Y) $$ 일반정규분포의 분산 $$ Var(X) = Var(\mu+\sigma Z) = Var(\sigma Z) = \sigma^2Var(Z) = \sigma^2 ..

Normal Distribution(정규분포) Central Limit Theorem(중심극한정리) 적당히 많은 수의 i.i.d 확률변수를 더하면 더한 평균값의 분포는 정규분포에 수렴한다 대칭인 종모양의 pdf 평균이 0이고 분산이 1이면 표준정규분포 $Z \sim N(0,1^2)$. PDF $$ f(z) = ce^{-z^2/2} $$ c는 normalize constant로 적분을 통해 c값을 구해보자 $$ \int_{-\inf}^{\inf} e^{-z^2/2}dz $$ closed-form으로 적분식 풀이가 불가능 $$ \int_{-\inf}^{\inf} e^{-x^2/2}dx\int_{-\inf}^{\inf} e^{-y^2/2}dy \\=\int_{-\inf}^{\inf}\int_{-\inf}^{\..

Probability Density Function(PDF) 정의 확률변수 $X$가 모든 a,b에 대해 $P(a\le X \le b) = \int_{a}^bf(x)dx$ 를 만족시키면, $X$는 확률밀도함수(PDF) $f_X(x)$를 가짐 a=b라면 적분값은 0 = 특정 값을 가질 확률은 0 pmf와 마찬가지로 음수가 아니며, 모든 구간에 대해 적분하면 1이 되어야 함 Density의 의미 CDF와 PDF의 관계 $$ F_X(x) = P(X\le x) = \int_{-\infin}^{x}f(t)dt $$ $$ pdf \space f_X(x) = cdf \space F'(x) $$ 기댓값 $$ E(X) = \int_{-\infin}^{\infin}xf_X(x)dx $$ 분산, 표준편차 $$ Var(x) =..

확률변수와 확률분포의 혼동 확률변수 X, 확률변수 Y를 합하는 것은 확률변수 X가 따르는 확률분포와 Y가 따르는 확률분포를 합하는 것과 다름 X,Y가 이산확률변수라고 하면 $$ P(X+Y=k) \ne P(X=k) + P(Y=k) $$ 확률변수 $X+Y$의 pmf는 새로 찾아야 함 확률변수가 집(랜덤)이라면 확률분포는 집의 설계도(문이 빨간색일 확률, 문이 파란색일 확률) Poisson Distribution(포아송분포) $X \sim Pois(\lambda)$ PMF $$ P(X=k) = e^{-\lambda}\frac{\lambda^k}{k!}, k=\{0,1,...,\} $$ Expected value $$ E(X) = e^{-\lambda}\sum_{k=0}^{\infin}k\frac{\lambda..

Linearity Proof. $T=X+Y \rightarrow E(T) = E(X)+E(Y)$ 기댓값을 구하는 2가지 방식을 다시보면 가중치 없이 모두 더하기 같은 그룹으로 묶어 가중치 주기 $$ E(T) = \sum_ttP(X=t) $$ 위 식은 그룹으로 묶어 가중치를 주는 형태이고 위 그림(pebble world)에서 각 조약돌을 모두 더하는 방식은 가중치 없이 모두 더하는 기댓값 계산법 각 조약돌을 $s$라고 하고 등식을 세워보면 (P(s)는 조약돌의 질량) $$ E(T) = \sum_ttP(X=t) = \sum_sX(s)P(\{s\}) $$ 위 등식을 가지고 discrete case에서 Expected values의 Linearity 증명을 이어간다 $$ E(T) = \sum_S(X+Y)(s)P..

Average, Expected values, Mean은 아래에서 모두 같은 의미로 사용 CDF $F(x) = P(X\le x)$ cdf에서 pmf를 구하고 싶으면 값이 뛰는 수치를 계산 cdf $F$를 사용하여 $P(1

Binomial Distribution Story n번의 독립적인 Bern(p) 시행에서 성공 횟수 Sum of Indicator Random Variables $X = X_1+X_2+...+X_n$ $X_j$는 trial이 성공하면 1, 그렇지 않으면 0으로 2개의 값을 가질 수 있음 $X_j$는 independent identically distributed(i.i.d) 확률분포와 확률변수의 구분 확률변수는 수학적으로 함수 $X_j$는 시행이 성공하면 1, 아니면 0 확률분포는 $X$가 어떻게 다르게 행동할지에 대한 확률을 말함 같은 분포를 가진 확률변수가 여럿 존재 가능 i.i.d condition에서 확률변수들은 같은 분포를 가지지만 다른 값이 될 수 있음 PMF $X$가 특정값을 가질 확률을 수..

Gambler’s Ruin 두 도박사 A, B가 1달러를 걸고 게임을 반복. A가 이길 확률은 $p$, B가 이길 확률은 $1-p$. B가 파산하여 A확률 $p_i = P(A \space wins \space game|A \space starts \space at \space \$i)$로 정의 $p_i = pp_{i+1} + qp_{i=1}$ (1 ≤ i ≤ N-1) 이전 스텝에서 이겨서 현재 위치에 도달했거나 다음 스텝에서 져서 현재 위치에 도달했기 때문에 위와 같이 표현이 가능 [계차방정식(difference equation)] A가 이길확률이 0.49라면 N이 100일때 0.02 확률로 승리 확률변수 확률변수는 Sample space → 실수 공간을 매핑해주는 함수 확률변수 x가 베르누이 분포를 따..

Monty Hall 하나의 문 뒤에는 자동차, 2개의 문 뒤에는 염소가 있다. 참가자가 하나의 문을 고르고 사회자는 나머지 2개의 문 중에서 염소가 있는 문을 연다. 참가자는 그 뒤 선택할 문을 바꿀 기회가 주어지는데 문을 바꾸는 것이 자동차를 선택할 확률을 높여줄까? 수형도 참가자가 1번 문을 골랐다고 가정 자동차가 1,2,3번 문 뒤에 있을 확률은 각 1/3 사회자는 참가자가 고르지 않은 2 or 3번 문을 여는데, 여기에서 위 수형도를 보면 자동차가 1번 문 뒤에 있다면 사회자는 2,3 번 문을 동일한 확률로 열지만 자동차가 3번 문 뒤에 있다면 사회자는 2번 문 밖에 열 수 없다 “사회자가 2번문을 열었다”라는 조건 하에 각 분기의 확률을 보면 참가자가 1번 문 고름 → 자동차가 1번 문 뒤에 있..

Law of Total Probability 문제를 disjoint인 다른 사건들로 분할하여 푸는 방식 예제) 인구의 1%가 걸리는 병이 있는데 이 병에 걸리는 사건이 $D$, 검사 결과가 양성인 사건이 $T$ 라고 할 때 검사 결과가 양성일 때, 실제로 병에 걸렸을 확률은? ($P(D|T)$) 조건부 독립 사건 A, 사건 B가 사건 C가 발생하였을 때 독립인 상황 Reference [0] https://www.youtube.com/playlist?list=PL2SOU6wwxB0uwwH80KTQ6ht66KWxbzTIo Statistics 110: Probability Statistics 110 (Probability) has been taught at Harvard University by Joe Bli..

독립 독립이란? 위 식이 성립하면 독립 두 사건은 서로 영향을 끼치지 않음 서로소(disjoint)와 독립을 혼동하는 경우가 많음 서로소: 사건 A,B가 disjoint면 A가 발생할 때 B는 발생하지 않음 (배반사건, 독립 X) 독립: 사건 A, B가 독립이면 A의 발생은 B의 발생과 관련 없음 Conditional Probability(조건부 확률) Pebble World 관점 총 9개의 조약돌이 있는 sample space가 있다고 가정하자 위 조건부 확률 식은 사건 A(빨간색)가 일어났을 때의 사건 B(초록색)의 확률과 같다 이를 조약돌로 표현하면 사건 A,B에 공통으로 해당되는 조약돌 2개의 비중과 같다 사건 A가 일어났기 때문에 전체 world를 빨간 영역으로 줄이면 2/3이라는 답이 나온다 ..