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

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

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

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

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

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

Пример

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

АААББ
ОТЕЦ
ОТЕЦ
БАААБ
ОТЕЦ
АБАБА
БАБА
ОТЕЦ
ДОЧЬ
ББААА

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

Кандидат	А	А	Б	А	Б
А	1	2	2	3	3
Б	0	0	1	1	2

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

Кандидат	А	А	Б	Б	А
А	1	2	2	2	3
Б	0	0	1	2	2

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

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

Когда $m=0$ и $n$ четно, это дает каталонское число ${\frac {1}{{\tfrac {n}{2}}+1}}{\binom {n}{\tfrac {n}{2}}}$ . Таким образом, вероятность того, что случайное блуждание никогда не будет отрицательным и вовремя вернется в исходное положение $n$ является $2^{-n}{\frac {1}{{\tfrac {n}{2}}+1}}{\binom {n}{\tfrac {n}{2}}}$ . По формуле Стирлинга, когда $n\to \infty$ , эта вероятность $\sim {\frac {\sqrt {2}}{n^{3/2}}}$ .

[Обратите внимание, что $m,n$ имеют такую же четность следующим образом: пусть $P$ — число «положительных» ходов, т. е. вправо, и пусть $N$ — количество «отрицательных» ходов, т. е. влево. С $P+N=n$ и $P-N=m$ , у нас есть $P={\frac {n+m}{2}}$ и $N={\frac {n-m}{2}}$ . С $P$ и $N$ являются целыми числами, $m,n$ имеют одинаковое соотношение]

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

Чтобы А строго опережал Б на протяжении всего подсчета голосов, не может быть ничьей. Разделите подсчетные последовательности по первому голосованию. Любая последовательность, начинающаяся с голосования за B, в какой-то момент должна привести к ничьей, потому что A в конечном итоге побеждает. Для любой последовательности, которая начинается с A и достигает ничьей, отразите голоса до точки первой ничьей (так что любое A становится B и наоборот), чтобы получить последовательность, которая начинается с B. Следовательно, каждая последовательность, которая начинается с A и достигает ничьей, находится во взаимно однозначном соответствии с последовательностью, которая начинается с B, и вероятность того, что последовательность начинается с B, равна $q/(p+q)$ , поэтому вероятность того, что A всегда лидирует в голосовании, равна

=1-

вероятность последовательностей, которые связаны в какой-то момент

=1-

вероятность последовательностей, которые связаны в какой-то момент и начинаются с A или B

=1-2\times (

вероятность последовательностей, которые связаны в какой-то момент и начинаются с B

)

=1-2\times (

вероятность того, что последовательность начинается с B

)

=1-2{\frac {q}{p+q}}={\frac {p-q}{p+q}}

Доказательство по индукции

Другой метод доказательства — математическая индукция :

Мы ослабляем условие $p>q$ к $p\geq q$ . Очевидно, что теорема верна, если $p=q$ , так как в этом случае первый кандидат не будет строго впереди после подсчета всех голосов (поэтому вероятность равна 0).
Очевидно, что теорема верна, если p > 0 и q = 0, когда вероятность равна 1, учитывая, что первый кандидат получает все голоса; это также верно, когда p = q > 0, как мы только что видели.
Предположим, что это верно как при p = a − 1 и q = b , так и при p = a и q = b − 1, при a > b > 0. (Нам нет необходимости рассматривать случай $a=b$ здесь, так как мы уже избавились от него раньше.) Тогда, рассматривая случай с p = a и q = b , последний подсчитанный голос приходится либо за первого кандидата с вероятностью a /( a ), либо за второго с вероятностью a /( a + + b b ), или за второго с вероятность 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, где p > q > 0.

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

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

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

Позволять $n=p+q$ . Определите стохастический процесс «обратного счета».

$X_{k}={\frac {S_{n-k}}{n-k}};\quad k=0,1,...,n-1$ где $S_{n-k}$ является преимуществом кандидата A над B после $n-k$ голоса пришли.

Требовать: $X_{k}$ представляет собой мартингальный процесс.

Данный $X_{k}$ , мы это знаем $S_{n-k}=(n-k)X_{k}$ , так из первого $n-k$ голоса, ${\frac {X_{k}+1}{2}}(n-k)$ были за кандидата А, и ${\frac {-X_{k}+1}{2}}(n-k)$ были за кандидата Б.

Итак, с вероятностью ${\frac {X_{k}+1}{2}}$ , у нас есть $S_{n-k-1}=S_{n-k}-1$ , и $X_{k+1}={\frac {n-k}{n-k-1}}X_{k}-{\frac {1}{n-k-1}}$ . Аналогично и для другого. Затем вычислите, чтобы найти $E[X_{k+1}|X_{k}]=X_{k}$ .

