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

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

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

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

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

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

• 
  Определете периода на поредицата т.е. колко числа се генерират преди поредицата да започне да се повтаря.
  
• 
  Проверете за наличието на корелация като разгледате точки в равнинета, чиито координати са последователни числа от поредицата: (x_i,y_i)=(r_2i-1,r_2i), i=1,2,…Използвайте в MATLAB командата scatterplot(x,y).
  
• 
  Направете същата графична проверка за наличието на корелация като използвате вградения генератор на случайни числа.
  
• 
  Реализирайте алгоритъм от горния тип, който има много добри свойства за 32-битов компютър и е достатъчно бърз. Този алгоритъм е предложен от Park & Miller през 1988 г Приемаме а=7⁵ = 16,807; с=0;m=2³¹–1=2, 147,483,647. Ако приложим директно горния алгоритъм могат да възникнат някои проблеми. Например, ако някоя стойност излезе извън обхвата от стойности, компютъра ще връща грешни стойности без да дава съобщение за грешка. Затова предлагания алгоритъм е малко усложнен, но може да модулира числата с период m=2³¹–1.
  

1. 
   Дефинираме константи: а=7⁵ ; m=2³¹–1; q=m/a=127773; r=m%a=2836
   

2. 
   Задаваме начална стойност на поредицата seed=1
   
3. 
   Дефинираме цяла променлива h=seed/q
   
4. 
   Дефинираме цяла променлива i=seed%q
   
5. 
   Дефинираме цяла променлива t=a*i - r*h
   
6. 
   if(t>0) seed=t
   
7. 
   Else seed=t+m
   
8. 
   Return seed/(float)m // за да бъде резултата в интервала [0,1]
   

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

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

Year 0  y  99

Month 1  m  12

Hour 0  h  23

Minute 0  min  59

Second 0  s 5 9

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

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

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

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

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

(3)

(4)

Един начин за генериране на експоненциално разпределение е като използваме равномерното разпределение. Нека имаме равномерно разпределение 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)

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

(9)

(10)

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

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

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

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

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

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

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

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

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