Testes diehard

Os testes diehard são uma bateria de testes estatísticos para medir a qualidade de um gerador de números aleatórios. Eles foram desenvolvidos por George Marsaglia ao longo de vários anos e publicados pela primeira vez em 1995 em um CD-ROM de números aleatórios.^[1] Em 2006, os testes originais mais rigorosos foram estendidos para os testes dieharder.^[2]

Histórico

Um conjunto inicial de testes de aleatoriedade para RNGs foi sugerido na primeira edição de 1969 de The Art of Computer Programming, de Donald Knuth (Volume 2, Capítulo 3.3: Testes estatísticos). Os testes de Knuth foram depois suplantados pelos testes Diehard de George Marsaglia (1995), que consistiam em quinze tipos diferentes de testes. A incapacidade de modificar os parâmetros dos testes ou adicionar novos testes ao conjunto levou ao desenvolvimento da biblioteca TestU01, desenvolvida em 2007 por Pierre L'Ecuyer e Richard Simard da Universidade de Montreal .

Visão geral do teste

Espaçamentos de aniversário: Escolha pontos aleatórios em um intervalo relativamente grande. Os espaçamentos entre os pontos devem ser distribuídos exponencialmente de maneira assintótica.^[3] O nome é baseado no paradoxo do aniversário .

Permutações sobrepostas

Analise sequências de cinco números aleatórios consecutivos. As 120 ordenações que podem ser geradas devem ocorrer com probabilidade estatisticamente igual.

Postos de matrizes

Selecione um número de bits de um conjunto de números aleatórios de modo a formar uma matriz sobre {0,1} e então determine a classificação da matriz.

Testes de macacos

Trate sequências de uma sequência de bits como "palavras". Conte as palavras que ficam sobrepostas em um determinado fluxo. O número de "palavras" que não aparecem deve seguir uma distribuição conhecida. O nome é baseado no teorema do macaco infinito .

Conte os 1s

Conte os bits 1 em cada um dos bytes sucessivos ou escolhidos. Converta as contagens para "letras" e conte as ocorrências de "palavras" de cinco letras.

Teste de estacionamento

Coloque aleatoriamente círculos unitários em um quadrado de 100×100. Um círculo é considerado estacionado com sucesso se não se sobrepõe a outro já estacionado com sucesso. Após 12.000 tentativas, o número de círculos estacionados com sucesso deve seguir uma distribuição normal .

Teste de distância mínima

Coloque aleatoriamente 8000 pontos em um quadrado de 10000×10000 e então encontre a distância mínima entre os pares. O quadrado dessa distância deve ser distribuído exponencialmente com uma determinada média.

Teste de esferas aleatórias

Escolha aleatoriamente 4000 pontos em um cubo cuja aresta tem valor 1000. Centralize uma esfera em cada ponto, cujo raio é a distância mínima até outro ponto. O menor volume da esfera deve ser distribuído exponencialmente com uma determinada média.

Teste de compressão

Multiplique 2³¹ por números flutuantes aleatórios em (0,1) até chegar a 1. Repita isso 100.000 vezes. O número de números flutuantes necessários para chegar a 1 deve seguir uma certa distribuição.

Teste de somas sobrepostas

Gere uma longa sequência de números flutuantes aleatórios em (0,1). Adicione sequências de 100 pontos flutuantes consecutivos. As somas devem ser distribuídas normalmente com média e variância características.

Teste de runs

Gere uma longa sequência de números flutuantes aleatórios em (0,1). Conte os runs (quantidade de ascendências/descendências dentro de uma sequência). A sequência das contagens devem seguir uma determinada distribuição.

Teste de craps

Jogue 200.000 partidas de craps, contando as vitórias e o número de lançamentos por partida. Cada contagem deve seguir uma certa distribuição.

Descrições dos testes

Teste do espaçamento de aniversários

Escolha m aniversários num ano de n dias. Faça uma lista dos espaçamentos entre os aniversários. Se j for o número de valores que ocorrem mais do que uma vez nessa lista, então j tem uma Distribuição de Poisson assintótica com média $m 3 / (4 n)$ . A experiência mostra que n deve ser bastante grande, digamos $n\geq 2^{18}$ , para comparar os resultados com a distribuição de Poisson com essa média. Este teste utiliza $n=2^{24}$ e $m=2^{9}$ , de modo que a distribuição subjacente para j é considerada Poisson com $\lambda =2^{27}/2^{26}=2$ . É recolhida uma amostra de 500 j e um teste de adequação do qui-quadrado fornece um valor p. O primeiro teste utiliza os bits 1-24 (a contar da esquerda) dos inteiros no arquivo especificado. Depois, o arquivo é fechado e reaberto. Em seguida, os bits 2-25 são utilizados para fornecer os aniversários, depois 3-26 e assim sucessivamente até aos bits 9-32. Cada conjunto de bits fornece um valor p, e os nove valores p fornecem uma amostra para um KSTEST.

Permutações sobrepostas

Este é o teste OPERM5, baseado na análise de uma sequência de um milhão de números inteiros aleatórios de 32 bits. Cada conjunto de cinco números inteiros consecutivos pode estar num dos 120 estados, para as 5! ordenações possíveis de cinco números. Assim, o 5º, 6º, 7º, ... números fornecem cada um um estado. Como são observados muitos milhares de transições de estado, são efetuadas contagens cumulativas do número de ocorrências de cada estado. Em seguida, a forma quadrática na inversa fraca da matriz de covariância 120×120 produz um teste equivalente ao teste da razão de verossimilhança de que as 120 contagens de células provêm da distribuição normal (assimptoticamente) especificada com a matriz de covariância 120×120 especificada (de ordem 99). Esta versão usa 1.000.000 inteiros, duas vezes. Este teste pode ter erros não resolvidos que resultam em valores p consistentemente fracos.^[4]

Postos de matrizes 31×31

Os 31 bits mais à esquerda de 31 números inteiros aleatórios da sequência de teste são utilizados para formar uma matriz binária 31×31 sobre o corpo{0,1}. Determina-se o posto. Esse posto pode ser de 0 a 31, mas as posições < 28 são raras, e as suas contagens são agrupadas com as da posição 28. As classificações são encontradas para 40.000 matrizes aleatórias deste tipo e é efectuado um teste do qui-quadrado para as contagens das classificações 31, 30, 29, e ≤ 28.

Postos de matrizes 32×32

Forma-se uma matriz binária aleatória 32×32, sendo cada linha um número inteiro aleatório de 32 bits. Determina-se o posto. Essa posição pode ser de 0 a 32, mas as posições inferiores a 29 são raras e as suas contagens são agrupadas com as da posição 29. São encontradas classificações para 40.000 matrizes aleatórias deste tipo e é efetuado um teste do qui-quadrado para as contagens das classificações 32, 31, 30 e ≤ 29.

Postos de matrizes 6×8

A partir de cada um dos seis números inteiros aleatórios de 32 bits do gerador em teste, é escolhido um byte específico e os seis bytes resultantes formam uma matriz binária 6×8 cujo valor é determinado. Essa classificação pode ser de 0 a 6, mas as classificações 0, 1, 2, 3 são raras suas contagens são agrupadas com as da classificação 4. As classificações são encontradas para 100.000 matrizes aleatórias, e é efetuado um teste de qui-quadrado nas contagens para as classificações 6, 5 e ≤ 4. Teste do fluxo de bits O arquivo em teste é visto como um fluxo de bits. Chame-os de b₁, b₂, ... . Considere um alfabeto com duas "letras", 0 e 1, e pense no fluxo de bits como uma sucessão de "palavras" de 20 letras, sobrepostas. Assim, a primeira palavra é b₁b₂...b₂₀, a segunda é b₂b₃...b₂₁, e assim por diante. O teste de fluxo de bits conta o número de palavras de 20 letras (20 bits) ausentes em uma sequência de 2²¹ palavras de 20 letras sobrepostas. Existem 2²⁰ palavras possíveis de 20 letras. Para uma sequência verdadeiramente aleatória de 2²¹ + 19 bits, o número de palavras faltantes j deve ser (muito próximo de) distribuído normalmente com média 141.909 e sigma 428. Assim, $(j-141909)/428$ deve ser uma variável normal padrão (pontuação z) que leva a um valor p uniforme [0,1). O teste é repetido vinte vezes.

Testes OPSO, OQSO e DNA

O teste OPSO (do inglês overlapping-pairs-sparse-occupation) considera palavras de 2 letras de um alfabeto de 1024 letras. Cada letra é determinada por dez bits especificados de um inteiro de 32 bits na sequência a ser testada. OPSO gera 2²¹ palavras de 2 letras (sobrepostas) (de 2²¹ + 1 "pressionamentos de tecla") e conta o número de palavras faltantes j - ou seja, palavras de 2 letras que não aparecem na sequência inteira. Essa contagem deve ser muito próxima da distribuição normal com média 141909, sigma 290. Assim, $(j-141909)/290$ deve ser uma variável normal padrão. O teste OPSO pega 32 bits por vez do arquivo de teste e usa um conjunto designado de dez bits consecutivos. Em seguida, ele reinicia o arquivo para os próximos 10 bits designados e assim por diante. Já o teste OQSO (do inglês significa overlapping-quadruples-sparse-occupancy) é semelhante ao anterior, exceto que considera palavras de 4 letras de um alfabeto de 32 letras, cada letra determinada por uma sequência designada de 5 bits consecutivos do arquivo de teste, elementos dos quais são assumidos inteiros aleatórios de 32 bits. O número médio de palavras ausentes em uma sequência de 2²¹ palavras de quatro letras, (2²¹ + 3 "pressionamentos de tecla"), é novamente 141909, com sigma = 295. A média é baseada na teoria; sigma vem de simulação extensiva. O teste de DNA considera um alfabeto de 4 letras C, G, A, T, determinado por dois bits designados na sequência de inteiros aleatórios sendo testados. Ele considera palavras de 10 letras, de modo que, como em OPSO e OQSO, há 220 palavras possíveis, e o número médio de palavras faltantes de uma sequência de 2²¹ palavras de 10 letras (sobrepostas) (2²¹ + 9 "pressionamentos de tecla") é 141909. O desvio padrão sigma = 339 foi determinado como para OQSO por simulação. (Sigma para OPSO, 290, é o valor verdadeiro (para três casas), não determinado por simulação).

