Gerador de números pseudo-aleatório

Neste documento apresentamos algumas simulações envolvendo a geração de números pseudo-aleatórios.

Hilbert

Gerador Congruente Linear

O gerador congruente linear é um algoritmo que produz uma seqüência de números pseudo-aleatórios calculados a partir de uma relação de recorrência modular. O método representa um dos mais antigos e conhecidos algoritmos do geração de números de pseudo-aleatórios.

O gerador é definido pela relação de recorrência:

\[ X_ {n + 1} = \left (aX_ {n} + c \right) ~~ {\bmod {~}} ~ m\]

onde \(X\) é a seqüência de valores de pseudo-aleatório, e \(a,c<m\)

Como o número de classes módulo \(m\) é finito a sequência possui um período. Claramente o período é no máximo \(m\) e para algumas escolhas de \(a,c\) e \(m\) pode ser muito menor do que isso. O gerador congruente misto terá um período completo \(m\) para todos os valores de \(X_0\) se e somente se:

• m e c c são relativamente primos,
• a-1 é divisível por todos os fatores primos de m,
• a - 1 é divisível por 4 se m é divisível por 4.

Esse fato é conhecido como Teorema de Hull-Dobell.

Implementação

Nas linhas abaixo implementamos um CGL. Usamos definição recursiva com memorização dos valores já encontrados.

a=17
b=7
m=1024

RX <- local({
    memo <- c( rep(NA, 100000))
    f <- function(x) {
        if(x == 0) return(9)
        if(x < 0) return(NA)
        if(x > length(memo))
        stop("'x' grande demais")
        if(!is.na(memo[x])) return(memo[x])
        resp <- (a*f(x-1)+b)%% m
        memo[x] <<- resp
        resp
    }
})

Análise

Abaixo apresentamos o histograma dos números pseudo-aleatórios gerado.

hist(sapply(1:10000,RX),breaks = seq(0, 1024, by = 128),col="blue")

Comentários

O CGL é simples e ruim. Apresentamos ele apenas para fins didáticos.

O R possui funções para geração de números pseudo-aleatórios bem melhores, como por exemplo a função runif. Esta função gera valores da distribuição Uniforme. Veja como gerar um número aleatório entre 0 e 1:

runif(1, 0, 1)

## [1] 0.4804456

Uma sequência de números pseudo-aleatórios

runif(20, 0, 1)

##  [1] 0.54877864 0.49125663 0.80240070 0.22871092 0.02163787 0.75379398
##  [7] 0.17109699 0.27185996 0.60148640 0.97034241 0.27989723 0.52975556
## [13] 0.41458723 0.81697301 0.62827154 0.54807804 0.21882186 0.31572262
## [19] 0.99841193 0.10307046

```