Метод монте карло геометрический выделение главной части. Использование метода монте-карло для расчета риска. Пример. Вычисление числа π методом Монте-Карло

Лекция 5.

Метод Монте-Карло

Тема 3. Процессы массового обслуживания в экономических системах

1. Вводные замечания. 1

2. Общая схема метода Монте-Карло. 2

3. Пример расчета системы массового обслуживания методом Монте-Карло. 4

Контрольные вопросы.. 5

1. Вводные замечания

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

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

Термин "метод Монте-Карло" (предложенный Дж. Фон Нейманом и в 1940-х) относится к моделированию процессов с использованием генератора случайных чисел. Термин Монте-Карло (город, широко известный своими казино) произошел от того факта, что "число шансов" (методы моделирования Монте-Карло) было использовано с целью нахождения интегралов от сложных уравнений при разработке первых ядерных бомб (интегралы квантовой механики). С помощью формирования больших выборок случайных чисел из, например, нескольких распределений, интегралы этих (сложных) распределений могут быть аппроксимированы из (сгенерированных) данных.

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

Отечественные работы по методу Монте-Карло появились в гг. За два десятилетия накопилась обширная библиография по методу Монте-Карло, которая насчитывает более 2000 названий. При этом даже беглый просмотр названий работ позволяет сделать вывод о применимости методы Монте-Карло для решения прикладных задач из большого числа областей науки и техники.

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

Метод Монте-Карло оказал и продолжает оказывать существенное влияние на развитие метода вычислительной математики (например, развитие методов численного интегрирования) и при решении многих задач успешно сочетается с другими вычислительными методами и дополняет их. Его применение оправдано в первую очередь в тех задачах, которые допускают теоретико-вероятностное описание. Это объясняется как естественностью получения ответа с некоторой заданной вероятностью в задачах с вероятным содержанием, так и существенным упрощением процедуры решения. Трудность решения той или иной задачи на ЭВМ определятся в значительной мере трудностью переложения ее на «язык» машины. Создание языков автоматического программирования существенно упростило один из этапов этой работы. Наиболее сложными этапами поэтому в настоящее время являются: математическое описание исследуемого явления, необходимые упрощения задачи, выбор подходящего численного метода, исследование его погрешности и запись алгоритма. В тех случаях, когда имеется теоретико-вероятностное описание задачи, использование метода Монте-Карло может существенно упростить упомянутые промежуточные этапы. Впрочем, как будет следовать из дальнейшего, во многих случаях полезно и для задач строго детерминированных строить вероятностную модель (рандомизовать исходную задачу) с тем, чтобы далее использовать метод Монте-Карло.

2. Общая схема метода Монте-Карло

Предположим, что нам требуется вычислить некоторую неизвестную величину m, и мы хотим сделать это, рассматривая случайную величину такую, что ее математическое ожидание М, = m. Пусть при этом дисперсия данной случайной величины D = b.

Рассмотрим N случайных независимых величин,,…, распределения которых совпадают с распределением рассматриваемой случайной величины ξ..gif" width="247" height="48">

Последнее соотношение можно переписать в виде

Полученная формула дает метод расчета т и оценку погрешности этого метода.

Сущность применения метода Монте-Карло заключается в определении результатов на основании статистики, полу чаемой к моменту принятия некоторого решения.

Например. Пусть Е1 и Е2 - две единственно возможные реализации некоторого случайного процесса, причем p1 - - вероятность исхода Е1, а р2 = 1 – p1 - вероятность исхода Е2. Чтобы определить, какое из двух событий, e1 или Е2, имеет место в данном случае, возьмем в интервале между 0 и 1 случайное число и, равномерно распределенное в интервале (0, 1), и произведем испытание. Исход Е1 будет иметь место, если , а исход Е2 - в противном случае.

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

Для получения случайных чисел на ЭВМ используются способы генерирования, которые обычно основаны на много кратном повторении некоторой операции. Полученной таким образом последовательности более соответствует название псевдослучайных чисел, поскольку генерируемая последовательность является периодичной и, начиная с некоторого момента, числа начнут повторяться. Это следует из того, что в коде ЭВМ можно записать лишь конечное число различных чисел. Следовательно, в конце концов одно из генерируемых чисел γ1, совпадет с одним из предыдущих членов последовательности γL. А поскольку генерация осуществляется по формуле вида

γк+1 = F(γk),

с этого момента будут повторяться и остальные члены последовательности.

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

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

F(x) = Рr{Х< х} = х, .

При этом распределении одинаково правдоподобно по явление любых значений случайной величины в интервале (0, 1). Здесь Рг{Х< х} - вероятность того, что случайная величина X примет значение меньше х.

Основным методом получения случайных чисел является их генерация по модулю. Пусть m, a, с, х0 - целые числа, такие, что m > х0 и а, с, х0 > 0. Псевдослучайное число хi из последовательности {хi} получается с помощью рекуррентного соотношения

xi = а xi-1 + с (mod m).

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

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

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

Существует быстрый тест, с помощью которого необходимо проверять каждый генератор. Качество генератора случайных чисел можно продемонстрировать, заполняя полностью d-мерную решетку (например, двух - или трехмерную). Хороший генератор должен заполнить все пространство гиперкуба.

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

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

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

В начале программы целой переменной X присваивается некоторое значение Х0. Затем случайные числа генерируются по правилу

X = (аХ + с) mod m. (1)

Выбор параметров следует осуществлять, пользуясь следующими основными принципами.

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

2.Число m должно быть большим, например, 230 (поскольку именно это число определяет период генерируемой псевдослучайной последовательности).

3.Если m - степень двойки, выбирают а таким, чтобы a mod8 = 5. Если m - степень десяти, выбирают а таким, чтобы a mod10 = 21. Такой выбор гарантирует, что генератор случайных чисел будет вырабатывать все m возможных значений, прежде чем они начнут повторяться.

4.Множитель а предпочтительнее выбирать лежащим между 0.01m и 0.99m, и его двоичные или десятичные цифры не должны иметь простую регулярную структуру. Множитель должен пройти спектральный критерий и, желательно, еще несколько критериев.

5.Если a - хороший множитель, значение с не существен но, за исключением того, что с не должно иметь общего множителя с m, если m - размер компьютерного слова. Можно, например, выбрать с = 1 или с = а.

