ベルトランの投票定理

組合せ論におけるベルトランの投票問題とは、「候補者Aがp票を獲得し、候補者Bがq票を獲得し、 p  >  qである選挙において、投票がランダムに選ばれた順序で数えられるという仮定の下で、AがBよりずっと優勢である確率はどれくらいか？」という問題である。答えは次の通りである。

${\displaystyle {\frac {pq}{p+q}}.}$

この結果は1878年にWAウィットワースによって初めて発表されましたが、 1887年に再発見したジョセフ・ルイ・フランソワ・ベルトランにちなんで命名されました。 ^{[1] [2] [3] [4] [5]}

ベルトランの原著論文では、再帰関係を用いた好ましいシーケンスの数の一般的な公式に基づく証明を概説している。彼は、このような単純な結果はより直接的な方法で証明できる可能性があると述べている。そのような証明はデジレ・アンドレ^[6]によって与えられており、これは、好ましくないシーケンスが2つの等確率の場合に分けられ、そのうちの1つ（Bが最初の投票を受け取る場合）は簡単に計算できるという観察に基づいている。彼は明示的な一対一で等式を証明している。彼の方法のバリエーションはアンドレの反射法として広く知られているが、アンドレは反射をまったく使用していない。^[7]

ベルトランの投票定理は、サイクル補題と関連しています。これらは同様の式を与えますが、サイクル補題では、すべての順列ではなく、特定の投票集計順序の 循環シフトを考慮します。

投票者が 5 人いて、そのうち 3 人が候補者Aに投票し、2 人が候補者Bに投票するとします(つまり、p = 3、q = 2)。投票を数える順序は、次の 10 通りの確率で存在します。

• AAABB
• アアバブ
• アバアバ
• バァーブ
• アッバ
• アババ
• ババ
• アバ
• ババ
• BBAAA

AABAB の順序の場合、選挙の進行に伴う投票の集計は次のようになります。

各列では、 Aの合計が常にBの合計よりも大きいため、Aは常にBより確実に先行します。 AABBA の順序では、選挙の進行に伴う投票の合計は次のようになります。

この順位では、4回目の投票後、BはAと同点となるため、 Aは常にBより厳密に先行するわけではありません。10通りの順位のうち、Aが常にBより先行するのはAAABBとAABABの場合のみです。したがって、 Aが常に厳密に先行する 確率は

${\displaystyle {\frac {2}{10}}={\frac {1}{5}},}$

そしてこれは確かに定理が予測する通り 等しい。${\displaystyle {\frac {3-2}{3+2}}}$

ランダムな開票順序が望ましい特性を持つ確率を計算する代わりに、好ましい開票順序の数を計算し、それを開票が行われた可能性のある方法の総数で割ることができます。(これは Bertrand が使用した方法です。) 方法の総数は二項係数 です。Bertrand の証明では、開票に好ましい順序の数は であることが示されています(ただし、この数は明示的に示されていません)。そして実際に、割り算すると となります。 ${\displaystyle {\tbinom {p+q}{p}}}$${\displaystyle {\tbinom {p+q-1}{p-1}}-{\tbinom {p+q-1}{p}}}$${\displaystyle {\tfrac {p}{p+q}}-{\tfrac {q}{p+q}}={\tfrac {pq}{p+q}}}$

もう一つの同等の問題は、原点から始まり点mで終わる単位長さのnステップからなり、決して負にならない整数上のランダムウォークの数を計算することです。nとm は同じ偶奇性を持ち、なので、この数は ${\displaystyle n\geq m\geq 0}$

${\displaystyle {\binom {n}{\tfrac {n+m}{2}}}-{\binom {n}{{\tfrac {n+m}{2}}+1}}={\frac {m+1}{{\tfrac {n+m}{2}}+1}}{\binom {n}{\tfrac {n+m}{2}}}.}$

