第一通過浸透

同義語:第一通過パーコレーションfirst-passage percolationfirst passage percolation

概要

第一通過浸透(first-passage percolation)とは、格子の各辺に独立で同じ分布に従う非負の通過時間を置き、2 点を結ぶ道の通過時間の和の最小値をその 2 点の間の通過時間とするランダムな距離の模型で、Hammersley と Welsh が導入した。通過時間の期待値が有限なら、原点から $nx$ までの通過時間を $n$ で割ったものは、Kingman の劣加法的エルゴード定理により確率 $1$ で定数(時間定数)に収束する。時間定数はノルムか恒等的に $0$ で、通過時間 $0$ の確率がボンドパーコレーションの臨界確率より小さいことが正になる条件である。極限の形を述べる形状定理があり、通過時間のゆらぎの指数は平面で $1/3$ と予想されているが未解決である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: パーコレーション, Kingmanの劣加法的エルゴード定理, エルゴード定理

第一通過浸透(first-passage percolation)は、格子の各辺に独立で同じ分布に従う非負の 通過時間 を置き、2 点の間の道の通過時間の和の最小値をその 2 点の「距離」とするランダムな距離空間の模型である。J. M. Hammersley と D. J. A. Welsh が 1965 年に、ランダムな媒質の中を流体がしみ込む速さの模型として導入した。辺を開閉するだけの パーコレーション が「届くかどうか」を問うのに対し、第一通過浸透は「どれだけの時間で届くか」を問う。
最初の基本的な結果は、原点から $nx$ までの通過時間が $n$ にほぼ比例して増え、その比が確率 $1$ で定数 $\mu(x)$(時間定数)に収束することである。これは Kingman の劣加法的エルゴード定理の典型的な応用である。一方、その定数を分布から計算する方法は知られておらず、通過時間のゆらぎの大きさの指数も、平面の場合に予想される値 $1/3$ を含めて証明されていない。
この記事では、時間定数の存在の完全な証明、時間定数がノルムをなすこと、時間定数が正になる条件と $0$ になる条件、通過時間の分散が距離の 1 次で抑えられることを証明し、極限の形の定理(Cox–Durrett の形状定理)とゆらぎの予想を紹介する。

定義

$d\ge1$ とし、$\mathbb E^d$ を $\mathbb Z^d$ の隣り合う 2 点を結ぶ辺の集合、$\lvert x\rvert_1$ を $\ell^1$ ノルムとする。$F$ を $[0,\infty)$ 上の分布関数とし、$F(0)$ は値 $0$ の確率を表す。

第一通過浸透

$\Omega:=[0,\infty)^{\mathbb E^d}$ に、各成分 $\tau_e$ が独立に分布 $F$ に従う直積測度 $P$ を入れる。$\tau_e$ を辺 $e$ の 通過時間 という。頂点の列 $\Gamma=(x_0,x_1,\dots,x_k)$ で隣り合う 2 点が辺 $e_i=\langle x_{i-1},x_i\rangle$ で結ばれるものを、$x_0$ から $x_k$ への長さ $k$ の 道 といい、$T(\Gamma):=\sum_{i=1}^k\tau_{e_i}$ をその通過時間とする。$x,y\in\mathbb Z^d$ について
$$ T(x,y):=\inf\{T(\Gamma)\mid\Gamma \text{ は } x \text{ から } y \text{ への道}\} $$
を $x$ から $y$ への 通過時間(passage time)という。$T(\Gamma)=T(x,y)$ となる道を 測地線 という。

