Rand случайная величина


Содержание

Генерация случайных чисел в языке Си

Пожалуйста, приостановите работу AdBlock на этом сайте.

Иногда может возникнуть необходимость в генерации случайных чисел. Простой пример.

Пример: Определение победителя в конкурсе репостов.

Имеется список из 53 человек. Необходимо выбрать из них победителя. Если вы выберете его самостоятельно, то вас могут обвинить в предвзятости. Поэтому вы решили написать программу. Она будет работать следующим образом. Вы вводите количество участников N , после чего программа выводит одно число – номер победителя.

Как получить число от игрока, вам уже известно. А вот как заставить компьютер загадать случайное число? В этом уроке вы этому научитесь.

Функция rand().

Данная функция возвращает случайное целое число в диапазоне от нуля до RAND_MAX . RAND_MAX это специальная константа языка Си, в которой содержится максимальное целое число, которое может быть возвращено функцией rand() .

Функция rand() определена в заголовочном файле stdlib.h . Поэтому, если хотите использовать rand в своей программе, не забудьте подключить этот заголовочный файл. Константа RAND_MAX тоже определена в этом файле. Вы можете найти этот файл у себя на компьютере и посмотреть её значение.

Давайте посмотрим на эту функцию в действии. Запустим следующий код:

Должно получиться что-то вроде этого.

Рис.1 Пять случайных чисел, сгенерированных функцийе rand

Но нам бы хотелось получить числа от 1 до 53 , а не всё подряд. Ниже описано несколько трюков, позволяющих наложить ограничения на функцию rand() .

Ограничить случайные числа сверху.

Кто в школе ждал момента, когда ему пригодится математика, приготовьтесь. Этот момент наступил. Чтобы ограничить сверху случайные числа, можно воспользоваться операцией получения остатка от деления, которую вы изучили в прошлом уроке. Наверное вы знаете, что остаток от деления на числа K всегда меньше числа K . Например, при делении на 4 могут получиться остатки 0, 1, 2 и 3 . Поэтому если вы хотите ограничить сверху случайные числа числом K , то просто возьмите остаток от деления на K . Вот так:

Рис.2 Пять случайных чисел меньше 100

Ограничить числа снизу.

Функция rand возвращает случайные числа из отрезка [0, RAND_MAX] . А что если нам нужны только числа большие числа M (например, 1000 )? Как быть? Всё просто. Просто прибавим к тому, что вернула функция rand, наше значение M . Тогда если функция вернёт 0 , итоговый ответ будет M , если 2394 , то итоговый ответ будет M + 2394 . Этим действием мы как бы сдвигаем все числа на M единиц вперёд.

Задать границы функции rand сверху и снизу.

Например, получить числа от 80 до 100 . Кажется, нужно просто объединить два способа, которые приведены выше. Получим что-то вроде этого:

Попробуйте запустить эту программу. Удивлены?

Да, такой способ работать не будет. Давайте прокрутим эту программу руками, чтобы убедиться в том, что мы допустили ошибку. Допустим rand() вернула число 143 . Остаток от деления на 100 равен 43 . Дальше 80 + 43 = 123 . Значит такой способ не работает. Подобная конструкция выдаст числа от 80 до 179 .

Давайте разберём по действиям наше выражение. rand()%100 может выдать числа от 0 до 99 включительно. Т.е. из отрезка [0; 99] .
Операция + 80 сдвигает наш отрезок на 80 единиц вправо. Получаем [80; 179] .
Как видим, проблема у нас заключается в правой границе отрезка, она сдвинута вправо на 79 единиц. Это наше исходное число 80 минус 1 . Давайте наведём порядок и сдвинем правую границу назад: 80 + rand()%(100 — 80 + 1) . Тогда всё должно сработать как надо.

В общем случае если нам нужно получить числа из отрезка [A;B] , то необходимо воспользоваться следующей конструкцией:
A + rand()%(B-A+1) .

Согласно этой формуле перепишем нашу последнюю программу:

Рис.3 Случайные числа из диапазона [80;100]

Ну вот, теперь вы можете решить исходную задачу урока. Сгенерировать число из отрезка [1; N] . Или не можете?

Но прежде ещё немного полезной информации. Запустите последнюю программу три раза подряд и записывайте себе случайные числа, которые она генерирует. Заметили?

Функция srand().

Да, каждый раз появляются одни и те же одинаковые числа. «Так себе генератор!» – скажете вы. И будете не совсем правы. Действительно, генерируются всё время одинаковые числа. Но мы можем на это повлиять, для этого используется функция srand() , которая также определена в заголовочном файле stdlib.h . Она инициализирует генератор случайных чисел начальным числом.

Скомпилируйте и запустите несколько раз вот эту программу:

Теперь поменяйте аргумент функции srand() на другое число (надеюсь вы ещё не забыли, что такое аргумент функции?) и снова скомпилируйте и запустите программу. Последовательность чисел должна измениться. Как только мы меняем аргумент в функции srand – меняется и последовательность. Не очень практично, не правда ли? Чтобы изменить последовательность, нужно перекомпилировать программу. Вот бы это число туда подставлялось автоматически.

И это можно сделать. Например, воспользуемся функцией time() , которая определена в заголовочном файле time.h . Данная функция, если ей в качестве аргумента передать NULL , возвращает количество секунд, прошедших c 1 января 1970 года . Вот посмотрите, как это делается.

Вы спросите, а что такое NULL ? Резонный вопрос. А я вам пока отвечу, что это специальное зарезервированное слово такое. Могу ещё сказать, что им обозначает нулевой указатель, но т.к. это для вас никакой информации не несёт, то на данный момент рекомендую об этом не думать. А просто запомнить как некоторый хитрый трюк. В будущих уроках мы остановимся на этой штуке поподробнее.

Практика

Решите предложенные задачи. Для удобства работы сразу переходите в полноэкранный режим

Исследовательские задачи для хакеров:

  1. В каких ситуациях ещё может пригодиться генерация случайных чисел? Напишите ваши варианты в комментарии к этому уроку.
  2. Напишите программу, которая выводит на экран значение целочисленной константы RAND_MAX. Найдите файл stdlib.h на вашем компьютере, найдите значение этой константы в этом файле.
  3. Найдите в интернете описание функций, которые определены в заголовочном файле time.h Вы, конечно, ещё не сможете ими пользоваться, но знать, что такие функции есть, всё равно нужно. Ведь когда-то настанет момент, когда ваших знаний будет достаточно для их использования.
  4. Числа, генерируемые функцией rand(), имеют равномерное распределение. Это значит, что если запускать функцию rand очень много раз и каждый раз записывать, какое число выпало, то количество выпадения различных чисел будет одинаковым. Например, если генерировать только числа 0 и 1, то через 100 запусков примерно 50 раз выпадет ноль и 50 раз единичка. Обратите внимание, что я говорю примерно. Может быть, например, 49 и 51, или 53 и 47. Если рассматривать это в отношении к общему числу запусков, получим (49/100 и 51/100 или 53/100 и 47/100 соответственно). Но чем больше экспериментов мы проведём, тем ближе отношение количество единичек к количеству испытаний будет стремиться к 1/2. Проведите самостоятельно эксперимент с 10, 50 и 100 запусками. Это муторно и долго, если делать руками, но что поделать? В будущем мы напишем программу, чтобы проверить свойство равномерности распределения наших случайных чисел.

Зона кода

Просматривая книгу Седжвика, Уэйна и Дондеро «Программирование на языке Python: учебный курс» (я уже упоминал её на страницах данного сайта здесь и здесь), я наткнулся на код программы «Броуновский мост». В ней вызывалась функция gaussian () , входящая в стандартный модуль stdrandom языка Python.

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

Ведь все стандартные функции языка C99, каким-либо образом связанные с генерацией псевдослучайных чисел, исчерпываются всего лишь двумя функциями, входящими в библиотеку stdlib.h. Одна из них — это rand() . Данная функция генерирует псевдослучайные целые числа, равномерно распределённые в диапазоне от 0 до RAND_MAX включительно (в нашем случае значение макроса RAND_MAX равно 32767).

Другая функция — это srand() , которая «вынуждает» функцию rand() генерировать последовательность, «жёстко связанную» с аргументом, передаваемым srand() (каждому такому аргументу соответствует своя последовательность).

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

Выбор варианта решения поставленной задачи

Напомню, что случайная величина, распределённая по нормальному закону, — это непрерывная случайная величина, заданная следующей функцией распределения:

F m , σ x = 1 σ 2 π ∫ — ∞ x e — t — m 2 2 σ 2 d t .


Здесь m и σ — параметры случайной величины, имеющие смысл её математического ожидания и среднеквадратического отклонения соответственно. Часто нормальное распределение называют также распределением Гаусса.

В дальнейшем мы будем рассматривать стандартную нормальную случайную величину, имеющую параметры m = 0 и σ = 1. Её функцию распределения обозначим F(x):

F x = 1 2 π ∫ — ∞ x e — t 2 2 d t .

Стоит нам научиться генерировать псевдослучайные числа, распределённые по стандартному нормальному закону, так сразу же мы сможем получить и числа, распределённые по нормальному закону с произвольными значениями параметров (об этом поговорим в конце статьи).

Заметим, что с помощью функции rand() можно сгенерировать псевдослучайные числа, равномерно распределённые на отрезке [0; 1]. Для этого достаточно каждое значение, возвращаемое rand() , делить на значение макроса RAND_MAX . Так что постановку нашей задачи можно конкретизировать и перевести в теоретическую плоскость, не учитывающую псевдослучайность значений, получаемых программно.