6. Можно генерировать не больше m/1000 случайных чисел. После этого должна использоваться новая схема, например, новый множитель а .

Перечисленные правила, главным образом, относятся к машинному языку программирования. Для языка программирования высокого уровня, например С++, часто используют другой вариант (1): выбирается простое число m, близкое к наибольшему легко вычисляемому целому числу, значение а полагается равным первообразному корню из m, а с берется равным нулю. Например, можно принять a = 48271 и т =

3. Пример расчета системы массового обслуживания методом Монте-Карло

Рассмотрим простейшую систему массового обслуживания (СМО), которая состоит из n линий (иначе называемых каналами или пунктами обслуживания). В случайные моменты времени в систему поступают заявки. Каждая заявка поступает на линию № 1. Если в момент поступления за явки Тк эта линия свободна, заявка обслуживается время t3 (время занятости линии). Если линия занята, заявка мгновенно передается на линию № 2 и т. д. Если все n линий в данный момент заняты, то система выдает отказ.

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

Для подобных систем практически единственным методом расчета является метод Монте-Карло.

https://pandia.ru/text/78/241/images/image013_34.gif" width="373" height="257">

Для получения случайных чисел на ЭВМ используются алгоритмы, поэтому такие последовательности, являющиеся по сути детерминированными, называются псевдослучайными. ЭВМ оперирует n-разрядными числами, поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0,1) используют дискретную последовательность 2n случайных чисел того же интервала - закон распределения такой дискретной последовательности называется квазиравномерны распределением.

Требования к идеальному генератору случайных чисел:

1. Последовательность должна состоять из квазиравномерно распределенных чисел.

2. Числа должны быть независимыми.

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

4. Последовательности должны иметь неповторяющиеся числа.

5. Последовательности должны получаться с минимальными затратами вычислительных ресурсов.

Наибольшее применение в практике моделирования на ЭВМ для генерации последовательностей псевдослучайных числе находят алгоритмы вида:

представляющие собой реккурентные соотношения первого порядка.

Например. x0 = 0,2152 , (x0)2=0, x1 = 0,6311 , (x1)2=0, x2=0,8287 и т. д.

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

x0 = 0,4500 , (x0)2=0, x1 = 0,2500 , (x1)2=0, x2=0,2500 и т. д.

Широкое применение получили конгруэнтные процедуры генерации псевдослучайных последовательностей.

Два целых числа a и b конгруэнтны (сравнимы) по модулю m, где m - целое число, тогда и только тогда, когда существует такое целое число k, что a-b=km.

1984º4 (mod 10), 5008º8 (mod 103).

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

где - неотрицательные целые числа.

По целым числам последовательности {Xi} можно построить последовательность {xi}={Xi/M} рациональных чисел из единичного интервала (0,1).

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

Методы улучшения качества последовательностей случайных чисел:

1. Использование рекуррентных формул порядка r:

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

2. Метод возмущений:

.

5. Моделирование случайных воздействий на системы

1. Необходимо реализовать случайное событие А, наступающее с заданной вероятностью p. Определим А как событие, состоящее в том, что выбранное значение xi равномерно распределенной на интервале (0,1) случайной величины удовлетворяет неравенству:

Тогда вероятность события А будет https://pandia.ru/text/78/241/images/image019_31.gif" width="103" height="25">,

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

3. Рассмотрим независимые события А и В с вероятностями наступления рА и рВ. Возможными исходами совместных испытаний в этом случае будут события АВ, с вероятностями рАрВ, (1-рА)рВ, рА(1-рВ), (1-рА)(1-рВ). Для моделирования совместных испытаний можно использовать два варианта процедуры:

Последовательное выполнение процедуры, рассмотренной в п.1.

Определение одного из исходов АВ, по жребию с соответствующими вероятностями, т. е. процедура, рассмотренная в п.2.

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

4. События А и В являются зависимыми и наступают с вероятностями pА и pВ. Обозначим через pА(В) условную вероятность наступления события В при условии, что событие А произошло.

Контрольные вопросы

1) Как можно определить метод Монте-Карло?

2) Практическое значение метода Монте-Карло.

3) Общая схема метода Монте-Карло.

4) Пример расчета системы массового обслуживания методом Монте-Карло.

5) Способы генерации случайных чисел.

6) Каковы требования к идеальному генератору случайных чисел?

7) Методы улучшения качества последовательностей случайных чисел.

Другим методом оценки или анализа чувствительности на основе компьютерной имитации является метод Монте-Карло, под которым понимают определенный метод решения некоторого класса экономических или математических задач, в которых те или иные параметры, в нашем случае факторы риска, моделируются в форме случайных величин. Этот метод основан на компьютерной имитации распределений этих случайных величин и формировании соответствующих оценочных показателей проектов на основе этих распределений. Он представляет собой имитационный метод анализа устойчивости, который исторически получил свое название по названию города, в котором располагаются известные игорные дома и казино. Термин "моделирование по методу Монте-Карло" был предложен американскими учеными С. Уламом и Дж. фон Нейманом в процессе работы в рамках известного Манхэттенского проекта. Первая статья по этой проблематике была написана в 1949 г. .

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

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

Организационно метод Монте-Карло как метод имитационного компьютерного моделирования можно описать такой последовательностью основных этапов.

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

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

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

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

Имитационное моделирование случайных величин - выбранных параметров денежного потока. Для моделирования численной реализации соответствующей случайной величины используют встроенный генератор псевдослучайных чисел в опции "Анализ данных" меню "Сервис" пакета Microsoft Excel. В этом случае должно быть заранее задано ожидаемое значение рассматриваемого параметра и его стандартное отклонение, а также количество численных реализаций случайных величин, которые должны быть получены в течение одного цикла имитационных расчетов. Для подобных расчетов можно также применять специальные пакеты прикладных программ.

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

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

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

где k - число отрицательных значений чистой настоящей стоимости в полученной в процессе имитации выборке; т - количество проведенных имитационных экспериментов. Подобная оценка вероятности неблагоприятных исходов опирается на предположение о том, что вероятность каждого исхода в процессе одного цикла имитационного моделирования одинакова и составляет р = 1 /т. Аналогичные расчеты могут быть выполнены и для ставки внутреннего процента, индекса доходности, периода окупаемости.