$T(x,x)=0$、$T(x,y)=T(y,x)$ で、道をつなぐと $T(x,z)\le T(x,y)+T(y,z)$ である。道から閉路を取り除くと、辺が減り通過時間が増えない自己回避の道が残るので、下限は可算個の自己回避の道についてとってよく、$T(x,y)$ は可測である。$F(0)=0$ なら、どの頂点に接する辺の通過時間も確率 $1$ で正なので、$T$ は確率 $1$ で $\mathbb Z^d$ の距離である。$x$ から $y$ への長さ $\lvert x-y\rvert_1$ の道を 1 本固定すると
$$ E[T(x,y)]\le\lvert x-y\rvert_1E[\tau_e] $$
である。$z\in\mathbb Z^d$ について、平行移動 $\theta_z\colon\Omega\to\Omega$ を $(\theta_z\tau)_e:=\tau_{e+z}$ で定めると、$\theta_z$ は $P$ を保ち、$T(x,y)\circ\theta_z=T(x+z,y+z)$ である($\theta_z\tau$ の配置で道 $\Gamma$ をたどることは、$\tau$ の配置で $\Gamma+z$ をたどることと同じである)。

1 次元

$d=1$ では、$0$ から $n>0$ への道は辺 $\langle k,k+1\rangle$($0\le k< n$)をどれも少なくとも 1 回通るので、$T(0,n)=\sum_{k=0}^{n-1}\tau_{\langle k,k+1\rangle}$ である。$E[\tau_e]< \infty$ なら 大数の強法則 により $T(0,n)/n\to E[\tau_e]$ である。$d\ge2$ では遠回りができるので、$T(0,n e_1)$ は独立な変数の和にならない。

平行移動のエルゴード性

$z\ne0$ なら、$\theta_z$ は $P$ についてエルゴード的である。すなわち $\theta_z^{-1}A=A$ となる事象 $A$ は確率 $0$ か $1$ である。

要点:$A$ を有限個の辺で決まる事象で近似し、遠くへずらしたものとの独立性を使う。

詳しい証明を開く

有限個の辺の状態で決まる事象の全体は直積の $\sigma$ 加法族を生成する集合代数なので、$\varepsilon>0$ について、有限集合 $G\subseteq\mathbb E^d$ の上の状態で決まる事象 $A_\varepsilon$ で $P(A\triangle A_\varepsilon)< \varepsilon$ となるものがある。$\theta_z^{-k}A_\varepsilon$ は $G+kz$ の上の状態で決まり、$k$ が大きければ $G+kz$ と $G$ は交わらないので、$A_\varepsilon$ と $\theta_z^{-k}A_\varepsilon$ は独立である。$\theta_z$ は $P$ を保つので $P(\theta_z^{-k}A\triangle\theta_z^{-k}A_\varepsilon)< \varepsilon$ で、$\theta_z^{-k}A=A$ から $\lvert P(A)-P(A_\varepsilon)^2\rvert=\lvert P(A\cap\theta_z^{-k}A)-P(A_\varepsilon\cap\theta_z^{-k}A_\varepsilon)\rvert< 2\varepsilon$ である。$\lvert P(A_\varepsilon)^2-P(A)^2\rvert< 2\varepsilon$ と合わせて $\lvert P(A)-P(A)^2\rvert< 4\varepsilon$ で、$\varepsilon\to0$ として $P(A)\in\{0,1\}$ を得る。$\square$

時間定数

時間定数の存在

$E[\tau_e]< \infty$ とし、$x\in\mathbb Z^d$ とする。定数 $\mu(x)\in[0,\infty)$ があって、確率 $1$ で、かつ $L^1$ で
$$ \lim_{n\to\infty}\frac{T(0,nx)}n=\mu(x) $$
が成り立つ。さらに $\mu(x)=\lim_n\frac1nE[T(0,nx)]=\inf_n\frac1nE[T(0,nx)]\le\lvert x\rvert_1E[\tau_e]$ である。

劣加法的な列としての通過時間

