El concepto de secuencia aleatoria es esencial en la teoría de la probabilidad y la estadística . El concepto generalmente se basa en la noción de una secuencia de variables aleatorias y muchas discusiones estadísticas comienzan con las palabras "sean X 1 , ..., X n variables aleatorias independientes ...". Sin embargo, como dijo DH Lehmer en 1951: "Una secuencia aleatoria es una noción vaga ... en la que cada término es impredecible para los no iniciados y cuyos dígitos pasan un cierto número de pruebas tradicionales con los estadísticos". [1]
La teoría de la probabilidad axiomática evita deliberadamente una definición de secuencia aleatoria. [2] La teoría de la probabilidad tradicional no establece si una secuencia específica es aleatoria, pero generalmente analiza las propiedades de las variables aleatorias y las secuencias estocásticas asumiendo alguna definición de aleatoriedad. La escuela de Bourbaki consideró la afirmación "consideremos una secuencia aleatoria" como un abuso del lenguaje . [3]
Historia temprana
Émile Borel fue uno de los primeros matemáticos en abordar formalmente la aleatoriedad en 1909. [4] En 1919, Richard von Mises dio la primera definición de aleatoriedad algorítmica, que se inspiró en la ley de los grandes números, aunque utilizó el término colectivo en lugar de aleatorio. secuencia. Usando el concepto de la imposibilidad de un sistema de juego , von Mises definió una secuencia infinita de ceros y unos como aleatoria si no está sesgada por tener la propiedad de estabilidad de frecuencia, es decir, la frecuencia de ceros va a 1/2 y cada subsecuencia puede seleccionar de él mediante un método de selección "adecuado" tampoco está sesgado. [5]
El criterio de selección de subsecuencia impuesto por von Mises es importante, porque aunque 0101010101 ... no está sesgado, al seleccionar las posiciones impares, obtenemos 000000 ... que no es aleatorio. Von Mises nunca formalizó totalmente su definición de una regla de selección adecuada para subsecuencias, pero en 1940 Alonzo Church la definió como cualquier función recursiva que, habiendo leído los primeros N elementos de la secuencia, decide si desea seleccionar el elemento número N + 1. Church fue un pionero en el campo de las funciones computables, y la definición que hizo se basó en la tesis de Church Turing para la computabilidad. [6] Esta definición a menudo se llama aleatoriedad de Mises-Church .
Enfoques modernos
Durante el siglo XX se desarrollaron varios enfoques técnicos para definir secuencias aleatorias y ahora se pueden identificar tres paradigmas distintos. A mediados de la década de 1960, AN Kolmogorov y DW Loveland propusieron de forma independiente una regla de selección más permisiva. [7] [8] En su opinión, la definición de función recursiva de Church era demasiado restrictiva en el sentido de que leía los elementos en orden. En su lugar, proponen una regla basada en un proceso parcialmente computable, que después de haber leído ningún N elementos de la secuencia, decide si quiere seleccionar otro elemento que no se ha leído todavía. Esta definición a menudo se denomina estocasticidad de Kolmogorov-Loveland . Pero este método fue considerado demasiado débil por Alexander Shen, quien demostró que existe una secuencia estocástica Kolmogorov-Loveland que no se ajusta a la noción general de aleatoriedad.
En 1966, Per Martin-Löf introdujo una nueva noción que ahora se considera generalmente la noción más satisfactoria de aleatoriedad algorítmica . Su definición original incluía la teoría de la medida, pero más tarde se demostró que se puede expresar en términos de complejidad de Kolmogorov . La definición de Kolmogorov de una cadena aleatoria era que es aleatoria si no tiene una descripción más corta que ella a través de una máquina universal de Turing . [9]
Ahora han surgido tres paradigmas básicos para tratar con secuencias aleatorias: [10]
- El enfoque teórico de frecuencia / medida . Este enfoque comenzó con el trabajo de Richard von Mises y Alonzo Church. En la década de 1960, Per Martin-Löf notó que los conjuntos que codifican tales propiedades estocásticas basadas en la frecuencia son un tipo especial de conjuntos de ceros de medida , y que se puede obtener una definición más general y uniforme al considerar todos los conjuntos de ceros de medida eficaz.
- El enfoque de complejidad / compresibilidad . Este paradigma fue defendido por AN Kolmogorov junto con las contribuciones de Leonid Levin y Gregory Chaitin . Para secuencias finitas, Kolmogorov define la aleatoriedad de una cadena binaria de longitud n como la entropía (o complejidad de Kolmogorov ) normalizada por la longitud n . En otras palabras, si la complejidad de Kolmogorov de la cadena es cercana an , es muy aleatoria; si la complejidad está muy por debajo de n , no es tan aleatorio. El concepto dual de aleatoriedad es la compresibilidad: cuanto más aleatoria es una secuencia, menos compresible y viceversa.
- El enfoque de la previsibilidad . Este paradigma se debe a Claus P. Schnorr y utiliza una definición ligeramente diferente de martingalas constructivas que las martingalas utilizadas en la teoría de la probabilidad tradicional. [11] Schnorr mostró cómo la existencia de una estrategia de apuestas selectiva implicaba la existencia de una regla de selección para una subsecuencia sesgada. Si solo se requiere una martingala recursiva para tener éxito en una secuencia en lugar de tener éxito de manera constructiva en una secuencia, entonces se obtiene el concepto de aleatoriedad recursiva. [ se necesita más explicación ] Yongge Wang mostró [12] [13] que el concepto de aleatoriedad recursiva es diferente del concepto de aleatoriedad de Schnorr. [ se necesita más explicación ]
En la mayoría de los casos, se han probado teoremas que relacionan los tres paradigmas (a menudo equivalencia). [14]
Ver también
Referencias
- Sergio B. Volchan ¿Qué es una secuencia aleatoria? The American Mathematical Monthly , vol. 109, 2002, págs. 46–63
Notas
- ^ "Qué se entiende por la palabra aleatoria" en Matemáticas y sentido común por Philip J. Davis 2006 ISBN 1-56881-270-1 páginas 180-182
- ^ Aleatoriedad inevitable en matemáticas discretas por József Beck 2009 ISBN 0-8218-4756-2 página 44
- ^ Algoritmos: ideas principales y aplicaciones de Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X página 166
- ^ E. Borel, Les probabilites denombrables et leurs applications arithmetique Rend. Circ. Estera. Palermo 27 (1909) 247–271
- ^ Laurant Bienvenu "Estocasticidad de Kolmogorov Loveland" en STACS 2007: 24 ° Simposio anual sobre aspectos teóricos de la informática por Wolfgang Thomas ISBN 3-540-70917-7 página 260
- ^ Iglesia, Alonzo (1940). "Sobre el concepto de secuencia aleatoria". Toro. Amer. Matemáticas. Soc . 46 (2): 130-136. doi : 10.1090 / S0002-9904-1940-07154-X .
- ^ AN Kolmogorov, Tres enfoques para la definición cuantitativa de la información Problemas de información y transmisión, 1 (1): 1-7, 1965.
- ^ DW Loveland, Una nueva interpretación del concepto de von Mises de secuencia aleatoria Z. Math. Logik Grundlagen Math 12 (1966) 279-294
- ^ Una introducción a la complejidad de Kolmogorov y sus aplicaciones por Ming Li, PMB Vitányi 1997 0387948686 páginas 149-151
- ^ R. Downey, Algunos avances recientes en la aleatoriedad algorítmica en los fundamentos matemáticos de la informática 2004: por Jiří Fiala, Václav Koubek 2004 ISBN 3-540-22823-3 página 44
- ^ Schnorr, CP (1971). "Un enfoque unificado para la definición de una secuencia aleatoria". Teoría de sistemas matemáticos . 5 (3): 246–258. doi : 10.1007 / bf01694181 .
- ^ Yongge Wang: Aleatoriedad y complejidad. Tesis de doctorado, 1996. http://webpages.uncc.edu/yonwang/papers/IPL97.pdf
- ^ Wang, Yongge (1999). "Una separación de dos conceptos de aleatoriedad". Cartas de procesamiento de información . 69 (3): 115-118. CiteSeerX 10.1.1.46.199 . doi : 10.1016 / S0020-0190 (98) 00202-6 .
- ^ Wolfgang Merkle, Kolmogorov Loveland Estocasticidad en autómatas, lenguajes y programación: 29º coloquio internacional, ICALP 2002, por Peter Widmayer et al. ISBN 3-540-43864-5 página 391
enlaces externos
- "Secuencia aleatoria" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- Video sobre estabilidad de frecuencia. Por qué los humanos no pueden "adivinar" al azar
- Pruebas de aleatoriedad de Terry Ritter