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

• Conditioning : the soul of statistics 조건은 통계학에서 가장 중요한 핵심 주제이다.
• Random variables and their Distributions 확률변수와 그에 대한 분포

Gambler’s Ruin(도박꾼의 파산)

상황 : A와 B 두명의 도박꾼이 매 라운드 1달러씩 걸고 도박을 한다. 이긴 사람은 상대방의 1달러를 가져가고, 둘 중 한 명이 가지고 온 돈이 바닥날 때까지 이 과정을 반복한다.

• $p = P$, (A가 어떤 라운드를 이긴다, $i+1$)
• $q = 1- p$, ($i-1$)
• A는 $i$달러, B는 $N-i$달러를 가지고 게임을 한다고 할 때, 다음과 같은 양상을 보인다.

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

Strategy : condition on first step

첫 단계에서 전략을 세우는 방법

• $p_i$ : A가 $i$달러로 시작하여 게임을 이길 확률 $p_i = P(\text{A wins game} | \text{A starts i\$})$
• $p_i = p\cdot p_{i+1} + q \cdot p_{i-1} (1\leq i \leq N - 1)$이고, $p_0 = 0, p_n = 1$이다.
  • 여기서 $p_0, p_n$과 같은 극단적인 경우에는 **“경계 조건(boundary condition)”**이라 한다.
  • $p_0 = 0$인 이유는 0원 들고 있으면 시작부터 파산이고 $p_N = 1$인 이유는 N원 들고 있으면 시작부터 승리이기 때문
  • 위 식은 재귀적이기 때문에 해결 가능하다.

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

미분 방정식을 푸는 유명한 방법 중 하나는 “guess”하는 것 입니다.

guessing을 통한 풀이

$$ \begin{align} x^i = p\cdot x^{i+1} + q\cdot x^{i-1}\\ px^2-x + q = 0 \\ x = \cfrac{-1\pm \sqrt{1-4pq}}{2p}\\ 1-4pq=(2p-1)^2\\ x\in \{1, \cfrac{q}{p}\}\\ p_i = A\cdot 1^i + B\cdot(\cfrac{q}{p})^i \ \ (p\ne q)\\ p_0 = A+ B = 0 \rightarrow B = -A\\ p_N = A + B(\cfrac{q}{p})^N = A(1-(\cfrac{q}{p})^N) = 1\\ A = \cfrac{1}{1 - (\cfrac{q}{p})^N} \\ p_i = \cfrac{1 - (\cfrac{q}{p})^i}{1 - (\cfrac{q}{p})^{N}}\\ \lim_{x \rightarrow 1} = \lim_{x \rightarrow 1}\cfrac{1-x^i}{1-x^N} = \lim_{x \rightarrow 1} \cfrac{i(x^{i-1})}{N(x^{N-1})} = \cfrac{i}{N} \end{align} $$

1. $p_i = x_i$라고 하자.(문제의 내용을 $x$에 대한 지수 값 $i$에 대한 미분방정식으로 해결하겠다는 뜻, 하지만 위에서 가정한 경계조건 $i=0$일 때 $x^0 = 1$이므로 만족하지 않아 해결될 수 없다는게 자명하지만 일단 insight를 얻을 수 있다는 생각으로 접근하는 듯 함. 또한 )
   • 미분방정식을 공부했다면, 먼저 일반해를 구한다고 함. 그 후에 초기 조건이나, 경계 조건을 사용하여 특수해를 구함 지금까지 하는 건 일반해를 구하는 과정
2. 양변을 $x^{i-1}$로 나누면 $x$에 대한 2차방정식이 나옴
3. (2)에서 나온 2차 방정식을 근의 공식을 이용해 구하면 다음과 같이 계산됨
4. 이때 $q = 1-p$이기 때문에, (4)와 같은 식이 유도됨
5. (4)번의 식을 정리하면 (5)처럼 $x$ 값이 계산됨.

