Лекция генератори на случайни числа. Поредица от случайни числа със



Дата24.07.2016
Размер77.67 Kb.
ТипЛекция




ЛЕКЦИЯ 8. Генератори на случайни числа. Поредица от случайни числа със

зададено разпределение. Метод на фон Нойман

Много числови симулации се нуждаят от генератор на случайни числа (ГСЧ) или за създаване на случайни начални условия или при самата симулация. Ще наричаме една поредица от числа r1, r2, … случайни ако няма корелация между числата в поредицата. Истински случайна поредица от числа, която не може да се повтори може да се създаде от някакъв физически процес, например шума на транзисторите. Компютърът, обаче е напълно детерминистично устройство и в една програма няма нищо случайно. Затова под ГСЧ трябва да се разбира програма на генератор на псевдо-случайни числа, която може да генерира последователност от числа, която има много голям период на повторение и имитира дадено разпределение. В тази лекция ще разгледаме някои основни ГСЧ, които често се използват при компютърните симулации.


ГСЧ с равномерно разпределение


Стандартният компютърен ГСЧ генерира равномерно разпределени числа в интервала [0, 1]. Има три основни критерия за оценка на един ГСЧ с равномерно разпределение:

  1. Един добър ГСЧ трябва да има дълъг период на повтаряемост,

който да е равен или близък до обхвата на целите числа за дадената платформа. Например за 32-битов компютър един добър генератор трябва да има период близък до 231–1=2, 147,483,647. Обхвата на целите числа за 32-битов компютър е

[-231 , 231–1], където един бит се използва за знака на целите числа.



  1. Второто изискване е генератора да има добра корелационна

характеристика. За целта корелацията между две произволни числа в поредицата трябва да е много малка. Един начин да оценим корелационната функция n xn+i> е да нанесем числата xn и xn+i върху равнината (x,y). Един добър ГСЧ трябва да даде равномерно разпределение на точките в равнината за всяко i0. Лошият генератор ще произведе ивици, линии решетки или други структури и неравномерни разпределения.

Фиг.1 Корелация между двойките числа (x,y)=(ri, ri+1) за лош генератор (ляво)

и липса на корелация за добър генератор (дясно)


  1. Накрая, добрият ГСЧ трябва да е бърз. Тъй като в

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

Най-разпространения алгоритъм за ГСЧ е т.нар. линеен конгруентен алгоритъм, за който членовете в поредицата се определят от едно цяло число x0 според следната рекурсивна връзка:



(1)
Където числата m>0, a>0 и с са цели числа наричани съответно модулус, множител и адитивна константа. Тук операцията mod връща остатъка от делението т.е. цяло число. Ако искаме резултатът да е число в интервала un [0,1] трябва да извършим операцията un = xn/m . Ако с=0 генераторът се нарича мултипликативен линеен конгруентен генератор.

Зад 3.1 Сравняване на лош и добър ГСЧ с равномерно разпределение


С педагогическа цел ще приложим алгоритъма на конгруентен генератор с неподходящи коефициенти: а=57;с=1;m=256; r0=11.

  • Определете периода на поредицата т.е. колко числа се генерират преди поредицата да започне да се повтаря.

  • Проверете за наличието на корелация като разгледате точки в равнинета, чиито координати са последователни числа от поредицата: (xi,yi)=(r2i-1,r2i), i=1,2,…Използвайте в MATLAB командата scatterplot(x,y).

  • Направете същата графична проверка за наличието на корелация като използвате вградения генератор на случайни числа.

  • Реализирайте алгоритъм от горния тип, който има много добри свойства за 32-битов компютър и е достатъчно бърз. Този алгоритъм е предложен от Park & Miller през 1988 г Приемаме а=75 = 16,807; с=0;m=231–1=2, 147,483,647. Ако приложим директно горния алгоритъм могат да възникнат някои проблеми. Например, ако някоя стойност излезе извън обхвата от стойности, компютъра ще връща грешни стойности без да дава съобщение за грешка. Затова предлагания алгоритъм е малко усложнен, но може да модулира числата с период m=231–1.

  1. Дефинираме константи: а=75 ; m=231–1; q=m/a=127773; r=m%a=2836

Тук / връща цялата част от деленето, а % връща остатъка от деленето

  1. Задаваме начална стойност на поредицата seed=1

  2. Дефинираме цяла променлива h=seed/q

  3. Дефинираме цяла променлива i=seed%q

  4. Дефинираме цяла променлива t=a*i - r*h

  5. if(t>0) seed=t

  6. Else seed=t+m

  7. Return seed/(float)m // за да бъде резултата в интервала [0,1]

За проверка на програмата при начално seed=1 след 10,000 стъпки

трябва да получим seed=1,043,618,065 (без последната операция в програмата).



За да може генераторът всеки път да генерира различна поредица от числа трябва да можем да задаваме всеки път различен «зародиш» (начална стойност на seed). Това може да стане като се използва вътрешното време на компютъра. Например за повечето компютри величините година, месец, ден, час, минута, секунда се изменят в указаните интервали:

Year 0  y  99

Month 1  m  12


Day 1  d 31

Hour 0  h  23

Minute 0  min  59

Second 0  s 5 9



Зад. 3.2 Усъвършенствайте програма 3.1 като задавате начална стойност на поредицата по следната формула:

Seed=y + 70(m + 12{d + 31[h + 23{min + 59s)]})

