Random walks on groups - 에르고딕 이론 ③ 랜덤 워크의 drift

목차

 

지난 포스트에서 이어집니다.

Random walks on groups - 에르고딕 이론 ② 에르고딕성

 

지금까지의 흐름은 다음과 같습니다: 측도보존계 정의 $\rightarrow$ 에르고딕성 정의 & 에르고딕 정리.
랜덤 워크에 대해 이야기하다가 갑자기 왜 에르고딕 정리까지 오게 된 이유는 사실 랜덤 워크의 drift(혹은 랜덤워크의 속력)이 존재함을 보이기 위함입니다. 랜덤 워크의 drift는 직관적으로 이야기 하면 랜덤 워크의 평균적인 원점으로부터의 거리라고 보시면 됩니다. 이번 포스트에서는 또 하나의 에르고딕 정리인 Kingman의 에르고딕 정리를 알아보고, 이를 랜덤 워크에 적용하여 랜덤 워크의 drift가 존재함을 보이겠습니다. 뿐만 아니라, 랜덤 워크의 drift가 랜덤 워크의 경로에 의존하지 않음도 확인하겠습니다.

 

1. Kingman의 에르고딕 정리

Kingman의 에르고딕 정리는 subadditive cocycle에 대한 에르고딕 정리입니다. Subadditive cocycle의 정의는 다음과 같습니다.

(Def) Subadditive cocycle
A cocycle is a function $\alpha: \mathbb{N} \times X \rightarrow \mathbb{R}$ and is subadditive if for all $n,m \geq 0$ and $x \in X$, $\alpha(n+m,x) \leq \alpha(n,x) + \alpha(m, T^{n}x)$.

이해를 돕기 위해 예를 하나 들어봅시다.
사실 지난 포스트에서 다룬 ergodic sum이 subadditive cocycle의 한 예시입니다.
Ergodic sum은 다음과 같습니다: $\alpha(n,x) = \sum_{i=0}^{n-1} f \circ T^{i}(x)$ 그러면
$\begin{equation} \begin{split}
\alpha(n+m,x) &= \sum_{i=0}^{n+m-1} f \circ T^{i}(x) \\
&= \sum_{i=0}^{n-1}f\left(T^{i}(x)\right) + \sum_{i=n}^{n+m-1} f\left(T^{i}(x) \right) \\
&= S_{n}f(x) + S_{m}f(T^{n}(x)) \\
&= \alpha(n,x) + \alpha(m, T^{n}(x))
\end{split} \end{equation}$

Kingman의 에르고딕 정리는 다음과 같습니다. 지난 포스트에서 다뤘던 Birkhoff의 에르고딕 정리를 cocycle로 더 일반화시킨 정리라고 생각하면 됩니다.

(Thm) Kingman's ergodic theorem
Let $\alpha$ be a subadditive cocycle in $(X,\mathcal{A},\mathbb{P}, T)$: mps.
Suppose (1) $\alpha(n, \cdot) \in \mathcal{L}^{1}(X,\mathbb{P})$ for all $n$
               (2) $\inf_{n}\frac{1}{n}\int\alpha(n,x) \, d\mathbb{P}(x) > -\infty$
Then, for almost every $x \in X$, $\bar{\alpha} (x):= \lim\limits_{n \to \infty} \frac{\alpha(n,x)}{n} $ exists and $\bar{\alpha} \circ T = \bar{\alpha}$.
If $T$ is ergodic, $\bar{\alpha}$ is constant almost surely. 

2. 랜덤 워크의 drift(or speed)

이제 Kingman의 에리고딕 정리를 랜덤 워크에 적용해서 random walk의 drift가 존재함을 보이겠습니다. Setting은 다음과 같습니다.
$G$: countable group
$\mu$: $G$ 위의 확률 측도
$(\Omega, \mathbb{P})$: path space
그리고 $G$가 metric space $(Y,d)$에 istometries 로 작용(act)한다고 가정합시다.
즉, $d(x,y) = d(gx,gy)$ for all $x,y \in Y$ and for all $g \in G$ 입니다.
$y$를 시작점이라고 하면 다음과 같은 cocycle을 정의할 수 있습니다:
$d(n,\omega):=d(y, \omega_{n}y)$, $\omega = (\omega_{n}) \in \Omega$

path space로 정의 되는 cocycle

랜덤 워크의 first moment는 다음과 같이 정의 됩니다.

(Def) Finite first moment of a random walk
The random walk driven by $(G,\mu)$ has finite first moment if for some $y \in Y$,
$\sum_{g} d(y, gy)\mu(g) < \infty$

