При реализации на ЭВМ статистического моделирования возникает задача получения (генерирования) на ЭВМ случайных числовых последовательностей с заданными вероятностными характеристиками, в которых каждое число – это имитация случайного значения какого-либо параметра реального процесса или системы, подверженного случайным возмущениям.
Генерирование на ЭВМ таких случайных числовых последовательностей получило название
В математической литературе часто используется термины "последовательность случайных чисел" или просто "случайные числа".
Однако, если проанализировать эти термины с философской точки зрения, то можно спросить: а есть ли такой объект как случайное число? Число 2 – это случайное число? Или число 17 – это случайное число? Конечно, нет. Если использовать точные термины, то можно говорить только о случайной последовательности чисел или о случайном значении параметров. Однако, в литературе широко используется термины "случайные числа" и "последовательность случайных чисел", и это означает, что каждое число было получено самым произвольным образом, без всякой связи с другими членами последовательности, и что у него есть определенная вероятность оказаться в заданном интервале.
Раньше ученые, нуждавшиеся для своей работы в случайных числах, раскладывали карты, бросали кости или вытаскивали шары из урны, которую предварительно как следует трясли. В 1927 году Л. Типпетт опубликовал таблицы, содержащие свыше 40 000 случайных чисел, взятых произвольно из отчетов по переписи. Позже были сконструированы специальные машины, механически вырабатывающие случайные числа. В 1955 году компания RAND Corporation опубликовала хорошо известные таблицы с миллионом случайных чисел, полученных одной из таких машин.
После создания ЭВМ начались поиски эффективных алгоритмов получения (генерирования на ЭВМ) последовательностей случайных чисел, пригодных для программной реализации.
Последовательности случайных чисел, вырабатываемые детерминистскими способами (т. е. с помощью специальных алгоритмов) называются псевдослучайными или квазислучайными. В дальнейшем мы будем их называть просто случайными последовательностями, понимая, что они просто производят впечатление случайных.
Задачу
Вначале получают последовательность равномерно распределенных на интервале [0, 1] псевдослучайных чисел.
Из равномерно распределенной последовательности получают последовательность псевдослучайных чисел с заданным законом распределения в заданном интервале.
Равномерным называется такое распределение, при котором каждое возможное случайное число равновероятно. Обычно, если специально не оговорен закон распределения случайных чисел, то имеют в виду равномерное распределение.
Сущность алгоритмических методов получения равномерно распределенных псевдослучайных чисел заключается в том, что xi+1 = f (xi),
где каждое следующее (i+1)-e значение образуется из предыдущего (или группы предыдущих) путем применения некоторого алгоритма, содержащего логические и арифметические операции.
Известно большое количество имитации равномерного распределения (методы вычетов, суммирования, усечения, перемешивания). Общими для всех этих методов являются требования:
Первым алгоритмический метод получения равномерно распределенных псевдослучайных чисел предложил Джон фон Нейман (один из основоположников кибернетики).
Суть метода: предыдущее случайное число возводится в квадрат, а затем из результата извлекаются средние цифры.
Например:
$$\text{пусть } x_0 =0.2061, \text{ тогда } x_0^2 =0.04\vert 2477\vert 21;\\ x_1 =0.2477, x_1^2 =0.06\vert 1355\vert 29;\\ x_2 =0.1355, x_2^2 =0.01\vert 8360\vert 25$$и т.д.
Как видно
Свойство "зацикливаться" присуще всем последовательностям, построенных по рекуррентной формуле xi+1=f(xi).
Повторяющийся цикл называется периодом. Длина периода у различных последовательностей разная. Чем больше, тем лучше.
Наилучшие из известных сегодня методов имитации случайных чисел представляют собой частные случаи схемы, предложенные в 1948 году Д.Х.Лемером.
Суть метода: Выбираем четыре "магических числа":
$$x_0$$ – начальное значение, $$x_0\ge 0; $$
$$a$$ – множитель, $$a\ge 0;$$
$$c$$ – приращение, $$c\ge 0;$$
$$m$$ – модуль, $$m > x_0, m > a, m > c$$.
Тогда искомая последовательность случайных чисел получается из соотношения:
$$x_{i+1}=(ax_i+c) Mod(m), n\ge0,$$т. е. каждое случайное число – это остаток, при делении (axi+c) на m (операция Mod - "определение остатка", термин взят от слова "
Последовательность, полученная из соотношения (7.1) называется линейной конгруэнтной последовательностью.
Пример: x0 = a = c = 7, m = 10.
Тогда последовательность имеет вид: 7, 6, 9, 0, 7, 6, 9, 0,…
Как видно, при выбранных значениях "магических чисел" последовательность почти сразу "зациклилась", длина периода = 4.
Из этого примера видно, что "магические числа" нельзя выбирать произвольно. Проведено много исследований и доказано теорем по вопросу "как правильно выбирать" "магические числа".
Метод получения случайных чисел при c=0 называется "мультипликативный конгруэнтный метод", при $$c\neq0$$ - "смешанный конгруэнтный метод". При c=0, выработка последовательностей происходит быстрее, но при этом уменьшается длина периода последовательностей.
Первоначально в методе Лемера было принято c=0. Идея получения более длинных последовательностей за счет $$c\neq0$$ принадлежит Томпсону и независимо Ротенбергу.
Выбор модуля m. Для получения длинных последовательностей и для увеличения скорости вычисления рекомендуется m выбирать равным размеру машинного слова. Для 32х разрядного машинного слова m = 231=2147483648, (левый нулевой бит слова отведен под знак числа).
При этом в 32х разрядном машинном слове, максимальное целое число, размещающее в машинном слове, равно $$\omega=2^{31}-1=2147483647\dots $$
Тогда $$m=\omega+1$$
Значение множителя также влияет на длину периода последовательностей. По этому вопросу также проведено много исследований.
Линейные конгруэнтные последовательности – не единственный из предложенных источников случайных чисел. Его можно обобщить, превратив его, например, в квадратичный конгруэнтный метод
$$x_{i+1}=(dx_1^2+a \cdot X_n+c) Mod(m).$$Известен квадратичный метод, предложенный Р. Ковэю:
$$x_{i+1}=x_i(x_i+1) Mod(2^e).$$Известен метод получения случайных чисел, где реализуется последовательность Фибоначчи:
$$x_{i+1}=(x_i+x_{i-1}) Mod(m).$$Известен также метод получения случайных чисел, предложенный Грином:
$$x_{i+1}=(x_i+x_{i-k}) Mod(m),$$где k - большое число.
Имеются еще, так называемые, аддитивные методы, где не требуются операции умножения и деления, и другие методы.
При реализации на ЭВМ статистического моделирования возникает задача получения (генерирования) на ЭВМ случайных числовых последовательностей с заданными вероятностными характеристиками, в которых каждое число – это имитация случайного значения какого-либо параметра реального процесса или системы, подверженного случайным возмущениям.
Генерирование на ЭВМ таких случайных числовых последовательностей получило название
В математической литературе часто используется термины "последовательность случайных чисел" или просто "случайные числа".
Однако, если проанализировать эти термины с философской точки зрения, то можно спросить: а есть ли такой объект как случайное число? Число 2 – это случайное число? Или число 17 – это случайное число? Конечно, нет. Если использовать точные термины, то можно говорить только о случайной последовательности чисел или о случайном значении параметров. Однако, в литературе широко используется термины "случайные числа" и "последовательность случайных чисел", и это означает, что каждое число было получено самым произвольным образом, без всякой связи с другими членами последовательности, и что у него есть определенная вероятность оказаться в заданном интервале.
Раньше ученые, нуждавшиеся для своей работы в случайных числах, раскладывали карты, бросали кости или вытаскивали шары из урны, которую предварительно как следует трясли. В 1927 году Л. Типпетт опубликовал таблицы, содержащие свыше 40 000 случайных чисел, взятых произвольно из отчетов по переписи. Позже были сконструированы специальные машины, механически вырабатывающие случайные числа. В 1955 году компания RAND Corporation опубликовала хорошо известные таблицы с миллионом случайных чисел, полученных одной из таких машин.
После создания ЭВМ начались поиски эффективных алгоритмов получения (генерирования на ЭВМ) последовательностей случайных чисел, пригодных для программной реализации.
Последовательности случайных чисел, вырабатываемые детерминистскими способами (т. е. с помощью специальных алгоритмов) называются псевдослучайными или квазислучайными. В дальнейшем мы будем их называть просто случайными последовательностями, понимая, что они просто производят впечатление случайных.
Задачу
Вначале получают последовательность равномерно распределенных на интервале [0, 1] псевдослучайных чисел.
Из равномерно распределенной последовательности получают последовательность псевдослучайных чисел с заданным законом распределения в заданном интервале.
Равномерным называется такое распределение, при котором каждое возможное случайное число равновероятно. Обычно, если специально не оговорен закон распределения случайных чисел, то имеют в виду равномерное распределение.
Сущность алгоритмических методов получения равномерно распределенных псевдослучайных чисел заключается в том, что xi+1 = f (xi),
где каждое следующее (i+1)-e значение образуется из предыдущего (или группы предыдущих) путем применения некоторого алгоритма, содержащего логические и арифметические операции.
Известно большое количество имитации равномерного распределения (методы вычетов, суммирования, усечения, перемешивания). Общими для всех этих методов являются требования:
Первым алгоритмический метод получения равномерно распределенных псевдослучайных чисел предложил Джон фон Нейман (один из основоположников кибернетики).
Суть метода: предыдущее случайное число возводится в квадрат, а затем из результата извлекаются средние цифры.
Например:
$$\text{пусть } x_0 =0.2061, \text{ тогда } x_0^2 =0.04\vert 2477\vert 21;\\ x_1 =0.2477, x_1^2 =0.06\vert 1355\vert 29;\\ x_2 =0.1355, x_2^2 =0.01\vert 8360\vert 25$$и т.д.
Как видно
Свойство "зацикливаться" присуще всем последовательностям, построенных по рекуррентной формуле xi+1=f(xi).
Повторяющийся цикл называется периодом. Длина периода у различных последовательностей разная. Чем больше, тем лучше.
Наилучшие из известных сегодня методов имитации случайных чисел представляют собой частные случаи схемы, предложенные в 1948 году Д.Х.Лемером.
Суть метода: Выбираем четыре "магических числа":
$$x_0$$ – начальное значение, $$x_0\ge 0; $$
$$a$$ – множитель, $$a\ge 0;$$
$$c$$ – приращение, $$c\ge 0;$$
$$m$$ – модуль, $$m > x_0, m > a, m > c$$.
Тогда искомая последовательность случайных чисел получается из соотношения:
$$x_{i+1}=(ax_i+c) Mod(m), n\ge0,$$т. е. каждое случайное число – это остаток, при делении (axi+c) на m (операция Mod - "определение остатка", термин взят от слова "
Последовательность, полученная из соотношения (7.1) называется линейной конгруэнтной последовательностью.
Пример: x0 = a = c = 7, m = 10.
Тогда последовательность имеет вид: 7, 6, 9, 0, 7, 6, 9, 0,…
Как видно, при выбранных значениях "магических чисел" последовательность почти сразу "зациклилась", длина периода = 4.
Из этого примера видно, что "магические числа" нельзя выбирать произвольно. Проведено много исследований и доказано теорем по вопросу "как правильно выбирать" "магические числа".
Метод получения случайных чисел при c=0 называется "мультипликативный конгруэнтный метод", при $$c\neq0$$ - "смешанный конгруэнтный метод". При c=0, выработка последовательностей происходит быстрее, но при этом уменьшается длина периода последовательностей.
Первоначально в методе Лемера было принято c=0. Идея получения более длинных последовательностей за счет $$c\neq0$$ принадлежит Томпсону и независимо Ротенбергу.
Выбор модуля m. Для получения длинных последовательностей и для увеличения скорости вычисления рекомендуется m выбирать равным размеру машинного слова. Для 32х разрядного машинного слова m = 231=2147483648, (левый нулевой бит слова отведен под знак числа).
При этом в 32х разрядном машинном слове, максимальное целое число, размещающее в машинном слове, равно $$\omega=2^{31}-1=2147483647\dots $$
Тогда $$m=\omega+1$$
Значение множителя также влияет на длину периода последовательностей. По этому вопросу также проведено много исследований.
Линейные конгруэнтные последовательности – не единственный из предложенных источников случайных чисел. Его можно обобщить, превратив его, например, в квадратичный конгруэнтный метод
$$x_{i+1}=(dx_1^2+a \cdot X_n+c) Mod(m).$$Известен квадратичный метод, предложенный Р. Ковэю:
$$x_{i+1}=x_i(x_i+1) Mod(2^e).$$Известен метод получения случайных чисел, где реализуется последовательность Фибоначчи:
$$x_{i+1}=(x_i+x_{i-1}) Mod(m).$$Известен также метод получения случайных чисел, предложенный Грином:
$$x_{i+1}=(x_i+x_{i-k}) Mod(m),$$где k - большое число.
Имеются еще, так называемые, аддитивные методы, где не требуются операции умножения и деления, и другие методы.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.