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