コンクラーヴェはいつ終わるか？

こんにちは！Nappleです。

今回は、先日(2000億年前)話題になった『コンクラーヴェ』について、コンクラーヴェはいつ終わるのか？を確率的に考察します。

非常に雑な議論を含みます

コンクラーヴェとは？

カトリック教会の最高司祭であるローマ教皇を選出するための選挙です。
現代の方法では、教皇候補である枢機卿をシスティーナ礼拝堂と呼ばれる施設内に集め、匿名投票を繰り返すことで教皇を決定します。
枢機卿は自分以外の誰かに投票し、ある1人が$\frac{2}{3}$以上の得票率を得たとき、選挙は終了します。
選挙期間中は枢機卿たちは礼拝堂や宿舎の外へ出たり、外と連絡したりすることは許されないみたいです。

先日のコンクラーヴェは、133人の枢機卿から教皇が選ばれました。
今回は4回の投票で終結したようですが、
実際どのくらいで終わるものなのでしょうか。

もしかすると、
枢機卿たちは非常に長い時間を礼拝堂の中で過ごすことになるかもしれません。

問題の定式化

コンクラーヴェについて、問題1のように一般的な形で定式化します。

コンクラーヴェ問題

$n$人の枢機卿から$1$人の教皇を選ぶ。
$1$回の投票フェーズにつき、各枢機卿はそれぞれ自分以外の枢機卿$1$人だけに投票する。
ある候補者の得票率が$a$以上になったとき、選挙は終了する。
そうでない場合次の投票フェーズに進む。
候補者全員がそれぞれ一様な確率で投票するとき、平均何回で選挙は終わるか？

結論

問題1の結果は以下のように結論付けられます。

コンクラーヴェ期待回数(一般式)

\begin{align} C &= \dfrac{1}{1 - \sum\limits_{\substack{x_1 + \cdots + x_n = n,\\ x_i < \mathrm{ceil}(an)-1}} \dfrac{n!}{x_1!\cdots x_n!} \left(\dfrac{1}{n-1}\right)^n } \end{align}

コンクラーヴェ期待回数(特殊な場合)

$a > 0.5$の場合のみ、コンクラーヴェ期待回数は以下のようになる。

\begin{align} C &= \dfrac{1}{n \sum\limits_{i=\mathrm{ceil}(an)}^{n} {}_n \mathrm{C}_k \left(\dfrac{1}{n-1}\right)^i \left(\dfrac{n-2}{n-1}\right)^{n-i} } \end{align}

ここで、$\mathrm{ceil}$は天井関数を意味します。

導出(一般の場合)

$k = \mathrm{ceil}(an)$, 候補者$i$の得票数を$X_i$と置く。

ある投票フェーズで少なくとも1人が票数 $X \geq k$ を取る確率を
\begin{align} q &= \mathrm{P}(\max_i X_i \geq k) \end{align}
と書く。

$q$は各投票フェーズごとに独立なので、必要フェーズ数 $T$ は
$T-1$回目まではすべて$q$ではなく、最後の1回で$q$である確率に従うので、

必要フェーズ数の確率分布と期待値

必要フェーズ数は幾何分布に従う。
また、確率分布と期待値は以下となる。
\begin{align} \mathrm{P}(T = t) &= (1 - q)^{t-1}q\\ \mathbb{E}[T] &= \frac{1}{q} \end{align}

\begin{align} \mathbb{E}[T] &= \sum_{t = 1}^{\infty} t (1 - q)^{t-1}q\\ &= q \lim_{n\rightarrow \infty}\sum_{t=1}^{n} t (1-q)^{t-1}\\ ここで,\\ A &:= \sum_{k=1}^{n} k r^{k-1} = 1 + 2r + \cdots + nr^{n-1} \\ rA &= r + 2r^2 + \cdots + nr^{n} \\ A - rA &= 1 + r + r^2 + \cdots + r^{n-1} - nr^{n}\\ (1-r) A &= 1 + \sum_{k=1}^{n-1} r^k - nr^{n}\\ &= \frac{1-r^{n-1}}{1-r} + 1 - nr^{n}\\ A &= \frac{1-r^n}{(1-r)^2} + \frac{1 - nr^{n}}{1-r}\\ \lim_{n \rightarrow \infty} A &= \frac{1}{(1-r)^2} & \because\lim_{n\rightarrow\infty} nr^n = 1 \\ よって, \mathbb{E}[T] &= q \cdot \frac{1}{(1-(1-q))^2} \\ &= \frac{1}{q} \end{align}

