Случаjни броjеви су низови броjева коjи се не покораваjу никаквом обрасцу. Наjчешће се jављаjу у природним поjавама и ситуациjама коjе jе немогуће предвидети.

Постоје три начина за генерисање случајних бројева:

Псеудослучајни бројви су бројеви који се добијају по унапред одређеној формули и имају (скоро) сва својства случајних бројева.

\(\color{lightseagreen}{\text{1. Алгоритми за генерисање псеудослучајних бројева}}\)

Генератори псеудослучаjних броjева су алгоритми коjи на основу почетних услова даjу излазни низ псеудослучаjних броjева.

Пожељна своjстава коjа се очекуjу од генерисаног низа:

\(\color{lightseagreen}{\text{1.1. Линеарни конгруентни генератор - Linear Congruential Generator LCG }}\)

Метода линеарног конгруентног генератора (LCG – linear congruential generator) за генерисање случаjних броjева заснована jе на рекурентноj формули: \[X _ { n + 1 } = a X _ { n } + c \quad ( \bmod m ),\]

где су \(a\) и \(c\) константе, \(X_0\) почетни елемент овако насталог низа броjева и \(m\) горња граница генерисаних броjева.

Добијају се природни бројеви од 0 до \(m-1\), па је јасно је да је период овог алгоритма највише \(m\).

Услови за почетне вердности параметара

Вредност параметра \(m\) се бира тако да буде степен двојке, односно облика \(m=2^n\).

У зависности од избора вредности константе \(a\), мењаће се период алгоритма. Зато су дефинисани услови које треба да испуњава константа \(a\) да би се добио максимални период:

  1. \(a\) \(- 1\) треба да буде дељиво свим простим факторима од m;
  2. \(a\) \(- 1\) треба да буде дељиво са 4, ако је m дељиво са 4.

Поред ова два услова које треба да испуњава константа \(a\), додатан услов је:

  1. \(m\) и \(c\) треба да буду узајамно прости бројеви.

Имплементација

lcg <- function(a,c,m,x1,n) {
  x <- vector()
  #length(x) <- n
  x[1]<-x1
  for(i in 1:n) {
    x[i+1] <- (x[i]*a+c)%%m
  }
  return (x)
}

Предности овог алгоритма су:

  • једноставан
  • брз, не захтева много меморије, јер је за генерисање наредног броја довољно знати последњи и константе \(a, c, m\).

Мане:

  • постоји серијска корелација међу члановима низа;
  • низови добијени овим алгоритмом не пролазе неке од тестова случајности.
lcg(a=9,c=39,m=1000,x1=742,n=30) #овде је период само  8, јер није испуњено да је a-1=8 дељиво свим простим факторима од  1000, нпр 5 не дели 8
##  [1] 742 717 492 467 242 217 992 967 742 717 492 467 242 217 992 967 742
## [18] 717 492 467 242 217 992 967 742 717 492 467 242 217 992
lcg (113,23,10000000,721,30) # да ли су овде испуњени услови?
##  [1]     721   81496 9209071  625046  630221 1214996 7294571 4286546
##  [9] 4379721 4908496 4660071 6588046 4449221 2761996 2105571 7929546
## [17] 6038721 2375496 8431071 2711046 6348221 7348996  436571 9332546
## [25] 4577721 7282496 2922071  194046 1927221 7775996 8687571
lcg(a=5,c=7,m=16,x1=8,n=20) #ови параметри исуњавају услове за максималан период
##  [1]  8 15  2  1 12  3  6  5  0  7 10  9  4 11 14 13  8 15  2  1 12
\(\color{lightseagreen}{\text{1.1.1. Лемеров генератор - Lehmer RNG}}\)

Ово је специјални случај LCG za \(c=0\), назива се и MCG tj. Multiplicative Congruential Generator. Општа формула jе:

\[X _ { n + 1 } = a X _ { n } \quad ( \bmod m ),\] где jе \(a\) цео броj из интервала \([2, m − 1]\) и \(m\) прост броj.

Лемеров алгоритам jе сличан LCG генератору. Своjства коjа су карактеристична само за Лемеров алгоритам су:

  • у Лемеровом алгоритму почетни члан \(X_0\) и модул \(m\) мораjу бити узаjамно прости броjеви, што ниjе случаj за LCG;
  • наjвећи период Лемеровог алгоритма jе m − 1;
  • \(m\) мора бити прост броj.

Имплементација

Lg <- function(a,m,x1,n){
  x <- vector()
  x[1]<-x1
  for(i in 2:n){
    x[i]<-(a*x[i-1])%%m
  }
  return (x)
}
Lg(5,7,6,30) #уочава се периодичност
##  [1] 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 5 4

