Разыгрывание случайной величины

Лекция №15

Способ статистических испытаний
(способ Монте-Карло)

Случайные величины

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

Величину x именуют случайной с плотностью рассредотачивания r(x), если возможность того, что величина воспримет значение меж x1 и x2 равна . В силу определения вероятности, r(x) неотрицательна и нормирована на единицу, т.е.

. (1)

Если значения Разыгрывание случайной величины x всегда заключены меж a и b, то r(x) = 0 вне данных пределов. В данном случае интеграл в (1) следует брать по отрезку [a,b].

Случайная величина x может быть дискретной, т.е. принимать только полностью определенные значения xi с вероятностью ri. Дискретную величину можно формально соединить с непрерывной Разыгрывание случайной величины, считая

,

где — дельта-функция.

Если по значениям случайной величины x вычисляют какую-либо функцию f(x), то значения данной функции также будут случайными. Данную функцию время от времени именуют случайной.

Умеренно распределенная величина. Разглядим случайную функцию

, (2)

которая воспринимает значения из отрезка [0,1] и однообразно находится в зависимости от x. Возможность того, что g Разыгрывание случайной величины лежит меж g1 = g(x1) и g2 = g(x2), равна вероятности того, что x лежит меж x1 и x2. Возможность того, что x Î [x1,x2] равна согласно (2) = g2 - g1, т.е. эта возможность равна длине отрезка [g1,g2] и не находится в зависимости от положения отрезка. Другими словами, величина g(x Разыгрывание случайной величины) воспринимает с равной вероятностью любые значения из отрезка [0,1]. Плотность рассредотачивания таковой случайной величины g равна

Разыгрывание случайной величины

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

Запишем g как двоичную дробь g = 0,a1a2… и на место разрядов числа g после запятой поставим значения, которые выдает генератор, к Разыгрывание случайной величины примеру, g = 0,0011001110101… Так как на первом месте после запятой 0 и 1 возможно окажутся с равной вероятностью, постольку итоговое число может с равной вероятностью оказаться в левой и правой половинах единичного отрезка. Аналогично во 2-м разряде 0 и 1 возможно окажутся с равной вероятностью, т.е. итоговое число возможно окажется в одной Разыгрывание случайной величины из пары четвертей левой либо пары четвертей правой половин и т.д. Таким макаром, двоичная дробь со случайными цифрами 0 и 1 в разрядах вправду с равной вероятностью воспринимает хоть какое значение на полуинтервале [0,1).

Реально моделируется только конечное количество разрядов k. По этой причине рассредотачивание будет не полностью равномерным. Так, математическое Разыгрывание случайной величины ожидание Mg окажется меньше ½ на величину ~2-k -1, т.к. значение g = 0 может быть, а g = 1 нереально. Чтоб этот фактор не сказывался, довольно брать случайные числа при довольно большенном числе разрядов k. Так как в способе статистических испытаний точность ответа обычно не превосходит 0,1% = 10-3, то довольно ограничиться условием 2-k < 10-3, что производится при k > 10. Последнее Разыгрывание случайной величины условие на современных компьютерах выполнено с огромным припасом.

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

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

(3)

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

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

, (4)

где r = 1,2,…

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

Применим данные Разыгрывание случайной величины испытания к генератору умеренно распределенных на отрезке [0,1] случайных чисел, представленному в MATLAB функцией rand. На листинге_№1 приведен код программки по тестированию генератора псевдослучайных чисел rand. Было запрограммировано два теста. Согласно первому тесту, в наборе случайных чисел формата 0,a1a2…, представленных в десятичной форме записи, в k-м разряде подсчитывалась частота попадания числа Разыгрывание случайной величины в левую либо правую половину отрезка [0,1]. Попадание в левую либо правую половину отрезка определялось методом проверки выполнения либо не выполнения неравенства ak £ 4. Согласно второму тесту, оценивался коэффициент корреляции k по формуле (3) меж 2-мя подпоследовательностями {g1,g2,…,gN-1} и {g2,g3,…,gN} одной и той же последовательности {g1,g Разыгрывание случайной величины2,…,gN}.

