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

• Название: Лабораторная работа 2 Моделирование случайных блужданий Методические указания Случайные блуждания
• Анкор: Компьютерное моделирование
• Дата: 18.04.2022
• Размер: 229.5 Kb.
• Имя файла: Лабораторная работа 2.doc
• Тип: Лабораторная работа; #482752

Лабораторная работа № 2
Моделирование случайных блужданий

1. 
   Методические указания
   
   1. 
      Случайные блуждания
      

Случайное блуждание. Первоначальную формулировку задачи о “случайных блужданиях” предложил Пирсон в 1906 г. Если пьяный делает M шагов равной длины от фонарного столба в произвольных направлениях, то как далеко отойдет он от этого столба? Со времени такой формулировки случайного блуждания (в форме задачи о пьяном пешеходе) модели случайного блуждания получили широкое распространение в технике, физике, биологии и общественных науках (диффузия молекул в газе, броуновское движение коллоидных взвесей в жидкости, моделирование длинных полимерных цепочек, вычисление определенных интегралов, моделирование процессов принятия статистических решений и т.д.).
Одномерное случайное блуждание. Рассмотрим идеализированную одномерную задачу с движением пьяного (пешехода), который начинает двигаться от фонарного столба, расположенного в точке x=0 (см. рис. 1). Все шаги имеют одинаковую длину l. Направление каждого шага пешехода не зависит от направления предыдущего. Пешеход делает шаг вправо с вероятностью p и шаг влево с вероятностью q=1-p. Основной интересующей исследователя величиной является вероятность P_M(x) того, что после М шагов пешеход окажется на расстоянии x от фонарного столба.



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

, . (20)

Двумерное случайное блуждание. В моделях случайного блуждания двумерный случай является наиболее важным, т.к. применяется не только к блужданию пьяных или движению молекул. При двумерном случайном блуждании на каждом шаге по времени осуществляется движение случайным образом равновероятно в одном из четырех возможных направлений: на север, юг, восток или запад (см. рис. 2). Движение начинается из начальной точки H, совпадающей с началом координат (X=0; Y=0) и заканчивается через Mшагов (на рис. 3 показан возможный путь за M=12 шагов) в точке К.


Рисунок 2 – Двумерное случайное блуждание

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

2. 
   Планирование эксперимента для оценки с заданной точностью выборочной дисперсии
   

При ограниченном ресурсе времени моделирования первейшей задачей исследования является получение ответа на вопрос: как много выборочных значений следует взять во время моделирования, чтобы обеспечить достаточную статистическую значимость? Поскольку разбросы выборочных значений случайны, то обусловленная ими некоторая неточность результата эксперимента в значительной мере определяется размером выборки. Задача определения такого размера выборки, который позволяет обеспечить желаемый уровень точности и в то же время минимальную стоимость моделирования, является чрезвычайно важной.
1.2.1 Начальные условия и их влияние на достижение установившегося режима
Первая проблема при проведении машинного эксперимента заключается в максимальном исключении влияния начального периода работы машинной модели, что в значительной степени определяется начальными условиями запуска модели. При этом типичное поведение оцениваемого параметра при изменении объема N выборки показано на рисунке 1.

Существуют три основные пути уменьшения возможного влияния начального периода на получаемые данные.

1 Использование достаточно длинных вычислительных прогонов, чтобы число данных переходного периода было незначительно по сравнению с числом данных установившегося режима.

2 Исключение из рассмотрения начального периода прогона.

3 Выбор для установившегося состояния такого начального условия, которое ближе к типичному, и тем самым уменьшение переходного периода.
1.2.2 Оценивание среднего значения выборочной совокупности
Задача состоит в получении оценки неизвестного математического ожидания μ некоторого исследуемого параметра по выборочной средней . Выборочную среднюю можно рассматривать как случайную величину ( изменяется от выборки к выборке) и выборочные значения признака x₁, x₂, …, x_N – как одинаково распределенные независимые случайные величины X₁, X₂, …, X_N с математическим ожиданием μ и среднеквадратическим отклонением σ. Будем использовать предложение о независимости и нормальном распределении откликов модели. Это предположение основано на применении центральной предельной теоремы теории вероятностей, сущность которой состоит в утверждении, что распределение случайной величины, являющейся суммой большого числа независимых величин с одинаковыми распределениями вероятностей, близко к нормальному распределению. В более поздних работах показано, что требования независимости и одинаковой распределенности не являются необходимыми. Часто бывает достаточно, чтобы отклик представлял собой сумму большого числа небольших эффектов. Поэтому переменная отклика сложной имитационной модели, являющаяся результатом действия большого числа случайных переменных, распределена приблизительно нормально. В результате этого, если случайная величина Xраспределена нормально, то выборочная средняя , найденная по независимым наблюдениям, также распределена нормально с математическим ожиданием

M( )=μ

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

