zinet home
home home
home ИНТЕЛЛЕКТ-ПОРТАЛ
home Стартовал прием материалов в сборник XХХIX-й научной конференции. Требования к публикациям - в разделе "Объявления".

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

РЕСУРСЫ ПОРТАЛА:

Тридцать восьмая научно-практическая конференция
(23 - 28 мая 2016 г.)


Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)


Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)


Тридцать пятая научно-практическая конференция
(24-27 ноября 2015 г.)


Тридцать четвертая научно-практическая конференция
(13-17 октября 2015 г.)


Тридцать третья научно-практическая конференция
(20-27 мая 2015 г.)


Тридцать вторая научно-практическая конференция
(2-7 апреля 2015 г.)


Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)


Тридцатая научно-практическая конференция
(19-25 января 2015 г.)


Двадцать девятая международная научно-практическая конференция
(19-25 ноября 2014 г.)


Двадцать восьмая международная научно-практическая конференция
(08-13 октября 2014 г.)


Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)


Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)


Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)


Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)


Двадцать третья научно-практическая конференция
(10-15 декабя 2013 г.)


Двадцать вторая научно-практическая конференция
(4-9 ноябя 2013 г.)


Первая международная научно-практическая конференция
(14-18 мая 2013 г.)


Двадцать первая научно-практическая конференция
(14-18 мая 2013 г.)


Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)


Девятнадцатая научно-практическая конференция
(26 февряля - 3 марта 2013 г.)


Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)


Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)


Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)


Пятнадцатая научно-практическая конференция
(01 - 07 марта 2012 г.)


Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)


Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)


Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)


Одинадцатая научно-практическая конференция
(26 апреля - 04 мая 2011 г.)


Десятая научно-практическая конференция
(15-23 марта 2011 г.)


Девятая научно-практическая конференция
(27-31 декабря 2010 г.)


Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)


Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)


Шестая научно-практическая конференция
(1-15 апреля 2010 г.)


Пятая научно-практическая конференция
(20-27 мая 2009 г.)


Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)


Третья научно-практическая конференция
(20-27 декабря 2008 г.)


Вторая научно-практическая конференция
(1-7 ноября 2008 г.)


Первая научно-практическая конференция
(10-15 мая 2008 г.)



НАШИ ПАРТНЕРЫ:

Студия веб-дизайна www.zinet.info



Студия ландшафтного дизайна Флора-МК


Уникальное предложение!



Сайт-визитка - теперь
всего за 200 грн!

подробнее>>>



ПРИНЦИПЫ, МЕТОДЫ И СПОСОБЫ ПОСТРОЕНИЯ ГЕНЕРАТОРОВ СЛУЧАЙНЫХ ЧИСЕЛ

 

Шведова В.В., Заика Ю.В.

Украина, г. Киев

Национальный технический университет Украины

«Киевский политехнический институт»

 

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

 

Принципы и методы построения генераторов случайных чисел

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

Существует шесть основных направлений использования рандомизации:

·       отбор случайной выборки;

·       анализ выборочных данных;

·       разработка стандартов;

·       проверка теоретических результатов;

·       проверка того, что предложенная процедура соответствует заявленным свойствам;

·       принятие решений в условиях неопределенности.

Приведенные в статье методы и алгоритмы обладают большим периодом повторения и хорошо согласуются с генерируемым законом распределения [1]. При необходимости использования других алгоритмов генерации псевдослучайных чисел до их применения следует убедиться, что период последовательности псевдослучайных чисел является достаточным для решения задачи, а генерируемые псевдослучайные числа хорошо согласуются с моделируемым распределением.

Как показал анализ методов и способов генерации случайных последовательностей с разными законами распределения, большинство из них основываетстя на первоначальной генерации последовательности, которая имеет равномерное распределение. Для этой цели как правило используют метод М-последовательности, который состоит в следующем [1]:

1.     для натурального числа р и чисел  принимающих значения 0 или 1, определяют рекуррентную формулу:

.

2.     находят наименьшее положительное целое N, такое что  для всех значений  называют периодом последовательности. Эту последовательность называют М-последовательностью, период которой составляет .

3.     формируют полином

,

который является характеристическим полиномом для приведенной выше рекуррентной формулы.

Существуют такие методы, как Пятипараметрический метод, Комбинированый метод Таусворта, Метод Мерсена Твистера, которые являются модификациями метода М-последовательности, и имеют следующий вид:

Пятипараметрический метод

Данный метод использует характеристический полином 5 членов и позволяет генерировать последовательность w-битовых двоичных чисел в соответствии со следующей рекуррентной формулой. Такой алгоритм называют GFSR ли генератором случайных чисел «сдвиговый регистр с обратной связью».

Параметры  и X1, …, Xp первоначально задают как начальные числа.

Комбинированый метод Таусворта

При генерации случайных чисел методом Таусворта используют рекуррентную формулу

Где  – соответствующая М-последовательность.