Листинг_№1

%Тестирование генератора rand умеренно

%распределенных на отрезке [0,1] случайных чисел

clear all

%Определяем наивысшую степень двойки nmax числа

%псевдослучайных чисел и номер разряда k, в каком

%будет подсчитано число попаданий чисел

%последовательности в левую либо правую

%половину отрезка [0,1]

nmax=15; k=10;

%Организуем цикл расчетов с последовательностями

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

for n=1:nmax

%Определяем длину последовательности

%псевдослучайных чисел, как Разыгрывание случайной величины степень двойки

N=2^n;

%Генерируем при помощи функции rand

%последовательность чисел длины N

gamma=rand(1,N);

%Тест №1

%Определяем счетчики числа попаданий в левую cl и

%правую половины cr отрезка [0,1]

cl=0; cr=0;

for i=1:N

%Выделяем k-й разряд случайного числа

g=10^k*gamma(i);

g=mod(g,10);

s=g-mod(g,1);

if s<=4

cl=cl+1;

else

cr=cr Разыгрывание случайной величины+1;

end

end

%Запоминаем число попаданий в левую и правую

%половины отрезка [0,1]

frl(n)=cl/N; frr(n)=cr/N;

%Тест №2

%Определяем две подпоследовательности

%gamma1 и gamma2

for i=1:(N-1)

gamma1(i)=gamma(i);

gamma2(i)=gamma(i+1);

end

%Вычисляем коэффициент корреляции kappa меж

%парой подпоследовательностей

covar=0; s1=0; s2=0;

for i=1:(N-1)

covar=covar+(gamma1(i Разыгрывание случайной величины)-0.5)*(gamma2(i)-0.5);

s1=s1+(gamma1(i)-0.5)^2;

s2=s2+(gamma2(i)-0.5)^2;

end

kappa(n)=covar/sqrt(s1*s2);

lng(n)=N;

end

%Рисуем график числа попаданий в левую и правую

%половины отрезка [0,1] в к-м разряде от длины

%последовательности чисел lng

subplot(1,2,1); semilogx(lng,frl,lng,frr,'--');

%Рисуем график коэффициента корреляции от длины

%последовательности случайных чисел Разыгрывание случайной величины lng

subplot(1,2,2); loglog(lng,абс(kappa));

На рис.1 приведен результат работы кода программки листинга_№1. На левом рисунке представлены два графика частоты попадания k-го разряда в левую либо правую половину отрезка [0,1]. В расчете выбирался десятый разряд, т.е. k =10. Видно, что, по мере роста длины последовательности псевдослучайных чисел, частоты Разыгрывание случайной величины стремятся к предельному значению ½. На правом рисунке представлена зависимость коэффициента корреляции от длины последовательности псевдослучайных чисел. Видно, что, по мере роста длины последовательности, коэффициент корреляции в среднем миниатюризируется и стремится к нулю.

Рис.1. Тестирование MATLAB датчика псевдослучайных чисел rand

Более употребителен метод, связанный с выделением дробной части произведения

, (5)

где {,} — функция возврата Разыгрывание случайной величины дробной части числа, A — считается очень большой константой. Качество псевдослучайных чисел очень находится в зависимости от выбора числа A, в двоичной записи оно обязано иметь довольно случайный вид. Величина исходного приближения g0 слабо оказывает влияние на последовательность псевдослучайных чисел, хотя и находятся такие g0, которые приводят к неудовлетворительным последовательностям. В таблице Разыгрывание случайной величины ниже приведены некие ранее апробированные значения характеристик A и g0.

Некие значения характеристик генератора псевдослучайных чисел (5)
A 513 517 517
g0 2-36 2-40 2-42

На листинге_№2 приведен код программки тестирования датчика псевдослучайных чисел (5) при 2-ух значениях характеристик A и g0.

Листинг_№2

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

%чисел (5) при разных значениях констант A и gamma Разыгрывание случайной величины0

clear all

