2024.11.04
固定ページ

格子上のランダムウォーク1 ～ベルヌーイランダムウォークの再帰性～








格子上のランダムウォーク1 ～ベルヌーイランダムウォークの再帰性～



格子上のランダムウォーク1
～ベルヌーイランダムウォークの再帰性～

仁謹(Jyn kin)

初めまして仁謹です。いきなりですが、 今回はランダムウォークについてお話します。 特に、格子上のランダムウォーク、つまり、値が固定された自然数\(d\)に対して、 \(d\)次元の格子\(R\)というものを考え、その上を移動する点について考えていきましょう。 \[R := \{x = (x_1, x_2, \cdots, x_d) | x_1, x_2, \cdots, x_d \in {\mathbb Z}\}\] ここで、\({\mathbb Z}\)という集合はもちろん、整数全体を表します。

続いて、関数\(P: R^2 \to [0, 1]\)が、任意の\(x \in R\)に対して、 \[\sum_{y \in R} P(x, y) = 1\] を満たすとき、これを推移関数と呼びます。 特に、今回は任意の\(x, y \in R\)に対して\(P(x, y) = P(0, y – x)\)という、 空間に関する斉次性と呼ばれる性質を持つような\(P\)の性質を見ていきます。 推移関数によって定まる確率にしたがって移動する動点の動きとして想像されるものを ランダムウォークと呼びます。 推移関数およびランダムウォークは\(d > 1\)の場合でも考えられますが、 ここでは、\(d = 1\)の例を\(2\)つ紹介しましょう。

0.0.1 例1: \(1\)次元ベルヌーイランダムウォーク

\(p + q = 1\)を満たすような非負の実数を用い、 任意の\(x \in R\)に対して\(P(x, x + 1) = P(0, 1) = p, P(x, x – 1) = P(0, – 1) = q\) として定め、さらに、\(1, -1\)以外の全ての整数\(y\)に対して\(P(x, x + y) = P(0, y) = 0\) としたとき、この推移関数によって表される点の動きはベルヌーイランダムウォーク、 \(p = q = \frac{1}{2}\)のときには特に単純ランダムウォークと呼ばれます。

0.0.2 例2: 片側幾何ランダムウォーク

やはり、\(p + q = 1\)を満たすような非負の実数を用い、任意の\(x, y \in R\)に対して \[P(x, y) = \begin{cases}
p^{y – x} q & (y \ge x)\\
0 (\text{otherwise})
\end{cases}\] とすることでも、ランダムウォークを定めることができます。

このように、推移関数\(P(x, y)\)の値を定めてランダムウォークについて考えるのですが、 ここまでの話では、\(x\)から\(y\)へ一歩踏み出しただけのように見えます。 ここで、\(P\)を用いつつ、より「歩いている感じ」を醸し出す新たな関数を定義しましょう。 \(n\)を非負の整数、\(x, y \in R\)として、 \[P_0(x, y) = \begin{cases}
1 & (x = y)\\
0 (\text{otherwise})
\end{cases}, \
P_1(x, y) = P(x, y)\] さらに、\(2\)以上の自然数\(n\)に対して、 \[P_n(x, y) = \sum_{\substack{x_i \in R \\ i = 1, 2, \cdots, n-1}}
P(x, x_1)P(x_1, x_2)\cdots P(x_{n-1}, y)\] で\(P_n\)を定義します。 事実だけお伝えしますが、\(P_n\)の値は非負で、また\(P\)と同様、任意の\(x \in R\)と\(n\)に対して、 \[\sum_{y \in R}P_n(x, y) = 1\] が成り立ちます。 直観的な\(P_n(x, y)\)の理解として、 \(x\)を出発した動点が時刻\(n\)で\(y\)に居る確率と考えることができます。

