Verifique se uma sequência de caracteres não é aleatória

8

Antecedentes
Digamos que temos um alfabeto de A,B, C, D, em seguida, examinamos alguns dados e encontramos uma "palavra" que é DDDDDDDDCDDDDDDa chance de encontrar essa aleatória me parece baixa, enquanto a descoberta BABDCABCDACDBACDparece menos aleatória.

Pergunta
Como devo verificar se as strings que encontro não são aleatórias?

Eu tentei algumas coisas em R, por exemplo, codificando as letras numericamente e comparando-as com permutações. Mas a codificação antecipada é bastante complicada, provavelmente existe uma abordagem mais direta para isso.

CodeNoob
fonte
12
O que exatamente você quer dizer com "aleatório" neste contexto?
gung - Restabelece Monica
3
Você pode criar uma máquina de estado de n bits e depois registrar quantas previsões erradas ela faz. Mais ou menos como o preditor de ramificação de uma CPU.
21818 Alexyorke #
11
Você pode calcular a probabilidade de que uma sequência de caracteres tenha sido gerada por algum processo conhecido específico. Não se sabe se é "aleatório" (e provavelmente não é uma pergunta significativa).
OrangeDog
2
Você pode verificar com a contabilidade .
hlovdal
2
Se você estiver focado nas frequências das letras, e não nas seqüências, o teste do qui-quadrado da frequência real versus a esperada é comum. Ou seja, se o seu primeiro exemplo for "ímpar" porque possui muitos "D", enquanto o segundo tiver um número bastante igual de "A", "B", "C" e "D", então você ' gostaria de comparar o número de cada um de A, B, C e D versus o que você esperaria. (Números Talvez aproximadamente iguais de A, B, C, D, ou talvez o dobro de um como de B e duas vezes como muitos B de C como de ou D.)
Wayne

Respostas:

19

a chance de encontrar esse acaso me parece baixa, enquanto que encontrar BABDCABCDACDBACD parece menos aleatório.

Por que isso seria? Se a proporção geral de letras A ... D é igual a 0,25 para cada letra e cada letra é independente da outra, as duas palavras são exatamente igualmente prováveis. Se a distribuição das letras for diferente, é claro que as probabilidades de gerar as duas palavras podem ser diferentes.

Você pode tentar encontrar palavras de "baixa complexidade", por exemplo, palavras com uma proporção especialmente alta de uma letra (você pode usar as informações de Shannon conforme sugerido na outra resposta e, na análise de sequência biológica, existem muitas outras abordagens), mas existem não é um teste para "aleatoriedade", pois sem outras suposições ou conhecimento sobre o que você está realmente analisando, o termo "aleatoriedade" não faz sentido.

janeiro
fonte
10
"ambas as palavras são exatamente igualmente prováveis" seria um ótimo lugar para uma ênfase ousada.
Tashus 10/10
11
"Se a proporção total de letras A ... D for igual a 0,25 para cada letra ...". Não, na verdade toda palavra possível é tão provável quanto qualquer outra, qualquer que seja a proporção de letras da palavra.
precisa
6
@DJClayworth Acredito que a intenção dessa linha é dizer que, em vez de A: .25 B: .25 C: .25 D.25, temos A: .5, B: .25, C: .125, D : .125, a chance de obter a palavra ABAA é muito mais provável no segundo caso que no primeiro, e CDBD é igualmente provável como ABAA no primeiro cenário, mas menos provável que ABAA no segundo. Assim, a chance de uma determinada palavra depende da 'proporção' de letras em relação a outras possíveis proporções.
111018 ale10ander
17

Você pode tentar as informações de Shannon: onde, , é a contagem de algumas letras na palavra en.

H=i=0nPilog2(Pi)
Pi=cincicn=|word|

Para a primeira palavra, você tem . Na segunda palavra, você tem .H=0.35H=2

Se a entropia for alta, você pode pensar nela como mais aleatória do que outra palavra com menor entropia.

Edvrsoft
fonte
Este é um bom caminho a percorrer para detectar a imprevisibilidade de uma string, e eu votei, mas seu critério daria os mesmos resultados para ambos bababbaabbe aaaabbbbbb. A noção, reconhecidamente muito vaga, de "aleatoriedade" usada pelo OP provavelmente consideraria a primeira como "mais aleatória" que a segunda.
ymbirtt
8

Outras respostas aqui se concentraram na ocorrência geral de letras diferentes na sequência, que pode ser um aspecto da "aleatoriedade" esperada. No entanto, outro aspecto de interesse é a aparente aleatoriedade na ordem das letras na sequência. No mínimo, eu pensaria que a "aleatoriedade" implica a permutabilidade do vetor de letras, que pode ser testada usando um "teste de execução". O teste de execuções conta o número de "execuções" na sequência e compara o número total de execuções com sua distribuição nula sob a hipótese nula de permutabilidade, para um vetor com as mesmas letras. A definição exata do que constitui uma "execução" depende do teste específico (consulte, por exemplo, uma resposta semelhante aqui), mas neste caso, com categorias nominais, a definição natural é contar qualquer sequência consecutiva que consiste em apenas uma letra como uma "execução" única.

