Como devo testar a aleatoriedade?

Eu não acho que os testes unitários sejam a ferramenta certa para testar a aleatoriedade. Um teste de unidade deve chamar um método e testar o valor retornado (ou estado do objeto) em relação a um valor esperado. O problema com o teste de aleatoriedade é que não há um valor esperado para a maioria das coisas que você gostaria de testar. Você pode testar com uma determinada semente, mas isso só testa a repetibilidade . Ele não te dá nenhuma maneira de medir quão aleatória a distribuição é, ou se é aleatória mesmo.

Felizmente, existem muitos testes estatísticos que você pode executar, como a Bateria obstinada de testes de aleatoriedade . Veja também:

1. Como testar a unidade de um gerador de números pseudo-aleatórios?

   • Steve Jessop recomenda que você encontre uma implementação testada do mesmo algoritmo RNG que esteja usando e compare sua saída com as sementes selecionadas contra sua própria implementação.
   • Greg Hewgill recomenda o ENT conjunto de testes estatísticos.
   • John D. Cook encaminha os leitores ao seu artigo CodeProject
   • Várias pessoas recomendam testar se a distribuição dos números gerados é uniforme, o teste qui-quadrado e testar se a média e o desvio padrão estão dentro do intervalo esperado. (Observe que testar a distribuição sozinha não é suficiente. [1,2,3,4,5,6,7,8] é uma distribuição uniforme, mas certamente não é aleatória.)

2. Teste de unidade com funções que retornam resultados aleatórios

   • Brian Genisio aponta que zombar de seu RNG é uma opção para tornar seus testes repetíveis e fornece código de amostra C #.
   • Novamente, várias outras pessoas apontam o uso de valores fixos de sementes para repetibilidade e testes simples para distribuição uniforme, qui-quadrado, etc.

3. Aleatoriedade de Testes Unitários é um artigo wiki que fala sobre muitos dos desafios já abordados ao tentar testar o que é, por sua natureza, não repetível. Um detalhe interessante que eu aprendi foi o seguinte:

   I've seen winzip used as a tool to measure the randomness of a file of values before (obviously, the smaller it can compress the file the less random it is).

1. Teste da unidade seu algoritmo

Para a primeira pergunta, eu criaria uma classe falsa que você alimentaria uma sequência de números aleatórios para os quais você conhece o resultado do seu algoritmo. Dessa forma, você garante que o algoritmo que você construiu no topo de sua função aleatória funcione. Então, algo ao longo das linhas:

Random r = new RandomStub([1,3,5,3,1,2]);
r.random(); //returns 1
r.random(); //returns 3
...

2. Veja se sua função aleatória faz sentido

Para o teste de unidade, você deve adicionar um teste que é executado várias vezes e afirma que os resultados

• estão dentro dos limites que você definiu (portanto, um rolo de dados está entre 1 e 6) e
• mostra uma distribuição sensata (faça várias execuções de teste e veja se a distribuição está dentro de x% do que você esperava, por exemplo, para o lançamento de dados você deve ver 2 entre 10% e 20% (1/6 = 16,67%) do tempo dado que você rolou 1000 vezes).

3. Teste de integração para o algoritmo e a função aleatória

Com que frequência você esperaria que sua matriz fosse classificada na classificação original? Classifique algumas centenas de vezes e afirme que apenas x% do tempo a classificação não muda.

Isso já é um teste de integração, você está testando o algoritmo junto com a função aleatória. Uma vez que você está usando a função aleatória real, você não pode mais sair com testes únicos.

Da experiência (eu escrevi um algoritmo genético) eu diria que combinar o teste unitário de seu algoritmo, o teste de distribuição de sua função aleatória e o teste de integração é o caminho a percorrer.

Um aspecto dos PRNGs que parece esquecido é que todas as suas propriedades são de natureza estatística: você não pode esperar que embaralhar uma matriz resulte em uma permutação diferente daquela com a qual você começou. Basicamente, se você estiver usando um PRNG normal, a única coisa garantida é que ele não usa um padrão simples (espero) e que tem distribuição uniforme entre o conjunto de números que ele retorna.

Um teste adequado para um PRNG envolverá executá-lo pelo menos 100 vezes e, em seguida, verificar a distribuição da saída (que é uma resposta direta à segunda parte da questão).