Това число е в интервала [0, 231–1] и гарантира, че в продължение на 100 години ще получаваме различни серий от числа, ако времето между две поредици се различава поне с една секунда.

Може да се направи тест за равномерност като се оцени к-тия момент на разпределението:



(2)

Ако се изпълнява равенство (2) знаем че разпределението е равномерно. Ако отклонението от (2) варира както 1/√N знаем също че разпределението е случайно.



ГСЧ с експоненциално разпределение

След като разполагаме с ГСЧ с равномерно разпределние можем да създадем различни неравномерни разпределения, например експоненциално или гаусово разпределение. Експоненциалното разпределение в най-простия си вид се дава от:




(3)


Например ако системата има енергетични нива Е0, Е1, …ЕN вероятноста системата да се намира в състояние с енергетично ниво Еi при температура Т се дава от:


(4)


Ако изберем кТ като енергетична единица и Е0 като нулева точка то уравнение (4) се свежда до (3).

Един начин за генериране на експоненциално разпределение е като използваме равномерното разпределение. Нека имаме равномерно разпределение f(y)=1 за y[0,1], което можем да свържем с експоненциалното разпределение както следва:

(5)
От където след интегриране следва:

(6)
Ако положим y(0)=0 получаваме:

(7)
Това равенство свързва равномерното разпределение по y с експоненциално разпределение по x.

Зад. 3.3 Използвайки горната връзка и програма 3.1 за да напишете програма на ГСЧ с експоненциално разпределение. Може да се използва програмата за ГСЧ от предишната задача или вграденият в Java ГСЧ: Math.random(), който генерира равномерно разпределени случайни числа в интервала между 0 и 1. За да генерираме поредица от равномерно разпределени случайни цели числа между 0 и N-1 можем да използваме командата:

int i=(int)(N*random());



ГСЧ с гаусово разпределение

Друго полезно разпределение е Гаусовото разпределение:




(8)


Където е статистическото отклонение, което за простота ще положим равно на единица. Ако искаме да получим 1 в получения генератор

трябва да рескалираме променливата като умножим x c . Ще използваме равномерното разпределение f()=1 за [0,2] и едно експоненциално разпределение p(t)=exp(-t) за t[0,] и с помощта на тези две познати разпределения ще създадем две независими Гаусови разпределения g(x) и g(y). Можем да свържем произведението на равномерно и експоненциално разпределения с произведение на двете Гаусови разпределения както следва:




(9)


Което след заместване дава:


(10)


Това уравнение може да се разглежда като трансформация от полярна координатна система (,) с =2t в правоъгълна координатна система (x,y):


(11)
Зад 3.4 Като използвате уравнения (11) и получените програми (като функции или подпрограми) за равномерно и експоненциално разпределния напишете програма, която генерира две Гаусови разпределения.



Общ метод за генериране на произволно разпределение w(x)

Изискването към функцията на разпределение е следното:




(12)
Правим смяна на променливите, като новата променлива y е функция на

старата променлива x определена от следната зависимост:


(13)
Недостатък на този метод е, че трябва първо да определим функцията y(x) като интегрираме w(x), след което трябва да намерим обратната функция x(y), което не винаги е лесно а понякога даже е невъзможно.



Зад. 3.5 Да се програмира ГСЧ с разпределение w(x)=(1/3)(4-2x).

Упътване:По горната формула определяме y=(1/3)x(4-x) и оттам обратната функция х=2-(4-3y)1/2; x(y=0)=0; x(y=1)=1.


Общ метод за генериране на произволно разпределение w(x) по

метода на фон Нойман (метод на приемане или отхвърляне)

Друг удобен и универсален метод за генериране на едно- или многомерни случайни величини с неравномерно разпределение е метода на приемане или отхвърляне предложен от фон Нойман.

Геометричната интерпретация на метода е дадена на фиг.2 Нека искаме да генерираме случайна величина x в интервала [0,1] с вероятност w(x) и нека w0 е константа, за която е изпълнено условието w0 > w(x) в целия интервал. Удобно е да изберем w0 = wmax. Нека сега генерираме точки в двумерната област (w, x), които равномерно запълват повърхността под праватa w0, а след това приемем само тези точки които лежат под кривата w(x). Тогава приетите точки ще бъдат разпределени с вероятност w(x).

Фиг.2 Метод на фон Нойман



На практика това означава следното: взимаме две случайни величини xi и , при което първата величина е разпределена равномерно между wmin и w0 , а втората равномерно между 0 и 1. Стойноста на xi се приема ако  < w(xi) и се отхвърля в противния случай. След това се генерира нова двойка числа (xi, ) и отново се прилага горния критерии за приемане или отхвърляне.

Зад. 3.6 С помощта на метода на фон Нойман генерирайте поредица от случайни числа в интервала [0,1] с разпределение w(x)=(6/5)(1-x2/2).
Каталог: ~tank -> NumericalMethods
~tank -> Програма От командната линия, след като сме влезли в директорията където е файла с фортран-код
~tank -> Програма за изчисляване на средна стойност
~tank -> Лекция аплети и уеб-страници
NumericalMethods -> Задача за числово решение с компютърна симулация. Решението на проблема за перколацията включва намирането на критична вероятност, р
NumericalMethods -> Лекция Компютърно моделиране във физиката роля
NumericalMethods -> Лекция числово интегриране
NumericalMethods -> Лекция 10. Видове случайни разходки. Просто обхождане. Необратимо


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©obuch.info 2019
отнасят до администрацията

    Начална страница