$x=0$ なら $T(0,0)=0$ なので $\mu(0)=0$ とすればよい。$x\ne0$ とし、$\theta:=\theta_x$、$f_n:=T(0,nx)$($n\ge1$)とおく。
$\theta$ は $P$ を保ち、lem-fpp-ergodic によりエルゴード的である。$f_n$ は可測で $0\le E[f_n]\le n\lvert x\rvert_1E[\tau_e]< \infty$ なので可積分である。$n,m\ge1$ について、三角不等式と平行移動の関係 $T(nx,(n+m)x)=T(0,mx)\circ\theta^n$ から
$$ f_{n+m}=T(0,(n+m)x)\le T(0,nx)+T(nx,(n+m)x)=f_n+f_m\circ\theta^n $$
であり、$(f_n)$ は劣加法的である。$f_n\ge0$ なので $\gamma:=\inf_n\frac1nE[f_n]\ge0>-\infty$ である。
Kingmanの劣加法的エルゴード定理 の定理「Kingman の定理」により、$f_n/n$ は確率 $1$ で、かつ($\gamma>-\infty$ なので)$L^1$ で、可積分な極限 $f_*$ に収束し、$\theta$ がエルゴード的なので $f_*$ はほとんど確実に定数 $\gamma$ に等しい。$\mu(x):=\gamma$ とおく。同じ定理の $\gamma$ は $\lim_n\frac1nE[f_n]$ にも等しく、$E[f_n]\le n\lvert x\rvert_1E[\tau_e]$ から $\mu(x)\le\lvert x\rvert_1E[\tau_e]$ である。$\square$

積率の条件

ADH17 Theorem 2.1(p. 8)は、$\tau_e$ の独立な写し $2d$ 個の最小値の期待値が有限であるという、$E[\tau_e]< \infty$ より弱い条件のもとで同じ結論を述べ、Liggett の形の劣加法的エルゴード定理から導いている。この条件が満たされなければ、確率 $1$ の収束も $L^1$ の収束も成り立たない(同 p. 10。ex-fpp-counter の 1 行目)。この記事では $E[\tau_e]< \infty$ の場合だけを証明する。

時間定数は方向について次の性質をもつ。

時間定数はノルムか恒等的に 0

$E[\tau_e]< \infty$ とする。$x,y\in\mathbb Z^d$、$k\ge1$ について次が成り立つ。

  1. $\mu(kx)=k\mu(x)$、$\mu(x+y)\le\mu(x)+\mu(y)$ である。
  2. 原点を固定する $\mathbb Z^d$ の対称変換(座標の置換と符号の反転)$\sigma$ について $\mu(\sigma x)=\mu(x)$ である。
  3. $\lvert\mu(x)-\mu(y)\rvert\le E[\tau_e]\lvert x-y\rvert_1$ である。
  4. $\mu$ は $\mathbb R^d$ 上の半ノルムに一意に延長される。$\mu(e_1)>0$ なら $\mu$ はノルムであり、$\mu(e_1)=0$ なら $\mu\equiv0$ である。

要点:$\mu(x)=\lim_n\frac1nE[T(0,nx)]$ に、三角不等式と分布の対称性を当てる。4 の後半は $y+\sigma y=2y_ie_i$ となる符号の反転 $\sigma$ を使う。

詳しい証明を開く

1:$\frac1nE[T(0,nkx)]=k\cdot\frac1{nk}E[T(0,(nk)x)]$ は、収束する数列の部分列の $k$ 倍なので $k\mu(x)$ に収束する。$E[T(0,n(x+y))]\le E[T(0,nx)]+E[T(nx,nx+ny)]$ で、平行移動の不変性から第 2 項は $E[T(0,ny)]$ に等しい。$n$ で割って極限をとる。

2:$\sigma$ は辺を辺に、道を道に移し、$(\tau_{\sigma e})_e$ は $(\tau_e)_e$ と同じ分布なので、$T(0,n\sigma x)$ と $T(0,nx)$ は同じ分布である。

