Una taba con sesgo

http://www.elpais.com/videos/sociedad/Azarosa/taba/elpepusoc/20111027elpepusoc_4/Ves/

El desafío de esta semana es el siguiente: a partir de la serie aleatoria de bits conseguida lanzando repetidamente una misma taba, obtener una serie de bits -que necesariamente será más corta que la serie de partida- que no se pueda distinguir de la que produce una moneda sin trucar, es decir: obtener una serie de bits aleatoria y sin sesgo.

La solución a este desafío debe incluir una breve explicación de las operaciones y los pasos que llevan desde la serie de bits de la taba hasta una serie aleatoria de bits sin sesgo. La solución ha de funcionar usando una única taba, que puede ser cualquiera: por ejemplo, una de las tres que yo tengo aquí u otra taba que vosotros tengáis.

La idea es convertir una serie sesgada por ejemplo de unos y ceros en una serie no sesgada, es decir que sea tan probable encontrar unos como ceros.

Lo primero que pensé es en una forma de onda donde los unos son valores positivos y los ceros valores negativos.

Así pensé en sustituir los unos y los ceros por otra cosa, por ejemplo por cambios de signo. Así nos sale que es tan probable el 1 (cambio a positivo) como el cero (cambio a negativo). Pero hay un problema: que nos sale una serie 0,1,0,1,0,1,0,1

¿Cómo arreglarlo para que salga una serie aleatoria en función de la original?

Simplemente cogiendo los números originales de 2 en 2 y tomando solo los que tienen un cambio es decir 01 y 10 que los convertiremos en 1 y 0 respectivamente.

Ejemplo

Serie original

01110110011110101111

01 11 01 10 01 11 10 10 11 11

01 01 10 01 10 10

1 1 0 1 0 0

Matemáticamente: Si la probabilidad de que salga un 1 es X y la de que salga un 0 es Y, siendo X distinto de Y, la serie es sesgada, pero la probabilidad de que salga 10 es XY y la de que salga 01 es YX, es decir igual y por tanto la serie es no sesgada.

Finalmente la serie final va a ser sensiblemente inferior a la original. En el caso de que no hubiera sesgo quedaría 50% * 50% = 25%. Y el valor se aproximaría a cero en función de lo sesgada que esté la serie original.