ここで、次の関数\(F_n(x, y)\)について考えてみましょう。 \[F_0(x, y) = 0, \ F_1(x, y) = P(x, y)\] さらに、\(2\)以上の自然数\(n\)に対して、 \[F_n(x, y) = \sum_{\substack{x_i \in R\setminus \{ y\} \\ i = 1, 2, \cdots, n-1}}
P(x, x_1)P(x_1, x_2)\cdots P(x_{n-1}, y)\] これは、\(x\)を出発した動点が、時刻\(n\)で初めて\(y\)に到達する確率を表します。 特に、全ての自然数\(n\)に関して\(F_n(x, y)\)の和をとることで、 \(x\)を出発した動点が、いずれかの時刻で\(y\)に到達する確率を表すことができます。

\(F_n\)に関してさまざまな公式がありますが、特に、\(\delta\)をクロネッカーのデルタとして、 \[P_n(x, y) = \sum_{k = 1}^n F_k(x, y)P_{n-k}(y, y) + \delta(n, 0)\] であることは、これから行う計算で用います。

\(20\)世紀初頭の確率論の研究者の興味を引いたものの一つとして、 原点を出発した動点がランダムウォークすることにより 再び原点に戻ってくる確率が\(1\)となるための条件を調べる、というものがありました。 当然と言えば当然ですがベルヌーイランダムウォークも分析の対象となっていたようで、 今回はそちらを紹介します。すなわち、非負の実数\(p, q\)が\(p + q = 1\)を満たすとし、 \(P(0, 1) = p, P(0, – 1) = q\)として、 \[\sum_{k = 0}^\infty F_k(0, 0) = 1\] となるための\(p, q\)の条件を求めるわけです。 ちなみに、この等式を満たすようなランダムウォークを再帰的といい、 そうでないランダムウォークを推移的といいます。

ベルヌーイランダムウォークが再帰性を満たすかどうかを調べる 方法はいくつか考えられますが、今回は、絶対値が\(1\)よりも小さい複素数\(t\)に対して \(\displaystyle \sum_{k = 0}^\infty t^{\frac{k}{2}} F_k(0, 0)\)がどのような値をとるか調べて、 そこから\(t\)を実数として\(1\)に単調増大で近づけた極限をとるという、一見回りくどい方法をとります。 このやり方は、複素平面上の関数の知識をそのまま応用できる点や、 ランダムウォークが推移的であった場合の振る舞いもわかりやすい点で優れています。

\(\displaystyle\sum_{k = 0}^\infty t^{\frac{k}{2}} F_k(0, 0)\)の値について考えるために、 一旦、\(t^{\frac{n}{2}} P_n(0, 0)\)の和について考えます。 \[P_n(0, 0) = \sum_{k = 0}^n P_{n-k}(0, 0)F_k(0, 0) + \delta(n, 0)\] であること、\(n \to n-k\)の変数変換を用いて、 \[\begin{align}
\sum_{n = 0}^{\infty}t^{\frac{n}{2}} P_n(0, 0) &= \sum_{n = 1}^{\infty}t^{\frac{n}{2}} P_n(0, 0) + 1 \\
= \sum_{n = 1}^{\infty}t^{\frac{n}{2}} \sum_{k = 0}^n P_{n-k}(0, 0)F_k(0, 0) + 1\\
&= \sum_{k = 0}^{\infty} \sum_{n = k}^{\infty} t^{\frac{n}{2}} P_{n-k}(0, 0)F_k(0, 0) + 1\\
= \sum_{k = 0}^{\infty} \sum_{n = k}^{\infty}
t^{\frac{n – k}{2}} P_{n-k}(0, 0)t^{\frac{k}{2}} F_k(0, 0) + 1\\
&= \sum_{k = 0}^{\infty} \sum_{n = 0}^{\infty}
t^{\frac{n}{2}} P_{n}(0, 0)t^{\frac{k}{2}} F_k(0, 0) + 1\\
= \sum_{n = 0}^{\infty} t^{\frac{n}{2}} P_{n}(0, 0)
\sum_{k = 0}^{\infty}t^{\frac{k}{2}} F_k(0, 0) + 1\\
\end{align}\] が言えて、これを変形することで、 \[\begin{align}
\sum_{k = 0}^{\infty}t^{\frac{k}{2}} F_k(0, 0)
= 1 – \frac{1}{\sum_{n = 0}^{\infty}t^{\frac{n}{2}} P_n(0, 0)}
\label{sums_of_power_series}\tag{sums_of_power_series}
\end{align}\] が言えます。つまり、\(F_k(0, 0)\)の和を求めるために、一旦\(t^{\frac{k}{2}} F_k(0, 0)\)の和を求めるのですが、 式([sums_of_power_series])により、 後者の値を求めるためにはさらに\(t^{\frac{n}{2}} P_n(0, 0)\)の和が重要であることがわかりました。 これからその値を求めていきます。

