Sélection probabiliste à partir d'un ensemble

Question

Supposons que je souhaite sélectionner aléatoirement un nombre n compris entre 0 et 30, où la distribution est arbitraire et non uniforme. Chaque nombre a un poids correspondant P (n): P (0) = 5, P (1) = 1, P (2) = 30, P (3) = 25, et ainsi de suite. Comment faire une sélection aléatoire de cet ensemble, de sorte que la probabilité de sélectionner un nombre est proportionnelle à son poids?

Qu'est-ce que ce type de sélection aléatoire est appelé?

Je peux voir une façon de la mettre en œuvre:

1. plus d'une table de conversion V où V (n) = V (n-1) + P (n); avec le cas de base V (0) = P (0).
2. générer un nombre aléatoire X avec une répartition uniforme entre 0 et la valeur maximale de V.
3. Trouver la plus petite valeur de n tel que V (n)> X.

est quelque chose comme ça déjà mis en œuvre dans une bibliothèque? (L'utilisation de Perl.)

Answer 1

Ceci est en fait un problème très populaire, et est appelé sélection aléatoire pondéré (ou parfois choix aléatoire pondéré). Voici a complete article à ce sujet.

Answer 2

#!/usr/bin/perl 

use strict; use warnings; 

my @p = map { ($_) x int(1 + rand 50) } 0 .. 30; 
my @s = @p[ map rand @p, 1 .. 10 ]; 
print "@s\n";