При проведении расчетов можно использовать встроенные статистические функции пакета Microsoft Excel (табл. 5.12), которые задаются на распределении NPV или с помощью другого расчетного показателя, полученного в результате одного цикла имитационных расчетов.

Таблица 5.12

Используемые встроенные функции пакета Microsoft Excel

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

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

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

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

Рис. 5.4.

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

Общая последовательность расчетов по методу Монте-Карло представлена на рис. 5.4. Соответствующие расчеты могут быть выполнены только на ЭВМ при использовании встроенных возможностей пакета Microsoft Excel или иных пакетов прикладных программ.

Покажем возможности реализации метода Монте-Карло и особенности анализа полученных результатов на основе следующего условного примера. Все исходные данные по рассматриваемому проекту приведены в табл. 5.13.

Таблица 5.13

Исходные данные по проекту

Показатель
Коэффициент использования мощностей, %
Ожидаемая цена реализации, руб.
Стандартное отклонение цены реализации, руб.
Инвестиции, руб.
Условно-постоянные расходы, руб/год
Условно-переменные расходы, руб/сд. ирод.
Стандартное отклонение условно-переменных расходов

Выделим параметры и сформируем исходный денежный поток данного инвестиционного проекта. Расчеты компонентов денежного потока выполнены по формулам

где k t - коэффициент использования производственной мощности в году t, M t - производственная мощность предприятия в году t, p t - цена продукции в период t; h f - норма условно-переменных расходов в году t; H f - условно-постоянные расходы в период t,t= 1, 2,..., T; T - период исполнения проекта.

Результаты расчета исходного денежного потока по формулам (5.10) приведены в табл. 5.14.

В данном примере рассматривается компьютерное моделирование двух факторов риска: цены продукции во втором году и условно-переменных расходов в третьем году. Имитационное моделирование осуществляется на основе предположения о нормальном распределении обоих факторов.

Таблица 5.14

Параметры и денежный поток инвестиционного проекта

	Инвестиции		Коэффициент использования мощностей, %	Максимальный объем выпуска, ед. изд.	Ожидаемая пеалнзанмн.		постоянные	Условно- переменные расходы, руб/ед. ирод.	Денежный
			-

Для цены второго года в качестве ожидаемого или среднего значения выбирается 30 руб. (см. табл. 5.13), а стандартное отклонение полагается равным 2. Для условно-переменных расходов третьего года, соответственно, ожидаемое значение равно 16 руб. (см. табл. 5.13), а стандартное отклонение было выбрано равным 1. Оценка стандартного отклонения может быть получена на основе представлений о возможных интервалах колебаний соответствующего показателя. Так, если ожидаемое колебание цены реализации второго года составляет 6 руб. в обе стороны от ожидаемого значения, то, учитывая, что в условиях нормального распределения практически почти весь интервал составляет ±3а, приблизительная оценка стандартного отклонения в данном случае равна 6/3 = 2 руб. Аналогично могут быть получены и другие значения стандартного отклонения, приведенные в табл. 5.13.

При компьютерном моделировании случайной реализации обоих выбранных показателей были использованы встроенные возможности пакета Microsoft Excel по генерации псевдослучайных величин на основе нормального распределения. Каждый цикл имитационных расчетов включал в себя 100 итераций. Результаты одного цикла расчетов обоих случайных величин приведены в табл. 5.15.

Прежде чем выполнять дальнейшие расчеты, необходимо проверить гипотезу об отсутствии корреляции между обеими случайными величинами, распределения которых приведены в табл. 5.15. Для этого, используя встроенную функцию "КОРРЕЛ" пакета Microsoft Excel, рассчитаем выборочный коэффициент парной корреляции, значение которого составит r ph = -0,10906, т.е. почти равно нулю. Для формальной проверки гипотезы

Таблица 5.15

Имитация распределения случайных величин, руб.

І Іомер итерации	Цена второго года, руб.	Условно-переменные расходы третьего года, руб/ед. прод.
	Среднее значение - 30	Среднее значение -16
	Стандартное отклонение - 2	Стандартное отклонение - 1

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

где п - объем выборки, т.е. число итераций в одном цикле имитационных расчетов, и сопоставить ее со статистикой t a (n - 2), имеющей распределение Стъюдента сп - 2 степенями свободы и доверительный уровень а. Учитывая указанное значение выборочного коэффициента корреляции и объем выборки п = 100, в данном случае получим:

что по модулю меньше соответствующего табличного значения квантиля распределения Стьюдента с 98 степенями свободы и доверительным уровнем 0,95, которое составляет 1,984. Это позволяет принять гипотезу Н {) с вероятностью ошибки первого рода, равной 0,05.

Используя полученные численные реализации цены второго года и условно-переменных расходов третьего года (см. табл. 5.15), а также заданные значения остальных параметров денежного потока (см. табл. 5.14), формируются денежные потоки инвестиционного проекта, соответствующие полученным значениям цен на каждой итерации. Расчеты выполнены по формулам (5.10). Всего сформировано 100 денежных потоков. Результаты расчетов приведены в табл. 5.16.

Таблица 5.16

итерации

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

Была использована ставка расчетного процента, равная 12%. Эти расчеты выполнены в пакете Microsoft Excel с помощью встроенной финансовой функции "ЧПС", используемой для вычисления значений чистой настоящей стоимости. Результаты расчетов приведены в табл. 5.17.

Таблица 5.17

Варианты денежного потока рассматриваемого проекта в рамках одного цикла имитационных расчетов, руб.

Номер итерации	Чистая настоящая стоимость	Номер итерации	Чистая настоящая стоимость

Используя полученное распределение значений чистой настоящей стоимости проекта, можно определить основные характеристики, отражающие степень влияния факторов риска на чистую настоящую стоимость этого проекта. Построим частотную гистограмму значений чистой настоящей стоимости. Для этого все полученные на 100 итерациях значения чистой настоящей стоимости проекта подразделим на группы следующим образом. В первую группу включим те значения чистой настоящей стоимости, которые не превосходят -20 000 руб., а далее с шагом 10 000 руб. сформируем еще семь групп значений чистой настоящей стоимости, со 2-й но 8-ю, причем в последнюю группу включим те значения чистой настоящей стоимости, которые превышают 50 000 руб., и определим количество значений чистой настоящей стоимости, попавшей в каждую выделенную группу (табл. 5.18).