Teste de contagem de 1 em um fluxo de bytes

Considere o arquivo em teste como um fluxo de bytes (quatro por inteiro de 32 bits). Cada byte pode conter nenhum a oito 1s, com probabilidades de 1, 8, 28, 56, 70, 56, 28, 8, 1 sobre 256. Agora, deixe o fluxo de bytes fornecer uma sequência de palavras de 5 letras sobrepostas, cada "letra" assumindo os valores A, B, C, D, E. As letras são determinadas pelo número de 1s em um byte 0, 1 ou 2 produções A, 3 produções B, 4 produções C, 5 produções D e 6, 7 ou 8 resultados E. Assim, temos um macaco em uma máquina de escrever instruções cinco teclas com várias probabilidades (37, 56, 70, 56, 37 sobre 256). Há 55 palavras possíveis de 5 letras, e de uma sequência de 256000 palavras de 5 letras (sobrepostas), são feitas contagens nas frequências de cada palavra. A forma quadrática no inverso fraca da matriz de covariância das contagens de células fornece um teste qui-quadrado Q5–Q4, a diferença das somas de Pearson de $(OBS - EXP) 2 / EXP$ em contagens para células de 5 e 4 letras.

Teste de contagem de 1's para bytes específicos

Considere o arquivo em teste como um fluxo de inteiros de 32 bits. De cada inteiro, um byte específico é escolhido, escolha os bits mais à esquerda de 1 a 8. Cada byte pode conter de 0 a 8 1s, com probabilidades de 1, 8, 28, 56, 70, 56, 28, 8, 1 sobre 256. Agora, deixe que os bytes especificados de inteiros sucessivos forneçam uma sequência de palavras de 5 letras (sobrepostas), cada "letra" assumindo os valores A, B, C, D, E. As letras são determinadas pelo número de 1s, naquele byte 0, 1 ou 2 → A, 3 → B, 4 → C, 5 → D e 6, 7 ou 8 → E. Assim, temos um macaco em uma máquina de escrever digitando cinco teclas com probabilidades de 37 , 56, 70, 56, 37 sobre 256. Existem 55 palavras possíveis de 5 letras e, a partir de uma sequência de 256.000 palavras de 5 letras (sobrepostas), as contagens são feitas nas frequências de cada palavra. A forma quadrática no inverso fraca da matriz de covariância das contagens de células fornece um teste qui-quadrado Q5 – Q4, a diferença das somas de Pearson de $(OBS - EXP) 2 / EXP$ nas contagens para contagens de células de 5 e 4 letras.

Teste do estacionamento

Em um quadrado de lado 100, "estacione" aleatoriamente um carro – um círculo de raio 1. Em seguida, tente estacionar um 2º, um 3º e assim por diante, repetindo o estacionamento se uma tentativa de estacionar causar um acidente com um já estacionado (sobreposição), havendo a necessidade de tentar novamente estacionar em um novo local do quadrado. Cada tentativa leva a um acidente ou a um sucesso, este último seguido por um incremento na lista de carros já estacionados. Se produzirmos um gráfico de n: o número de tentativas, versus o número de estacionamentos bem sucedidos, obtemos uma curva que deve ser semelhante a selecionada por um gerador de números aleatórios perfeito. A teoria para o comportamento de tal curva supostamente parece fora de alcance, e como exibições gráficas não estão disponíveis para esta bateria de testes, uma caracterização simples do experimento aleatório é usada: k, o número de carros estacionados com sucesso após n = 12.000 experimentos. A simulação mostra que k deve ter uma média de 3523 com sigma 21,9 e está muito próximo da distribuição normal. Assim, $(k - 3523) / 21,9$ deve ser uma variável normal padrão, que, convertida em uma variável uniforme, fornece entrada para um KSTEST com base em uma amostra de 10.

Teste de distância mínima