およびが偶数のとき、カタラン数 が得られます。したがって、ランダム ウォークが決して負にならず、時刻 に原点に戻る確率は です。スターリングの公式により、 のとき、この確率は です。 ${\displaystyle m=0}$${\displaystyle n}$ ${\displaystyle {\frac {1}{{\tfrac {n}{2}}+1}}{\binom {n}{\tfrac {n}{2}}}}$${\displaystyle n}$${\displaystyle 2^{-n}{\frac {1}{{\tfrac {n}{2}}+1}}{\binom {n}{\tfrac {n}{2}}}}$${\displaystyle n\to \infty }$${\displaystyle \sim {\frac {\sqrt {2}}{n^{3/2}}}}$

[ は次のように同じパリティを持つことに注意してください。を「正の」移動、つまり右への移動の数とし、 を「負の」移動、つまり左への移動の数とします。 およびなので、および が成り立ちます。および は整数なので、は同じパリティを持ちます。] ${\displaystyle m,n}$${\displaystyle P}$${\displaystyle N}$${\displaystyle P+N=n}$${\displaystyle PN=m}$${\displaystyle P={\frac {n+m}{2}}}$${\displaystyle N={\frac {nm}{2}}}$${\displaystyle P}$${\displaystyle N}$${\displaystyle m,n}$

投票の集計中、A が B より確実にリードするには、同点があってはなりません。集計シーケンスを最初の投票数で分けます。B への投票で始まるシーケンスは、いずれ A が勝つため、どこかの時点で必ず同点になります。A で始まり同点になるシーケンスについては、最初の同点の時点までの投票を反映して (つまり、すべての A が B になり、その逆も同様)、B で始まるシーケンスを取得します。したがって、A で始まり同点になるシーケンスはすべて、B で始まるシーケンスと 1 対 1 に対応しており、シーケンスが B で始まる確率は であるため、A が常に投票でリードする確率は です。 ${\displaystyle q/(p+q)}$

${\displaystyle =1-}$ある時点で同点になるシーケンスの確率

${\displaystyle =1-}$ある時点で同点となり、A または B で始まるシーケンスの確率

${\displaystyle =1-2\times (}$ある時点で同点となり、Bで始まるシーケンスの確率${\displaystyle )}$

${\displaystyle =1-2\times (}$シーケンスがBで始まる確率${\displaystyle )}$

${\displaystyle =1-2{\frac {q}{p+q}}={\frac {pq}{p+q}}}$

もう一つの証明方法は数学的帰納法です。

• 条件を まで緩めます。 の場合には、明らかに定理は正しいです。なぜなら、この場合、すべての投票が集計された後、最初の候補者が厳密にリードすることはないからです (したがって、確率は 0 です)。${\displaystyle p>q}$${\displaystyle p\geq q}$${\displaystyle p=q}$
• 明らかに、最初の候補者がすべての票を獲得すると仮定すると、確率が 1 のときにp  > 0 かつq = 0であれば定理は真です 。また、先ほど見たように、p  =  q > 0 の場合にも定理は真です。
• p  =  a  − 1 かつq  =  b の場合と、p  =  aかつq  =  b  − 1 でa  >  b > 0 の場合の両方が真であると仮定します。(このケースは以前に処理したため、ここで 考慮する必要はありません。) 次に、 p  =  aかつq  =  bの場合を考えると、最後にカウントされる投票は、確率 a /( a  +  b )で最初の候補者に、または確率b /( a  +  b )で2番目の候補者に投票されます。したがって、カウント全体を通して、最後から2番目の投票がカウントされるまで(および最終投票後も)、最初の候補者がリードしている確率は次のとおりです。${\displaystyle a=b}$

${\displaystyle {a \over (a+b)}{(a-1)-b \over (a+b-1)}+{b \over (a+b)}{a-(b-1) \over (a+b-1)}={ab \over a+b}.}$

• したがって、p  >  q  > 0となるすべてのpとqに対してこれが当てはまります。