• $p \ne q, x = \cfrac{q}{p}$ 인 경우
  1. $p\ne q$일 때 $p_i = A1^i + B(\cfrac{q}{p})^i$라고 함.
     • 다항식의 여러 해를 찾았을 경우, 일반해는 그 해의 선형 결합이 된다고 합니다. 여러 해라고 가정하기 위해 $p\ne q$의 조건도 추가했음.
     • 그래서 선형결합을 위한 $A, B$가 항에 추가됨.
  2. 앞선 boundary contition을 설정할 때 자명한 $p_0, p_N$을 구하는 과정
     • $p_0 = 0$을 만족하기 위해 $i =0$을 (6)에 대입해서 식을 풀면 $B = -A$라는 식이 나옴
  3. (7)에서 구한 값을 이용해 $p_N$도 구할 수 있음.
     • $p_N = 1$을 만족하기 위해 $i = N$을 (6)에 대입해서 식을 풀면 다음과 같이 계산됨.
  4. 다음과 같이 $A$값을 정리할 수 있음.
  5. (9)에서 구한 $A$값을 이용해 $p\ne q$일 때의 경우에 대해 (6)의 $p_i$값에 적용해 결론에 도달할 수 있음.
• $p = q$인 경우 → $x = 1$인 경우, (사실 이러면 그냥 x = 1인 거 같은데, 왜 갑자기 극한 상황을 보는지는 이해하지 못했음.)
  1. $x = \cfrac{p}{q}$라고 놓고, $x \rightarrow 1$의 극한을 살펴볼 때 (11)처럼 전개되는 것을 확인할 수 있다. (11)에서 $\cfrac{0}{0}$꼴이므로 로피탈의 정리를 이용해 위아래를 도함수로 대체할 수 있다. 고로 $\cfrac{i}{N}$이 나오게 된다.

사실 guessing을 통한 풀이가 중요한게 아니라, 문제를 조건적으로 생각하는 것과 이 문제의 구조를 알아보는 것이 중요하다고 함.

위에서 구한 방식으로 실제 값을 넣어서 결과를 도출했을 때의 결과는 다음과 같다.

• $p = 0.49$ → A가 이길 확률
  • $N = 20$ → 40%로 A가 이김
  • $N = 100$ → 12%로 A가 이김
  • $N = 200$ → 2%로 A가 이김
• $p = q$인 경우에 $B$가 이길 확률
  • $A$가 이길 확률이 $\cfrac{i}{N}$이므로, $B$의 경우 $\cfrac{N-i}{N}$이 나오게 된다.
    • 이때 $\cfrac{N-i}{N}$가 나오는게, $1- A\text{의 확률}$이라서 $\cfrac{N-i}{N}$가 나오는게 아님.
    • $A$가 이길 확률이 $\cfrac{i}{N}$가 나오는 이유가 게임을 시작할 때 전체 돈 $N$ 중 $i$를 가지고 있다고 가정했고, $B$의 경우 $N-i$를 가지고 있기 때문에$\cfrac{N-i}{N}$가 나오는 것임.
  • $A$가 $\cfrac{i}{N}$, $B$가 $\cfrac{N-i}{N}$인데, 둘의 합이 1이다.
    • 그래서 모든 경우의 수가 $A \text{ or }B$가 파산하는 경우밖에 없다.
    • Naive하게 전체 경우의 수를 생각하면 아래와 같다.
      1. $A$가 파산
      2. $B$가 파산
      3. 게임이 영원히 끝나지 않음.
    • 이때 1번과 2번 사건이 일어날 확률의 합이 1이므로 3이 존재하지 않는다는 증명 방식

---

확률 변수(Random Variable)

• $S$라고 했던 표본 공간안에서 정의되는 함수이다.
• 확률변수는 표본 공간상에서의 어떤 사건인 $s$를 입력으로 받아 실수값에 대응시키는 “함수”입니다.
• 수업에서는 확률 변수를 **수치적인 요약(이때 전체를 요약하는 것이 아닌, 입력으로 들어오는 특정 사건들의 집합의 요약이라고 생각합니다.)**이라고 표현합니다.

