Melhor maneira de determinar se uma lista de bytes é aleatória?

8

Existe algum algoritmo por aí que pode retornar algum valor indicando um nível de aleatoriedade? Eu acredito que se chama Entropia de Dados .

Li recentemente este artigo: http://faculty.rhodes.edu/wetzel/random/mainbody.html

Sua abordagem de analisar lançamentos de moedas se aplica a bytes? Devo descer para o nível de bit em que é verdadeiro / falso novamente ou existe uma maneira de determinar com base no valor total de bytes?

Suas análises são melhores do que este artigo?

Corey Ogburn
fonte

Respostas:

16

No TCS, outra abordagem para esse problema tem sido o teste de propriedades das distribuições , em que se deve distinguir se uma distribuição é (verdadeiramente) uniforme ou se "não chega nem perto" de ser uniforme (de maneira formal). Aqui se obtém limites precisos sobre o número de amostras necessárias para decidir sobre a questão.

Consulte, por exemplo, a Seção 6 do seguinte tutorial: http://people.csail.mit.edu/ronitt/papers/icm.ps

[n]ϵO(n/ϵ4)Ω(n)

Alex Andoni
fonte
Curiosamente, todos esses métodos assumem que a distribuição é iid. Ou seja, uma sequência cíclica simples, como 123123123 com entropia muito baixa, seria considerada uniforme com alta probabilidade. Você sabe se alguém considerou o teste de distribuição para sequências não-iid?
Thomas Ahle
Eu escrevi isso para verificar coisas como seqüências simples e detectar variações brutas de distribuições uniformes de bytes aleatórios ... funciona muito bem: github.com/earonesty/dotfiles/blob/master/randbytestest.py .
Erik Aronesty 14/01/19
6

Não existe um algoritmo correto para medir a aleatoriedade. Vários testes estatísticos são uma abordagem possível, como os outros já disseram. Outra possibilidade é comprimir a sequência de bytes e ver o que acontece. Se você obtiver cerca de 8 bits / byte (ou mais), a sequência será aleatória em relação ao modelo de dados subjacente ao compressor.

Dos métodos de compactação padrão, o PPM usa um modelo estatístico explícito para prever o próximo caractere com base no contexto anterior. Sua principal fraqueza é que não pode utilizar repetitividade em larga escala, como repetições idênticas de uma longa sequência aleatória.

Os métodos de compactação baseados na análise LZ77 ou na BWT (Burrows-Wheeler Transform) têm bom desempenho quando existem muitas substrings repetidas na sequência. No entanto, muitas implementações práticas têm tamanho limitado de bloco / janela para economizar memória, tornando-as também incapazes de utilizar repetitividade em larga escala.

Em vez de compactar a sequência, você também pode calcular algumas medidas relacionadas ao modelo de dados do compressor: entropia empírica de ordem superior para PPM, número de letras iguais executadas no BWT ou número de frases na análise do LZ77. Nos dois primeiros casos, 8 bits de entropia por byte ou n (1 - 1/256) são executados para uma sequência de comprimento n significa dados totalmente aleatórios.

Jouni Sirén
fonte
5

Do random.org:

Curiosamente, é teoricamente impossível provar que um gerador de números aleatórios é realmente aleatório. Em vez disso, você analisa uma quantidade crescente de números produzidos por um determinado gerador e, dependendo dos resultados, sua confiança no gerador aumenta (ou diminui, conforme o caso)

Mais informações podem ser encontradas aqui

Niels
fonte
4

http://www.phy.duke.edu/~rgb/General/dieharder.php

whuber
fonte
bom para números, pouco adequado para seqüências de bytes. poderia adaptá-lo embora
Erik Aronesty
@Erik É facilmente aplicado de várias maneiras. Tudo que você precisa é uma maneira de usar o RNG para criar sequências de bits - e uma sequência de bytes já é uma sequência de bits.
whuber
acho que não vi como aplicá-lo a, digamos, uma matriz de 30 amostras de sequências de 32 bytes. parece muito abrangente ... e fácil de usar ( apt install dieharder).
Erik Aronesty
1
@Erik Os documentos dizem que "o dieharder prefere testar geradores agrupados em uma interface compatível com GSL, para que eles possam retornar um fluxo ilimitado de números aleatórios". Para esse propósito, uma sequência de 32 bytes pode ser interpretada como uma sequência de 8 curtos não assinados, 4 longos não assinados, etc. É bastante flexível, mas você precisa escrever uma interface.
whuber
@ErikAronesty: 30 * 32 bytes simplesmente não são dados suficientes e nenhum teste de aleatoriedade será capaz de contornar esse fato. O Dieharder (por um bom motivo) rirá do tamanho da sua amostra até que você tenha aproximadamente 1 GB de dados.
Jay Sullivan
3

A complexidade de Kolmogorov é uma maneira de medir a aleatoriedade das seqüências de caracteres e é algoritmicamente incontestável. Usando essa noção, é impossível medir a aleatoriedade de todas as strings. A existência desse algoritmo poderia ser usada para resolver o problema da parada.

Mohammad Al-Turkistany
fonte
3

Como outras respostas mencionadas, a versão de decisão desse problema (como o problema da parada e vários outros problemas, como o problema do lado a lado) é indecidível. No entanto, acredito que você está perguntando sobre maneiras práticas de medir a aleatoriedade de uma coleção de bits.

A prática padrão aqui é executar os dados através de uma série de testes aleatórios, como o teste do qui-quadrado.

Ross Snider
fonte
3

ip(i1/n,,ik/n)

Na prática, não há um teste universal para a aleatoriedade do fluxo; em vez disso, há uma série de testes. Se o seu fluxo tentar k dos melhores testes e passar em todos eles, podemos ter certeza razoável de que é aleatório ... até que alguém invente k + 1 ' primeiro teste que o quebra.

Aqui está o que Knuth diz sobre isso em "Art of Computer Algorithms, Vol 2"

"Se uma sequência se comporta aleatoriamente em relação aos testes T1, T2, ..., Tn, em geral não podemos ter certeza de que não será uma falha miserável quando for submetida a outro teste T (n + 1). cada teste nos dá mais e mais confiança na aleatoriedade da sequência.Na prática, aplicamos cerca de meia dúzia de tipos diferentes de testes estatísticos a uma sequência e, se os passar satisfatoriamente, consideramos aleatório - presume-se que inocente até que se prove a culpa."

Eu recomendo a leitura da seção "Arte dos algoritmos de computador" de Knuth 3.1 para introdução geral à pseudo-aleatoriedade e 3.3 sobre testes estatísticos para fluxos.

Yaroslav Bulatov
fonte
0

Fiz um conjunto de testes bastante fraco que, no entanto, foi muito útil para mim e indicativo da natureza dos testes de aleatoriedade em geral:

  1. gerar uma estatística para "dados aleatórios bons conhecidos" (matematicamente ou empiricamente)
  2. gere a mesma estatística para seus dados de amostra (esperamos que você tenha pelo menos 30 amostras)
  3. obter um valor de p para a diferença (hipóteses: são de diferentes distribuições)
  4. repita para N estatísticas
  5. bonferonni corrige os resultados (divida por N)

A fonte está aqui: https://github.com/earonesty/dotfiles/blob/master/randbytestest.py

Erik Aronesty
fonte