В этой постановке задача будет формулироваться так: получить случайную величину, распределённую по стандартному нормальному закону, имея в распоряжении непрерывную случайную величину, равномерно распределённую на отрезке [0; 1]. Сразу же замечу, что эта задача имеет достаточно простое решение. Обозначим, например, первую из упомянутых величин символом Y, а вторую — символом X. Легко показать, что Y можно выразить через X следующим образом:

Здесь F −1 (x) — это функция, обратная по отношению к функции F(x) (такая функция существует, поскольку F(x) монотонна на всей числовой оси).

Основная проблема при практическом использовании такого решения заключается в сложности вычисления значений функции F −1 (x).

Имеются и другие способы получения нормально распределённой случайной величины из распределённой равномерно. Некоторые из них описаны во 2-м томе «Искусства программирования» Дональда Кнута (способ, приведённый выше, там же тоже рассмотрен).

Из алгоритмов, приведённых в книге Кнута, самыми простыми для реализации являются, пожалуй, метод полярных координат и метод отношений. Оба этих метода используют в качестве исходных две независимые непрерывные случайные величины, распределённые равномерно на отрезке [0; 1], причём первый из них приводит к получению «на выходе» сразу двух нормально распределённых независимых случайных величин.

Ознакомившись с алгоритмами, предлагаемыми Кнутом, я решил, всё же, остановиться на самом первом варианте, приведённом в данном разделе, сводящем решение задачи к вычислению F −1 (x). Объясню причины такого решения.

Во-первых, даже упомянутые мною два алгоритма из книги Кнута требуют наличие «на входе» двух независимых равномерно распределённых на отрезке [0; 1] случайных величин. Если мы сразу же задумаемся о программной реализации этих алгоритмов, то перед нами сразу встанет вопрос: а сможем ли мы смоделировать две такие независимые случайные величины, обладая лишь одним единственным генератором псевдослучайных чисел (функцией rand() )?

Ведь в нашем распоряжении имеется только одна последовательность псевдослучайных чисел. Допустим, мы разделим её на 2 подпоследовательности (по принципу чётности и нечётности членов). В какой степени эти две новые последовательности можно рассматривать как модели независимых случайных величин, если они получены из одной последовательности? На этот вопрос я ответить не готов; для ответа, как мне кажется, требуется проводить дополнительные исследования.

Так что от упомянутых методов, в которых требуется независимость исходных случайных величин я решил, на всякий случай, отказаться.

Вторая причина, побудившая меня обратиться к методу, требующему вычисления F −1 (x), заключается в том, что стандартная библиотека языка C99 может мне «помочь» с вычислением функции F (x). К сожалению, вычисление значений самой функции F (x) в библиотеке не реализовано, но зато библиотекой math.h поддерживается вычисление функции erf(x), называемой функцией ошибок, выражающейся через интеграл следующим образом:

erf x = 2 π ∫ 0 x e — t 2 d t .

Вычислением её значений занимается функция erf() из библиотеки math.h. Подчеркну, что поддержка данной функции предусмотрена стандартом C99, но стандартные библиотеки более ранних версий языка C поддерживать эту функцию не обязаны.

Так вот, функция erf(x) является «родственной» по отношению к F(x). Говоря более конкретно: F(x) можно выразить через erf(x) следующим образом:

F ( x ) = 1 2 1 + erf x 2 .

А для чего нам нужно уметь вычислять значения F(x), ведь нас же интересует функция F −1 (x)? Ответ на этот вопрос читатель получит, ознакомившись со следующим разделом статьи.

Вычисление значений функции F −1 (x)

Предположим, что мы хотим вычислить значение функции F −1 (x) в некоторой точке x = a (разумеется, число a предполагаем принадлежащим множеству определения функции F −1 (x) , т. е. интервалу (0; 1) ). Искомое значение F −1 (a), очевидно, является корнем уравнения

Ниже приведён рисунок, иллюстрирующий данный факт. Он содержит графики функций y = F(x) и y = a. Видно, что абсцисса точки пресечения графиков — это и есть F −1 (a) .

Графики функций y = F(x) и y = a (щёлкните для увеличения)

Давайте составим схему приближённого решения уравнения F(x) = a одним из численных методов. Я предлагаю применить весьма простой в реализации метод, называемый методом Ньютона или методом касательных. Я уже упоминал и даже описывал этот метод в статьях данного сайта (здесь и здесь), так что на этот раз буду краток.

Метод Ньютона позволяет приближённо решать уравнения вида

при условии, что функция g(x) имеет в некоторой окрестности X корня x

этого уравнения отличную от нуля производную. Строится задаваемая рекуррентно последовательность следующего вида:

x 0 задано , x k + 1 = x k — g x k g ‘ x k , k = 0 , 1 , 2 , … .

Здесь x — это некоторое начальное значение, принадлежащее X. Разумеется, встаёт вопрос о существовании членов этой последовательности. Однако, известно, что если все они существуют и принадлежат X, то данная последовательность сходится к корню исходного уравнения.

На практике, естественно, члены последовательности прекращают вычислять при достижении нужной степени точности и последний вычисленный член берут в качестве приближённого корня уравнения.

В качестве условия окончания итераций (т. е. вычислений членов последовательности) часто выбирают выполнение неравенства

— x k + 1 ) не превысит ε. Такой же критерий окончания итераций будем использовать и мы.

В нашем случае, очевидно, g(x) = F(x) − a. Таким образом, итерационная схема будет иметь вид.

x 0 задано , x k + 1 = x k — F x k — a F ‘ x k , k = 0 , 1 , 2 , … .

Учитывая связь между F(x) и erf(x), а также то, что

F ‘ x = 1 2 π e — x 2 2 ,

перепишем схему в виде

x 0 задано , b = 1 — 2 a , x k + 1 = x k — π 2 erf x 2 + b e x 2 2 , k = 0 , 1 , 2 , … .

Как известно, функция F(t) обладает свойством

из которого следует, что

Возьмём от обеих частей этого равенства функцию F −1 :

Сделаем замену: x = F(t), т. е. t = F −1 (x). В итоге, получаем:

Таким образом, мы можем ограничиться реализацией вычислений значений функции F −1 (x) лишь на интервале (0,5; 1) , а её значения на интервале (0; 0,5) получать по приведённой выше формуле (а то, что F(0,5) = 0 мы знаем и так, без всяких вычислений).

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

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

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

К сожалению, график функции F(x) при увеличении x «очень быстро» начинает «прижиматься снизу» к прямой y = 1 (см. рисунок), т. е. производная F(x) (совпадающая с производной функции F(x) − a) становится слабо отличимой от нуля. Это неблагоприятным образом сказывается на количестве итераций при значениях a, близких к 1. Можно попытаться компенсировать увеличение итераций при таких a выбором начальных значений x.


Поговорим, как раз, о выборе значений x. Поступим следующим образом. Найдём приближённые значения функции F −1 (x) в «эталонных» точках 0,5, 0,6, 0,7, 0,8, 0,9, 0,97. Для приближённого нахождения значения F −1 (x) в точке a в качестве начального значения x возьмём значение F −1 (x) в той из этих шести точек, к которой точка a наиболее близка (исключение составит лишь случай попадания a в интервал (0,935; 0,95); здесь в качестве x будет выбрано ≈F −1 (0,95)).

А что, если нам потребуется найти F −1 (0) и F −1 (1)? С формальной точки зрения, F −1 (x) в точках 0 и 1 не определена, однако имеет в этих точках следующие односторонние пределы:

lim x → — 0 F — 1 x = — ∞ , lim x → 1 + 0 F — 1 x = + ∞ .

Тем не менее, случайная величина, непрерывно распределённая на отрезке [0; 1], может принимать значения, совпадающие с границами отрезка (правда, теоретически вероятности принятия таких значений нулевые, но наша случайная величина, моделируемая программно, может принять эти значения пусть и с малыми вероятностями, но отличными от нуля). Так что решать проблему «вычисления» F −1 (0) и F −1 (1), всё же, придётся.

Можно, конечно, возвращать специальные значения типа double , соответствующие «−∞» и «+∞», но это не лучшее решение, поскольку конструируемый нами генератор псевдослучайных чисел, распределённых по нормальному закону, должен всегда выдавать именно вещественные числа, и ничего кроме них.

Итак, какое значения приписать F −1 (1)? Напомню, что мы моделируем непрерывную случайную величину, равномерно распределённую на отрезке [0; 1], вызывая функцию rand() и деля возвращённое ею значение на RAND_MAX , т. е. на 32767. Максимальное значение такого частного, не превышающее единицу, равно, очевидно, 32766 / 32767, т. е. 0,99997… . Так что F −1 (1) припишем значение, немного превышающее F −1 (0,99997) ≈ 4,012811 . Я решил принять это значение равным 4,3. В этом случае, очевидно, в качестве F −1 (0) следует брать число −4,3.

Наша функция, написанная на C99, будет возвращать значение 4,3 даже в более общем случае: если переданный ей аргумент превышает разность 1 − ε. А если значение меньше ε, то функция будет возвращать −4,3.

Какое число принять за ε? Два соседних значения, выдаваемых нашим генератором псевдослучайных чисел, равномерно распределённых на отрезке [0; 1], различаются на 1 / 32767, т. е. примерно на 3,05 * 10 -5 . Нет смысла вычислять значения F −1 (x) с точностью, сильно превышающей точность, с которой «выдаются» упомянутые выше псевдослучайные числа. Так что в качестве ε я решил взять, для простоты, 10 −5 .

Ну что ж, все теоретические проблемы мы обсудили, так что можно приступать к программированию.

Создание функции, вычисляющей F −1 (x) и её тестирование

Мы создадим функцию, вычисляющую F −1 (x), в рамках программы, которая будет эту функцию тестировать. Вся программа целиком уместится в одном-единственном файле.

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

Следующий блок кода содержит определения макросов-констант:

Смысл первых двух констант, полагаю, ясен из комментариев. Что касается макроса-константы eps , то он имеет тот же смысл, что и число ε.

Илон Маск рекомендует:  Что такое код ifx_num_fields

Объявляем и инициализируем массив, который содержит приближённые значения функции F −1 (x) в 6 точках, которые будут использоваться в качестве начальных значений для итераций:

Объявляем глобальную переменную it — счётчик итераций:

Наконец, создаём функцию f_1() , вычисляющую значения F −1 (x):

Функция f_1() вычисляет и возвращает приближённое значение функции F −1 (x) в точке, переданной f_1() в виде параметра. Вычисление производится с теми оговорками, касающимися значений аргументов, близких к 0 и 1, о которых шла речь в предыдущем разделе.

Сначала обрабатываем частные случаи аргументов функции F −1 (x), не требующие привлечение метода Ньютона (стр. 3-8).

Далее (см. стр. 9-14) выясняем, в какой из интервалов попадает аргумент: в (0; 0,5) или в (0,5; 1). В первом случае от аргумента x переходим к аргументу 1 — x . В переменной sign сохраняем знак искомого значения функции F −1 (x) (т. е. число −1, если знак отрицателен или число 1, если положителен).

Создаём переменные xk1 и xk — аналоги текущего (вычисляемого) и предыдущего членов последовательности приближённых значений корня соответственно; первой из этих переменных сразу присваиваем соответствующее аргументу x начальное значение из массива val (стр. 15). Обнуляем счётчик итераций (стр. 17).

Сами итерации реализованы в цикле do while (стр. 18-25). Последний вычисленный член последовательности, содержащийся в xk1 , присваиваем переменной xk (стр. 20), после чего вычисляем новое значение xk1 через старое, хранящееся в xk , в соответствии со схемой, приведённой ранее, т. е. выполняем итерацию (стр. 21-22). Не забываем инкрементировать счётчик итераций (стр. 23).

Цикл продолжается, пока требуемая погрешность не превышает модуля разности двух последних вычисленных членов последовательности (см. стр 25). Как только это условие нарушается, т. е., как только модуль разности становится меньше погрешности, итерации заканчиваются; последний вычисленный член последовательности в этот момент содержится в переменной xk1 .

Остаётся выполнить последнее действие: в качестве окончательного результата вернуть либо значение переменной xk1 , либо значение, противоположное данному, в зависимости от знака результата, хранящегося в переменной sign (стр. 26).

Разумеется, окончательная версия функции f_1() не должна содержать кода, работающего со счётчиком итераций, т. е. строк 17 и 23. Данный код понадобится нам только для тестирования.

Собственно, количество итераций, требующихся для вычислений значений F −1 (x) в различных точках, — это, как раз, то, что будет нас интересовать в ходе тестирования в первую очередь.

Создадим, для удобства, функцию calc() , выводящую на печать переданную ей в качестве параметра точку, значение функции F −1 (x) в этой точке, полученное, естественно, с помощью вызова f_1() , и количество итераций, потребовавшееся для вычисления этого значения:

Не могу упустить возможность задать вопрос новичкам в программировании (если вдруг они читают эту статью). Почему нельзя было ограничиться единственным вызовом функции printf() ? Другими словами, почему тело функции calc() не может состоять из единственной строчки, приведённой ниже?

Ну что, догадались?

Всё дело в способе передачи фактических параметров функции в момент её вызова. Они передаются через стек. При этом, стандарт языка не оговаривает, в каком порядке параметры в него заталкиваются.

Предположим теперь, что параметры заталкиваются в стек в обратном порядке (т. е. справа налево). Разумеется, вычисляются параметры непосредственно перед заталкиванием (нет смысла их сначала вычислять и где-то временно хранить, а затем заталкивать). Таким образом, при вызове printf() (см. приведённую выше строку кода) сначала в стек будет помещено значение переменной it , затем будет произведён вызов f_1(x) и в стек будет направлен его результат, далее в стек будет помещено значение x , и, наконец, последним в стек пойдёт адрес C-строки, описывающей формат вывода.

Таким образом, в стеке окажется (и затем будет выведено на печать) то значение переменной it , которое ещё не изменено вызовом функции f_1() , т. е. «старое» значение. А это совсем не то, что нам нужно!

Что касается двух вызовов функции printf() (см. код функции calc() ), то они гарантируют, что значение it будет выведено на печать уже после вызова f_1() .

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

И ещё. Проблема обсуждаемого вызова функции printf() обусловлена ещё и тем, что функция f_1() обладает так называемым побочным эффектом: она изменяет значение глобальной переменной it . Такого рода побочные эффекты часто ведут к ошибкам, которые не так уж и прост обнаружить. Именно по этой причине часто рекомендуют свести использование глобальных переменных к минимуму (а, по возможности, не использовать их вовсе).

Но нам, для подсчёта количества итераций удобно счётчик сделать, всё-таки, глобальным.

Очень уж долгим оказалось отступление! Возвращаемся к нашей тестирующей программе. Непосредственно тестированием будет заниматься функция main() , имеющая следующий незатейливый код:

Мы просто берём и вычисляем приближённые значения F −1 (x) в различных точках и выясняем, сколько требуется итераций для каждого такого вычисления. Несколько первых точек специально взяты как средние арифметические между «эталонными» точками, приближённые значения F −1 (x) в которых хранятся в массиве val . Таким образом мы пытаемся в некоторой степени минимизировать влияние близости выбранных нами точек к «эталонным» на количества итераций.

Вот результат выполнения нашей программы:

Итак, что мы видим? Как и ожидалось, при увеличении аргумента функции F −1 (x), количество итераций, необходимых для нахождения её приближённого значения, возрастает. Действительно, ведь увеличение аргумента ведёт к приближению к 0 производной функции F(x) − a, чего очень «не любит» метод Ньютона.

4 итерации — это вполне нормально, на мой взгляд. А вот 12 — это уже очень много (впрочем, как мы помним, при использовании нашего компилятора, делением значения, возвращаемого rand() , отличного от RAND_MAX , на RAND_MAX , мы можем получить максимум 0,99997… (а данному числу соответствуют лишь 11 итераций), но никак не 0,99999)! Как мы видим, выход за предел 4-х итераций наступает после превышения аргументом числа 0,98.

Можно, конечно же, попытаться число итераций уменьшить, увеличив количество «эталонных» точек в самом конце интервала (0; 1). Но стоит ли усложнять функцию ради этого? Я считаю, что нет. Ведь (псевдо)случайная величина, равномерно распределённая на отрезке [0; 1], принимает значения, превышающие 0,98 или меньшие 0,02 достаточно редко. А при генерации большого количества псевдослучайных чисел, распределённых по нормальному закону, важную роль играет среднее число итераций, а не максимальное.

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

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

Функция get_norm_rand_val() будет генерировать псевдослучайные числа, распределённые по стандартному нормальному закону. По сути, она будет преобразовывать одну последовательность псевдослучайных чисел, генерируемую функцией rand() , в другую. Вот код этой функции:

Думаю, смысл кода настолько очевиден, что не требует комментариев.

Нужно иметь в виду, что, многократно вызывая функцию get_norm_rand_val() (а каким образом её ещё можно использовать?), следует не вызывать в промежутках между её вызовами функцию rand() . Такие промежуточные вызовы могут привести к тому, что числа, полученные вызовами rand() внутри get_norm_rand_val() , уже не будут распределены равномерно на отрезке [0; 1], и, как следствие, числа, генерируемые get_norm_rand_val() , не будут распределены по нормальному закону.

Итак, каким образом мы будем производить тестирование нашего генератора нормально распределённых псевдослучайных чисел? Разумеется, сначала мы сгенерируем некий набор таких чисел — выборку. Более или менее серьёзное исследование такой выборки подразумевает проверку гипотезы о нормальном распределении чисел, образующих выборку, например, с помощью критерия согласия Пирсона (χ 2 -критерия).


Но мы пойдём гораздо более простым путём: построим гистограмму относительных частот и наложим на неё график плотности распределения вероятностей. Затем качественно, «на глаз», оценим, в какой степени гистограмма «соответствует» графику.

Напомню, что плотность распределения вероятностей, — это, ни что иное, как F ‘(x).

А ещё не забудем подсчитать количество всех итераций, использовавшихся для формирования выборки, чтобы затем вычислить среднее число итераций, приходящееся на однократный вызов функции get_norm_rand_val() .

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

Модернизируем программу, описанную в предыдущем разделе.

Добавим в блок инструкций #include инструкцию, подключающую библиотеку pgraph. Теперь блок будет выглядеть так:

При построении графика плотности распределения вероятностей понадобится константа-макрос, равная приближённому значению 1 2 π . Внесём соответствующее дополнение в блок инструкций #define :

Глобальную константу it инициализируем сразу же в момент объявления:

Определение функция calc() нам больше не нужно. Заменим его определением функции get_norm_rand_val() .

Единственное изменение функции f_1() заключается в удалении из её кода 17-й строки, в которой инициализируется нулём переменная it . Теперь it после формирования выборки будет содержать общее количество итераций, потребовавшихся для генерации сразу всех чисел.

Старую версию функции main() удаляем и на её место помещаем новую.

Перед тем, как привести её код, объясню принцип построения гистограммы.

