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

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.

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.

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

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

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

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.$^\dagger$$n = 16$$r = 16$

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'); 

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

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.