Sección : Simulación, modelos y realidad
Previo : Sucesiones uniformes
Siguiente : Variables aleatorias

Complejidad y aleatoriedad


Entre las diferentes formalizaciones de la aleatoriedad que se pueden proponer, la noción de sucesión uniforme es la única que se puede emplear en la práctica: es la única que puede ser comprobada por un test para un generador dado, y ella es suficiente para justificar todas las aplicaciones de la función Random. Una ``verdadera'' sucesión aleatoria debe ser uniforme. Pero, ¿podemos considerar como aleatoria a toda sucesión uniforme? Vamos a ver, lamentablemente, que no.

Vamos a limitarnos a las sucesiones de bits en $ \{0, 1\}$. Esperamos que una sucesión de este tipo sea el resultado típico de lanzar una moneda, Cara o Cruz. Veamos tres sucesiones particulares:

$\displaystyle 0~0~0~0~0~0~0~0~0~0~0~0~0~0~0~0
$

$\displaystyle 0~1~0~1~0~1~0~1~0~1~0~1~0~1~0~1
$

$\displaystyle 0~1~1~0~1~0~0~0~1~1~0~1~1~1~0~0
$


La tercera presenta mejor aspecto que las dos primeras. Sin embargo ella tiene las mismas probabilidades de salir así en el juego de Cara o Cruz: $ 1/2^{16}$. Entre las $ 1000$-tuplas de bits, todos tienen, a priori, la misma probabilidad de salir: $ 1/2^{1000}$. Toda sucesión aleatoria de bits debe contener, necesariamente, una infinidad de veces $ 1000$ ceros uno detrás del otro. ¿Aceptaríamos que un generador aleatorio de bits nos dé como resultado solamente $ 100$ ceros en sucesión? Esto parece poco verosímil.

De los $ 3$ ejemplos anteriores, descartaríamos el primero pues parece violar la $ 1$-uniformidad. Descartaríamos el segundo en nombre de la $ 2$-uniformidad. Pero, ¿qué decir entonces de la sucesión concatenada de todos los enteros en base $ 2$? (sucesión de Champernowne)

$\displaystyle 0~1 \underbrace{1~0}_2 \underbrace{1~1}_3
\underbrace{1~0~0}_4 \...
...race{1~0~1~1}_{11}
\underbrace{1~1~0~0}_{12}\underbrace{1~1~0~1}_{13}~\ldots
$


Se puede demostrar que ella es $ \infty$-uniforme. Pero ¿cómo calificar de aleatoria una sucesión tan perfectamente previsible?

La definición mas intuitiva de azar, la de los diccionarios, no tiene ninguna relación con la uniformidad. Es aleatorio lo que es imprevisible. Una sucesión sería aleatoria, si no pudiésemos prever su término $ (n\!+\!1)$ conociendo los $ n$ primeros. La sucesión

$\displaystyle 0~1~0~1~0~1~0~1~\ldots~0~1~\ldots
$


no es aleatoria porque sin haber escrito los $ 999$ primeros términos, sabemos que el $ 1000$-ésimo será $ 1$ y el siguiente 0. Por el contrario, la sucesión

$\displaystyle 0~1~1~0~1~0~1~1~1~0~0~1~0~1
$

no parece presentar regularidades ni estructura que nos permitan prever los términos que siguen. Por tanto una sucesión es aleatoria si no tiene una regla de construcción simple. A una regla de construcción la podemos ver como un medio de comprimir a una sucesión en un algoritmo que la engendra.

Ejemplo:

Repetir $ n$ veces
escribir 0, luego $ 1$
finRepetir.

La codificación binaria de este algoritmo es una sucesión cuya longitud depende de la expresión de $ n$. El número de bits necesarios para escribir $ n$, más o menos $ 1$, es el logaritmo de $ n$ en base $ 2$: $ \log_2(n)$. El resto de la cadena no depende de $ n$ y es un número constante de bits, digamos $ k$. En total, una cadena de $ \log_2(n)+k$ bits de longitud, engendrará al ejecutarse una cadena de longitud $ 2n$. Denotemos por $ X^*$ al conjunto de todas las cadenas de bits, de longitud finita. Si $ x\in X^*$, denotaremos su longitud (número de bits) por $ l(x)$. Un algoritmo es una aplicación de $ X^*$ en sí mismo.

