Generador justo de números aleatorios en Arduino

Partimos de que tenemos una fuente aleatoria de bits (como el generador del mi otro post) pero desconocemos si es justa. ¿Que significa justa?. Significa que ambos valores (0,1) tiene la misma probabilidad (50%). Un bit puede ser aleatorio, pero no por ello sus posible valores han de tener la misma probabilidad. Vamos a usar como ejemplo un generador de bits cuyas probabilidades son:

P(0) = 0,1 = 10%
P(1) = 0,9 = 90%

si usamos esta fuente para generar bytes, números con muchos bit a 1 (11111101, 11110011,….) son más probables que el resto. Para evitar esto podemos convertir el generador de números en uno justo.

Para transformar la salida de ese generador en un salida justa necesitamos obtener dos bits. Si son iguales los desechamos, si son distintos devolvemos el valor del primero (también se podría usar el del segundo). ¿donde esta el truco? Que las probabilidad de que la pareja de bits sea [0,1] o [1,0] son siempre las mismas.

[0,1] = P(0) * P(1)
[1, 0] = P(1) * P(0)

Podemos ver una tabla con todas las opciones

Bit1 Bit2 Resultado Probabilidad Ejemplo
0 0 P(0) * P(0) 0,1 * 0,1 = 0,01
0 1 0 P(0) * P(1) 0,1 * 0,9 = 0,09
1 0 1 P(1) * P(0) 0,9 * 0,1 = 0,09
1 1 P(1) * P(1) 0,9 * 0.9 = 0,81

La desventaja de este sistema es que si las probabilidades están muy desparejadas puede costar tiempo encontrar una pareja distinta, en este caso el 82% de la veces habrá que descartar la pareja de bits.

Sin embargo cuenta con la ventaja de que no hace falta que conozcamos las probabilidades si tenemos dudas y necesitamos que nuestra cadena aleatoria, simplemente podemos aplicar este método y listo.

El código de ejemplo:

byte randomFairAnalog(int analogInput){
  byte rnd = 0;

  for(int i = 0; i < 8; ){
    delay(5);
    int aux1 = analogRead(analogInput)%2<< i;
    delay(5);
    int aux2 = analogRead(analogInput)%2<< i;

    if(aux1 == aux2)
      continue;

    rnd += aux1;
    i++;
  }

  return rnd;
}

Cuidado con este código en caso de que por algún motivo las lecturas del puerto dejen de ser aleatorias y sean todo el rato la misma la función caerá en un  bucle infinito.

Todo el código puede verse aqui.

Un comentario en “Generador justo de números aleatorios en Arduino

  1. Pingback: Generando números aleatorios en Arduino | Construyendo a Chispas

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.