Descartando, que es gerundio...

Vídeo publicado en CienciaXplora 

Por si no queda suficientemente claro con el vídeo, voy a tratar de explicarlo con un concurso :) 

Nos muestran un cierto número de cajas, N, y podemos abrirlas en el orden que nos plazca. Cada caja contiene una cantidad de dinero distinta de las otras (no sabemos qué cantidades hay en cada una, ni cuáles son esas cantidades). Cada vez que abrimos una caja decidimos (después de contar el dinero en ella, se entiende) si nos quedamos con ella (esa es la caja que escogemos) o si la descartamos para siempre (una vez que una caja ha sido descartada, ya no podemos volver a ella). Tratamos de diseñar una estrategia que nos garantice escoger la mejor caja (la que tiene más dinero) el mayor número de veces posible

¿A qué parece que no se va a ser posible? Pues sí, como hemos contado en el vídeo. Vamos a explicarlo.

Para simplificar supongamos que tenemos 3 cajas: A, B y C. Abrimos la primera (la A), como no tenemos ni idea de qué cantidades hay en cada caja, en A puede estar el mayor botín o no, no tenemos ninguna información adicional, por lo tanto, si escogemos A, nuestro posibilidades de acertar con el premio máximo es de ⅓.

¿Podemos mejorar dicha estrategia?¿Podemos diseñar otra estrategia que garantice siempre más de ⅓ de posibilidades de obtener la máxima cantidad?

Les propongo una: abrimos la primera caja (la A) y contamos el dinero que hay, pero la descartamos independientemente de cuánto dinero encierre. Ahora abrimos la segunda caja (la B), si contiene más dinero que la primera, nos quedamos con la segunda, en caso contrario nos quedamos con la tercera ¿En cuántos casos hemos acertado con esta estrategia?

Realicemos un examen viendo todas las posibilidades distintas.

En cada caso, escribiremos las tres cajas ordenadas por la cantidad de dinero que tienen de mayor a menor.

El primer caso lo escribimos como (A, B,C) (esto es, la caja A tiene más dinero, después la B, después la C). Vamos a suponer que las 3 cantidades son, respectivamente, 100, 50 y 25, pero, claro, eso no lo sabe el concursante a priori, no sabe cuál es el premio máximo, ¿me explico? Pero lo pensamos así para hacer una simulación de los 6 casos posibles con 3 cajas.

Siguiendo la estrategia descrita, abrimos la A, la descartamos, abrimos la B y como tiene menos que la A, escogemos la C, que es la que menos dinero tiene: mal empezamos. Nos hemos quedado con el peor premio…

(He hecho unas figuras para cada simulación, en otro color pongo la caja que escogeríamos con esta estrategia. Si el color es verde, es que hemos ganado)

Veamos, entonces, apoyándonos en las figuras, qué caja escogeríamos, en cada caso,  siguiendo nuestra estrategia.

Para (A,B,C) escogemos C y hemos perdido, es la que acabamos de analizar unas líneas más arriba.

Para (A,C,B) escogemos C, y perdemos.

Para (B,A,C), abrimos la A, la descartamos, abrimos la B que tiene más dinero y nos quedamos con ella y hemos ganado (¡por fín!).

Para (B,C,A) escogemos la B y ganamos (¡ole con ole!)

Con (C,A,B) escogemos C y ganamos, (¡toma, toma, toma!)

Y para (C,B,A) escogemos B y perdemos.

Como vemos, con la estrategia anterior podemos garantizar un éxito del 50% (ganamos 3 de 6), lo cual es mejor que el 33% (=1/3) que teníamos si escogemos una caja al azar. 

Lo curioso es que esta estrategia se puede aplicar a cualquier número de cajas, por sorprendente que parezca y aunque no se conseguirá siempre un éxito del 50%, sí que podemos obtener un porcentaje sorprendentemente alto (mayor de ⅓ independientemente del número de cajas). Sí, sí,éxito con una probabilidad casi del 37%, sea cual sea el número de cajas.

Se puede probar que el método que nos garantiza mejor resultado es el siguiente: Si tenemos que escoger entre N cajas, abrimos unas cuantas (digamos r) y las descartamos, pero anotamos de esas r cajas cuánto dinero tenía la que más tenía. A continuación seguimos abriendo las cajas restantes y nos quedamos con la primera que tenga más dinero que el que habíamos anotado como el máximo de las r primeras.

Si ninguna tiene más dinero obviamente nos quedamos con la última. Solo queda por determinar cuánto vale r, es decir, ¿cuántas cajas tenemos que abrir y descartar inicialmente?

Hemos visto que en el caso de 3 cajas (N=3, 3 cajas) r es 1. Se puede comprobar que en el caso de N=4 (cuatro cajas) r también vale 1 (miramos la primera, la descartamos, y después vamos abriendo las restantes y nos plantamos si una tiene más dinero que la inicial, con esta técnica en el caso de 4 cajas podemos garantizar que escogeremos la mejor en un 46% de los casos).

En la siguiente tabla se muestra cuántas cajas tenemos que desestimar dependiendo del número de cajas que tengamos en total para asegurar la mayor probabilidad de éxito (se puede comprobar haciendo algunas cuentas, bastantes):

¿Y si son más de 9 cajas? Se puede aplicar la misma técnica, pero ¿cómo calculamos el número de cajas r que tenemos que  desestimar? 

Hay una regla más o menos sencilla: el número r de cajas a desestimar es el número entero más próximo a N/e donde e es el número de Euler que es aproximadamente igual a 2,71828182845905 (no es un número racional y por tanto tiene infinitas cifras decimales que no se repiten de forma periódica).

Pues sí, desechando ese número de cajas, podemos asegurar que siempre obtendremos un éxito de al menos 1/e de los casos: un 36,8%, por muy grande que sea el número de cajas. La tabla anterior añadiendo una fila con los valores obtenidos al dividir el número de cajas entre e, quedaría:

Por ejemplo, para 10000 cajas, N=10000, tendríamos 10000/e= 3678,794411714, descartamos las 3679 (éste es el número entero más próximo a 3678,794411714) primeras cajas, y nos quedamos con la primera de las restantes que supere en dinero a todas las 3879 descartadas inicialmente y … ¡tachán! La probabilidad de éxito es del 37%…

Este problema se conoce como el Problema de la secretaria, el Problema de la dote del Sultán, del Pretendiente exigente y no sé si algún otro nombre más. Podéis conocer más si queréis aquí yaquí.

Volvemos pronto :)