Генератор марковской последовательности случайных чисел

(088,8) аявки М присоединением 3) Приоритет Опубликован 5.05.80, Бкт летень .% 1 я 28.05.80 Дата опубликования описани Автор аобретен) ГЕНЕРАТОР МАРКОВСКОЙ ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЪХ ЧИСЕЛ ов йных чинако лучайныема-распределением. яет вырабатывать с сел с г оно поз амма-распределением то го параметра. Для гамма й .с неполуцелым параме т являться лишь приближ исла коасполуцелопределенионо мож ением,бли тбрать в качестве парам к нужному значению па лое число.(2 во делам изобретений и открытийИзобретение относится к вычислительной технике и может найти применение при моделировании случайных процесс и .статистических испытаниях.Известен метод генерирования случайныхчисел с гамма-распределением при дробном значении параметров 13Однако этот метод позволяет получат только некоррелированные числа. Наиболее близким техническим решением к данному изобретению является генератор марковской последовательности случайных чисел, содержаший счетчик, выход Которого подключен к первому входу блока сравнения, а вход счетчика подключен к выходу генератора тактовых импульсов и ко входу генератора нормально распределенных случайных чисел, выход которого подключен к первому входу первого умножнтеля, второй вход которого соединен с первым выходом первого датчика чисел, второй выход которого соедине с первым входом второго умножителя, второй вход которого через первый элемент задержки и блок памяти подключен ко входу квадратора и к выходу сумматора, первый и второй входы которого соединены с выходами первого и второго умножителей соответственно, второй датчик чисел, выход которого соединен с первым входом третьего умножителя, выход которого является выходом генератора, а второй вход третьего умножителя соединен с выходом интегратора, третий датчик чисел 21,Это устройство вырабатывает марковскую последовательность случаЗО 35 тп 45 зо 3736Цель изобретения - повышение точности выработки марковских последовательностей случайных чисел с любымзначением параметра.Пля достижения поставленной целигенератор содержит блок вычисленияцелой части числа, блок вычисления дробной части числа, управляемый перехтцочатель, второй элемент задержки и четвертый умножитель, первыи вход которого через блок вычисления дробной частичисла подключен к выходу третьего датчика чисел и ко входу блока вычисленияцелой чести числа, выход которого соединен со вторым входом блоке сравне-.ния, выход которого подключен к первому входу управляемого переключателяи. через второй элемент задержки - кпервому входу интегратора, второй Входкоторого соединен с первым выходомуправляемого переключателя и с выходомчетвертого умножителя, второй входкоторого соединен со вторым выходомуправляемого перехлючателя, второй входкоторого соединен с выходом кведратора,На чертеже приведене блок-схема генератора,Генератор содержит генератортактовых импульоов, генератор 2 нормальнораспределенных случайных чисел, счетчик 3, первый умножитель 4 сумматор5, квадретор 6, блок 7 памяти, первыйэлемент 8 задержки второй умножитель9, первый датчик 10 чиселинтегратор11, третий умножитель 12, выход 13,второй датчик 14 чисел, третийетчих 15чисел, блок 16 сравнения, управ;тнемый1переключатель 17, четвертый умножи тель 18, второй элемент 19 зедеГхцсд,блок 20 вьгчитсления целой части числаблок 21 вычисления дробной части чис.,ГенеретОр 1 тактовых иапульсов сое - динен с генератором 2 нормально ряс- прострененньЖ случайных чисел и со счетчиком 3, К Выходу генераторе 2 цодхлючены последовательно соединенные первый умножитель 4, сумматор 5 и кведратор 6. Выход умметора 5 соединенные последовательно блох 7 памяти и элемент 8 задержки ло,к:цочен к второму входу второго ум цртт и Реля 9 выход которого соединен со вторым входом сумматора 5. К другим входам умножителей 4 и 9 подключены соответствутощие выходы первого датчике 10 чисел, Выход квадраторе 6 соединен с входом упревляемога переключателя 17д 4первый выход которого соединен с втор.м ВхОдОм интегратора 1 1, ВыхОд которого через третий умножитель 12 подкпючен х Выходной клемме 13 всегоУстройства, К другому входу умножителя12 подсоединен выход второго детчиха 14чисел. Выход третьего датчика 15чисел соединен со входами блока 20выпи,.ления целой части и блока 21 вычисления дробной части. Выход блок 20соединен с одним входом блоха 16 срэвчения, с другим входом которого соединен выход счетчика 3, е с выходам -Вход второго элемента 19 задержки и . управляющий вход переключателя 17.Второй выход переключателя 17 соединенс одним из входов четвертого умножитатя 18, с другим входом которого соединен выход блока 21 вьчисления дробной 20 части. Выход второго элемента 19 задержки соединен с первым входоминтегратора 11, второй вход которогосоединен с выходом четвертого умножи-.дОля 18,Устройство работает следующим об -ДЕЗОМ,Генератор 1 тактовых импульсов,управляющий генератором 2 нормальнозаснределенных случайных чисел и счетчиком 3, а тэеоке последовательно соединенные квадратор 6, интегратор 11и третий умножитель 12 необходимы длягенерирования последовательности случайных чисел с одномерным гамме-распределением полупелого нереметра. Генератор 2 тьормирует нормально распределенные независимые случайные числа снулевым среууим жячением и единичнойдисперсией,. Получение требуемого одномерного ряспределенйя вероятности осттовено ,а, тот,т Обстоятелутве чтоузап 1 аквадратов неисимых нормальных случайных чисел, распределенных одинаковос н-левым средним знеч 8 нием, имеетгамме-аспоелеление полэаелого парамет -ра. Последова"-"чьнась слъ ейных чиселпР.ОбРе т Яет. Овойсво МЯРковостти бе 1 щ Оамару уотд-.т ь - то ВОЗВЭтМОЕ и КВадреткведразром 6 нормальное слу ейноеЧИСЛО Об-:ЯЗуотзя СЛОЖЕНИЕМ, В СуММаторе 5 генерируемого в генераторе 2 накаждом его такте новогО незяВиснмогО нормального числе, умноженного в первом умножителе 4 не положительноечисломеьц шее единицы, и сформированного на предыдущем шаге нормальногочисла с вь 6 ода сумматора 5, хранимого15 Если параметр распределения - полу- целое число, то последовательность случайных чисел, снимаемых с клеммы 13, имеет в качестве одномерного распределения гамма - распределение, потому что этн числа образуются как сумма квадратов нормальных случайных чисел, количество которых определяется целым числом с выхода блока 20. Если параметр распределения - неполупелое число,в блоке 7 памяти, задержанного элементом 8 задержки на один шаг и умноженного во втором умножителе 9 на поло-.жительное число, меньшее единицы. Положительные числа, меньшие единицы поступают на входы умножителей 4 и 9 с выхода первого датчика 10 чисел. Для того, чтобы изменение степени корреляционной связи в последовательности не изменяло масштаб генерируемых чисел с гамма-распределением, сумма квадратов чисел на выходах датчика 10 поддерживается постоянной. Вторым датчиком 14 чисел, поступаюших на вход третьего умножителя, осушествлявтся изменение масштаба генерируемых чисел.В третьем датчике 15 устанавливается число, равное удвоенному значению параметра гамма-распределения. В обшем случае параметр распределения не яв 20 ляется полуцелым числом, поэтому число на выходе датчика 15 не является целым числом. Из этого нецелого числав блоках 20 и 21 извлекается его це 25 лая и дробная часть. Белое число с блока 20 поступает на блок 16 сравнения, который вырабатывает импульс, когда состояние счетчика 3 совпадает с целым числом с выхода блока 20, Этот импульсзо переключает на один такт управляемый переключатель 17, так что следуюшее возведенное в квадрат нормальное случайное число поступает на второй вход интегратора 11 не прямо с выхода квадратора 6, а через четвертый умножительЗ 5 18) гдв квадрат нормального числа умножается на число, поступаюшее с выхода блока 21. Импульс с выхода блока 16 сравнения задерживается на один такт вторым элементом 19 задержки, который, поступая на первый вход интегратора 11, прекрашает суммирование квадраторов нормальных случайных чисел, после чего начинается формирование следуюшего числа в последовательности случайных чисел с гамма-распределением. Последовательность чисел снимается с клеммы 13. то последовательность случайных чисел,снимаемых с клеммы 13, не имеет гаммараспределения, потому, что квадраты нормальных случайных чисел, количествокоторых на одно больше числа с выходаблока 20, имеют неодинаковые коэффициенты. Это обусловлено умножениемпоследнего квадрата в сумме на числомежду 0 и 1 в четвертом умножителе 18.Однако первые начальные моменты, тоесть средние, случайных чисел с гаммараспредвлением требуемого параметра. ислучайных чисел, вырабатываемых предложенным устройством, совпадают,Если пользоваться гамма-распределением с полуцелым параметром для приближения гамма-распределения с неполуцелым параметром, то максимальнаяошибка в среднем значении наблюдаетсяв случав, когда значение параметра лежит как раз в середине между двумясоседними полуцелыми числами. Относительная ошибка в среднем значении составляет тогда 0,250, где й - значение параметра. Предложенное устройствопозволяет исключить ошибку приближенияв среднем значении.Вторыв начальные моменты случайныхчисел с гамма-распределением и случайных чисел, вырабатываемых предложенным устройством, не совпадают, когда параметр не является полуцелым.Если пользоваться гамма-распределениемс полуцелым параметром для приближения гамма-распределения с неполуцелымпараметром, то максимальная относительная ошибка во втором начальноммоменте составляет (8 а + 7)( 16 а+ 24 а+ 5), Если пользоватьсяпредложенным устройством, то максимальная относительная ошчбка приближения составляет 2(16 а - 24 а+ 5 ) . т.в.ошибка уменьшилась в (4 а+ 3,5) раза.Кроме того, при больших а ошибкауменьшается в первом случае обратнопропорционально О во втором случаеобратно пропорционально Ю.Добавление последнего квадрата нормального случайного числа в сумму сотличным от предыдуших квадратов весомнв изменяет коэффициента корреляциимежду соседними числами в последовательности случайных чисел, который попрежнему равняется квадрату числа свыхода датчика 10, поступаюшего навторой умножитель 9.Таким образом, данный генераторпозволяет повышать точность выработкимарковской последовательности случайных чисел с дробньм значением а)а- метра.Устройство сохраняет достоинства генератора марковской последователыости случайных чисел с гамма-распределением полуцелого параметра, зак)почающиеся в возможности независимого регулирования трех характеристик таКой последовательности, а именно корреляпоного коэффициента между соседними числами Б последовательности, масштаба чисел и формы кривой плотности вероятности, при помощи трех датчиков 10, 14 15, В частности, некоррелированная последо-. ватеЛьность случайных чисел с гамма- распределением дробного параметра получается, когда на первый вход второго умножителя О с первого датчика 1 С) поступает число О., При помощи данного устройства можно генерировать как случайные, так и псевдослучайные последсВательности В зависимости от того яВ-.ляетсяли генератор с ГенератОром слу чайных нормальных чисел или генерато=25 ром псевдослучайньх нормалъньх чисел.Таким Образом, Генератор Обладает новыми и более широкими вазможностя)и по сравнению с существующими и позВоляет решать бОлее сложные задачи из области цифрового моделирования и статистических испьтаний.Формула изОбретенияГенератор марковской последовательности случайных чисел, содержыций СЧЕТЧИК, ВЫХОД КОТОРОГО ПОДКЛЮЧЕН К первому входу блока сравнения, а вход счетчика подклочен к Вьходь генер ат.ра ТВКТОВЫХ ИМПУЛЬСОВ И КО БХОДу "енератОра нормальнО распределснньх сл- чайных чисел,. вьход которого попки)счен к первому входу первого уможителя, второй вход которого соединен " первым БыхОдОм первого датчика чисел, Второй выход которого соединен с первым Входом второго умнсжителя, Второй Бьход которого соединен с первым Входом второго умножителя, Второй вход которого через первый элемент задержки и блок памяти подключен ко входу квадратОра и к выходу сумматора, первый и второй входы которого соединены с выходами первого и второго умножителей соответственно, Второй датчик чис:.: выход которого соединен с первьгм Входом ",ретьего умножителя, Выход которого является выходом генератора, а втор)й БхОд третьео умеожь.еля соединен с выходом инт:;: - : ратора, третий датчик чисел, о т л и :. а ю щ и й с я тем,что, с цельО повьпцения точности генератора, он содержит блок вычисления целой части числа, бло:;, вычисления др"= ной части числа, управляемый перекчатель, Второй элемент задержки и четвертый умножитель, первый Вход котороа через блок вычисления дробной части числа подкцочен к выходу третьеГо датчка чиси и ко ВхОду бп)ка Вычисления целой части числа; ,ыхоц ко- торОГО сОединен СО вторым Блодом Оло - ка сравнения, выход которого подключен к первому ВхОду управляемоГО переклк)- чателя и через второй элемент задержю к ервому входу интегратс,р-.), Второй вхОд которОГО соедиен с ервм Выходом управляемого переключателя и с выходом четвертого умножителя, Второй вход ко торого сОединен со БТОр ым Выходом управляемого переключателя, второй вход которого соединен с выходом квадратОра.Источники информацп,прннятыв во Внимание при экспертизе1. З, ), серия "Е)ьгчислительаятехнипа", 1975, Ио 17, с. 1-7.2 Авторское свидетельство СССРю заявке % 21 7 2 0331 1 Я - 2 4,кл.:. С 7 С5/):, 197";. прототс7361 47 Составитель А. Карасовахтар В. Зарванская Техред О. Легем Корректор М. Шарощи ж 6 арственн делам изоб осква, Жлиал ППП "Патент", г. Ужгород, ул, Проектная, 4 акаэ 2281/9 ТПНИИПИ Госпо113035 М Подписноего комитета СССРретений и открытий5, Раушская наб., д. 4