3:1 と 2($\sigma=-\mathrm{id}$)から $\mu(x)\le\mu(y)+\mu(x-y)$、$\mu(y)\le\mu(x)+\mu(x-y)$ で、thm-fpp-time から $\mu(x-y)\le E[\tau_e]\lvert x-y\rvert_1$ である。

4:$q\in\mathbb Q^d$ について、$kq\in\mathbb Z^d$ となる $k\ge1$ をとり $\mu(q):=\mu(kq)/k$ とおく。1 により $k$ の選び方によらない。1〜3 は $\mathbb Q^d$ に引き継がれ(正の有理数倍について斉次)、3 から $\mu$ は $\mathbb Q^d$ 上で一様連続なので $\mathbb R^d$ に連続に延長され、劣加法性と、2 の $\sigma=-\mathrm{id}$ と合わせた $\mu(cx)=\lvert c\rvert\mu(x)$($c\in\mathbb R$)が極限で保たれる。よって半ノルムである。$\mu(e_1)=0$ なら 2 からすべての $\mu(e_i)=0$ で、劣加法性から $\mu\equiv0$ である。$\mu(e_1)>0$ のとき $\mu(y)=0$、$y\ne0$ とすると、$y_i\ne0$ となる $i$ をとり、$i$ 以外の座標の符号を反転する $\sigma$ について $y+\sigma y=2y_ie_i$ なので $2\lvert y_i\rvert\mu(e_i)\le2\mu(y)=0$、2 から $\mu(e_1)=\mu(e_i)=0$ となり矛盾する。$\square$

1 次元では $\mu(e_1)=E[\tau_e]$ だった(ex-fpp-one)。2 次元以上では遠回りの効果で一般に小さくなる。

遠回りによる時間定数の評価

$d\ge2$ とし、$\tau_1,\dots,\tau_4$ を $F$ に従う独立な変数とする。辺 $a_i=\langle ie_1,(i+1)e_1\rangle$ の代わりに、$ie_1\to ie_1+e_2\to(i+1)e_1+e_2\to(i+1)e_1$ の 3 辺を通ることもできるので、$T(0,ne_1)\le\sum_{i=0}^{n-1}\min\bigl(\tau_{a_i},\ \tau_{b_i}+\tau_{c_i}+\tau_{b_{i+1}}\bigr)$ である($b_i$ は $ie_1$ の上の縦の辺、$c_i$ は上の横の辺)。各項の 4 辺は異なるので、各項は $\min(\tau_1,\tau_2+\tau_3+\tau_4)$ と同じ分布に従い、期待値をとって $n$ で割ると
$$ \mu(e_1)\le E\bigl[\min(\tau_1,\tau_2+\tau_3+\tau_4)\bigr] $$
を得る。$\tau_e$ が確率 $\frac12$ ずつ $1$ と $4$ をとるなら、右辺は $2.4375$ で、$E[\tau_e]=2.5$ より小さい。分布が 1 点に集中しなければ $\mu(e_1)< E[\tau_e]$ であることは Hammersley と Welsh による(ADH17 Theorem 2.4、p. 10)。

時間定数が正になる条件

時間定数が正かどうかは、通過時間 $0$ の辺がつくる パーコレーション で決まる。

時間定数の正値性と消滅

$E[\tau_e]< \infty$ とする。

  1. $(2d-1)F(0)< 1$ なら $\mu(e_1)>0$ であり、$\mu$ は $\mathbb R^d$ のノルムである。
  2. $d\ge2$ で、$F(0)$ が $\mathbb Z^d$ のボンドパーコレーションの臨界確率 $p_c(d)$ より大きいなら、$\mu\equiv0$ である。
道の数え上げと、通過時間 0 の無限クラスタ

