Analyse théorique d'algorithmes qui renvoient vrai ou faux, basée sur l'étude de probabilités données

Question

Je souhaite implémenter une méthode qui renvoie vrai avec une probabilité n/m et faux avec une probabilité (m-n)/m. Par exemple, je veux obtenir vrai avec une probabilité de 7/10 000. Pour atteindre cet objectif, j'obtiens d'abord un entier aléatoire n inférieur à 10 000 à partir de la fonction getRandomIntUnderN. Ensuite, je détermine si n est inférieur à (7+1), et si c'est le cas, je renvoie vrai, sinon je renvoie faux. Voici mon implémentation : //0isincluswhilenisnotconstgetRand

P粉616383625 · Answer

Ce n’est pas comme ça qu’on fait. Votre code vérifie si n est inférieur à 7, ce qui est la bonne méthode.

D'où vient cette déclaration ? Vous pouvez certainement tester cette prémisse... et voir à quel point c'est possible.

C'est vrai.

Comment tester

Vous pouvez facilement tester la distribution de votre implémentation. Vous pouvez appeler cette fonction à plusieurs reprises, enregistrer le résultat que vous obtenez et voir comment il évolue au fil du temps. En statistique, plus la taille de l’échantillon est grande, plus les résultats sont fiables.

Il s'agit d'un extrait de code qui exécute en continu le rapport entre goAtChance函数并记录调用的总次数和true结果的数量。每隔10毫秒，结果会在页面上更新，包括truenombre et total. Si tout se passe bien, ce ratio devrait se rapprocher de 0,0007 au fil du temps.

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

样本数：

命中数：

比例：