베르누이(Bernoulli) 확률변수

확률변수 $x$가 베르누이 분포를 따른다는 건 베르누이 분포의 정의라고 생각.

만약 $x$가 2개의 값 0, 1만을 가질 수 있다면,

• $P(x= 1) = p, P(x= 0) = 1-p$
  • 어떤 확률시행이 있을 때 결과는 무조건 0또는 1로 대응되게 된다.
• $P(x = 1)$에서 $x = 1$은 어떤 사건(event)를 의미합니다.
  • 이게 코딩에서도 비슷한 맥락을 가질 수도 있을 듯 한데, python을 예로 들어서
    • 1 + 1 → 2
    • ‘a’ + ‘b’ → ‘ab’
    • 같은 + 연산자이지만, 완전히 다른 기능을 한다.
    • 일반적으로 $x = 1$이라는 것은 ‘x가 1이다’라는 뜻이지만, 위에서는 사건 s의 확률변수가 1이 나오는 사건(?)라는 뜻으로 받아드리면 될 듯 하다.
  • $\{s : x(s) = 1\}$라는 수식으로 $x = 1$을 형식적으로 쓸 수 있습니다.

Binomial(n,p)

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

→ 베르누이($p)$ 시행 = $(0, 1)$이 결과값으로 나오는 시행

이항분포에서의 $x = k$는 성공횟수가 $k$번 이라는 뜻 그래서 $P(x= k)$는 다음과 같다.

$$ P(x = k) = \binom{n}{k}p^k (1-p)^{n-k} $$

• 분포에서의 $x = k$는 사건이 $k$번 일어날 확률
• 확률 변수에서의 $x = k$는 $k$라는 사건이 일어날 확률

$X \sim Bin(n,p)$ : 베르누이 분포에서 $X$번 성공했음

$X \sim Bin(n,p)$, $Y \sim Bin(m,p)$일 때, $X + Y \sim Bin(n + m,p)$을 따른다.

PMF(probability mass function)

$x = k$일 때의 확률을 명시해주는 함수

---

확률론 강의에서 중요한 것.

• 문제의 구조가 무엇인지 파악하는 것, 위의 Gambler’s Ruin이라는 문제에서 예시를 도박꾼으로 들었지만, 사실 금융쪽이나 물리쪽에서도 같은 상황이 자주 포착됨. 실제 상황에서도 이게 같은 “구조”인지를 파악하는게 중요함

  • 딥러닝에서도 비슷한 예시를 생각할 수 있을 듯 한데, 딥러닝에서 내가 생각했을 때 가장 중요한 것은 “모델의 구조”, “loss function”이다. 실제 개발할 때에는 hyperparameter도 중요하겠지만, 왜 위 2가지를 꼽았는지 설명해보겠습니다.

  • 나중에 배울 내용이지만 regression을 해결할 수 있는 model 중 linear model과 logistic model이 있고, 각각의 특징에 대해 배우게 됩니다.

    • linear regression model
    • logistic regrssion model

    두 모델의 차이는 무엇일까요? 직관적으로 모델의 “생김새” 혹은 “구조”가 다름을 시각적으로 확인할 수 있습니다. 그러면 이 구조가 다름으로 인해서 어떤 차이가 발생할 수 있을까요?

    • linear model의 경우 Data의 distribution을 가장 잘 표현하는 1개의 직선을 표현할 수 있습니다.
    • logistic regression의 경우 어떤 부분이 Data의 Decision boundry인지 표현할 수 있습니다.즉 모델마다 하는 역할, 할 수 있는 능력이 다르고, 이로인해 이러한 layer들을 쌓았을 때 model이 할 수 있는 capacity의 영역이 다르다는 insight를 가지고 있습니다.