Cómo eliminar el sesgo de una taba

Cristina García Serrano, de Madrid, es la ganadora de la biblioteca matemática de esta semana

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.

Rafael Tesoro, licenciado y máster en Matemáticas por la <a href="http://www.uam.es" target="_blank">Universidad Autónoma de Madrid</a> y responsable de planificación y control de proyectos en <a href="http://www.sainsel.es/" target="_blank">Sainsel Sistemas Navales SAU</a>, presenta el 33º desafío con el que EL PAÍS celebra el <a href="http://www.rsme.es/centenario/" target="_blank">centenario de la Real Sociedad Matemática Española</a>. Envía tu respuesta antes de las 0.00 horas del martes 1 de noviembre (medianoche del lunes, hora peninsular española) a <a href="mailto:problemamatematicas@gmail.com" target="_blank">problemamatematicas@gmail.com</a>, entre los acertantes sortearemos una <a href="http://www.elpais.com/promociones/matematicas/" target="_blank">biblioteca matemática</a>como la que cada domingo se distribuye con EL PAÍS. A continuación, para aclarar las dudas y en atención a nuestros lectores sordos, añadimos el <b>enunciado del problema por escrito</b>. Lanzamos repetidas veces una moneda que no esté trucada y anotamos 1 cuando sale cara y 0 cuando sale cruz. Conseguimos así una serie de cifras binarias o bits que es aleatoria y no tiene sesgo. Por ejemplo, yo he conseguido una que empieza así: <i>0 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1</i> Decimos que la serie no tiene sesgo porque en cada tirada la probabilidad de 1 es igual a la probabilidad de 0. Decimos que la serie es aleatoria porque nunca se puede adivinar el resultado que saldrá en la siguiente tirada, a diferencia de lo que, por ejemplo, pasa con estas otras series: <i>0 1 0 1 0 1 0 1...</i>. <i>0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1...</i> dentro de las cuales detectamos un patrón con el que, si conocemos unos cuantos bits de la serie, podemos adivinar cuál será el siguiente bit. (Apostaríamos tranquilos a que las dos últimas series no han sido obtenidas lanzando una moneda). ¿Para qué sirven las series de bits aleatorias y sin sesgo? Por ejemplo, para generar números aleatorios del tipo que se usan para sortear el ganador en cada desafío matemático de EL PAÍS. Pero esta semana no tenemos ninguna moneda. ¿Que podemos hacer?... Por suerte, hemos conseguido unas tabas. La taba es un hueso que los mamíferos tenemos en el pie. Las de los corderos se usan para jugar desde tiempo inmemorial: aparecen en estatuas romanas y también en el cuadro <a href="http://bilddatenbank.khm.at/viewArtefactImageLarge?image=http://bilddatenbank.khm.at/images/500/GG_1017_17725.jpg&backuid=http://bilddatenbank.khm.at/viewArtefact?id=321" target="_blank"><i>Juegos de niños</i></a> de Brueghel el Viejo. Los habitantes de algunos lugares de España mantienen una ancestral tradición de reunirse para apostar usando tabas. Por ejemplo, estas que me han prestado vienen de Colmenar Viejo, cerca de Madrid, en donde se juega con ellas los días de San Andrés y de Santa Lucía. Cualquier taba está cargada porque no es simétrica respecto a su centro de gravedad y, aunque tiene cuatro formas distintas de caer, nosotros tendremos en cuenta dos posibles resultados. Vamos a lanzar repetidas veces una misma taba y anotamos 1 cuando queda hacia arriba la parte hundida del hueso (pintada de negro en las que yo tengo aquí) 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. Notemos que los tamaños y las formas de las tabas varían y por eso cada taba tiene su propia carga, distinta de las demás. 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. <a href="http://www.elpais.com/articulo/sociedad/desafios/matematicos/elpepusoc/20110712elpepusoc_8/Tes" target="_blank">DESAFÍOS ANTERIORES Y SUS SOLUCIONES</a>Vídeo: Á. R. DE LA RÚA / J. L. ARANDA
Esta es la <a href="http://www.elpais.com/videos/sociedad/Azarosa/taba/elpepusoc/20111027elpepusoc_4/Ves/">solución del trigésimo tercer desafío matemático</a> con el que EL PAÍS celebra el <a href="http://www.rsme.es/centenario/" target="_blank">centenario de la Real Sociedad Matemática Española</a>, planteado por Rafael Tesoro, licenciado y máster en Matemáticas por la <a href="http://www.uam.es" target="_blank">Universidad Autónoma de Madrid </a>y responsable de planificación y control de proyectos en <a href="http://www.sainsel.es/" target="_blank">Sainsel Sistemas Navales SAU. La ganadora de <a href="http://www.elpais.com/promociones/matematicas/">una biblioteca matemática</a> como la que entrega cada semana EL PAÍS ha sido en esta ocasión Cristina García Serrano, de Madrid. </a> <a href="http://www.elpais.com/articulo/sociedad/eliminar/sesgo/taba/elpepusoc/20111101elpepusoc_7/Tes">SOLUCIÓN POR ESCRITO</a> | <a href="http://www.elpais.com/articulo/sociedad/desafios/matematicos/elpepusoc/20110712elpepusoc_8/Tes">VER DESAFÍOS ANTERIORES</a> Vídeo: JOSÉ LUIS ARANDA / ÁLVARO RODRÍGUEZ DE LA RÚA

Archivado En

Recomendaciones EL PAÍS
Recomendaciones EL PAÍS
Recomendaciones EL PAÍS