Определите время остановки $T$ как минимум $k$ такой, что $X_{k}=0$ , или $n-1$ если такого нет $k$ . Тогда вероятность того, что кандидат А лидирует все время, равна просто $E[X_{T}]$ , что по необязательной теореме об остановке равно $E[X_{T}]=E[X_{0}]={\frac {p-q}{p+q}}$

Доказательства Бертрана и Андре.

Бертран выразил решение как

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

где $\mu =p+q$ общее число избирателей и $m=p$ – число избирателей за первого кандидата. Он утверждает, что результат следует из формулы

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

где $P_{m,\mu }$ — число благоприятных последовательностей, но «кажется вероятным, что такой простой результат можно было бы показать более прямым способом». Более прямое доказательство вскоре представил Дезире Андре. Современные авторы часто ошибочно называют его подход «принципом отражения», но на самом деле он использует перестановку. Он показывает, что «неблагоприятные» последовательности (те, которые достигают промежуточной связи) состоят из равного числа последовательностей, начинающихся с А, и последовательностей, начинающихся с В. Всякая последовательность, начинающаяся с В, является неблагоприятной, и существуют ${\tbinom {p+q-1}{q-1}}$ такие последовательности, в которых за 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 равно

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

и, таким образом, требуемая вероятность равна

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

как и ожидалось.

Вариант: разрешены ничьи

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

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

Вариантная задача может быть решена методом отражения аналогично исходной задаче. Число возможных последовательностей голосования равно ${\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 ). Число этих путей ${\tbinom {p+q}{q-1}}$ и это количество «плохих» последовательностей. В результате количество «хороших» последовательностей остается равным

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

Поскольку существуют ${\tbinom {p+q}{q}}$ В целом вероятность того, что последовательность окажется хорошей, равна ${\tfrac {p+1-q}{p+1}}$ .

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

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

Примечания

^ Бартон, Делавэр; Маллоуз, CL (1965). «Некоторые аспекты случайной последовательности» . Энн. Математика. Статист . 36 : 236–260. дои : 10.1214/aoms/1177700286 .
^ Феллер, Уильям (1968), Введение в теорию вероятностей и ее приложения, том I (3-е изд.), Wiley, стр. 69 .
^ Уитворт, Вашингтон (1878 г.). «Расположение $m$ вещей одного рода и $n$ вещей другого рода при определенных условиях приоритета» . Посланник математики . 8 : 105–114 . Проверено 25 мая 2024 г.
^ Уитворт, Вашингтон (1886 г.). «Глава V». Выбор и шанс (четвертое изд.). Кембридж: Дейтон, Белл и Ко.
^ Ж. Бертран, Решение проблемы, Comptes Rendus de l'Académie des Sciences de Paris 105 (1887), 369.
^ Д. Андре, Прямое решение проблемы, решенной М. Бертраном, Comptes Rendus de l'Académie des Sciences, Paris 105 (1887) 436–437.
^ Рено, Марк (2008). «Потерянные (и найденные) в переводе: реальный метод Андре и его применение к обобщенной задаче голосования» . амер. Математика. Ежемесячно . 115 (4): 358–363.
^ Дворецкий, Арье; Моцкин, Теодор (1947), «Проблема расположения», Duke Mathematical Journal , 14 (2): 305–313, doi : 10.1215/s0012-7094-47-01423-3

Ссылки

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

Внешние ссылки

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

[1] Бартон, Делавэр; Маллоуз, CL (1965). «Некоторые аспекты случайной последовательности» . Энн. Математика. Статист . 36 : 236–260. дои : 10.1214/aoms/1177700286 .

[2] Феллер, Уильям (1968), Введение в теорию вероятностей и ее приложения, том I (3-е изд.), Wiley, стр. 69 .

[3] Уитворт, Вашингтон (1878 г.). «Расположение $m$ вещей одного рода и $n$ вещей другого рода при определенных условиях приоритета» . Посланник математики . 8 : 105–114 . Проверено 25 мая 2024 г.

[4] Уитворт, Вашингтон (1886 г.). «Глава V». Выбор и шанс (четвертое изд.). Кембридж: Дейтон, Белл и Ко.

[5] Ж. Бертран, Решение проблемы, Comptes Rendus de l'Académie des Sciences de Paris 105 (1887), 369.

[6] Д. Андре, Прямое решение проблемы, решенной М. Бертраном, Comptes Rendus de l'Académie des Sciences, Paris 105 (1887) 436–437.

[7] Рено, Марк (2008). «Потерянные (и найденные) в переводе: реальный метод Андре и его применение к обобщенной задаче голосования» . амер. Математика. Ежемесячно . 115 (4): 358–363.

[8] Дворецкий, Арье; Моцкин, Теодор (1947), «Проблема расположения», Duke Mathematical Journal , 14 (2): 305–313, doi : 10.1215/s0012-7094-47-01423-3

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]