ベルトランの投票問題
ベルトランの投票問題はなかなか面白い問題で、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}$はカタラン数の一般項と一致することが確認できました。