Aleatoriedad estadística

Una secuencia numérica se dice que es aleatoriedad estadística cuando no contiene patrones reconocibles o regularidades; secuencias como el resultado de una tirada de dados.^[1] Existen diversas definiciones que tratan de formalizar la noción intuitiva anterior.

La aleatoriedad estadística no implica necesariamente aleatoriedad "verdadera". La secuencia pseudoaleatoria es suficiente para muchos usos.

Definiciones formales

Reales aleatorios

Un número real $0<r=0.r_{1}r_{2}r_{3}r_{4}\dots <1$ es b-normal (aleatorio en base b) si escrita como expresión numérica:

$r=r_{1}b^{-1}+r_{2}b^{-2}+\dots =\sum _{k=1}^{\infty }r_{k}b^{-k},\qquad r_{k}\in \{0,1,\dots ,b-1\}$

Si todas las secuencias de k dígitos que aparecen en la secuencia $r_{m+1}r_{m+2}\dots r_{m+k}$ tienen la misma probabilidad $p_{k}=1/b^{k}$ . En los años 1920, Émile Borel conjeturó que la mayor parte de números reales eran aleatorios (concretamente que un número real escogido al azar es con probabilidad 1). Igualmente, la computación de números trascendentes como $\pi$ o $e$ sugieren que sus desarrollos decimales parecen b-normales (ver números de Stoneham). Sin embargo, demostrar formalmente que un número real es realmente b-normal se ha revelado auténticamente difícil. Sólo en 1973, Richard Stoneham demostró formalmente que algunos números reales son b-normales.^[2]

La siguiente tabla muestra la aparente 10-normalidad de las cifras de $\pi$ :

Secuencia	Ocurrencias	Secuencia	Ocurrencias	Secuencia	Ocurrencias
0	99 993 942	00	10 004 524	000	1 000 897
1	99 997 334	01	9 998 250	001	1 000 758
2	100 002 410	02	9 999 222	002	1 000 447
3	99 986 911	03	10 000 290	003	1 001 566
4	100 011 958	04	10 000 613	004	1 000 741
5	99 998 885	05	10 002 048	005	1 002 881
6	100 010 387	06	9 995 451	006	999 294
7	99 996 061	07	9 993 703	007	998 919
8	100 001 839	08	10 000 565	008	999 962
9	100 000 273	09	9 999 276	009	999 059
__	__	10	9 997 289	010	998 884
__	__	11	9 997 964	011	1 001 188
__	__	...	...	...	...
__	__	99	10 003 709	099	999 201
__	__	__	__	...	...
__	__	__	__	999	1 000 905
Total	1000 000 000	Total	1000 000 000	Total	1000 000 000

Compresibilidad algorítmica

Artículo principal: Complejidad de Kolmogórov

La complejidad de Kolmogórov puede pensarse como una cota inferior de la compresibilidad algorítmica de una secuencia finita (de caracteres o dígitos binarios). Asigna a cada secuencia de ese tipo W un número natural K(w) que, intuitivamente, mide la mínima longitud de un programa informático (escrito en cierto lenguaje de programación fijo y preestablecido) que tiene input vacío y tiene como output la secuencia W cuando es ejecutado. Dado un número natural c y una secuencia w, decimos que w es c-incompresible si $K(w)\geq |w|-c$ .

Una sucesión infinita S es aleatoria en el sentido de Martin-Löf si y sólo si existe una constante c tal que todas los prefijos finitos de S's son c-incompresibles.

Por ejemplo, se conjetura que el número $\pi$ es b-normal, sin embargo, es algorítmicamente compresible ya que es un número calculable mediante un procedimiento finito bien definido.