При использовании такой М-последовательности последовательность w -битовых целых чисел, называемую простой последовательностью Таусворта с параметрами  получают по формуле

Где t – натуральное число взаимно простое с периодом  М-последовательности;

w – длина слова, не превышающая  бит

Если имеется несколько, например J простых последовательностей Таусворта  с одной и той же длиной слова w, комбинированный метод Таусворта генерирует последовательность псевдослучайных чисел  как результат побитовой операции «исключающее ИЛИ» при двоичном представлении чисел в этих J последовательностях.

Параметры и начальные числа комбинированной последовательности Таусворта представляют собой комбинацию параметров и начальных чисел каждой простой последовательности Таусворта. Если периоды J простых последовательностей Таусворта являются взаимно простыми, то период комбинированной последовательности Таусворта равен произведению периодов J последовательностей.

Метод Мерсена Твистера

Метод Мерсена Твистера позволяет генерировать последовательность двоичных псевдослучайных целых w-бытовых чисел в соответствии со следующей рекуррентной формулой

где  – целые константы;

 – двоичное w-битовое целое число (формирующее матрицу А);

 – w-битовое двоичное целое число;

– двоичное целое число, полученное конкатенацией чисел  и , когда первые (w-r) битов взяты из  а последние r битов из () в том же порядке;

 – матрица размера w×w, состоящая из нулей и единиц, определенная посредством а;

 – произведение, при вычислении которого сначала выполняют операцию , если последний бит  равен 0, а затем, когда последний бит , вычисляют .

(Здесь  также как и  представляет собой w-мерный вектор, состоящий из нулей и единиц.)

Генерация случайных последовательностей с заданными распределения на основе метода М-последовательности (имеющей равномерное распределение) осуществляется согласно следующим аналитическим выражения:

Равномерное распределение

а) стандартное равномерное распределение

Функция плотности вероятности

Метод генерации случайной величины: если максимальное значение равномерного случайного целого числа Х равно , для генерации стандартных равномерных случайных чисел необходимо применять следующую формулу:

б) общий случай равномерного распределения

Функция плотности вероятности

.

Метод генерации случайной величины: если стандартное равномерное случайное число U получено методом, установленным в 2.1.1.1, то равномерное случайно число должно быть получено в соответствии со следующей формулой

Стандартное бета-распределение

Функция плотности вероятности

,

где  – бета-функция с параметрами c и d(c > 0, d > 0).

Метод генерации случайной величины - метод Йонка:

Если стандартные равномерные случайные числа  и  независимо генерированы методом, установленным в 2.1.1, то соответствующее стандартному бета-распределению случайное число Y получают в соответствии со следующими процедурами.

Если  в противном случае генерируют два новых стандартных равномерных случайных числа до тех пор, пока неравенство не будет выполнено.

Метод генерации случайной величины - Метод Ченга

Если стандартные равномерные случайные числа  и  независимо получены методом, установленным в 2.1.1, то случайное число Y, соответствующее стандартному бета-распределению, получают в соответствии со следующей процедурой

а)

б) вычисляют

в) если

Тогда

d) В противном случае генерируют ,  и переходят к b.

Если , применяют метод Йонка, в противном случае применяют метод Ченга.

Треугольное распределение

Функция плотности вероятности

,

где .

Метод генерации случайной величины: если стандартные равномерные случайные числа , и независимо генерированы методом, установленным в 2.1.1, то случайное число Y, подчиняющееся треугольному распределению, определяют по формуле  .

Общее экспоненциальное распределение с параметрами положения и масштаба

Функция плотности вероятности

,

где  и  – параметры положения и масштаба экспоненциального распределения соответственно

Метод генерации случайной величины: если стандартное случайное число  генерировано методом, установленным в 2.1.1, то случайное число соответствующее экспоненциальному распределению, получают по формуле

Нормальное распределение (распределение Гаусса)

Функция плотности вероятности

где  и  – среднее и стандартное отклонение нормального распределения соответственно.

Метод генерации случайной величины - Метод Бокса-Мюллера

Если стандартные равномерные случайные числа , и  независимо генерированы методом, установленным в 2.1.1, то два независимых нормальных случайных числа ,  получают в соответствии со следующей процедурой

.

Гамма-распределение

Функция плотности вероятности

где  – параметры положения, масштаба и формы соответственно.

Распределение Вейбулла

Функция распределения вероятности

где  – параметры положения, масштаба и формы соответственно.

Метод генерации случайной величины: если стандартные равномерные случайные числа  генерированы методом, установленным в 2.1.1, то случайные числа, соответствующие распределению Вейбулла, получают по формуле

.

Логнормальное распределение

Функция плотности вероятности

где – параметры положения, масштаба соответствующего нормального распределения.

Метод генерации случайной величины: используя стандартные нормальные случайные числа применяют формулу

для получения случайных чисел соответствующих логнормальному распределению.

Логистическое распределение

Функция вероятности

