algorithm - tabla - pruebas de aleatoriedad ejemplos
Una buena y simple medida de aleatoriedad (10)
"¿Qué tan aleatoria es esta secuencia?" es una pregunta difícil porque fundamentalmente le interesa cómo se generó la secuencia. Como otros han dicho, es totalmente posible generar secuencias que parecen aleatorias, pero que no provienen de fuentes que consideremos aleatorias (por ejemplo, dígitos de pi).
La mayoría de las pruebas de aleatoriedad intentan responder preguntas ligeramente diferentes, que son: "¿Es esta secuencia anómala con respecto a un modelo dado?". Si su modelo está lanzando dados de diez caras, entonces es bastante fácil cuantificar la probabilidad de que se genere una secuencia a partir de ese modelo, y los dígitos de pi no se verán anómalos. Pero si su modelo es "¿Se puede generar fácilmente esta secuencia a partir de un algoritmo?" se vuelve mucho más difícil.
¿Cuál es el mejor algoritmo para tomar una secuencia larga de enteros (digamos 100,000 de ellos) y devolver una medición de qué tan aleatoria es la secuencia?
La función debería devolver un único resultado, digamos 0 si la secuencia no es completamente aleatoria, hasta, digamos 1 si es perfectamente aleatorio. Puede dar algo intermedio si la secuencia es algo aleatoria, por ejemplo, 0.95 podría ser una secuencia razonablemente aleatoria, mientras que 0.50 podría tener algunas partes no aleatorias y algunas partes aleatorias.
Si tuviera que pasar los primeros 100.000 dígitos de Pi a la función, debería dar un número muy cercano a 1. Si aprobé la secuencia 1, 2, ... 100.000, debería devolver 0.
De esta forma, puedo tomar fácilmente 30 secuencias de números, identificar cuán aleatorio es cada uno y devolver información sobre su aleatoriedad relativa.
¿Hay tal animal?
@JohnFx "... matemáticamente imposible".
estados del póster: toma una larga secuencia de enteros ...
Por lo tanto, tal como se usan los límites en The Calculus, podemos tomar el valor como el valor: el estudio de Chaotics nos muestra que los límites finitos pueden ''encenderse'' produciendo campos de tensor que proporcionan la ilusión de absoluto (s), y que se puede ejecutar mientras haya tiempo y energía. Debido a la curvatura del espacio-tiempo, no existe la perfección, por lo tanto, la operación " ... decir 1 si es perfectamente aleatoria " es un nombre inapropiado.
{ notado : se han proporcionado amplias observaciones sobre eso - sálvame}
De acuerdo con su posición, dado dos bytes [] de unos k, cada uno aleatorio independientemente - op no pudo obtener "una medida de cuán aleatoria es la secuencia" El artículo en Wiki es informativo, y hace avances definidos para desenmarañar el asunto, pero
En comparación con la física clásica, la física cuántica predice que las propiedades de un sistema mecánico cuántico dependen del contexto de medición, es decir, si se llevan a cabo o no otras mediciones del sistema.
Un equipo de físicos de Innsbruck, Austria, dirigido por Christian Roos y Rainer Blatt, ha demostrado por primera vez en un experimento integral que no es posible explicar los fenómenos cuánticos en términos no contextuales.
Fuente: Science Daily
Consideremos movimientos de lagarto no aleatorios. La fuente del estímulo que inicia movimientos complejos en las colas de los geckos leopardo, bajo su hipertesis original corregida, nunca puede ser conocida. Nosotros, los experimentados informáticos, sufrimos el desafío inocente planteado por los novatos sabiendo muy bien que allí, en el contexto de una mente intacta y prístina, están las gemas y los germinadores del pensamiento avanzado.
Si el campo de pensamiento de la lagartija original produce un campo de tensor (se trata de gente, esto es investigación de primera línea en física sublineal) entonces podríamos tener "el mejor algoritmo para tomar una secuencia larga" de civilizaciones que abarcan desde el Evento Toba para presentar a través de una Inversión Caótica ". Considere la cuestión de si ese campo de pensamiento producido por el lagarto, tomado independientemente, es espeluznante o cognoscible.
"Observación directa de la paradoja de Hardy mediante mediciones débiles conjuntas con un par de fotones entrelazados", escrito por Kazuhiro Yokota, Takashi Yamamoto, Masato Koashi y Nobuyuki Imoto de la Escuela de Graduados de Ciencias de la Ingeniería en la Universidad de Osaka y el Proyecto de Información Fotónica Cuántica CREST en la ciudad de Kawaguchi
Fuente: Science Daily
(considerando la dicotomía spooky / cognoscible)
Sé por mis propios experimentos que la observación directa debilita la absolutez de los tensores perceptibles, es imposible distinguir entre el pensamiento y los tensores perceptibles usando solo técnicas de enfoque único porque el tensor perceptible no es el pensamiento original. Una consecuencia fundamental del quantaeus es que solo los estados débiles de tensores perceptibles se pueden distinguir confiablemente entre sí sin causar un colapso en un tensor perceptible unificado. Pruébelo alguna vez: trabaje en la conservación de alguna eventualidad deseada, utilizando el pensamiento puro. Como una idea no tiene tiempo ni espacio, es infinita. (no finito) y, por lo tanto, puede alcanzar la "perfección", es decir, la absolutez. Solo por una pista, comience con el clima ya que es lo más fácil de influenciar (al menos hasta donde se conoce actualmente) luego muévase lo más pronto posible para hacer una combinación desde el estado de reposo hasta el estado de vigilia con prácticamente no hay interrupción de encadenamiento secuencial.
Hay un bache casi inevitable allí cuando el cuerpo se despierta, pero es como cuando suena el timbre, lo que trae un área interesante de investigación estadística a la disponibilidad de fondos: ¿cuántos pensamientos se pueden mantener sincrónicamente? Encuentro que la dualidad es el límite de trabajo práctico, en triune o se rompe en el siguiente pensamiento o no dura mucho.
Tal vez el trabajo de Yokota et al podría revelar la fuente del tráfico neto espurio ... quizás sean fantasmas.
Como han señalado otros, no se puede calcular directamente qué tan aleatoria es una secuencia, pero hay varias pruebas estadísticas que se pueden usar para aumentar su confianza en que una secuencia es o no aleatoria.
El paquete DIEHARD es el estándar de facto para este tipo de prueba, pero no devuelve ningún valor ni es simple.
ENT: un programa de prueba de secuencia de número pseudoaleatorio , es una alternativa más simple que combina 5 pruebas diferentes. El sitio web explica cómo funciona cada una de estas pruebas.
Si realmente necesita un solo valor, puede elegir una de las 5 pruebas ENT y usar eso. La prueba de Chi-cuadrado probablemente sea la mejor para usar, pero es posible que no cumpla con la definición de simple.
Tenga en cuenta que una sola prueba no es tan buena como ejecutar varias pruebas diferentes en la misma secuencia. Dependiendo de la prueba que elijas, debería ser lo suficientemente buena como para marcar las secuencias obviamente sospechosas como no aleatoria, pero podría no fallar para las secuencias que superficialmente parecen aleatorias pero que en realidad muestran algún patrón.
De acuerdo con Knuth, asegúrese de probar los bits de orden bajo para la aleatoriedad, ya que muchos algoritmos exhiben una terrible aleatoriedad en los bits más bajos.
En Computer Vision, al analizar texturas, surge el problema de tratar de medir la aleatoriedad de una textura para segmentarla. Esto es exactamente lo mismo que su pregunta, porque está tratando de determinar la aleatoriedad de una secuencia de bytes / enteros / flotantes. La mejor discusión que pude encontrar sobre la entropía de la imagen es http://www.physicsforums.com/showthread.php?t=274518 .
Básicamente, es la medida estadística de aleatoriedad para una secuencia de valores.
También probaría la autocorrelación de la secuencia consigo misma. En el resultado de la autocorrelación, si no hay más picos que el primer valor, significa que no hay periodicidad para su entrada.
Lo que buscas no existe, al menos no cómo lo estás describiendo ahora.
El problema básico es este:
Si es aleatorio, pasará las pruebas de aleatoriedad; pero lo contrario no es válido: no hay ninguna prueba que pueda verificar la aleatoriedad.
Por ejemplo, uno podría tener correlaciones muy fuertes entre elementos muy alejados y, en general, uno debería probarlo explícitamente. O uno podría tener una distribución plana, pero generada de una manera no aleatoria. Etcétera etcétera.
Al final, debe decidir qué aspectos de la aleatoriedad son importantes para usted y evaluarlos (como describe James Anderson en su respuesta). Estoy seguro de que si piensas en alguno que no sea obvio como probar, la gente aquí te ayudará.
Por cierto, generalmente abordo este problema desde el otro lado: me dan algunos datos que buscan que todo lo que puedo ver sea completamente aleatorio, pero necesito determinar si hay algún patrón en alguna parte. Muy no obvio, en general.
Podría intentar comprimir rápidamente la secuencia. Cuanto mejor triunfe, menos aleatoria es la secuencia.
Por lo tanto, aleatoriedad heurística = longitud del código postal / longitud de la secuencia original
Puede tratar 100.000 salidas como posibles resultados de una variable aleatoria y calcular la entropía asociada de la misma. Le dará una medida de incertidumbre. (La siguiente imagen es de wikipedia y puedes encontrar más información sobre Entropy allí). Simplemente:
Solo necesita calcular las frecuencias de cada número en la secuencia. Eso le dará p (xi) (por ej., Si 10 aparece 27 veces p (10) = 27 / L donde L es 100.000 para su caso.) Esto debería darle la medida de entropía.
Aunque no le dará un número entre 0 y 1. Aún 0 será una incertidumbre mínima. Sin embargo, el límite superior no será 1. Necesita normalizar el resultado para lograrlo.
Se puede hacer de esta manera:
CAcert Research Lab realiza un análisis de generador de números aleatorios .
Su página de resultados evalúa cada secuencia aleatoria usando 7 pruebas (Entropía, espaciado de cumpleaños, rangos de matriz, rangos de matriz de 6x8, distancia mínima, esferas aleatorias y el apretón). Cada resultado de la prueba se codifica por color como uno de "Sin problemas", "Potencialmente determinista" y "No aleatorio".
Entonces se puede escribir una función que acepte una secuencia aleatoria y haga las 7 pruebas. Si alguna de las 7 pruebas es "No aleatoria", la función devuelve 0. Si todas las 7 pruebas son "Sin problemas", devuelve 1. De lo contrario, puede devolver algún número intermedio en función de cuántos las pruebas aparecen como "Potencialmente deterministas".
Lo único que falta en esta solución es el código para las 7 pruebas.
Tu pregunta se responde a sí misma. "Si tuviera que pasar los primeros 100.000 dígitos de Pi a la función, debería dar un número muy cercano a 1", excepto que los dígitos de Pi no son números aleatorios, así que si su algoritmo no reconoce una secuencia muy específica como no al azar, entonces no es muy bueno.
El problema aquí es que hay muchos tipos de no aleatorio: por ejemplo. "121,351,991,7898651,12398469018461" o "33,27,99,3000,63,231" o incluso "14297141600464,14344872783104,819534228736,3490442496" definitivamente no son aleatorios.
Creo que lo que debes hacer es identificar los aspectos de la aleatoriedad que son importantes para ti: distribución, distribución de dígitos, falta de factores comunes, número esperado de números primos, número de fibonacci y otros números "especiales", etc.
PD. La prueba de aleatoriedad rápida y sucia (y muy efectiva) es que el archivo termina más o menos del mismo tamaño después de que gzip.