Generating Random Numbers/ru

│ Deutsch (de) │ English (en) │ suomi (fi) │ français (fr) │ polski (pl) │ русский (ru) │

Случайные числа являются важными ресурсами для научных приложений, образования, разработки игр и визуализации. Они играют ключевую роль в численном моделировании.

Генерируемые алгоритмом случайные числа являются псевдослучайными числами. Они принадлежат (большому) набору повторяющихся чисел, последовательность которых невозможно или, по крайней мере, трудно предсказать. В отличие от Delphi, в котором используется линейный конгруэнтный генератор (см. Delphi compatible LCG Random), Free Pascal использует алгоритм MersenneTwister для своей стандартной random функции, определенной в RTL. Перед первым использованием генератор случайных чисел FPC должен быть проинициализирован единичным вызовом функции randomize, которая устанавливает начальное число генератора. Предпочтительнее это делать на этапе запуска программы.

Кроме того, в системах на основе Unix и Linux доступны виртуальные устройства /dev/random и /dev/urandom. Они генерируют (псевдо) случайные числа на основе оборудования.

Третий вариант - использовать случайные числа из внешних источников, либо из специализированных аппаратных устройств, либо из общедоступных источников, например. на основе данных радиоактивного распада.

Равномерное распределение

Непрерывное равномерное распределение (также называемое прямоугольным распределением) представляет собой семейство симметричных вероятностных распределений. Здесь для каждого члена семьи все интервалы одинаковой длины в поддержке распределения одинаково вероятны.

Стандартная функция RTL random генерирует случайные числа с равномерным распределением. При вызове без параметра random выдает псевдослучайное число с плавающей запятой в интервале [0, 1), т.е. 0 <= result < 1. Если random вызывается с аргументом longint L, возвращается случайное значение longint в интервале [0, L).

Дополнительный набор равномерно распределенных генераторов случайных чисел представлен в генераторах псевдослучайных чисел Марсальи.

Равномерно распределенные случайные числа полезны не для каждого приложения. Для создания случайных чисел других распределений необходимы специальные алгоритмы.

Нормальное (гауссово) распределение

Одним из наиболее распространенных алгоритмов получения нормально распределенных случайных чисел из равномерно распределенных случайных чисел является преобразование Бокса-Мюллера. Следующая функция вычисляет распределенные по Гауссу случайные числа:

 function rnorm (mean, sd: real): real;
 {Вычисляет гауссовы случайные числа в соответствии с преобразованием Бокса-Мюллера}
  var
   u1, u2: real;
 begin
   u1 := random;
   u2 := random;
   rnorm := mean * abs(1 + sqrt(-2 * (ln(u1))) * cos(2 * pi * u2) * sd);
  end;

Тот же алгоритм используется функцией randg randg из модуля RTL math:

function randg(mean,stddev: float): float;

Экспоненциальное распределение

Экспоненциальное распределение часто встречается в реальных задачах. Классическим примером является распределение времени ожидания между независимыми пуассоновскими случайными событиями, например, радиоактивный распад ядер [Press et al. 1989].

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

function randomExp(a, rate: real): real;
const
  RESOLUTION = 1000;
var
  unif: real;
begin
  if rate = 0 then
    randomExp := NaN
  else
  begin
    repeat
      unif := random(RESOLUTION) / RESOLUTION;
    until unif <> 0;
    randomExp := a - rate * ln(unif);
  end;
end;

Гамма-распределение

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

Следующая функция возвращает одно действительное случайное число из гамма-распределения. Форма распределения определяется параметрами a, b и c. Функция использует функцию randomExp, как определено выше.

function randomGamma(a, b, c: real): real;
const
  RESOLUTION = 1000;
  T = 4.5;
  D = 1 + ln(T);
var
  unif: real;
  A2, B2, C2, Q, p, y: real;
  p1, p2, v, w, z: real;
  found: boolean;
begin
  A2 := 1 / sqrt(2 * c - 1);
  B2 := c - ln(4);
  Q := c + 1 / A2;
  C2 := 1 + c / exp(1);
  found := False;
  if c < 1 then
  begin
    repeat
      repeat
        unif := random(RESOLUTION) / RESOLUTION;
      until unif > 0;
      p := C2 * unif;
      if p > 1 then
      begin
        repeat
          unif := random(RESOLUTION) / RESOLUTION;
        until unif > 0;
        y := -ln((C2 - p) / c);
        if unif <= power(y, c - 1) then
        begin
          randomGamma := a + b * y;
          found := True;
        end;
      end
      else
      begin
        y := power(p, 1 / c);
        if unif <= exp(-y) then
        begin
          randomGamma := a + b * y;
          found := True;
        end;
      end;
    until found;
  end
  else if c = 1 then
    { Гамма-распределение становится экспоненциальным, если c = 1 }
  begin
    randomGamma := randomExp(a, b);
  end
  else
  begin
    repeat
      repeat
        p1 := random(RESOLUTION) / RESOLUTION;
      until p1 > 0;
      repeat
        p2 := random(RESOLUTION) / RESOLUTION;
      until p2 > 0;
      v := A2 * ln(p1 / (1 - p1));
      y := c * exp(v);
      z := p1 * p1 * p2;
      w := B2 + Q * v - y;
      if (w + D - T * z >= 0) or (w >= ln(z)) then
      begin
        randomGamma := a + b * y;
        found := True;
      end;
    until found;
  end;
