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

Question

I want to implement a method that returns true with probability n/m and false with probability (m-n)/m. For example, I want to get true with probability 7/10000. To achieve this goal, I first get a random integer n less than 10000 from the function getRandomIntUnderN. Then, I determine whether n is less than (7+1), and if so, return true, otherwise return false. Here is my implementation: //0isincludedwhilenisnotconstgetRand

P粉616383625 · Answer

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
});

样本数：

命中数：

比例：