Распределение полученных значений чистой настоящей стоимости по группам, которые указаны в табл. 5.18, можно представить на следующей частотной гистограмме (рис. 5.5). Эта гистограмма показывает, что наибольшее количество полученных значений NPV располагается в интервале от -10 000 до 30 000. Она дает также определенное представление о возможных отрицательных значениях чистой настоящей стоимости, которые в данном примере попали в 1 -ю, 2-ю и 3-ю группы. При этом большая часть

Таблица 5.18

Группировка расчетных значений чистой настоящей стоимости

Рис. 55.

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

Метод Монте-Карло позволяет проанализировать влияние факторов риска - выбранных параметров проекта - на изучаемые показатели его оценки. В нашем примере в качестве такого показателя рассматривается чистая настоящая стоимость. Результаты расчетов шести показателей, характеризующих распределения NPV, построенные последовательно на каждом из выполненных 10 циклов имитационных расчетов, приведены в табл. 5.19.

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

Проанализируем подробнее результаты расчетов, которые приведены в табл. 5.19. При этом показатели для 1-го цикла имитационных расчетов были определены на основе распределения NPV, представленного в табл. 5.17.

Таблица 5.19

Характеристики распределений NPV, полученных в режиме имитации, руб.

Показатель	Цикл имитационных расчетов
Ожидаемое значение NPV
Стандартное отклонение NPV
Коэффициент вариации
Вероятность отрицательного значения NPV
Наибольшее значение NPV
Наименьшее значение NPV

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

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

В-третьих, этот вывод подтверждают полученные оценки вероятности отрицательного значения NPV проекта, которое определяется в соответствии с формулой (5.9) как отношение числа полученных отрицательных значений чистой настоящей стоимости на данном цикле имитационных расчетов к общему числу итераций, которое равно 100. Для всех проведенных циклов имитационных расчетов эта вероятность составляет примерно 30%.

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

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

1. Можно использовать визуальную оценку распределения результатов, представленных в табл. 5.19. Так, на рис. 5.6 приведено распределение вероятности отрицательного значения NPV r полученное в 10 циклах имитационных расчетов.

При анализе графика, приведенного на рис. 5.6, очевидно, что полученный интервал колебаний этой вероятности достаточно узок. Если использовать максимальное и минимальное значения этой вероятности, то можно показать, что отклонения от среднего значения этой вероятности по данной выборке, которое равно 0,31, составляет примерно 13% в обе стороны.

Рис. 5.6. Вероятность отрицательного значения NPV по циклам имитации

Аналогично можно выделить интервал колебания ожидаемого значения чистой настоящей стоимости проекта. Как показывают данные табл. 5.19, во всех циклах имитационных расчетов ожидаемая NPV имела положительное значение, хотя и была подвержена определенным колебаниям. График, приведенный на рис. 5.7, показывает, как возможные тенденции изменения указанного показателя, так и интервал колебаний его значения по выполненным циклам имитационных расчетов.

Рис. 5.7. Ожидаемое значение NPV по циклам имитации

Если учесть, что среднее по выборке значение ожидаемой чистой настоящей стоимости - 6332,38 руб., то можно показать, что интервал колебаний расчетных значений составляет примерно 24% в обе стороны от среднего значения. Полученные оценки весьма зависят от числа выполненных циклов имитационных расчетов и, естественно, будут меняться при проведении последующих циклов. Относительная надежность подобных оценок возрастает по мере роста числа циклов имитационных расчетов и расширения объема выборки, представленной в табл. 5.19. Аналогичный анализ может быть выполнен и для других показателей, определяемых в каждом цикле имитационных расчетов (см. табл. 5.19).

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

Принятие решения об исполнении или неисполнении инвестиционного проекта на основе данных, полученных по методу Монте-Карло, прежде всего предполагает анализ полученных распределений значений чистой настоящей стоимости проекта, который можно проводить на основе гистограммы, аналогичной показанной на рис. 5.5. Подобная гистограмма может быть также построена для среднего по всем реализациям распределения NPV.

Если все значения распределения NPV на каждом цикле имитационных расчетов оказываются положительными, то проект можно рекомендовать к исполнению, в противном случае, если все значения распределения NPV проекта отрицательны на каждом цикле имитационных расчетов, проект не рекомендуется к исполнению. Во всех других случаях необходимо сопоставлять шансы на получение положительного и отрицательного значений NPV. Для гистограммы, представленной на рис. 5.5, можно отметить, что положительные значения NPV достигаются для групп с 4-й по 8-ю. Учитывая данные табл. 5.18, можно отметить, что по данной выборке 65% значений NPV положительны и только 35% отрицательны. Аналогичный анализ можно выполнить и по среднему значению распределения по всем циклам имитационных расчетов.

В литературе, посвященной проблемам оценки инвестиционных проектов по методу Монте-Карло, предлагается рассчитать еще некоторые показатели по выборке NPV при предположении, что результаты на каждой итерации в течение одного цикла имитационных расчетов имеют одинаковую вероятность р= 1 /п. Именно на основе данного подхода рассчитаны значения ожидаемой NPV в табл. 5.19. Предлагается по такой же схеме определять "ожидаемый выигрыш" по положительным значениям NPV в полученной выборке и "ожидаемый проигрыш" - по отрицательным значениям NPV в этой выборке .

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

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

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

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

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

Подробнее о проверке гипотез см.: Магнус Я. Р.. Катышев П. К., Пересецкий А. А. Эконометрика. Начальный курс. М.: Дело, 1997. С. 219-221.

Риск-менеджмент инвестиционного проекта: учебник / под ред. М. В. Грачевой, Л. Б. Сикерина. М.: ЮНИТИ-ДАНА, 2009. С. 169-170.

Глава 2. Примеры использования метода Монте-Карло 8

2.1 Простейший пример использования метода Монте-Карло 8

2.2 Вычисление числа Пи методом Монте-Карло 8

2.2.1 Постановка задачи для нахождения числа Пи методом Монте-Карло 10

2.2.2 Листинг программы для нахождения числа Пи методом Монте-Карло 10

2.3 Решение задачи аналитически и методом Монте-Карло 12

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

Заключение 20

Список литературы 21

Введение

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

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

