ベルトランの投票問題

ベルトランの投票問題はなかなか面白い問題で、Bertrand's ballot theorem (Wikipedia)【英文】に説明がありますが残念ながら日本語訳がないので、簡単ですが紹介します。

【問題】選挙において、候補者$M$は$m$票を、候補者$N$は$n$票を得票した。ただし、$m \gt n$である. 開票していく過程において$M$の得票数が$N$の得票数を常に上回る確率は$\Large \frac{m-n}{m+n}$となる。

数学的帰納法で証明

驚くほど簡単な式になりますが、以下ののように数学的帰納法で証明することが出来ます。

\begin{align*}
&m \gt 0 かつ n=0のときは常に上回るので \\
&P_{m,n} = \frac{m-0}{m+0} = 1で正しい \\
&m = n \gt 0のときは成り立たないので \\
&P_{m,n} = \frac{0}{m+m} = 0で正しい \\
&P_{m,n-1} とP_{m-1,n}が成り立つとき P_{m,n}は \\ 
&P_{m,n-1} が起こった後、Nが出た場合と、\\
&P_{m-1,n} が起こった後、Mが出た場合なので\\
\end{align*}

\begin{align*}
P_{m,n} &= P_{m,n-1}\frac{n}{m+n}+P_{m-1,n} \frac{m}{m+n}  \\
&= \frac{m-(n-1)}{m+(n-1)}\frac{n}{m+n}+\frac{(m-1)-n}{(m-1)+n}\frac{m}{m+n}\\
&= \frac{m-n}{m+n} \\
\end{align*}

カタラン数との関係

同じ問題を確率ではなくて場合の数$C_{m,n}$で考えてみます。その場合も以下の同様の式が成り立ちます。

\begin{align*}
&c_{m,0} = 1  & (m \gt 0) \\
&c_{m,n} = 0  & (m \le n) \\
&c_{m,n} = c_{m,n-1}+c_{m-1,n}  & (m \gt n)\\
\end{align*}

この結果を表にすると以下のようになります。

m\n	0	1	2	3	4	5	6	7	8
1	1
2	1	1
3	1	2	2
4	1	3	5	5
5	1	4	9	14	14
6	1	5	14	28	42	42
7	1	6	20	48	90	132	132
8	1	7	27	75	165	297	429	429
9	1	8	35	110	275	550	902	1430	1430

この対角線の数列$c_{n+1,n}$は $1,1,2,5,14,42,132,429,1430$ですが、これはカタラン数(Catalan number) Wikipediaのように見えます。カタラン数の一般項は以下の式で表されますので、これと一致するか確認していきます。

\frac{1}{n+1}\times\binom{2n}{n}

カタラン数の一般項と一致するか

$c_{n+1,n}$の値をベルトランの投票問題の確率から場合の数を逆算します。

\begin{align*}
&一般に、確率 = \frac{場合の数}{すべての数} なので\\
&場合の数 = 確率 \times すべての数 \\ \\

&したがって \\
& c_{n+1,n} = \frac{1}{2n+1} \times 同じものを含む順列(n+1,n)\\
&           = \frac{1}{2n+1}  \times \binom{2n+1}{n} \\

& = \frac{1}{2n+1}  \times\frac{(2n+1)!}{(n+1)!n!}  \\
& = \frac{1}{n+1}\times \frac{(2n)!}{n!n!}  \\
& = \frac{1}{n+1}\times\binom{2n}{n}
\end{align*}

となりベルトランの投票問題の場合の数$c_{n+1,n}$はカタラン数の一般項と一致することが確認できました。