Comment générer des nombres aléatoires pondérés : échantillonnage de rejet ou sommation itérative des poids ?

Générer un nombre aléatoire pondéré

Introduction

Dans diverses applications, il est souvent nécessaire de sélectionner un nombre aléatoire parmi un ensemble d’options, où chaque option se voit attribuer une probabilité spécifique d’être choisie. Ce concept est connu sous le nom de génération d'un nombre aléatoire pondéré.

Approche d'échantillonnage par rejet

Une méthode de génération de nombres aléatoires pondérés consiste à utiliser l'échantillonnage par rejet. Cette approche consiste à créer une table de recherche dans laquelle chaque option apparaît autant de fois que le poids qui lui est attribué. Par exemple, si l’option A a une probabilité de 80 %, elle apparaîtra 80 fois dans la table de recherche. Pour générer un nombre aléatoire, un emplacement aléatoire dans le tableau est sélectionné et l'option correspondante est renvoyée.

Avantages et inconvénients de l'échantillonnage par rejet

L'échantillonnage par rejet fournit une constante -performance temporelle pour choisir un nombre aléatoire après la construction de la table de recherche. Cependant, cela nécessite des performances algorithmiques linéaires pour construire le tableau, ce qui peut être problématique pour de grands ensembles d'options ou pour ceux avec des pondérations très précises.

Approche itérative de sommation des poids

Une approche alternative est la sommation itérative des poids. Ici, un nombre aléatoire est généré dans la plage [0,1) et est comparé à la somme cumulée des poids. L'option associée au poids qui dépasse le nombre aléatoire est sélectionnée comme nombre aléatoire pondéré.

Avantages et inconvénients de la sommation itérative des poids

Par rapport à l'échantillonnage de rejet, l'échantillonnage itératif la sommation des poids n'entraîne pas de coûts initiaux mais présente des performances algorithmiques moyennes linéaires par rapport au nombre d'options dans l'ensemble. Cela suppose également que la somme des poids est égale à un.

Considérations relatives à la mise en œuvre

Lors de la mise en œuvre de ces approches, il est recommandé de créer une fonction d'ordre supérieur qui prend une spécification de poids. et renvoie une fonction qui génère des nombres aléatoires pondérés. Cela permet la réutilisation et évite les frais généraux liés à la création de la table de recherche ou à l'accumulation des poids plusieurs fois.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!