Résoudre le problème de probabilité de chaîne 3Blue1Brown (sans IA)

la peine de résoudre un problème de probabilité idiot pendant mon temps libre alors que j’aurais pu faire défiler la catastrophe ? Parce que j’essaie de rester vigilant dans cette période unique où nous pouvons confier l’essentiel de notre réflexion critique à l’IA générative. Si vous lisez des articles sur TDS, vous et moi partageons probablement cet objectif.

Cet article portera sur la résolution d’un casse-tête de probabilité amusant que l’un de mes YouTubers préférés (3Bleu1Marron) publié récemment. D’ailleurs, si vous ne connaissez pas sa chaîne, vous devez la découvrir. Il se concentre sur des visuels et des explications intuitifs qui vous feront vous demander pourquoi les mathématiques sont enseignées autrement.

La configuration du problème

Le court métrage que j’ai lié ci-dessous vous donnera la meilleure introduction, mais je passerai brièvement en revue la configuration ici en complément.

Imaginez que nous ayons une boîte contenant plusieurs chaînes. Nous sélectionnons au hasard la fin d’une chaîne, puis sélectionnons au hasard la fin d’une autre chaîne. Nous attachons ensuite les extrémités ensemble. Deux choses peuvent se produire : (1) les extrémités proviennent de chaînes différentes et nous avons maintenant une chaîne plus longue ou (2) la deuxième extrémité provient de la même chaîne que nous avons sélectionnée initialement et les attacher ensemble forme une boucle.

Si nous attachons deux ficelles distinctes ensemble, nous replaçons la ficelle la plus longue dans la boîte. Si on fait une boucle, on la retire de la boîte. Ce processus de sélection aléatoire de chaînes se poursuit jusqu’à ce qu’il ne reste plus de chaînes dans la boîte.

La question problématique est la suivante : combien de boucles pensons-nous que ce processus créera ? Ou, en termes moins précis, mais plus pratiques : si nous répétions ce processus plusieurs fois, quel est le nombre moyen de boucles qui seraient créées ?

Principales observations sur le problème

Bien comprendre un problème est toujours essentiel pour trouver une bonne solution. En plus de la simple compréhension des mécanismes abordés dans la dernière section, nous devrons comprendre certaines observations clés.

Observation #1

Chaque tour de tirage au sort comporte deux composantes aléatoires. Le premier tirage au sort et le second. Le premier tirage n’est pas très important. Le deuxième tirage est le cas, car il détermine si nous faisons une boucle ou une chaîne plus longue.

Observation #2

Chaque tour entraîne une chaîne de moins dans la boîte, quoi qu’il arrive. Si une boucle est créée, la chaîne qui a créé la boucle est supprimée. Si une chaîne plus longue est créée, deux chaînes ne font plus qu’une, réduisant de 1 le nombre de chaînes dans la boîte.

Observation #3

Le nombre de tirages est pas une variable aléatoire. Chaque tour retire une ficelle de la boîte quel que soit le résultat (observation n°2). Chaque tour comporte deux tirages, le nombre de tours sera donc égal au nombre de chaînes. Par exemple, si nous avons 10 chaînes, nous avons 20 tirages aléatoires en 10 tours. Notez que le dernier « tour » n’a qu’une seule chaîne restante et aboutit toujours à une boucle.

Observation #4

Cette observation s’appuie sur les trois autres et est la plus importante. Du point de vue du comptage des boucles, chaque tour de tirage au sort est indépendant des tours précédents. Cela signifie que nous pouvons diviser le problème en tours individuels plutôt que d’avoir à considérer l’ensemble de la séquence de tours ensemble.

Notez que si nous nous intéressions à des mesures telles que la circonférence attendue d’un cercle, cette observation ne serait pas vraie. La longueur des ficelles (et donc la circonférence des boucles) sont en fonction des tours précédents.

Bon, avec ces observations faites, voyons comment nous pouvons résoudre le problème !

La solution « force brute »

Presque tous les problèmes comme ceux-ci (et les problèmes réels) ont une solution de type force brute. Une approche qui revient à creuser à la main un trou pour une piscine.

Pour ce problème, nous pouvons créer un arbre de probabilité et calculer manuellement le nombre attendu de boucles. Les regards le parcourent ici.

C’est une solution lourde mais efficace pour un petit nombre de chaînes. Dans la vidéo, Grant appelle spécifiquement 50 chaînes comme nombre à résoudre (cela nécessiterait un arbre comportant 2⁵⁰ feuilles!). Il a fait cela pour pousser son public hors de la méthode de la force brute vers des solutions plus intelligentes.

Voyons si nous pouvons trouver une approche plus intelligente.

Solution diviser pour régner

En réfléchissant bien aux caractéristiques du processus aléatoire, nous nous sommes rendu compte que chaque tour de tirage au sort est indépendant des autres (observation n°4). Grâce à cette propriété, nous pouvons calculer la valeur attendue de tirages uniques, puis voir si nous pouvons trouver un moyen de combiner plusieurs tirages uniques pour résoudre le problème.

Nombre de boucles attendu pour un seul tirage

Nous avons déjà réalisé que le premier tirage au sort n’est pas très important (observation n°1), il s’agit plutôt du deuxième tirage.

Passons en revue un problème simple avec 4 chaînes. Nous effectuons notre premier tirage au sort pour obtenir le premier bout (peu importe lequel nous choisissons). Notre deuxième tirage au sort peut être l’une des extrémités de la boîte, sauf la fin que nous avons sélectionnée pour le premier tirage.

