Введение в компьютерное моделирование. Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие
 Скачать 1.03 Mb.
|
|
Задачи на самостоятельную работу 1. Пусть на планете Оз если начался дождь, то он длится всегда, определите T, и B. 2. Пусть вероятность перехода влево равна 1/3, а вправо 2/3 для пьяницы. Определите T, и B. 3. Число Х случайно выбирается из чисел 1, 2, 3, 4 и 5. После то- го как оно выбрано, следующее число выбирается случайным обра- 47 зом среди тех чисел, которые больше Х. Процесс завершается, ко- гда выбранным числом оказывается 1. Состояние марковского про- цесса задаются числами, которые могут быть выбраны. Покажите, что 1 0 0 0 1 1 2 0 0 1 1 2 1 3 0 1 1 2 1 3 1 4 T I , где I – единичная матрица 4-го порядка. Каково среднее число выборов? (Ответ 25/12). 4. Три танка ведут бой, каждый с двумя другими. Танк А уни- чтожает танк, по которому ведет огонь с вероятностью 1/3, танк B – с вероятностью 1/3, танк C – с вероятностью 1/6. Открывают огонь одновременно, и каждый стреляет по сильнейшему из неуни- чтоженных к этому моменту танку. Найдите T, и B. 5.3. Цепи Маркова в социологии [5] Испытуемый среди других 7 человек участвует в эксперименте по зрительному восприятию: необходимо выбрать из 3-х сравнива- емых линий ту, которая равна эталонной. Испытуемый отвечает последним после 7 одинаковых неправильных ответов. С одной стороны он должен ответить согласно своему восприятию, а с дру- гой стороны согласиться с единодушным мнением группы. В экс- перименте исследуется последовательность ответов в серии испы- таний. Можно построить вероятностную модель, которая предска- жет некоторые средние свойства. Каждый из 33 испытуемых под- вергается 35 испытаниям, и ответы могут быть такого вида aaabbаааbbbааааb..........аааааааа начальный отрезок конечный, где а – правильный ответ, b – неправильный. Конечным ответом (а или b) назовем последний 35-й ответ и конечным отрезком – по- следовательность совпадающих с последним ответов. Какие вели- чины пригодны для наблюдения в такой серии? Начнем с подсчета переходов, пусть aa n – число переходов от а к а в начальном отрез- 48 ке, ab n – число переходов от а к b, аналогичное значение имеют ba n и bb n Эти величины однозначны за исключением первого ответа, его будем классифицировать как аа переход, добавляя нулевой ответ а спереди. Тогда в приведенной последовательности 8 aa n , 3 ab n , 3 ba n и 3 bb n . Зная эти соотношения, можно опреде- лить другие. Например, если a n – общее число случаев, когда в начальном отрезке дается ответ а и b n – общее число, когда в нача- ле ответ b, имеются соотношения , a aa ab b ba bb n n n n n n , длина начального отрезка равна a b n n , длина конечного отрезка равна 36 a b n n . Чтобы знать общее число ответов а, нужно знать, что если ab ba n n , то конечный ответ должен быть а, если 1 ab ba n n , то конечный ответ – b. Рассмотрим теперь всех 33 испытуемых. Пусть aa n – общее число а–а переходов для всех ис- пытуемых, тогда первые 2 соотношения остаются справедливыми, только a n теперь обозначает общее количество всех ответов а во всех начальных отрезках, b n – то же для b и их сумма есть общая длина всех отрезков. Пусть n – число всех испытуемых (n = 33), t а – число конечных ответов а, t b – число конечных ответов b. Тогда b ab ba t n n и a b t n t Задачей нашей модели является описание и предсказание таких наблюдаемых величин. В эксперименте Коэна было получено 196, 117, 106, 102, 313, 208, 22, 11, 33. aa ab ba bb a b a b n n n n n n t t n Поскольку выбор n произволен, а результат сильно меняется, то целью будет предсказание усредненных величин b t n и aa n n Для интерпретации эксперимента предполагается гипотеза, что ис- пытуемый может находиться в одном из 4 психических состояний: 1) нонконформизм, 2) временный нонконформизм, 3) временный конформизм, 4) конформизм. В начальном состоянии испытуемый 49 предполагается находящимся в состоянии 2. При последователь- ных испытаниях изменение состояния может быть описано с по- мощью цепи Маркова с четырьмя состояниями и матрицей вероят- ностей переходов вида 1 2 3 4 1 2 21 22 23 3 32 33 34 4 1 0 0 0 0 0 0 0 1 p p p P p p p Переходы из состояния 2 в 4 и из 3 в 1 исключены. Из состояний 1 и 4 нет переходов, так как они являются поглощающими. Испыту- емый дает нонконформные ответы а, находясь в состоянии 1 и 2 и конформные ответы b – в состоянии 3 и 4. Мы не знаем точно, где на конечном отрезке испытуемый достигает состояние 1 или 4. Мы знаем лишь, что он точно придет в одно из этих состояний и для этого достаточно 35 испытаний. Приводя матрицу Р к канониче- скому виду, можно показать, что матричные элементы ij p связаны с математическими ожиданиями введенных выше величин следу- ющим образом: 21 1 1 ab ab ba aa ab ba M M M p M M M , 22 aa aa ab M p M M , 2 23 1 ab aa ab ba M p M M M , 2 32 ba ab ba bb M p M M M , 33 bb ba bb M p M M , 34 ba ab ba ab ba bb M M M p M M M , где , , , ab ab aa aa ba ba bb bb M M n n M M n n M M n n M M n n , Считая, что при больших n величина ab n n должна быть близка к Мав и т.д., можно вычислить из экспериментальных данных Маа=196/33,Мав=117/33, Мва=106/33, Мвв=102/33, что дает следующую матрицу Р. 50 1 0 0 0 0, 06 0, 63 0, 31 0 0 0, 46 0, 49 0, 05 0 0 0 1 P Приводя матрицу к каноническому виду, получим 4 3 2 1 23 22 21 34 33 12 1 4 2 3 0 0 0 1 1 0 0 0 0 0 0 I P p p R Q p p p p Тогда фундаментальная матрица N будет 2 3 1 2 1 32 23 33 23 3 32 33 32 22 1 1 1 1 p p p p P I Q p p p p , где 22 33 23 32 1 1 p p p p . Матрица вероятностей погло- щения B = NR будет равна 1 4 2 23 34 21 33 3 34 22 32 21 1 1 p p p p B p p p p Согласно вышеизложенной теории вероятность поглощения в со- стояние 4 из начального состояния 2 равна 24 b , а в состояние 1 – 21 b . Так как процесс начинается в состоянии 2, коэффициент 23 n матрицы N дает среднее значение общего числа опытов, при которых испытуемый находится в психическом состоянии 3 во время эксперимента. Сделаем предсказание о числе случаев, когда испытуемый ме- няет ответы от правильного к неправильному и наоборот. Среднее число таких случаев равно ab ba M M . Мы можем вычислить веро- ятность ровно 2k изменений, которая дается формулой 21 22 23 32 22 33 2 1 1 1 k P k p p p p p p (32) 51 Так как значения для больших k невелики, то мы скомбинируем четные и нечетные случаи и будем рассматривать их отдельно, так как четное k соответствует конечному ответу а, а нечетное – b. Сравнение результатов предсказания с экспериментом дано в табл. 5. Таблица 5 K Количество испытуемых изменивших ответ k раз Предсказанное число 0 10 5,22 1 1 2,61 2 или 4 5 7,01 3 или 5 4 3,51 6,8 или 10 2 5,41 7,9 или 11 1 2,71 Большие четные 5 4,30 Большие нечетные 5 2,15 Задачи на самостоятельную работу 1. Эксперимент с 30 участниками дал 120, 140 aa ab n n , 120, 114 ba bb n n . Оцените матрицу Р и определите, какова веро- ятность конформизма испытуемого в конце опыта. 2. Решите ту же задачу для 150 ab n 3. В эксперименте с 40 участниками получена матрица Р вида 1 0 0 0 7 136 10 17 49 136 0 0 24 49 3 7 4 49 0 0 0 1 P Каковы наблюдаемые значения , , , , , ab aa ba bb a b n n n n t t ? 5.4. Численная имитация марковского процесса Рассмотрим простой способ численной имитации марковского процесса с использованием строк переходной матрицы Р. Считает- ся, что за один такт процесс переходит из состояния i в другое со- стояние j, если 52 1 1 1 j j k ik k ik p r p , (33) где через r обозначено псевдослучайное число из интервала [0,1]. Таким образом, последовательность псевдослучайных чисел, гене- рируемая в машине с помощью датчика, порождает реализацию марковской цепи. Ниже представлена программа машинной имита- ции марковского процесса, где М – число состояний, N – моделируемое число переходов, I – начальное состояние процесса. Матрица Q получается элементарным преобразованием матрицы Р. Ее строки задают распределение кумулятивных вероятностей. Про- грамма определяет и выводит на печать номер состояния процесса в каждый из N рассматриваемых моментов времени. 10 INPUT «введите M,N,I»; M, N, I 20 FOR I=1 TO M 30 FOR J=1 TO M 40 READ Q(I,J) 50 DATA элементы матрицы Q 60 FOR L=1 TO N 70 A=RND(1) 80 FOR J=1 TO M 90 IF Q(I,J)-A>=0 THEN 110 100 NEXT J 110 I=J 120 PRINT I 130 NEXT L 6. С ТАНДАРТНЫЕ РАСПРЕДЕЛЕНИЯ СЛУЧАЙНЫХ ВЕЛИЧИН И ИХ ПОЛУЧЕНИЕ [3] При рассмотрении дискретных или непрерывных случайных процессов вводят функцию F(x) , называемую кумулятивной функ- цией распределения величины X. Эта функция задает вероятность того, что случайная величина X принимает значение, не превосхо- дящее числа х. Если случайная величина дискретна, т.е. X прини- мает конечное число значений, то функция F(x) является ступенча- той. Если F(x) непрерывна, то ее можно продифференцировать и получить функцию f x dF x dx . Функция f(x) называется 53 функцией плотности вероятностей. Кумулятивную функцию рас- пределения можно определить как x F x P X x f t dt , (34) где F(x) изменяется на отрезке (0,1), а f(t) представляет собой зна- чение функции плотности вероятностей случайной величины Х при X = t. Кумулятивная функция распределения дискретной случайной величины Х задается аналогично F(x) в виде 0 x t F x P X x f t , (35) где f(t) – частота или функция вероятностей, которая определяется для целых значений аргумента t по формуле , 0,1, 2, f t P X t t (36) При генерировании случайных величин, имеющих различные функции распределения, в качестве исходного используются рав- номерно распределенные случайные величины. Их будем обозна- чить через r, 0 1, r F r r . Методы генерирования случайных величин равномерно распределенных на [0, 1] даны нами ранее в разделе 3. Если требуется генерировать случайные числа x i из некоторой статистической совокупности с функцией плотности вероятностей f(x), то сначала строят кумулятивную функцию распределения F(x) (рис. 14). 1. Строим график или таблицу интегральной функции распреде- ления на основе ряда чисел, отражающих исследуемый процесс, значения случайной переменной откладываются по оси х, а значе- ние вероятности (от 0 до 1) по оси у. 2. С помощью генератора случайных чисел выбираем случайное число в пределах от 0 до 1. 3. Проводим прямую до пересечения с кривой F(x) и снимаем значение х по оси х – оно берется как выбранное. 4. Повторяем процесс столько раз, сколько необходимо. 54 Рис. 14. Кумулятивная функция распределения Пусть имеем систему, в которой за каждый 10-минутный период число клиентов нуждающихся в обслуживании соответствует рас- пределению, приведенному в табл. 6. Таблица 6 Число клиентов Вероятность Кумулятивная вероятность 0 0,40 0,40 1 0,25 0,65 2 0,20 0,85 3 0,15 1,00 Рис. 15. Распределение кумулятивных вероятностей Предположим, что мы хотим провести эксперимент для 5 пери- одов времени. Строим график распределения кумулятивной веро- ятности (рис. 15). 55 Генерируем 5 двузначных целых чисел из интервала 00–99 и делим их на 100. Каждое из получившихся чисел используем для опреде- ления числа клиентов, появляющихся в данный момент времени. Если эти числа, например, равны 09, 54, 42, 80 и 20, то получаем следующую табл. 7. Таблица 7 Период времени Случайное число Число клиентов 1 0,09 0 2 0,54 1 3 0,42 1 4 0,80 2 5 0,20 0 Для непрерывной функции F(x), так как F(x) изменяется на проме- жутке [0,1], как показано на рис. 15, то чтобы получить случайные числа с этим распределением, можно также генерировать равно- мерно распределенные числа r и полагать F(х) = r. Величина х од- нозначно определяется из этого соотношения. Следовательно, для конкретного значения r, скажем 0 r , можно найти величину х, в данном случае 0 x , связанную с 0 r обратной функцией к F 1 0 0 x F r , (37) где 1 F r – братное отображение величины r, заданной на еди- ничном интервале, в область изменения х. Математически этот ме- тод можно выразить следующим образом: если мы генерируем равномерно распределенные случайные числа и ставим их в соот- ветствие данной функции F(x), т.е. x r F x f t dt , то 1 P X x F x P r F x P F r x (38) и, следовательно, 1 F r есть случайная величина с функцией плотности вероятностей f x . Это равносильно выражению вели- чины х через значение r с помощью (37). Такая процедура называ- ется методом обратного преобразования. 56 6.1 Равномерное распределение Функция плотности вероятностей равномерного распределения на промежутке [a, b] имеет вид 1 f x b a , (39) для a x b и 0 иначе. График равномерного распределения изображен на рис. 16. Рис. 16. Равномерное распределение Здесь х – случайная величина, определенная на интервале [a, b]. Это самое простое непрерывное распределение с функцией плот- ности вероятностей постоянной на интервале [a, b] и равной нулю вне его. Оно часто применяется в имитационных методах, так как простое и используется для получения других распределений. Ку- мулятивная функция распределения F(x) равномерно распределен- ной случайной величины X есть 1 , 0 1 x a F x b a dx x a b a F x (40) Для имитации равномерного распределения на интервале [a, b] сначала генерируются случайные числа r, равномерно распреде- ленные в [0, 1], затем вычисляют х по формуле , 0 1 x a b a r r (41) Каждое случайное число однозначно определяет реализацию рав- номерно распределенной случайной величины Х. Программа генерирования равномерного распределения, задан- ного на интервале [a, b], имеет вид |