Random walks on groups - 마팅게일의 응용

목차

이번 포스트에서는 마팅게일을 응용하여 방사형 대칭 트리 (radially symmetric tree) 위에서의 랜덤 워크는 transient함을 보이겠습니다. (transience: 랜덤 워크가 시작점을 재방문할 확률이 1보다 작음) 마팅게일에 대해서 더 자세히 알고 싶으시면, 아래의 포스트를 참고해 주세요.

Random walks on groups - 조건부 기댓값과 마팅게일(martingale)

 

1. Blackwell's lemma

먼저, radially symmetric tree를 정의하겠습니다.

(Def)
Given $(a_{0}, a_{1}, a_{2}, \dotsc)$ with $a_{n} \geq 1$, the radially symmetric tree $T(a_{0}, a_{1}, a_{2}, \dotsc)$ is a rooted tree where the nodes at distance $n$ from the root have $a_{n}$ children for all $n$

즉, 루트에서 같은 거리만큼 떨어진 노드는 같은 수의 자식 노드를 가집니다. 따라서, 루트를 중심으로 대칭인 트리가 되는 것입니다.

(예시)

Radially symmetric tree의 예는 다음과 같습니다.

1. $T(2,2,2,\dotsc)$

 

2. 정수 $\mathbb{Z} = T(2,1,1,1,\dotsc)$

트리 위의 랜덤 워크에 대한 증명을 하기 전에 먼저 Blackwell의 보조정리(lemma)를 증명하겠습니다. 

Lemma (Blackwell)
Consider the Markov chain on $\mathbb{N}$ defined by $p(0,0)=1$, $p(n,n+1) = p_{n}$, $p(n,n-1)=q_{n} = 1 - p_{n}$ for $n \geq 1$. Then, the Markov chain hits 0 almost surely, starting from any $n$ if and only if $f(n)=q_{n}f(n-1) + p_{n}f(n+1) (*)$ has no non-constant bounded solutions $f:\mathbb{N} \rightarrow \mathbb{R}$

Blackwell's lemma를 그림으로 나타내면 아래와 같습니다.

증명은 다음과 같습니다.

(proof)

$(\Longleftarrow)$
$f(n) = \mathbb{P}(\text{hitting 0 starting from } n)$라고 합시다. 그러면
$f(n) = \mathbb{P}(\text{hit zero} | X_{0}=n) = p(n, n-1) \mathbb{P} (\text{hit zero} | X_{0}=n-1) + p(n,n+1) \mathbb{P}(\text{hit zero} | X_{0} = n+1)$ 입니다.
따라서, $f$는 위의 식 (*)을 만족합니다.
만약 Markov chain이 transient하다면,  $f(n_{0}) < 1=f(0)$인 $n_{0}$가 존재합니다.
그러면, $f$는 상수함수(constant)가 아니므로, 모순입니다.

$(\Longrightarrow)$
이번엔 $f$가 (*)를 만족하는 bounded non-constant function 이라고 합시다.
그러면 $a,b \in \mathbb{R}$를 잘 선택해서 $f'(\mathbb{N}) = a+bf(\mathbb{N}) \subset [0,1]$이 되게끔 $f$를 rescale할 수 있습니다. 따라서, $f:\mathbb{N} \rightarrow [0,1]$이라고 가정하도록 하겠습니다.
이제 $X_{n}:= f(\omega_{n})$를 정의 합시다. $\omega_{n}$은 Markov chain과 관련된 $\mathbb{N}$ 위의 랜덤 워크 입니다.
우리가 보여야 하는 것은 $X_{n}$이 마팅게일이라는 것입니다.

(i) 모든 $n$에 대해서 $E|X_{n}| < \infty$임은 clear 합니다.
 
(ii) claim: $E[X_{n+1} | X_{n}] = X_{n}$ 임을 보이겠습니다.

$\begin{equation} \begin{split}
E[X_{n+1} | X_{n}] &= E[f(\omega_{n+1} ) | f(\omega_{n})] \\
&= E[f(\omega_{n}+1) \mathbb{1}_{\{ \omega_{n+1} = \omega_{n} + 1 \} } | f(\omega_{n})] + E[f(\omega_{n} - 1) \mathbb{1}_{\{ \omega_{n+1} = \omega_{n}- 1\} } | f(\omega_{n})] \\
&= f(\omega_{n} + 1)E[\mathbb{1}_{\{ \omega_{n+1} = \omega_{n} +1\} } | f(\omega_{n})] + f(\omega_{n} - 1) E[\mathbb{1}_{\{ \omega_{n+1} = \omega_{n} - 1\} } | f(\omega_{n})] \\
&= f(\omega_{n} + 1) \mathbb{P}(\omega_{n+1} = \omega_{n} + 1) + f(\omega_{n} - 1)\mathbb{P}(\omega_{n+1} = \omega_{n} - 1) \\
&= f(\omega_{n}+1) p_{\omega_{n}} + f(\omega_{n} - 1) q_{\omega_{n}} \\
&= f(\omega_{n}) \\
&= X_{n}
\end{split} \end{equation}$