%Определяем длину последовательности псевдослучайных

%чисел

N=10^4;

%Задаем значения констант A и gamma0

A=[5^13 170]; gamma0=[2^(-36) 0.01];

%Организуем цикл расчетов с разными значениями

%констант A и gamma0

for s=1:length(A)

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

%чисел, согласно методу (5)

gamma(1)=mod(A(s)*gamma0(s),1);

for i=2:N

gamma(i)=mod(A(s)*gamma(i-1),1);

end

%Строим точечную диаграмму в Разыгрывание случайной величины координатах gamma(i-1)

%и gamma(i) соответственно

subplot(1,2,s);

plot(gamma([1:(N-1)]),gamma([2:N]),'.');

%Тест №1

%Определяем счетчики числа попаданий в левую cl и

%правую половины cr отрезка [0,1] в к-ом разряде

k=10; cl=0; cr=0;

for i=1:N

%Выделяем k-й разряд случайного числа

g=10^k*gamma(i);

g=mod(g,10);

s=g-mod(g,1);

if s<=4

cl Разыгрывание случайной величины=cl+1;

else

cr=cr+1;

end

end

%Запоминаем число попаданий в левую и правую

%половины отрезка [0,1]

frl=cl/N; frr=cr/N;

%Тест №2

%Определяем две подпоследовательности

%gamma1 и gamma2

for i=1:(N-1)

gamma1(i)=gamma(i);

gamma2(i)=gamma(i+1);

end

%Вычисляем коэффициент корреляции kappa меж

%парой подпоследовательностей

covar=0; s1=0; s2=0;

for i=1:(N-1)

covar=covar+(gamma Разыгрывание случайной величины1(i)-0.5)*(gamma2(i)-0.5);

s1=s1+(gamma1(i)-0.5)^2;

s2=s2+(gamma2(i)-0.5)^2;

end

kappa=covar/sqrt(s1*s2);

%Выводим при избранных значениях констант A и gamma0

%число попаданий в левую и правую половины отрезка [0,1]

%в k-ом разряде, также коэффициент корреляции kappa

[frl frr kappa]

end

Код программки листинга_№2 генерирует два Разыгрывание случайной величины графика — две точечные диаграммы в координатах , представленных на рис.2. На левой диаграмме точки плотно покрывают единичный квадрат, что гласит о неплохом качестве данного набора псевдослучайных чисел. На правом графике имеет место зацикливание процесса (gi = 0 при i > 47), точки не могут плотно покрыть единичный квадрат, что гласит о нехорошем качестве псевдослучайных Разыгрывание случайной величины чисел при выборе характеристик A = 170 и g0 = 0.01.

Рис.2. Точечные диаграммы рекуррентных алгоритмов (5) при
2-ух разных парах характеристик A и g0

Не считая диаграмм рассеяния, представленных на рис.2, код программки листинга_№2 возвращает частоты попадания десятого разряда псевдослучайных чисел в левую и правую половины отрезка [0,1], также коэффициент корреляции, вычисленный согласно формуле (3). Ниже представлены Разыгрывание случайной величины надлежащие численные значения обоих тестов для 2-ух пар характеристик A и g0:

A = 513, g0 = 2-36:

0.50100000000000 0.49900000000000 -0.00450974364702

A = 170, g0 = 0.01:

0.99780000000000 0.00220000000000 0.99885276017610

Анализ этих данных указывает, что набор псевдослучайных чисел, приобретенный в согласовании с первой парой значений A = 513, g0 = 2-36, удовлетворяет обоим тестам. 2-ая пара значений характеристик A = 170, g0 = 0.01 приводит к набору чисел, которые не удовлетворяют ни Разыгрывание случайной величины первому (превалирует попадание десятого разряда в левую половину отрезка [0,1]), ни второму тестам (коэффициент корреляции близок к единице).

Случайное рассредотачивание. Для разыгрывания случайной величины с неравномерным рассредотачиванием r(x) воспользуемся формулой (2). Выберем случайным образом gi и найдем xi из уравнения

. (6)

