Actualización sobre cointoss en Bash para evitar azar cargado

Hace unas 3 semanas publiqué una nota personal para implementar «cosstoin» en Bash:

cointoss() {
    # Probability is $1/$2, for example, cointoss 3 5
    # will hit 60% of the time. Defaults to 1/2 if no
    # arguments are supplied.
    [ $((RANDOM % ${2-2})) -lt ${1-1} ];
}

Actualización

Sin embargo, como bien me lo indica dualbus, este volado está cargado cuando la cantidad de caras en la moneda, el denominador (indicado por $2), no es múltiplo de 2. Y me hace llegar la implementación para azar balanceado que greybot recomienda en #bash en Freenode:

rand() {
    local max=$((32768 / $1 * $1)) r
    while (( (r=$RANDOM) >= max ))
    do
        :
    done
    echo $(( r % $1 ))
} ## Returns unbiased random number from 0 to ($1-1) inclusive, $1 <= 32768

La razón es sencilla: cuando se invoca la variable RANDOM en Bash, regresa un valor entero entre 0 y 32,767. Estos 32,768 posibles valores no se pueden dividir exactamente en N grupos cuando N no es múltiplo de 2; siempre quedan algunos grupos con más valores posibles. La «carga» cambia según el denominador.

La única manera de evitar este efecto es que si RANDOM cae en valores sobrantes, se repita la invocación a la variable RANDOM. De esta manera se garantiza el balanceo de la distribución probabilística, aunque no sea posible garantizar que el resultado se logre siempre en menos de K intentos.

Ejemplo cuando el denominador es 3

Si queremos dividir los 32,768 valores en 3 grupos:

  • X mod 3 == 0 lo cumplen 10,923 valores: 0, 3, 6… 32,763 y 32,766.
  • X mod 3 == 1 lo cumplen 10,923 valores: 1, 4, 7… 32,764 y 32,767.
  • X mod 3 == 2 lo cumplen sólo 10,922 valores: 2, 5, 8… y 32,765.

El 32,768 ya no forma parte del conjunto de resultados de RANDOM. Esto significa que hay una desventaja para X mod 3:

  • X mod 3 == 0: 33.3343506%
  • X mod 3 == 1: 33.3343506%
  • X mod 3 == 2: 33.3312988%

La diferencia es de 0.0030518% entre extremos, un incremento de 0.009156%.

Si ejecutamos 1,000,000 de veces cointoss 1 3, espero un hit 33.3…% de las veces (más/menos el error causado por el azar). El resultado medido 5 veces cae entre 33.27% y 33.38%. El valor esperado cae dentro de lo medido.

Ejemplo cuando el denominador es 24,576 (forzando el bug)

¿Qué pasa si llamamos cointoss 16384 24576?

  • X mod 24576 == 0 lo cumplen 2 valores: 0 y 24,576.
  • X mod 24576 == 1 lo cumplen 2 valores: 1 y 24,577.
  • X mod 24576 == 2 lo cumplen 2 valores: 2 y 24,578.
  • X mod 24576 == 8190 lo cumplen 2 valores: 8190, 32766.
  • X mod 24576 == 8191 lo cumplen 2 valores: 8191, 32767.
  • X mod 24576 == 8192 lo cumple 1 valor: 8192.
  • X mod 24576 == 8193 lo cumple 1 valor: 8193.
  • X mod 24576 == 24573 lo cumple 1 valor: 24573.
  • X mod 24576 == 24574 lo cumple 1 valor: 24574.
  • X mod 24576 == 24575 lo cumple 1 valor: 24575.

Entonces, para los grupos de 2 valores, la probabilidad de salir es de 0.0061035%, mientras que para los grupos de 1 valor, la probabilidad de salir es de 0.0030518, una diferencia de 0.0030518%, ¡pero un incremento de 200%!

Si ejecutamos 1,000,000 de veces cointoss 16384 24576, espero un hit 66.6…% de las veces (más/menos el error causado por el azar). El resultado medido 5 veces cae entre 74.95% y 75.07%. ¡El valor esperado no cae dentro de lo medido!

De nuevo, gracias a dualbus por el apunte.


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *