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?
fonte
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.
fonte
Do random.org:
Mais informações podem ser encontradas aqui
fonte
http://www.phy.duke.edu/~rgb/General/dieharder.php
fonte
apt install dieharder
).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.
fonte
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.
fonte
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.
fonte
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:
A fonte está aqui: https://github.com/earonesty/dotfiles/blob/master/randbytestest.py
fonte