Теорема присяжных Кондорсе

редактировать

Теорема присяжных Кондорсе - это политическая теорема об относительной вероятности того, что данная группа людей придет к правильному решению. Теорема была впервые выражена маркизом де Кондорсе в его работе 1785 года « Эссе о применении анализа к вероятности решений большинства».

Предположения теоремы таковы, что группа желает принять решение большинством голосов. Один из двух результатов голосования правильный, и каждый избиратель имеет независимую вероятность p проголосовать за правильное решение. Теорема спрашивает, сколько избирателей мы должны включить в группу. Результат зависит от того, больше или меньше p:

Если p больше 1/2 (вероятность того, что каждый избиратель проголосует правильно), то добавление большего количества избирателей увеличивает вероятность того, что решение большинства будет правильным. В пределе вероятность того, что большинство проголосует правильно, приближается к 1 по мере увеличения числа избирателей.
С другой стороны, если p меньше 1/2 (вероятность того, что каждый избиратель проголосует неправильно), то добавление большего количества избирателей усугубляет ситуацию: оптимальное жюри состоит из одного избирателя.

Начиная с Кондорсе, многие другие исследователи доказали различные другие теоремы присяжных, ослабив некоторые или все предположения Кондорсе.

СОДЕРЖАНИЕ

1 Доказательства ^[2]
- 1.1 Доказательство 1: Расчет вероятности того, что два дополнительных избирателя изменят исход
- 1.2 Доказательство 2: Расчет вероятности правильности решения
2 Асимптотика
3 Теорема в других дисциплинах
4 Дальнейшее чтение
5 Примечания

Доказательства

Доказательство 1: расчет вероятности того, что два дополнительных избирателя изменят исход

Чтобы избежать необходимости в правилах разрешения ничьей, мы предполагаем, что n нечетно. По сути, тот же аргумент работает для четного n, если ничья нарушена честным подбрасыванием монеты.

Теперь предположим, что мы начинаем с n избирателей, и пусть m из них проголосуют правильно.

Подумайте, что произойдет, если мы добавим еще двух голосующих (чтобы общее число оставалось нечетным). Большинство голосов меняется только в двух случаях:

m было на один голос слишком мало, чтобы получить большинство из n голосов, но оба новых избирателя проголосовали правильно.
m просто равно большинству из n голосов, но оба новых избирателя проголосовали неправильно.

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

Ограничивая наше внимание этим случаем, мы можем представить, что первые n -1 голосов аннулируются и что решающий голос подает n-й избиратель. В этом случае вероятность получить правильное большинство составляет всего p. Теперь предположим, что мы отправим двух дополнительных избирателей. Вероятность того, что они изменят неправильное большинство на правильное большинство, равна (1- p) p ², в то время как вероятность того, что они изменят правильное большинство на неправильное большинство, равна p (1- p) (1- p). Первая из этих вероятностей больше второй тогда и только тогда, когда p gt; 1/2, что доказывает теорему.

Доказательство 2: Расчет вероятности того, что решение верное.

Это доказательство прямое; он просто суммирует вероятности большинства. Каждый член суммы умножает количество комбинаций большинства на вероятность этого большинства. Каждая часть отсчитываются с помощью комбинации, п деталей взята K в то время, где п является размером жюри, и к является размером большинства. Вероятности варьируются от 0 (= голос всегда ошибочен) до 1 (= всегда правильный). Каждый человек решает самостоятельно, поэтому вероятность их решений умножается. Вероятность каждого правильного решения p. Вероятность неправильного решения q противоположна p, то есть 1 - p. Обозначение степени, т.е. сокращение для x умножений p. ${\ displaystyle p ^ {x}}$ ${\ displaystyle p ^ {x}}$

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

В качестве примера возьмем простейший случай n = 3, p = 0,8. Нам нужно показать, что у трех человек шанс оказаться правым выше 0,8. Действительно:

0,8 × 0,8 × 0,8 + 0,8 × 0,8 × 0,2 + 0,8 × 0,2 × 0,8 + 0,2 × 0,8 × 0,8 = 0,896.

Асимптотика

Вероятность правильного решения большинством P ( n,  p), когда индивидуальная вероятность p близка к 1/2, линейно растет в единицах p - 1/2. Для n избирателей, каждый из которых имеет вероятность p правильного решения, и для нечетных n (при отсутствии возможных равных):

{\ Displaystyle P (n, p) = 1/2 + c_ {1} (p-1/2) + c_ {3} (p-1/2) ^ {3} + O \ left ((p-1 / 2) ^ {5} \ right),}

{\ Displaystyle P (n, p) = 1/2 + c_ {1} (p-1/2) + c_ {3} (p-1/2) ^ {3} + O \ left ((p-1 / 2) ^ {5} \ right),}

где

{\ displaystyle c_ {1} = {n \ choose {\ lfloor n / 2 \ rfloor}} {\ frac {\ lfloor n / 2 \ rfloor +1} {4 ^ {\ lfloor n / 2 \ rfloor}}} = {\ sqrt {\ frac {2n + 1} {\ pi}}} \ left (1 + {\ frac {1} {16n ^ {2}}} + O (n ^ {- 3}) \ right),}

{\ displaystyle c_ {1} = {n \ choose {\ lfloor n / 2 \ rfloor}} {\ frac {\ lfloor n / 2 \ rfloor +1} {4 ^ {\ lfloor n / 2 \ rfloor}}} = {\ sqrt {\ frac {2n + 1} {\ pi}}} \ left (1 + {\ frac {1} {16n ^ {2}}} + O (n ^ {- 3}) \ right),}

и асимптотическое приближение по n очень точное. Расширение только в нечетных степенях и. Проще говоря, это означает, что, когда решение сложно ( p близко к 1/2), выигрыш от наличия n избирателей растет пропорционально. ${\ displaystyle c_ {3} lt;0}$ $c_ {3} lt;0$ ${\ displaystyle {\ sqrt {n}}}$ ${\ sqrt {n}}$

Теорема в других дисциплинах

Теорема присяжных Кондорсе недавно была использована для концептуализации интеграции оценок, когда несколько читающих врачей (радиологи, эндоскописты и т. Д.) Независимо оценивают изображения на предмет активности болезни. Эта задача возникает при централизованном чтении, выполняемом во время клинических испытаний, и имеет сходство с голосованием. По мнению авторов, применение теоремы может переводить индивидуальные оценки читателей в окончательные оценки математически обоснованным (избегая усреднения порядковых данных), математически поддающимся дальнейшему анализу способом, совместимым с текущая задача оценки (на основе решений о наличии или отсутствии признаков, задача субъективной классификации)

Теорема жюри Кондорсе также используется в ансамблевом обучении в области машинного обучения. Метод ансамбля объединяет предсказания многих индивидуальных классификаторов большинством голосов. Если предположить, что каждый из отдельных классификаторов предсказывает с точностью чуть более 50%, а их прогнозы независимы, тогда совокупность их прогнозов будет намного больше, чем их индивидуальные прогностические оценки.