Введение

Теорема, дающая вероятность того, что победитель выборов будет лидировать перед проигравшим на протяжении всего подсчета голосов.

В комбинаторике задача о бюллетенях Бертрана формулируется следующим образом: "В выборах, где кандидат А получает p голосов, а кандидат Б получает q голосов при p > q, какова вероятность того, что А будет строго опережать Б на протяжении всего подсчета?" Ответ:

Этот результат был впервые опубликован У. А. Уитвортом в 1878 году, но назван в честь Жозефа Луи Франсуа Бертрана, который заново открыл его в 1887 году. В оригинальной статье Бертран представил эскиз доказательства, основанного на общей формуле для числа благоприятных последовательностей с использованием рекуррентного соотношения. Он отметил, что, вероятно, такой простой результат можно доказать более прямым методом. Такое доказательство было дано Дезире Андре, который исходил из наблюдения, что неблагоприятные последовательности можно разделить на два равновероятных случая, один из которых (случай, когда Б получает первый голос) легко вычислить; он доказал равенство с помощью явной биекции. Вариант его метода широко известен как метод отражения Андре, хотя сам Андре не использовал никаких отражений. Теорема о бюллетенях Бертрана связана с леммой о циклах. Они дают схожие формулы, но лемма о циклах рассматривает циклические сдвиги заданного порядка подсчета голосов, а не все перестановки.

Благоприятные решения

Вместо вычисления вероятности того, что случайный порядок подсчета голосов обладает нужным свойством, можно вычислить количество благоприятных порядков подсчета, а затем разделить его на общее количество возможных порядков подсчета голосов. (Этот метод использовал Бертран.) Общее количество порядков – это биномиальный коэффициент; доказательство Бертрана показывает, что количество благоприятных порядков подсчета голосов равно (хотя он и не приводит это число явно). И действительно, после деления получается .

Случайные прогулки

Еще одна эквивалентная задача — вычислить количество случайных блужданий по целым числам, состоящих из n шагов единичной длины, начинающихся в начале координат и заканчивающихся в точке m, которые никогда не становятся отрицательными. Поскольку n и m имеют одинаковую четность и , это число равно

Когда и является четным, это дает число Каталана. Таким образом, вероятность того, что случайное блуждание никогда не станет отрицательным и вернется в начало координат в момент времени , по формуле Стирлинга, когда , эта вероятность равна.
[Отметим, что n и m имеют одинаковую четность следующим образом: пусть p будет числом "положительных" шагов, то есть вправо, а q — числом "отрицательных" шагов, то есть влево. Поскольку n = p + q и m = p - q, то p = (n + m) / 2 и q = (n - m) / 2. Поскольку n и m — целые числа, p и q также являются целыми числами и, следовательно, имеют одинаковую четность.]

Доказательство леммы цикла

Простое доказательство основано на лемме о циклах Дворецкого и Мотцкина. Назовем последовательность голосования доминирующей, если A строго опережает B на протяжении всего подсчета голосов. Лемма о циклах утверждает, что любая последовательность, состоящая из A и B, где , имеет ровно доминирующих циклических перестановок. Чтобы понять это, расположите данную последовательность A и B по кругу и последовательно удаляйте смежные пары AB, пока не останутся только A. Каждая из этих A была началом доминирующей циклической перестановки до удаления каких-либо элементов. Таким образом, из всех циклических перестановок любой комбинации A голосов и B голосов, доминирующими являются.

Доказательство мартингалом

Определим стохастический процесс "обратного отсчета", где – это отрыв кандидата А от кандидата Б после подсчета голосов. Утверждение: является мартингалом. Зная , мы знаем, что из первых голосов были отданы за кандидата А, а – за кандидата Б. Следовательно, с вероятностью , мы имеем , и аналогично для другого случая. Затем вычислим, чтобы найти . Определим время остановки как минимальное такое, что , или если такого не существует. Тогда вероятность того, что кандидат А лидирует все время, равна , что, согласно теореме об остановке, равно .