Por exemplo, sua sequência BABD-CABC-DACD-BACDparece prima facie não aleatória para mim (nenhuma letra aparece consigo mesma, o que provavelmente é incomum para uma sequência por tanto tempo). Para testar isso formalmente, podemos executar um teste de execução para troca. Nesta sequência, temos letras (quatro de cada letra) e existem execuções, cada uma consistindo em uma única instância de uma letra. O número observado de execuções pode ser comparado à sua distribuição nula sob a hipótese de permutabilidade. Podemos fazer isso via simulação, que gera uma distribuição nula simulada e um valor p para o teste. O resultado para esta sequência de caracteres é mostrado no gráfico abaixo.n=16r=16

insira a descrição da imagem aqui

Para esta sequência, o valor de p para o teste de execuções (sob a hipótese nula de ) é . Isso é significativo no nível de significância de 10%, mas não no nível de significância de 5%. Há alguma evidência para sugerir uma série não permutável (isto é, ordem não aleatória), mas a evidência não é particularmente forte. Com uma sequência mais longa observada, o teste de execução teria maior poder para distinguir uma sequência trocável de uma sequência não trocável. (Como você pode ver, meu julgamento inicial prima facie de que essa sequência não é aleatória pode estar errada - o valor de p não é tão baixo quanto eu esperava.)p=0.0537

Por fim, é importante observar que esse teste apenas analisa a aleatoriedade da ordem das letras na sequência - toma o número de letras de cada tipo como uma entrada fixa. Este teste detectará não aleatoriedade no sentido de não permutabilidade das letras na sequência, mas não testará "aleatoriedade" no sentido de probabilidades gerais de letras diferentes. Se o último também fizer parte do significado especificado de "aleatoriedade", esse teste de execução poderá ser aumentado com outro teste que analise as contagens gerais das letras e o compare com uma distribuição nula hipotética.


Código R: O gráfico e o valor p acima foram gerados usando o seguinte Rcódigo:

#Define the character string vector (as factors)
x <- factor(c(2,1,2,4, 3,1,2,3, 4,1,3,4, 2,1,3,4), 
            labels = c('A', 'B', 'C', 'D'))

#Define a function to calculate the runs for an input vector
RUNS <- function(x) { n <- length(x);
                      R <- 1;
                      for (i in 2:n) { R <- R + (x[i] != x[i-1]) }
                      R; }

#Simulate the runs statistic for k permutations
k <- 10^5;
set.seed(12345);
RR <- rep(0, k);
for (i in 1:k) { x_perm <- sample(x, length(x), replace = FALSE);
                 RR[i] <- RUNS(x_perm); }

#Generate the frequency table for the simulated runs
FREQS <- as.data.frame(table(RR));

#Calculate the p-value of the runs test
R      <- RUNS(x);
R_FREQ <- FREQS$Freq[match(R, FREQS$RR)];
p      <- sum(FREQS$Freq*(FREQS$Freq <= R_FREQ))/k;

#Plot estimated distribution of runs with test
library(ggplot2);
ggplot(data = FREQS, aes(x = RR, y = Freq/k, fill = (Freq <= R_FREQ))) +
geom_bar(stat = 'identity') +
geom_vline(xintercept = match(R, FREQS$RR)) +
scale_fill_manual(values = c('Grey', 'Red')) +
theme(legend.position = 'none',
      plot.title      = element_text(hjust = 0.5, face = 'bold'),
      plot.subtitle   = element_text(hjust = 0.5),
      axis.title.y    = element_text(margin = margin(t = 0, r = 10, b = 0, l = 0))) +
labs(title    = 'Runs Test - Plot of Distribution of Runs under Exchangeability',
     subtitle = paste0('(Observed runs is black line, p-value = ', p, ')'),
     x = 'Runs', y = 'Estimated Probability'); 

quebrei a sequência com traços apenas para facilitar a leitura; os traços não têm significado para a análise.

Ben - Restabelecer Monica
fonte
11
Interessante! definitivamente dará uma olhada no script R
KingBoomie
1

Supondo que a sequência de letras seja longa o suficiente, você pode aplicar testes de aleatoriedade nos dados.

Um conjunto desses testes é chamado de testes obstinados :

Os testes obstinados 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.

Eles envolvem um conjunto de testes, talvez arbitrário, como:

  • Espaçamentos de aniversário
  • Permutações sobrepostas
  • Classes de matrizes
  • Testes em macacos
  • Conte os 1s
  • Teste de estacionamento
  • Teste de distância mínima
  • Teste de esferas aleatórias
  • O teste de compressão
  • Teste de somas sobrepostas
  • Executa o teste
  • O teste de dados

Uma boa sequência de dados aleatórios deve passar nesses testes.

No entanto, passar nesses testes não é suficiente para provar que os números realmente não codificam um sinal real. Eles podem ser a saída de uma rotina de criptografia de alta qualidade.

Oddthinking
fonte