Escolha n = 8.000 pontos aleatórios em um quadrado de lado 10.000, repetindo este processo 100 vezes. Encontre d, a distância mínima entre os pares de pontos (n² − n)/2. Se os pontos forem realmente uniformes independentes, então d², o quadrado da distância mínima deve ser (muito próximo de) distribuído exponencialmente com média de 0,995. Assim, $1 - exp(- d 2 / 0,995)$ deve ser uniforme em [0,1) e um KSTEST nos 100 valores resultantes serve como um teste de uniformidade para pontos aleatórios no quadrado. Números de teste = 0 mod 5 são impressos, mas o KSTEST é baseado no conjunto completo de 100 escolhas aleatórias de 8.000 pontos no quadrado 10.000×10.000.

Teste das esferas 3D

Escolha 4.000 pontos aleatórios em um cubo de aresta 1.000. Em cada ponto, centralize uma esfera grande o suficiente para alcançar o próximo ponto mais próximo. Então o volume da menor esfera é (muito próximo de) distribuído exponencialmente com média 120π/3. Assim, o raio ao cubo é exponencial com média 30. (A média é obtida por simulação extensiva). O teste das esferas 3D gera 4.000 dessas esferas 20 vezes. Cada raio mínimo ao cubo leva a uma variável uniforme por meio de $1 - exp(- r 3 / 30)$ , então um KSTEST é feito nos 20 valores-p.

Teste de compressão

Inteiros aleatórios são tornados flutuantes para obter uniformes em [0,1). Começando com k = 2³¹ = 2147483648, o teste encontra j, o número de iterações necessárias para reduzir k a 1, usando a redução k = ceiling(k×U), com U fornecido por inteiros flutuantes do arquivo sendo testado. Esses js são encontrados 100.000 vezes, então contagens para o número de vezes que j foi ≤ 6, 7, ...≤ 6, 7, ... são usadas para fornecer um teste qui-quadrado para frequências de células.

Teste de somas sobrepostas

Os inteiros são tornados flutuantes para obter uma sequência U(1), U(2), ... de variáveis uniformes [0,1). Então somas sobrepostas, S(1) = U(1) + ... + U(100), S(2) = U(2) + ... + U(101), ... são formadas. Os Ss são virtualmente normais com uma certa matriz de covariância. Uma transformação linear dos Ss os converte em uma sequência de normais padrão independentes, que são convertidas em variáveis uniformes para um KSTEST. Os valores-p de dez KSTESTs recebem ainda outro KSTEST.

Teste de runs

Ele conta as runs, quantidade de ascendências/descendências dentro de uma sequência, em uma sequência de variáveis uniformes [0,1), obtidas tornando flutuantes os inteiros de 32 bits no arquivo especificado. Este exemplo mostra como as execuções são contadas: 0,123, 0,357, 0,789, 0,425, 0,224, 0,416, 0,95 contém uma run ascendente de comprimento 3, uma run descendente de comprimento 2 e uma execução ascendente de (pelo menos) 2, dependendo dos próximos valores. As matrizes de covariância para as execuções ascendentes e descendentes são bem conhecidas, levando a testes qui-quadrado para formas quadráticas nos inversos fracos das matrizes de covariância. As runs são contadas para sequências de comprimento 10.000. Isso é feito dez vezes.

Teste de craps

Ele joga 200.000 jogos de craps, encontra o número de vitórias e o número de jogadas necessárias para terminar cada jogo. O número de vitórias deve ser (muito próximo de) um normal com média 200000p e variância $200000 p (1 - p)$ , com $p = 244 / 495$ . As jogadas necessárias para completar o jogo podem variar de 1 a infinito, mas as contagens para todos os > 21 são agrupadas com 21. Um teste qui-quadrado é feito nas contagens de células de número de jogadas. Cada inteiro de 32 bits do arquivo de teste fornece o valor para o lançamento de um dado, tornando flutuante dentro do intervalo [0,1), multiplicando por 6 e pegando 1 mais a parte inteira do resultado.

A maioria dos testes em DIEHARD retorna um valor-p, que deve ser uniforme em [0,1) se o arquivo de entrada contiver bits aleatórios realmente independentes. Esses valores de p são obtidos por p = F(X), onde F é a distribuição presumida da variável aleatória da amostra X – geralmente normal. Mas esse F presumido é apenas uma aproximação assintótica, para a qual o ajuste será pior nas caudas. Portanto, você não deve se surpreender com valores de p ocasionais próximos de 0 ou 1, como 0,0012 ou 0,9983. Quando um fluxo de bits REALMENTE FALHA MUITO, você obterá p s de 0 ou 1 a seis ou mais lugares. Como há muitos testes, não é improvável que um p < 0,025 ou p > 0,975 signifique que o RNG "falhou no teste no nível 0,05". Esperamos que vários desses eventos ps aconteçam entre as centenas de eventos que o DIEHARD produz, mesmo condicionados à perfeição do gerador de números aleatórios.