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

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的数组，除了第一个条目1。这描述了没有状态被计算在内之后的概率:如果还没有状态，他们肯定会得到0张选举人票。

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

设P2 为新的概率数组。如果我 < k，那么:

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

如果 i >= k，那么:

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

也就是说，候选人现在拥有 i 票的概率是他们已经拥有 i 票并且失去华盛顿的概率，加上他们之前拥有 i-k 票(如果可能)并且赢得华盛顿的概率。

p>

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，最后一个元素直接表示获胜概率。但同样，这使得编码变得更加繁琐。