Como testar a aleatoriedade (caso em questão - Embaralhamento)
https://stackoverflow.com/questions/56411
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Em primeiro lugar, esta questão foi arrancada de esse pergunta.Fiz isso porque acho que esta parte é maior do que uma subparte de uma pergunta mais longa.Se isso ofende, por favor me perdoe.
Suponha que você tenha um algoritmo que gera aleatoriedade.Agora, como você testa isso?Ou, para ser mais direto: suponha que você tenha um algoritmo que embaralha um baralho de cartas, como testar se é um algoritmo perfeitamente aleatório?
Para adicionar alguma teoria ao problema - um baralho de cartas pode ser arrastado em 52!(52 fatorial) de maneiras diferentes.Pegue um baralho, embaralhe-o à mão e anote a ordem de todas as cartas.Qual é a probabilidade de você ter conseguido exatamente esse embaralhamento?Responder:1/52!.
Qual é a chance de você, depois de embaralhar, obter A, K, Q, J...de cada naipe em uma sequência?Resposta 1/52!
Portanto, apenas embaralhar uma vez e observar o resultado não fornecerá absolutamente nenhuma informação sobre a aleatoriedade do algoritmo de embaralhamento.Duas vezes e você terá mais informações, Três ainda mais...
Como você testaria a caixa preta de um algoritmo de embaralhamento quanto à aleatoriedade?
Solução
Estatisticas.O padrão de fato para testar RNGs é o Suíte obstinada (originalmente disponível em http://stat.fsu.edu/pub/diehard).Alternativamente, o Programa Ent fornece testes que são mais simples de interpretar, mas menos abrangentes.
Quanto aos algoritmos de embaralhamento, use um algoritmo bem conhecido, como Fisher-Yates (também conhecido como "Knuth Shuffle").O embaralhamento será uniformemente aleatório, desde que o RNG subjacente seja uniformemente aleatório.Se você estiver usando Java, este algoritmo está disponível na biblioteca padrão (veja Coleções.shuffle).
Provavelmente não importa para a maioria das aplicações, mas esteja ciente de que a maioria dos RNGs não fornece graus de liberdade suficientes para produzir todas as permutações possíveis de um baralho de 52 cartas (explicado aqui).
Outras dicas
Aqui está uma verificação simples que você pode realizar.Ele usa números aleatórios gerados para estimar Pi.Não é prova de aleatoriedade, mas RNGs ruins normalmente não se saem bem (eles retornarão algo como 2,5 ou 3,8 em vez de ~3,14).
Idealmente, este seria apenas um dos muitos testes que você executaria para verificar a aleatoriedade.
Outra coisa que você pode verificar é o desvio padrão da saída.O desvio padrão esperado para uma população uniformemente distribuída de valores no intervalo 0..n se aproxima de n/sqrt(12).
/**
* This is a rudimentary check to ensure that the output of a given RNG
* is approximately uniformly distributed. If the RNG output is not
* uniformly distributed, this method will return a poor estimate for the
* value of pi.
* @param rng The RNG to test.
* @param iterations The number of random points to generate for use in the
* calculation. This value needs to be sufficiently large in order to
* produce a reasonably accurate result (assuming the RNG is uniform).
* Less than 10,000 is not particularly useful. 100,000 should be sufficient.
* @return An approximation of pi generated using the provided RNG.
*/
public static double calculateMonteCarloValueForPi(Random rng,
int iterations)
{
// Assumes a quadrant of a circle of radius 1, bounded by a box with
// sides of length 1. The area of the square is therefore 1 square unit
// and the area of the quadrant is (pi * r^2) / 4.
int totalInsideQuadrant = 0;
// Generate the specified number of random points and count how many fall
// within the quadrant and how many do not. We expect the number of points
// in the quadrant (expressed as a fraction of the total number of points)
// to be pi/4. Therefore pi = 4 * ratio.
for (int i = 0; i < iterations; i++)
{
double x = rng.nextDouble();
double y = rng.nextDouble();
if (isInQuadrant(x, y))
{
++totalInsideQuadrant;
}
}
// From these figures we can deduce an approximate value for Pi.
return 4 * ((double) totalInsideQuadrant / iterations);
}
/**
* Uses Pythagoras' theorem to determine whether the specified coordinates
* fall within the area of the quadrant of a circle of radius 1 that is
* centered on the origin.
* @param x The x-coordinate of the point (must be between 0 and 1).
* @param y The y-coordinate of the point (must be between 0 and 1).
* @return True if the point is within the quadrant, false otherwise.
*/
private static boolean isInQuadrant(double x, double y)
{
double distance = Math.sqrt((x * x) + (y * y));
return distance <= 1;
}
Primeiro, é impossível saber com certeza se uma determinada saída finita é "verdadeiramente aleatória", uma vez que, como você aponta, qualquer saída é possível.
O que pode ser feito é pegar uma sequência de resultados e comparar várias medições dessa sequência com o que é mais provável.Você pode obter uma espécie de pontuação de confiança de que o algoritmo gerador está fazendo um bom trabalho.
Por exemplo, você pode verificar a saída de 10 embaralhamentos diferentes.Atribua um número de 0 a 51 a cada carta e calcule a média da carta na posição 6 ao longo dos embaralhamentos.A média convergente é 25,5, então você ficaria surpreso ao ver o valor 1 aqui.Você poderia usar o teorema do limite central para obter uma estimativa da probabilidade de cada média para uma determinada posição.
Mas não devemos parar por aqui!Porque este algoritmo pode ser enganado por um sistema que alterna apenas entre dois embaralhamentos projetados para fornecer a média exata de 25,5 em cada posição.Como podemos fazer melhor?
Esperamos uma distribuição uniforme (probabilidade igual para qualquer carta) em cada posição, em diferentes embaralhamentos.Portanto, entre os 10 shuffles, poderíamos tentar verificar se as escolhas 'parecem uniformes'. Esta é basicamente apenas uma versão reduzida do problema original.Você pode verificar se o desvio padrão parece razoável, se o mínimo é razoável e o valor máximo também.Você também pode verificar se outros valores, como as duas cartas mais próximas (pelos números atribuídos), também fazem sentido.
Mas também não podemos simplesmente adicionar várias medidas como esta ad infinitum, uma vez que, dadas estatísticas suficientes, qualquer embaralhamento específico parecerá altamente improvável por alguma razão (por exemplo,este é um dos poucos embaralhamentos em que as cartas X, Y, Z aparecem em ordem).Então a grande questão é:qual é o conjunto correto de medições a serem tomadas?Aqui tenho que admitir que não sei a melhor resposta.No entanto, se você tiver uma determinada aplicação em mente, poderá escolher um bom conjunto de propriedades/medidas para testar e trabalhar com elas - esta parece ser a maneira como os criptógrafos lidam com as coisas.
Há muita teoria sobre testar a aleatoriedade.Para um teste muito simples em um algoritmo de embaralhamento de cartas, você poderia fazer vários embaralhamentos e, em seguida, executar um teste qui-quadrado para verificar se a probabilidade de cada carta aparecer em qualquer posição era uniforme.Mas isso não testa se cartas consecutivas não estão correlacionadas, então você também gostaria de fazer testes sobre isso.
O Volume 2 de Art of Computer Programming de Knuth fornece vários testes que você pode usar nas seções 3.3.2 (Testes Empíricos) e 3.3.4 (O Teste Espectral) e a teoria por trás deles.
Embaralhe bastante e registre os resultados (se estiver lendo corretamente).Lembro-me de ver comparações de "geradores de números aleatórios".Eles apenas testam repetidamente e depois representam graficamente os resultados.
Se for verdadeiramente aleatório, o gráfico será praticamente uniforme.
A única maneira de testar a aleatoriedade é escrever um programa que tente construir um modelo preditivo para os dados que estão sendo testados e, em seguida, usar esse modelo para tentar prever dados futuros e, então, mostrar que a incerteza, ou entropia, de suas previsões tendem para o máximo (ou seja,a distribuição uniforme) ao longo do tempo.É claro que você sempre não terá certeza se seu modelo capturou ou não todo o contexto necessário;dado um modelo, sempre será possível construir um segundo modelo que gere dados não aleatórios que pareçam aleatórios para o primeiro.Mas contanto que você aceite que a órbita de Plutão tem uma influência insignificante nos resultados do algoritmo de embaralhamento, então você deverá ser capaz de se certificar de que seus resultados são aceitavelmente aleatórios.
Claro, se você fizer isso, você também poderá usar seu modelo generativamente, para realmente criar os dados desejados.E se você fizer isso, você estará de volta à estaca zero.
Não estou acompanhando totalmente sua pergunta.Você diz
Suponha que você tenha um algoritmo que gera aleatoriedade.Agora, como você testa isso?
O que você quer dizer?Se você está assumindo que pode gerar aleatoriedade, não há necessidade de testá-la.
Depois de ter um bom gerador de números aleatórios, é fácil criar uma permutação aleatória (por exemplo,Ligue para seus cartões 1-52.Gere 52 números aleatórios atribuindo cada um a um cartão em ordem e depois classifique de acordo com seus 52 números aleatórios.Você não vai destruir a aleatoriedade do seu bom RNG gerando sua permutação.
A questão difícil é se você pode confiar no seu RNG. Aqui está um exemplo de link para pessoas que discutem esse assunto em um contexto específico.
Testando 52!possibilidades é obviamente impossível.Em vez disso, tente embaralhar um número menor de cartas, como 3, 5 e 10.Então você pode testar bilhões de embaralhamentos e usar um histograma e o teste estatístico do qui-quadrado para provar que cada permutação ocorre um número “par” de vezes.
Nenhum código até agora, portanto copiei e colei uma parte de teste de minha resposta para a pergunta original.
// ...
int main() {
typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
Map freqs;
Deck d;
const size_t ntests = 100000;
// compute frequencies of events: card at position
for (size_t i = 0; i < ntests; ++i) {
d.shuffle();
size_t pos = 0;
for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos)
++freqs[std::make_pair(pos, *j)];
}
// if Deck.shuffle() is correct then all frequencies must be similar
for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
std::cout << "pos=" << j->first.first << " card=" << j->first.second
<< " freq=" << j->second << std::endl;
}
Este código não testa a aleatoriedade do gerador de números pseudoaleatórios subjacente.Testar a aleatoriedade do PRNG é todo um ramo da ciência.
Para um teste rápido, você sempre pode tentar compactá-lo.Uma vez que não seja compactado, você poderá passar para outros testes.
Eu tentei mais obstinadamente, mas ele se recusa a funcionar para uma mudança aleatória.Todos os testes falham.Também é muito pesado, não permite especificar o intervalo de valores desejado ou algo parecido.
Refletindo sobre isso, o que eu faria seria algo como:
Configuração (pseudocódigo)
// A card has a Number 0-51 and a position 0-51
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values
ShuffleCards();
ForEach (card in Cards) {
StatMatrix[Card.Position][Card.Number]++;
}
Isto nos dá uma matriz 52x52 indicando quantas vezes uma carta acabou em uma determinada posição.Repita isso um grande número de vezes (eu começaria com 1000, mas pessoas melhores em estatística do que eu podem fornecer um número melhor).
Analise a matriz
Se tivermos uma aleatoriedade perfeita e embaralharmos um número infinito de vezes, então para cada carta e para cada posição o número de vezes que a carta terminou naquela posição é o mesmo que para qualquer outra carta.Dizendo a mesma coisa de uma maneira diferente:
statMatrix[position][card] / numberOfShuffle = 1/52.
Então, eu calcularia a que distância estamos desse número.
