Skypainter
목차
이번 포스트에서는 조건부 기댓값(conditional expectation)과 마팅게일에martingale에 대해서 다루겠습니다. 후에 Martingale convergence theorem을 이용하여 방사상 대칭의 트리(radially symmetric tree)에서는 random walk가 transient 하다는 것을 증명할 것입니다.
1. 조건부 기댓값(Conditional Expectation)
기본적인 setting은 다음과 같습니다.
$(X, \mathcal{A}, \mathbb{P})$: 확률 공간
$\mathcal{B} \subset \mathcal{A}$: sub $\sigma$-algebra
그러면 자연스럽게 $\mathcal{L}^{1}(X,\mathcal{B}, \mathbb{P}) \subset \mathcal{L}^{1}(X, \mathcal{A}, \mathbb{P})$가 성립합니다.
이 포스트에서는 아래와 같이 조건부 기댓값을 정의를 하겠습니다.
(Def) Conditional expectation
Given $f \in \mathcal{L}^{1}(X, \mathcal{A}, \mathbb{P})$ and $\mathcal{B} \subset \mathcal{A}$, the conditional expectation $E[f | \mathcal{B}]$ is the unique function $g:X \rightarrow \mathbb{R}$ such that
(1) $g \in \mathcal{L}^{1}(X, \mathcal{B}, \mathbb{P})$ (in particular, $g$ is $\mathcal{B}$-measurable)
(2) $\int_{B} g \, d\mathbb{P} = \int_{B} f \, d\mathbb{P}, \;\; \forall B \in \mathcal{B}$
즉, 조건부 기댓값 $g=E[f | \mathcal{B}]$는 주어진 부분 시그마 대수(sub sigma algebra) $\mathcal{B}$에 의해 정의됩니다. $g$는 $\mathcal{B}$에 대해 measurable 해야하며, $\mathcal{B}$에 속한 모든 $B$위의 적분값이 $f$와 동일해야 합니다.
시그마 대수에 대해 조건을 건다는 것을 직관적으로 설명하면 다음과 같습니다. (제가 이해한 방식임으로 틀릴 가능성이 있습니다.)
시그마 대수는 우리의 정보 집합이라고 생각할 수 있습니다. 시그마 대수가 크다는 것은 우리가 상황을 더 세분화 하여 생각할 수 있다는 것으로 볼 수 있습니다.
예를 들어, 우리가 주사위에 대한 정보를 다 파악하고 있다면, 1~6의 눈이 나올 수 있고, 각각 1/6의 확률이라는 것을 알 것입니다. 이 경우의 정보 집합(시그마 대수)는 $\mathcal{A} = \mathcal{P}(\{1,2,3,4,5,6\})$ 입니다(멱집합). 하지만 정보가 부족하여 주사위의 눈이 홀수 또는 짝수인지만 구분할 수 있다면, 우리의 정보 집합(부분 시그마 대수)은 $\mathcal{B} = \{\emptyset, \{1,3,5\},\{2,4,6\} ,\Omega\}$일 것입니다. $f$가 주사위 눈의 수라고 하면, $\mathcal{B}$에 대한 $f$의 조건부 기댓값은 짝수와 홀수로밖에 구분할 수 없는 상황 하에서의 주사위 눈의 개수의 기댓값이라고 할 수 있습니다.
구체적으로, f에 대한 조건부 기댓값은 $E[f | \mathcal{B}](\omega) =
\begin{cases}
3 \; \text{if } \omega \in \{1,3,5\} \\
4 \; \text{if } \omega \in \{2,4,6\}
\end{cases}$ 입니다.
사실 위 정의의 조건을 만족하는 $g$가 존재함을 보여야 합니다. 하지만 존재성까지 다루면 포스트가 너무 길어지기 때문에 생략하겠습니다. (존재성은 라돈-니코딤 정리(Radon-Nikodym theorem)을 사용해야 합니다.)
아래는 조건부 기댓값의 특징입니다.
(Prop)
$\mathcal{B} \subset \mathcal{A}$: $\sigma$-algebra
(1) (선형성)
$\forall \lambda \in \mathbb{R}, \; \forall f,g \in \mathcal{L}^{1}(X, \mathcal{A})$.
$E[f+\lambda g | \mathcal{B}] = E[f | \mathcal{B}] + \lambda E[g | \mathcal{B}]$
(2) If $f$ is $\mathcal{B}$-measurable, $E[f | \mathcal{B}] = f$
(3) If $f$ is independent of $(X_{1}, \dotsc, X_{n})$ random variables,
$E[f | \sigma(X_{1}, \dotsc, X_{n})] = E[f]$.
여기서, $\sigma(X_{1}, \dotsc, X_{n})$은 확률변수 $X_{1}, \dotsc, X_{n}$을 measurable 하게 하는 가장 작은 시그마 대수를 의미합니다: $\sigma(X_{1}, \dotsc, X_{n}) = \sigma(\{ X_{i}^{-1}(B)| i \in \{ 1, \dotsc, n\}, \; B \in Borel(\mathbb{R}) \})$
(4) If $f,g \in \mathcal{L}^{1}(X, \mathcal{A}, \mathbb{P})$ and $f$ is $\mathcal{B}$-measurable, then $E[fg|\mathcal{B}] = fE[g|\mathcal{B}]$
편의를 위해 $E[f | X_{1}, \dotsc, X_{n}]: = E[f | \sigma(X_{1}, \dotsc, X_{n})]$ 라고 쓰기도 합니다.
이는 우리가 학부 확률 또는 통계에서 자주 봤던 표현으로, 사실 그 뒤에는 이렇게 복잡한 개념들이 숨어있었던 것입니다.
이제 예를 하나 다뤄보겠습니다.
(예시)
$(X_{n})$은 iid 확률 변수이고, $X_{n}: \Omega \rightarrow \{0,1\}$ for all $n$ 이라고 합시다. (즉, 0 또는 1을 값으로 갖는 확률 변수 입니다.)
시그마 대수는 $\sigma(X_{1}, \dotsc, X_{n}) = \{ X_{i_{1}} = a_{1}, \dotsc , X_{i_{r}} = a_{r} | (a_{1}, \dotsc, a_{r} ) \in \{ 0,1\}^{r}, r \leq n \}$ 라고 합시다. 그러면,
$\sigma(X_{1}) = \{\emptyset, X_{1}^{-1}(\{0\}) , X_{1}^{-1}(\{ 1\}), \Omega \}$이므로, $ X_{1}^{-1}( \{ 0 \} )$와 $X_{1}^{-1}( \{1 \} ) $의 경우만 생각하면 됩니다.
$C_{0} = X_{1}^{-1}( \{ 0 \} ), \; C_{1} = X_{1}^{-1}( \{1 \} )$ 라고 하면,
$\sigma(X_{1})$에 대한 조건부 기댓값은 다음과 같이 쓸 수 있습니다.
$E[f | \sigma(X_{1})] = \mathbb{1}_{C_{0}} \frac{ \int_{C_{0}} f \, d \mathbb{P} }{\mathbb{P(C_{0}) } } + \mathbb{1}_{C_{0} } \frac{\int_{C_{1} } f \, d \mathbb{P} }{\mathbb{P}(C_{1} ) }$
다음과 같이 Invariant한 set들로 만들어진 $\sigma$-algebra를 정의할 수 있습니다.
(Def) Invariant $\sigma$-algebra
Let $(X, \mathcal{A}, \mathbb{P}, T)$: measure-preserving system
Define the invariant $\sigma$-algebra as $\mathcal{A}^{T} = \{ A \in \mathcal{A}: T^{-1}A = A \text{ up to measure 0} \}$
That is, $\forall A \in \mathcal{A}^{T}, \; \mathbb{P}(T^{-1}(A) \Delta A) = 0$
$f$가 $\mathcal{A}^{T}$-measurable 하면, $\forall c \in \mathbb{R}, \; \{ x: f(x) \geq c \} \in \mathcal{A}^{T} 이고, \{ x: f(Tx) \geq c \} \in \mathcal{A}^{T}$ 이므로, 다음의 동치 관계가 성립합니다.
$f$ is $\mathcal{A}^{T}$-measurable $\Longleftrightarrow$ $f \circ T = f$ almost surely.
사실 $f$의 시간에 대한 평균의 극한은 $f$의 $\mathcal{A}^{T}$에 대한 조건부 기댓값입니다.
(Prop)
Let $(X, \mathcal{A}, \mathbb{P}, T)$: measure-preserving space
Then, for any $f \in \mathcal{L}^{1}(X, \mathcal{A})$, $E[f | \mathcal{A}^{T}] = \bar{f} = \lim\limits_{n \to \infty} \frac{S_{n}f}{n}$. ($S_{n}$: ergodic sum)
이에 대한 증명은 아래와 같습니다.
(Proof)
Birkhoff의 에르고딕 정리에 의하여 $\bar{f} \in \mathcal{L}^{1}(X, \mathcal{A}^{T}, \mathbb{P})$ 입니다.
우리가 보이고 싶은 것: $\forall B \in \mathcal{A}^{T}$, $\int_{B} \bar{f} \, d \mathbb{P} = \int_{B} f \, d \mathbb{P}$.
$f$를 양수 부분과 음수 부분으로 나눠서 고려해봅시다: $f = f^{+} - f^{-}$ where $f^{+} = max(0,f)$ and $f^{-} = f^{+} - f $
$f \geq 0$를 가정하면,
$\begin{align*}
& \int_{B} \bar{f} \, d\mathbb{P} = \int_{B} \lim\limits_{n \to \infty} \left(\frac{1}{n} \sum_{i=0}^{n-1} f \circ T^{i} \right) \, d\mathbb{P} \\
& \leq \lim\limits_{n \to \infty} \left( \frac{1}{n} \sum_{i=0}^{n-1} \int_{B} f \circ T^{i} \, d \mathbb{P} \right) \;\;\;\; \text{(Fatou's lemma})\\
&= \int_{B} f \, d \mathbb{P} \;\;\;\; \text{(measure-preserving 하고 } B \text{가 invariant 하므로)}
\end{align*}$
이제 반대 방향의 부등식을 얻어봅시다.
$f_{N}:=min\{f,N\}$ 라고 합시다.
$f \in \mathcal{L}^{1}$이므로, $\forall \epsilon > 0$, $\int_{X} f \, d \mathbb{P} \leq \int_{X} f_{N} \, d\mathbb{P} + \epsilon$ 을 만족하는 $N$이 존재합니다.
그러면 dominated convergence theorem에 의해서,
$\begin{align*}
& \int_{B} f_{N} \, d\mathbb{P} = \lim\limits_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} \int_{B} f_{N} \circ T^{i} \, d\mathbb{P} \\
& = \int_{B} \left( \lim\limits_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} f_{N \circ T^{i}} \right) \, d \mathbb{P} \;\;\; \text{(Dominated Convergence)}\\
& \leq \int_{B} \left( \lim\limits_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} f \circ T^{i} \right) \, d \mathbb{P} \;\;\; (f \geq f_{N})\\
&= \int_{B} \bar{f} \, d \mathbb{P}
\end{align*}$
따라서, $\int_{B} f \, d \mathbb{P} \leq \bar{f} \, d\mathbb{P} + \epsilon$이고, $\epsilon \rightarrow 0$ 하면, $ \int_{B} f \, d \mathbb{P} \leq \bar{f} \, d\mathbb{P} $ 입니다. $\square$
$f \in \mathcal{L}^{2}(X, \mathcal{A}, \mathbb{P})$ 라면, 조건부 기댓값 $E[f | \mathcal{A}^{T}]$는 $ (\mathcal{L}^{2})(X,\mathcal{A}^{T}, \mathbb{P}) $로의 직교사영(orthogonal projection) 입니다.
(Remark)
$f \in \mathcal{L}^{2}(X, \mathcal{A}, \mathbb{P})$, then $E[f | \mathcal{A}^{T}]$ is the orthogonal projection of $f$ onto $\mathcal{L}^{2}(X,\mathcal{A}^{T}, \mathbb{P})$
2. 마팅게일(Martingale)
마팅게일(martingale)은 다음과 같이 정의됩니다.
(Def) Martingale
A sequence $(X_{n})$ of random variable is a martingale if $E[X_{n+1} | X_{1}, \dotsc, X_{n}] = X_{n}$
정의를 보면 알 수 있듯이 다음 값에 대한 조건부 기댓값이 현재의 값인 경우 입니다. 내일을 예측할 때, 현재의 위치가 중요한 것이지 현재의 위치에 당도하게 된 경로는 영향을 주지 않는 것입니다.
마팅게일 외에도, 아래와 같이 부등호의 방향에 따라 supermartingale과 submartingale로 구분할 수도 있습니다.
(Def) Supermartingale and submartingale
If $(X_{n})$ is a submartingale, $E[X_{n+1} | X_{1}, \dotsc, X_{n}] \geq X_{n}$
If $(X_{n})$ is a supermartingale, $E[X_{n+1} | X_{1}, \dotsc, X_{n}] \leq X_{n}$
(예시)
$(X_{n})$가 iid 이고, $E[X_{1}] = 0 $ 이면, $Y_{n}:= X_{1} + \dotsc + X_{n}$이 마팅게일임을 보이겠습니다.
$Y_{1}, \dotsc, Y_{n}$을 알고 있다면, $X_{1}, \dotsc, X_{n}$을 아는 것과 같기 때문에 다음과 같이 쓸 수 있습니다.
$\begin{equation} \begin{split}
E[Y_{n+1} | Y_{1}, \dotsc, Y_{n}] &= E[X_{n+1} + X_{n} + \dotsc + X_{1} | X_{1}, \dotsc, X_{n}] \\
&= X_{1} + \dotsc + X_{n} + E[X_{n+1}] \;\;\; \text{(Prop 2)} \\
&= X_{1} + \dotsc + X_{n}
\end{split} \end{equation}$
따라서, $Y_{n}$은 마팅게일 입니다.
다음은 마팅게일과 관련된 중요한 정리중 하나인 martingale convergence theorem 입니다.
(Thm) Martingale convergence theorem
Let $(X_{n}) \subset \mathcal{L}^{1}(\Omega, \mu)$ be a submartingale such that $\sup_{n} E[X_{n}^{+} < \infty]$.
Then, there exists $X_{\infty}: \Omega \rightarrow \mathbb{R}$ such that $X_{n} \rightarrow X_{\infty}$ almost surely
(예시)
$(X_{n})$이 $\mathbb{P}(X_{n} = 0) = \mathbb{P}(X_{n} = 2) = 1/2$을 만족하는 iid 확률 변수라고 합시다.
$Y_{n}: = X_{1}\dotsc X_{n}$라고 할 때, $Y_{n}$이 마팅게일임을 보입시다.
$\begin{equation} \begin{split}
E[Y_{n+1} | Y_{1}, \dotsc, Y_{n}] &= E[X_{n+1}Y_{n} | Y_{n}] \\
&= Y_{n} \cdot E[X_{n+1}] \;\;\;\; \text{(Prop 4)} \\
&= Y_{n}
\end{split} \end{equation}$
또한, $E[Y_{n}] = 2^{n} \cdot \frac{1}{2^{n}} = 1$ 이므로, martingale convergence theorem에 의해서
$Y_{n} \rightarrow Y_{\infty}$ almost surely 입니다.
Martingale convergence theorem을 $-X_{n}$에 대해 적용하면, 다음의 결과를 얻을 수 있습니다.
(coro)
If $(X_{n})$ is a supermartingale with $\sup_{n} E[X_{n}^{-}] < \infty$, then there exists $X_{\infty}$ such that $X_{n} \rightarrow X_{\infty}$ almost surely
또한, martingale convergence theorem은 $\mathcal{L}^{}1$ 수렴을 의미하지 않습니다.
(Remark)
Martingale convergence theorem does not imply $X_{n} \rightarrow X_{infty}$ in $\mathcal{L}^{1}$