Глава 1. Предыстория и определение метода Монте-Карло

Создателями метода статистических испытаний (метода Монте-Карло) считают американских математиков Д. Неймана и С. Улама. В 1944 году, в связи с работами по созданию атомной бомбы Нейман предложил широко использовать аппарат теории вероятностей для решения прикладных задач с помощью ЭВМ. Первая работа, где этот вопрос систематически излагался, принадлежит Метрополису и Уламу.

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

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

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

Основными недостатками аналитических методов являются:

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

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

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

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

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

Оценка погрешности решения представляет намного более трудную процедуру, чем сам процесс решения. Зачастую она просто невозможна.

Метод статистических испытаний свободен от всех этих недостатков.

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

Задача метода Монте-Карло после получения ряда реализаций интересующей нас случайной величины заключается в получении некоторых сведений о ее распределении, т.е. является типичной задачей математической статистики.

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

М(Х)= A .

Практически же поступают так: производят N испытаний, в результате которых получают N возможных значений X, вычисляют их среднее арифметическое и принимают его в качестве оценки (приближенного значения) A ’ искомого числа A .

Как правило, составляется программа для осуществления одного случайного испытания. Погрешность вычислений, как правило, пропорциональна , где D – некоторая постоянная.

Это значит, что N должно быть велико, поэтому метод существенно опирается на возможности ЭВМ. Ясно, что добиться таким путем высокой точности невозможно. Это один из недостатков метода. Во многих задачах удается значительно увеличить точность, выбрав способ расчета, которому соответствует значительно меньшее D .

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

Отыскание возможных значений случайной величины Х (моделирование) называют «разыгрыванием случайной величины».

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

В отличие от аналитических методов, ищущих решение в виде ряда по собственным функциям, методы Монте-Карло ищут решения в виде статистических сумм. Для их применения достаточно описания вероятностного процесса и не обязательна его формулировка в виде интегрального уравнения; оценка погрешности чрезвычайно проста, их точность слабо зависит от размерности пространства.

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

Преимущество метода Монте-Карло состоит в том, что он способен “сработать” там, где не справляются другие методы.

Аналитические методы исследования позволяют существенно уменьшить погрешность метода Монте-Карло и могут поднять его до уровня получения качественных закономерностей. Синтез аналитических и статистических методов может свести D к очень малой величине, следовательно, уменьшить погрешность.

Приведем примеры задач, решаемых методом Монте-Карло:

расчет системы массового обслуживания;

расчет качества и надежности изделий;

теория передачи сообщений;

вычисление определенного интеграла;

задачи вычислительной математики;

задачи нейтронной физики и другие.

Глава 2. Примеры использования метода Монте-Карло

2.1 Простейший пример использования метода Монте-Карло

Предположим, что нам нужно определить площадь плоской фигуры, расположенной внутри единичного квадрата, т.е. квадрата, сторона которого равна единице (рис. 1). Выберем внутри квадрата наугад N точек. Обозначим через M количество точек, попавших при этом внутрь фигуры. Тогда площадь фигуры приближенно равна отношению . Отсюда, чем больше N , тем больше точность такой оценки.

Рисунок 1. Площадь фигуры приближенно равна, отношению числа точек попавших в фигуру к числу всех точек.

2.2 Вычисление числа Пи методом Монте-Карло

Попробуем построить метод Монте-Карло для решения задачи о вычислении числа Пи. Для этого рассмотрим четверть круга единичного радиуса (рис. 2). Площадь круга равна
, очевидно, площадь четверти круга равна:

.

Зная, что радиус круга равен 1, получим:

X

Рисунок 2. Нахождение числа Пи методом Монте-Карло.

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

Пусть всего было испытано N точек, и из них M попало в круг. Рассмотрим отношение количества точек, попавших в круг, к общему количеству точек (M /N ). Очевидно, что чем больше случайных точек мы испытаем, тем это отношение будет ближе к отношению площадей четверти круга и квадрата. Таким образом, имеем, что, для достаточно больших N , верно равенство:

.

Из полученного равенства:

.

Итак, мы построили метод Монте-Карло для вычисления числа Пи. Опять перед нами стоит вопрос о том, какое именно количество точек N нужно испытать для того, чтобы получить Пи с предсказуемой точностью? Вопрос о точности вычислений с помощью методов Монте-Карло рассматривается в традиционных курсах теории вероятностей, и мы не будем останавливаться на нем подробно. Можно отметить лишь, что точность вычислений очень сильно зависит от качества используемого генератора псевдослучайных чисел. Другими словами, точность тем выше, чем более равномерно случайные точки распределяются по единичному квадрату.

2.2.1 Постановка задачи для нахождения числа Пи методом Монте-Карло

Для проверки формулы , была написана программа в среде программирования Турбо Паскаль. В программе нужно ввести число K – количество испытаний и число N – количество испытываемых точек. Для координат точек (X, Y) используется генератор случайных чисел. Результаты всех испытаний усредняются.

2.2.2 Листинг программы для нахождения числа Пи методом Монте-Карло

K, {количество испытаний}

N, {количество точек}

i, j: word; {для циклов}

s, {сумма всех Пи}

P: real; {среднеарифметическое значение Пи}

{функция возвращает число Пи}

FUNCTION raschet: real;

x, y: word; {координаты точек}

M: word; {число точек попавших в окружность}

for i:=1 to N do

x:=random(2); {x, y – случайные числа}

if sqr(x)+sqr(y)<=1 then inc(M); {точка с координатами x, y попала в круг}

raschet:=4*M/N; {из формулы }

write("Введите количество испытаний: ");

write("Введите количество испытываемых точек: ");

for j:=1 to K do s:=s+raschet;

writeln("Число Пи, рассчитанное методом Монте-Карло равно:");

writeln("Точное число Пи равно:");

writeln(Pi:1:6);

Итак, с помощью этой программы была проверена верность формулы . В результате получилось число Пи равное: 3.000808 , при количестве испытаний 500 раз с количеством точек 5000. Точное число Пи равно: 3.141593 .

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

2.3 Решение задачи аналитически и методом Монте-Карло

Рассмотрим задачу:

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

Аналитическое решение.

Событие А – выход из строя хотя бы одного из трех приборов за время Т и событие – ни один из трех приборов не выйдет из строя за время Т, противоположные. Вероятность
– искомая вероятность. Отсюда:

