27,28. Свойство конгруэнтности (сравнимости) целочисленных величин и его использование в генераторах бсв

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

Свойства конгруэнтности:

1) А и В целые числа;

2) интервал между числами А и В д.б. равен целому числу умноженному на m;

3) остатки от деления А и В на модуль m д.б. одинаковы.

Формально:

a,b,m – целые числа

│a-b│ =k*m, где k – целое.

]a/m[=]b/m[

Если 1, 2, 3 выполн., то a=b(mod m) {т.е. сравнимы по модулю}.

При формировании БСВ конгруэнтными процедурами, на роль очередных xi+1 и текущих xi выбираются конгруэнтные: xi+1=xi(mod m).

Конгруэнтные процедуры являются чисто детерминированными, т.к. описываются виде рекуррентного соотношения, когда функция xi+1=Ф(xi) имеет вид xi+1≡αxi +β (mod m)

xi= [αix0 + β (αi-1) /(α-1)](mod m).

Если задано начальное значение x0, множитель α и аддитивная константа β, то данная формула однозначно определяет послед-ть целых чисел {xi}.

29. Мультипликативная и мультипликативно-аддитивная процедура генерации бсв.

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

Мультипликативный метод задает послед-ть неотр. целых чисел {xi}, не превосходящих m, по формуле xi+1≡λxi(mod m). Получаются воспроизводимые последовательности. Требуемый объем памяти минимален, необходим последовательный подсчет произв-я двух целых чисел, т.е. вып-я операции, быстро реализуемой на ЭВМ. Для машинной реализации наиболее удобна версия m=p^g, где p – число цифр в системе счисления, принятой в ЭВМ, g – число бит в машинном слове. Тогда вычисление остатка от деления на m сводится к выделению g младших разрядов делимого, а преобразования целого числа xi в рациональную дробь из интервала (0,1) осуществляется подстановкой слева двоичной или десятичной запятой.

Пример:для g=4, получить числа последовательности, используя алгоритм мультипликативного метода.

выбираем x0=7(10)=0111(2)

при t=1 получим λ=11(10) или 5(10) (λ=8t±3), пусть λ=5(10)=0101(2)

рассчит. произв-е λx0, берем g мл. р-дов, вычисляем x1 и присваиваем x0=x1

λx0=(0101)(0111)=00100011, x1=0011, x1=3/16=0,1875

λx1=(0101)(0011)=00001111, x2=1111, x2=15/16=0,9375 и т.д.

Мультипликативно-аддитивный м-д (смешанный) позв. вычислять послед-ть по формуле xi+1≡λxi +β (mod m), т.е. в отличие от мультиплик-ного м-да β≠0. Этот метод сложнее мультиплик-ного на одну операцию «+», но возможность выбора доп. параметра позволяет уменьшить корреляцию получаемых чисел.

30. Проверка бсв; плотность распределения и математическое ожидание равномерного распределения.

Эффективность статистического моделирования систем и достоверность получаемых результатов существенно зависит от БСВ. Проверка равномерности БСВ осуществляется следующим образом: Выдвигается гипотеза о равномерности распределения чисел в интервале (0,1). Затем интервал (0,1) разбивают на m равных частей, тогда при генерации последовательности {xi} каждое из чисел xi с вероятностью pj=1/m, j=1…m попадает в один из подинтервалов. Всего в каждый j-й интервал попадет Nj чисел. Относительная частота попадания случайных чисел в каждый подинтервал равна Nj/N. По виду полученной гистограммы и теоретической прямой можно судить о равномерности распределения БСВ.

Плотность распределения – такая функция p(x)≥0, что вероятность неравенства a<x<b при любых a и b равна ∫ab p(x)dx, при этом функция p(x) должна удовлетворять условию ∫p(x)dx=1.

Математическое ожидание – среднее значение, одна из важнейших характеристик распределения вероятностей с.в.

Плотность распределения равномерно распределенной с.в. на инт. (a,b) — это прямая f=1/(b-a). Мат. ожидание такой величины mx = (a+b)/2

(первый график слева – плотность распределения fx(x), справа – функция распределенияF(x))

31. Проверка законов распределения ПСВ; критерий Колмогорова.

Пусть имеется теор. закон распределения с.в. Имеется некоторое мн-во статистических данных, которые подчиняются некоторому собственному закону распред-я. Фактические данные могут отличаться от теории в связи с тем, что:

а) теор. кривая не соотв. фактическому распределению, т.е. гипотеза не верна;

б) случайные факторы.

При условии, что гипотеза выбрана правильно, мы должны убедиться, что отклонения полученной кривой от теор. связаны со случ. факторами. Для этого определяем вероятность того, что зафиксированное случайное расхождение не больше допустимого и объясняется случ. факторами.

Для опред-я расхождения теор. кривой с практической разбиваем весь диапазон на интервалы, при этом чем больше выборка тем точнее. Подсчитываем число попаданий в каждый интервал Ni, и статистическую вероятность Ni/N. Сама мера или степень расхождения является с.в. и подчинена своему з-ну распред-я, зависящему от вида теор. кривой и случайных факторов.

мера расхождения определяется гораздо проще: определяется max величина расхождения между теор. и фактическим значением ф-ции распределения. Т.о., сравниваются ф-ции распределения, а не плотности.

D = max |F*(x) – F(x)|

При n ∞

1) находим D

2)

3) по таблице определяем P(λ) – вероятность того, что возможные отклонения от Dmax будут не меньше установленного по случайным причинам.

Критерий Колмогорова также не гарантирует факт полного совпадения, а позволяет определять степень уверенности. Он пригоден только тогда, когда заранее известен з-н распределения. Если известен только вид ф-ции без параметров, крит. Колмогорова дает завышенную оценку.