где параметры положення и масштаба соответственно.

Метод генерации случайной величины: если стандартные равномерные случайные числа  генерированы методом, установленным ранее, то случайные числа, соответствующие логистическому распределению, получают по формуле

Многомерное нормальное распределение

Случайные числа ,, соответствующие n-мерному нормальному распределению со средними ,, дисперсиями и ковариациями  получают, используя взаимно независимые стандартные нормальные случайные числа ,

где – константы, вычисляемые до начала генерации в соответствии с процедурой факторизации Холецкого.

Биноминальное распределение

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

где

Распределение Пуассона

Функция распределения Пуассона со средним  имеет вид

, где .

Метод, использующий связь с экспоненциальным распределением: генерируют стандартные равномерные случайные числа , В качестве  используют максимальное значение , удовлетворяющее следующему неравенству

Метод генерации случайной величины: - метод наложения

Сначала выбирают постоянную , для которой вероятность того, что  пренебрежимо мала, например, целая часть числа  может быть установлена равной . Затем применяют процедуру Метод положения приведенную для биноминального распределения. Однако на сей раз для  должна быть использована функция распределения Пуассона

Дискретное равномерное распределение

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

Определяют натуральное число , удовлетворяющее следующему неравенству:

Добавляют 1 к двоичному целому числу, которое сформировано из первых  битов случайного числа, и конвертируют его в десятичное число

Искомое десятичное случайное число – это соответствующее десятичное число плюс  при отбрасывании чисел более

Далее, если  является десятичным  – значным натуральным числом  не является слишком большим, например  меньше 20, может быть использован метод, установленный в 1.1. При этом выполняют процедуру в соответствии с d) и e)

Генерируют последовательность десятичных случайных чисел из  цифр, использую процедуру 1.1.

Из последовательности случайных чисел, полученной в соответствии с d), удаляют числа более . Полученная таким образом последовательность является искомой последовательностью десятичных случайных чисел.

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

 

Рисунок 1 – Структуру взаимосвязи способов генерации случайных последовательностей с заданным законом распределения.

 

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

 

Литература

1.     ГОСТ Р ИСО 28640-2012 Статистические методы. Генерация случайных чисел

2.     Варакин Л. Е. Системы связи с шумоподобными сигналами. — М.: Радио и связь, 1985. — 384 с.



Первая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(10-15 мая 2008 г.)


(отчет)
Вторая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(1-7 ноября 2008 г.)
(отчет)
Третья научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(20-27 декабря 2008 г.)
(отчет)
Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)
(отчет)
Пятая научно-практическая конференция
(20-27 мая 2009 г.)
(отчет)
Шестая научно-практическая конференция
(1-15 апреля 2010 г.)
(отчет)
Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)
(отчет)
Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)
(отчет)
Девятая научно-практическая конференция
(27-31 декабря 2010 г.)
(отчет)
Десятая научно-практическая конференция
(15-23 марта 2011 г.)
(отчет)
Одинадцатая научно-практическая конференция
(26 апреля 04 мая 2011 г.)
(отчет)
Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)
(отчет)
Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)
(отчет)
Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)
(отчет)
Пятнадцатая научно-практическая конференция
(01-07 марта 2012 г.)
(отчет)
Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)
(отчет)
Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)
(отчет)
Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)
(отчет)
Девятнадцатая научно-практическая конференция
(26 февраля - 3 марта 2013 г.)
(отчет)
Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)
(отчет)
Двадцать первая научно-практическая конференция
(13-18 мая 2013 г.)
(отчет)
Первая международная научно-практическая конференция
"Перспективные направления отечественной науки - ХХI век"
(13-18 мая 2013 г.)
(отчет)
Двадцать вторая научно-практическая конференция
(4-9 ноября 2013 г.)
(отчет)
Двадцать третья научно-практическая конференция
(10-15 декабря 2013 г.)
(отчет)
Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)
(отчет)
Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)
(отчет)
Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)
(отчет)
Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)
(отчет)
Двадцать восьмая научно-практическая конференция
(08-13 октября 2014 г.)
(отчет)
Двадцать девятая научно-практическая конференция"
(19-25 ноября 2014 г.)
(отчет)
Тридцатая научно-практическая конференция
(19-25 января 2015 г.)
(отчет)
Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)
(отчет)
Тридцать вторая научно-практическая конференция
(2 - 7 апреля 2015 г.)
(отчет)
Тридцать третья научно-практическая конференция
(20 - 27 мая 2015 г.)
(отчет)
Тридцать четвертая научно-практическая конференция
(13 - 17 октября 2015 г.)
(отчет)
Тридцать пятая научно-практическая конференция
(24 - 27 ноября 2015 г.)
(отчет)
Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)
(отчет)
Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)
(отчет)
Тридцать восьмая научно-практическая конференция
(23 - 25 мая 2016 г.)
(отчет)

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

Copyright © Zinet.info. Разработка и поддержка сайта - Студия веб-дизайна Zinet.info