如何計算總統候選人獲勝的概率？

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是機會，共和黨勝。但是由於我不能那樣做，我們假設我通過一系列隨機的狀態集來運行該過程。那麼我會乘以total2^41以獲得真實值的近似值嗎？

Answer 1

在你的問題你所描述的解決方案的問題是，有一個指數大量狀態的子集來考慮的。即使當一組狀態相對較小時（例如：50），這也會使解決方案不可行。但是，您可以使用時間O（NS）中的動態規劃來解決此問題，其中N是選舉投票總數，S是狀態數。

開始用大小爲N + 1的數組P上。條目i中的條目將代表共和黨人獲得我選舉人票的概率。它的大小爲N + 1，因爲它們可以得到的票數是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 

也就是說，考生現在有我投票的可能性是，他們已經有了我的概率他們失去了華盛頓，加上他們以前擁有ik投票的可能性（如果可能的話），他們贏得了華盛頓。

一旦我們提供了這樣所有的州，他們在大選中獲勝的概率是具有我投票，其中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，最後一個元素直接代表勝利概率。但是，這又使得代碼更加簡單。