Как мы выяснили, все значения, возвращаемые функцией get_norm_rand_val() , укладываются в отрезок [−4,3; 4,3]. Но нам будет удобнее работать с промежутком [−4,5; 4,5). Разобьём его на следующие 18 полуинтервалов одинаковой длины:

Далее 10000 раз вызываем функцию get_norm_rand_val() и подсчитываем, сколько чисел, возвращаемых ею, попадает в каждый из 18-ти полуинтервалов. Для таких подсчётов создаём «массив счётчиков», состоящий из 18-ти элементов, каждый из которых соответствует «своему» полуинтервалу.

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

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

Далее наносим на холст для рисования координатные оси и для каждого полуинтервала вида [p; q) строим прямоугольный столбик, основанием которого служит отрезок [p; q]. Высота столбика равна отношению доли чисел, попавших в полуинтервал [p; q) (т. е. частному от деления количества чисел, попавших в полуинтервал, на их общее количество, т. е. на 10000; такое частное называется относительной частотой) к длине полуинтервала, равной 0,5.

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

А вот и код новой версии функции main() , в которой реализованы все описанные выше действия:

Думаю, дальнейшие пояснения излишни, поскольку комментарии приведены в самом коде.

Компиляция и запуск программы приводит к выводу на консоль следующего текста:

Итак, среднее количество итераций, приходящееся на один вызов функции get_norm_rand_val() , — 3,3262, т. е. меньше четырёх. Это очень неплохо!

Ещё одним результатом выполнения программы является появление в корневой директории исполняемого файла графического файла result.bmp, содержащего следующее изображение:

Гистограмма и график плотности распределения вероятностей

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

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

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

Генерация псевдослучайных чисел, распределённых по нормальному закону с произвольными параметрами m и σ

Если X — случайная величина, распределённая по стандартному нормальному закону, то несложно показать, что случайная величина Y, выражающаяся через X следующим образом:

распределена по нормальному закону с параметрами m и σ. Таким образом, если, например, в некоторой программе значения параметров m и σ содержатся в переменных m и sigma соответственно, то для генерации псевдослучайных чисел, нормально распределённых с параметрами m и σ, можно многократно осуществлять вызов функции get_norm_rand_val() внутри следующего выражения:

Здесь многоточиями обозначен некоторый код, каким-либо образом обрабатывающий значение выражения.

Заключение

Итак, поставленная задача успешно решена, причём её решение оказалось получить достаточно несложно. Теперь связку функций f_1() и get_norm_rand_val() можно использовать везде, где требуется генерировать псевдослучайные числа, распределённые по нормальному закону.

Rand случайная величина

Отметим, что случайные величины (или «случайно выбранные» числа) оказываются полезными не только для статистического моделирования, но и в численном анализе. Для решения различных задач были предложены так называемые методы Монте-Карло [ Кнудт Д. Искуссиво программирования для ЭВМ. Т. 2 ]. Случайные числа используются также для формирования случайных выборок, необходимых при проведении различных социологических исследований. Случайность, кроме того, есть существенная часть оптимальных стратегий в теории игр. Генерирование случайных чисел в Фортране 90 выполняется подпрограммой RANDOM_NUMBER . Обращение к подпрограмме генерирования случайного числа имеет вид

Методы Монте-Карло (ММК) – это численные методы решения математических задач с помощью моделирования случайных величин. ММК позволяют успешно решать математические задачи, обусловленные вероятностными процессами. Более того, при решении задач, не связанных с какими-либо вероятностями, можно искусственно придумать вероятностную модель (и даже не одну), позволяющую решать эти задачи. Рассмотрим вычисление определенного интеграла

При вычислении этого интеграла по формуле прямоугольников интервал [a,b] разбиваем на N одинаковых интервалов, в серединах которых вычислялись значения подынтегральной функции. Вычисляя значения функции в случайных узлах, можно получить более точный результат:

Здесь γi – случайное число, равномерно распределенное на интервале [0, 1). Погрешность вычисления интеграла ММК

, что значительно больше, чем у ранее изученных детерминированных методов.

CALL RANDOM_NUMBER( имя переменной >),

Кроме встроенной функции RANDOM _ NUMBER во входных языках имеются дополнительные подпрограммы, реализующие генерирование случайных чисел,

RANDOM и RAN , а также встроенные подпрограммы функции DRAND , DRANDM , IRAND , RAN и RAND . Все эти подпрограммы используют один и тот же алгоритм получения псевдослучайных чисел.

В CVF можно подключить библиотеку IMSLF 90 , и тогда будет доступна функция RAND , которая позволяет осуществлять заполнение случайными числами массива любой размерности. При этом инициировать датчик нет необходимости ( см. пример ). Программа, показанная в примере, демонстрирует использование функции CONST ( ) , которая позволяет вычислять значение некоторых констант . Здесь – переменная строкового типа. Проверить работу программы , осуществив несколько запусков программы, задавая различные значения K.

Дискретная случайная величина

Определение:
Случайная величина (англ. random variable) — отображение из множества элементарных исходов в множество вещественных чисел. [math] \xi\colon\Omega \to \mathbb[/math]

Содержание

Дискретная случайная величина [ править ]

Определение:
Дискретной случайной величиной (англ. discrete random variable) называется случайная величина, множество значений которой не более чем счётно, причём принятие ею каждого из значений есть случайное событие с определённой вероятностью.


Примеры [ править ]

Проще говоря, дискретные случайные величины — это величины, количество значений которых можно пересчитать. Например:

  1. Число попаданий в мишень при [math]n[/math] выстрелах. Принимаемые значения [math]0 \ldots n[/math]
  2. Количество выпавших орлов при [math]n[/math] бросков монетки. Принимаемые значения [math]0 \ldots n[/math]
  3. Число очков, выпавших при бросании игральной кости. Случайная величина принимает одно из значений — [math]\<1,2,3,4,5,6\>[/math]

Существуют также непрерывные случайные величины. Например, координаты точки попадания при выстреле.

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

Определение:
Функция распределения случайной величины (англ. cumulative distribution function (CDF)) — функция [math]F(x)[/math] , определённая на [math]\mathbb[/math] как [math]P(\xi \lt x)[/math] , т.е. выражающая вероятность того, что [math]\xi[/math] примет значение, меньшее чем [math]x[/math]

Если случайная величина [math]\xi[/math] дискретна, то есть её распределение однозначно задаётся функцией [math]\mathbb

(\xi = x_i) = p_i,\; i=1,2,\ldots[/math]

Функция распределения [math]F(x)[/math] этой случайной величины кусочно-постоянна и может быть записана как [math]F(x) = \sum\limits_

x_i \leqslant x> p_i[/math] .

