Теорема Бертрана о голосовании

В комбинаторике проблема голосования Бертрана — это вопрос: «На выборах , где кандидат А получает p голосов, а кандидат В получает q голосов, причем p >  q  , какова вероятность того , что А будет строго опережать В на протяжении всего подсчета, при условии, что голоса подсчитываются в случайно выбранном порядке?» Ответ:

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

Результат был впервые опубликован У. А. Уитвортом в 1878 году, но назван в честь Жозефа Луи Франсуа Бертрана, который заново открыл его в 1887 году . ^{[1] [2] [3] [4] [5]}

В оригинальной статье Бертрана он набрасывает доказательство, основанное на общей формуле для числа благоприятных последовательностей с использованием рекурсивного отношения . Он замечает, что кажется вероятным, что такой простой результат может быть доказан более прямым методом. Такое доказательство было дано Дезире Андре ^[6] , основанное на наблюдении, что неблагоприятные последовательности можно разделить на два равновероятных случая, один из которых (случай, когда B получает первый голос) легко вычисляется; он доказывает равенство явной биекцией . Разновидность его метода широко известна как метод отражения Андре , хотя Андре не использовал никаких отражений. ^[7]

Теорема Бертрана о бюллетене связана с леммой о цикле . Они дают похожие формулы, но лемма о цикле рассматривает циклические сдвиги заданного порядка подсчета бюллетеней, а не все перестановки.

Предположим, что есть 5 избирателей, из которых 3 голосуют за кандидата A и 2 голосуют за кандидата B (то есть p = 3 и q = 2). Существует десять равновероятных порядков, в которых можно подсчитать голоса:

• АААББ
• ААБАБ
• АБААБ
• БААБ
• ААББА
• АБАБА
• БААБА
• АББАА
• БАБАА
• ББААА

Для порядка AABAB подсчет голосов по ходу выборов будет следующим:

Для каждого столбца счет для A всегда больше счета для B , поэтому A всегда строго впереди B. Для порядка AABBA счет голосов по ходу выборов следующий:

Для этого порядка B делит с A после четвертого голоса, поэтому A не всегда строго впереди B. Из 10 возможных порядков A всегда впереди B только для AAABB и AABAB . Поэтому вероятность того, что A всегда будет строго впереди, равна

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

и это действительно равно тому, что предсказывает теорема.${\displaystyle {\frac {3-2}{3+2}}}$

Вместо того чтобы вычислять вероятность того, что случайный порядок подсчета голосов обладает желаемым свойством, можно вместо этого вычислить количество благоприятных порядков подсчета, а затем разделить на общее количество способов, которыми могли быть подсчитаны голоса. (Это метод, который использовал Бертран.) Общее количество способов — это биномиальный коэффициент ; доказательство Бертрана показывает, что количество благоприятных порядков, в которых следует подсчитывать голоса, равно (хотя он не приводит это число явно). И действительно, после деления это дает .${\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}}}$

Другая связанная проблема — вычислить количество случайных блужданий по целым числам , состоящим из n шагов единичной длины, начинающихся в начале и заканчивающихся в точке m , которые никогда не становятся отрицательными. Поскольку 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 м=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 м,н}$${\displaystyle P}$${\displaystyle N}$${\displaystyle P+N=n}$${\displaystyle PN=м}$${\displaystyle P={\frac {n+m}{2}}}$${\displaystyle N={\frac {нм}{2}}}$${\displaystyle P}$${\displaystyle N}$${\displaystyle м,н}$

Чтобы A был строго впереди B на протяжении всего подсчета голосов, не может быть никаких ничьих. Разделите последовательности подсчета в соответствии с первым голосованием. Любая последовательность, которая начинается с голоса за B, должна достичь ничьей в какой-то момент, потому что A в конечном итоге побеждает. Для любой последовательности, которая начинается с A и достигает ничьей, отразите голоса до точки первой ничьей (так, чтобы любой A стал B, и наоборот), чтобы получить последовательность, которая начинается с B. Следовательно, каждая последовательность, которая начинается с A и достигает ничьей, находится во взаимно-однозначном соответствии с последовательностью, которая начинается с B, и вероятность того, что последовательность начинается с 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}$
• Очевидно, теорема верна, если p  > 0 и q  = 0, когда вероятность равна 1, при условии, что первый кандидат получает все голоса; она также верна, когда 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 ). Таким образом, вероятность того, что первый будет впереди на протяжении подсчета до предпоследнего подсчитанного голоса (а также после окончательного голосования), равна:${\displaystyle а=б}$

${\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 при p  >  q  > 0.

Простое доказательство основано на лемме о цикле Дворецкого и Моцкина. ^[8] Назовем последовательность бюллетеней доминирующей, если A строго опережает B на протяжении всего подсчета голосов. Лемма о цикле утверждает, что любая последовательность A и B, где , имеет точно доминирующие циклические перестановки. Чтобы увидеть это, просто расположите заданную последовательность A и B в круг и многократно удаляйте соседние пары AB, пока не останутся только A. Каждая из этих A была началом доминирующей циклической перестановки до того, как что-либо было удалено. Таким образом, из циклических перестановок любой расстановки голосов A и B являются доминирующими.${\displaystyle p}$${\displaystyle д}$${\displaystyle p>q}$${\displaystyle pq}$${\displaystyle p+q}$${\displaystyle pq}$${\displaystyle pq}$${\displaystyle p+q}$${\displaystyle p}$${\displaystyle д}$

Пусть . Определим стохастический процесс «обратного счета»${\displaystyle n=p+q}$

$${\displaystyle X_{k}={\frac {S_{nk}}{nk}};\quad k=0,1,...,n-1}$$где находится преимущество кандидата А над кандидатом В после подсчета голосов?${\displaystyle S_{nk}}$${\displaystyle нк}$

Утверждение: это процесс мартингейла . ${\displaystyle X_{k}}$

Учитывая , мы знаем, что , поэтому из первых голосов было подано за кандидата А, а было за кандидата Б. ${\displaystyle X_{k}}$${\displaystyle S_{nk}=(nk)X_{k}}$${\displaystyle нк}$${\displaystyle {\frac {X_{k}+1}{2}}(nk)}$${\displaystyle {\frac {-X_{k}+1}{2}}(nk)}$

Итак, с вероятностью , имеем , и . Аналогично для другого. Затем вычисляем, чтобы найти . ${\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 Т}$${\displaystyle к}$${\displaystyle X_{k}=0}$${\displaystyle n-1}$${\displaystyle к}$${\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, может быть преобразована в произвольную последовательность из ( q -1) B и p A, путем нахождения первого B, который нарушает правило (вызывая ничью подсчетов голосов), и удаления его, а также перестановки порядка оставшихся частей. Чтобы обратить процесс, возьмите любую последовательность из ( 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}}.}$

Вариантную задачу можно решить методом отражения аналогично исходной задаче. Число возможных последовательностей голосования равно . Назовем последовательность «плохой», если второй кандидат когда-либо впереди, и если число плохих последовательностей можно перечислить, то число «хороших» последовательностей можно найти вычитанием, а вероятность можно вычислить.${\displaystyle {\tbinom {p+q}{q}}}$

Представьте последовательность голосования в виде решетчатого пути на декартовой плоскости следующим образом:

• Начните путь с (0, 0)
• Каждый раз, когда поступает голос за первого кандидата, переместитесь вправо на 1 единицу.
• Каждый раз, когда поступает голос за второго кандидата, поднимитесь на 1 единицу.

Каждый такой путь соответствует уникальной последовательности голосов и заканчивается в точке ( p , q ). Последовательность является «хорошей» ровно тогда, когда соответствующий путь никогда не выходит за пределы диагональной линии y  =  x ; эквивалентно, последовательность является «плохой» ровно тогда, когда соответствующий путь касается линии y  =  x  + 1.

Для каждого «плохого» пути P определите новый путь P ′, отразив часть P до первой точки, в которой она касается линии, пересекающей его. P ′ — это путь из (−1, 1) в ( p ,  q ). Та же операция, примененная снова, восстанавливает исходный P . Это создает однозначное соответствие между «плохими» путями и путями из (−1, 1) в ( p ,  q ). Количество этих путей равно и, таким образом, это количество «плохих» последовательностей. Это оставляет количество «хороших» последовательностей как${\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}}}$

На самом деле, решения исходной задачи и вариантной задачи легко связаны. Чтобы кандидат А был строго впереди на протяжении всего подсчета голосов, он должен получить первый голос, а для остальных голосов (игнорируя первый) он должен быть либо строго впереди, либо иметь равные голоса на протяжении всего подсчета. Следовательно, решение исходной задачи:

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

по мере необходимости.

Наоборот, случай равенства голосов может быть получен из случая равенства голосов. Обратите внимание, что количество последовательностей равенства голосов с p+1 голосами за A равно количеству последовательностей равенства голосов с p голосами за A. Количество голосов без равенства голосов с p + 1 голосами за голоса за A равно , что путем алгебраических манипуляций равно , поэтому доля последовательностей с p голосами за голоса за A равна .${\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}}}$

• Теоремы голосования, старые и новые, Л. Аддарио-Берри, Б. А. Рид , 2007, в «Горизонтах комбинаторики», редакторы Эрвин Дьери, Г. Катона, Дьюла О.Х. Катона, Ласло Ловас , Springer, 2008, ISBN 978-3-540-77199-9 

• Проблема с бюллетенями (включает сканы оригинальных французских статей и английские переводы)
• Бернар Брю, Уроки расчета вероятностей Жозефа Бертрана, история проблемы (на французском языке)
• Вайсштейн, Эрик В. «Проблема голосования». Математический мир .