Kingman合体過程

同義語:Kingman coalescentKingmanの合体過程

概要

Kingman合体過程(Kingman coalescent)とは、ブロックが $k$ 個のとき $\binom k2$ 個の対のそれぞれが率 $1$ で合わさる、集合の分割に値をとる Markov 過程である。$n$ 個から始めた $n$-合体過程を $\{1,\dots,m\}$ に制限すると $m$-合体過程になり、この整合性から自然数全体の分割に値をとる過程が定まる。この過程は無限個のブロックから始まっても正の時刻ではブロックが有限個で、$t\downarrow0$ でその数と $2/t$ の比は $1$ に確率収束する。すべての系統が合わさるまでの時間の平均は $2(1-1/n)$ で、Wright–Fisher 模型の標本の系譜は時間を集団の大きさで縮めるとこの過程に近づく。

$$\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}} $$

前提知識: Markov連鎖, 指数分布, Kolmogorovの拡張定理

Kingman合体過程(Kingman coalescent)は、ブロックの数が $k$ のとき、$\binom k2$ 個のブロックの対のそれぞれが率 $1$ で合わさっていく、集合の分割に値をとる連続時間の Markov 過程である。集団遺伝学で、いま採った標本の個体の祖先を過去へたどるとき、2 本の系統が共通の祖先に行き着く(合体する)様子の極限の模型として、J. F. C. Kingman が 1982 年に導入した。エルゴード理論の Kingmanの劣加法的エルゴード定理 とは別の対象である。
$n$ 個の標本から始めたものを $n$-合体過程という。$n$-合体過程を $\{1,\dots,m\}$($m\le n$)に制限すると $m$-合体過程になる(thm-kc-consistent)。この整合性により、自然数全体の分割に値をとる無限の合体過程が定まり、無限個のブロックから始めても、正の時刻ではブロックの数が有限になる(無限からの降下、thm-kc-cdi)。また Wright–Fisher 模型の標本の系譜は、時間を集団の大きさで縮めると $n$-合体過程に近づく(thm-kc-wf)。この記事ではこれらと、すべての系統が合体するまでの時間の平均 $2(1-1/n)$(cor-kc-tmrca)、突然変異を載せたときの Ewens の分布(prop-kc-ewens)を証明する。

定義

$[n]:=\{1,\dots,n\}$ とし、$[n]$ の分割(互いに素な空でない部分集合(ブロック)への分け方)全体を $\mathcal P_n$ と書く。$\pi\in\mathcal P_n$ のブロックの数を $\#\pi$ とし、すべてのブロックが 1 点である分割を $\mathbf 0_n$ と書く。$\pi'$ が $\pi$ の 2 つのブロックを合わせて得られるとき $\pi\to\pi'$ と書く。

$n$-合体過程