1:$0$ から出る長さ $k$ の自己回避の道は $2d(2d-1)^{k-1}$ 本以下である。$\lambda>0$ について $E[e^{-\lambda\tau_e}]=\int e^{-\lambda t}\,dF(t)$ は $\lambda\to\infty$ で $F(0)$ に減少して収束する(優収束定理)ので、$q:=(2d-1)E[e^{-\lambda\tau_e}]< 1$ となる $\lambda$ がとれる。次に $c>0$ を $r:=qe^{\lambda c}< 1$ となるようにとる。長さ $k$ の自己回避の道 $\Gamma$(辺はすべて異なる)について、Markov の不等式と辺の独立性から
$$ P(T(\Gamma)< ck)\le e^{\lambda ck}E\bigl[e^{-\lambda T(\Gamma)}\bigr]=e^{\lambda ck}E[e^{-\lambda\tau_e}]^k $$
である。$T(0,ne_1)< cn$ なら、$0$ から $ne_1$ への自己回避の道 $\Gamma$ で $T(\Gamma)< cn$ となるものがあり、その長さ $k$ は $k\ge n$ を満たすので $T(\Gamma)< ck$ である。よって
$$ P\bigl(T(0,ne_1)< cn\bigr)\le\sum_{k\ge n}2d(2d-1)^{k-1}e^{\lambda ck}E[e^{-\lambda\tau_e}]^k=\frac{2d}{2d-1}\sum_{k\ge n}r^k=\frac{2d}{2d-1}\cdot\frac{r^n}{1-r} $$
で、これは $n$ について和が有限である。Borel–Cantelliの補題 により、確率 $1$ で有限個を除くすべての $n$ について $T(0,ne_1)\ge cn$ であり、thm-fpp-time から $\mu(e_1)\ge c>0$ である。prop-fpp-norm の 4 により $\mu$ はノルムである。
2:通過時間が $0$ の辺を開いた辺とみなすと、各辺は独立に確率 $F(0)>p_c(d)$ で開いたパーコレーションになる。パーコレーション の定理「無限クラスタの一意性」により、確率 $1$ で無限の開クラスタはちょうど 1 つあり、これを $C$ とする。$\vartheta:=P(0\in C)>0$ である。
$x\in C$ という事象は平行移動について $\mathbf 1\{ne_1\in C\}=\mathbf 1\{0\in C\}\circ\theta_{e_1}^n$ を満たす(配置をずらすと無限クラスタもずれる)。lem-fpp-ergodic により $\theta_{e_1}$ はエルゴード的なので、エルゴード定理(Birkhoff の個別エルゴード定理)により確率 $1$ で
$$ \frac1N\sum_{n=1}^N\mathbf 1\{ne_1\in C\}\longrightarrow\vartheta>0 $$
であり、無限に多くの $n$ について $ne_1\in C$ である。事象 $\{0\in C\}$ の上では、そのような $n$ について $0$ と $ne_1$ は同じ開クラスタにあるので、通過時間 $0$ の辺だけを通る道で結ばれ、$T(0,ne_1)=0$ である。よって確率 $\vartheta>0$ で $\liminf_nT(0,ne_1)/n=0$ である。thm-fpp-time により $T(0,ne_1)/n$ は確率 $1$ で定数 $\mu(e_1)$ に収束するので、$\mu(e_1)=0$ であり、prop-fpp-norm の 4 により $\mu\equiv0$ である。$\square$

$p_c(d)\ge1/(2d-1)$ なので、1 と 2 の間には隙間がある。この隙間は Kesten が埋めた。

時間定数が正になる条件(Kesten)

$\mathbb Z^d$($d\ge2$)の第一通過浸透で、$\mu(e_1)>0$ であることと $F(0)< p_c(d)$ であることは同値である(ADH17 Theorem 2.5、p. 11。この記事では証明しない)。

平面の場合は $p_c(2)=1/2$(パーコレーション の定理「Kesten の定理」)なので、$F(0)< 1/2$ が時間定数が正である条件になる。

形状定理

