単純ランダムウォークの到達時間と全訪問時間のまとめ

概要

連結無向グラフ上の単純ランダムウォークの到達時間(hitting time)と全訪問時間(cover time)に関する様々な結果を紹介します. 前半で諸定義を書き後半は軽いサーベイになっています.

1. 用語と定義

この章は基本的な用語の定義だけなのでよく分からなければ読み飛ばしても大丈夫です. 本記事では有限集合$V$上の離散時間マルコフ連鎖$(X_t)_{t\geq 0}$をランダムウォークと呼ぶことにします. 便宜上, 集合$V$を頂点集合と呼びその要素$v\in V$を頂点と呼ぶことにします. 遷移確率が時刻に依存せず一定であれば, $(X_t)$は斉時的である (time-homogeneous) といいます. 以下では断りなく$(X_t)$はtime-homogeneousなランダムウォークを表すこととし, その遷移確率行列を$P$と表記します. 即ち, $P\in[0,1]^{V\times V}$であって$(X_t)$は

$$\Pr[X_{t+1}=v\mid X_t=u] = P(u,v)$$

の遷移規則を満たす確率変数列です. 数直線上のランダムウォークなどを考えると$V=\mathbb{Z}$は無限集合になることもあり, この時は$P$は行列ではなく線形作用素と見なすことになりますが, ここではそのようなケースは考慮しません.

$P$と初期点$X_0$を与えると$(X_t)$の軌道の分布が定まります. $X_t$の分布を$x_t\in[0,1]^V$とすると, $x_{t}=x_{t-1} P = \dots = x_0 P^t$を満たします. 大袈裟に言ってしまえば, $(X_t)$の分布を調べることは$P^t$の性質を調べることと同義なので, 線形代数が重要になってくることは想像に難くないと思います. 特に, $P$がその定常分布から誘導される計量(内積空間)において自己随伴的であることを仮定することが多く (これを可逆性; reversibility), この場合は特に実固有値を持ち, 特にCourant–Fischerの定理を使うことによって混交時間 (mixing time)などを抑えることができます. これらの基礎をちゃんと学びたい人は Reversible Markov Chains and Random Walks on Graphs や Markov Chains and Mixing Times などの教科書がオススメです.

例(単純ランダムウォーク)

無向グラフ$G=(V,E)$の頂点$u\in V$の次数を$\deg(u)$とします. 

$$\begin{align*} P(u,v) = \begin{cases} \frac{1}{\deg(u)} & \text{if }uv\in E,\\ 0 & \text{otherwise}\end{cases}\end{align*}$$

によって定義される$P$によって定まる$(X_t)$を単純ランダムウォーク(simple random walk; SRW) といいます. 言い換えると, 隣接頂点から一様ランダムに頂点を選びそこに遷移する過程で, 最も有名なランダムウォークだと思います. $X_t$の分布のベクトル$x_t\in[0,1]^V$に対し, $\lim_{t\to\infty}x_t$は収束するでしょうか?

結論から言うとNOとなる例が存在します. 無向二部グラフ上の単純ランダムウォークを考えてみましょう. すると左右の頂点集合に交互に移動することになるので, $x_t$は収束しないことがすぐわかります.

このようなランダムウォークの周期性 (periodicity) を除去するために, 確率$1/2$で今の位置にとどまるような以下の$P$で定まるランダムウォークを考えてみましょう:

$$\begin{align*} P(u,v) = \begin{cases} \frac{1}{2} & \text{if }u=v,\\ \frac{1}{2\deg(u)} & \text{if }uv\in E,\\ 0 & \text{otherwise}.\end{cases}\end{align*}$$

自己ループをくっつけたので, 先ほどの二部グラフのような周期性は除外され, 実は$x_t$の集束することが証明できます ($G$の無向性は必要). このようなランダムウォークは遅延単純ランダムウォーク (lazy simple random walk; LSRW) と呼びます (lazyの和訳でよく使われるものを知らないのでとりあえずここでは遅延と呼ぶことにします).

1.1. 到達時間, 全訪問時間, 混交時間

$V$上のランダムウォーク$(X_t)_{t\geq 0}$を考えます. 二つの頂点$u,v$に対し確率変数 $$\tau_{\mathrm{hit}}(u,v)=\min\{t\geq 0\colon X_t=v,X_0=u\}$$

