Theoretical analysis of algorithms that return true or false, based on the study of given probabilities

Question

<p>I want to implement a method that returns <code>true</code> with probability of <code>n/m</code> Probability returns <code>false</code>. </p> <p>For example, I want to get <code>true</code> with a probability of 7/10000. </p> <p>To achieve this, I first obtain a random integer

P粉026665919544 days ago650

Answer 1

This is not how you implement it. Your code checks if n is less than 7, which is the correct way.

Where does this statement come from? You could definitely test this premise...and see how possible it is.

This is real.

How to test

You can easily test the distribution of your implementation. You can call this function repeatedly and record the result you get and see how it changes over time. In statistics, the larger the sample size, the more reliable the results.

This is a code snippet that continuously executes the goAtChance function and records the total number of calls and the number of true results. Every 10 milliseconds, the results are updated on the page, including the ratio of the number of true to the total. If all goes well, this ratio should approach 0.0007 over time.

const getRandomIntUnderN = (n) => Math.floor(Math.random() * n);
const goAtChance = (n, m) => getRandomIntUnderN(m) < n; 

let [outTotal, outHits, outRatio] = document.querySelectorAll("span");

let hits = 0; // Number of results that are true
let total = 0; // Total number of results

requestAnimationFrame(function loop() {
   let deadline = performance.now() + 10;
   do {
     hits += goAtChance(7, 10000); // boolean coerces to 0 or 1
     total++;
   } while (performance.now() < deadline);
   // Show the accumulated results
   outTotal.textContent = total;
   outHits.textContent = hits;
   outRatio.textContent = (hits / total).toFixed(8);
   requestAnimationFrame(loop); // Allow screen to update and then continue
});

样本数：<span></span><br>
命中数：<span></span><br>
比例：<span></span>