次に、$q = \mathrm{P}(\max_i X_i \geq k)$を求める。

最大の得票数が一定以上になる確率

\begin{align} q = \mathrm{P}(\max_i X_i \geq k) = 1 - \sum\limits_{\substack{x_1 + \cdots + x_n = n,\\ x_i < k}} \dfrac{n!}{x_1!\cdots x_n!} \left(\dfrac{1}{n-1}\right)^n \end{align}

$(X_1, \cdots, X_n)$は多項分布に従う。
なぜならば、各枢機卿$i$が1票を得る確率は$p_i = \frac{1}{n-1}$であり、
枢機卿$i$が$x_i$票を得る確率は
\begin{align} P(X_1=x_1, \cdots, X_n=x_n) &= \frac{n!}{x_1!\cdots x_n!} p_1^{x_1}\cdots p_n^{x_n}\\ &= \frac{n!}{x_1!\cdots x_n!} \left(\dfrac{1}{n-1}\right)^n \end{align}
となる。
ただし$x_1+\cdots + x_n = n$

ここで、
$q = \mathrm{P}(\max_i X_i \geq k) = 1-\mathrm{P}(\max_i X_i < k)$
として$\mathrm{P}(\max_i X_i < k)$を考えることにすると、

全ての$X_i$が$k$より小さければ良いので、
\begin{align} \mathrm{P}(\max_i X_i < k) &= \sum\limits_{\substack{x_1 + \cdots + x_n = n,\\ x_i < k}} \dfrac{n!}{x_1!\cdots x_n!} \left(\dfrac{1}{n-1}\right)^n\\ \end{align}

よって、
\begin{align} q = 1 - \sum\limits_{\substack{x_1 + \cdots + x_n = n,\\ x_i < k}} \dfrac{n!}{x_1!\cdots x_n!} \left(\dfrac{1}{n-1}\right)^n \end{align}

上記より、コンクラーヴェ期待回数は一般に以下となる。

\begin{align} C &= \dfrac{1}{1 - \sum\limits_{\substack{x_1 + \cdots + x_n = n,\\ x_i < \mathrm{ceil}(an)-1}} \dfrac{n!}{x_1!\cdots x_n!} \left(\dfrac{1}{n-1}\right)^n } \end{align}

導出(特殊な場合)

もし$a>0.5$の場合、
$k=\mathrm{ceil}(an)$以上の得票数を得られる候補者は多くても1人だけである(鳩の巣原理)。

$a>0.5$で、2人以上が$k=\mathrm{ceil}(an)$以上の得票数を得たと仮定する。
このとき、全員の得票数の合計$n'$は、
$$n' > 2k > n$$
しかし、枢機卿たちはそれぞれ$1$票ずつしか投票できないので、
$$n' = n$$
であり、これは矛盾する。
ゆえに、$k$以上の得票数を得られる候補者は多くても1人だけである。

この場合、コンクラーヴェ期待回数は簡単な形で計算できる。

$n$人の枢機卿のうち、誰か1人が$i$以上の得票数を得る確率は、
\begin{align} p_{\geq i}^{(n)} &= n \sum\limits_{i=k}^{n} {}_n\mathrm{C}_i\left(\frac{1}{n-1}\right)^{i} \left(1 - \frac{1}{n-1}\right)^{n-i} \end{align}

証明手法（任意）

ある枢機卿1人が$i$の得票数を得る確率は、
\begin{align} p_i &= {}_n\mathrm{C}_i\left(\frac{1}{n-1}\right)^{i} \left(1 - \frac{1}{n-1}\right)^{n-i} \end{align}