Imaginez que nous ayons 4 cordes dans la boîte, ce qui nous donne 8 extrémités. Après avoir choisi la première extrémité, nous ne pouvons pas la choisir à nouveau, nous avons donc 7 extrémités parmi lesquelles choisir. L’une des 7 entraînera une boucle, les autres extrémités ne créeront pas de boucle. L’image ci-dessous illustre la configuration plus clairement que les chiffres.

Ainsi, la probabilité de faire une boucle est de 1/7 et la probabilité de ne pas faire de boucle est de 6/7 – cela donne 1/7 de boucles attendues (1*1/7 + 0*6/7).

Généralisons cela à une formule utilisant le nombre de chaînes comme entrée. Si S est le nombre de chaînes – le nombre de extrémités est 2S (deux extrémités par chaîne). Après la première sélection, nous pouvons choisir parmi 2S-1 se termine, une seule de ces extrémités aboutit à une boucle. Ainsi, la formule des boucles attendues est 1/(2S-1).

Combiner plusieurs tirages pour résoudre le problème complet

Maintenant que nous avons créé une formule pour calculer le nombre attendu de boucles pour un seul tour, voyons comment combiner plusieurs tours. Grâce à l’observation n°4 (l’indépendance des tours pour compter les boucles) et à l’observation n°2 (nombre déterministe de tours), nous pouvons simplement additionner les boucles attendues de chaque tour. Bien sûr, nous devons mettre à jour le nombre de chaînes pour chaque tour – nous pouvons le faire en utilisant la fonction de sommation.

Maintenant que nous avons la formule, terminer le défi est aussi trivial que d’en brancher 50 pour S ce qui nous donne ~2,94 boucles – mission accomplie !

La solution Monte-Carlo

Étant donné que ce problème a une solution sous forme fermée, nous aurions pu arrêter notre conversation avec la dernière section. Cependant, il est utile de discuter de la manière dont nous pourrions résoudre ce problème avec une simulation de Monte Carlo. Bien qu’il ne soit pas nécessaire pour des problèmes assez simples, Monte Carlo peut venir à la rescousse si l’on y ajoute quelques complications.

Les simulations Monte Carlo estiment les valeurs à l’aide de processus aléatoires répétés. Dans notre problème, nous simulons le processus de tirage aléatoire plusieurs fois et prenons la moyenne du nombre de boucles comptées dans les simulations.

À mesure que le nombre de simulations augmente – grâce à la loi des grands nombres – le nombre de Monte Carlo converge vers la véritable valeur attendue. Voici le lien au code complet – j’ajouterai la boucle qui crée la simulation réelle ci-dessous.

from monte_carlo_funcs import create_strings, select_ends, tie_ends

# Run the Monte Carlo
list_of_circles = []
num_strings = 50
num_simulations = 10000

if __name__ == "__main__":
  for _ in range(0, num_simulations):
      
      # create the simulated starting box of strings
      strings = create_strings(num_strings)
  
      # start circle counter for this simulation
      circle_counter = 0
  
      # draw from the box until there are no more strings left
      while 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
          
      # add the number of circles that counts number of circles for each round
      list_of_circles.append(circle_counter)
  
  print(np.mean(list_of_circles))

Quand j’ai exécuté ceci (cela changera un peu à chaque fois), j’ai obtenu 2,95 – très proche du bon 2,94. Cela met en évidence quelque chose d’important : le processus de Monte Carlo est un bon moyen d’obtenir une estimation, mais la flexibilité se fait au détriment de l’exactitude.

Rendre le problème plus difficile

Prenons le temps de souligner les points forts de l’approche de Monte Carlo en rendant le problème beaucoup plus difficile. Et si nous changions le problème du calcul du nombre attendu de boucles au nombre attendu de boucles ? circonférence moyenne des boucles. Ce problème est beaucoup plus complexe car il repose sur des dépendances entre chaque tour de tirages aléatoires.

Je n’ai pas réussi à trouver une solution fermée au problème (il pourrait en exister une). Lorsque nous ne parvenons pas à trouver des solutions fermées aux problèmes – ce qui sera la plupart du temps – Monte Carlo peut sauver la situation ! Nous pourrions facilement modifier le code Monte Carlo pour suivre les longueurs de chaque chaîne, puis utiliser ces longueurs pour calculer les circonférences des boucles lors de leur création. L’utilisation de Monte Carlo réduit ce calcul d’un problème mathématique très difficile à un problème de codage assez simple.

Le principal point à retenir est que lorsque la création d’une solution sous forme fermée est difficile, voire impossible, Monte Carlo peut être un moyen plus simple de résoudre le problème.

Conclusion

La capacité de comprendre en profondeur un problème et de créer une solution réfléchie a toujours été une compétence différenciante en science des données – et avec notre récente dépendance à l’IA générative – elle devient encore plus rare. J’ai trouvé ce puzzle comme un exercice amusant pour perfectionner ces compétences.

Même si vous n’aurez pas à calculer le nombre attendu de boucles dans une boîte de chaînes en tant que professionnel des données (ou du moins, c’est très improbable), vous rencontrerez fréquemment des situations où le chemin vers une solution n’est pas immédiatement évident. Comprendre en profondeur le problème, le décomposer en composants plus petits et développer soigneusement une solution sur mesure sont des compétences qui se transfèrent directement au travail réel de science des données et d’analyse.