end;

Распределение Эрланга

Распределение Эрланга - это двухпараметрическое семейство непрерывных распределений вероятностей. Это обобщение экспоненциального распределения и частный случай гамма-распределения, где c - целое число. Распределение Эрланга было впервые описано Агнером Крарупом Эрлангом для моделирования временного интервала между телефонными звонками. Он используется для теории очередей и для моделирования линий ожидания.

  function randomErlang(mean: real; k: integer): real;
  const
    RESOLUTION = 1000;
  var
    i: integer;
    unif, prod: real;
  begin
    if (mean <= 0) or (k < 1) then
      randomErlang := NaN
    else
    begin
      prod := 1;
      for i := 1 to k do
      begin
        repeat
          unif := random(RESOLUTION) / RESOLUTION;
        until unif <> 0;
        prod := prod * unif;
      end;
      randomErlang := -mean * ln(prod);
    end;
  end;

Распределение Пуассона

Распределение Пуассона применяется к целочисленным значениям. Оно представляет вероятность успеха k, когда вероятность успеха в каждом испытании мала, а частота появления (среднее значение) постоянна.

function randomPoisson(mean: integer): integer;
{ Генератор для распределения Пуассона (алгоритм Дональда Кнута) }
const
  RESOLUTION = 1000;
var
  k: integer;
  b, l: real;
begin
  assert(mean > 0, 'mean < 1');
  k := 0;
  b := 1;
  l := exp(-mean);
  while b > l do
  begin
    k := k + 1;
    b := b * random(RESOLUTION) / RESOLUTION;
  end;
  randomPoisson := k - 1;
end;

t-распределение (Стьюдента)

t-распределение (также относится к t-распределению Стьюдента, поскольку оно было опубликовано Уильямом Сили Госсетом в 1908 году под псевдонимом Student) - это непрерывное распределение вероятностей. Его форма определяется одним параметром, степенями свободы (df). В статистике много оценок являются t-распределением. Таким образом, t-распределение Стьюдента играет главную роль в ряде широко используемых статистических анализов, включая t-критерий Стьюдента для оценки статистической значимости разницы между двумя средними выборками, построение доверительных интервалов для разницы между двумя средними значениями, и в линейном регрессионном анализе. Т-распределение также возникает при Байесовском выводе данных из нормального семейства.

Следующий алгоритм зависит от функции RTL random и от функции randomChisq

function randomT(df: integer): real;
{ Генератор для распределения Стьюдента }
begin
  if df < 1 then 
    randomT := NaN
  else begin
    randomT := randg(0, 1) / sqrt(randomChisq(df) / df);
  end;
end;

Распределение хи-квадрат

Распределение хи-квадрат - это непрерывное распределение случайных чисел со степенями свободы df. Это распределение суммы квадратов независимых стандартных нормальных случайных величин. Распределение хи-квадрат имеет множество применений в выводной статистике, например, в оценке дисперсий и для тестов хи-квадрат. Это специальное гамма-распределение с c = df/ 2 and b = 2. Поэтому следующая функция зависит от функции randomGamma.

function randomChisq(df: integer): real;
begin
  if df < 1 then 
    randomChisq := NaN
  else
    randomChisq := randomGamma(0, 2, 0.5 * df);
end;

F-распределение (Фишера)

Распределение F, также называемое распределением Фишера-Снедекора, является непрерывным распределением вероятности. Используется для F-теста(критерия Фишера) и ANOVA(ANalysis Of VAriance, или дисперсионный анализ). Оно имеет две степени свободы, которые служат параметрами формы v и w, и являются положительными целыми числами. Следующая функция randomF использует randomChisq.

function randomF(v, w: integer): real;
begin
  if (v < 1) or (w < 1) then
    randomF := NaN
  else
    randomF := randomChisq(v) / v / (randomChisq(w) / w);
end;

См.также

• Dev random
• Functions for descriptive statistics
• Marsaglia's pseudo random number generators
• A simple implementation of the Mersenne twister
• Delphi compatible LCG Random

Рекомендации

1. G. E. P. Box and Mervin E. Muller, A Note on the Generation of Random Normal Deviates, The Annals of Mathematical Statistics (1958), Vol. 29, No. 2 pp. 610–611
2. Dietrich, J. W. (2002). Der Hypophysen-Schilddrüsen-Regelkreis. Berlin, Germany: Logos-Verlag Berlin. ISBN 978-3-89722-850-4. OCLC 50451543.
3. Press, W. H., B. P. Flannery, S. A. Teukolsky, W. T. Vetterling (1989). Numerical Recipes in Pascal. The Art of Scientific Computing, Cambridge University Press, ISBN 0-521-37516-9.
4. Richard Saucier, Computer Generation of Statistical Distributions, ARL-TR-2168, US Army Research Laboratory, Aberdeen Proving Ground, MD, 21005-5068, March 2000.
5. R.U. Seydel, Generating Random Numbers with Specified Distributions. In: Tools for Computational Finance, Universitext, DOI 10.1007/978-1-4471-2993-6_2, © Springer-Verlag London Limited 2012
6. Christian Walck, Hand-book on STATISTICAL DISTRIBUTIONS for experimentalists, Internal Report SUF–PFY/96–01, University of Stockholm 2007