Генератор марковской последовательности случайных чисел
Иллюстрации
Реферат
«»736347
Д (61) Дополнительное к авт. свид-ву (22) Заявлено 12.09.77 (2i) 2524666/18 24 (51)M. Кл, С 07 С 15/00
С 06 G 7/52 с присоединением заявки ¹
Государственный комитет
{23) Приоритет пс делен изобретений и етирытий (53) УДК 681.325 (088.8) Опубликовано 25.05.80. Бюллетень ¹ 19
Дата опубликования описания 28.05.80 (72) Автор изобретения
А. А. Коорт (71) Заявитель (54) ГЕНЕРАТОР МАРКОВСКОЙ ПОСЛЕДОВАТЕЛЬНОСТИ
СЛУЧАЙНЫХ ЧИСЕЛ
Изобретение относится к вычислительной технике и может найти применение при моделировании случайных процессов и .статистических испытаниях.
Известен метод генерирования случайных чисел с гамма-распределением при дробном значении параметров (13.
Однако этот метод позволяет получать только некоррелированные числа. о
Наиболее близким техническим решением к данному изобретению является генератор марковской последовательности случайных чисел, содержаший счетчик, выход Которого подключен к первому
15 входу блока сравнения, а вход счетчика подключен к выходу генератора тактовых импульсов и ко входу генератора нормально распределенных случайных чисел, выход которого подтслючен к первому входу первого умножнтеля, второй вход которого соединен с первым выходом первого датчика чисел, второй выход которого соединеп с первым входом вто2 рого умножителя, второй вход которого через первый элемент задержки и блок памяти подключен ко входу квадратора и к выходу сумматора, первый и второй входы которого соединены с выходами первого и второго умножителей соответственно, второй датчик чисел, выход которого соединен с первым входом третьего умножителя, выход которого является выходом генератора, а второй вход третьего умножителя соединен с выходом интегратора, третий датчик чисел (2).
Это устройство вырабатывает марковскую последовательность случайных чисел с гамма-распределением. Однако оно позволяет вырабатывать случайные числа с гамма-распределением только полуцелого параметра. Для гамма-распределений .с неполуцелым параметром оно может являться лишь приближением, если выбрать в качестве параметра ближайшее к нужному значению параметра полуцелое число. о
4"
/$ за.
736
Цель изобретения — повышение точности выработки марковских последовательностей случайных чисел с любым значением параметра.
Для достижения поставленной цели генератор содержит блок вычисления целой части числа, блок вычислегп-я дробной части числа, управляемый перехлгочатель, второй элемент задержки и четвертый умножитель, первыи вход которого через блок вычисления дробной части числа подключен к выходу третьего датчика чисел и ко входу блока вычисления целой чести числа, выход которого сае-динен со вторым входом блока сравпе-ния, выход которого подключен к первому входу управляемого перектпочателя и. через второй элемент задержки — к первому входу интегратора, второй вход которого соединен с первым выходом управляемого переключателя и с выходом четвертого умножителя, второй вход которого соединен со вторым выходом управляемого перехлючателя, второй вход которого соединен с вьгходом квадратора, На чертеже приведена блок-схема ге-. нератора.
Генератор содержит генератор тактовых импульоов, генератор 2 норм,чьно распределенных случайных чисел, счетчик 3, первый умножитель 4-„сумматор
5, кведретор 6, блок 7 памяти, и;ервый элемент 8 задержки., второй умножитель
9, первый датчик 10 чисел„интч-ратор
11, третий умножитель 12, выход 13, второй датчик 14 чисел, третий,атчих 15 чисел, блок 16 сравнения, управляемый
1 переключатель 17, четвертый умножи.-тель 18, второй элемент19, зедеГх." :и ° блок 20 вьгчнсления целой части иола блок 21 вычисления дробной части чис =.
Генератор 1 тактовых югпулсов ="ee— динен с генератором 2 нормально распространенньЖ случайных чисел ги со счетчиком 3. Х выходу генератора 2 подключены последовательно соединенные первый умножитель 4, сумматор 5 и кведратор 6. Выход умматора 5 ч раз соединенные последовательно блох 7 памяти и элемент 8 задержки IIG„-:ггочен к второму входу второго умножитсля 9, выход которого соединен со вторьп: входом сумматора 5. K другим входам умножителей 4 и 9 подключены соответствуюцгие выходы первого датчика 10 чисел. Выход квадратора 6 соед)п ен с входом управляемого перехтычателя 17,, д (4 первый выход которого соединен с втор. м входом интегратора 11, выход которого через третий умножитель 12 подкнючен х выходной клемме 13 всего устройства, К другому входу умножителя
3 2 подсоединен выход второго датчиха 14 чисел Выход третьего датчика 15 чисел соединен со входами блока 20 вьнп :.".пения целой части и блока 21 вычисления дробной части. Выход блоке 20 соединен с одним входом блоха 16 сравнения, с другим входом которого соединен выход счетчика 3, е с выходом— вход второго элемента 19 задержки и управляющий вход переключателя 17.
Второй выход переключателя 17 соединен одним и з входов ч етв ед того умно жя-;-ms> 3 8, с другим входом которого соединен выход блока 2.1 вьгчисления дробной е части. Выход второго элемента 19 задержки "îåäèíåí с первым входом инте=ратора 11, второй вход которого соединен с выходом четвертого умножи-.
18.
Устройство работает следующим об—
Д сФ лом
Генерегор 1 тактовых импульсов, управляющий генератором 2 нормально засцределенных случайных чисел и счетчиком 3, а таагже последовательно соединенные квадратор 6, интегратор 11 ; третий умножитесь, 12 необходимы для генерирования последовательности случайных чисел = одномерным гамме-распределением попупелого нереметра. Генератор 2 формирует нормально распределенные независимые случайные числа с нулевым среууим жачением и единичной дисперсией,. Получение требуемого одномерного,-аспределенйя вероятности ос тован - :е уо,г Обстоятелу тве что су п га квадпатов не исимых нормальных случайных чисел, распределенных одинаково зне ен" ем Ф спЛМЯ!-РаСПОЕ %ЭЛЕНИЕ ПОЛ ДЕЛС ГО ПЕРаМЕт— ра. !:-Оследова."-" чьнос. .ь сл чайных чисел .триобретает свойство марковости 6;1GFoу аря ;ом-,; = о возу, гимое в квадрат кввдратором 6 нормальное случайное число об-:азуе "я сх ожением, s. сумматоре 5 генерируемого в генераторе 2 на хажцОм его такте новОгО незевиснмогО нормального числе, умноженного в nep ì умножителе 4 иа положительное число„меьпшее едигцгцы, и сфгрмированного на предьгдущем шаге нормального
"-ясла с выхода сумматора 5, хрантлого
736147 в блоке 7 памяти, задержанного элементом 8 задержки на один шаг и умноженного во втором умножителе 9 на поло-. жительное число, меньшее единицы. Положительные числа, меньшие единицы> поступают на входы умножителей 4 и 9 с выхода первого датчика 10 чисел. Для того, чтобы изменение степени корреляционной связи в последовательности не изменяло масштаб генерируемых чисел с гамма-распределением, сумма квадратов чисел на выходах датчика 10 поддерживается постоянной. Вторым датчиком 14 чисел, поступаюших на вход третьего умножителя, осушествляется изменение масштаба генерируемых чисел.
В третьем датчике 15 устанавливается число, равное удвоенному значению параметра гамма-распределения. В обшем случае параметр распределения не яв20 ляется полуцелым числом, поэтому число на выходе датчика 15 не является целым числом. Из этого нецелого числа в блоках 20 и 21 извлекается его це25 лая и дробная часть. Белое число с блока 20 поступает на блок 16 сравнения, который вырабатывает импульс, когда состояние счетчика 3 совпадает с целым числом с выхода блока 20. Этот импульс
30 переключает на один такт управляемый переключатель 17, так что следуюшее возведенное в квадрат нормальное случайное число поступает на второй вход интегратора 11 не прямо с выхода квадратора 6, а через четвертый умножитель
18) где квадрат нормального числа умножается на число, поступаюшее с выхода блока 21. Импульс с выхода блока 16 сравнения задерживается на один такт вторым элементом 19 задержки, который, поступая на первый вход интегратора 11, прекрашает суммирование квадряторов нормальных случайных чисел, после чего начинается формирование следуюшего числа в последовательности случайных чисел с гамма-распределением. Последовательность чисел снимается с клеммы 13.
Если параметр распределения — полуцелое число, то последовательность случайных чисел, снимаемых с клеммы 13, имеет в качестве одномерного распределения гамма — распределение, потому что этн числа образу отся как сумма квадратов нормальных случайных чисел, количество которых определяется целым числом с выхода блока 20. Если параметр распределения — неполуцелое число, то последовательность случайных чисел, снимаемых с клеммы 13, не имеет гаммараспределения, потому, что квадраты нормальных случайных чисел, количество которых на одно больше числа с выхода блока 20, имеют неодинаковые коэффициенты. Это обусловлено умножением последнего квадрата в сумме ня число между 0 и 1 в четвертом умножителе 18.
Однако первые начальные моменты, то есть средние, случайных чисел с гаммараспределением требуемого параметра. и случайных чисел, вырабатываемых предложенным устройством, совпадают.
Если пользоваться гамма-распределением с полуцелым параметром для приближения гамма-распределения с неполуцелым параметром, то максимальная ошибка в среднем значении наблюдается в случае, когда значение параметра лежит как раз в середине между двумя соседними полуцелыми числами. Относительная ошибка в среднем значении составляет тогда 0,25@, где R - значение параметра. Предложенное устройство позволяет исключить ошибку приближения в среднем значении.
Вторые начальные моменты случайных чисел с гамма-распределением и случайных чисел, вырабатываемых предложенным устройством, не совпадают, когда параметр не является полуцелым.
Если пользоваться гамма-распределением с полуцелым параметром для приближения гамма-распределения с неполуцелым параметром, то максимальная относительная ошибка во втором начальном моменте составляет (8 a + 7) (16a+ 24m+ 5) . Если пользоваться предложенным устройством, то максимальная относительная ошчбка приближения составляет 2(16я-24 + 5 ) . т.е. ошибка уменьшилась в (4m+ 3,5) раза.
Кроме того, при больших с ошибка уменьшается в первом случае обратно пропорционально a, во втором случае обратно пропорционально Q. .
Добавление последнего квадрата нормального случайного числя в сумму с отличным от предыдуших квадратов весом не изменяет коэффициента корреляции между соседними числами в последовательности случайных чисел, который попрежнему равняется квадрату числа с выхода датчика 10, поступаюшего на второй умножитель 9.
Таким образом, данный генератор позволяет повышать точность выработки марковской последовательности случайных чисел с дробным знячением Нараметра.
Устройство сохраняет достоинс IBa генератора марковской последоватепытости. случайных чисел с гамма-распределением полуцелого параметра, зякгпочяющиеся в
Возможности независимого регулирования трех характеристик такой последовательности, а именно корреляционного коэффициента между соседними числами в .последовательности, масштаба чисел и фОрм ы криво Й плотнОсти Веро я тнос ти, при помощи трех датчиков 20, 14,, 15.
В частности, некоррелировянная последо- вательность случайных чисел с гаммараспределением дробного параметра получается, когда на первый вход вто= рого умножителя О с первого датчика 16 поступает число О., При помощи данного устройства можно генерировать как случайные, так и псевдослучайные последоВательности В зявисимОсти От того, яВ= ляется. Ли генератор 2 генератором случайных нормальных чисел или генерате=
Я ром псевдослучайных НОрмальных чисел.
Таким образом, генератор абладв=т новыми и более широкими возможностями по сравнению с существующими и позВоляет решять бОлее сложные зядя чи из области цифрового моделирования и с-.-атистических испытаний.
Ф О р м g л а H з О б р е T е и и я
Генератор марковской последовательности случайных чисел, содержыций счетчик, ВыхОЦ КОТОрОРО подкжОчен K первому входу блока сравнения, а <-хот счетчика подклточен к выход ч герер а 1 ра ТЯКТОВЫХ ИМПУЛЬСОВ И KG БХОДу т" е— нератОря нормальнО распределенных случайных чисел,. Выход которого подк,шс= чен к первому входу первого умноыт ..еIIH, второй вход которого соединен " первым БыхОдОМ перБОГО датчика чисел, второй выход которого соединен с первым входом второго умнсжителя, второй выход которого соединен с первым Входом второго умножителя, Второй вход которого через первый элемент задержки и блок памяти подключен КО ВХОду квадраTQpa u K выхОду сумматора, первый и второй входы которого соединены с выхОдями первОго и Б ."Орого умножителей соответственно) второй дятчкк чис :-л, выход которого соединен с первьгм входом
",ретьего умножителя, Выход которо.-"з является выходом генератора, я Втор и вход третьего умнож ;.еля "..îåäèíåí с выходом инт:;ъ ратора, третий датчик чисел, о т I H -:. я ю шийся тем, что, с цельк> повьпцения точности генератора, он содержит блок вычисления целой чести числа, бло:;; вычисления ар= ."=ной Hac r-и числа, управляемый переключатель, ВТОрой элемент задержки и четвертый умножи*тель, первый Вход которого через блОк Вычисления дробной части числа подктцочен к выходу третье. О iс1ТЧХГКЯ ЧИСЕЛ И EQ ВХОДУ с :П.:.КЯ BbIчисления целОЙ части числа; .ыхО ц KQ—
TopQFQ СО единен со в тор ым Б.;одом блока сравнения, выход которого подключен к первому входу управляемого переключателя и через второй элемент задержтс. к рервому входу интегратор:., Второй
БхОд кОТОрОРО соединен с перВМ ВыходОМ управляемого переключателя и с выходом четвертого умножнтеля, второй вход которого соединен сс вторым выходом управляемого переключателя, второй вход которого соединен с выходом IcaagpaTGpa °
Источники информяшп, прннятыв во внимание при экспертизе
1. З. К, серия "Вьгчислительняя техника, 1975, Ио 17, с. 1-7.
2,: ABTQpcêoe свидетельство СССР по заявке ¹ 2172938/ 18-24, С7 С 5/ 9, 1*3 6;H7iD QT!. .I) 7361 47
Составитель А. Карасов
Редактор В. Зарванская Техред О. Легеэа Корректор М. Шароши
Лакаэ 2281/9 Тираж 641 Подписное
Ш ИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4