如何计算总统候选人获胜的概率

Question

我有一个像这样的对象

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 得到真实值的近似值吗？

Answer 1

您在问题中描述的解决方案的问题在于，需要考虑指数级数量的状态子集。这将使解决方案不可行，即使状态集相对较小（例如：50）。但是，您可以使用时间 O（NS） 中的动态规划来解决此问题，其中 N 是选举人票总数，S 是州数。

从大小为 N+1 的数组 P 开始。数组中的条目 i 将表示共和党获得 i 选举人票的概率。它的大小为 N+1，因为他们可以获得的票数是 0 到 N（包括 0 到 N）。

启动初始化为 0 的数组，第一个条目 1 除外。这描述了计算中没有州被包括后的概率：如果还没有州被包括在内，他们肯定会获得0张选举人票。

现在，对于一个新州（例如华盛顿州），我们也可以更新数组以包含该州。假设有 k 张选举人票，我们的候选人在那里获胜的概率为 p。

让P2成为新的概率数组。如果我<k，那么：>

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

如果我>= k，那么：

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

也就是说，候选人现在拥有 i 票的概率是他们已经拥有 i 票并且他们失去了华盛顿的概率

，加上他们以前拥有 i-k 票（如果可能的话）并且他们赢得了华盛顿的概率。

一旦我们把所有这样的州都包括在内，他们赢得选举的概率就是他们在我> N/2 的地方投了 i 票的概率之和。

在伪代码中：

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)

原则上，可以通过就地更新P来避免P2数组，但编码有点棘手（因为您必须向后迭代以避免更改稍后需要读取的条目）。同样原则上，数组 P 的大小可以是 floor(N/2) + 2 最后一个元素直接表示获胜概率。但同样，这使得编码更加繁琐。