を考えます. これは頂点$u$からスタートして頂点$v$に初めて到達するまでに要する時間を意味します. 定義より明らかに$\tau_{\mathrm{hit}}(u,u)=0$です.

$$t_{\mathrm{hit}}=\max_{u,v\in V}\mathrm{E}[\tau_{\mathrm{hit}}(u,v)]$$

を到達時間(hitting time)と呼びます. 以降, ``$\tau$"が付くものは確率変数で``$t$"がつくものはそれの期待値だと思ってください.

次に, 全訪問時間(cover time)を定義します. 頂点$u$に対し確率変数

$$\tau_{\mathrm{cov}}(u)=\min\{t\geq 0\colon \{X_0,\dots,X_t\}=V,X_0=u\}$$

を定義します. これは$u$を始点としたランダムウォークが全ての頂点に少なくとも1回ずつ到達するのに要した時間を表す確率変数です.

$$t_{\mathrm{cov}}=\max_{u\in V}\mathrm{E}[\tau_{\mathrm{cov}}(u)]$$

を$(X_t)$の 全訪問時間(cover time) と呼びます.

1.2. SRWに対する有名なバウンド

この節では連結無向グラフ$G$上のSRWの到達時間と全訪問時間のバウンドに関する既存結果だけを簡単に紹介します. LSRWを考えても期待値的に値は2倍しか変わりません. $G$の頂点数を$n$, 辺数を$m$とします.

自己ループ付きの完全グラフ上のSRWの全訪問時間はクーポンコレクター問題になり, 古くから研究されており, $t_{\mathrm{cov}}=(1+o(1))n\log n$です.

$n$頂点のパスグラフは最悪な始点として端の頂点を考えればよく, この場合はもう一方の端の頂点に到達するまでに要する時間を考えれば$t_{\mathrm{hit}}=t_{\mathrm{cov}}=\Theta(n^2)$が示せます. $\Theta(n^2)$の直感としては, 無限の数直線$\mathbb{Z}$上の$T$ステップの単純ランダムウォークは$T$個の独立なRademacher確率変数 (一様に$\pm 1$のいずれかを出力する確率変数)の和として表すことができ, 中心極限定理より$T$ステップ後の座標は絶対値が大体$\Theta(\sqrt{T})$くらいになります. $n$だけずれるのに要する時間は$\Theta(\sqrt{T})=n$を$T$について解いて$T=\Theta(n^2)$を得ます.

明らかに到達時間は全訪問時間の下界になるため$t_{\mathrm{hit}}\leq t_{\mathrm{cov}}$なのですが, 実は$t_{\mathrm{cov}}=O(\log n\cdot t_{\mathrm{hit}})$が任意のグラフで成り立ちます. これはランダムウォークの文脈ではMatthew's bound [Matthew, Ann. Probab. 88]などと呼ばれる非常に有名なテクニックです.

Aleliunasら [Aleliunas, Karp, Lipton, Lovász, and Rackoff, FOCS1979]は任意の連結グラフに対し$t_{\mathrm{cov}}\leq 2m(n-1)$を証明しました. この証明は全域木に沿った軌道を考えそれぞれの辺に対するedge commute timeの総和を考えることで得られており, 1ページほどにまとめられていて面白いです.

Kahnら [Kahn, Linial, Nisan, Saks, J. Theor. Probab., 1989]は$\frac{m}{2d_{\min}}\leq t_{\mathrm{hit}} \leq t_\mathrm{cov}\leq 16mn/d_{\min}$ ($d_{\min}$は最小次数) を示しました. ここから系として, 正則グラフに対する$t_{\mathrm{cov}}=O(n^2)$というバウンドが得られます. この定理の証明はAleliunasらの証明における全域木を巧妙に構成することによって得られています. この上界は定数倍を除いてタイトで, t_{\mathrm{hit}}=\Omega(n^2)$を満たす3正則グラフが構成されています (cf. Aldous--Fill本).

Aleliunasらの上界がタイトになる例も知られており[Brightwell, Winkler, RSA1990]はロリポップグラフと呼ばれるグラフが$t_{\mathrm{hit}}=(4/27+o(1))n^3$になることを証明し, Feige [Feige, RSA1995]は任意の連結グラフで$t_{\mathrm{cov}}=(4/27)n^3+O(n^{2.5})$となることを証明しました.