В качестве примера разглядим рассредотачивание с . В данном случае уравнение (6) просто решается Разыгрывание случайной величины и находится ответ:

(7)

На листинге_№3 приведен код программки, которая разыгрывает случайные величины xi с законом рассредотачивания .

Листинг_№3

%Разыгрывание случайной величины xi,

%распределенной по закону 0.5*exp(-abs(x))

%согласно формуле (7)

clear all

%Определяем длину последовательности

N=10^4;

%Организуем цикл генерации последовательности

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

%0.5*exp(-abs(x))

for i=1:N

gamma=rand;

if Разыгрывание случайной величины gamma>=0.5

xi(i)=log(1.0/(2-2*gamma));

else

xi(i)=log(2*gamma);

end

end

x=-10:0.05:10;

%Рисуем гистограмму совокупы чисел xi

hist(xi,x);

Итогом работы кода программки листинга_№3 является гистограмма, моделирующая плотность рассредотачивания приобретенной совокупы псевдослучайных чисел. На гистограмме по оси ординат отложено число членов из начальной совокупы, которые попадают в определенный интервал оси Разыгрывание случайной величины абсцисс. Интервал определяется массивом x в программке листинга_№3. Зрительно видна схожесть гистограммы и графика функции плотности рассредотачивания .

Рис.3. Гистограмма рассредотачивания псевдослучайных чисел,
построенных согласно формуле (7)

Интерполяция

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

Пусть определена некая функция y = f(x1,…,xn Разыгрывание случайной величины) в пространстве размерности n. Ее значения определены в верхушках ei, i = 1,2,…,2n единичного куба G(x1,…,xn) = [0,1]n, где eij = 0,1; j = 1,2,…,n, т.е. составляющие векторов могут принимать значения или 0, или 1. Задачка состоит в нахождении методом линейной интерполяции значения функции f в случайной точке (x1,…,xn), лежащей снутри Разыгрывание случайной величины куба либо на его границе.

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

,

(8)

Интерполяция функции в таковой постановке становится неувязкой в связи с тем, что количество слагаемых в интерполяционном выражении вырастает по закону 2n и уже при n = 10 становится больше 103. Чтоб разрешить данное затруднение, воспользуемся способом статистических испытаний, придерживаясь последующего Разыгрывание случайной величины сценария.

По определенному правилу разыграем процесс выбора вектора из набора , находим значение функции в данной точке, дальше повторяем функцию достаточное количество раз, находим среднее значение, которое и будет являться разыскиваемым интерполирующим значением. Итак, пусть задана случайная точка (x1,…,xn) Î G. Построим случайный вектор e = (e1,…,en), составляющие которого Разыгрывание случайной величины принимают значения 0 и 1 с вероятностями P(ei = 0) = 1 - xi, P(ei = 1) = xi, i = 1,…,n. Разыскиваемое интерполирующее значение будет найдено по формуле , где M — обозначает математическое ожидание либо среднее значение функции в случайных верхушках единичного куба при повторных статистических испытаниях.

На листинге_№4 приведен пример решения задачки интерполяции способом Монте-Карло в двумерном случае Разыгрывание случайной величины. В этом случае задачка линейной интерполяции осуществляется при помощи функции (8), которая и выступает в качестве аналитического решения.

Листинг_№4

%Программка моделирования линейной интерполяции в

%единичном квадрате G(x1,x2)=[0,1]x[0,1] при помощи

%способа Монте-Карло

function square

%Избираем длину статистической серии для

%определения значения интерполирующей функции в

%некой точке снутри квадрата

N=1000;

%Определяем число узлов сетки Разыгрывание случайной величины по координатам x1 и x2

n1=21; n2=21;

%Определяем шаги сеток по координатам x1 и x2

h1=1.0/(n1-1); h2=1.0/(n2-1);

%Определяем сетки по координатам x1 и x2

x1=0:h1:1; x2=0:h2:1;

%Определяем значения интерполирующей функции (8) в

%узлах сетки

for i1=1:n1

for i2=1:n2

z(i1,i2)=f_interpl(x Разыгрывание случайной величины1(i1),x2(i2));

end

end

%Рисуем профиль четкой интерполирующей функции (8)

subplot(1,2,1); surf(x2,x1,z);

%Организуем цикл расчета задачки интерполяции

%способом Монте-Карло в узлах сетки

for i1=1:n1

for i2=1:n2

s=0;

for n=1:N

e=rand(1,2)<=[x1(i1) x2(i2)];

s=s+f_vertex(e(1),e(2));

end

Monte_Carlo(i1,i2)=s/N;

end

end

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

%способом Монте-Карло

subplot(1,2,2); surf(x2,x1,Monte_Carlo);

%Определение интерполируемой функции в узлах квадрата

function y=f_vertex(x1,x2)

y=(-1+x1+x2)^2;

%Аналитическая интерполирующая функция

function y=f_interpl(x1,x2)

y=(1-x1)*(1-x2)*f_vertex(0,0)+x1*(1-x2)*f_vertex(1,0)+...

(1-x1)*x2*f_vertex(0,1)+x1*x Разыгрывание случайной величины2*f_vertex(1,1);

Рис.4. Решение задачки линейной интерполяции способом Монте-Карло в
единичном квадрате

На рис.4 приведен результат работы кода программки листинга_№4. На левой фигуре построен профиль интерполирующей функции (8), данной в программке листинга_№4 своими значениями в верхушках единичного квадрата. На правой фигуре построен интерполирующий профиль, приобретенный способом Монте-Карло. Выбиралась умеренная серия статистических испытаний Разыгрывание случайной величины в количестве 103 в расчете на определение значения интерполирующей функции в одной точке.

На листинге_№5 приведен код программки интерполирования функции, данной в верхушках многомерного куба (n = 100).

Листинг_№5

%Программка интерполяции в многомерном кубе

%функции, данной в верхушках куба

function cube

%Определяем размерность куба

n=100;

%Определяем точку, в которую функция

%будет интерполирована

x=0.5*ones(1,n);

k=0;

%Организуем цикл Разыгрывание случайной величины статистических испытаний с

%различной длиной статистических серий

for N=2000:2000:100000

s=0; sd=0;

for i=1:N

e=rand(1,n)<=x;

fv=f_vertex(e);

s=s+fv; sd=sd+fv^2;

end

k=k+1;

%Вычисляем среднее Mf(e1,...,en) значение

%интерполируемой функции в избранной точке x

Mf(k)=s/N;

%Определяем дисперсию Df(e1,...,en)

%интерполируемой Разыгрывание случайной величины функции в избранной точке x

Df(k)=sd/N-Mf(k)^2;

lng(k)=N;

end

%Рисуем зависимость среднего значения интерполируемой

%функции от длины статистической серии N

subplot(1,2,1); semilogx(lng,Mf);

%Рисуем зависимость дисперсии интерполируемой

%функции от длины статистической серии N

subplot(1,2,2); semilogx(lng,Df);

%Определение интерполируемой функции в узлах

%многомерного куба

function y=f_vertex(e)

y=sum(e Разыгрывание случайной величины);

На рис.5 приведен результат работы кода программки листинга_№5. Решалась задачка интерполирования способом Монте-Карло функции, данной в верхушках 100-мерного куба. На левой фигуре изображено значение интерполирующей функции в точке (0.5,…,0.5) зависимо от длины статистической серии. Видно, что колебания происходят вокруг значения 50 со средней амплитудой 0.05 при наибольшей длине статистической серии 105. На правой Разыгрывание случайной величины фигуре изображена дисперсия интерполирующей функции зависимо от длины статистической серии.

Рис.5. Результаты интерполяции способом Монте-Карло функции,
данной в верхушках 100-мерного куба


razmer-vkladov-fizicheskih-lic.html
razmer-zadatka-10-ot-nachalnoj-stoimosti-8-943-000-vosem-millionov-devyatsot-sorok-tri-tisyachi-rublej.html
razmeri-babochek.html