Secuencia aleatoria

El concepto de una 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 "let X₁,..., X_n sean variables aleatorias independientes...". Sin embargo, como dijo D. H. 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".

La teoría axiomática de la probabilidad deliberadamente evita una definición de secuencia aleatoria. La teoría de la probabilidad tradicional no establece si una secuencia específica es aleatoria, pero generalmente procede a discutir 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" un abuso del lenguaje.

Historia temprana

Émile Borel fue uno de los primeros matemáticos en abordar formalmente la aleatoriedad en 1909. 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 una secuencia aleatoria. Utilizando 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 llega a 1/. 2 y cada subsecuencia que podemos seleccionar de ella mediante un "adecuado" El método de selección tampoco está sesgado.

El criterio de selección de subsecuencias 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 quiere seleccionar el número de elemento 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. Esta definición a menudo se llama aleatoriedad 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, A. N. Kolmogorov y D. W. Loveland propusieron de forma independiente una regla de selección más permisiva. En su opinión, la definición de la función recursiva de Church era demasiado restrictiva porque leía los elementos en orden. En cambio, propusieron una regla basada en un proceso parcialmente computable que, habiendo leído cualquier N elementos de la secuencia, decide si quiere seleccionar otro elemento que aún no ha sido leído. 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 de 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 involucraba la teoría de la medida, pero luego se demostró que se puede expresar en términos de la 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 misma a través de una máquina de Turing universal.

Ahora han surgido tres paradigmas básicos para tratar con secuencias aleatorias:

• El frecuencia / medida-teorética enfoque. Este enfoque comenzó con la obra de Richard von Mises y la Iglesia Alonzo. En la década de 1960 Per Martin-Löf notó que los conjuntos de codificación de tales propiedades estocásticas basadas en frecuencia son un tipo especial de conjuntos de medida cero, y que una definición más general y suave puede obtenerse considerando todos los conjuntos de medida efectiva cero.

• El complejidad / compresibilidad enfoque. Este paradigma fue defendido por A. N. Kolmogorov junto con contribuciones de Leonid Levin y Gregory Chaitin. Para secuencias finitas, Kolmogorov define aleatoriedad de una cadena binaria de longitud n como la entropía (o la complejidad de Kolmogorov) normalizada por la longitud n. En otras palabras, si la complejidad de Kolmogorov de la cuerda está cerca n, es muy aleatorio; si la complejidad está muy por debajo nNo es tan aleatorio. El concepto dual de aleatoriedad es la compresibilidad - cuanto más aleatorio es una secuencia, menos compresible y viceversa.

• El Previsibilidad enfoque. Este paradigma se debe a Claus P. Schnorr y utiliza una definición ligeramente diferente de martingales constructivos que los martingales utilizados en la teoría de probabilidad tradicional. Schnorr mostró cómo la existencia de una estrategia de apuesta selectiva implicaba la existencia de una regla de selección para una subsecuencia parcial. Si uno sólo requiere un martingale recursivo para tener éxito en una secuencia en lugar de tener éxito constructivo en una secuencia, entonces uno consigue el concepto de aleatoriedad recursiva. Yongge Wang mostró que el concepto de aleatoriedad recursiva es diferente del concepto de aleatoriedad de Schnorr.

En la mayoría de los casos, se han probado los teoremas que relacionan los tres paradigmas (a menudo equivalencia).