簡単な証明は、Dvoretzky と Motzkin の巡回補題に基づいています。^[8]投票の集計全体を通して A が B より確実に進んでいる場合、 投票シーケンスは支配的と呼ばれます。巡回補題は、であるA とB の任意のシーケンスには、正確に支配的な巡回順列があると主張しています。これを確認するには、指定されたA と B のシーケンスを円形に配置し、隣接するペア AB を繰り返し削除して、A だけが残るようにします。これらの A はそれぞれ、何かが削除される前の支配的な巡回順列の始まりでした。そのため、A 票とB 票の任意の配置の巡回順列では、支配的です。 ${\displaystyle p}$${\displaystyle q}$${\displaystyle p>q}$${\displaystyle pq}$${\displaystyle p+q}$${\displaystyle pq}$${\displaystyle pq}$${\displaystyle p+q}$${\displaystyle p}$${\displaystyle q}$

とする。「逆算」確率過程を定義する。 ${\displaystyle n=p+q}$

$${\displaystyle X_{k}={\frac {S_{nk}}{nk}};\quad k=0,1,...,n-1}$$投票が集まった 後、候補者 A は候補者 B に対して どの程度リードしていますか。${\displaystyle S_{nk}}$${\displaystyle nk}$

主張:はマーチンゲール過程です 。 ${\displaystyle X_{k}}$

を前提とすると、 であることが分かるので、最初の投票のうち、は候補者 A に、 は候補者 B に投票されたことになります。 ${\displaystyle X_{k}}$${\displaystyle S_{nk}=(nk)X_{k}}$${\displaystyle nk}$${\displaystyle {\frac {X_{k}+1}{2}}(nk)}$${\displaystyle {\frac {-X_{k}+1}{2}}(nk)}$

したがって、確率 で、 、 が成り立ちます。もう 1 つについても同様です。次に を計算して を見つけます。 ${\displaystyle {\frac {X_{k}+1}{2}}}$${\displaystyle S_{nk-1}=S_{nk}-1}$${\displaystyle X_{k+1}={\frac {nk}{nk-1}}X_{k}-{\frac {1}{nk-1}}}$${\displaystyle E[X_{k+1}|X_{k}]=X_{k}}$

停止時間をとなる最小値、またはとなるような が存在しない場合に と定義します。この場合、候補者Aが常にリードする確率は となり、これはオプション停止定理により次のようになります。${\displaystyle T}$${\displaystyle k}$${\displaystyle X_{k}=0}$${\displaystyle n-1}$${\displaystyle k}$${\displaystyle E[X_{T}]}$${\displaystyle E[X_{T}]=E[X_{0}]={\frac {pq}{p+q}}}$

ベルトランは解決策を次のように表現した。

${\displaystyle {\frac {2m-\mu }{\mu }}}$

ここで、は投票者総数、は第一候補の投票者数である。彼は、結果は次の式に従うと述べている。 ${\displaystyle \mu =p+q}$${\displaystyle m=p}$

${\displaystyle P_{m+1,\mu +1}=P_{m,\mu }+P_{m+1,\mu },}$

ここで、 は好ましいシーケンスの数ですが、「このような単純な結果は、より直接的な方法で示すことができると思われます」。実際、より直接的な証明は、デジレ・アンドレによってすぐに作成されました。彼のアプローチは、現代の著者によって誤って「反射原理」と呼ばれることがよくありますが、実際には順列を使用しています。彼は、「好ましくない」シーケンス (中間の同点に達するシーケンス) は、A で始まるシーケンスと B で始まるシーケンスの数が等しいことを示しています。B で始まるシーケンスはすべて好ましくなく、 B の後に任意の ( q -1) 個の B とp個の A のシーケンスが続くシーケンスがあります。A で始まる各好ましくないシーケンスは、ルールに違反する最初の B (投票数が同点になる) を見つけて削除し、残りの部分の順序を入れ替えることで、任意の( q -1) 個の B とp個の A のシーケンスに変換できます。逆の手順を踏むには、( q -1) 個の B とp個の A の任意のシーケンスを取り、末尾から A の数が B の数を超える最初の場所を探し、次に部分の順序を入れ替えて間に B を置きます。たとえば、不利なシーケンスAAB B ABAA は、任意のシーケンス ABAA AABに一意に対応します。このことから、 p個の A とq個の B の有利なシーケンスの数は、${\displaystyle P_{m,\mu }}$${\displaystyle {\tbinom {p+q-1}{q-1}}}$

