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

Question

我有一个对象

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

其中键值对如

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

意味着 "Washinton state has 12 electoral votes and the Republican candidate has a 0% chance of winning the state." 由此我试图估计共和党获胜的可能性。

我意识到有 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的数组，除了第一个条目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 票（如果可能的话）并赢得华盛顿的概率。

Once we've included all the states like this, the probability they win the election is the sum of the probabilities of them having i votes where 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)

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

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

How do I calculate the probability of a presidential candidate winning?

javascript

algorithm

statistics

probability

statistics-bootstrap