$\mathcal P_n$ 上の行列 $Q_n$ を、$\pi\to\pi'$ なら $Q_n(\pi,\pi')=1$、$Q_n(\pi,\pi)=-\binom{\#\pi}2$、それ以外は $0$ で定める。$Q_n$ を率の行列とし $\mathbf 0_n$ から出る連続時間の Markov連鎖 $(\Pi^{(n)}_t)_{t\ge0}$ を $n$-合体過程 という。推移確率は $P(\Pi^{(n)}_{t+s}=\pi'\mid\Pi^{(n)}_s=\pi)=e^{tQ_n}(\pi,\pi')$ である(有限状態の連鎖については Feller過程 の系「有限状態の場合」)。

$\mathcal P_n$ は有限集合なので、この連鎖は次のように作れる。ブロックが $k\ge2$ 個の状態では、平均 $1/\binom k2$ の指数分布に従う時間だけ待ち、$\binom k2$ 個の対から一様に選んだ対を合わせる。待ち時間と選び方は互いに独立で、過去とも独立である。ブロックが 1 個になると止まる。

ブロックの数と合体までの時間

ブロックの数は純粋な死滅過程

$N^{(n)}_t:=\#\Pi^{(n)}_t$ とし、ブロックの数が $k$ である時間の長さを $T_k$($2\le k\le n$)とする。$T_n,\dots,T_2$ は独立で、$T_k$ は平均 $1/\binom k2$ の指数分布に従う。さらに、合体の順の列(跳躍の連鎖)は $(T_k)$ と独立で、各段で合わさる対は、そのときのブロックの対から一様に選ばれる。

上の作り方で、状態 $\pi$ から出る率の和は $\binom{\#\pi}2$ で、$\#\pi$ だけで決まる。ブロックが $k$ 個の状態にいる時間は平均 $1/\binom k2$ の指数分布に従い、次の状態の選び方と独立である。ブロックの数は跳ぶたびにちょうど 1 減るので、$N^{(n)}$ は $n,n-1,\dots,1$ と順に下がり、$k$ 個の段の滞在時間が $T_k$ である。連続時間の Markov 連鎖の強 Markov 性により、各段の滞在時間と選び方は、それまでの経過と独立である。待ち時間の分布が状態の中身によらないので、$(T_k)$ 全体が跳躍の連鎖と独立になる。$\square$

すべての標本の系統が 1 つに合わさる時刻(最も近い共通祖先までの時間)を $T_{\mathrm{MRCA}}:=\inf\{t\mid N^{(n)}_t=1\}=\sum_{k=2}^nT_k$ とおく。系図の枝の長さの合計は、ブロックが $k$ 個の間に $k$ 本の枝が伸びるので $L_n:=\sum_{k=2}^nkT_k$ である。

合体までの時間と枝の長さ

$$ E[T_{\mathrm{MRCA}}]=2\Bigl(1-\frac1n\Bigr),\qquad \operatorname{Var}(T_{\mathrm{MRCA}})=\sum_{k=2}^n\frac{4}{k^2(k-1)^2},\qquad E[L_n]=2\sum_{j=1}^{n-1}\frac1j $$
である。とくに $n$ によらず $E[T_{\mathrm{MRCA}}]< 2$ で、最後の 2 本が合わさる時間 $T_2$ の平均 $1$ が全体の平均の半分以上を占める。

prop-kc-count により $E[T_k]=\frac2{k(k-1)}=2\bigl(\frac1{k-1}-\frac1k\bigr)$ で、$k=2,\dots,n$ について足すと和は畳み込まれて $2(1-\frac1n)$ になる。独立性から分散は $\operatorname{Var}(T_k)=E[T_k]^2=\frac4{k^2(k-1)^2}$ の和である。$E[kT_k]=\frac2{k-1}$ を足せば $E[L_n]$ を得る。$\square$

$n\to\infty$ で分散は $4\sum_{k\ge2}\frac1{k^2(k-1)^2}=\frac{4\pi^2}3-12\approx1.16$ に近づく($\frac1{k^2(k-1)^2}=\frac1{(k-1)^2}+\frac1{k^2}-\frac2{k-1}+\frac2k$ による)。

整合性と無限の合体過程

$m\le n$ のとき、$\pi\in\mathcal P_n$ の $[m]$ への制限を $r_{n,m}(\pi):=\{B\cap[m]\mid B\in\pi,\ B\cap[m]\ne\emptyset\}\in\mathcal P_m$ とおく。次の補題は、Markov 連鎖の関数がふたたび Markov 連鎖になる十分条件である。

連鎖をまとめる

$S,S'$ を有限集合、$Q$ を $S$ 上の率の行列、$r:S\to S'$ を全射、$Q'$ を $S'$ 上の率の行列とする。すべての $x\in S$ と $y'\ne r(x)$ について
$$ \sum_{y\in S,\ r(y)=y'}Q(x,y)=Q'(r(x),y') $$
が成り立つなら、$Q$ の連鎖 $X$ について $r(X)$ は、$r(X_0)$ の分布から出る $Q'$ の連鎖と同じ有限次元分布をもつ。

行列の交換関係

$R(x,y'):=\mathbf 1\{r(x)=y'\}$ とおく。仮定は $(QR)(x,y')=Q'(r(x),y')$($y'\ne r(x)$)である。$y'=r(x)$ のときは、率の行列の行の和が $0$ であることを $Q$ と $Q'$ に使い、仮定を $y'\ne r(x)$ について足すと
$$ (QR)(x,r(x))=-\sum_{y:\,r(y)\ne r(x)}Q(x,y)=-\sum_{y'\ne r(x)}Q'(r(x),y')=Q'(r(x),r(x)) $$
である。よって $QR=RQ'$ で、帰納的に $Q^jR=RQ'^j$、級数で $e^{tQ}R=Re^{tQ'}$ を得る。$0< t_1< \dots< t_k$、$y_1,\dots,y_k\in S'$ とし、$s_j:=t_j-t_{j-1}$($t_0=0$)、$P'_s:=e^{sQ'}$ とおく。$h(x):=R(x,y_k)$ に $e^{s_kQ}$ を当てると $e^{s_kQ}R=Re^{s_kQ'}$ から $x\mapsto P'_{s_k}(r(x),y_k)$ で、これに $R(x,y_{k-1})$ を掛けると $R(x,y_{k-1})P'_{s_k}(y_{k-1},y_k)$ になる。これを $j=k,k-1,\dots,1$ と繰り返せば
$$ P\bigl(r(X_{t_1})=y_1,\dots,r(X_{t_k})=y_k\bigr)=\sum_{y_0\in S'}P(r(X_0)=y_0)\prod_{j=1}^kP'_{s_j}(y_{j-1},y_j) $$
で、右辺は $Q'$ の連鎖の有限次元分布である。$\square$

整合性

$m\le n$ とする。$n$-合体過程の制限 $\bigl(r_{n,m}(\Pi^{(n)}_t)\bigr)_{t\ge0}$ は、$m$-合体過程と同じ有限次元分布をもつ。

lem-kc-lump の仮定を $r=r_{n,m}$、$Q=Q_n$、$Q'=Q_m$ について確かめる。$\pi\in\mathcal P_n$、$\sigma:=r_{n,m}(\pi)$ とする。$\pi$ のブロックのうち $[m]$ と交わるもの(見えるブロック)は、$B\mapsto B\cap[m]$ により $\sigma$ のブロックと 1 対 1 に対応する。$\pi$ の 2 つのブロックを合わせる遷移は、両方が見えるブロックなら $\sigma$ の対応する 2 つのブロックを合わせた分割に写り、少なくとも一方が見えないなら制限は $\sigma$ のまま変わらない。よって $\sigma'\ne\sigma$ について、$r_{n,m}(\pi')=\sigma'$ となる $\pi\to\pi'$ は、$\sigma\to\sigma'$ のときちょうど 1 つ(対応する 2 つの見えるブロックを合わせるもの)で率は $1=Q_m(\sigma,\sigma')$、それ以外のときは無く $0=Q_m(\sigma,\sigma')$ である。$r_{n,m}(\mathbf 0_n)=\mathbf 0_m$ なので、主張は lem-kc-lump から従う。$\square$

自然数全体の分割の集合を $\mathcal P_\infty$ とし、$\pi\in\mathcal P_\infty$ の $[n]$ への制限を $\pi|_{[n]}$ と書く。分割は制限の列 $(\pi|_{[n]})_{n\ge1}$ で決まり、整合的な列($r_{n+1,n}(\pi_{n+1})=\pi_n$)はただ 1 つの $\pi\in\mathcal P_\infty$ から来る($i\sim j$ を $i,j\le n$ となる $n$ での $\pi_n$ で定めればよい)。

Kingman 合体過程

$\mathcal P_\infty$ に値をとる過程 $(\Pi_t)_{t\ge0}$ で、各 $n$ について $(\Pi_t|_{[n]})_{t\ge0}$ が $n$-合体過程と同じ有限次元分布をもつものを Kingman 合体過程 という。

有限個の時刻の組 $J$ ごとに、$(\Pi^{(n)}_t)_{t\in J}$ の分布の族は thm-kc-consistent により $n$ について整合的なので、Kolmogorovの拡張定理 により $\mathcal P_\infty^J$ 上の分布が定まる。これらは $J$ についても整合的なので、もう一度拡張定理を使えば Kingman 合体過程の有限次元分布の族が得られ、その分布はただ 1 つに決まる。

無限からの降下

$\#\pi$ を $\pi\in\mathcal P_\infty$ のブロックの数($\infty$ もとりうる)とする。時刻 $0$ ではブロックは無限個ある。

無限からの降下

$(\Pi_t)$ を Kingman 合体過程とし、$N_t:=\#\Pi_t$ とおく。$(T_j)_{j\ge2}$ を、$T_j$ が平均 $1/\binom j2$ の指数分布に従う独立な列とし、$S_k:=\sum_{j>k}T_j$ とおく。

  1. $t>0$、$k\ge1$ について $P(N_t>k)=P(S_k>t)$ である。とくに $t>0$ なら確率 $1$ で $N_t< \infty$ である。
  2. $t\downarrow0$ のとき $tN_t\to2$(確率収束)である。
制限のブロック数の増加極限

1. $\pi\in\mathcal P_\infty$ について、$\#(\pi|_{[n]})$ は $n$ について単調非減少で、$\#\pi$ に増加収束する($\pi$ のブロックが $k$ 個以上なら、そのうち $k$ 個は十分大きな $n$ ですべて $[n]$ と交わる)。よって $\{N_t>k\}$ は事象 $\{\#(\Pi_t|_{[n]})>k\}$ の $n$ についての増加和である。$n>k$ のとき、$n$-合体過程のブロックの数が時刻 $t$ に $k$ より大きいことは、$n$ 個から $k$ 個に減るまでの時間 $T_n+\dots+T_{k+1}$ が $t$ を超えることと同じなので、prop-kc-count により $P(\#(\Pi_t|_{[n]})>k)=P(\sum_{j=k+1}^nT_j>t)$ である。$n\to\infty$ とすれば、部分和は $S_k$ に増加し $\{\sum_{j=k+1}^nT_j>t\}$ は $\{S_k>t\}$ に増加するので、$P(N_t>k)=P(S_k>t)$ を得る。$E[S_k]=\sum_{j>k}\frac2{j(j-1)}=\frac2k$ なので、Markov の不等式により $P(N_t>k)\le\frac2{kt}\to0$($k\to\infty$)である。
2. $\frac1{j^2(j-1)^2}\le\frac1{(j-1)^4}$ と $\sum_{i\ge k}i^{-4}\le k^{-4}+\int_k^\infty x^{-4}dx\le2k^{-3}$ から、$\operatorname{Var}(S_k)=\sum_{j>k}\frac4{j^2(j-1)^2}\le\frac8{k^3}$ である。$0< \varepsilon< 1$ とする。
上側:$k:=\lfloor2(1+\varepsilon)/t\rfloor$ とおくと、$tN_t>2(1+\varepsilon)$ なら $N_t>k$ で、また $t>\frac{2(1+\varepsilon)}{k+1}$ である。$k\ge1+2/\varepsilon$ なら $\frac{2(1+\varepsilon)}{k+1}-\frac2k=\frac{2\varepsilon k-2}{k(k+1)}\ge\frac\varepsilon k$ なので、1 と Chebyshev の不等式により
$$ P\bigl(tN_t>2(1+\varepsilon)\bigr)\le P\Bigl(S_k-\frac2k>\frac\varepsilon k\Bigr)\le\frac{8/k^3}{(\varepsilon/k)^2}=\frac8{\varepsilon^2k} $$
である。
下側:$x:=2(1-\varepsilon)/t$、$k:=\lceil x\rceil-1$ とおくと、$tN_t< 2(1-\varepsilon)$ なら $N_t\le k$ で、$k< x$ から $t< \frac{2(1-\varepsilon)}k$ である。よって
$$ P\bigl(tN_t< 2(1-\varepsilon)\bigr)\le P(S_k\le t)\le P\Bigl(S_k-\frac2k\le-\frac{2\varepsilon}k\Bigr)\le\frac{8/k^3}{(2\varepsilon/k)^2}=\frac2{\varepsilon^2k} $$
である。$t\downarrow0$ でどちらの $k$ も $\infty$ に発散するので、両方の確率は $0$ に近づく。$\square$

時刻 $0$ で無限個あったブロックが、どんなに短い時間でも有限個に減る。これは対の数 $\binom k2$ が $k$ の 2 乗で増え、$\sum_k1/\binom k2$ が収束することによる。$N_t\approx2/t$ は、平均の挙動 $\frac{d}{dt}N=-\binom N2\approx-\frac{N^2}2$ の解 $N=2/t$ と一致する。

Wright–Fisher 模型の系譜

大きさ $N$ の集団が世代ごとに入れ替わり、各個体は前の世代の $N$ 個体から親を一様に、ほかの個体と独立に選ぶとする(Wright–Fisher 模型)。現在の世代の個体 $1,\dots,n$($n\le N$)を標本とし、$r$ 世代さかのぼって同じ祖先をもつ標本どうしを同じブロックに入れた分割を $A^N_r\in\mathcal P_n$ とおく($A^N_0=\mathbf 0_n$)。世代ごとの親の選び方が独立なので、$(A^N_r)_{r\ge0}$ は $\mathcal P_n$ 上の離散時間の Markov 連鎖で、ブロックが $k$ 個の状態からの推移は、$k$ 個の異なる祖先がそれぞれ独立に一様に親を選び、同じ親を選んだブロックを合わせることで起こる。

Wright–Fisher 模型の系譜の極限

$n$ を固定する。$0\le t_1< \dots< t_k$ について、$N\to\infty$ のとき $(A^N_{\lfloor Nt_1\rfloor},\dots,A^N_{\lfloor Nt_k\rfloor})$ は $(\Pi^{(n)}_{t_1},\dots,\Pi^{(n)}_{t_k})$ に分布収束する。すなわち時間を $N$ 世代を単位に測ると、標本の系譜は $n$-合体過程に近づく。

推移行列を $I+Q_n/N$ と比べる

$P_N$ を $(A^N_r)$ の推移行列とし、$\pi$ のブロックの数を $k$ とする。$a_i\in[0,1]$ について $\bigl\lvert\prod_i(1-a_i)-1+\sum_ia_i\bigr\rvert\le\frac12(\sum_ia_i)^2$ である($\prod_i(1-a_i)$ を $a$ の多項式として、帰納法で示せる)。

  • $P_N(\pi,\pi)$ は $k$ 個の親がすべて異なる確率 $\prod_{i=0}^{k-1}(1-\frac iN)$ で、$\sum_i\frac iN=\binom k2/N$ から $\lvert P_N(\pi,\pi)-1+\binom k2/N\rvert\le\binom k2^2/N^2$ である。
  • $\pi\to\pi'$ で、合わさる 2 つのブロックが決まっているとき、$P_N(\pi,\pi')$ はその 2 つの親が等しく、残りの $k-2$ 個の親が互いにもそれとも異なる確率 $\frac1N\prod_{i=1}^{k-2}(1-\frac iN)$ で、$\lvert P_N(\pi,\pi')-\frac1N\rvert\le\binom k2/N^2$ である。
  • それ以外の $\pi'$ への推移には、親の一致が 2 組以上(異なる 2 つの対がそれぞれ一致)必要である。異なる 2 つの対が両方一致する確率は、対が交わらなくても 1 点を共有しても $1/N^2$ なので、合計は $\binom{\binom k2}2/N^2$ 以下である。
    よって $P_N=I+Q_n/N+E_N/N^2$ で、$E_N$ の成分は $N$ によらない定数 $c_n$ で押さえられる。行列のノルムを行の絶対値の和の最大値とし、$B_N:=e^{Q_n/N}$ とおく。$P_N$ と $B_N$ は確率行列なのでノルムは $1$ で、$e^{Q_n/N}-I-Q_n/N=\sum_{j\ge2}(Q_n/N)^j/j!$ から $\| P_N-B_N\|\le c'_n/N^2$ である。$P_N^m-B_N^m=\sum_{i=0}^{m-1}P_N^i(P_N-B_N)B_N^{m-1-i}$ により
    $$ \| P_N^m-B_N^m\|\le\frac{mc'_n}{N^2} $$
    である。$s\ge0$ と、$m_N/N\to s$ を満たす整数の列 $m_N$ について、$\| P_N^{m_N}-B_N^{m_N}\|\to0$ で、$B_N^{m_N}=e^{(m_N/N)Q_n}\to e^{sQ_n}$ である。$m_N:=\lfloor Nt_j\rfloor-\lfloor Nt_{j-1}\rfloor$($t_0=0$)とおけば $m_N/N\to t_j-t_{j-1}$ なので、$A^N_0=\mathbf 0_n$ から
    $$ P\bigl(A^N_{\lfloor Nt_j\rfloor}=\pi_j\ (j\le k)\bigr)=\prod_{j=1}^kP_N^{\lfloor Nt_j\rfloor-\lfloor Nt_{j-1}\rfloor}(\pi_{j-1},\pi_j)\to\prod_{j=1}^ke^{(t_j-t_{j-1})Q_n}(\pi_{j-1},\pi_j) $$
    ($\pi_0=\mathbf 0_n$)であり、右辺は $n$-合体過程の有限次元分布である。$\square$

$k$ 本の系統が 1 世代で異なる祖先をもつ確率が $1-\binom k2/N+O(N^{-2})$、ちょうど 1 組が合わさる確率が $\binom k2/N+O(N^{-2})$ であることが極限の理由である(DL10 §2、arXiv 版 v1 pp. 6–7)。親の選び方を変えた多くの集団の模型でも、時間の単位を適切にとれば同じ極限が現れる。

突然変異と Ewens の分布

$\theta>0$ とする。$n$-合体過程の系図の各枝に、枝の長さについて率 $\theta/2$ の Poisson 過程で突然変異を独立に載せる。突然変異のたびに、それまでにない新しい型が生じるとし(無限対立遺伝子模型)、標本の個体の型を、その個体から根へ向かう道の上で最も近い突然変異の型(無ければ根の型)とする。同じ型の個体をまとめた $[n]$ の分割を 型の分割 という。上昇階乗を $\theta^{(n)}:=\theta(\theta+1)\cdots(\theta+n-1)$ と書く。

型の分割は Ewens の分布に従う

型の分割を $\Pi^{\mathrm a}$ とすると、ブロックの大きさが $b_1,\dots,b_K$ の分割 $\pi\in\mathcal P_n$ について
$$ P(\Pi^{\mathrm a}=\pi)=\frac{\theta^K}{\theta^{(n)}}\prod_{i=1}^K(b_i-1)! $$
である。これは 中華料理店過程 の定理「Ewens の分布」の式と同じである。

過去へたどる事象の列を数える

過去へたどり、まだ突然変異に出会っていない系統を 生きた系統 と呼ぶ。生きた系統はそれぞれ標本の部分集合(いずれ同じ型になる個体の集まり)を運ぶ。生きた系統の上で突然変異が起これば、その集合が型の分割の 1 つのブロックになり、系統は生きた系統から外れる。生きた系統が別の系統と合わさるとき、相手も生きた系統なら 2 つの集合が合わさり、相手が外れた系統なら集合は変わらない(外れた系統の突然変異は合流点より下にある)。
生きた系統が $k$ 本あるとき、指数分布の無記憶性と prop-kc-count の作り方により、次に起こる「生きた系統どうしの合体」と「生きた系統の上の突然変異」のうち、決まった対の合体は率 $1$、決まった系統の突然変異は率 $\theta/2$ で競い、外れた系統の関わる合体はこれらに影響しない。よって次の事象が決まった対の合体である確率は $1/c_k$、決まった系統の突然変異である確率は $\frac\theta2/c_k$ で、$c_k:=\binom k2+\frac{k\theta}2=\frac{k(k-1+\theta)}2$ である。どちらの事象でも生きた系統は 1 本減る。最後の 1 本の集合は(根まで突然変異に出会っても出会わなくても)1 つのブロックになるので、これを確率 $1$ の「突然変異」と数えると、事象はちょうど $n$ 回起こる。
したがって、合体が $n-K$ 回、突然変異が $K$ 回の事象の列 $h$ の確率は
$$ P(h)=\Bigl(\frac\theta2\Bigr)^{K-1}\prod_{k=2}^n\frac1{c_k}=\Bigl(\frac\theta2\Bigr)^{K-1}\frac{2^{n-1}\theta}{n!\,\theta^{(n)}}=\frac{\theta^K2^{n-K}}{n!\,\theta^{(n)}} $$
で、列によらない($\prod_{k=2}^nk(k-1+\theta)=n!\,\theta^{(n)}/\theta$ による)。型の分割が $\pi$ になる列を数える。ブロック $B_i$ について、その $b_i$ 個の 1 点集合を 1 つにまとめる合体の順序つきの列は $\prod_{j=2}^{b_i}\binom j2=\frac{b_i!(b_i-1)!}{2^{b_i-1}}$ 通りあり、その後に突然変異が 1 回来る。この長さ $b_i$ の列を $K$ 個のブロックについて並べ合わせる仕方は $\frac{n!}{\prod_ib_i!}$ 通りなので、列の数は
$$ \frac{n!}{\prod_ib_i!}\prod_{i=1}^K\frac{b_i!(b_i-1)!}{2^{b_i-1}}=\frac{n!}{2^{n-K}}\prod_{i=1}^K(b_i-1)! $$
である。$P(h)$ を掛ければ主張の式を得る。$\square$

型の分割の分布が 中華料理店過程 と一致するので、標本の大きさを増やした極限で、型の割合を大きい順に並べたものは Poisson–Dirichlet分布 に従う(同記事の定理「中華料理店過程の割合の極限」)。

反例:仮定を外すと成り立たないこと

主張外す仮定例成り立たなくなる結論
thm-kc-consistent各対の率がブロックの数によらず $1$ブロックが $k$ 個のとき各対の率を $\frac1{k-1}$ とした連鎖で、$n=3$、$m=2$制限が $2$-合体過程と同じ分布をもつこと
thm-kc-cdi各対の率が時刻によらず $1$時刻 $t$ での各対の率を $\mathbf 1\{t>1\}$ とした過程正の時刻でブロックの数が有限であること
thm-kc-wf各個体が親を独立に一様に選ぶ各世代で、確率 $\frac1N$ で全員が一様に選んだ同じ 1 個体を親とし、それ以外は一様な全単射で親を割り当てる極限が $n$-合体過程であること
反例の確かめ
確かめを開く

1 行目。 3 個の 1 点集合からの率の和は $3\cdot\frac12=\frac32$ で、最初の合体までの時間の平均は $\frac23$ である。合わさる対は一様なので、確率 $\frac13$ で $\{1,2\}$ が合わさって制限が 1 個のブロックになり、確率 $\frac23$ で $3$ を含む対が合わさって制限は変わらない。後者では残る 2 個のブロックの率は $\frac1{2-1}=1$ なので、さらに平均 $1$ だけ待つ。制限が 1 個のブロックになる時刻の平均は $\frac23+\frac23\cdot1=\frac43$ で、$2$-合体過程の平均 $1$ と異なる。よって制限は $2$-合体過程と同じ分布をもたない。

2 行目。 時刻 $1$ までどの対も合わさらないので、$0< t\le1$ では $\Pi_t=\Pi_0$ のブロックは無限個である。時刻 $1$ 以降は Kingman 合体過程を時刻 $1$ だけずらしたものなので、各 $[n]$ への制限は整合的で、過程は定まる。

3 行目。 $n=3$ とする。親がすべて異なる世代では系統は合わさらず、全員が同じ親をもつ世代では 3 本が一度に合わさる。推移行列はちょうど $I+Q^\ast/N$ で、$Q^\ast$ は $\mathbf 0_3$ から 1 個のブロックへ率 $1$ で跳ぶ行列である。prf-kc-wf と同じ評価($E_N=0$)により、極限は $Q^\ast$ の連鎖で、ブロックが 2 個の状態を通らない。$3$-合体過程では各 $t>0$ で $P(\Pi^{(3)}_t$ のブロックが 2 個$)=\frac32(e^{-t}-e^{-3t})>0$ なので、極限は $3$-合体過程と異なる。

補足

歴史と呼び名

$n$-合体過程は J. F. C. Kingman の 1982 年の論文(Kin82、Kin82b)で導入された。Kingman は $n$-合体過程を $[n]$ 上の同値関係に値をとる確率過程として定式化した(DL10 §2、arXiv 版 v1 p. 7。同値関係は分割と同じものである)。系図を根つきの 2 分木として描き、ブロックが $k$ 個の間の時間が独立な平均 $1/\binom k2$ の指数分布に従い、一様に選ばれた 2 本の枝が合わさる、という見方も同じ過程を表す(DL10 §2、arXiv 版 v1 p. 7)。

関連項目

参考文献

[1]
Peter Donnelly, Stephen Leslie, The coalescent and its descendants, N. H. Bingham, C. M. Goldie (eds.), Probability and Mathematical Genetics: Papers in Honour of Sir John Kingman, Cambridge University Press (2010), pp. 204–237, DOI 10.1017/CBO9781139107174.011; arXiv:1006.1514, 2010, arXiv 版 v1 の頁。§2(pp. 6–7)
[2]
J. F. C. Kingman, The coalescent, Stochastic Processes and their Applications 13 (1982), no. 3, 235–248, 1982
[3]
J. F. C. Kingman, On the genealogy of large populations, Journal of Applied Probability 19A (1982), 27–43, 1982

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