まず、整数(特に\(0\))に対して値を\(1\)足す、または引くということを奇数回繰り返して元の 数と同じになることはあり得ませんから、\(m\)を\(0\)以上の整数としたとき、\(P_{2m + 1}(0, 0) = 0\)です。 \(P_{2m}(0, 0)\)の値について、証明は省略し直観的に説明しますが、これは、\(2m\)回の試行のうち、 \(1\)の移動と\(-1\)の移動が同じ回数だけ起こる確率に等しく、\(\frac{(2m)!}{m!m!}p^m q^m\)となります。 これらのことから、 \[\begin{align}
\sum_{n = 0}^{\infty}t^{\frac{n}{2}} P_{n}(0, 0)
&= \sum_{m = 0}^{\infty}t^{\frac{2m}{2}} P_{2m}(0, 0)
+ \sum_{m = 0}^{\infty}t^{\frac{2m + 1}{2}} P_{2m + 1}(0, 0) \\
= \sum_{m = 0}^{\infty}t^m \frac{(2m)!}{m!m!}p^m q^m + 0\\
&= \sum_{m = 0}^{\infty}t^m \frac{2^m m!\prod_{k=0}^{m-1} (2k + 1)}{m!m!}p^m q^m\\
= \sum_{m = 0}^{\infty}t^m \frac{2^m (-2)^m\prod_{k=0}^{m-1} (- 1/2 – k)}{m!}p^m q^m\\
&= \sum_{m = 0}^{\infty}\frac{\prod_{k=0}^{m-1} (- 1/2 – k)}{m!}(-4pqt)^m
\end{align}\]

この事実と、複素数の冪に対する二項定理 (※筆者が少し調べたところ、 この定理の説明に関しては杉浦(1980)あたりが簡潔かつ書籍の入手難易度が低くて、良い。) を用いて、最後の式をべき乗の形で表しましょう。

複素数の冪に対する二項定理 \(w, z \in {\mathbb C}\)であり、\(z\)について\(|z|<1\)のとき、 \[(1 + z)^w = \sum_{m = 0}^\infty \frac{\prod_{k = 0}^{m-1} (w – k)}{m!}z^m\]

この公式を、\(z = -4pqt, w = – \frac{1}{2}\)として用いることで、 \[\sum_{n = 0}^{\infty}t^{\frac{n}{2}} P_{n}(0, 0) = \frac{1}{\sqrt{1 – 4pqt}}\] という数式が得られます。

これと式([sums_of_power_series])を合わせて \[\sum_{n = 0}^\infty F_n(0, 0) = \lim_{t \uparrow 1} \sum_{n = 0}^\infty t^{\frac{n}{2}} F_n(0, 0)
= 1 – \sqrt{1 – 4pq}\] という式が、\(p = q = \frac{1}{2}\)であってもなくても成り立ちますが、 値が\(1\)となる\(p, q\)の値は、\(p = q = \frac{1}{2}\)に限られるということが判明しました。

そうでないケースに関しても、 \(\displaystyle \sum_{n = 0}^\infty F_n(0, 0)\) の情報が残ることで推移的なベルヌーイランダムウォークの振る舞いもわかります。 例えば、\(p > \frac{1}{2} > q\)のとき、 \[1 – \sqrt{1 – 4pq} = 1 – \sqrt{1 – 4p + 4p^2} = 1 – \sqrt{(2p – 1)^2} = 2(1 – p)\] であり、\(p = \frac{3}{4}\)のときのように、かなり正の方向に進みがちなランダムウォークも、 \(\frac{1}{2}\)の確率で原点に戻ってくることがわかります。

参考文献