따라서, $X_{n}$은 마팅게일이므로, Martingale convergence theorem에 의해서 $\lim\limits_{n \to \infty} f(X_{n}) = f_{\infty}$ 가 almost surely 존재합니다.
만약 랜덤 워크가 almost surely 0에 도착하면, $f(\omega_{n}) \rightarrow 1$ 입니다. 하지만 $f$가 non-constant 이기 때문에 $f_{\infty}$도 non-constant합니다. (체크 필요: Fatou's lemma 이용) 이는 모순입니다.

2. Random walk on radially symmetric tree

다음은 radially symmetric tree 위의 랜덤 워크가 대부분의 경우 transient 함을 보여줍니다.

(Thm)
The simple random walk on $T(a_{0}, a_{1},\dotsc)$ is transient if and only if $\sum_{n=1}^{\infty} \frac{1}{a_{0}a_{1} \dotsc a_{n}} < \infty$

증명은 아래와 같습니다.

(proof)
위의 Blackwell 정리에서와 같이 $\mathbb{N}$ 위에서의 Markov chain을 생각해 봅시다.
그리고 $\omega_{n}$은 tree 위에서의 random walk 라고 합시다,
$d_{n} := d(\omega_{n}, 0 )$를 정의하면, 이는 $\mathbb{N}$ 위에서의 Markov chain이 됩니다.
그러면 $p_{n} = \frac{a_{n}}{a_{n}+1}$, $q_{n} = \frac{1}{a_{n} + 1}$ 이고, 
$f(n) = q_{n}f(n-1) + p_{n} f(n+1) = \frac{1}{a_{n}+1} + \frac{a_{n}}{a_{n}+1} f(n+1)$(**) 입니다.
따라서, Blackwell의 lemma에 따르면, random walk가 transient 하다는 것은 (**)를 만족하는 bounded non-constant $f$가 존재한다는 것과 동치입니다.
그럼 $f$가 bounded non-constant 하며, (**)를 만족한다고 가정합시다.
Rescale(빼기)을 통해서 $f(0)=0$이라고 가정할 수 있고, $f$가 non-constant면서 (**)를 만족하므로 $f(0) \neq f(1)$가 보장됩니다. Rescale(곱하기)을 통해서 $f(1)=1$을 가정할 수 있습니다.
그러면 (**)를 아래와 같이 쓸 수 있습니다: $(a_{n}+1)f(n) = f(n-1) + a_{n} f(n+1)$
$\Delta(n) = f(n) - f(n-1)$ 라고 하면, $ \frac{\Delta(n)}{a_{n}} = \Delta(n+1)$
$\Delta(1) = 1$ 이므로, 
$\Delta(n) = \frac{1}{a_{0} \dotsc a_{n-1}}$ 이 됩니다. 또한
$f(n) = f(0) + \sum_{k=1}^{n} \Delta(k) = f(0) + \sum_{k=1}^{n} \frac{1}{a_{0} \dotsc a_{k-1}}$ 이므로,
$f$는 bounded 하고 monotonically increasing 합니다.
따라서, $\sum_{k=1}^{\infty} \frac{1}{a_{0} \dotsc a_{k-1}} = \lim\limits_{n \to infty} f(n) < \infty$ 입니다.

위의 정리를 통해서 다음의 결과를 자연스럽게 얻을 수 있습니다.

(Coro)
If the simple random walk is recurrent, then there are infinitely many $n$ such that $a_{n} = 1$

이에 대한 예로 다음의 예시를 확인할 수 있습니다.

(예시)
$T(2,1,2,1,1,2,1,1,1,1, \dotsc, 2,\underbrace{1,\dotsc,1}_{2^{n}}, \dotsc)$

2를 기준으로 나눠서 생각하면, 다음 2가 나타나기까지 $\frac{1}{2^{n+1}}$이 $2^{n}+1$번 반복됩니다.
따라서, $\sum_{n=0}^{\infty} \frac{1}{a_{0}a_{1} \dotsc a_{n}} = \sum_{n=0}^{\infty} \left( \frac{1}{2} + \frac{1}{2^{n+1}} \right) = \infty$ 입니다.