$ X^*$ $ \stackrel{\phi}{\longrightarrow}$ $ X^*$
$ y$ $ \longrightarrow$ $ x$
input   output
Sea $ \tau (\phi)$ el tamaño de la codificación de $ \phi$ expresada en bits (sin contar el output).

Definición 2.4   Llamamos complejidad de $ x$ relativa a $ \phi$ al entero:

$\displaystyle K_\phi (x)
=\inf~\{~l(y),~\phi (y)=x~\}+\tau (\phi)~~
(=+\infty$ si $\displaystyle x\not\in\phi (X^*))
\;.
$


En otras palabras $ K_{\phi}(x)$ es la cantidad de información que hace falta para producir $ x$ empleando el algoritmo $ \phi$. En el ejemplo anterior, una cadena de $ \log_2(n)+k$ bits bastaba para producir la siguiente cadena de longitud $ 2n$.

$\displaystyle \underbrace{0~1~0~1~\cdots \cdots ~0~1}_{\mbox{$n$ veces}}
\;.
$

Definición 2.5   Se llama complejidad de $ x$ al entero:

$\displaystyle K(x)=
\inf\limits_\phi K_\phi (x)
\;.
$

$ K(x)$ es la cantidad minimal de información necesaria para producir a $ x$.

Observación :

Aunque estas páginas no tienen la pretensión de ser un curso sobre complejidad, debemos al menos señalar que las definiciones anteriores no tienen sentido si no restringimos un poco la noción de algoritmo. Si nos mantenemos en el campo de las aplicaciones cualesquiera en $ X^*$, podemos llegar a paradojas del tipo de la de R. Berry :

``El menor número que no puede ser definido con menos de $ 20$ palabras''.
El marco adecuado es el de las funciones recursivas, calculables por máquinas de Turing.

Para generar una sucesión dada de $ n$ bits, el algoritmo a lo ``bruto'' consiste en escribirlos todos en el orden correspondiente. Esto corresponde a la aplicación identidad $ I$ de $ X^*$ en símismo, con respecto a este algoritmo la complejidad de cualquier sucesión de $ n$ bits es $ n$. Por tanto la complejidad de toda sucesión está mayorada por su longitud:

$\displaystyle \forall x~~
K_{I}(x)=l(x)
\Longrightarrow K(x)\leq l(x)
\;.
$


Decir que una sucesión es aleatoria es decir que no se puede mejorar el algoritmo a lo bruto para generarla.

Definición 2.6   Sea $ x=(x_n)_{n\in\mathbb {N}^*}$ una sucesión de bits. Decimos que es aleatoria si existe una constante $ c$ tal que para todo $ n$ :

$\displaystyle K((x_1,\ldots ,x_n))\geq n-c
\;.
$


Según la proposición siguiente, la mayor parte de las sucesiones son aleatorias.

Proposición 2.7   El cardinal del conjunto de las sucesiones de bits de longitud $ n$ cuya complejidad está acotada inferiormente por $ n\!-\!c$ es al menos :

$\displaystyle 2^n(1-2^{-c})
\;.
$


Demostración : Entre los inputs susceptibles de generar a las sucesiones de longitud $ n$, solamente nos interesan aquellos cuya longitud es inferior a $ (n-c)$. Hay a lo sumo:

$\displaystyle 2^0+2^1+\cdots +2^{n-c-1}
=2^{n-c}-1
\;.
$

Cada par (input+algoritmo) genera a lo sumo una sucesión de longitud $ n$. Hay por tanto a lo sumo $ 2^{n-c}$ sucesiones de longitud $ n$ cuya complejidad es inferior a $ n-c$.
$ \square$

Concretamente, entre todas las sucesiones de longitud $ n$, solamente una proporción de $ 1/2^{10}\simeq 10^{-3}$ entre ellas es de complejidad $ <n-10$.

Debe ser, por tanto, fácil encontrar sucesiones aleatorias, puesto que la mayor parte de ellas lo son. Paradójicamente, el problema de demostrar que una sucesión en particular es aleatoria es, en general, irresoluble.



Sección : Simulación, modelos y realidad
Previo : Sucesiones uniformes
Siguiente : Variables aleatorias