23 Sat

TIL

[Statistics 110] 7강- 도박꾼의 파산 문제와 확률변수 (Gambler's Ruin and Random Variables)

Gambler's Ruin(도박꾼의 파산): A와 B 두 명의 도박꾼이 매 라운드 $1씩 걸고 도박을 한다. 이긴 사람은 상대방의 $1을 가져가고, 둘 중 한 명이 가지고 온 돈이 바닥날 때까지 이 과정을 반복한다.

• 이 문제는 0부터 N까지의 수직선위에 i 지점에 있는 벌레의 무작위 행보문제와 동일하다

p = P(A가 한 라운드를 이길 확률)

q = 1-p (B가 한 라운드를 이길 확률)

A는 i 달러, B는 N-i 달러를 가지고 게임을 한다고 할 때,

p의 확률로 A가 1달러를 더 얻고, q의 확률로 1달러를 잃는다. 0, N은 흡수상태(absorbing state)라 하여, 게임 종료를 나타낸다.

$p_i$​​ : A가 i 달러로 시작하여 게임을 이길 확률 : $P(A ~wins ~game | A~ start~ at~ i~ dollars)$

$p_i = p \cdot p_{i+1}+q \cdot p_{i-1}​ ( 1 \le i \le N-1)$ 이고, $p_0 = 0, p_{N} = 1$ 이다.

이를 계차방정식(difference equation)이라고 한다.(미분방정식의 이산 형태)

guessing을 통한 풀이

$p_i = x^i$라고 하자.

$x^i = p \cdot x^{i+1} +q \cdot x^{i-1}$​​

$px^2 - x +q = 0$

$x = \large {\frac{-1 \pm \sqrt{1-4pq}}{2p}}$ 이고, $q = 1-p$이기 때문에, $1-4pq = (2p-1)^2$​​ 이 성립한다.

따라서 $x \in \{1, \large\frac{q}{p} \}$ 이 때, 우리가 관심있는 것은 p와 q가 다를 떄 이다.

→ 두 해가 다른 경우 다음과 같이 선형인 식으로 표현한다.

$p_i = A\cdot 1^i + B \cdot (\large\frac{q}{p})^i​​ (p \ne q)$

여기에 조건 $p_0 = 0, p_{N} = 1$ 을 대입하면,

$p_0 = A+B = 0$ $\rightarrow B=-A$

$p_N = A +B \large(\frac{q}{p})^N​​​ = A(1-\large(\frac{q}{p})^N)=1$

$A = \Large \frac{1}{1-(\frac{q}{p})^N}$

$p_i = \Large{\frac{1-(\frac{q}{p})^i}{1-(\frac{q}{p})^{N-i}}}(p \ne q)$

그리고 $p = q$ 인 경우,

$x = \large\frac{q}{p}$ 라고 놓고 $x \rightarrow 1$ 의 극한을 살펴보았을 때,

$\lim_{x \rightarrow 1} = \lim_{x \rightarrow 1}{\large\frac{1-x^i}{1-x^N}}​​ = \lim_{x \rightarrow 1} \large \frac{i(x^{i-1})}{N(x^{N-1})} = \large \frac{i}{N}$

$\Rightarrow p_i = {\Large{\frac{1-(\frac{q}{p})^i}{1-(\frac{q}{p})^{N-i}}}} (p \ne q) ~ or ~ {\large \frac {i}{N}​}~ (p = q)$

해석

하우스와 같은 돈을 가지고 시작하고, 1%정도로만 불공평한 게임이라고 해도 게임을 계속하다 보면 이길 확률이 매우 적어지게 된다. ('도박꾼의 파산')

확인할 점: 게임이 끝나지 않고 영원히 계속될 확률이 있는가?

게임이 공평한 상황에서 (p = q) B가 (N-i 달러를 갖고) 이길 확률은 $\large \frac {N-i}{N}​$이다.

$\large \frac{i}{N} + \frac{N-i}{N}=1$이므로 게임이 계속될 확률은 0이다.

확률변수(Random Variable): 표본공간 S부터 실수 체계 R로 '맵핑' 하는 함수

예시) 베르누이(Bernoulli) 확률변수

X가 0(실패), 1(성공) 두 가지의 값만 가질 수 있으며,

P(x=1)=p, P(X=0) = 1-p 일 때

X는 Bernoulli(p) 분포를 따른다고 한다.

예시) 이항(Binomial) 확률변수

n번의 독립적인 베르누이(p) 시행에서 성공 횟수의 분포는 Bin(n,p) 를 따른다고 한다.

• 이항확률변수의 확률질량변수(PMF): $P(X = k) = {n\choose k} p^k(1-p)^{n-k}$
• 이항확률변수의 특징

X~Bin(n,p), Y~ Bin(m,p) 일 때,

X+Y~Bin(n+m,p) 를 따른다.