En una entrada anterior se planteaba el siguiente problema:
Tenemos una urna con 5 bolas numeradas del 1 al 5. Hay que sacarlas de
una en una al azar, sin mirar. Se pierde el juego si sacamos la bola "n" en la extracción número "n".
Abordar dicho problema con un enfoque de probabilidad clásica realizando el diagrama de árbol es factible pero muy tedioso, teniendo en cuenta que con 5 bolas el árbol completo tiene 5! = 120 ramas. En realidad, dicho proceso no dista mucho de calcular todas las permutaciones y comprobar cuáles cumplen las condiciones (método exhaustivo).
Si aumentamos el número de bolas en la urna olvidémonos del método exhaustivo manual. Podemos utilizar programación para que realice dicho método exhaustivo. El problema es el tiempo de computación. Para hacernos una idea, con 13 bolas en la urna tenemos 6.227.020.800 permutaciones diferentes que crear y comprobar si cumplen o no la condición del enunciado (aproximadamente 52 minutos con mi ordenador).
Muchos problemas no tienen mucho interés desde el punto de vista algorítmico-teórico porque es fácil definir el algoritmo que resuelve el problema, pero llevado a la práctica con los ordenadores de los que disponemos actualmente el tiempo de computación de dicho algoritmo puede hacer inviable su resolución en un tiempo "razonable". Y esto obliga a tener que optimizar los algoritmos o buscar alternativas a los mismos.
Volviendo al problema, he creado un programa en Python que resuelve la generalización del problema con N bolas. Como se planteaba al final de la entrada anterior.
He utilizado dos métodos. Empiezo por el segundo, método exhaustivo. Se calculan todas las permutaciones con la librería itertools de Python y se recorren comprobando si cumplen o no la condición de que ninguna bola salga en la posición que indica su número. Para N pequeño (<10) el tiempo de ejecución es razonable, no así conforme se aumenta el número de bolas.
El primer método utilizado es matemáticamente mucho más interesante. Hace uso del concepto de desarreglo, que expliqué en la entrada anterior.
No es difícil ver la relación de los desarreglos con el problema planteado de las bolas numeradas. Que ninguna bola salga en el orden que indica su número equivale a decir que en la permutación del conjunto {1, 2, 3, 4, 5} ningún elemento coincida con su posición original. Por tanto, si calculamos el número de desarreglos del conjunto {1, 2, ..., N} la probabilidad de ganar el juego será: número de desarreglos / permutaciones totales. Es decir, el subfactorial dividido entre el factorial.
p(ganar juego con N bolas) = !N / N!
Una fórmula muy bonita y computacionalmente mucho más rápida que el método exhaustivo.
Nota: Para calcular el factorial y el subfactorial en Python he utilizado la librería SymPy.
En el caso del problema original, N = 5, la probabilidad de ganar es aproximadamente 0.36666666666666664. Por lo que tenemos la probabilidad cuantificada y podemos decir que es más fácil perder el juego que ganarlo.
Además se planteaba la pregunta de si nos parecía lucrativo que nos doblaran la apuesta en caso de ganar, teniendo en cuenta el riesgo que se asume. La respuesta es negativa, dado que a la larga ganaremos aproximadamente un 36'67% de las veces que juguemos y si sólo nos doblan la apuesta lo más probable es acabar perdiendo dinero en dicho juego.
Por último, se planteaba la siguiente pregunta:
Conforme aumentamos el número de bolas, ganar el juego ¿es más fácil, más difícil o va variando?
He creado otro programa en Python que devuelve las probabilidades de ganar el juego variando el número de bolas. El resultado obtenido se recoge en la siguiente tabla:
| N | Probabilidad de ganar |
|---|---|
| 2 | 0.5 |
| 3 | 0.3333333333333333 |
| 4 | 0.375 |
| 5 | 0.36666666666666664 |
| 6 | 0.3680555555555556 |
| 7 | 0.3678571428571429 |
| 8 | 0.36788194444444444 |
| 9 | 0.36787918871252206 |
| 10 | 0.3678794642857143 |
| 11 | 0.3678794392336059 |
| 12 | 0.3678794413212816 |
| 13 | 0.36787944116069116 |
| 14 | 0.3678794411721619 |
| 15 | 0.3678794411713972 |
| 16 | 0.367879441171445 |
| 17 | 0.36787944117144217 |
| 18 | 0.36787944117144233 |
| 19 | 0.36787944117144233 |
| 20 | 0.36787944117144233 |
| 21 | 0.36787944117144233 |
| 22 | 0.36787944117144233 |
| 23 | 0.36787944117144233 |
| 24 | 0.36787944117144233 |
| 25 | 0.36787944117144233 |
| 26 | 0.36787944117144233 |
| 27 | 0.36787944117144233 |
| 28 | 0.36787944117144233 |
| 29 | 0.36787944117144233 |
| 30 | 0.36787944117144233 |
Vemos que en las primeras N la probabilidad una veces sube y otras baja pero que conforme aumenta N la probabilidad se va estabilizando en torno a un valor: 0.36787944117144233. Podríamos decir que a nivel práctico a partir de 5 bolas la probabilidad de ganar el juego no cambia demasiado.
Y aquí podría acabar esta entrada. Pero las matemáticas están repletas de conexiones sorprendentes y en ocasiones inesperadas. ¿Alguien al leer el problema de las bolas numeradas pensó en el famoso número e?
Pues aquí va su aparición estelar: ese número al cual tiende la probabilidad conforme aumentamos el número de bolas, 0.3678794411714423..., es exactamente el inverso del número e.
1/e = 0.3678794411714423...
Dejo como ejercicio a quien quiera la explicación de este hecho (pista: mirar en la entrada anterior la fórmula del subfactorial).
No hay comentarios:
Publicar un comentario