사실 $\sum_{g} d(y, gy)\mu(g) < \infty$ 는 한개의 $y \in Y$만 만족하면, 모든 $y \in Y$에 대해서 성립합니다. 왜냐하면
$\begin{align*}
& d(y', gy') \leq d(y',y) + d(y, gy) + d(gy, gy') \;  \text{ (by triangle inequality)} \\
& \leq d(y,gy) + 2d(y,y') \; \text{( by isometry }  d(gy,gy') = d(y,y'))
\end{align*}$

따라서, $\int d(y',gy') \, d\mu \leq \int d(y,gy) \, d\mu + 2d(y,y')$ 이므로 임의의 $y' \in Y$에 대해서 finite first moment가 존재합니다.

랜덤 워크가 finite first moment가 존재한다면, 다음과 같은 특징을 갖습니다.

(Prop)
Let $(G,\mu)$ be a measured group acting by isometries on $(Y,d)$.
If the first moment is finite, then there is $l \geq 0$ such that for almost every $\omega$,
$\lim\limits_{n \to \infty} \frac{d \left( y,\omega_{n}y \right)}{n} = l$.

위의 $l$을 랜덤 워크의 drift 또는 speed 라고 합니다. 중요한 점은 이 drift가 랜덤 워크의 경로(path)에 의존하지 않는다는 점입니다.

(Def) Drift of a random walk
We call $l$ the drift, rate of escape or speed of the random walk.

이제 위의 Prop을 증명하겠습니다.

(Proof)
우리가 보이고 싶은 것은 $d(n,\omega):=d(y,\omega_{n}y)$ 이 $(\Omega,\mathbb{P}, T)$ 하에서 subadditive cocycle 이라는 것입니다. ($T$ 는 shift of increments  입니다.)
즉, $d(n+m, \omega) \leq d(n,\omega) + d(m, T^{n}\omega)$ 임을 보여야 합니다.

먼저, $d(n+m, \omega) = d(\omega_{n+m}y,y)$ 입니다.
그러면 triangle inequality에 의하여
$d(\omega_{n+m}y,y ) \leq d(\omega_{n+m}y,\omega_{n} y) + d(\omega_{n}y, y)$ 입니다.
$\omega = (g_{1},g_{2},\dotsc,g_{n},g_{n+1}, \dotsc)$ 라고 하면,
$ d(\omega_{n+m}y, \omega_{n} y) = d(g_{1} \dotsc g_{n}g_{n+1} \dotsc g_{m} y, g_{1}g_{2}\dotsc g_{n} y)$ 입니다.
$G$는 군이기 때문에 $ g_{1}g_{2}\dotsc g_{n} \in G$이고, isometry로 작용하기 때문에 $ d(g_{1} \dotsc g_{n}g_{n+1} \dotsc g_{m} y,g_{1}g_{2}\dotsc g_{n} y) = d( g_{n+1}g_{n+2}\dotsc g_{m}y, y)$ 입니다.
따라서, $d(\omega_{n+m}y,y ) \leq d( g_{n+1}g_{n+2}\dotsc g_{m}y, y)  + d(\omega_{n}y, y) $ 가 성립합니다.
그리고 $T$는 shift 이기 때문에 $T^{n}\omega = (g_{n+1},g_{n+2},\dotsc)$ 가 되고, $ d( g_{n+1}g_{n+2}\dotsc g_{m}y, y) = d(y,(T^{n}\omega)_{m}) )=d(m, T^{n}\omega)$ 가 됩니다.
그러므로, $d(n+m, \omega) \leq d(n,\omega) + d(m, T^{n}\omega)$ 가 성립하므로, $d(n,\omega)$는 subadditive cocycle 입니다.

이제 cocycle의 integrability를 체크해야 합니다. 그전에 먼저 다음을 확인하겠습니다.
(Remark)
If subadditive cocycle $\alpha(n,x) \geq 0$ for all $n \in \mathbb{N}$ and $x \in X$, it is enough to check that $\alpha(1,x) \in \mathcal{L}^{1}$ to show $\alpha(n,x) \in \mathcal{L}^{1}$ for all $n$.

즉, $\alpha(1,x)$가 적분가능하다면, 다른 모든 $n$의 적분 가능성은 자동으로 따라온다는 것입니다.

위의 remark가 성립하는 이유는 다음과 같습니다.
$\alpha(n,x)$가 subadditive cocycle 이기 때문에 $\alpha(n+1,x) \leq \alpha(n,x) + \alpha(1,T^{n}x)$가 성립합니다. 그러면
$\begin{align*}
& \int\alpha(n+1,x) \, d\mathbb{P} \leq \int\alpha(n,x)\, d\mathbb{P} + \int \alpha(1, T^{n}x) \, d\mathbb{P} \;\;\;\; (\alpha(n,x) \geq 0 \text{ 이기 때문}) \\
&= \int \alpha(n,x) \, d\mathbb{P} + \int \alpha(1,x) \, d\mathbb{P} \;\;\;\;(\text{measure-preserving})
\end{align*}$
입니다.
따라서, 수학적 귀납법(induction)에 의해서 $\int \alpha(n,x) \, d\mathbb{P} < \infty$ 가 모든 $n \in \mathbb{N}$에 대하여 성립합니다.

이제 $d(1,\omega)$의 적분가능성을 확인하겠습니다.
$\begin{equation} \begin{split}
\int_{\Omega} d(1,\omega) \, d\mathbb{P} &= \int_{\Omega} d(y, \omega_{1}y)\, d\mathbb{P} \\
&= \int_{G} d(y ,gy) \, d\mu(g) < \infty \;\;\; \text{(first moment 조건에 의하여)} 
\end{split} \end{equation}$

따라서, $d(n,\omega)$는 subadditive cocycle 이며, 모든 $n$에 대하여 적분가능합니다. 그러면 Kingman의 에르고딕 정리에 의하여, 거의 모든(almost every)  $\omega \in \Omega$에 대하여
$\lim\limits_{n \to \infty} \frac{d(y, \omega_{n}y)}{n} = l(\omega)$ 가 존재합니다.
그리고 $T$는 shift이므로 에르고딕 하기 때문에, 거의 모든 $\omega$에 대해 $l=l(\omega)$ 를 만족하는 $l \in \mathbb{R}$ 이 존재합니다.