σ( )=σ/γ

Потребуем, чтобы выполнялось соотношение

p(μ-d≤ ≤μ+d)<γ, (1)

где – выборочное значение средней;

γ – вероятность того, что интервал μ d содержит (надежность, задаваемая исследователем);

d – точность оценки.

Задаваемая надежность γоднозначно связана с уровнем значимости α получаемой оценки формулой

γ=1-α.

Если требуется оценить математическое ожидание μ наперед заданной точностью dи надежностьюγ(уровнем значимости α), то минимальный объем выборки, который обеспечит эту точность, находим по формуле

, (2)

где число t – определяется из равенства 2Ф(t)=γ или Ф(t)=γ/2по таблице функции Лапласа.

Если неизвестны точность d и среднеквадратическое отклонение σ, то задачу можно поставить так: каков должен быть размер выборки, чтобы искомая оценка с вероятностью γ=1-α находилась в пределах μ σ, где σ – некоторая доля σ (например, σ = σ/2; σ/4; σ/6; σ/10; σ/20; …).

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

, (3)

где оценка s² дисперсии получена по формуле

;

n – размер выборки пробного эксперимента.
1.2.3 Применение теоремы Чебышева
Неравенство Чебышева говорит, что при заданном числе k(не меньшем единицы) и произвольной выборке x₁, x₂, …, x_N размера N по меньшей мере 1-1/k измерений находятся вблизи среднего значения на расстоянии не более k среднеквадратических отклонений. Это неравенство справедливо для любых распределений. Если не исходить из предположения о нормальном распределении выхода (которое не всегда выполняется с достаточной точностью), можно воспользоваться неравенством Чебышева, которое имеет вид

. (4)

Если задаться условием, при котором оценка должна находиться в интервале μ σ/m (m=2, 4, 6, 10, …) с вероятностью γ=1-α, т.е.

, (5)

тогда, используя уравнение (1), получаем

, (6)

так как

Отсюда находим требуемый размер выборки машинного эксперимента

. (7)

Полученный размер выборки существенно больше того, который оказывается достаточным в случае нормального распределения совокупности. В таблице 1 приведены размеры выборки при различных значениях dпри α=0.05 (γ=0.95).

Таблица 1 – Размеры выборки

Отклонение	Необходимый объем выборки N
	По центральной предельной теореме	По теореме Чебышева
σ/2	15	80
σ/4	61	320
σ/6	138	720
σ/8	246	1280
σ/10	384	2000
σ/12	553	2880
σ/20	1537	8000

1.2.4 Оценивание процентных отношений
Во многих случаях целью машинного эксперимента является получение оценки вероятности появления p=P(A) некоторого события A, определяемого состояниями процесса функционирования исследуемой системы. В качестве оценки вероятности p выступает частость , где θ – число положительных исходов.

Представим частость в виде

,

где частость в данной реализации из N наблюдений является случайной величиной, принимающей значения x_i=1 с вероятностью p и x_i=0 с дополнительной вероятностью 1-p, тогда

.

По теореме Лапласа частость θ/N при достаточно больших N можно рассматривать как случайную величину, описываемую нормальным законно распределения вероятности с математическим ожиданием и дисперсией . Поэтому точность ε и достоверность γ оценок связаны с количеством N реализаций равенством

,

из которого объем выборки, необходимый для получения оценки с точностью ε и достоверностью γ, определим в виде

. (9)

При тактическом планировании эксперимента, когда значение p неизвестно, проводят предварительное моделирование для произвольного значения n. По результатам предварительного моделирования p₀=θ/n, а затем по (9) вычисляют, используя вместо p значение p₀, необходимое количество реализаций N. Такая процедура оценки N может выполняться несколько раз в ходе машинного эксперимента.

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

.

Тогда соотношение (9) примет вид

. (10)

Соотношение (10) для объема выборки статистического моделирования редких событий, выражающееся в том, что для оценивания малых вероятностей p с высокой точностью необходимо очень большое число реализаций. В практических случаях для оценивания вероятностей порядка 10^-k целесообразно количество реализаций выбирать равным 10^k+1.
1.2.5 Оценивание дисперсии совокупности
В качестве показателя эффективности системы может выступать дисперсия σ², оценку которой s² требуется получить в результате проведения машинных экспериментов с некоторой надежностью γ=1-α.

Потребуем, чтобы выполнялось соотношение

P{s²-d≤σ²≤s²+d}-γ.

Преобразуем двойное неравенство

s²-d≤σ²≤s²+d

в равносильное

s²(1-q)≤σ²≤s²(1+q),

где q=d/s² – число, характеризующее степень близости оценки s² к истинной дисперсии σ².

Для удобства пользования введем в рассмотрение χ² – статистику

,

которая распределена по закону χ² (хи-квадрат) с N-1 степенями свободы.

Плотность распределения χ² имеет вид

