Últimos Cambios
Blog personal: El hilo del laberinto
|
|
|
Últimos Cambios |
|
Blog personal: El hilo del laberinto
|
|
|
Última Actualización: 11 de Noviembre de 1.998 - Jueves
La idea inicial de este texto fue una pregunta sobre el número de iteraciones que es necesario ejecutar el siguiente código para asegurar un resultado aleatorio:
repeat NUM_REPETICIONES
{
i = random 1..n
j = random 1..n
swap(array[i],array[j])
}
En este artículo se ve como algo aparentemente tan sencillo no lo es tanto. Desató un prolífico e interesante debate en la lista de correo de CoderPunks. Esta página muestra algunos de los resultados comentados. Es imposible proporcionar una lista de personas que han colaborado, ya que es muy larga, y muchas de ellas utilizan anonimizadores de e-mail. En cualquier caso mi agradecimiento a todas ellas, por mostrarme que un tema aparentemente tan trivial tiene mucha más miga de lo que parecía en un principio.
La primera sugerencia era evitar generar dos valores aleatorios por iteración además de fijar un número máximo de iteraciones:
for i in 1..n
{
j = random 1..n
swap(array[i],array[j])
}
Aunque esta solución parece bastante evidente, se puede ver que los resultados (en contra de lo que diría la intuición) no son nada buenos. Por ejemplo, para un array de tres elementos, las posibilidades finales son:
Si hay n elementos, el último paso arroja una probabilidad de 1/nn para cada permutación, que deben dividirse entre las n! permutaciones realmente posibles con n elementos. Con este algoritmo es imposible tener una distribución equiprobable para cualquier n mayor que 2. De hecho, cuando mayor es el número de elementos, más dispares son las distribuciones finales. ¡¡Un resultado que va en contra de la intuición!!.abc: 5/27 acb: 5/27 bac: 4/27 bca: 4/27 cab: 4/27 cba: 5/27
Con ese algoritmo, el contenido del slot que estamos procesando en cada momento es aleatorio tras cada iteración. El problema es que ese proceso de aleatorización de cada slot afecta a la "aleatoriedad" de los otros. Tras el paso n-1, el slot es aleatorio, pero el slot en la posición n no es aleatorio (tiene un bias). Ese bias es transferido al slot n con probabilidad 1/n.
En cualquier caso, el algoritmo inicial (elegir dos elementos al azar e intercambiarlos, repitiendo el proceso un cierto número de veces) tampoco genera un resultado equiprobable, por muchas iteraciones que se realicen. Veamos la demostración:
Sea n elementos. En cada iteración obtenemos ((n2-n)/2)+1 permutaciones. Cada una de ellas, i, tendrá una probabilidad de ocurrencia de ki/((n2-n)/2)+1, siendo ki un valor entero.
Por tanto, si se hacen m iteraciones, la probabilidad de cada permutación i será ki,m/(((n2-n)/2)+1)m.
Supongamos ahora que existe un m para el cual ki,m = km para todo i. Es decir, que existe un m para el cual se ha logrado la equiprobabilidad. En ese caso la probabilidad de cada permutación debe ser 1/n!. Por tanto, para algún m, (((n2-n)/2)+1)m = km*n!. Como km es un valor entero, para que se cumpla esa igualdad debe verificarse que ((n2-n)/2)+1 es un múltiplo de n!. Dado que el factorial crece mucho más rápidamente que n2, basta con comprobar los casos para pequeños valores de n. Vemos que la ecuación anterior se cumple, por tanto, exclusivamente para n = 1 y n = 2.
Por lo tanto, nunca conseguiremos con ese algoritmo una distribución equiprobable, por muchas iteraciones que hagamos, si n>2.
La solución consiste en utilizar el algoritmo P de Knuth:
for i in 1..n-1
{
j = random i..n
swap(array[i],array[j])
}
Este algoritmo proporciona una distribución equiprobable si la función aleatoria lo es.
Más información sobre los OpenBadges
Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS
