Модели датчиков случайных и псевдослучайных чисел. Обработка одномерной выборки

ЛЕКЦИЯ 2. Модели датчиков случайных и псевдослучайных чисел. Обработка одномерной выборки Наша цель – научиться отвечать на четыре вопроса: 1. Для каких задач требуется моделировать случайные величины? 2. Какие существуют способы описания случайных величин? 3. Чем случайные величины отличаются от псевдослучайных? 4. Какие существуют модели и методы моделирования псевдослучайных величин? Определение случайной величины Случайной величиной (СВ) называют переменную, которая в результате испытания принимает единственное значение, которое зависит от события и не может быть известно заранее. СВ обозначается как Х, а ее значения как х. Случайные величины Дискретные случайные величины Непрерывные случайные величины Дискретная случайная величина (СВ) Дискретной СВ называется СВ, которая в результате испытания принимает отдельные значения с определёнными вероятностями. Число возможных значений дискретной случайной величины может быть конечным и бесконечным. Число очков при бросании игральных кубиков Число попаданий в мишень при N выстрелах Количество выпавших орлов при N бросках монеты Непрерывная случайная величина Непрерывной СВ называют СВ, которая в результате испытания принимает все значения из некоторого числового промежутка. Число возможных значений непрерывной случайной величины бесконечно. отклонение от номинала некоторого размера детали при правильно налаженном технологическом процессе Зачем нужны случайные величины? Случайные величины являются математическим инструментом (моделями) для описания или имитации различных случайных событий или явлений. Источник информации Источник информации Шумы/ помехи 1 1 0.5 signal n - 1.714 10 - 15 - 0.5 200 400 600 n 800 1 10 3 10 3 100 76.543 50 signal_plus_shumn - 50 - 85.613 - 100 200 400 600 n 800 3 1 10 3 10 Распределение случайной величины Вероятностное распределение СВ это график, формула или таблица, которые указывают на соответствие между принимаемыми значениями и их вероятностями. Законом распределения СВ называется соответствие между значениями случайной величины и их вероятностями. Пример. График. Распределение числа мальчиков среди шести новорожденных: Гистограмма показывает нам соответствие между принимаемыми значениями СВ и их вероятностями Пример. Таблица. Таблица указывает на соответствие между принимаемыми значениями СВ и их вероятностями. Таблица задает закон распределения СВ Пример. Аналитическое описание СВ. Вероятностное распределение СВ может быть задано аналитически – формулой. Формула для нахождения вероятности к мальчиков среди 6 новорожденных: Основные законы распределения, необходимые для генерации случайных величин В статистических способах моделирования случайных величин используются два базовых закона распределения. Проведенные на практике эксперименты показывают, что двух видов СВ: распределенных равномерно R(0,1) и нормально N(0,1) – достаточно для генерации из них и случайных величин других ЗР (Релея, Релея Райса, Вейбулла, Фишера и т.д.), встречающихся в практике статистического моделирования. 1 , где 𝑎 < 𝑥 ≤ 𝑏 𝑓(𝑥) = ቐ 𝑏−𝑎 0, где 𝑥 не принадлежит (𝑎, 𝑏) Равномерный ЗР R(0,1) 𝑓(𝑥) = 1 𝜎 2𝜋 (𝑥−𝜇)2 − 𝑒 2𝜎2 Нормальный ЗР N(0,1) Равномерное распределение Непрерывная случайная величина имеет равномерное распределение или согласуется с ним, если ее значения равномерно распределены на отрезке. 1 , где 𝑎 < 𝑥 ≤ 𝑏 𝑓(𝑥) = ቐ 𝑏−𝑎 0, где 𝑥 не принадлежит (𝑎, 𝑏) 0, 𝑥 < 𝑎 F 𝑥 = ቐ 𝑥 − 𝑎 𝑏 − 𝑎 ,𝑎 < 𝑥 < 𝑏 1, 𝑥 > 𝑏 Равномерное распределение. Пример Продолжительность лекции – 85 минут. Преподаватель планирует свои лекции так, чтобы их продолжительность равномерно распределена на отрезке времени от 80 до 90 минут Какова вероятность, что лекция задержится больше чем на одну минуту? 0.1 80 90 Нормальное распределение Непрерывная случайная величина имеет нормальное распределение, если ее плотность задается выражением: 𝑓(𝑥) = Ф(𝑥) = 1 𝜎 2𝜋 (𝑥−𝜇)2 − 𝑒 2𝜎2 𝑥 1 𝑒 ‫׬‬ 𝜎 2𝜋 −∞ (𝑡−𝜇)2 − 2𝜎2 𝑑𝑡 Нормальное распределение. Пример Пример 1: случайная величина, средний рост взрослого человека в отдельно взятом городе, будет подчиняться нормальному распределению. Действительно, большинство людей имеют рост 170 см, но также будут встречаться и высокие люди более 2 метров, и низкие с ростом менее 150 см. Пример 2: нормальному распределению подчиняются большое количество случайный величин, среди них: вес полуфабриката, длина изделия, время производственного цикла, время обработки, количество дефектов по дням и т.д. Случаи когда перечисленные величины не распределены по нормальному закону могут возникать, но довольно редко. Генерация случайных чисел Ключевым вопросом при моделировании случайных событий и случайных величин является получение (генерация) случайных чисел. Пример применения генератора: - Генерация паролей - Шифрование - Генератор текста - Порядок раздачи карт в карточной игре в интернете Генератор случайных и псевдослучайных чисел Генератор псевдослучайных чисел (ГПСЧ) использует единственное начальное значение, откуда и следует его псевдослучайный характер. Генератор случайной величины (ГСЧ) всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии. Энтропия – мера беспорядка. Информационная неопределенности или непредсказуемость информации. энтропия – мера ГСПЧ – имеет алгоритм, который можно воспроизвести ГСЧ – получаем числа из какого либо шума, возможность предсказать значения которого стремится к нулю. Требования к генератору псевдослучайных чисел Генератор равномерно распределенных псевдослучайных чисел должен удовлетворять следующим требованиями: - Генерируемая СВ r должна быть равномерно распределена на интервале (0,1) - Все ее значения должны быть независимы между собой, т.е. не подчиняться никаким рекуррентным последовательностям. - Обладать максимальным быстродействием и не требовать больших затрат памяти - Обеспечивать возможность многократно точно воспроизводить заданный поток случайных чисел. Методы формирования равномерно распределенных случайных чисел с помощью вычислительной техники 1. Таблицы случайных чисел (на практике используется редко) Когда случайные числа составлены вне устройства и записаны в оперативную память из вне. 2. Физические генераторы. Дополнительные подключаемые устройства. Как правило содержат источник шумового напряжения (диод, резистор и др.). Данный способ обеспечивает нас истинно случайными числами, но числа полученные такими генераторами нельзя получить повторно, что усложняет возможности отладки алгоритмов. 3. Метод псевдослучайных чисел Используется заранее заданный алгоритм. При М разрядах мантиссы в ПК может быть сформировано 2М случайных чисел. Пример наиболее простых и часто используемых генераторов - Линейный конгруэнтный - Фибоначчи - Мультипликативный - Мультипликативный (Полларда) - Вихрь Мерсена Линейный конгруэнтный метод моделирования распределенных равномерно СВ Линейный конгруэнтный метод является одной из простейших процедур для генерации псевдослучайных чисел. Для задания такого датчика, требуется 4 числа: - Начальное значение x0, x0 ≥0 - Множитель a, a ≥0 - Приращение b, c≥0 - Модуль n, n>x0, m>a, m>c Линейный конгруэнтный метод. Рекомендации Выбирать коэффициенты конгруэнтного уравнения и значения модуля рекомендуется следующим образом: 1. Оптимальный выбор модуля, n – это наибольшее простое число, близкое к размеру слова, используемого в компьютере. К примеру можно использовать тридцать первое простое число Мерсенна М[31]. 2. Значение b следует брать близким к машинному нулю. Модель датчика Фибоначчи Существует класс генератор, основанный на использовании последовательностей Фиббоначи. Пример – 0,1,1,2,3,5,8,13,21,34,… каждый последующий член равен сумме двух предыдущих (кроме первых двух чисел последовательности). Один из датчиков имеет следующий вид: 𝑋𝑘−𝑎 − 𝑋𝑘−𝑏 , 𝑋𝑘−𝑎 ≥ 𝑋𝑘−𝑏 𝑋𝑘 = ቊ 𝑋𝑘−𝑎 − 𝑋𝑘−𝑏 + 1, 𝑋𝑘−𝑎 < 𝑋𝑘−𝑏 Где, Xk – вещественные числа из диапазона [0,1), a и b – целые положительные числа. Для старта такому датчику необходимо задать max(a,b) случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком. Модель датчика Фибоначчи. Пример Вычислим последовательность из первых десяти чисел, генерируемую методом Фибоначчи с запаздыванием начиная с k5 при следующих исходных данных: a = 4, b = 1, k0=0.1; k1=0.7; k2=0.3; k3=0.9; k4=0.5: k5 = k1 - k4 = 0.7 - 0.5 = 0.2; k6 = k2 - k5= 0.3 - 0.2 = 0.1; k7 = k3 - k6 = 0.9 - 0.1 = 0.8; k8 = k4 - k7 + 1 =0.5 - 0.8 + 1 = 0.7; k9 = k5- k8 + 1 =0.2 - 0.7 + 1 = 0.5; k10 = k6 - k9 + 1 =0.1 - 0.5 + 1 = 0.6; k11 = k7 - k10 = 0.8 - 0.6 = 0.2; k12 = k8 - k11 = 0.7 - 0.2 = 0.5; k13 = k9 - k12 + 1 =0.5 - 0.5 + 1 = 1; k14 = k10 - k13 + 1 =0.6 - 1 + 1 = 0.6. Модель датчика Фибоначчи. Рекомендации Практики рекомендуют для использования следующие пары значений a и b: 17 и 5 - хорошо подходят для простых приложений; 55 и 24 – удовлетворительны для большинства криптографических алгоритмов; 97 и 33 – позволяют получать очень качественные случайные числа, которые используются для генерации случайных векторов большой размерности 20 и 5 – применяется для генерации распределенных равномерно случайных чисел в системе MATLAB Модель мультипликативного датчика Мультипликативные датчики используют следующий алгоритм генерации: где m – число двоичных разрядов в мантиссе ячейки, M – достаточно большое целое число, {.} – взятие дробной части числа, заключенного в фигурные скобки. Гистограмма и эмпирическая функция распределения Гистограмма частот - ступенчатая фигура, состоящая из прямоугольников, основаниями которых служат частичные интервалы длиной h, а высоты равны отношению ni / h (плотность частоты). Для построения гистограммы частот на оси абсцисс откладывают частичные интервалы, а над ними проводят отрезки, параллельные оси абсцисс на расстоянии ni / h. Площадь i - го частичного прямоугольника равна h*ni / h = ni - сумме частот вариант i - го интервала; следовательно, площадь гистограммы частот равна сумме всех частот, т.е. объему выборки. Эмпирическая функция распределения (функция распределения выборки) - это функция F*(x), которая определяет для каждого значения xi относительную частоту события X