El problema de la clase práctica de ayer puede bajarse, pasado en limpio, [aquí]. La semana que viene empezamos con la Guía 3, que es la guía. Hasta aquí fue todo preparativos.
A propósito del problema 16 de la Guía 2, de los dos jugadores que tiran una moneda, alguien me preguntó ayer sobre el problema de las series de penales. Para decidir quién patea primero se tira una moneda. Pero lo que viene después depende más de la psicología que del cálculo de probabilidades. [Aquí] pueden leer una nota de Paenza muy informativa.
Recuerden que hasta el 7 tienen tiempo de inscribirse en la materia.
“Este pensador observó que todos los libros, por diversos que sean, constan de elementos iguales: el espacio, el punto, la coma, las veintidós letras del alfabeto. También alegó un hecho que todos los viajeros han confirmado: No hay en la vasta Biblioteca, dos libros idénticos. De esas premisas incontrovertibles dedujo que la Biblioteca es total y que sus anaqueles registran todas las posibles combinaciones de los veintitantos símbolos ortográficos (número, aunque vastísimo, no infinito) o sea todo lo que es dable expresar: en todos los idiomas. Todo: la historia minuciosa del porvenir, las autobiografías de los arcángeles, el catálogo fiel de la Biblioteca, miles y miles de catálogos falsos, la demostración de la falacia de esos catálogos, la demostración de la falacia del catálogo verdadero, el evangelio gnóstico de Basilides, el comentario de ese evangelio, el comentario del comentario de ese evangelio, la relación verídica de tu muerte, la versión de cada libro a todas las lenguas, las interpolaciones de cada libro en todos los libros, el tratado que Beda pudo escribir (y no escribió) sobre la mitología de los sajones, los libros perdidos de Tácito.”
Jorge Luis Borges, La Biblioteca de Babel (1941).
¿De cuántas formas pueden reordenarse los veintitantos símbolos ortográficos de la Biblioteca de Babel? ¿De cuántas formas puede Christopher Nolan reordenar el argumento de sus películas para hacer una película nueva? (de ser posible, que todavía se entienda). ¿Y cuanta información quedará en la película más arrevesada que Christopher Nolan pueda dirigir? Como suele ocurrir, los Simpsons se preguntaron todo esto antes (¡pero no antes que Borges o que Claude Shannon!):
¿Cuál es la relación entre entropía e información? En 1949, ocho años después que Borges publicase La Biblioteca de Babel, Claude Shannon publicó un trabajo en el que introdujo su famoso concepto de entropía de la información,
S = – Σ pi log pi.
En ese trabajo, aunque presentó una serie de teoremas con motivaciones plausibles, Shannon acepta que su principal motivación para usar una definición de este tipo, y en particular la función logaritmo, tiene que ver con que es práctica para lidiar con magnitudes medidas que pueden variar en varios órdenes de magnitud, con que vuelve ciertas operaciones con números grandes más fáciles de manejar, y con resultados previos en mecánica estadística como las definiciones de entropía de Boltzmann y de Gibbs. Shannon usó log2, pero nosotros usamos el logaritmo natural porque es más natural para nuestra materia. En clase vimos cómo esta definición se relaciona con nociones de desorden o de interteza, y que para sucesos equiprobables se reduce a S = log(N), donde N es el número de sucesos posibles. Pero ¿cómo se relaciona esto con la noción de información?
Llamativamente, Borges se adelantó en su Biblioteca de Babel a esta pregunta. En otra parte del cuento escribe:
“El número de símbolos ortográficos es veinticinco. Esa comprobación permitió, hace trescientos años, formular una teoría general de la Biblioteca y resolver satisfactoriamente el problema que ninguna conjetura había descifrado: la naturaleza informe y caótica de casi todos los libros. Uno, que mi padre vio en un hexágono del circuito quince noventa y cuatro, constaba de las letras MCV perversamente repetidas desde el renglón primero hasta el último. Otro (muy consultado en esta zona) es un mero laberinto de letras, pero la página penúltima dice «Oh tiempo tus pirámides».”
Imaginemos, como Borges, un conjunto de símbolos ortográficos formado por 22 letras del alfabeto, mas el punto, la coma y el espacio (que marcaremos como “_”):
El primer mono (M1) aprieta la letra A todas las veces: “AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA”.
El segundo mono (M2) aprieta solo letras con equiprobabilidad, sin usar puntuación o espacios: “AYZTMOICPQERVILVVLMODNBEKSDEHGAHGALMKEYC”
El tercer mono (M3) aprieta cualquiera de las 25 teclas con equiprobabilidad: “DH, EKHVOZ . EZVIASC B PIM,YICAK DELA.ALSFBZOQNY E”.
El cuarto mono (M4) aprieta cualquier tecla con su probabilidad de uso en el español (por ejemplo, el espacio tiene una probabilidad de ocurrencia de ≈ 0.17, la letra “A” de ≈ 0.10, la “E” de ≈ 0.11, etc.): “EOS RILND . QNL PAE A ARDTEOS DCMAEE AMA”.
El quinto mono (M5) tiene un vocabulario de 10 palabras, y usa las reglas de espaciado y puntuación del español. Su vocabulario es: CASA, PEPE, TUS, PESCA, EN, PIRAMIDES, DOS, OH, PARA y TIEMPO. Usando solo esas palabras al azar, y el punto, la coma y el espacio, escribe: “DOS PESCA. TUS CASA PEPE, OH TIEMPO TUS PIRAMIDES.”
¿Cuánta información hay en cada mensaje? Para contestar esto, preguntémonos para qué emisor es más difícil predecir la ocurrencia de la siguiente letra, si nos llegasen sus mensajes de a una letra por vez (por ejemplo, por un telégrafo). En el primer caso, una vez que reconocimos el patrón, es fácil saber que la siguiente letra será una A. Cada nueva A no agrega entonces más información que la que ya teníamos (¡ya sabíamos que nos llegaría una A!). Es fácil también ver que el caso más difícil para predecir la ocurrencia de una nueva letra corresponde al del mono M3. Por otro lado, el mensaje de M5 parece más complicado, pero luego de recibir las letras “PES”, sabemos que solo pueden estar seguidas por “CA”. La entropía de Shannon mide esta noción de información, basada en la idea de que cuanto más difícil sea predecir la siguiente letra, más información nos aporta conocerla. Calculemos la entropía de cada emisor:
S1 = ln 1 = 0
S2 = ln 22 ≈ 3.091
S3 = ln 25 ≈ 3.219
S4 = -Σ pi log pi ≈ 2.766
La entropía S5 es más difícil de calcular, pero es menor a S4 y mayor a S1.
Hay otra forma interesante de pensar cuánta información genera el emisor, y es pensar cuánto podemos comprimir el mensaje que nos envía el emisor sin perder información. Para el primer mono nos alcanza con decir que envió 50 “A”. El mensaje de M5 lo podemos comprimir como “D PES. TU C PEP, O TI TU PIR.” (ya que “D” solo puede ser seguido por “OS”, “PES” por “CA”, “TU” por “S”, etc.). En el mensaje de M3 no podemos sacar nada sin perder información. Un teorema famoso de Shannon nos dice que (para mensajes muy largos) la cota máxima a cuánto podemos comprimir el mensaje de un emisor sin perder información está relacionada con su entropía.
Los que quieran saber más pueden leer el paper original de Shannon:
Me imagino que todos quieren ser millonarios. ¡Pero seguro nunca se imaginaron que esta materia era la forma de alcanzar sus deseos! Salvo, obviamente, que hayan visto The hangover (2009), o películas un poco más serias como Rain Man (1988) y 21 (2008) (ambas basadas, con diversas libertades narrativas, en historias reales). En la última teórica vimos probabilidades. Las herramientas del curso se pueden usar para ganar en juegos de azar (¡o mejor aún, para evitarlos!), y para ilustrar cómo les cuento dos historias.
La primer historia es la del método para ganar en la ruleta de Edward Thorp (también creador de métodos para contar cartas en el blackjack) y Claude Shannon (el mismo Shannon de la entropía que veremos repetidas veces en la materia). Todos los juegos de azar en los casinos tienen esperanza negativa: si siguen jugando, a la larga solo pueden perder. En el caso de la ruleta, esto está relacionado con que un pleno (acertar a un número) paga 35 veces la apuesta, pero la probabilidad de acertar el número es 1/37 (pues la ruleta tiene 36 números más el cero). Así, en promedio, cada vez que apuestan pierden. El desafío es convertir la esperanza en positiva, es decir, saber con probabilidad mayor a 1/35 qué número va a salir. En los siguientes artículos Edward Thorp explica en detalle diversos métodos para ganar en la ruleta:
Los que quieran mas información sobre juegos de azar (y las siguientes entregas de estos artículos) pueden mirar la página web de Edward Thorp.
Básicamente existen tres tipos de métodos para la ruleta: (1) métodos matemáticos, (2) métodos basados en desperfectos de la ruleta, y (3) métodos predictivos basados en la física de la ruleta. Los primeros no son viables, ya que como mencioné arriba, los juegos de casino están diseñados para tener esperanza negativa. Para ser más claro: todo método que les cuenten basado solo en la matemática o la estadística o es mentira, o está explícitamente prohibido en las reglas del juego que usan los casinos. Al segundo método vamos a volver en un rato. El tercer camino es el que eligieron Thorp y Shannon.
En 1960 Thorp y Shannon usaron el hecho de que en los casinos se puede seguir apostando mientras la ruleta gira (y hasta que el crupier grita “¡No va más!”) para crear un algoritmo que basado en la velocidad de rotación de la ruleta, la velocidad de la bola, y su posición inicial aproximada (estimadas contando solo con inspección visual el número de vueltas que la ruleta y la bola dan en un período corto de tiempo), predice estadísticamente en qué octante de la ruleta puede caer la bola. En espíritu (aunque no en los detalles) esto es parecido a lo que vimos en el problema del camino al azar: no podemos saber dónde terminará la bola, pero nos alcanza con conocer la zona más probable de la ruleta en la que la bola puede terminar. Con esta información extra, la esperanza se vuelve positiva para el apostador. Pueden encontrar un artículo de divulgación con esta historia aquí:
Para realizar predicciones rápidas en el casino, Thorp y Shannon armaron una computadora pequeña, del tamaño de un atado de cigarrillos, que se llevaba con una faja en la cintura y se conectaba al zapato para ingresar los datos pisando fuerte o moviendo los dedos del pie. La siguiente foto muestra la pequeña computadora de Thorp y Shannon (la que se llevaba en la cintura):
Otra persona (el apostador) usaba un pequeño receptor y un auricular para obtener la predicción y realizar rápidamente una apuesta. En la práctica, y para evitar ser detectados usaban a tres personas: una que medía, otra que llevaba la computadora, y el tercero que realizaba la apuesta, todos conectados por un sistema de radio:
¡Lo mas interesante es que el método funciona! Thorp y Shannon lo usaron con cierto éxito en Las Vegas. Una década más tarde un grupo de estudiantes de California perfeccionaría el sistema reduciendo aún más las computadoras y escondiéndolas completamente en zapatos (aquí pueden ver una imagen de las computadoras y encontrar algunos detalles sobre cómo funcionaban; el apostador ingresaba el período de rotación de la ruleta y el de la bola apretando un pulsador con el dedo del pie, y en otro zapato otra computadora devolvía la predicción del octante en el que caería la bola con una vibración). Todo esto además terminó siendo usado para el guión de un episodio de la serie original de Misión Imposible (1966), con un título insuperable:
La segunda historia tiene que ver con el segundo método para ganar en la ruleta, basado en desperfectos de la ruleta, e involucra a un estudiante de doctorado de Richard Feynman. Alrededor de 1940, Albert Hibbs y Roy Walford acumularon datos de jugadas en casinos de Reno y Las Vegas, para identificar algún pequeño bias o desperfecto en las ruedas de ruleta que favoreciera estadísticamente a ciertos números. Usando los datos estadísticos obtenidos para cada ruleta, Hibbs y Walford ganaron 8300 dólares en un día (las ruletas actuales no tienen este nivel de imperfección, por lo que el método ya no es aplicable hoy). Pueden leer una historia sobre Hibbs y Walford aquí:
Espero haberlos convencido, con estas historias, de que lo más conveniente es no apostar (salvo que uno esté dispuesto a esconder una computadora en un zapato). Para mostrar que más de 4000 físicos llegaron a la misma conclusión, les dejo un link a la famosa historia de la convención de físicos en Las Vegas que dió origen a la frase “They each brought one shirt and a ten-dollar bill, and changed neither”:
