对返回真或假的算法进行理论分析,基于给定概率的研究
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。