$t\ge0$ について、時刻 $t$ までに原点から届く点を太らせた集合を
$$ B(t):=\bigcup\bigl\{x+[-\tfrac12,\tfrac12]^d\bigm|x\in\mathbb Z^d,\ T(0,x)\le t\bigr\}\subseteq\mathbb R^d $$
とおく。thm-fpp-time は各方向で $B(t)$ が $t$ に比例して伸びることを述べるが、すべての方向で一様にそうなることは次の定理による。

Cox–Durrett の形状定理

$\tau_e$ の独立な写し $t_1,\dots,t_{2d}$ について $E[\min(t_1,\dots,t_{2d})^d]< \infty$ であり、$F(0)< p_c(d)$ であるとする。内部が空でなく座標軸について対称な、決定的な凸コンパクト集合 $\mathcal B\subseteq\mathbb R^d$ があって、任意の $\varepsilon>0$ について
$$ P\Bigl((1-\varepsilon)\mathcal B\subseteq\frac{B(t)}t\subseteq(1+\varepsilon)\mathcal B \text{ が十分大きいすべての } t \text{ で成り立つ}\Bigr)=1 $$
である(ADH17 Theorem 2.16、p. 15。この記事では証明しない)。$\mathcal B$ は時間定数 $\mu$ をノルムとする単位球 $\{x\mid\mu(x)\le1\}$ である(同 p. 28)。

形状定理と同じ積率の条件のもとで $F(0)\ge p_c(d)$ なら、どんな有界集合も $B(t)/t$ に最終的に含まれる(同 p. 15、Remark 2.17)。時間定数と同じく、$\mathcal B$ を分布から具体的に求める方法は知られていない。自明でない分布で $\mu(e_1)$ を決定できる例を求めることも、未解決の問題として挙げられている(同 Question 1、p. 11)。

通過時間のゆらぎ

$d=1$ では $T(0,n)$ は独立な変数の和なので、分散は $n$ に比例する。$d\ge2$ でも、分散は高々距離の 1 次で増える。

分散の線形の上界

$0< a\le b< \infty$ とし、確率 $1$ で $a\le\tau_e\le b$ とする。すべての $x\in\mathbb Z^d$ について
$$ \operatorname{Var}T(0,x)\le\frac{b^3}a\lvert x\rvert_1 $$
が成り立つ。

測地線の上の辺だけが分散に効く

