對返回真或假的演算法進行理論分析,基於給定機率的研究
P粉026665919
2023-09-05 19:57:42
<p>我想實作一個方法,以<code>n/m</code> 的機率回傳<code>true</code>,以<code>(m-n)/m</code> 的機率回傳<code>false</code>。 </p>
<p>例如,我想以 7/10000 的機率獲得 <code>true</code>。 </p>
<p>為了實現這個目標,我先從函數 <code>getRandomIntUnderN</code> 中取得一個小於 10000 的隨機整數 <code>n</code>。然後,我判斷 <code>n</code> 是否小於 (7 1),如果是,則回傳 <code>true</code>,否則回傳 <code>false</code>。 </p>
<p>下面是我的實作:</p>
<p>
<pre class="brush:js;toolbar:false;">// 0 is included while n is not
const getRandomIntUnderN = (n) => {
const rn = Math.random() * n
return Math.trunc(rn)
}
// the opportunity of a truthy return value is n/m
const goAtChance = (n, m) => {
return getRandomIntUnderN(m) < n
}
// a opportunity of 7‰ to return true
console.log(goAtChance(7, 10000))</pre>
</p>
<p>我的問題是:我只判斷 <code>n</code> 是否小於 (7 1) 來達到預期的完美機率,這樣可以嗎? </p>
<p>一方面,從 1 到 7 的數字在 1 到 10000 的範圍內不夠離散分佈:似乎存在一種偏差,使得返回真值的可能性較小。 </p>
<p>另一方面,由於我可以從 <code>getRandomIntUnderN</code> 中取得純隨機數,因此機率不會受到我選擇哪些數字來決定傳回值的影響。它可以是[1,2,3,4,5,6,7],[21,22,23,24,25,26,27],[23,55,3,66,762,92,123] 或任何小於10000的數字。 </p>
<p>那麼,哪一種觀點才是正確的呢? </p>
這不是你實現的方式。你的程式碼檢查n是否小於7,這是正確的方式。
這個陳述是從哪裡來的?你肯定可以測試這個前提...並看看它有多大可能性。
這是真的。
如何測試
你可以很容易地測試你的實作的分佈。你可以反覆呼叫這個函數並記錄你得到的結果,然後看看它隨時間的變化。在統計學中,樣本的大小越大,結果越可靠。
這是一個程式碼片段,它不斷執行
goAtChance
函數並記錄呼叫的總次數和true
結果的數量。每隔10毫秒,結果會在頁面上更新,包括true
數量與總數的比例。如果一切正常,這個比例隨時間應該趨近於0.0007。