${\displaystyle {\binom {p+q}{q}}-2{\binom {p+q-1}{q-1}}={\binom {p+q}{q}}{\frac {p-q}{p+q}}}$

したがって必要な確率は

${\displaystyle {\frac {p-q}{p+q}}}$

予想通り。

元々の問題は、第一候補が常に投票数でリードしている確率を求めることです。代わりに、第二候補が決してリードしていない確率を求める問題を考えることもできます（つまり、同点が許されます）。この場合、答えは次のようになります。

${\displaystyle {\frac {p+1-q}{p+1}}.}$

バリアント問題は、元の問題と同様に、反射法で解決できます。可能な投票シーケンスの数は です。2 番目の候補者が常に先行している場合はシーケンスを「悪い」と呼び、悪いシーケンスの数を列挙できる場合は、減算によって「良い」シーケンスの数を見つけて、確率を計算できます。 ${\displaystyle {\tbinom {p+q}{q}}}$

投票シーケンスを、次のように直交平面上の 格子パスとして表します。

• パスを(0, 0)から開始します
• 最初の候補者への投票を受け取るたびに、1 単位右に移動します。
• 2 番目の候補者への投票が受信されるたびに、1 単位ずつ上がります。

このようなパスはそれぞれ、一意の投票シーケンスに対応し、( p、q ) で終了します。シーケンスが「良い」のは、対応するパスが対角線y  =  xより上に行かないときです。同様に、シーケンスが「悪い」のは、対応するパスが線y  =  x  + 1 に接するときです。

それぞれの「悪い」パスPについて、 Pの一部を、その線に接する最初の点まで反転させて、新しいパスP ′ を定義します。 P ′ は、(−1, 1) から ( p ,  q )へのパスです。同じ操作をもう一度適用すると、元のP が復元されます。これにより、「悪い」パスと (−1, 1) から ( p ,  q )へのパスの間に 1 対 1 の対応が生成されます。これらのパスの数は であり、 は「悪い」シーケンスの数です。これにより、「良い」シーケンスの数は次のようになります。 ${\displaystyle {\tbinom {p+q}{q-1}}}$

${\displaystyle {\binom {p+q}{q}}-{\binom {p+q}{q-1}}={\binom {p+q}{q}}{\frac {p+1-q}{p+1}}.}$

全部で 個あるので、シーケンスが良好である確率は です。 ${\displaystyle {\tbinom {p+q}{q}}}$${\displaystyle {\tfrac {p+1-q}{p+1}}}$

実際、元の問題と変形問題の解決策は簡単に関連付けることができます。候補者Aが投票カウント全体を通して確実にリードするには、最初の投票を獲得する必要があり、残りの投票（最初の投票は無視）では、カウント全体を通して確実にリードするか同点である必要があります。したがって、元の問題の解決策は次のようになります。

${\displaystyle {\frac {p}{p+q}}{\frac {p-1+1-q}{p-1+1}}={\frac {p-q}{p+q}}}$

必要に応じて。

逆に、同点の場合は同点ではない場合から導き出すことができます。Aに対する p+1 票の同点ではないシーケンスの数は、A に対する p 票の同点シーケンスの数に等しいことに注意してください。A に対する p + 1 票の同点ではない投票数は であり、代数操作により となる ため、A に対する p 票のシーケンスの割合は となります。 ${\displaystyle {\tfrac {p+1-q}{p+1+q}}{\tbinom {p+1+q}{q}}}$${\displaystyle {\tfrac {p+1-q}{p+1}}{\tbinom {p+q}{q}}}$${\displaystyle {\tfrac {p+1-q}{p+1}}}$

• 新旧の投票定理、L. Addario-Berry、BA Reed、2007 年、組み合わせ論の地平線、編集者 Ervin Győri、G. Katana、Gyula OH Katana、László Lovász、Springer、2008、ISBN 978-3-540-77199 -9 

• 投票問題（フランス語の原文記事のスキャンと英語訳を含む）
• Bernard Bru、Les leçons de calcul des probabilités de Joseph Bertrand、問題の歴史 (フランス語)
• ワイスタイン、エリック・W.「投票問題」。マスワールド。