Как рассчитать вероятность победы кандидата в президенты?

У меня есть объект вроде

const data = {
    'Washington' : { ElectoralVotes : 12, RChance: 0 },
    'Oregon': { ElectoralVotes: 7, RChance: 15 }, 
    .
    .
    . 
    'Hawaii' : { ElectoralVotes: 4, RChance : 35 }
}

где пара ключ-значение, например

'Washington' : { ElectoralVotes : 12, RChance: 0 }

означает "Штат Вашингтон имеет 12 голосов выборщиков, и у кандидата-республиканца есть 0% шансов на победу в штате". Исходя из этого, я пытаюсь приблизить шансы на победу республиканцев.

Я понимаю, что существует 2^51 поднаборов состояний, поэтому правильный метод, требующий слишком большого объема вычислений для обычных компьютеров, будет

total = 0;
For each array A in [ [], ['Washington'], ['Oreogon'], ... , ['Washington', 'Oregon', ..., 'Hawaii'] ]
    If (sum of electoral votes of states in A) >= 270
         p = multiply together chances of winning states in A
         total += p;

а затем total - это шанс на победу республиканца. Но поскольку я не могу этого сделать, скажем, вместо этого я запускаю процедуру над случайным набором из 2^10 наборов состояний. Должен ли я затем умножить total на 2^41, чтобы получить приблизительное истинное значение?


javascript algorithm statistics probability statistics-bootstrap
person user6048670    schedule 15.07.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Проблема с решением, которое вы описываете в своем вопросе, заключается в том, что необходимо учитывать экспоненциально большое количество подмножеств состояний. Это сделает решение невозможным, даже если набор состояний относительно мал (например, 50). Однако вы можете решить эту проблему с помощью динамического программирования за время O(NS), где N — общее количество голосов выборщиков, а S — количество штатов.

Начните с массива P размера N+1. Запись i в массиве будет представлять вероятность того, что республиканец получит i голосов выборщиков. Он имеет размер N+1, потому что количество голосов, которое они могут получить, равно от 0 до N включительно.

Начните массив с инициализации 0, за исключением первой записи 1. Это описывает вероятности после того, как ни одно из штатов не было включено в расчет: они обязательно получат 0 голосов выборщиков, если штаты еще не включены.

Теперь для нового штата (скажем, Вашингтона) мы можем обновить массив, включив в него и этот штат. Допустим, есть k голосов выборщиков, и вероятность того, что наш кандидат победит, равна p.

Пусть P2 будет новым массивом вероятностей. Если i ‹ k, то:

P2[i] = P[i] * (p - 1)

А если i >= k, то:

P2[i] = P[i] * (p - 1) + P[i-k] * p

То есть вероятность того, что кандидат сейчас имеет i голосов, равна вероятности того, что у него уже было i голосов и он потерял Вашингтон, плюс вероятность того, что ранее у него было i-k голосов (если это возможно) и он выиграл Вашингтон.

Как только мы включили все подобные штаты, вероятность того, что они выиграют выборы, равна сумме вероятностей того, что они получат i голосов, где i > N/2.

В псевдокоде:

P[] = {1, 0, 0, ..., 0} // size N+1
for state of all_states {
    P2 = new array of size N+1.
    for i = 0, 1 ... N {
        let p = state.RChance / 100.0
        let k = state.ElectoralVotes
        P2[i] = P[i] * (1 - p)
        if i >= k {
            P2[i] += P[i - k] * p
        }
    }
    P = P2
}
win_probability = sum(P[i] for i = floor(N/2)+1 ... N)

В принципе, можно избежать массива P2, обновив P на месте, но это немного сложнее в кодировании (потому что вам придется выполнять итерацию в обратном направлении, чтобы избежать изменения записей, которые вам позже понадобятся для чтения). Также в принципе массив P может иметь размер floor(N/2) + 2, причем последний элемент непосредственно представляет вероятность выигрыша. Но опять же, это еще больше усложняет кодирование.

person Paul Hankin    schedule 15.07.2016
comment
@ user6048670: Это отличный ответ на заданный вопрос, но результат неприменим к реальному миру. Вопрос (и ответ) предполагают, что результаты в каждом состоянии независимы, но это даже не грубое приближение; напротив, результаты состояния сильно коррелируют друг с другом, в результате чего p(a и b) более близко аппроксимируется min(p(a), p(b)), чем p(a)×p(b). ). - person rici; 16.07.2016