Вероятностный отбор из набора

Question

Предположим, я хочу случайным образом выбрать число n от 0 до 30, где распределение является произвольным, а не равномерным. Каждое число имеет соответствующий вес P (n): P (0) = 5, P (1) = 1, P (2) = 30, P (3) = 25 и так далее и тому подобное. Как сделать случайный выбор из этого набора, чтобы вероятность выбора числа была пропорциональна его весу?

Как вообще называется этот тип случайного выбора?

Я вижу один из способов его реализации:

1. Составить справочную таблицу V, где V (n) = V (n-1) + P (n); с базовым регистром V (0) = P (0).
2. Генерирует случайное число X с равномерным распределением между 0 и максимальным значением V.
3. Найдите наименьшее значение n такое, что V (n)> X.

Что-то подобное уже реализовано в библиотеке? (С использованием Perl.)

Answer 1

Это на самом деле очень популярная проблема, которая называется взвешенный случайный выбор (или иногда взвешенный случайный выбор ). Вот полная статья об этом.

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";