Таким образом,

Заметим, что для выбора М различных чисел из N при использовании алгоритма SELECT должно генерироваться только фиксированное

СГЕНЕРИРОВАННОЕ.

СЛУЧАЙНОЕ

ЧИСЛО

6 7 6 4 3

МЕЖДУ

1-10 1-9 1« 1-7 16

ВЫБРАННОЕ ЧИСЛО

ITEM(6J = e ТЕМ.(71 = 7 1ТЕМ(61 = 10 1ТЕМ(41=4 ТЕМ(Э1=3 Рис. 6.3.1. Пример работы алгоритма SELECT (выбор).

количество М случайных чисел. В действительности объем необходимой работы равен 0{N+M), т. е. алгоритм SELECT выполняет: операторов присваивания на шаге 1;

4М операторов присваивания на шаге 2;

М обращений к генератору случайных чисел на шаге 3. Сравните это с алгоритмом SS, выполняющим:

2 оператора присваивания на шаге 0;

0{N) обращений к генератору случайных чисел на шаге 2;

0{N) проверок на шаге 3;

ЗМ операторов присваивания на шаге 3;

0{N) сложений на шаге 4.

Заметим также, что в качестве побочного продукта алгоритм SELECT дает случайную перестановку чисел 1, .... Л, что еще увеличивает его полезность.

Генераторы случайных чисел

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

Случайная переменная X является непрерывной, если существует неотрицательная функция f{x), определенная на всей вещественной прямой и обладающая тем свойством, что если S - произвольное множество вещественных чисел, то

P{XeS)=lfix)dx.

Функция fix) называется плотностыо распределения вероятности X.

В частности, если S - вся вещественная прямая, то, поскольку X обязательно принимает некое значение,

1 = Р(Х€(-оо, оо))= ] f{x)dx.

~ со

Аналогично, если S - некоторый интервал [а, Ь] на вещественной прямой, то

P{aXb) = lf(x)dx.

Непрерывньш аналогом дискретной переменной с равновероятным распределением является равномерно распределенная переменная. Если X - случайная переменная, принимающая с одинаковой вероятностью любое значение в интервале [О, 1], ее плотность вероятности равна

/1, 0<х<1;

остальных случаях.

) Напоминаем, случайная переменная является функцией.

Тогда, например,

Е[Х]=] xf{x)dx; var[X]= I {x-E[X]ff{x)dx.

Для равномерно распределенной переменной U в [0,1] получим

о~ 2

[t/]= J xf{x)dx = xdx = var[t/]= J {x-E[X]mx)dx=[x-ydx = .

-oo 0

Еще одно важное непрерывное распределение - это нормальное распределение. Плотность вероятности для случайной переменной X, обладающей нормальным распределением с параметрами [л и о.

) Иногда для обозначения этого распределения мы будем пользоваться символом и (О, 1).

P(l/4<X<3/4)= 5 Ыл;=3/4-1/4=1/2;

Р(Х=1/2)= J Ыл;= 1/2-1/2 = 0.

Последний результат особенно важен. Вероятность того, что непрерывная случайная переменная окажется равной некоторому частному значению из своего интервала, всегда равна О, а не /(X). Невозможно поставить в соответствие конечную вероятность каждому из бесконечного множества значений, так как «сумма» всех этих вероятностей окажется бесконечной (а не единицей). Не забывайте об этом. Равномерное распределение на интервале [0,1]i)-или (0,1); имеет ли это какое-нибудь значение? - по существу является именно тем распределением, которое моделируют программные генераторы случайных чисел. То есть случайное число, генерируемое компьютером, по существу представляет собой выборку из равномерно распределенной переменной.

Математическое ожидание и дисперсия непрерывной случайной переменной определяются аналогично соответствующим величинам для дискретной случайной переменной, за исключением того, что суммы заменяются на интегралы. Таким образом.