ベルトランの投票定理

組み合わせ論において、ベルトランの投票問題は、「候補者Aがp票、候補者Bがq票（p > q）を獲得する選挙において、投票がランダムに選ばれた順序で集計されるという仮定の下で、AがBを常にリードし続ける確率はどれくらいか？」という問題である。答えは  

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

この結果は1878年にWA Whitworthによって初めて発表されたが、1887年にそれを再発見したJoseph Louis François Bertrandにちなんで名付けられた。 ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ]}

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

ベルトランの投票定理は、サイクル補題と関連している。両者は類似した公式を与えるが、サイクル補題はすべての順列ではなく、与えられた投票数順列の循環的なシフトを考慮する。

有権者が5人いて、そのうち3人が候補者Aに、2人が候補者Bに投票したとします（つまり、p =3、q =2）。投票が数えられる順序は、10通りあり、いずれも等確率です。

• AAABB
• AABAB
• BAAB
• ばあーーーー
• AABBA
• アババ
• バーバ
• アッバー
• ババア
• 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}}}$定理が予測するように。

投票集計全体を通してAがBを常に上回るためには、同票があってはならない。最初の投票に基づいて集計シーケンスを分割する。Bへの投票で始まるシーケンスは、最終的にAが勝つため、どこかの時点で同票になる。Aで始まり同票になるシーケンスについては、最初の同票の時点までの投票を反転させ（つまり、AはBになり、BはAになる）、Bで始まるシーケンスを得る。したがって、Aで始まり同票になるすべてのシーケンスは、Bで始まるシーケンスと1対1で対応しており、シーケンスがBで始まる確率は${\displaystyle q/(p+q)}$したがって、Aが常に投票でリードする確率は

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

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

• 条件を緩和します${\displaystyle p>q}$に${\displaystyle p\geq q}$明らかに、次の場合に定理は正しい。${\displaystyle p=q}$この場合、すべての票が集計された後、最初の候補者が厳密にリードしているわけではないため（確率は0）、
• 明らかに、最初の候補者がすべての票を獲得した場合、確率が 1 のときp  >  0 かつq  = 0であれば定理は真である。また、先ほど見たようにp = q > 0 の場合にも真である。    
• p  = a − 1 かつq = bの場合と、p = aかつq = b − 1 の場合の両方で成り立つと仮定します(ただし、 a > b > 0 です)。               ${\displaystyle a=b}$（ここでは、すでに以前に処理済みなので、ここでは省略します。）次に、p  = aかつq = bの場合を考えると、最後に集計される票は、確率 a /( a + b ) で最初の候補者に、または確率b /( a + b )で2番目の候補者に投じられます。したがって、最後の投票から2番目の投票まで（そして最後の投票後も）最初の候補者がリードしている確率は次のようになります。       

${\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に対して、これは真である。    

簡単な証明は、ドヴォレツキーとモツキンのサイクル補題に基づいています。^{[ 8 ]}投票の集計全体を通してAがBより厳密に先行している場合 、投票シーケンスが支配的であると言います。サイクル補題は、任意のシーケンスが${\displaystyle p}$Aと${\displaystyle q}$B'sでは、${\displaystyle p>q}$正確に${\displaystyle pq}$支配的な巡回順列。これを見るには、与えられたシーケンスを並べ替えるだけです。${\displaystyle p+q}$円の中にAとBを配置し、隣接するペアABを繰り返し取り除き、最終的に${\displaystyle pq}$Aが残ります。これらのAはそれぞれ、何も取り除かれる前に支配的な循環順列の開始点でした。したがって${\displaystyle pq}$から${\displaystyle p+q}$任意の配置の巡回順列${\displaystyle p}$投票と${\displaystyle q}$B票が圧倒的に優勢だ。

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

$${\displaystyle X_{k}={\frac {S_{nk}}{nk}};\quad k=0,1,...,n-1}$$ どこ${\displaystyle S_{nk}}$候補者AがBをリードしている、${\displaystyle nk}$投票結果が出ました。

請求：${\displaystyle X_{k}}$これはマルチンゲール過程である 。

与えられた${\displaystyle X_{k}}$私たちは知っている${\displaystyle S_{nk}=(nk)X_{k}}$なので最初の${\displaystyle nk}$投票、${\displaystyle {\frac {X_{k}+1}{2}}(nk)}$候補者Aに対するもので、${\displaystyle {\frac {-X_{k}+1}{2}}(nk)}$候補者Bへの支持だった。

つまり、確率的に${\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}}$。

停止時間を定義する${\displaystyle T}$最低限${\displaystyle k}$そのため${\displaystyle X_{k}=0}$、 または${\displaystyle n-1}$もしそのようなものがなければ${\displaystyle k}$すると、候補者Aが常にリードする確率は${\displaystyle E[X_{T}]}$任意停止定理によれば、${\displaystyle E[X_{T}]=E[X_{0}]}$最後のリードを${\displaystyle S_{n}}$、そして定義${\displaystyle X_{k}}$0で、${\displaystyle E[X_{0}]={\frac {p-q}{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 },}$

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

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

予想通り。

元の問題は、最初の候補者が常に得票数で厳密にリードしている確率を求めることです。代わりに、2番目の候補者が決してリードしない確率（つまり、同票が許容される）を求める問題を考えることもできます。この場合、答えは

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

変形問題は、元の問題と同様の方法で反射法によって解くことができます。可能な投票シーケンスの数は${\displaystyle {\tbinom {p+q}{q}}}$2番目の候補が常に先行する場合、そのシーケンスを「悪い」と呼び、悪いシーケンスの数を列挙できれば、引き算によって「良い」シーケンスの数を求めることができ、確率を計算できます。

投票シーケンスを、デカルト座標平面上の北東方向の格子パスとして以下のように表現します。

• パスの開始位置を(0,  0)とする
• 最初の候補者への投票が1票入るたびに、右に1単位移動する。
• 2番目の候補者への投票が1票入るごとに、順位を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 票が入った非同票の数は${\displaystyle {\tfrac {p+1-q}{p+1+q}}{\tbinom {p+1+q}{q}}}$代数操作により、 ${\displaystyle {\tfrac {p+1-q}{p+1}}{\tbinom {p+q}{q}}}$したがって、A票に対してp票を持つシーケンスの割合は${\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. 「投票問題」。マスワールド。