Свойства функции распределения дискретной случайной величины:

  • [math]F(x_1)\leqslant F(x_2)[/math] при [math]x_1 \leqslant x_2;[/math]
  • [math]F(x)[/math] непрерывна во всех точках [math]x\in \mathbb[/math] , таких что [math]\forall i

    x \ne x_i [/math] , и имеет разрыв первого рода в точках, таких что [math]\forall i

    Примеры [ править ]

    1. Найдем функцию распределения количества попаданий в мишень. Пусть у нас есть [math]n[/math] выстрелов, вероятность попадания равна [math]p[/math] . Необходимо найти [math]F(k)[/math] . Для [math]k \leqslant 0

    F(k) = 0[/math] , так как нельзя попасть в мишень отрицательное число раз. Для [math]k \gt 0

    F(k) = \sum\limits_^<\min(n, \lceil k \rceil - 1) >\dbinomp^ (1-p)^< n - i>[/math]

  • Аналогичное решение имеет функция распределения числа выпавших орлов при броске монеты, если шанс выпадения орла — [math]p[/math] .
  • Найдем функцию распределения числа очков, выпавших при бросании игральной кости. Пусть у нас есть вероятности выпадения чисел [math]1 \ldots 6[/math] соответственно равны [math]p_ <1>\ldots p_<6>[/math] . Для [math]k \leqslant 1

    F(k) = 0[/math] , так как не может выпасть цифра меньше [math]1[/math] . Для [math]k \gt 1

    В отличие от дискретной случайной величины, непрерывная случайная величина может принять любое действительное значение из некоторого промежутка ненулевой длины, что делает невозможным её представление в виде таблицы или перечисления состояний. Поэтому ее часто явно задают через функцию распределения, например [math] F(x) = \begin 0, & x \lt 0 \\ \dfrac><9>, & 0 \leqslant x \leqslant 3\\ 1, & x \gt 3 \end[/math]

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

    Определение:
    Функция плотности распределения вероятностей (англ. Probability density function) — функция [math]f(x)[/math] , определённая на [math]\mathbb[/math] как первая производная функции распределения. [math]f(x) = F'(x)[/math]

    Свойства функции плотности вероятности:

    • Интеграл от плотности по всему пространству равен единице:

    [math]\int\limits_<\mathbb^n> f(x)\, dx = 1[/math] .

    • Плотность вероятности определена почти всюду.

    Иными словами, множество точек, для которых она не определена, имеет меру ноль.

    Для примера выше [math] f(x)=F'(x) = \begin (0)’, & x \lt 0 \\ \left(\dfrac> <9>\right)’, & 0 \leqslant x \leqslant 3\\ (1)’, & x \gt 3 \end = \begin 0, & x \lt 0 \\ \dfrac<2x><9>, & 0 \leqslant x \leqslant 3\\ 0, & x \gt 3 \end [/math]

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

    Дискретная случайная величина и функция её распределения

    Определение дискретной случайной величины и ряд её распределения

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

    Кроме дискретных случайных величин существуют также непрерывные случайные величины.

    Рассмотрим более подробно понятие случайной величины. На практике часто встречаются величины, которые могут принимать некоторые значения, но нельзя достоверно предсказать, какое именно значение каждая из них примет в рассматриваемом опыте, явлении, наблюдении. Например, число мальчиков, которые родятся в Москве в ближайший день, может быть различным. Оно может быть равным нулю (не родится ни одного мальчика: родятся все девочки или вообще не будет новорождённых), одному, двум и так далее до некоторого конечного числа n. К подобным величинам относятся: масса корнеплода сахарной свеклы на участке, дальность полёта артиллерийского снаряда, количество бракованных деталей в партии и так далее. Такие величины будем называть случайными. Они характеризуют все возможные результаты опыта или наблюдения с количественной стороны.

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

    Число значений дискретной случайной величины может быть и бесконечным, но счётным множеством. Но в любом случае их можно в каком-то порядке пронумеровать, или, более точно — установить взаимно-однозначное соответствие между значениями случайной величины и натуральными числами 1, 2, 3, . n.

    Внимание: новое, очень важное понятие теории вероятностей — закон распределения. Пусть дискретная случайная величина X может принимать n значений: . Будем считать, что они все различны (в противном случае одинаковые должны быть объединены) и расположены в возрастающем порядке. Для полной характеристики дискретной случайной величины должны быть заданы не только все её значения, но и верояности , с которыми случайная величина принимает каждое из значений, т. е. .

    Законом распределения дискретной случайной величины называется любое правило (функция, таблица) p(x), позволяющее находить вероятности всевозможных событий, связанных со случайной величиной (например, вероятность того, что она пример какое-то значение или попадёт в какой-то интервал).

    Наиболее просто и удобно закон распределения дискретной случайной величины задавать в виде следующей таблицы:

    Значение .
    Вероятность .

    Такая таблица называется рядом распределения дискретной случайной величины. В верхней строке ряда распределения перечислены в порядке возрастания все возможные значения дискретной случайной величины (иксы), а в нижней — вероятности этих значений (p).

    События являются несовместимыми и единственно возможными: они образуют полную систему событий. Поэтому сумма их вероятностей равна единице:

    Пример 1. В студенческой группе организована лотерея. Разыгрывается две вещи стоимостью по 1000 руб. и одна стоимостью по 3000 руб. Составить закон распределения суммы чистого выигрыша для студента, который приобрёл один билет за 100 руб. Всего продано 50 билетов.

    Решение. Интересующая нас случайная величина X может принимать три значения: — 100 руб. (если студент не выиграет, а фактически проиграет 100 руб., уплаченные им за билет), 900 руб. и 2900 руб. (фактический выигрыш уменьшается на 100 руб. — на стоимость билета). Первому результату благоприятствуют 47 случаев из 50, второму — 2, а третьему — один. Поэтому их вероятности таковы: P(X=-100)=47/50=0,94 , P(X=900)=2/50=0,04 , P(X=2900)=1/50=0,02 .


    Закон распределения дискретной случайной величины X имеет вид

    Сумма выигрыша -100 900 2900
    Вероятность 0,94 0,04 0,02

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

    Ряд распределения может быть построен только для дискретной случайной величины (для недискретной он не может быть построен хотя бы потому, что множество возможных значений такой случайной величины несчётно, их нельзя перечислить в верхней строке таблицы).

    Наиболее общей формой закона распределения, пригодной для всех случайных величин (как дискретных, так и недискретных), является функция распределения.

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

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

    Пример 2. Дискретная случайная величина X — число очков, выпавших при бросании игральной кости. Постоить её функцию распределения.

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

    Значение 1 2 3 4 5 6
    Вероятность 1/6 1/6 1/6 1/6 1/6 1/6

    Функция распределения F(x) имеет 6 скачков, равных по величине 1/6 (на рисунке внизу).

    Пример 3. В урне 6 белых шаров и 4 чёрных шара. Из урны вынимают 3 шара. Число белых шаров среди вынутых шаров — дискретная случайная величина X . Составить соответствующий ей закон распределения.

    Решение. Дискретная случайная величина X может принимать значения 0, 1, 2, 3. Соответствующие им вероятности проще всего вычислисть по правилу умножения вероятностей. Получаем следующий закон распределения дискретной случайной величины:

    Значение 1 2 3
    Вероятность 1/30 3/10 1/2 1/6

    Пример 4. Составить закон распределения дискретной случайной величины — числа попаданий в цель при четырёх выстрелах, если вероятность попадания при одном выстреле равна 0,1.

    Решение. Дискретная случайная величина X может принимать пять различных значений: 1, 2, 3, 4, 5. Соответствующие им вероятности найдём по формуле Бернулли . При

    Следовательно, закон распределения дискретной случайной величины X имеет вид

    Число попаданий 1 2 3 4
    Вероятность 0,6561 0,2916 0,0486 0,0036 0,0001

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

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

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

    Чтобы вычислить функцию распределения дискретной случайной величины F(х), требуется сложить вероятности всех тех значений, которые меньше или равны граничному значению х.

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

    Длительность брака (лет) Число Вероятность F(x)
    10 0,002 0,002
    1 80 0,013 0,015
    2 177 0,029 0,044
    3 209 0,035 0,079
    4 307 0,051 0,130
    5 335 0,056 0,186
    6 358 0,060 0,246
    7 413 0,069 0,314
    8 432 0,072 0,386
    9 402 0,067 0,453
    10 и более 3287 0,547 1,000
    Всего 6010 1

    Решение. Вероятности вычислены путём деления числа соответствующих расторгнутых браков на общее число 6010. Вероятность того, что очередной расторгнутый брак был длительностью в 5 лет, равна 0,056. Вероятность, что длительность очередного расторгнутого брака меньше или равна 5 годам, равна 0,186. Мы получили её, прибавив к значению F(x) для браков с длительностью по 4 года включительно вероятность для браков с длительностью в 5 лет.

    Связь закона распределения дискретной случайной величины с математическим ожиданием и дисперсией

    Часто не все значения дискретной случайной величины известны, но известны некоторые значения или вероятности из ряда, а также математическое ожидание и (или) дисперсия случайной величины, которым посвящён отдельный урок.

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

    Математическое ожидание дискретной случайной величины — сумма произведений всех возможных её значений на вероятности этих значений:

    Формула дсперсии дискретной случайной величины по определению:

    Часто для вычислений более удобна следующая формула дисперсии:

    Пример 6. Дискретная случайная величина X может принимать только два значения. Меньшее значение она принимает с вероятностью p = 0,6 . Найти закон распределения дискретной случайной величины X , если известно, что её математическое ожидание и дисперсия .

    Решение. Вероятность того, что случайная величина примет бОльшее значение x 2 , равна 1 − 0,6 = 4 . Используя формулу (1) математического ожидания, составим уравнение, в котором неизвестные — значения нашей дискретной случайной величины:

    Используя формулу (2) дисперсии, составим другое уравнение, в котором неизвестные — также значения дискретной случайной величины:

    Систему из двух полученных уравнений

    решаем методом подстановки. Из первого уравнения получаем

    Подставив это выражение во второе уравнение, после несложных преобразований получим квадратное уравнение

    которое имеет два корня: 7/5 и −1 . Первый корень не отвечает условиям задачи, так как x 2 1 . Таким образом, значения, которые может принимать дискретная случайная величина X по условиям нашего примера, равны x 1 = −1 и x 2 = 2 .

    Закон распределения дискретной случайной величины X можем представить в виде следующей таблицы:

    Значение −1 2
    Вероятность 0,6 0,4

    Пример 7. Дискретная случайная величина X может принимать только два значения. Большее значение 3 она принимает с вероятностью p = 0,4 . Кроме того, известна дисперсия дискретной случайной величины: D(X) = 6 Найти закон распределения дискретной случайной величины X .

    Решение. В этом примере вероятности равны p 1 = 0,6 и p 2 = 0,4 . Математическое ожидание обозначим μ . Из формул математического ожидания и дисперсии (1) и (2) получим систему уравнений

    Возводя первое уравнение в квадрат и приравнивая к μ² выражения из обоих уравнений, получим квадратное уравнение

    Корни этого уравнения 8 и −2 . По условию задачи в качестве значения дискретной случайной величины годится только корень −2 .

    Получаем закон распределения дискретной случайной величины X :

    Значение −2 3
    Вероятность 0,6 0,4

    Пример 8. Дискретная случайная величина X может принимать только два значения: 1 и 6. Известна дисперсия дискретной случайной величины: D(X) = 6 Найти закон распределения дискретной случайной величины X .


    Решение. Математическое ожидание обозначим μ . Получим закон распределения дискретной случайной величины, в котором пока неизвестны вероятности:

    Значение 1 6
    Вероятность p 1−p

    Из формул математического ожидания и дисперсии (1) и (2) получим систему уравнений

    Возводя первое уравнение в квадрат и приравнивая к μ² выражения из обоих уравнений, получим квадратное уравнение

    имеющее корни 0,4 и 0,6 .

    Таким образом, возможны два закона распределения дискретной случайной величины X :

    Значение 1 6
    Вероятность 0,4 0,6
    Значение 1 6
    Вероятность 0,6 0,4

    Чтобы задание было сформулировано более полно, необходимо указать какое-либо дополнительное условие, например, что меньшему значению дискретной случайной величины соответствует меньшее, или, наоборот, большее значение вероятности.

    Случайные числа в стандартном си

    Псевдослучайные числа

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

    С примерами использования случайных чисел вы сталкиваетесь повсюду. Псевдослучайные числа используются в дизайне и графике, для генерации уровней в компьютерных играх и симулирования ИИ. Наборы случайных чисел используются в математических алгоритмах (см. Методы Монте-Карло).

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

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

    Посмотрим стандартный генератор.

    Для начала необходимо инициализировать генератор случайных чисел (ГСЧ, или RNG — random number generator), задать зерно – seed, на основе которого в дальнейшем будет происходить генерация. Важно, что для одного и того же начального значения генератор будет возвращать одни и те же числа.

    Присваиваем переменной r случайное значение

    Значение будет лежать в диапазоне от 0 до RAND_MAX.

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

    Функция getpid библиотеки process.h возвращает идентификатор процесса (можно также использовать getpid, не POSIX версию функции).

    Центральная Предельная Теорема

    Очень важно сразу напомнить или познакомить с центральной предельной теоремой. Неформальное определение – распределение суммы слабо зависимых случайных величин стремится к нормальному. Пальцеобразное объяснение: если сложить несколько случайных величин, независимо от их распределения, то распределение суммы будет нормальным. Часто можно увидеть такой код

    Таким образом автор пытается сделать случайное число «более» случайным, но получает менее случайное число.

    Генерация случайных чисел на заданном отрезке

    Во-первых, получим случайное число от нуля до единицы:

    Для получения числа в отрезке от нуля до N умножим N на случайное число от нуля до единицы. Для получения случайного числа от M До N, сдвинем полученное число на M.

    Для получения целого числа, будем брать остаток от деления на длину интервала. Но остаток от деления будет возвращать число на единицу меньше, чем наш интервал, поэтому увеличим его на единицу:

    Пример использования случайных чисел для вычисления интеграла. Пусть у нас есть некоторая гладкая функция от одной переменной. Ограничим её квадратом от a до b, и от 0 до некоторой точки, которая заведомо больше нашей функции.

    Будем случайным образом кидать точки на нашем квадрате. Если они лежат выше функции (на рисунке изображены зелёными крестиками), то отнесём их к первой группе A, если ниже функции (на рисунке красные), то отнесём их ко второй группе B. Положение точек случайное и распределено равномерно (т.к. стандартный генератор даёт равномерное распределение. Этот простой пример, кстати, уже показывает, насколько важно знать свойства ГСЧ). Тогда отношение красных точек к общему числу точек будет равно отношению площади под графиком к общей площади. А общая площадь – это квадрат (b-a) на q.

    Отношение зелёного к красному будет равно отношению площади над графиком к площади под графиком.» src=»https://learnc.info/images/c_random_integral.png» alt=»Всё, что случайно попадает выше нашей функции — зелёное, всё что ниже — красное.
    Отношение зелёного к красному будет равно отношению площади над графиком к площади под графиком.»/> Всё, что случайно попадает выше нашей функции — зелёное, всё что ниже — красное.
    Отношение зелёного к красному будет равно отношению площади над графиком к площади под графиком.

    Применим наши выкладки – найдём интеграл функции x^2 на отрезке от 0 до двух двумя способами.

    Поиграйте со значением ROUNDS, измените его и посмотрите, как меняется точность вычислений.

    Генерация истинно случайных чисел

    Для генерации настоящих случайных чисел используют генераторы, основанные на каких-то случайных физических процессах. Например, на тепловых шумах, на подсчёте числа делений радиоактивного вещества, на атмосферных шумах и т.п. Недостаток таких генераторов – низкая скорость работы (количество сгенерированных чисел в секунду) ; конечно, такие генераторы обычно являются отдельным устройством.

    Rand случайная величина

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

    • — грань с одной точкой;
    • — грань с двумя точками;
    • .
    • — грань с шестью точками.

    Множество всех граней образует пространство элементарных событий , подмножества которого называются случайными событиями [1] . В случае однократного подбрасывания игровой кости примерами событий являются

    • выпадение грани с нечётным количеством точек, то есть событие — это выпадение грани с одной точкой или грани с тремя точками, или грани с пятью точками). Математически событие записывается как множество, содержащее элементарные события: , и . Таким образом, ;
    • выпадение грани с чётным количеством точек, то есть событие — это выпадение грани с двумя точками или грани с четырьмя точками, или грани с шестью точками. Математически событие записывается как множество, содержащее элементарные события: , и . Таким образом, ;

    Алгебра событий

    Множество случайных событий образует алгебру событий [2] , если выполняются следующие условия:

    1. содержит пустое множество .
    2. Если событие принадлежит , то и его дополнение принадлежит . С помощью кванторов это записывается так: : .
    3. Если и принадлежат , то их объединение также принадлежит . С помощью кванторов это записывается следующим образом ( ) ( ) .

    Если вместо третьего условия удовлетворяет другому условию: объединение счётного подсемейства из также принадлежит , то множество случайных событий образует σ-алгебру событий.

    -алгебра событий является частным случаем σ-алгебры множеств.


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

    Вероятность

    Если каждому элементарному событию поставить в соответствие число , для которого выполняется условие:

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

    Рассмотрим пример определения вероятности различных случайных событий. Например, если событие является пустым множеством, то его вероятность равна нулю [3] :

    Если событием является пространство элементарных событий, то его вероятность равна единице:

    Вероятность события (подмножества пространства элементарных событий) равна сумме вероятностей тех элементарных событий, которые включает в себя рассматриваемое событие.

    Определение случайной величины

    Случайной величиной называется функция , измеримая относительно и борелевской σ-алгебры на [4] .

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

    Примеры

    • Пусть случайная величина имеет дискретное равномерное распределение, то есть Тогда её математическое ожидание

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

    • Пусть случайная величина имеет непрерывное равномерное распределение на интервале , где . Тогда её плотность имеет вид и математическое ожидание равно

    .

    • Пусть случайная величина имеет стандартное распределение Коши. Тогда

    ,

    то есть математическое ожидание не определено.

    Классификация

    Случайные величины могут принимать дискретные, непрерывные и дискретно-непрерывные значения. Соответственно случайные величины классифицируют на дискретные, непрерывные и дискретно-непрерывные (смешанные).

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

    • Пример смешанной случайной величины — время ожидания при переходе через автомобильную дорогу в городе на нерегулируемом перекрёстке.
    • В бесконечных схемах (дискретных или непрерывных) уже изначально элементарные исходы удобно описывать количественно. Например, номера градаций типов несчастных случаев при анализе ДТП; время безотказной работы прибора при контроле качества и т. п.
    • Числовые значения, описывающие результаты опытов, могут характеризовать не обязательно отдельные элементарные исходы в схеме испытаний, но и соответствовать каким-то более сложным событиям.

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

    • Например, координаты (абсцисса, ордината) какого-то разрыва снаряда при стрельбе по наземной цели; метрические размеры (длина, ширина и т. д.) детали при контроле качества; результаты медобследования (температура, давление, пульс и пр.) при диагностике больного; данные переписи населения (по возрасту, полу, достатку и пр.).

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

    Методы описания

    Частично задать случайную величину, описав этим все её вероятностные свойства как отдельной случайной величины, можно с помощью функции распределения, плотности вероятности и характеристической функции, определяя вероятности возможных её значений. Функция распределения F(x) является вероятностью того, что значения случайной величины меньше вещественного числа x. Из этого определения следует, что вероятность попадания значения случайной величины в интервал [a, b) равна F(b)-F(a). Преимущество использования функции распределения заключается в том, что с её помощью удаётся достичь единообразного математического описания дискретных, непрерывных и дискретно-непрерывных случайных величин. Тем не менее, существуют разные случайные величины, имеющие одинаковые функции распределения.

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

    Биноминальный закон распределения описывает случайные величины, значения которых определяют количество «успехов» и «неудач» при повторении опыта N раз. В каждом опыте «успех» может наступить с вероятностью p, «неудача» — с вероятностью q=1-p. Закон распределения в этом случае определяется формулой Бернулли:

    При стремлении к бесконечности произведение np остаётся равной константе , а закон распределения сходится к закону Пуассона, который описывается следующей формулой:

    Простейшие обобщения

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

    • Измеримая функция называется n-мерным случайным вектором (относительно борелевской -алгебры на ).
    • Измеримая функция называется n-мерным комплексным случайным вектором (также относительно соответствующей борелевской -алгебры).
    • Измеримая функция, отображающая вероятностное пространство в пространство подмножеств некоторого (конечного) множества, называется (конечным) случайным множеством.

    Урок №71. Генерация случайных чисел

    Обновл. 30 Апр 2020 |

    Возможность генерировать случайные числа очень полезна в некоторых видах программ, в частности в играх, программах научного или статистического моделирования. Возьмём, к примеру, игры без рандомных (или ещё «случайных») событий — монстры всегда будут атаковать вас одинаково, вы всегда будете находить одни и те же предметы/артефакты, макеты темниц и подземелий никогда не будут меняться и т.д., в общем, сюжет такой игры не очень и вряд ли вы долго продержитесь.

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

    Так как же генерировать случайные числа? В реальной жизни мы часто бросаем монетку (орёл/решка), кости или перетасовываем карты. Эти события включают в себя так много физических переменных (например, сила тяжести, трение, сопротивление воздуха и т.д.), что они становятся почти невозможными для прогнозирования/контроля и выдают результаты, которые во всех смыслах являются случайными.

    Однако компьютеры не предназначены для использования физических переменных — они не могут бросить монетку, кости или перетасовать реальные карты. Компьютеры живут в контролируемом электрическом мире, где есть только два значения (true и false), чего-то среднего между ними нет. По своей природе компьютеры предназначены для получения прогнозируемых результатов. Когда мы говорим компьютеру посчитать, сколько будет 2 + 2 , мы всегда хотим, чтобы ответом было 4 (не 3 и не 5 ).

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

    Генератор псевдослучайных чисел (или ещё «ГПСЧ») — это программа, которая принимает стартовое/начальное значение и выполняет с ним определённые математические операции, чтобы конвертировать его в другое число, которое совсем не связанное со стартовым. Затем программа использует новое сгенерированное значение и выполняет с ним те же математические операции, что и с начальным числом, чтобы конвертировать его в ещё в одно новое число — третье, которое не связано ни с первым, ни со вторым. Применяя этот алгоритм к последнему сгенерированному значению, программа может генерировать целый ряд новых чисел, которые будут казаться случайными (при условии, что алгоритм будет достаточно сложным).

    На самом деле, написать простой ГПСЧ не так уж и сложно. Вот небольшая программа, которая генерирует 100 рандомных чисел:

    Результат выполнения программы выше:

    18256 4675 32406 6217 27484
    975 28066 13525 25960 2907
    12974 26465 13684 10471 19898
    12269 23424 23667 16070 3705
    22412 9727 1490 773 10648
    1419 8926 3473 20900 31511
    5610 11805 20400 1699 24310
    25769 9148 10287 32258 12597
    19912 24507 29454 5057 19924
    11591 15898 3149 9184 4307
    24358 6873 20460 2655 22066
    16229 20984 6635 9022 31217
    10756 16247 17994 19069 22544
    31491 16214 12553 23580 19599
    3682 11669 13864 13339 13166
    16417 26164 12711 11898 26797
    27712 17715 32646 10041 18508
    28351 9874 31685 31320 11851
    9118 26193 612 983 30378
    26333 24688 28515 8118 32105


    Каждое число кажется случайным по отношению к предыдущему. Но, поскольку этот алгоритм довольно примитивен, то в этом и его недостаток.

    Функции srand() и rand()

    Языки C и C++ имеют свои собственные встроенные генераторы случайных чисел. Они реализован в двух отдельных функциях, которые находятся в заголовочном файле cstdlib:

    Функция srand() устанавливает передаваемое пользователем значение в качестве стартового. srand() следует вызывать только один раз: в начале программы (обычно в верхней части функции main()).

    Функция rand() генерирует следующее случайное число в последовательности. Оно будет находиться в диапазоне от 0 до RAND_MAX (константа в cstdlib, значением которой является 32 767).

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

    Результат выполнения программы выше:

    14867 24680 8872 25432 21865
    17285 18997 10570 16397 30572
    22339 31508 1553 124 779
    6687 23563 5754 25989 16527
    19808 10702 13777 28696 8131
    18671 27093 8979 4088 31260
    31016 5073 19422 23885 18222
    3631 19884 10857 30853 32618
    31867 24505 14240 14389 13829
    13469 11442 5385 9644 9341
    11470 189 3262 9731 25676
    1366 24567 25223 110 24352
    24135 459 7236 17918 1238
    24041 29900 24830 1094 13193
    10334 6192 6968 8791 1351
    14521 31249 4533 11189 7971
    5118 19884 1747 23543 309
    28713 24884 1678 22142 27238
    6261 12836 5618 17062 13342
    14638 7427 23077 25546 21229

    Стартовое число и последовательности в ГПСЧ

    Если вы запустите программу выше (генерация случайных чисел) нескольких раз, то заметите, что в результатах всегда находятся одни и те же числа! Это означает, что, хотя каждое число в последовательности кажется случайным относительно предыдущего, вся последовательность не является случайной вообще! А это, в свою очередь, означает, что наша программа полностью предсказуема (одни и те же значения ввода приводят к одним и тем же значениям вывода). Бывают случаи, когда это может быть полезно или даже желательно (например, если вы хотите, чтобы научная симуляция повторялась, или вы пытаетесь отлаживать причины сбоя вашего генератора рандомных подземелий).

    Но, в большинстве случаев, это не совсем то, что нам нужно. Если вы пишете игру типа Hi-Lo (где у пользователя есть 10 попыток угадать число, а компьютер говорит ему, насколько его предположения близки или далеки от реального числа), вы бы не хотели, чтобы программа выбирала одни и те же числа каждый раз. Поэтому давайте более подробно рассмотрим, почему это происходит и как это можно исправить.

    Помните, что каждое новое число в последовательности ГПСЧ генерируется исходя из предыдущего определённым способом. Таким образом, при любом начальном числе ГПСЧ всегда будет генерировать одну и ту ​​же последовательность! В программе выше последовательность чисел всегда одинакова, так как стартовое число всегда равно 4 541.

    Чтобы это исправить нам нужен способ выбрать стартовое число, которое не будет фиксированным значением. Первое, что приходит на ум — использовать рандомное число! Это хорошая мысль, но если нам нужно случайное число для генерации случайных чисел, то это какой-то замкнутый круг, вам не кажется? Оказывается, нам не обязательно использовать случайное стартовое число — нам просто нужно выбрать что-то, что будет меняться каждый раз при новом запуске программы. Затем мы сможем использовать наш ГПСЧ для генерации уникальной последовательности рандомных чисел исходя из уникального стартового числа.

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

    В языке C есть функция time(), которая возвращает в качестве времени общее количество секунд от полуночи 1 января 1970 года. Чтобы использовать эту функцию, нам просто нужно подключить заголовочный файл ctime, а затем инициализировать функцию srand() вызовом функции time(0).

    Вот та же программа, что выше, но уже с использованием функции time() в качестве стартового числа:

    Теперь наша программа будет генерировать разные последовательности случайных чисел! Попробуйте сами.

    Генерация случайных чисел в определённом диапазоне

    В большинстве случаев нам не нужны рандомные числа между 0 и RAND_MAX — нам нужны числа между двумя другими значениями: min и max. Например, если нам нужно сымитировать бросок кубика, то диапазон значений будет невелик: от 1 до 6.

    Вот небольшая функция, которая конвертирует результат функции rand() в нужный нам диапазон значений:

    Чтобы сымитировать бросок кубика — вызываем функцию getRandomNumber(1, 6) .

    Какой ГПСЧ является хорошим?

    Как мы уже говорили, генератор случайных чисел, который мы написали выше, не является очень хорошим. Сейчас рассмотрим почему.

    Хороший ГПСЧ должен иметь ряд свойств:

    Свойство №1: ГПСЧ должен генерировать каждое новое число с примерно одинаковой вероятностью. Это называется равномерностью распределения. Если некоторые числа генерируются чаще, чем другие, то результат программы, использующей ГПСЧ, будет предсказуем!

    Например, предположим, вы пытаетесь написать генератор случайных предметов для игры. Вы выбираете случайное число от 1 до 10, и, если результатом будет 10, игрок получит крутой предмет вместо среднего. Шансы будут 1 к 10. Но, если ваш ГПСЧ не равномерно генерирует числа, например, 10-тки генерируются чаще, чем должны, то ваши игроки будут получать более редкие предметы чаще, чем предполагалось, и сложность + интерес к такой игре автоматически уменьшается.

    Создать ГПСЧ, который бы генерировал равномерные результаты — сложно, и это одна из главных причин, по которым ГПСЧ, который мы написали в начале этого урока, не является очень хорошим.

    Свойство №2: Метод, с помощью которого генерируется следующее число в последовательности, не должен быть очевиден или предсказуем. Например, рассмотрим следующий алгоритм ГПСЧ: num = num + 1 . У него есть равномерность распределения рандомных чисел, но это не спасает его от примитивности и предсказуемости!

    Свойство №3: ГПСЧ должен иметь хорошее диапазонное распределение чисел. Это означает, что маленькие, средние и большие числа должны возвращаться случайным образом. ГПСЧ, который возвращает все маленькие числа, а затем все большие — предсказуем и приведёт к предсказуемым результатам.

    Свойство №4: Все ГПСЧ являются циклическими, т.е. в какой-то момент последовательность генерируемых чисел начнёт повторяться. Как упоминалось ранее, ГПСЧ являются детерминированными, и с одним значением ввода мы получим одно и то же значение вывода. Подумайте, что произойдёт, когда ГПСЧ сгенерирует число, которое уже ранее было сгенерировано. С этого момента начнётся дублирование последовательности чисел между первым и последующим появлением этого числа. Длина этой последовательности называется периодом.

    Например, вот представлены первые 100 чисел, сгенерированные ГПСЧ с плохой периодичностью:

    112 9 130 97 64
    31 152 119 86 53
    20 141 108 75 42
    9 130 97 64 31
    152 119 86 53 20
    141 108 75 42 9
    130 97 64 31 152
    119 86 53 20 141
    108 75 42 9 130
    97 64 31 152 119
    86 53 20 141 108
    75 42 9 130 97
    64 31 152 119 86
    53 20 141 108 75
    42 9 130 97 64
    31 152 119 86 53
    20 141 108 75 42
    9 130 97 64 31
    152 119 86 53 20
    141 108 75 42 9

    Заметили, что он сгенерировал 9 как второе число, а затем как 16-е. ГПСЧ застревает, генерируя последовательность между этими двумя 9-ми: 9-130-97-64-31-152-119-86-53-20-141-108-75-42- (повтор).

    Хороший ГПСЧ должен иметь длинный период для всех стартовых чисел. Разработка алгоритма, удовлетворяющее это свойство, может быть чрезвычайно сложной — большинство ГПСЧ имеют длинные периоды для одних начальных чисел и короткие для других. Если пользователь выбрал начальное число, которое имеет короткий период, то и результаты будут соответствующие.

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

    Почему rand() является посредственным ГПСЧ?

    Алгоритм, используемый для реализации rand(), может варьироваться в разных компиляторах, и, соответственно, результаты также могут быть разными. В большинстве реализаций rand() используется Линейный Конгруэнтный Метод (или ещё «ЛКМ»). Если вы посмотрите на первый пример в этом уроке, то заметите, что там, на самом деле, используется ЛКМ, хоть и с намеренно подобранными плохими константами.

    Одним из основных недостатков функции rand() является то, что RAND_MAX обычно устанавливается как 32 767 (15-битное значение). Это означает, что если вы захотите сгенерировать числа в более широком диапазоне (например, 32-битные целые числа), то функция rand() не подойдёт. Кроме того, она не подойдёт, если вы захотите сгенерировать случайные числа типа с плавающей запятой (например, между 0.0 и 1.0), что часто используется в статистическом моделировании. Наконец, функция rand() имеет относительно короткий период по сравнению с другими алгоритмами.

    Тем не менее, этот алгоритм отлично подходит для изучения программирования и для программ, в которых высококлассный ГПСЧ не является необходимостью.

    Для приложений, где требуется высококлассный ГПСЧ, рекомендуется использовать алгоритм Вихрь Мерсенна (англ. «Mersenne Twister»), который генерирует отличные результаты и относительно прост в использовании.

    Отладка программ, использующих случайные числа

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

    Поэтому, проводя отладку программы, полезно использовать в качестве стартового числа (с использованием функции srand()) определённое значение (например, 0), которое вызовет ошибочное поведение программы. Это будет гарантировать, что наша программа каждый раз генерирует одни и те же результаты (что значительно облегчит процесс отладки). После того, как мы найдём и исправим ошибку, мы сможем снова использовать системные часы для генерации рандомных результатов.

    Рандомные числа в C++11

    В C++11 добавили тонну нового функционала для генерации случайных чисел, включая алгоритм Вихрь Мерсенна, а также разные виды генераторов случайных чисел (например: равномерные, генератор Poisson и т.д.). Доступ к ним осуществляется через подключение заголовочного файла random. Вот пример генерации случайных чисел в C++11 с использованием Вихря Мерсенна:

    Оглавление

    2.Генерация случайных чисел в matlab. 4

    3.Моделирование распределений случайных величин в matlab. 9


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

    3.4Пуассоновское распределение. 12

    3.6Нормальное распределение. 15

    4.Метод Монте-Карло 17

    5.Использование пакета Simulink для моделирования случайных чисел. 20

    6.Программа в matlab 22

    7.Список литературы. 25

    1.Кетков Ю. Л., Кетков А. Ю., Шульц М. М. “MATLAB 7: программирование, численные методы”, СПБ. БХВ-Петербург, 2005 — 752 с. 25

    2.К. Чен, П. Джиблин, А. Ирвинг, “MATLAB в математических исследованиях”, изд. “Мир”, 2001 — 353 c. 25

    3.С. П. Иглин, “Теория вероятностей и математическая статистика на базе MATLAB”,НТУ “ХПИ”, 2006—612 c. 25

    4.С. В. Поршнев, “Компьютерное моделирование физических процессов в пакете MATLAB”,изд. ”Горячая линия-телеком”,2003—592 с. 25

    5.Н. Н. Снетков, “Имитационное моделирование экономических процессов”, изд. центр ЕАОИ, 2008. – 228 с. 25

    Введение.

    В любых сферах деятельности мы всегда сталкиваемся с различного рода случайностями. Они встречаются и в технике, и в экономике, и даже в обычной повседневной жизни. Из-за этого мы никогда не можем точно описать протекание какого либо процесса, работу какого либо устройства. Но для того, чтобы расчеты были хотя бы приближены к реальности, нужно то, что будет учитывать воздействие случайных факторов. Для этого мы и вводим понятие случайной величины. Это величина, которая принимает в результате опыта одно из множества значений, причём появление того или иного значения этой величины до её измерения нельзя точно предсказать.

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

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

    Генерация случайных чисел в matlab.

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

    Поэтому вместо чисто случайных чисел стали использовать псевдослучайные числа, генерируемые с помощью той или иной программы. Случайность при таком подходе заменяется непредсказуемостью для неосведомленного пользователя: наблюдая некоторое время «хорошую» последовательность псевдослучайных чисел, он не в состоянии предсказать, каким будет следующий член этой последовательности, хотя на самом деле все они вычисляются по довольно простой формуле. Прежде чем использовать для решения задач тот или иной датчик случайных чисел (табличный, физический или программный), его подвергают разнообразным тестам: на равномерность (или согласие с другим предписанным законом распределения), на независимость и т. д. [2]

    Функция rand используется для генерации псевдослучайных чисел, равномерно распределенных в интервале от 2 -53 до 1-2 -53 (примерно — [0;1]). Эти числа называются псевдослучайными, так как они выглядят случайными последовательностями, но существует метод их воспроизводства. Теоретически функция rand позволяет без повторений сгенерировать 21492 псевдослучайных чисел.[1] Обратившись к этой функции без аргумента, мы получаем очередное случайное число:

    Последовательности генерируются детерминированным алгоритмом, но ему можно дать “затравку” [2] , которая позволит породить конкретную последовательность:

    rand(‘seed’,13)-устанавливает в качестве “затравки” 13-ое число.

    Если у функции задается один скалярный аргумент, то функция rand(n) возвращает квадратную матрицу n-го порядка, элементами которой являются случайные числа из интервала [0;1] :

    Функция rand(n,m) возвращает прямоугольную матрицу размерности

    n x m со случайными числами:

    0.035711678574190 0.933993247757551 0.757740130578333

    0.849129305868777 0.678735154857773 0.743132468124916

    Обращение rand (size (А)) позволяет сгенерировать матрицу случайных чисел, размерность которой совпадает с размерностью массива А:

    0.392227019534168 0.171186687811562 0.031832846377421

    0.655477890177557 0.706046088019609 0.276922984960890

    Для перехода от чисто дробных случайных чисел к случайным числам из произвольного диапазона [а; b] достаточно воспользоваться преобразованием а+(b-a)*rand:

    В большинстве алгоритмических языков существует средство для возмущения датчика случайных чисел, в С и Pascal — это функция или процедура randomize. Она позволяет избежать повторения результатов при многократных запусках программ, использующих датчик случайных чисел. В системе MATLAB тоже имеется аналогичное средство:

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

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

    • среднее значение случайной величины равно 0;

    • дисперсия σ 2 =1;

    • средняя квадратическая ошибка (стандарт) σ=1.

    Форматы обращения к функции randn такие же, как и к функции rand. Если потребуются случайные числа, распределенные по нормальному закону со смещенным центром m и заданной дисперсией s, то достаточно воспользоваться преобразованием m+sqrt (s) *randn.

    Кроме функций rand и randn, MATLAB предлагает и другие функции, с помощью которых можно создавать различные случайные объекты. [1] Для генерации случайных перестановок из целых чисел 1, 2, . п используется функция randperm(n):

    Функции MATLAB’a ceil, fix, floor и round, вместе с rand по­рождают случайные целые числа. Здесь ceil(x) есть наименьшее целое > х, floor(x) — это наибольшее целое > х = rand(n,l); floor((k+l)*x)

    >> b = rand(5,1); floor((5+1)*b)

    Но мы можем получить и столбец из n чисел, принимающих с рав­ной вероятностью целые значения 1. ,k (т.е. целые значения из замкнутого интервала [l,k]), выполнив

    Команда round используется немного по-другому. Например.

    порождает n чисел, которые принимают значения 0,1. ,10 с не­равными вероятностями. [2]

    Дискретная случайная величина

    Определение:
    Случайная величина (англ. random variable) — отображение из множества элементарных исходов в множество вещественных чисел. [math] \xi\colon\Omega \to \mathbb[/math]

    Содержание

    Дискретная случайная величина [ править ]

    Определение:
    Дискретной случайной величиной (англ. discrete random variable) называется случайная величина, множество значений которой не более чем счётно, причём принятие ею каждого из значений есть случайное событие с определённой вероятностью.

    Примеры [ править ]

    Проще говоря, дискретные случайные величины — это величины, количество значений которых можно пересчитать. Например:

    1. Число попаданий в мишень при [math]n[/math] выстрелах. Принимаемые значения [math]0 \ldots n[/math]
    2. Количество выпавших орлов при [math]n[/math] бросков монетки. Принимаемые значения [math]0 \ldots n[/math]
    3. Число очков, выпавших при бросании игральной кости. Случайная величина принимает одно из значений — [math]\<1,2,3,4,5,6\>[/math]

    Существуют также непрерывные случайные величины. Например, координаты точки попадания при выстреле.

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

    Определение:
    Функция распределения случайной величины (англ. cumulative distribution function (CDF)) — функция [math]F(x)[/math] , определённая на [math]\mathbb[/math] как [math]P(\xi \lt x)[/math] , т.е. выражающая вероятность того, что [math]\xi[/math] примет значение, меньшее чем [math]x[/math]

    Если случайная величина [math]\xi[/math] дискретна, то есть её распределение однозначно задаётся функцией [math]\mathbb

    (\xi = x_i) = p_i,\; i=1,2,\ldots[/math]

    Функция распределения [math]F(x)[/math] этой случайной величины кусочно-постоянна и может быть записана как [math]F(x) = \sum\limits_

    x_i \leqslant x> p_i[/math] .

    Свойства функции распределения дискретной случайной величины:

    • [math]F(x_1)\leqslant F(x_2)[/math] при [math]x_1 \leqslant x_2;[/math]
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL