Cómo eliminar el sesgo de una taba

Ya hay solución para el trigésimo tercer desafío matemático con el que EL PAÍS celebra el centenario de la Real Sociedad Matemática Española (ver el vídeo conmemorativo). Rafael Tesoro, licenciado y máster en Matemáticas por la Universidad Autónoma de Madrid y responsable de planificación y control de proyectos en Sainsel Sistemas Navales SAU propuso el problema (ver vídeo de la izquierda) y lo resuelve ahora (vídeo de la derecha).

Para este desafío se han recibido en el plazo marcado 193 respuestas (algunas desde sitios tan lejanos como El Salvador o Bangkok), de las que un 62% presentaban un argumento correcto y completo. La ganadora de una biblioteca matemática como la que entrega cada semana EL PAÍS ha sido en esta ocasión Cristina García Serrano, de Madrid.

Recordemos el desafío. Lanzamos repetidas veces una misma taba y anotamos 1 cuando queda hacia arriba la parte hundida del hueso y anotamos 0 si la taba cae de cualquier otra forma. La taba tiene carga, así que -casi seguro- obtendremos una serie aleatoria de bits con sesgo. Lo que pedíamos era un procedimiento para obtener, a partir de la serie aleatoria de bits conseguida lanzando la taba, 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.

Llamamos serie resultado a la serie de bits que se pide construir en el desafío. Una solución sencilla es la siguiente:

1) Tomamos la primera pareja de la serie de bits generada con la taba.

1.a - Si la pareja es repetitiva (es decir o bien 00 o bien 11) la desechamos.

1.b - En otro caso (es decir o bien 01 o bien 10) nos quedamos con el primer bit de la pareja, que será el primer bit de la serie resultado.

2) Repetimos el primer paso con la siguiente pareja de la serie de bits de la taba. Si no es repetitiva, el bit que extraemos de esta pareja se añade al final de lo que llevamos de la serie resultado. Y así sucesivamente hasta agotar la serie de bits de la taba.

Para demostrar la validez de esta solución vamos a usar la letra p refiriéndonos a la probabilidad de que, tras lanzar la taba, queden hacia arriba las partes hundidas del hueso, lo que corresponde a un 1. En consecuencia la probabilidad del 0 es 1-p. Calculamos la probabilidad de que, en la serie de la taba, salga una pareja no repetitiva. Como cada lanzamiento es independiente del anterior multiplicamos las probabilidades individuales:

Probabilidad del suceso 01 = (1-p) × p

Probabilidad del suceso 10 = p × (1-p)

Sabemos que el orden los factores no altera el producto y entonces notamos que ambos sucesos 01 y 10 tienen la misma probabilidad de ocurrir dentro de la serie de la taba. Por este motivo la serie obtenida siguiendo este método no tiene sesgo. Además conserva la propiedad de ser aleatoria que le viene de que también es aleatoria la serie original de la taba. No sabemos cuál es el valor concreto de p, sin embargo ¡no hace falta saberlo! Si usamos una taba distinta tendrá posiblemente otra carga y en consecuencia otro valor para p, sin embargo esto no impide que la solución siga funcionando.

La mayoría de las respuestas que han resuelto correctamente el desafío han seguido este camino. Varias recuerdan expresamente que este algoritmo se atribuye a J. von Neumann.

Alguna respuesta correcta incluye variantes de la esta solución. Por ejemplo Javier Navaridas explica como, en lugar de dividir la serie original en pares, sería posible utilizar grupos más largos. Por ejemplo podríamos dividir la serie en cuartetos y codificar todos las posibilidades menos 2 (0000 y 1111) ya que hay cuatro sucesos con probabilidad (1-p)^3 × p, seis sucesos con probabilidad (1-p)^2 × p^2 y otros cuatro sucesos con probabilidad (1-p) × p^3. Utilizando la mitad de cada uno de los tipos para codificar 1 y la otra para 0 podríamos obtener igualmente una serie aleatoria sin sesgo.

Varias respuestas han elaborado acerca de que, con el algoritmo de von Neumann, la longitud de la serie resultado es menor que la de serie original. Adrián Franco lo expresa adecuadamente como sigue: la probabilidad de que un bloque nos sea útil es 2p(1 - p), de modo que es previsible obtener, para una secuencia original muy larga de 2N dígitos (y N bloques), unos 2p(1 - p)N bloques "válidos" y, puesto que cada uno nos aporta un sólo bit al final del proceso, la longitud de la serie final rondará los 2p(1 - p)N dígitos, es decir, el resultado de multiplicar la longitud de la serie original por p(1 - p). Para hacernos una idea, el máximo valor que puede tomar este factor (alcanzado para una taba "equilibrada" o no cargada), sería de 0.25, es decir, obtendríamos una serie 4 veces más corta, en promedio.

Otra línea de argumentación en varias respuestas se ha apoyado en la frecuencia relativa del 1 (es decir: el porcentaje de 1 en la serie de bits) en lugar de la probabilidad de que en cada tirada salga 1. El sesgo es una propiedad de la probabilidad, y aunque la probabilidad y la frecuencia relativa están íntimamente relacionadas no son directamente intercambiables y únicamente se aproximan -todo lo que se quiera bajo ciertas condiciones- cuando el número del lanzamientos es suficientemente grande.

Una parte de ellas incluyeron la idea siguiente: cambiar el valor (de 0 a 1 o de 1 a 0) en cada posición par de la serie obtenida con la taba. Otras respuestas se han basado en ideas similares para equilibrar la cantidad de 1 y 0 en la serie. Un subgrupo en esta línea de argumentación añade el paso de calcular la frecuencia relativa del 1 para aproximar el valor de p (nótese que con el método de von Neumann no hace falta saber p).

Unas pocas de estas respuestas desarrollan el argumento de modo riguroso imponiendo la condición adicional de que el número de tiradas de la taba sea muy grande (esta restricción tampoco es necesaria en el algoritmo de von Neumann) y en algún caso se apela a ingredientes matemáticos más sofisticados como el Teorema Central del Límite y las distribuciones de probabilidad Binomial y Normal.

Dado que la ausencia de sesgo pedida requiere, como al lanzar una moneda, la equiprobabilidad de 1 y 0 en cada tirada, este grupo de respuestas no se han considerado totalmente correctas aunque varias de ellas sí consiguen una buena aproximación a la serie que se pide en el desafío.

Pedro Correa desvela en su respuesta un modo de aumentar el aprovechamiento de bits con sesgo. Esto se puede conseguir reciclando el material inicialmente desechado en el algoritmo simple de von Neumann, es decir, aprovechando también todas las parejas repetitivas (o bien 00 o bien 11). Esta mejora alarga la serie resultado como sigue. Si nos quedamos con un único representante de cada pareja repetitiva, tendríamos una segunda serie -mucho más corta que la inicial- de bits con sesgo. A esa segunda serie sesgada le podríamos aplicar el algoritmo de von Neumann consiguiendo una segunda serie sin sesgo y añadiríamos estos nuevos bits sin sesgo a la serie resultado. Este proceso podríamos reiterarlo tantas veces como fuera necesario hasta que se acabaran los bits.

Animamos a los lectores con interés en profundizar a que lean el artículo titulado Tossing a Biased Coin de Michael Mitzenmacher (al que también se refiere María Nieves Salas en su respuesta). Este artículo -cuya lectura completa requiere un mayor grado de conocimientos técnicos- concluye relacionando el aprovechamiento de bits aleatorios con H=- p × log_2(p) - (1-p) × log_2(1-p), magnitud que mide cuán incierto es el resultado en cada tirada de una serie aleatoria de bits (en 1948 C. E. Shannon acuñó el término "entropía" para H). La relación entre máximo aprovechamiento de bits aleatorios y entropía es mencionada por Øyvind Ytrehus quien nos envía su respuesta desde Bergen, Noruega.

El jueves plantearemos un nuevo reto.

Azarosa taba

Una taba sin sesgo