Comprobar si una cadena de caracteres no es aleatoria

Question

Antecedentes
Digamos que tenemos un alfabeto de A,B, C, D , entonces buscamos entre algunos datos y encontramos una "palabra" que es DDDDDDDDCDDDDDD la posibilidad de encontrar este azar me parece baja mientras que encontrar BABDCABCDACDBACD parece menos aleatorio.

Pregunta
¿Cómo puedo comprobar si las cadenas que encuentro no son aleatorias?

He intentado algunas cosas en R, por ejemplo, codificar las letras numéricamente y luego compararlas con las permutaciones. Pero la codificación previa es bastante engorrosa. ¿Es probable que haya un enfoque más directo para esto?

Answer 1

la posibilidad de encontrar esto al azar me parece baja mientras que encontrar BABDCABCDACDBACD parece menos al azar.

¿Por qué? Si la proporción global de letras A...D es igual a 0,25 para cada letra, y cada letra es independiente de la otra, entonces ambas palabras son exactamente igual de probables. Si la distribución de las letras es diferente, entonces, por supuesto, las probabilidades de generar ambas palabras pueden ser diferentes.

Se puede intentar encontrar palabras de "baja complejidad", por ejemplo, palabras con una proporción especialmente alta de una letra (se podría utilizar la información de Shannon, como se sugiere en la otra respuesta, y en el análisis de secuencias biológicas hay muchos otros enfoques), pero no hay ninguna prueba de "aleatoriedad", ya que sin más suposiciones o conocimientos sobre lo que realmente se está analizando, el término "aleatoriedad" no tiene sentido.

Answer 2

Puedes probar con la información de Shannon: $$ H = -\sum_{i = 0}^n {P_{i}\log_{2}(P_{i})} $$ donde, $P_{i} = \frac{c_{i}}{n}$ , $c_{i}$ es el recuento de alguna letra $c$ en la palabra y $n = |{\rm word}|$ .

Para la primera palabra tienes $H = 0.35$ . En la segunda palabra tiene $H = 2$ .

Si la entropía es alta, se podría pensar que es más aleatoria frente a otra palabra con menor entropía.

Answer 3

Otras respuestas se han centrado en la ocurrencia general de diferentes letras en la secuencia, que puede ser un aspecto de la "aleatoriedad" esperada. Sin embargo, otro aspecto de interés es la aparente aleatoriedad en la pedir de las letras de la secuencia. Como mínimo, creo que la "aleatoriedad" implica la intercambiabilidad del vector de letras, que puede comprobarse mediante una "prueba de carreras". La prueba de carreras cuenta el número de "carreras" en la secuencia y compara el número total de carreras con su distribución nula bajo la hipótesis nula de intercambiabilidad, para un vector con las mismas letras. La definición exacta de lo que constituye una "carrera" depende de la prueba concreta (véase, por ejemplo, una respuesta similar aquí ), pero en este caso, con categorías nominales, la definición natural es contar cualquier secuencia consecutiva que conste de una sola letra como una sola "carrera".

Por ejemplo, su secuencia BABD-CABC-DACD-BACD mira a primera vista no me parece aleatorio (ninguna letra aparece con ella misma, lo que probablemente es inusual para una secuencia tan larga). $^\dagger$ Para comprobarlo formalmente, podemos realizar una prueba de intercambiabilidad. En esta secuencia tenemos $n = 16$ letras (cuatro de cada letra) y hay $r = 16$ carreras, cada una de las cuales consiste en una sola instancia de una letra. El número de ejecuciones observado puede compararse con su distribución nula bajo la hipótesis de intercambiabilidad. Podemos hacerlo mediante una simulación, que arroja una distribución nula simulada y un valor p para la prueba. El resultado para esta secuencia de caracteres se muestra en el siguiente gráfico.

Para esta secuencia, el valor p de la prueba de las carreras (bajo la hipótesis nula de intercambiabilidad) es $p=0.0537$ . Esto es significativo al nivel de significación del 10%, pero no al del 5%. Hay algunas pruebas que sugieren una serie no intercambiable (es decir, un orden no aleatorio), pero las pruebas no son especialmente sólidas. Con una serie observada más larga, la prueba de corridas tendría mayor poder para distinguir una serie intercambiable de una no intercambiable. (Como puede ver, mi a primera vista El juicio de que esta cadena no es aleatoria puede ser erróneo: el valor p no es en realidad tan bajo como esperaba).

Por último, es importante tener en cuenta que esta prueba sólo examina la aleatoriedad del pedir de las letras de la cadena - toma el número de letras de cada tipo como entrada fija. Esta prueba detectará la no aleatoriedad en el sentido de la no intercambiabilidad de las letras de la cadena, pero no comprobará la "aleatoriedad" en el sentido de las probabilidades globales de las diferentes letras. Si esto último también forma parte del significado especificado de "aleatoriedad", esta prueba de ejecución podría aumentarse con otra prueba que examine los recuentos globales de las letras y los compare con una distribución nula hipotética.

---

Código R: El gráfico anterior y el valor p se generaron utilizando lo siguiente R có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$ He dividido la secuencia con guiones únicamente para facilitar la lectura; los guiones no tienen ninguna importancia para el análisis.

Answer 4

Suponiendo que la cadena de letras sea lo suficientemente larga, se puede aplicar Pruebas de aleatoriedad en los datos.

Un conjunto de estas pruebas se denomina pruebas de resistencia :

Las pruebas diehard son una batería de pruebas estadísticas para medir la calidad de un generador de números aleatorios. Fueron desarrolladas por George Marsaglia a lo largo de varios años y publicadas por primera vez en 1995 en un CD-ROM de números aleatorios.

Implican un conjunto, quizás arbitrario, de pruebas como:

• Espacios para cumpleaños
• Permutaciones superpuestas
• Rangos de matrices
• Pruebas con monos
• Cuente los 1s
• Prueba de estacionamiento
• Prueba de distancia mínima
• Prueba de esferas aleatorias
• La prueba de apriete
• Prueba de sumas superpuestas
• Realiza la prueba
• La prueba de los dados

Una buena secuencia de datos aleatorios debería pasar estas pruebas.

Sin embargo, pasar estas pruebas no es suficiente para probar los números no codifican una señal real. Podrían ser la salida de una rutina de encriptación de alta calidad.