Теперь решим задачу методом Монте-Карло.

Напомним, что при использовании данного метода возможны два подхода: либо непосредственно проводят эксперименты, либо имитируют их другими экспериментами, имеющими с исходными одинаковую вероятностную структуру. В условиях данной задачи «натуральный» эксперимент – наблюдение за работой системы в течение времени Т. Многократное повторение этого эксперимента может оказаться трудноосуществимым или просто невозможным. Заменим этот эксперимент другим.

Для определения того, выйдет или не выйдет из строя за время Т отдельный прибор, будем подбрасывать игральную кость. Если выпадет одно очко, то будем считать, что прибор вышел из строя; если два, три, четыре, пять, шесть очков, то будем считать, что прибор работал безотказно. Вероятность того, что выпадет одно очко, так же как и вероятность выхода прибора из строя, равна 1/6, а вероятность того, что выпадет любое другое число очков, как и вероятность безотказной работы прибора, равна 5/6.

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

Повторим испытание, состоящее в подбрасывании трех игральных костей, много раз подряд и найдем отношение числа M – отказов системы к общему числу N – проведенных испытаний. Вероятность отказа будет равна:

.

Для проверки формулы , которая основана на методе Монте-Карло, я решил написать программу в среде программирования Турбо Паскаль. Дело в том, что если бы вероятность безотказной работы приборов была не , а например , имитировать другими экспериментами, имеющими с исходными одинаковую вероятностную структуру, без использования ЭВМ было бы затруднительно.

Данная программа рассчитана на любые подобные задачи. В конце расчетов программа выдает два ответа. Первый – полученный методом Монте-Карло по формуле . Второй – полученный аналитическим методом по формуле .

В программе нужно ввести: B – количество приборов; вероятность в виде дроби; N – количество проведенных опытов.

B, {количество приборов}

S, D: byte; {вероятность P(A)=S/D}

N, {количество опытов}

i, j, {для циклов}

summa: word; {суммарное число отказов}

P_M, P_A: real; {полученная вероятность}

{функция возвращает количество отказов за одно испытание}

FUNCTION otkaz: word;

for i:=1 to B do

R:=random(D+1)+1; {случайное число >=1 и <=D}

if R<=D-S then inc(o); {выпал "отказ"}

write("Введите количество приборов: ");

writeln("Введите вероятность безотказной работы (в виде дроби):");

write(" числитель – ");

write(" знаменатель – ");

readln(D); {т.е. P=S/D}

write("Введите количество опытов: ");

{расчет методом Монте-Карло}

for j:=1 to N do summa:=summa+otkaz;

{расчет аналитическим методом}

for i:=1 to B-1 do P_A:=P_A*S/D; {возведение в степень}

writeln("* * * Ответ * * *");

writeln("Методом Монте-Карло: ", P_M:1:6);

writeln("Аналитическим методом: ", P_A:1:6);

Итак, проверив формулу с помощью своей программы со значениями: количество приборов – 3; вероятность безотказной работы ; количество опытов – 50000, я получил два ответа. Решение задачи методом Монте-Карло – 0.429420 . Решение задачи аналитическим методом – 0.421296 . Отсюда вывод – вероятность, полученная разными методами сходна.

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

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

Итак, дадим определение этих чисел. Обозначим через R непрерывную случайную величину, распределенную равномерно в интервале (0, 1).

Случайными числами называют возможные значения r j непрерывной случайной величины R, распределенной равномерно в интервале (0, 1).

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

Случайная величина R’ обладает свойством: вероятность попадания ее в любой интервал, принадлежащий интервалу (0; 1) равна длине этого интервала.

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

Исчерпание этой последовательности при большом числе циклов Монте-Карло или размере системы снижает ее фактический размер до:

N – размер системы (количество частиц);

P – период последовательности псевдослучайных чисел;

k – количество случайных чисел, используемых для определения состояния одной частицы;

n – суммарное количество циклов Монте-Карло, необходимое для стабилизации системы и расчета ее характеристик.

Например, при моделировании системы Изинга, состоящей из 2000 частиц требуется, как правило, не менее 500 циклов МК, т.е. необходимо не менее 10 5 случайных чисел. Если используемый генератор является 16-ти разрядным и не может произвести последовательность, состоящую из более чем 2 16 (65536) псевдослучайных чисел, то фактический размер системы по формуле будет порядка 1000 частиц.

С играми ситуация еще более трагическая: например, колода из 52 карт может быть упорядочена 52! способами. Это примерно 8e67 или 2 226 . Значит для того, чтобы в процессе игры мог возникнуть любой расклад, создателю полноценной карточной игры типа «21» необходим 256 разрядный генератор случайных чисел. Если колода состоит из 36 карт, то соответствующие числа равны 4e41 и 2 138 , т.е. без суперкомпьютера опять не обойдешься. В карточной игре «преферанс» количество вариантов раздач равно 32!/10! или 2 96 , что тоже не мало. Несмотря на несравнимость этих чисел с реальными возможностями 32-х разрядного процессора, необходимо, конечно, использовать его возможности максимально, ведь только так можно приблизиться к разнообразию реальности.

Заключение

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

Задачи, решаемые методом Монте-Карло: расчет системы массового обслуживания; расчет качества и надежности изделий; теория передачи сообщений; вычисление определенного интеграла; задачи вычислительной математики; задачи нейтронной физики; моделирования дискретных и непрерывных случайных величин; моделирования случайных процессов и полей; вычисления многомерных интегралов и другие.

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

И.М.Соболь «Метод Монте-Карло», М., 1985

Интернет-ресурс «Предыстория и определение метода Монте-Карло» /GIS/Learning/Monte-Carlo_2/Page01.htm

/~gene/probset/prob13.koi8.html

Интернет-ресурс «Метод Монте-Карло» /Exponenta_Ru/educat/systemat/boziev/13.asp.htm

Интернет-ресурс «Вундеркинд» /2001/leto/stend/Vynderkind.htm

Интернет-ресурс «Метод Монте-Карло» /docs/TViMS/NP/lekziitv/lekziya17.htm

Документ

Предыдущих главах настоящей работы. Такая модификация позволила сделать метод Монте -Карло более... 78 до 0,95. Пример одной из таких связей... точками (при использовании метода Монте -Карло ). Основным недостатком первого метода является недостаточная...

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