Параметре који се углавном користе и којима се добијају случајни низови који пролазе многе стандардне статистичке тестове случајности и успешно се користе у многим апликациjама, предложили су Park и Miller 1988. године:

  • m = 2^31-1 = 2,147,483,647 (Mersenne prime M31)
  • a = 7^5 = 16,807.
plot(Lg(7^5,2^31-1,243954,30)/(2^31-1),type="l")

\(\color{lightseagreen}{\text{1.2. Фибоначиjев генератор - LFG – Lagged Fibonacci generator}}\)

Фибоначиjев генератор jе добио име због сличности формуле сa рекурзивном формулом коjом се добиjаjу броjеви Фибоначиjевог низа. Општи облик формуле је:

\[X _ { n } = X _ { n - l } + X _ { n - k } \quad ( \bmod m ),\]

где су \(l\) и \(k\) цели броjеви, такви да важи \(l > k > 0\). За оваj генератор потребно jе \(l\) почетних броjева, а тестови показуjу да вредност броjа \(l\) треба да буде већа од 16.

Овакви генератори су у неким своjствима значаjно бољи од линеарних конгруетних генератора. Период низа броjева добиjених овако ниjе ограничен броjем \(m\). Проблем понављања нижих битова се може поjавити код малих вредности броjева \(l\) и \(k\), али ово се може лако избећи. И оваj поступак захтева мало рачунања, па узима мало процесорског времена и захтева памћење последњих \(l\) вредности. Барем jедан од тих \(l\) броjева на самом почетку мора бити непаран.

Наводимо некe изборе \(k\) и \(l\) у паровима, за које се добија максимални период:

\[\{k = 7, l = 10\}, \{k = 5, l = 17\}, \{k = 24, l = 55\} \{k = 65, l = 71\}, \{k = 418, l = 1279\}\]

Имплементација

lfg <- function(x, k, m, n) {
  #y <- vector()
  y<-x
  for(i in (length(x)+1):n) {
    y[i]<-(y[i-length(x)]+y[i-k])%%m
  }
  return (y)
}
a<-1:10
lfg(a,7,2^32,20) #лоше изгледа
##  [1]  1  2  3  4  5  6  7  8  9 10  5  7  9 11 13 15 17 13 16 19
a<-lcg(a=5,c=7,m=2^31,x1=8,n=20) #генеришемо почетни низ
lfg(x=a[1:10],k=7,m=2^31,n=20) #сада изгледа случајно
##  [1]        8       47      242     1217     6092    30467   152342
##  [8]   761717  3808592 19042967     1225     6139    30709   153559
## [15]   767809  3839059 19195309   762942  3814731 19073676

У R-у су имплементирани различити генератори псеудослучајних бројева, који су компликованији од наведених, па нећемо улазити у детаље њихове имплементације.

Функцијом RNGkind() можемо задати који алгоритам желимо да користимо.

help(RNGkind)

RNGkind(kind = NULL, normal.kind = NULL)

kind - алгоритам за генерисање бројева, ако се стави NULL исписује се назив тренутно одбраног алгоритма - подразумевани је “Mersenne-Twister”.

normal.kind - алгоритам који се користи за генерисање бројева из нормале расподеле

.Random.seed даје низ целих бројева у ком се налазе почетне вредности за изабрани алгоритам - број почетних вредности зависи од алгоритма

У R-у постоје функције које генеришу случајне бројеве. На пример, генерисање случајних бројева из униформне расподеле или неке друге дискретне или непрекидне расподеле. Све те функције имплицитно позивају генераторе случајних бројева.

runif(n=1,min=0,max=1)
## [1] 0.8253018

Функцијом set.seed сами задајемо иницијалне вредности алгоритму. Аргумент ове функције је само један број, а видели смо да је неким алгоритмима потребно много више од једне иницијалне вредности, што значи да функција set.seed на основу једне целобројне вредности генерише низ потребне дужине.

u<-vector()
for(i in 1:5){
u[i]<-runif(1)}
u
## [1] 0.7568471 0.4850673 0.5507074 0.2800088 0.4455836
us<-vector()
for(i in 1:5){
set.seed(99)  #увек се добија иста вредност
us[i]<-runif(1)} 
us
## [1] 0.5847119 0.5847119 0.5847119 0.5847119 0.5847119

Ова функција је веома значајна јер омогућава реконструисање истих резултата неких симлуација.

Пример функције у R-у која генерише случајне бројеве из унапред задатог скупа бројева је функција sample().

set.seed(8)
sample(6,2)
## [1] 3 2

Ова функција се може користити за генерисање простог случајног узорка, о чему ће бити више речи у наставку.