Uma resposta para a primeira pergunta é quase a mesma: execute o teste cerca de 100 vezes com {1, 2, ..., n} e conte o número de vezes que cada elemento esteve em cada posição. Eles devem ser praticamente iguais se o método shuffle for bom.

Uma questão totalmente diferente é como testar os PRNGs com criptografia. Este é um assunto em que você provavelmente não deveria se deitar, a menos que você realmente saiba o que está fazendo. As pessoas são conhecidas por destruir (leia-se: abrir brechas catastróficas em) bons sistemas criptográficos com apenas algumas 'otimizações' ou edições triviais .

EDIT: Reli completamente a questão, a resposta principal e a minha. Enquanto os pontos que eu faço ainda estão, eu daria a segunda resposta de Bill The Lizard. Os testes unitários são de natureza booleana - ou falham, ou são bem-sucedidos e, portanto, inadequados para testar "quão boas" são as propriedades de um PRNG (ou um método usando um PRNG), pois qualquer resposta a essa pergunta seria quantitativa , em vez de polar.

Existem duas partes para isso: testar a randomização e testar coisas que usam randomização.

Testar a randomização é relativamente simples. Você verifica que o período do gerador de números aleatórios é como você espera que seja (para algumas amostras usando algumas sementes aleatórias, dentro de algum limite) e que a distribuição da saída em um tamanho de amostra grande é como você espera que seja (dentro de algum limite).

Testar coisas que usam randomização é melhor feito com um gerador de números aleatórios determinístico de psuedo. Como a saída da randomização é conhecida com base na semente (suas entradas), então você pode testar a unidade como normal com base em entradas versus saídas esperadas. Se o seu RNG é não determinístico, então zombe dele com um que é determinístico (ou simplesmente não aleatório). Teste a randomização isolada do código que a consome.

Deixe que ele seja executado várias vezes e visualize seus dados .

Veja um exemplo de uma mistura de Horror de codificação , você pode ver que o algoritmo está OK ou não:

É fácil ver que todos os itens possíveis são retornados pelo menos uma vez (os limites são OK) e que a distribuição está correta.

Ponteiros gerais que considero úteis ao lidar com códigos que usam entradas aleatórias: Verifique os casos de borda da aleatoriedade esperada (valores máximos e mínimos, e os valores máximos + 1 e min-1, se aplicável). Verifique os locais (on, above e below) onde os números têm pontos de inflexão (ou seja, -1, 0, 1 ou maior que 1, menor que 1 e não negativo para casos em que um valor fracionário pode atrapalhar a função). Confira alguns lugares completamente fora da entrada permitida. Verifique alguns casos típicos. Você também pode adicionar uma entrada aleatória, mas para um teste unitário que tenha o efeito colateral indesejado de que o mesmo valor não esteja sendo testado toda vez que o teste for executado (teste de sementes, teste os primeiros 1.000 números aleatórios da semente S ou algo assim).

Para testar a saída de uma função aleatória, é importante identificar a meta. No caso das cartas, o objetivo é testar a uniformidade do gerador aleatório de 0-1, para determinar se todas as 52 cartas aparecem no resultado, ou algum outro objetivo (talvez toda essa lista e mais)?

No exemplo específico, você tem que assumir que seu gerador de números aleatórios é opaco (assim como não faz sentido testar o syscall ou malloc do SO - a menos que você grave sistemas operacionais). Pode ser útil medir o gerador de números aleatórios, mas seu objetivo não é escrever um gerador aleatório, apenas para ver que você recebe 52 cartões cada vez e que eles mudam de ordem.

Essa é uma maneira longa de dizer que há duas tarefas de teste aqui: testar se o RNG está produzindo a distribuição correta e verificar se o código de embaralhamento de seu cartão está usando esse RNG para produzir resultados aleatórios. Se você estiver escrevendo o RNG, use a análise estatística para provar sua distribuição, se você estiver escrevendo o embaralhador de cartas, certifique-se de que existem 52 cartões não repetidos em cada saída (é um caso melhor para testar por inspeção que você está usando o RNG).

Você pode confiar em geradores de números aleatórios seguros

Eu só tive um pensamento horrível: você não está escrevendo seu próprio gerador de números aleatórios, não é?