$Z:=T(0,x)$ とおく。長さ $\lvert x\rvert_1$ の道があるので $Z\le b\lvert x\rvert_1$ であり、長さ $k$ の道の通過時間は $ak$ 以上なので、通過時間が $Z$ 以下の道の長さは $b\lvert x\rvert_1/a$ 以下である。したがって $Z$ は、$0$ から長さ $b\lvert x\rvert_1/a$ 以下で届く有限個の道の通過時間の最小値であり、その道の上の有限個の辺 $e_1,\dots,e_m$ の通過時間の関数である。最小値をとる道(測地線)がこの有限個の中にあるので、それらの道に順序を固定して最初の測地線を $\Gamma$ とする。$\Gamma$ は $(\tau_{e_1},\dots,\tau_{e_m})$ の関数で、$a\cdot\#\Gamma\le T(\Gamma)=Z\le b\lvert x\rvert_1$ から $\#\Gamma\le(b/a)\lvert x\rvert_1$ である($\#\Gamma$ は辺の数)。
$\tau'_{e_j}$ を $\tau_{e_j}$ の独立な写しとし、$Z^{(j)}$ を $\tau_{e_j}$ だけを $\tau'_{e_j}$ に取り替えた配置での通過時間とする。ジャックナイフ法 の定理「Efron–Stein の不等式」により $\operatorname{Var}Z\le\frac12\sum_{j=1}^mE[(Z-Z^{(j)})^2]$ である。$(Z,Z^{(j)})$ と $(Z^{(j)},Z)$ は同じ分布に従う($\tau_{e_j}$ と $\tau'_{e_j}$ を入れ替える)ので、$E[(Z-Z^{(j)})^2]=E[(Z^{(j)}-Z)_+^2]+E[(Z-Z^{(j)})_+^2]=2E[(Z^{(j)}-Z)_+^2]$ であり、
$$ \operatorname{Var}Z\le\sum_{j=1}^mE\bigl[(Z^{(j)}-Z)_+^2\bigr] $$
である。取り替えた配置で道 $\Gamma$ をたどると $Z^{(j)}\le Z+(\tau'_{e_j}-\tau_{e_j})\mathbf 1\{e_j\in\Gamma\}$ なので、$(Z^{(j)}-Z)_+\le\tau'_{e_j}\mathbf 1\{e_j\in\Gamma\}\le b\,\mathbf 1\{e_j\in\Gamma\}$ である。よって
$$ \operatorname{Var}Z\le b^2\sum_{j=1}^mP(e_j\in\Gamma)=b^2E[\#\Gamma]\le\frac{b^3}a\lvert x\rvert_1 $$
である。$\square$

Kesten は、$E[\tau_e^2]< \infty$、$F(0)< p_c(d)$ で分布が 1 点に集中しないとき、正の定数 $C_1,C_2$ があって、$0$ でないすべての $x$ で $C_1\le\operatorname{Var}T(0,x)\le C_2\lvert x\rvert_1$ であることを示した(ADH17 Theorem 3.1、p. 35)。上の証明はその有界な場合である。$d\ge2$ では、分布についての適当な条件のもとで、一つの辺が測地線に乗る確率が小さいことを使って、分散が $\lvert x\rvert_1/\log\lvert x\rvert_1$ の定数倍で抑えられることが示されている。最初の証明は Benjamini、Kalai、Schramm による、通過時間が 2 つの値を確率 $\frac12$ ずつとる場合のもので、Talagrandの不等式 の型の影響の不等式を使う(同 p. 37)。
ゆらぎの大きさは、$\operatorname{Var}T(0,x)$ がおよそ $\lvert x\rvert_1^{2\chi}$ の大きさであるとして指数 $\chi$ で表される。$d=1$ では $\chi=\frac12$ で、平面では $\chi=\frac13$ と予想されている(同 p. 35)。この値は Kardar、Parisi、Zhang らの物理学の予測による(同 p. 5、p. 32。KPZ方程式 を参照)。しかし $d\ge2$ で $\chi< \frac12$ であることも、平面で $\chi=\frac13$ であることも、未解決の問題として挙げられている(同 Question 13、p. 37)。上の定理が与える $\chi\le\frac12$ は、上界として知られている最良のものである(同 p. 35)。

反例

外した仮定反例成り立たなくなる結論
$E[\tau_e]< \infty$(thm-fpp-time)$s\ge1$ で $P(\tau_e>s)=s^{-1/(2d)}$確率 $1$ で $\limsup_nT(0,ne_1)/n=\infty$ となり、有限の定数に収束しない
通過時間が同じ分布に従う(def-fpp-main)$d=1$、$4^j\le k< 2\cdot4^j$ となる $j\ge0$ があれば $\tau_{\langle k,k+1\rangle}=1$、なければ $2$$T(0,n)/n$ は $\frac43$ と $\frac53$ に近づく部分列をもち、収束しない
$(2d-1)F(0)< 1$(thm-fpp-positive の 1)$d=2$、$\tau_e$ が確率 $0.6$ で $0$、確率 $0.4$ で $1$$\mu\equiv0$ で、$\mu$ はノルムでない
$\tau_e\le b$(thm-fpp-var)$d=1$、$s\ge1$ で $P(\tau_e>s)=s^{-3/2}$$E[\tau_e]=3$ だが、すべての $n\ge1$ で $\operatorname{Var}T(0,n)=\infty$
反例の確かめ

要点:1 行目は遠くの点の周りの辺がすべて長いこと、2 行目は 1 次元の和の直接計算、3 行目は thm-fpp-positive の 2、4 行目は独立な和の分散による。

詳しい確かめを開く

1 行目:$E[\tau_e]=\int_0^\infty P(\tau_e>s)\,ds=\infty$ である。$n\ge1$ について $M_n$ を頂点 $2ne_1$ に接する $2d$ 本の辺の通過時間の最小値とすると、$P(M_n>s)=(s^{-1/(2d)})^{2d}=s^{-1}$($s\ge1$)である。$0$ から $2ne_1$ への道はこれらの辺のどれかを通るので $T(0,2ne_1)\ge M_n$ である。$n\ne m$ なら $2ne_1$ と $2me_1$ の距離は $2$ 以上で接する辺は共通しないので、$M_1,M_2,\dots$ は独立である。$c>0$ について $\sum_{n\ge1/(2c)}P(M_n>2cn)=\sum_{n\ge1/(2c)}\frac1{2cn}=\infty$ なので、Borel–Cantelliの補題 の第 2 の形により、確率 $1$ で無限に多くの $n$ について $T(0,2ne_1)/(2n)>c$ である。$c$ は任意である。

2 行目:$4^j\le k< 2\cdot4^j$ となる $k$ の数は、$i\le j$ について合わせて $\sum_{i=0}^j4^i=(4^{j+1}-1)/3$ である。$T(0,n)=2n-\#\{k< n\mid\tau_{\langle k,k+1\rangle}=1\}$ なので、$n=2\cdot4^j$ では $T(0,n)/n=2-\frac{4^{j+1}-1}{6\cdot4^j}\to\frac43$、$n=4^{j+1}$ では $T(0,n)/n=2-\frac{4^{j+1}-1}{3\cdot4^{j+1}}\to\frac53$ である。

3 行目:$F(0)=0.6>\frac12=p_c(2)$(パーコレーション の定理「Kesten の定理」)なので thm-fpp-positive の 2 により $\mu\equiv0$ である。$(2d-1)F(0)=1.8\ge1$ で、1 の仮定は成り立たない。

4 行目:$E[\tau_e]=1+\int_1^\infty s^{-3/2}\,ds=3$、$E[\tau_e^2]=1+\int_1^\infty2s\cdot s^{-3/2}\,ds=\infty$ である。ex-fpp-one により $T(0,n)$ は $n$ 個の独立な $\tau_e$ の和で、各項の分散が無限なので和の分散も無限である。

歴史と出典

第一通過浸透は Hammersley と Welsh が 1965 年に導入し(ADH17 p. 4)、平面で時間定数の確率収束を示した。Kingman は劣加法的エルゴード定理によって、これを確率 $1$ の収束と $L^1$ の収束に強めた(ADH17 p. 10)。時間定数が正になる条件は Kesten による(同 Theorem 2.5、p. 11)。形状定理は Richardson の結果を Cox と Durrett が改良したもので(同 p. 5、Theorem 2.16)、分散の線形の上界は Kesten の 1993 年の仕事による(同 p. 35)。この記事の thm-fpp-positive と thm-fpp-var の証明は、主張を弱めて初等的に書いたもので、後者は ADH17 pp. 35–36 の Efron–Stein の不等式による筋を、有界な通過時間の場合に完結させたものである。

関連項目

参考文献

[1]
Antonio Auffinger, Michael Damron, Jack Hanson, 50 Years of First-Passage Percolation, University Lecture Series 68, American Mathematical Society, 2017, arXiv 版 v2 の頁で引用。§1(pp. 4–5)、Theorem 2.1(p. 8)、Theorem 2.4(p. 10)、Theorem 2.5・Question 1(p. 11)、Theorem 2.16・Remark 2.17(p. 15)、p. 28、§2.9(p. 32)、§3.1(pp. 34–37、Theorem 3.1・Question 13)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する