Автореферат диссертации

... использованием метода Монте -Карло для условий реальной геометрии спектрометрического измерения. Метод Монте -Карло ... расчетов. Глава III. Спектрометрические методы определения... разделе 4.2 приведены примеры использования прибора при измерениях...

Глава 11 эконометрические информационные технологии

Документ

Итоговой процедуры можно рассчитать (см. примеры в главе 13). В результате итоговую процедуру нельзя... использовании метода сценариев (см. главу 12). При имитационном моделировании часто используется метод статистических испытаний (Монте -Карло ...

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

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

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

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

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

Общая характеристика метода Монте-Карло

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

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

Каждое значение случайной величины x i представляется в машине двоичным числом, которое поступает с выхода датчика случайных чисел на сумматор. Для статистического моделирования рассматриваемой задачи требуется N-кратное повторение решения.

Рассмотрим ещё один пример. Производится десять независимых выстрелов по мишени. Вероятность попадания при одном выстреле задана и равна p. Требуется определить вероятность того, что число попаданий будет чётным, т.е. 0, 2, 4, 6, 8, 10. Вероятность того, что число попаданий будет 2k, равна:

откуда искомая вероятность

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

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

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

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

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

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

При решении алгебраических уравнений методом Монте-Карло число операций пропорционально числу уравнений, а при их решении детерминированными численными методами это число пропорционально кубу числа уравнений. Такое же приблизительно преимущество сохраняется вообще при выполнении различных вычислений с матрицами и особенно в операции обращения матрицы. Надо заметить, что универсальные вычислительные машины не приспособлены для матричных вычислений и метод Монте-Карло, применённый на этих машинах, лишь несколько улучшает процесс решения, но особенно преимущества вероятностного счёта проявляются при использовании специализированных вероятностных машин. Основной идеей, которая используется при решении детерминированных задач методом Монте-Карло, является замена детерминированной задачи эквивалентной статистической задачей, к которой можно применять этот метод. Естественно, что при такой замене вместо точного решения задачи получается приближённое решение, погрешность которого уменьшается с увеличением числа испытаний.

Эта идея используется в задачах дискретной оптимизации, которые возникают при управлении. Часто эти задачи сводятся к перебору большого числа вариантов, исчисляемого комбинаторными числами вида N=. Так, задача распределения n видов ресурсов между отраслями для n>3 не может быть точно решена на существующих цифровых вычислительных машинах (ЦВМ) и ЦВМ ближайшего будущего из-за большого объёма перебора вариантов. Однако таких задач возникает очень много в кибернетике, например синтез конечных автоматов. Если искусственно ввести вероятностную модель-аналог, то задача существенно упростится, правда, решение будет приближённым, но его можно получить с помощью современных вычислительных машин за приемлемое время счёта.

При обработке больших массивов информации и управлении сверхбольшими системами, которые насчитывают свыше 100 тыс. компонентов (например, видов работ, промышленных изделий и пр.), встаёт задача укрупнения или эталонизации, т.е. сведения сверхбольшого массива к 100-1000 раз меньшему массиву эталонов. Это можно выполнить с помощью вероятностной модели. Считается, что каждый эталон может реализоваться или материализоваться в виде конкретного представителя случайным образом с законом вероятности, определяемым относительной частотой появления этого представителя. Вместо исходной детерминированной системы вводится эквивалентная вероятностная модель, которая легче поддаётся расчёту. Можно построить несколько уровней, строя эталоны эталонов. Во всех этих вероятностных моделях с успехом применяется метод Монте-Карло. Очевидно, что успех и точность статистического моделирования зависит в основном от качества последовательности случайных чисел и выбора оптимального алгоритма моделирования.

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

Если y является функцией x, т.е. y=F(x), то и поэтому. Таким образом, для получения последовательности случайных чисел, имеющих заданную функцию распределения F(x), необходимо каждое число y с выхода датчика случайных чисел, который формирует числа с равномерным законом распределения в интервале , подать на нелинейное устройство (аналоговое или цифровое), в котором реализуется функция, обратная F(x), т.е.

Полученная таким способом случайная величина X будет иметь функцию распределения F(x). Рассмотренная выше процедура может быть использована для графического способа получения случайных чисел, имеющих заданный закон распределения. Для этого на миллиметровой бумаге строится функция F(x) и вводится в рассмотрение другая случайная величина Y, которая связана со случайной величиной X соотношением (2) (рис. 2).

Так как любая функция распределения монотонно неубывающая, то

Отсюда следует, что величина Y имеет равномерный закон распределения в интервале , т. к. её функция распределения равна самой величине

Плотность распределения вероятности для Y

Для получения значения X берётся число из таблиц случайных чисел, имеющих равномерное распределение, которое откладывается на оси ординат (рис. 2), и на оси абсцисс считывается соответствующее число X. Повторив неоднократно эту процедуру, получим набор случайных чисел, имеющих закон распределения F(x). Таким образом, основная проблема заключается в получении равномерно распределённых в интервале случайных чисел. Один из методов, который используется при физическом способе получения случайных чисел для ЭВМ, состоит в формировании дискретной случайной величины, которая может принимать только два значения: 0 или 1 с вероятностями

Можно доказать, что случайная величина? * , заключённая в интервале , имеет равномерный закон распределения

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

Вероятность каждого значения (3) равна 2 -k . Эти значения можно получить следующим образом

Случайная величина имеет математическое ожидание

Учитывая, что

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

получаем:

Аналогично можно определить дисперсию величины:

или, используя формулу (4), получаем:

Согласно формуле (5) оценка величины?* получается смещённой при конечном k. Это смещение особенно сказывается при малом k. Поэтому вместо вводят оценку

Очевидно, что случайная величина? в соответствии с соотношением (3) может принимать значения

I=0,1,2,…, 2 k -1

с вероятностью p=1/2 k .

Математическое ожидание и дисперсию величины? можно получить из соотношений (5) и (6), если учесть (7). Действительно,

Отсюда получаем выражение для среднеквадратичного значения в виде

Напомним, что для равномерно распределённой в интервале величины x имеем

Из формулы (8) следует, что при среднеквадратичное отклонение? квазиравномерной совокупности стремится к. Ниже приведены значения отношения среднеквадратичных значений двух величин? и? в зависимости от числа разрядов, причём величина? имеет равномерное распределение в интервале (табл. 1).

Таблица 1

Из табл. 1 видно, что при k>10 различие в дисперсиях несущественно.

На основании вышеизложенного задача получения совокупности квазиравномерных чисел сводится к получению последовательности независимых случайных величин z i (i=1,2,…, k), каждая из которых принимает значение 0 или 1 с вероятностью 1/2. Различают два способа получения совокупности этих величин: физический способ генерирования и алгоритмическое получение так называемых псевдослучайных чисел. В первом случае требуется специальная электронная приставка к цифровой вычислительной машине, во втором случае загружаются блоки машины.

При физическом генерировании чаще всего используются радиоактивные источники или шумящие электронные устройства. В первом случае радиоактивные частицы, излучаемые источником, поступают на счётчик частиц. Если показание счётчика чётное, то z i =1, если нечётное, то z i =0. Определим вероятность того, что z i =1. Число частиц k, которое испускается за время?t, подчиняются закону Пуассона:

Вероятность чётного числа частиц

Таким образом, при больших??t вероятность P{Z i =1} близка к 1/2.

Второй способ получения случайных чисел z i более удобен и связан с собственными шумами электронных ламп. При усилении этих шумов получается напряжение u(t), которое является случайным процессом. Если брать его значения, достаточно отстоящие друг от друга, так чтобы они были некоррелированы, то величины u(t i) образуют последовательность независимых случайных величин. Обычно выбирают уровень отсечки a и полагают

причём уровень a следует выбрать так, чтобы

Также применяется более сложная логика образования чисел z i . В первом варианте используют два соседних значения u(t i) и u(t i+1), и величина Z i строится по такому правилу:

Если пара u(t i) - a и u(t i+1) - a одного знака, то берётся следующая пара. Требуется определить вероятность при заданной логике. Будем считать, что P {u(t i)>a}=W и постоянная для всех t i . Тогда вероятность события равна по формуле событий A 1 H v . Здесь H v - это вероятность того, что v раз появилась пара одинакового знака

u(t i) - a; u(t i+1) - a. (9)

Поэтому вероятность события A 1 H v

P{A 1 H v }=W (1-W) v .

Это - вероятность того, что после v пар вида (9) появилось событие A 1 . Оно может появиться сразу с вероятностью W (1-W), оно может появиться и после одной пары вида (9) с вероятностью

W (1-W)

и т.д. В результате

Отсюда следует, что если W=const, то логика обеспечивает хорошую последовательность случайных чисел. Второй способ формирования чисел zi состоит в следующем:

W=P {u(t i)>a}=1/2+?.

P{Z i =1}=2W (1-W)=1/2-2? 2 .

Чем меньше?, тем ближе вероятность P{Z i =1} к величине 1/2.

Для получения случайных чисел алгоритмическим путём с помощью специальных программ на вычислительной машине разработано большое количество методов. Так как на ЦВМ невозможно получить идеальную последовательность случайных чисел хотя бы потому, что на ней можно набрать конечное множество чисел, такие последовательности называются псевдослучайными. На самом деле повторяемость или периодичность в последовательности псевдослучайных чисел наступает значительно раньше и обусловливается спецификой алгоритма получения случайных чисел. Точные аналитические методы определения периодичности, как правило, отсутствуют, и величина периода последовательности псевдослучайных чисел определяется экспериментально на ЦВМ. Большинство алгоритмов получается эвристически и уточняется в процессе экспериментальной проверки. Рассмотрение начнём с так называемого метода усечений. Пусть задана произвольная случайная величина u, изменяющаяся в интервале , т.е. . Образуем из неё другую случайную величину

u n =u , (10)

где u используется для определения операции получения остатка от деления числа u на 2 -n . Можно доказать, что величины u n в пределе при имеют равномерное распределение в интервале .

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

Пример 1. Пусть u = 0,10011101… = 1?1/2 + 0?1/2 2 + 0?1/2 3 + 1?1/2 4 + 1?1/2 5 + 1?1/2 6 + 0?1/2 7 + 1?1/2 8 + …

Выберем для простоты n=4. Тогда {u mod 2 -4 } = 0,1101…

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

При проверке качества псевдослучайных чисел прежде всего интересуются длиной отрезка апериодичности и длиной периода (рис. 3). Под длиной отрезка апериодичности L понимается совокупность последовательно полученных случайных чисел? 1 , …, ? L таких, что? i ? j при, но? L+1 равно одному из? k ().

Под длиной периода последовательности псевдослучайных чисел понимается T=L-i+1. Начиная с некоторого номера i числа будут периодически повторяться с этим периодом (рис. 3).

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

Точность метода Монте-Карло

Метод Монте-Карло применяется там, где не требуется высокой точности. Например, если определяют вероятность поражения мишени при стрельбе, то разница между p 1 =0,8 и p 2 =0,805 несущественна. Обычно считается, что метод Монте-Карло позволяет получить точность примерно 0,01-0,05 максимального значения определяемой величины.

Получим некоторые рабочие формулы. Определим по методу Монте-Карло вероятность пребывания системы в некотором состоянии. Эта вероятность оценивается отношением

где M - число пребываний системы в этом состоянии в результате N моделирований. Учитывая выражение для дисперсии величины M/N

и неравенство Чебышёва

Величина

есть ни что иное, как ошибка моделирования по методу Монте-Карло. С помощью формулы (11) можно написать следующую формулу для величины (12):

где p 0 - вероятность невыполнения этой оценки. С помощью частоты M/N может быть получена оценка математического ожидания m x некоторой случайной величины X. Ошибка этой оценки

находится с помощью соотношения

Отсюда видно, что ошибка моделирования находится в квадратичной зависимости от числа реализаций, т.е.

Пример 2. Допустим, что определяется математическое ожидание ошибки x поражения мишени. Процесс стрельбы и поражения моделируется на ЦВМ по методу Монте-Карло. Требуется точность моделирования? = 0,1 м с вероятностью p = 1-p 0 = 0,9 при заданной дисперсии? x = 1 м. Необходимо определить количество моделирований N. По формуле (13) получаем:

При таком количестве реализаций обеспечивается?=0,1 м с вероятностью p=0,9.