伯特蘭投票問題

在組合數學中，伯特蘭投票問題（英語：Bertrand's ballot theorem）是指，在一場選舉中候選人A得到了p張選票，而候選人B得到了q張選票（p>q），那麼在整個點票過程中A的票數都嚴格大於B的概率是多少。這個問題的答案是

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

這個結果首次由威廉·亞倫·維特沃斯（W·A·Whitworth）於1878年發佈，但最終以在1887年重新發現這個問題的約瑟·伯特蘭的名字命名。

舉例

假設有5名選民，其中3名候選人投票給A，2名候選人投票給B（即p = 3，q = 2）， 則投票順序有以下十種可能性：

• $AAABB$
• $AABAB$
• $ABAAB$
• $BAAAB$
• $AABBA$
• $ABABA$
• $BAABA$
• $ABBAA$
• $BABAA$
• $BBAAA$

假設投票順序為$AABAB$，則點票過程中點完每一票的結果為：

候選人	A	A	B	A	B
A	1	2	2	3	3
B	0	0	1	1	2

對於每一列（即點完每一票後）， A的票數始終大於B的票數，因此A的票數始終嚴格領先於B。而對於AABBA的順序，隨着選舉的進行，選票總數為：

候選人	A	A	B	B	A
A	1	2	2	2	3
B	0	0	1	2	2

對於這個投票順序， B在第四次投票後與A並列，因此A並不總是嚴格地領先於B。在10個可能的順序中，只有AAABB和AABAB兩個順序滿足A總是領先於B。 因此，A始終嚴格領先的概率為

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

這與定理得出的${\frac {3-2}{3+2}}$結果相符。

問題的等價

計算符合要求的選票順序出現的概率可以通過使用滿足要求的選票順序數量除以可能的順序總數來得到（這正是伯特蘭鎖使用的方法）。順序的總數由二項式係數 ${\tbinom {p+q}{p}}$ 決定，伯特蘭的證明顯示，符合要求的選票順序為${\tbinom {p+q-1}{p-1}}-{\tbinom {p+q-1}{p}}$ （儘管他沒有明確給出這個數字）。 作除法後可以得到問題的答案： ${\tfrac {p}{p+q}}-{\tfrac {q}{p+q}}={\tfrac {p-q}{p+q}}$ 。

另一個等價的問題是計算 n 個整數上的隨機遊走數量，從坐標原點開始到 m 點終止，且不到達負數的範圍。假設 n 和 m 具有相同的奇偶性，且$n\geq m\geq 0$，則這個結果為

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

令 n 為投票問題中的較大數 p ，m 為兩候選人票數之差 p-q，即可得到該問題的結果。當m = 0 且 n 為偶數時，可以通過卡塔蘭數${\frac {1}{{\tfrac {n}{2}}+1}}{\binom {n}{\tfrac {n}{2}}}$ 確定結果。

使用數學歸納法證明

• 我們將條件$p>q$放縮至$p\geq q$，很明顯，當$p=q$時這個定理是正確的，因為當所有票點完時候選人A將不再領先，此時這個問題的概率為$0$。
• 當$p>0$且$q=0$時這個概率為$1$，因為候選人A收到了全部的選票，自然一直領先。
• 假設當$p=a-1$且$q=b\;(a>b>0)$，或者當$p=a$且$q=b-1\;(a>b>0)$時這個定理均成立，則考慮$p=a,q=b$的情形，最後一票投給候選人A的概率為${\frac {a}{a+b}}$，投給候選人B的概率為${\frac {b}{a+b}}$，所以這種情形下A一直領先B的概率為

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

• 因此，對於所有$p>q>0$，這個定理均成立。