Galton–Watson過程(Galton–Watson process)とは、各個体が同じ分布に従う数の子を独立に残すときの、第 $n$ 世代の個体数 $Z_n$ のなす確率過程である。子の数の確率母関数を $G$、平均を $\mu$ とすると、絶滅確率は $G(s)=s$ の $[0,1]$ での最小の解で、自明な場合を除き $\mu\le1$ のとき $1$、$\mu>1$ のとき $1$ より小さい。臨界の $\mu=1$ では、分散が有限なら第 $n$ 世代まで途絶えない確率は $1/n$ の程度に減り、$\mu>1$ では $Z_n/\mu^n$ の極限の非退化性を Kesten–Stigum の定理が決める。
前提知識: 確率母関数, マルチンゲール, Doobのマルチンゲール収束定理, Markov連鎖
Galton–Watson 過程(Galton–Watson process)は、各個体が同じ分布に従う数の子を独立に残し、世代を交代していくときの、第 $n$ 世代の個体数 $Z_n$ のなす確率過程である。家系の途絶え、感染の連鎖、核分裂の連鎖のように、「1 つが独立にいくつかを生む」現象の最も基本的なモデルである。
中心の問いは 2 つある。家系はいつか途絶えるか。途絶えないなら、どれくらいの速さで増えるか。答えは子の数の平均 $\mu$ でほぼ決まる。$\mu\le1$ なら(自明な場合を除いて)確率 $1$ で途絶え、$\mu>1$ なら正の確率で永続して増え続け、子の数の分布の裾が重すぎなければ $\mu^n$ の速さで増える。境目の $\mu=1$ では、個体数の平均は $1$ のままなのに家系は必ず途絶え、分散が有限なら、第 $n$ 世代まで途絶えない確率は $1/n$ の程度になる。
この記事の内容は次のとおりである。
| 結果 | 内容 | 扱い |
|---|---|---|
| prop-gw-moments | 世代の平均と分散 | 証明 |
| thm-gw-extinction | 絶滅確率と $\mu$ による分類 | 証明 |
| thm-gw-critical | 臨界の場合の Kolmogorov の評価と Yaglom の極限 | 証明 |
| thm-gw-l2 | 優臨界の極限 $W$($2$ 次の積率をもつ場合) | 証明 |
| thm-gw-ks | Kesten–Stigum の定理 | 引用 |
確率母関数の側から見た計算(世代の確率母関数が合成になること)は 確率母関数 の節「応用:分枝過程の絶滅確率」にある。この記事はそれを受けて、過程としての振る舞いを主題にする。
$(p_k)_{k\ge0}$ を $\mathbb Z_{\ge0}$ 上の確率分布とする。これを 子の数の分布 という。$\xi$ をこの分布に従う確率変数とし、
$$
G(s):=\sum_{k\ge0}p_ks^k,\qquad\mu:=E[\xi]\in[0,\infty],\qquad\sigma^2:=\operatorname{Var}(\xi)
$$
とおく。$\sigma^2$ は $\mu< \infty$ のときに考える。
$\xi_{n,i}$($n,i\ge1$)を、独立に子の数の分布に従う確率変数の族とする。$Z_0:=1$、
$$
Z_{n+1}:=\sum_{i=1}^{Z_n}\xi_{n+1,i}
$$
で定まる $(Z_n)_{n\ge0}$ を Galton–Watson 過程 という(空の和は $0$)。ある $n$ で $Z_n=0$ となる事象を 絶滅 といい、その確率 $q$ を 絶滅確率 という。
$\mathcal F_n:=\sigma(\xi_{m,i}\mid m\le n,\ i\ge1)$ とする。$\xi_{n+1,i}$ は $\mathcal F_n$ と独立なので、$(Z_n)$ は状態空間 $\mathbb Z_{\ge0}$ の Markov連鎖 で、$0$ は吸収状態である。$G_n$ を $Z_n$ の確率母関数とすると、確率母関数 の定理「世代の大きさの確率母関数」により $G_n=G\circ\cdots\circ G$($n$ 個)である。
個体に家系の番号を付けても同じ法則の過程が作れる。有限列 $u=(u_1,\dots,u_n)$ ごとに独立な $\xi_u$ を用意し、$u$ の子を $(u,1),\dots,(u,\xi_u)$ とする。すると第 1 世代の $Z_1=k$ を与えたとき、$k$ 個の個体のそれぞれから始まる部分木は、独立で、もとの過程と同じ法則に従う。以下の「最初の世代で分ける」議論はこの形で使う。
$\mu< \infty$ なら $E[Z_n]=\mu^n$ である。$\sigma^2< \infty$ なら
$$
\operatorname{Var}(Z_n)=\begin{cases}\sigma^2\mu^{n-1}\dfrac{\mu^n-1}{\mu-1}&(\mu\ne1)\\ n\sigma^2&(\mu=1)\end{cases}
$$
である。
$Z_n=k$ の上で $Z_{n+1}$ は $k$ 個の独立な $\xi$ の和なので、$E[Z_{n+1}\mid\mathcal F_n]=\mu Z_n$、$\operatorname{Var}(Z_{n+1}\mid\mathcal F_n)=\sigma^2Z_n$ である。よって $E[Z_{n+1}]=\mu E[Z_n]$ で、
$$
\operatorname{Var}(Z_{n+1})=E[\sigma^2Z_n]+\operatorname{Var}(\mu Z_n)=\sigma^2\mu^n+\mu^2\operatorname{Var}(Z_n)
$$
である。$\operatorname{Var}(Z_0)=0$ から帰納法で式を得る。$\square$
$\mu=1$ では平均は一定で、分散は $n$ に比例して増える。平均が一定のまま個体数のばらつきが増えることが、次の節の絶滅と両立する。
$p_1< 1$ とする。確率 $1$ で、$Z_n\to0$ または $Z_n\to\infty$ である。
$k\ge1$ とする。$p_0>0$ なら、$Z_n=k$ のとき確率 $p_0^k>0$ で $Z_{n+1}=0$ となり、$0$ からは戻らない。$p_0=0$ なら $Z$ は非減少で、$Z_n=k$ のとき確率 $1-p_1^k>0$ で $Z_{n+1}>k$ となり、$k$ へは戻らない。どちらの場合も、状態 $k$ を訪れるたびに、確率 $\delta_k>0$ 以上で二度と戻らない。よって $k$ を $m$ 回以上訪れる確率は $(1-\delta_k)^{m-1}$ 以下で、$k$ を無限回訪れる確率は $0$ である。可算個の $k\ge1$ について合わせると、$Z_n$ は確率 $1$ でどの $k\ge1$ にも有限回しかいない。$0$ は吸収状態なので、$Z_n\to0$ または $Z_n\to\infty$ である。$\square$
1。 $q_n:=P(Z_n=0)=G_n(0)$ とおく。絶滅の事象は増大する事象 $\{Z_n=0\}$ の和なので $q_n\uparrow q$ である。$q_{n+1}=G(q_n)$ で $G$ は連続なので $q=G(q)$ である。$r\in[0,1]$ が $G(r)=r$ を満たすなら、$G$ は単調なので、$q_0=0\le r$ から帰納法で $q_n\le r$ で、$q\le r$ である。
$\mu< 1$ の場合。 Markovの不等式 から $P(Z_n>0)\le E[Z_n]=\mu^n\to0$ である。よって $q=1$ である。
$\mu=1$、$p_1< 1$ の場合。 $Z_n$ は $0$ 以上のマルチンゲールなので、Doobのマルチンゲール収束定理 により確率 $1$ で有限の極限をもつ。lem-gw-dichotomy から $Z_n\to\infty$ の確率は $0$ なので、$Z_n\to0$ である。よって $q=1$ である。
$\mu>1$ の場合。 $G'(s)=\sum_kkp_ks^{k-1}\uparrow\mu$($s\uparrow1$)なので、$G'>1$ が $[s_0,1)$ で成り立つ $s_0< 1$ がある。平均値の定理 から $G(s_0)< s_0$ である($G(1)=1$)。$G(0)\ge0$ なので、中間値の定理 により $[0,s_0)$ に解がある。1 から $q< 1$ である。$\mu>1$ なら $p_k>0$ となる $k\ge2$ があり、$G$ は $(0,1)$ で狭義凸である。狭義凸な関数と直線 $y=s$ は高々 2 点でしか交わらず、$s=1$ が 1 つなので、$[0,1)$ の解は 1 つである。
3。 lem-gw-dichotomy から、$Z_n\to0$ でない事象の上で $Z_n\to\infty$ である。$\square$
$\mu=1$ の場合に上ではマルチンゲールの収束を使った。確率母関数 の定理「絶滅確率」は同じ結論を凸性だけで導いている。
$\mu>1$ で $Z_0=k$ から始めると、$k$ 本の家系が独立なので絶滅確率は $q^k$ である。$q^{Z_n}$ はマルチンゲールである。実際、$E[q^{Z_{n+1}}\mid\mathcal F_n]=G(q)^{Z_n}=q^{Z_n}$ である。
子の数の分布は $\mu$ によって次の 3 つに分かれる($p_1< 1$ とする)。
| 区分 | $\mu$ | 絶滅確率 | $E[Z_n]$ | $P(Z_n>0)$ の振る舞い |
|---|---|---|---|---|
| 劣臨界 | $\mu< 1$ | $1$ | $\mu^n\to0$ | $\mu^n$ 以下で減る |
| 臨界 | $\mu=1$ | $1$ | $1$ | $\sigma^2< \infty$ なら $2/(\sigma^2n)$ に漸近する |
| 優臨界 | $\mu>1$ | $< 1$ | $\mu^n\to\infty$ | $1-q>0$ に減少して収束する |
$\mu=1$、$0< \sigma^2< \infty$ とする。
$s\in[0,1)$ について
$$
\phi(s):=\frac1{1-G(s)}-\frac1{1-s}
$$
とおく。
段 1:$s\uparrow1$ で $\phi(s)\to\sigma^2/2$。 $u:=1-s$ とする。$G(1)=1$、$G'(1-)=1$ と Taylor の公式の積分形から
$$
G(1-u)=1-u+r(u),\qquad r(u):=\int_{1-u}^1\bigl(t-(1-u)\bigr)G''(t)\,dt
$$
である。$G''(t)=\sum_kk(k-1)p_kt^{k-2}$ は $t\uparrow1$ で $E[\xi(\xi-1)]=\sigma^2$ に単調に増加するので、$r(u)/u^2\to\sigma^2/2$ である。$r(u)< u$ に注意すると
$$
\phi(s)=\frac1{u-r(u)}-\frac1u=\frac{r(u)}{u(u-r(u))}\to\frac{\sigma^2}2
$$
である。
段 2:一様な Cesàro 平均。 $s\in[0,1)$ について、$\phi$ の定義を $G_k(s)$ に当てて足すと
$$
\frac1{1-G_n(s)}-\frac1{1-s}=\sum_{k=0}^{n-1}\phi(G_k(s))
$$
である。thm-gw-extinction から $q=1$ なので、$G_k(0)\uparrow1$ である。$G_k(0)\le G_k(s)< 1$ なので、$G_k(s)\to1$ は $s$ について一様である。段 1 と $\phi$ の有界性から、$s\in[0,1)$ について一様に
$$
\frac1{n}\Bigl(\frac1{1-G_n(s)}-\frac1{1-s}\Bigr)\to\frac{\sigma^2}2
$$
である。
1。 $s=0$ とすると $\frac1{nP(Z_n>0)}\to\frac{\sigma^2}2$ である。
2。 $\lambda>0$、$s_n:=e^{-\lambda/n}$ とする。$n(1-s_n)\to\lambda$ なので、段 2 の式は $\frac1{n(1-G_n(s_n))}\to\frac1\lambda+\frac{\sigma^2}2$ を与える。よって
$$
E\bigl[e^{-\lambda Z_n/n}\bigm|Z_n>0\bigr]=1-\frac{1-G_n(s_n)}{1-G_n(0)}\to1-\frac{\sigma^2/2}{1/\lambda+\sigma^2/2}=\frac1{1+\lambda\sigma^2/2}
$$
である。右辺は平均 $\sigma^2/2$ の指数分布の Laplace 変換である。Laplace 変換の連続性定理から結論を得る。$\square$
$Z_n>0$ のとき $Z_n$ は $n$ の程度の大きさになる。$E[Z_n]=1$ を保っているのは、確率 $2/(\sigma^2n)$ の生存と、大きさ $\sigma^2n/2$ の積である。
$0< \mu< 1$ とする。$P(Z_n>0)/\mu^n$ は $n$ について減少する。その極限が正であることと $E[\xi\log^+\xi]< \infty$ は同値である。
減少することは、$s\mapsto(1-G(s))/(1-s)$ が凸性から増加で、$s\uparrow1$ で $\mu$ に近づくので、$1-G_{n+1}(0)\le\mu(1-G_n(0))$ となることから分かる。同値性は Heathcote、Seneta、Vere-Jones の定理で、LPP95 Theorem B にある。この記事では証明しない。
$\mu\in(1,\infty)$ とする。$W_n:=Z_n/\mu^n$ は $E[Z_{n+1}\mid\mathcal F_n]=\mu Z_n$ から $0$ 以上のマルチンゲールである(Dur19 Lemma 4.3.9)。よって確率 $1$ で極限 $W:=\lim_nW_n$ が存在する。
$1< \mu< \infty$、$\sigma^2< \infty$ とする。
1:マルチンゲールの増分は直交する。$E[(Z_{n+1}-\mu Z_n)^2\mid\mathcal F_n]=\sigma^2Z_n$ なので
$$
E[(W_{n+1}-W_n)^2]=\mu^{-2n-2}\sigma^2E[Z_n]=\sigma^2\mu^{-n-2}
$$
である。和は $\sum_{n\ge0}\sigma^2\mu^{-n-2}=\sigma^2/(\mu^2-\mu)< \infty$ なので、$(W_n)$ は $L^2$ の Cauchy 列である。$L^2$ の極限は概収束の極限 $W$ と一致する。よって $E[W]=\lim E[W_n]=1$、$\operatorname{Var}(W)=\lim\operatorname{Var}(W_n)=\sigma^2/(\mu^2-\mu)$ である。
2:$r:=P(W=0)$ とおく。rem-gw-branching から $W=\mu^{-1}\sum_{i\le Z_1}W^{(i)}$ である。$W^{(i)}$ は $Z_1$ を与えたとき独立で、$W$ と同じ法則に従う。よって $W=0$ は、すべての $W^{(i)}$ が $0$ であることと同値で、$r=E[r^{Z_1}]=G(r)$ である。$E[W]=1$ から $r< 1$ なので、thm-gw-extinction の 2 から $r=q$ である。絶滅の事象は $\{W=0\}$ に含まれ、確率が等しいので、2 つの事象は確率 $0$ を除いて一致する。$\square$
どこまで積率を弱められるかは、次の定理で完全に分かっている。
$1< \mu< \infty$ とする。次は同値である。
1〜3 の同値は LPP95 Theorem A にある。Dur19 Theorem 4.3.13 は、$W$ が恒等的に $0$ でないことと 3 の同値を述べている。この記事では証明しない。最後の文は、$r=P(W=0)$ が $G(r)=r$ を満たすので $r\in\{q,1\}$ となることから分かる(prf-gw-l2 の 2 の前半は $\sigma^2$ を使っていない)。つまり極限は $0$ 以外の確率変数か、常に $0$ かのどちらかである。後者でも、永続する事象の上で $\frac1n\log Z_n\to\log\mu$ が成り立つ(LPP95 §1)。$\mu^n$ の正規化だけが合わないのである。
$0< a< 1$ とし、$p_k=(1-a)a^k$ とする。$G(s)=(1-a)/(1-as)$ は 1 次分数関数で、$\mu=a/(1-a)$、$\sigma^2=\mu(1+\mu)$ である。
$\mu\ne1$ のとき、$G(s)=s$ の解は $1$ と $r:=1/\mu$ で、$w(s):=(s-r)/(s-1)$ とおくと、直接の計算で $w\circ G=\mu^{-1}w$ である。反復すると $w(G_n(s))=\mu^{-n}w(s)$ である。$s=0$ を代入して解くと
$$
P(Z_n>0)=\frac{\mu^n(\mu-1)}{\mu^{n+1}-1}
$$
である。$\mu=1$($a=\frac12$)では $G_n(s)=\frac{n-(n-1)s}{n+1-ns}$ で、$P(Z_n>0)=\frac1{n+1}$ である。これは $\sigma^2=2$ の thm-gw-critical の 1 と合う。$\mu>1$ では $q=1/\mu$ である。
さらに $\mu>1$ で $s=e^{-\lambda\mu^{-n}}$ とおくと、$w(s)\sim-(1-r)\mu^n/\lambda$ から
$$
E[e^{-\lambda W}]=\lim_nG_n(e^{-\lambda\mu^{-n}})=r+(1-r)\frac{1-r}{\lambda+1-r}
$$
である。すなわち $W$ は、確率 $q=r$ で $0$、確率 $1-r$ で平均 $\mu/(\mu-1)$ の指数分布である。分散は $(\mu+1)/(\mu-1)$ で、thm-gw-l2 の式 $\sigma^2/(\mu^2-\mu)$ と一致する。
$T:=\sum_{n\ge0}Z_n$ を全世代の個体数とし、$H(s):=E[s^T;T< \infty]$ とおく。rem-gw-branching から $T=1+\sum_{i\le Z_1}T^{(i)}$ なので、$H(s)=sG(H(s))$ である。$\mu< 1$ なら $E[T]=\sum_n\mu^n=1/(1-\mu)$ である。
$p_0=p_2=\frac12$(臨界)とする。$H=\frac s2(1+H^2)$ を解くと $H(s)=(1-\sqrt{1-s^2})/s$ で、Catalan数 $C_n$ について
$$
P(T=2n+1)=\frac{C_n}{2^{2n+1}}
$$
である。$2n+1$ 頂点の二分木の数が $C_n$ で、各木の確率が $2^{-2n-1}$ であることと同じである。$H(1)=1$ なので $T$ は確率 $1$ で有限だが、$E[T]=\sum_nE[Z_n]=\infty$ である。
$\xi$ が平均 $c>1$ の Poisson分布 に従うなら、$G(s)=e^{c(s-1)}$ で、生存確率 $\rho:=1-q$ は $1-\rho=e^{-c\rho}$ の正の解である。$c=2$ なら $\rho=0.7968\ldots$ である。平均 $c$ の感染の連鎖で、最初の 1 人から大きな流行になる確率がこの $\rho$ である。
| 主張 | 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|---|
| $\mu\le1$ なら絶滅 | $p_1< 1$ | $p_1=1$ | $\mu=1$ だが $Z_n\equiv1$、$q=0$ |
| $\mu>1$ なら永続しうる | 兄弟の独立性 | 同じ世代の全員が同じ数 $\eta_n$ の子を残す。$\eta_n$ は独立で $P(\eta_n=0)=P(\eta_n=3)=\frac12$ | $\mu=\frac32$ だが $q=1$ |
| $\mu\le1$ なら絶滅 | 世代による同分布 | 世代 $n$ の子の数が確率 $2^{-n-1}$ ずつで $0$ と $2$、残りで $1$ | 各世代の平均は $1$ だが $q< 1$ |
| thm-gw-l2 の $W$ の非退化 | $E[\xi\log^+\xi]< \infty$ | $k\ge3$ で $p_k$ が $1/(k\log k)^2$ に比例 | $\mu< \infty$ だが $W=0$(確率 $1$) |
| thm-gw-critical の $1/n$ の速さ | $\sigma^2< \infty$ | $G(s)=s+\frac{(1-s)^{1+\alpha}}{1+\alpha}$($0< \alpha< 1$) | $P(Z_n>0)$ は $n^{-1/\alpha}$ の程度 |
| $W_n$ の $L^1$ 収束 | $\mu>1$ | $\mu=1$、$p_1< 1$ | $W_n=Z_n\to0$ だが $E[W_n]=1$ |
兄弟の独立性。 $Z_{n+1}=Z_n\eta_{n+1}$ である。$Z_n>0$ であるためには $\eta_1,\dots,\eta_n$ がすべて $3$ でなければならず、その確率は $2^{-n}\to0$ である。平均は $E[Z_n]=(3/2)^n$ で増える。
世代による同分布。 どの個体も子が 1 人である確率が世代 $n$ で $1-2^{-n}$ なので、家系が 1 本の線のまま続く確率は $\prod_{n\ge1}(1-2^{-n})>0$ である。
Kesten–Stigum の条件。 $\sum_kk\cdot1/(k\log k)^2=\sum_k1/(k(\log k)^2)< \infty$ で、$\sum_kk\log k/(k\log k)^2=\sum_k1/(k\log k)=\infty$ である。台が $k\ge3$ なので $\mu\ge3$ である。thm-gw-ks から $W=0$ である。
無限分散。 $(1-s)^{1+\alpha}$ の係数は、$s^1$ を除いて正なので、$G$ の係数はすべて $0$ 以上で、$p_0=1/(1+\alpha)$、$p_1=0$ である。$G(1)=1$、$G'(1-)=1$ で $G''(1-)=\infty$ である。$u_n:=1-G_n(0)$ は $u_{n+1}=u_n-u_n^{1+\alpha}/(1+\alpha)$ を満たす。$u_n\to0$ で、$u_{n+1}^{-\alpha}-u_n^{-\alpha}\to\alpha/(1+\alpha)$ なので、$u_n\sim\bigl((1+\alpha)/(\alpha n)\bigr)^{1/\alpha}$ である。
過程の名は、家名が途絶える確率の問題を考えた Galton と Watson による(Dur19 第 4.3 節の演習の記述)。$2$ 次の積率のもとの thm-gw-l2 は Dur19 Example 4.4.9 にある。thm-gw-critical の 1 と 2 は、$3$ 次の積率のもとでそれぞれ Kolmogorov(1938 年)と Yaglom(1947 年)が示し、$2$ 次の積率のもとでは Kesten、Ney、Spitzer(1966 年)が示した(LPP95 Theorem C)。ここの証明は、$1/(1-G_n)$ の差を見る形で書いた。LPP95 は Kesten–Stigum の定理などを、大きさで偏らせた木との比較から示している。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する