Supondo que você não é, deve testar o código pelo qual é responsável , e não o código de outras pessoas (como a implementação SecureRandom do seu framework).

Testando seu código

Para testar se o seu código responde corretamente, é normal usar um método de baixa visibilidade para produzir os números aleatórios, de modo que possa ser facilmente substituído por uma classe de teste de unidade. Esse método substituído efetivamente bloqueia o gerador de números aleatórios e fornece controle total sobre o que é produzido e quando. Consequentemente, você pode exercitar totalmente seu código, que é o objetivo do teste de unidade.

Obviamente, você verificará as condições da borda e garantirá que o embaralhamento ocorra exatamente como o seu algoritmo dita, dadas as entradas apropriadas.

Testando o gerador seguro de números aleatórios

Se você não tiver certeza de que o gerador de números aleatórios seguros para o seu idioma não é verdadeiramente aleatório ou com bugs (fornece valores fora do intervalo, etc.), será necessário executar uma análise estatística detalhada da saída em várias centenas de milhões de iterações. Trace a frequência de ocorrência de cada número e ele deverá aparecer com igual probabilidade. Se os resultados se desviarem de uma forma ou de outra, você deve relatar suas descobertas para os projetistas da estrutura. Eles definitivamente estarão interessados em consertar o problema, já que os geradores seguros de números aleatórios são fundamentais para muitos algoritmos de criptografia.

Bem, você nunca terá 100% de certeza, então o melhor que você pode fazer é que é provável que os números sejam aleatórios. Escolha uma probabilidade - digamos que uma amostra de números ou itens surgirá x vezes, dado um milhão de amostras, dentro de uma margem de erro. Execute a coisa um milhão de vezes e veja se está dentro da margem. Felizmente, os computadores facilitam esse tipo de coisa.

Para testar se uma fonte de números aleatórios está gerando algo que pelo menos tem a aparência de aleatoriedade, eu teria o teste gerando uma seqüência razoavelmente grande de bytes, gravando-os em um arquivo temporário e, em seguida, enviando para Ferramenta ent do Fourmilab. Entregue o switch -t (conciso) para gerar um CSV fácil de analisar. Em seguida, verifique os vários números para ver se eles são "bons".

Para decidir quais números são bons, use uma fonte conhecida de aleatoriedade para calibrar seu teste. O teste deve quase sempre passar quando é dado um bom conjunto de números aleatórios. Como até mesmo uma sequência verdadeiramente aleatória tem uma probabilidade de gerar uma sequência que parece não ser aleatória, você não pode fazer um teste que certamente será aprovado. Você apenas seleciona limites que tornam improvável que uma sequência aleatória cause uma falha de teste. A aleatoriedade não é divertida?

Nota: Você não pode escrever um teste que mostre que um PRNG gera uma sequência "aleatória". Você só pode escrever um teste que, se passar, indica alguma probabilidade de que a sequência gerada pelo PRNG seja "aleatória". Bem-vindo à alegria da aleatoriedade!

Caso 1: testando um shuffle:

Considere um Array [0, 1, 2, 3, 4, 5], embaralhe, o que pode dar errado? As coisas de sempre: a) sem shuffle, b) embaralhando 1-5 mas não 0, embaralhando 0-4 mas não 5, embaralhando, e sempre gerando o mesmo padrão, ...

Um teste para pegá-los todos:

Embaralhe 100 vezes, adicione os valores em cada espaço. A soma de cada slot deve ser semelhante a outro slot. Avg / Stddev pode ser calculado. (5 + 0) /2=2.5, 100 * 2.5 = 25. O valor esperado é de cerca de 25, por exemplo.

Se os valores estiverem fora do intervalo, há uma pequena chance de você ter um falso negativo. Você pode calcular, quão grande é essa chance. Repita o teste. Bem - claro que há uma pequena chance, que o teste falha 2 vezes seguidas. Mas você não tem uma rotina que exclua automaticamente sua fonte, se o teste da unidade falhar, não é? Execute de novo!

Pode falhar 3 vezes seguidas? Talvez você devesse tentar a sorte na loteria.

Caso 2: Jogue um dado

A questão dos dados é a mesma. Jogue os dados 6000 vezes.

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;