¿La molestia de resolver un tonto problema de probabilidad en mi tiempo libre cuando podría haber estado haciendo Doom Scroll? Porque estoy tratando de mantenerme alerta en este período de tiempo único en el que podemos subcontratar la mayor parte de nuestro pensamiento crítico a la IA generativa. Si está leyendo artículos sobre TDS, probablemente usted y yo compartamos ese objetivo.
Este artículo analizará la resolución de un divertido acertijo de probabilidad que uno de mis YouTubers favoritos (3Blue1Brown) publicó recientemente. Por cierto, si no estás familiarizado con su canal, debes echarle un vistazo. Se centra en explicaciones y elementos visuales intuitivos que le harán preguntarse por qué las matemáticas se enseñan de otra manera.
La configuración del problema
El breve que vinculé a continuación le brindará la mejor introducción, pero repasaré brevemente la configuración aquí como complemento.
Imaginemos que tenemos una caja con varias cadenas dentro. Seleccionamos aleatoriamente el final de una cadena y luego seleccionamos aleatoriamente el final de otra cadena. Luego unimos los extremos. Puede suceder una de dos cosas: (1) los extremos provienen de diferentes cuerdas y ahora tenemos una cuerda más larga o (2) el segundo extremo es de la misma cuerda que seleccionamos inicialmente y al atarlos se forma un bucle.
Si unimos dos hilos separados, colocamos el hilo más largo nuevamente en la caja. Si hacemos un bucle, lo sacamos de la caja. Este proceso de selección aleatoria de cadenas continúa hasta que no quedan cadenas en el cuadro.
La pregunta del problema es: ¿cuántos bucles esperamos que cree este proceso? O, en palabras menos precisas, pero más prácticas: si repitiéramos este proceso muchas veces, ¿cuál es el número promedio de bucles que se crearían?
Observaciones clave sobre el problema.
Tener una buena comprensión de un problema siempre es clave para encontrar una buena solución. Además de simplemente comprender la mecánica cubierta en la última sección, hay algunas observaciones clave que necesitaremos comprender.
Observación #1
Cada ronda de sorteos aleatorios tiene dos componentes aleatorios. El primer sorteo aleatorio y el segundo. El primer empate no es muy importante. El segundo sorteo es porque determina si hacemos un bucle o una cuerda más larga.
Observación #2
Cada ronda da como resultado una cuerda menos en la caja, pase lo que pase. Si se hace un bucle, se elimina la cuerda que formó el bucle. Si se hace una cadena más larga, dos cadenas se convierten en una, lo que reduce en 1 el número de cadenas en el cuadro.
Observación #3
El número de sorteos no es una variable aleatoria. Cada ronda elimina una cuerda de la caja independientemente del resultado (observación n.° 2). Cada ronda tiene dos sorteos, por lo que el número de rondas será igual al número de cuerdas. Por ejemplo, si tenemos 10 cuerdas, tenemos 20 sorteos aleatorios en 10 rondas. Tenga en cuenta que a la última ‘ronda’ solo le queda una cadena y siempre resulta en un bucle.
Observación #4
Esta observación se basa en las otras tres y es la más importante. Desde la perspectiva del conteo de bucles, cada ronda de sorteos aleatorios es independiente de las rondas anteriores. Esto significa que podemos dividir el problema en rondas individuales en lugar de tener que considerar toda la secuencia de rondas juntas.
Tenga en cuenta que si estuviéramos interesados en métricas como la circunferencia esperada de un círculo, esta observación no sería cierta. La longitud de las cuerdas (y por lo tanto la circunferencia de los bucles) depende de las rondas anteriores.
Bien, con estas observaciones, ¡vamos a ver cómo podemos resolver el problema!
La solución de la “fuerza bruta”
Casi todos los problemas como estos (y los problemas de la vida real) tienen una solución de fuerza bruta. Un enfoque que es como cavar a mano un hoyo para una piscina.
Para este problema, podemos crear un árbol de probabilidad y calcular manualmente el número esperado de bucles. Mira, revísalo aquí.
Esta es una solución torpe pero buena para un número pequeño de cadenas. En el video, Grant menciona específicamente 50 cuerdas como un número para resolver (¡eso requeriría un árbol que tenga 250 hojas!). Lo hizo para sacar a su audiencia del método de la fuerza bruta y adoptar soluciones más inteligentes.
Veamos si podemos encontrar un enfoque más inteligente.
Solución divide y vencerás
Al pensar realmente en las características del proceso aleatorio, nos dimos cuenta de que cada ronda de sorteos aleatorios es independiente de las demás (observación n.° 4). Debido a esta propiedad, podemos calcular el valor esperado de sorteos únicos y luego ver si podemos encontrar una manera de combinar múltiples sorteos únicos para resolver el problema.
Número esperado de bucles de un solo sorteo
Ya nos hemos dado cuenta de que el primer sorteo al azar no es muy importante (observación n.º 1): en realidad se trata del segundo sorteo.
Repasemos un problema simple con 4 cuerdas. Hacemos nuestro primer sorteo aleatorio para conseguir el primer final (realmente no importa cuál elijamos). Nuestro segundo sorteo aleatorio puede ser cualquiera de los extremos de la caja, excepto el extremo que seleccionamos para el primer sorteo.
Imaginemos que tenemos 4 cuerdas en la caja, lo que nos da 8 extremos. Después de elegir el primer extremo, no podemos volver a elegirlo, por lo que tenemos 7 extremos entre los que podemos elegir. Uno de los 7 resultará en un bucle, los otros extremos no crearán un bucle. La siguiente imagen ilustra la configuración con mayor claridad que hablar de números.
Entonces, la probabilidad de hacer un bucle es 1/7 y la probabilidad de no hacer un bucle es 6/7; esto produce 1/7 bucles esperados (1*1/7 + 0*6/7).
Generalicemos esto a una fórmula usando el número de cadenas como entrada. Si S es el número de cuerdas, el número de extremos es 2S (dos extremos por cuerda). Después de la primera selección, podemos elegir entre 2S-1 extremos, solo uno de esos extremos da como resultado un bucle. Entonces, la fórmula para los bucles esperados es 1/(2S-1).
Combinando múltiples sorteos para resolver el problema completo
Ahora que hemos creado una fórmula para calcular el número esperado de bucles para una sola ronda, veamos cómo combinar varias rondas. Debido a la observación n.° 4 (la independencia de las rondas para contar bucles) y la observación n.° 2 (número determinista de rondas), podemos simplemente sumar los bucles esperados de cada ronda. Por supuesto, tenemos que actualizar el número de cadenas para cada ronda; podemos hacerlo usando la función de suma.
Ahora que tenemos la fórmula, terminar el desafío es tan trivial como conectar 50 para S, lo que nos da ~2,94 bucles: ¡misión cumplida!
La solución Montecarlo
Debido a que este problema tiene una solución cerrada, podríamos haber detenido nuestra conversación en la última sección. Sin embargo, vale la pena hablar de cómo podríamos resolver este problema con una simulación de Monte Carlo. Si bien no es necesario para problemas bastante simples, Monte Carlo puede venir al rescate si agregamos algunas arrugas complicadas.
Las simulaciones de Monte Carlo estiman valores mediante procesos aleatorios repetidos. En nuestro problema, simulamos el proceso de dibujo aleatorio varias veces y tomamos el promedio del número de bucles contados en las simulaciones.
A medida que aumenta el número de simulaciones (gracias a la ley de los grandes números), el número de Monte Carlo converge al verdadero valor esperado. Aquí está el enlace al código completo. Agregaré el bucle que crea la simulación real a continuación.
from monte_carlo_funcs import create_strings, select_ends, tie_ends # Ejecute Monte Carlo list_of_circles = []
num_strings = 50 num_simulations = 10000 if __name__ == “__main__”: for _ in range(0, num_simulations): # crear el cuadro inicial simulado de cadenas strings = create_strings(num_strings) # iniciar el contador de círculos para esta simulación círculo_counter = 0 # dibujar desde el cuadro hasta que no queden más cadenas mientras len(strings) > 0: end_1, end_2, strings = select_ends(strings) strings, Circle_bool = tie_ends(strings, end_1, end_2) Circle_counter += Circle_bool # agrega el número de círculos que cuenta el número de círculos para cada ronda list_of_circles.append(circle_counter) print(np.mean(list_of_circles))
Cuando ejecuté esto (cambiará un poco cada vez) obtuve 2,95, muy cerca del 2,94 correcto. Esto resalta algo importante: el proceso de Monte Carlo es una buena manera de obtener un presupuesto, pero la flexibilidad tiene el costo de la exactitud.
Haciendo el problema más difícil
Tomémonos un tiempo para resaltar dónde brilla el enfoque de Montecarlo al hacer el problema mucho más difícil. ¿Qué pasaría si cambiáramos el problema de calcular el número esperado de bucles a la circunferencia promedio esperada de los bucles? Este problema es mucho más complejo porque depende de las dependencias entre cada ronda de sorteos aleatorios.
No pude encontrar una solución cerrada al problema (podría existir). Cuando no podemos encontrar soluciones cerradas a los problemas, lo cual sucederá la mayor parte del tiempo, ¡Monte Carlo puede salvar el día! Podríamos modificar fácilmente el código Monte Carlo para rastrear las longitudes de cada cuerda y luego usar esas longitudes para calcular las circunferencias de los bucles cuando se crean. El uso de Monte Carlo reduce este cálculo de un problema matemático muy difícil a un problema de codificación bastante simple.
La conclusión principal es que cuando crear una solución de forma cerrada es difícil o imposible, Monte Carlo puede ser una forma más sencilla de resolver el problema.
Conclusión
La capacidad de comprender profundamente un problema y crear cuidadosamente una solución siempre ha sido una habilidad diferenciadora en la ciencia de datos (y con nuestra reciente dependencia de la IA generativa) se está convirtiendo en un bien aún más escaso. Este rompecabezas me pareció un ejercicio divertido para perfeccionar esas habilidades.
Si bien no tendrá que calcular el número esperado de bucles en un cuadro de cadenas como profesional de datos (o al menos es muy poco probable), con frecuencia encontrará situaciones en las que el camino hacia una solución no es inmediatamente obvio. Comprender profundamente el problema, dividirlo en componentes más pequeños y desarrollar cuidadosamente una solución personalizada son habilidades que se transfieren directamente al trabajo real de análisis y ciencia de datos.