Perl. Библиотека программиста

Генерация случайных чисел с неравномерным распределением

Проблема

Требуется генерировать случайные числа в ситуации, когда одни значения появляются с большей вероятностью, чем другие (неравномерное распределение). Допустим, вы отображаете на своей Web-странице случайный баннер и у вас имеется набор весовых коэффициентов, определяющих частоту появления того или иного баннера. А может быть, вы имитируете нормальное распределение (закон распределения Гаусса).

Решение

Следующая функция генерирует случайные числа с нормальным распределением, со стандартным отклонением 1 и нулевым математическим ожиданием.

sub gaussian_rand {	
  mу ($u1, $u2);                  # Случайные числа с однородным распределением
  mу $w;                          # Отклонение, затем весовой коэффициент
  mу ($g1, $g2);                  # Числа с гауссовским распределением
  do {
    $u1 = 2 * rand() - 1;
    $u2 = 2 * rand() - 1;
    $w = $u1*$u1 + $u2-u2;
  } while ($w >= 1);
  $w = sqrt( (-2 * log($w)) / $w);
  $g2 = $u1 - $w;
  $g1 = $u2 * $w;
  # Возвратить оба числа или только одно
  return wantarray ? ($g1, $g2) : $g1;
}

Если у вас есть список весовых коэффициентов и значений и вы хотите выбирать элементы списка случайным образом, выполните два последовательных шага. Сначала превратите весовые коэффициенты в вероятностное распределение с помощью приведенной ниже функции weight_to_dist, а затем воспользуйтесь функцией weighted_rand для случайного выбора чисел.

# weight_to_dist: получает хэш весовых коэффициентов
# и возвращает хэш вероятностей
sub weight_to_dist {
  my %weights = @_;
  my %dist    = ();
  my $total   = 0;
  my ($key, $weight);
  local $_;
  foreach (values %weights) {
    $total += $_;
  }
  while ( ($key, $weight) = each %weights ) {
    $dist{$key} = $weight/$total;
  }
  return %dist;
}
# weighted_ran : получает хэш вероятностей
# и возвращает случайный элемент хэша
sub weighted_rand {
  my %dist = @_;
  my ($key, $weight);
  while (1) {              # Чтобы избежать погрешностей вычислений
                           # с плавающей запятой
    my $rand = rand;
    while ( ($key, $weight) = each %dist ) {
      return $key if ($rand -= $weight) < 0;
    }
  }
}

Комментарий

Функция gaussian_rand реализует полярный метод Бокса—Мюллера для преобразования двух независимых случайных чисел с однородным распределением, лежащих в интервале от 0 до 1 в два числа с математическим ожиданием 0 и стандартным отклонением 1 (то есть распределенных по закону Гаусса). Чтобы сгенерировать числа с другим математическим ожиданием и стандартным отклонением, умножьте выходные данные gaussian_rand на нужное стандартное отклонение и прибавьте математическое ожидание:

# gaussian_rand - см. выше
$mean = 25;
$sdev = 2;
$salary – gaussian_rand() * $sdev + $mean;
printf("You have been hired at \$%.2f\n", $salary);

Функция weighted_rand получает случайное число из интервала от 0 до 1. Затем она использует вероятности, сгенерированные weight_to_dist, и определяет, какому элементу соответствует это случайное число. Из-за погрешностей представления с плавающей запятой накопленные ошибки могут привести к тому, что возвращаемый элемент не будет найден. Поэтому код размещается в цикле while, который в случае неудачи выбирает новое случайное число и делает очередную попытку.

Кроме того, модуль Math::Random с CPAN содержит функции, генерирующие случайные числа для многих распределений.

См. также

Описание функции rand