また、ある枢機卿1人が$i$以上の得票数を得る確率は、
\begin{align} p_{\geq i} &= \sum\limits_{i=k}^{n}p_i\\ &= \sum\limits_{i=k}^{n} {}_n\mathrm{C}_i\left(\frac{1}{n-1}\right)^{i} \left(1 - \frac{1}{n-1}\right)^{n-i} \end{align}

よって、$n$人の枢機卿のうち、誰か1人が$i$以上の得票数を得る確率は、
\begin{align} p_{\geq i}^{(n)} &= n p_{\geq i}\\ &= n \sum\limits_{i=k}^{n} {}_n\mathrm{C}_i\left(\frac{1}{n-1}\right)^{i} \left(1 - \frac{1}{n-1}\right)^{n-i} \end{align}

補題1と補題3から、

\begin{align} C &= \frac{1}{p_{\geq i}^{(n)}} \\ &= \frac{1}{n \sum\limits_{i=k}^{n} {}_n\mathrm{C}_i\left(\frac{1}{n-1}\right)^{i} \left(1 - \frac{1}{n-1}\right)^{n-i} } \end{align}

実際に計算してみる

証明ができたところで、前回のコンクラーヴェの状況設定において実際にその期待値を計算してみましょう。

状況設定

枢機卿の人数$n = 133$
必要な得票率$a = 2 / 3$

この状況で、選挙が終了するまでにかかる投票回数の期待値を計算する。

計算

数値計算する

Desmosに投げると、次のようになりました。

$$C = 1.6627\times10^{151} $$

正直思っていたよりもデカいです。
全然コンクラーヴェ終わりません

ただ、これだけではおもしろくないので、オーダーを計算してみましょう。

オーダーを計算する

計算が難しいのは分母の総和の項(二項分布の上側確率)です。

$$ \sum\limits_{i=k}^{n} {}_n\mathrm{C}_i\left(\frac{1}{n-1}\right)^{i} \left(1 - \frac{1}{n-1}\right)^{n-i} $$

簡単な近似のために、非常に雑な議論をします。
$k < \frac{1}{2} n$なので、特に$i=k$の項が支配的だと考えると、
$$ \sum\limits_{i=k}^{n} {}_n\mathrm{C}_i\left(\frac{1}{n-1}\right)^{i} \left(1 - \frac{1}{n-1}\right)^{n-i} \approx {}_n\mathrm{C}_k\left(\frac{1}{n-1}\right)^{k} \left(1 - \frac{1}{n-1}\right)^{n-k} $$

ここで、二項係数について
$$ \left(\frac{n}{i}\right)^i \leq {}_n\mathrm{C}_i \leq \frac{n^i}{i!} \leq \left(\frac{n\cdot e}{i}\right)^i$$
という不等式が成り立ちます。よって、
$$\left(\frac{n}{k}\right)^k \left(\frac{1}{n-1}\right)^{k} \left(1 - \frac{1}{n-1}\right)^{n-k} \leq {}_n\mathrm{C}_k \left(\frac{1}{n-1}\right)^{k} \left(1 - \frac{1}{n-1}\right)^{n-k} \leq \left(\frac{n\cdot e}{k}\right)^k \left(\frac{1}{n-1}\right)^{k} \left(1 - \frac{1}{n-1}\right)^{n-k}$$

$k\approx an$として、式変形を繰り返すと、
$$\frac{1}{(an)^{an}} \leq {}_n\mathrm{C}_k \left(\frac{1}{n-1}\right)^{k} \left(1 - \frac{1}{n-1}\right)^{n-k} \leq \frac{e^n}{(an)^{an}}$$

よって、コンクラーヴェ期待回数は近似的に以下のようになります。
$$ \frac{(an)^{an}}{e^n} \leq C \leq (an)^{an}$$

コンクラーヴェ期待回数の近似

$a<0.5$, 十分大きな$n$について、
$$ \frac{(an)^{an}}{e^n} \leq C \leq (an)^{an}$$

実際に$n=133, a=2/3$を代入すると、
$(an)^{an} = 10^{an\log_{10}(an)} = 10^{88.7\log_{10}88.7} = 10^{173}$
$e^n = 10^{n\log_{10}e} = 10^{58}$
$C \approx 10^{144\pm 29}$
非常に雑な近似ですが、とにかく膨大な値となることがわかりました。