Группирование членов ряда распределения

Отдельные члены ряда распределения объединяются в группы. Обозначим через Q_j суммарную вероятность всех вероятностей членов j‑ой группы.

Алгоритм использует другой метод поиска отрезка, на который попадает базовое число x:

сначала определяется номер группы, куда попало x. При этом сравнение идет с границами деления отрезка [0,1] на определенные выше группы, рассчитываемыми аналогично тому, как это делалось ранее, только в соответствии с вероятностями Q_j ;

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

Путем подбора групп можно дополнительно уменьшить среднее число производимых алгоритмом сравнений.

Метод группирования может применяться в дополнение к методу переупорядочения членов ряда распределения.

Рассмотрим пример:

Для следующего биномиального распределения с параметрами n=6 и p=1/2:

Р(Х=х) = С6^х ×(1/2) ^x× (1/2)^6–x, (х = 0, 1, 2, …,6). (1.3)

применим последовательно оба метода уменьшения среднего числа сравнений.

Исходный ряд распределения определяется таблицей1.2:

Таблица 1.2

В результате расчета среднего числа сравнений по этой таблице получаем m = 3,98.

Таблица 3.5 показывает действие обоих методов:

Таблица 3.5

Среднее число сравнений после переупорядочения mп = 2,52. После дополнительного группирования mп+г= 2,38.

Способ группирования членов ряда распределения эффективно применяется для повышения быстродействия точных алгоритмов моделирования дискретных случайных величин с бесконечным рядом распределения (например, распределения Пуассона, геометрического распределения). Дело в том, что заранее рассчитать вероятности всех значений таких случайных величин и соответствующие им границы деления отрезка [0,1] невозможно. Поэтому весь ряд делят как минимум на две группы. В первую (первые) группу включают члены ряда распределения, составляющие его основную часть (сумма вероятностей которых близка к единице). Так как бесконечные распределения характеризуются тем, что их вероятности с увеличением n после возможно некоторого увеличения вначале (например, при некоторых значениях параметра закона Пуассона) асимптотически стремятся к нулю, то в первые группы попадают, соответственно, первые члены исходного ряда. Вероятности отдельных членов ряда, включенных в эти группы, и соответствующие им границы деления отрезка [0,1], рассчитываются заранее, хранятся в таблице и используются в алгоритме при попадании базового числа в отрезок, соответствующий этим группам. И только при попадании базового числа вне этого отрезка становится необходимым последовательный расчет других вероятностей ряда до выполнения указанных ранее условий реализации конкретного значения случайной величины. За счет этого увеличивается быстродействие датчика. Если монотонность уменьшения вероятностей для первых членов ряда не выполняется, то для них дополнительно может быть применен метод переупорядочения.