Explicación técnica sobre la repartición de piedras

En esta carta queremos dar respuesta a un usuario que sugeria que se randomizara varias veces la generacion de piedras.

Es un error lo de la *necesidad* de randomizar varias veces. Esto es cierto solamente si el generador *pseudo-random* no tiene suficiente entropia, lo cual no es el caso con nuestro sistema --- por supuesto que NO usamos la funcion rand() de la libreria de C o de C++ !!! (ni nada por el estilo). No solo esa funcion es un generador pauperrimo ("linear congruential"), sino que la semilla es de solo 32 bits (bueno, quiza dependa de la implementacion, pero igual, no gastemos mas espacio discutiendo las virtudes de lo que NO USAMOS :-) )

Nuestro sistema usa el dispositivo /dev/urandom como fuente de valores random. Asumo que como computista debes conocer este dispositivo, pero en caso que nunca hayas trabajado con el mismo, te invito a que leas al respecto (p.ej, en su pagina de Wikipedia, http://en.wikipedia.org/wiki//dev/urandom . En particular, la seccion de Linux es la que aplica a nuestro caso, ya que esta es la plataforma en la que corren nuestros servidores).

Adicionalmente, te comento que hemos tenido todo el cuidado del mundo en la rutina de permutacion de las 28 piedras.

En particular, tuvimos todo el cuidado del mundo en asegurar que la permutacion es hecha de manera que todos y cada uno de los 28! (28 factorial) posibles permutaciones ocurren con igual probabilidad. Para esto, tenemos particular cuidado con usar valores al azar uniformemente distribuidos *en el rango adecuado* (la primera vez un valor entre 0 y 27, luego un valor entre 0 y 26, luego entre 0 y 25 ... Es la unica manera en la que hay 28! posibles instancias de los valores dados --- seleccionar 28 valores entre 0 y 27 daria 28^28 (28 a la potencia 28) posibles instancias, lo cual no es divisible por 28! lo cual implicaria que las permutaciones no pueden ser equiprobables.

Date cuenta que aun en ese caso, la diferencia seria tan minuscula y tan absolutamente despreciable que de ninguna manera podria afectar la calidad de la reparticion de piedras --- pero aun asi, igual decidimos tomarnos el cuidado adicional de garantizar la calidad teorica asi como la calidad practica en el mas minimo detalle, por mas insignificante que pudiera parecer.

Ya va, que eso no es todo: pregunta: con un generador que te da un valor al azar entre 0 y 255 (uno lee bytes de /dev/urandom), &iquote;como obtienes valores *uniformemente distribuidos* entre 0 y N ?

La respuesta "inocente" e incorrecta es: sacando el residuo de la division por N+1 (lease, el valor random modulo N+1).

Quiza estes al tanto del por que ese procedimiento es incorrecto; fijate, si el valor de N fuera 99, es bastante obvio que el resultado de rnd modulo 100 no esta uniformemente distribuido entre 0 y 99; de los 256 posibles valores, hay 3 valores que producen un resultado de 0 (0, 100, y 200); 3 valores que producen un resultado de 1 (1, 101, y 201), y asi sucesivamente, hasta 55 ... Hay tres valores que producen un resultado de 55: 55, 155, y 255 ... A partir de 56, hay solo dos valores que producen ese resultado: 56 y 156, 57 y 157, etc. etc.

De modo que si tienes un valor RND que te da un numero al azar entre 0 y 255, el valor RND modulo 100 te da un resultado entre 0 y 99, pero no uniformemente distribuido: los valores entre 0 y 55 tienen probabilidad 3/256, y los valores entre 56 y 99 tienen probabilidad 2/256 !!

La manera correcta es *descartar* los valores de RND que estan por encima del maximo multiplo de N !!! Por ejemplo, en el caso de N = 100 (bueno, 99 ... no nos distraigamos con el +/- 1), la idea es que uno saca valores de /dev/urandom, y todo valor que sea >= 200 *lo descartas* --- al obtener uno por debajo de 200, entonces sacas rnd modulo 100, o incluso rnd dividido por el valor adecuado (en este caso, 2).

Pues bueno, te comento que nuestro sistema hace precisamente eso: como te decia, nos tomamos *todo el cuidado del mundo* en que el mas minimo detalle en cuanto a la calidad y a la uniformidad y equiprobabilidad de todos y cada uno de los pasos este en su optimo.

Aparte de estos detalles tecnicos, realmente no hay mas nada que te pueda comentar al respecto, aparte de los aspectos "filosoficos" de los procesos aleatorios:

A manera de ejemplo: lanza 20 veces una moneda, y cuenta cuantas caras y cuantos sellos... Creo que cualquier persona estara de acuerdo en que la probabilidad de cara es 0.5 (50%) y la probabilidad de sello es 0.5 ... Ahora bien: te salieron *exactamente 10 caras y 10 sellos*??? No?? Dale otra vez. Te salieron exactamente 10 y 10 la segunda vez?? Muy probablemente NO ... (de hecho, si sacas la cuenta con la distribucion binomial, te daras cuenta de que la probabilidad de que salgan exactamente 10 y 10 es bajisima!!!!!! Para ser exacto, la probabilidad de que salgan exactamente 10 y 10 es 0.1762 ).

Ahora bien, cuando uno le da, y te salen 11 caras y 9 sellos, y le das otra vez y te salen 12 sellos y 8 caras.... ¿que? ¿vas a proponer la hipotesis de que eso es evidencia de que la moneda esta sesgada o de alguna manera defectuosa???

Entonces, te pregunto: porque tu seas *en este momento* uno de los jugadores que esta en la mitad que esta *ligeramente por encima* de los promedios teoricos, ¿crees que eso es evidencia de que la reparticion de piedras este defectuosa?? Te puedo garantizar que asi como en este momento tus numeros estan por encima de los promedios, en otros momentos del tiempo tus numeros habran estado por debajo ... Claro, si tu dejas pasar esos momentos y no nos escribes para contarnos como tus promedios de dobles estan por debajo del promedio teorico, y esperas a que esten por encima para escribirnos protestando sobre la calidad de la reparticion, pues bueno, te podras dar cuenta que eso seria un problema sin solucion.

Bueno, lo dejo de este tamaño por ahora.... que ya estuvo bien largo el mensaje !

Saludos