,

где r(λ)= – гамма-функция; в частности, r(n+1)=n!.

Распределение нормированной величины (χ²-N)/ стремится к стандартному нормальному распределению

,

откуда можно получить уравнение



или

,

где t – квантиль нормального распределения, значение которого находится из равенства 2Ф(t)=λ по таблице функции Лапласа.
1.2.6 Сравнение двух распределений
При исследовании результатов машинного моделирования часто возникает задача проверки близости распределения отклика модели к некоторому другому распределению. Для проверки близости двух распределений можно воспользоваться критерием Колмогорова-Смирнова. Задаваясь требуемой точностью (абсолютной ошибкой) d при заданном уровне значимости α, можно вычислить необходимый объем выборки по формулам:

; (13)

; (14)

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

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

(16)

, (17)

где - дисперсия совокупности;

ρ_p,x – p-й коэффициент автокорреляции;

m – максимальная глубина рассматриваемой автокорреляции, p=1, 2, …, m.

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

; (18)

где – дисперсия N измерений в пробном эксперименте.

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

,

где - относительная погрешность истинного среднего.

Максимальную глубину m вычисляемых коэффициентов корреляции выбирают на практике равной примерно 10% от числа N измерений. При выполнении задания по данной лабораторной работе достаточно выбрать m=5.
2 Порядок выполнения работы
а) Каждое задание предполагает разработку программной имитационной модели случайного блуждания, с помощью которой могут быть получены необходимые результаты.

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

в) Во втором варианте выполняется планирование эксперимента для оценки с заданной точностью выборочной дисперсии.
1. Простое случайное блуждание с поглощающими экранами. Пусть заданы целые числа a>0 и b>0; блуждание прекращается, если x=b или x=-a. Составить машинную модель для определения времени блуждания. Для проверки правильности модели вычислить оценку вероятности того, что блуждание прекратится возле правой границы и сравнить с полученной вероятностью.

. (1)

При q=p=0.5 имеем
2. Модель падения дождевой капли. При воздействии случайных порывов резкого ветра падение дождевой капли можно моделировать случайным блужданием на квадратной решетке (см. рис. 3). Движение начинается из узла, расположенного на расстоянии h=yнад горизонтальной линией (поверхностью земли). Вероятность p↓ шага “вниз” больше вероятности p↑ шага “вверх”. Вероятности скачков целесообразно выбрать равными p↓=0.5; p↑=0.1; p← = p→ =0.2.

Определите время τ, за которое капля достигнет горизонтальную прямую (поверхность земли y=0) и функциональную зависимость τ от h (4-6 значений).



Рисунок 3 – Модель падения дождевой капли
3. Пчелы на квадратной решетке. “Рой” из V “пчел” изначально расположен в единичном круге с центром в начале координат. На каждом шаге по времени каждая пчела движется случайным образом равновероятно в одном из четырех направлений: на север, юг, восток и запад. Определите расстояние, на которое удаляется отдельная пчела за М=8 шагов. В течение каждого временного интервала каждая пчела делает шаг единичной длины. Усреднение выполняется по Nпчелам. Сравните с данными моделирования для заданий 5 и 6.
4. Кристаллы с дефектами. Кристаллическое твердое тело никогда не является совершенным, а содержит разнообразные дефекты. Простейшим дефектом является вакансия решетки, т.е. отсутствие атома в узле решетки и помещение дополнительного атома на поверхность. При конечной температуре в реальном кристалле всегда имеется некоторое число решеточных вакансий. Во многих случаях вакансия диффундирует (движется), меняясь местами с соседними атомами случайным образом. Предположите, что вакансия в начальный момент времени t=0 расположена в центре окружности радиусом r, и определите время, за которое вакансия достигает поверхности металла, находящейся на расстоянии r (r выбрать произвольно).
5. Блуждание на треугольной решетке. Составьте имитационную модель случайного блуждания пчелы на треугольной решетке (см. рис. 4). На каждом шаге по времени пчела движется равновероятно в одном из шести возможных направлений. На какое расстояние удаляется пчела за М=8 шагов. Полученные результаты сравните с данными моделирования для заданий 3 и 6.


Рисунок 4 – Блуждание на треугольной решетке
6. Блуждание на сотах. Составьте имитационную модель случайного блуждания на сотах (см. рис. 5). На каждом шаге по времени пчела движется равновероятно в одном из трех направлений. На какое расстояние удаляется пчела за M=8 шагов. Сравните результаты с данными моделирования для заданий 3 и 5.


Рисунок 5 – Блуждание на сотах
7. Случайное блуждание на трехмерной решетке. Оцените расстояние, на которое удаляется частица, равновероятно блуждающая по трехмерной решетке. Число шагов блуждания M=10. Параллельно исследуемому процессу определите удаление от начального состояния отдельно по всем трем составляющим координатам.