Arbre binaire à nombre aléatoire de fils.

[invitecb6e3de4]

Bonsoir,

Au cours d'un projet de recherche, je me retrouve face à un problème qui me pose quelques soucis!

Pour faire simple, je génère un arbre binaire ou chaque noeud possède soit zéro soit deux fils avec probabilité 0.5, et je n'arrive pas à exprimer en termes de probabilités la quantité de noeuds qu'un tel arbre a en moyenne. L'arbre a de plus forcément une racine, donc un noeud.

Avec une simulation informatique, j'ai pu voir que comme prévu l'arbre n'a qu'un seul noeud dans la moitié des cas, mais à coté de ça les valeurs explosent de temps en temps (plusieurs milliards de noeuds voire arbre trop grand et programme qui ne peut pas terminer ).

Quelqu'un saurait-il caractériser d'une manière ou d'une autre le nombre de noeuds? Car mes recherches ne me mènent nulle part (je suis d'avantage informaticien que matheux )

Merci!
-----

[invite179e6258]

en somme tu simules une réaction en chaîne et de temps en temps tu as une explosion atomique...

[invite179e6258]

bon le_teap ne reparaît plus, j'ai dû l'effaroucher...

ma remarque n'était pas une plaisanterie. Ce problème a été étudié par E Schrödinger dans son papier de 1945 (!) : Probability problems in nuclear chemistry.

le processus que tu décris est appelé processus de branchement (branching process en Anglais).

Si m est le nombre moyen de descendants d'un sommet, on peut montrer que :

Si m>1 le processus peut ne pas se terminer, auquel cas la variable aléatoire "nombre total de sommets de l'arbre" n'est pas bien définie. Mais il y a toujours une probabilité positive pour que le processus se termine.

Si 0<m<1 le processus se termine presque-sûrement et l'espérance du nombre total de sommets est 1/(1-m).

Si m=1 le processus se termine presque-sûrement mais l'espérance du nombre total de sommets est infinie. Tu es dans ce cas et c'est pourquoi tu peux observer de très grands arbres.

[invitecb6e3de4]

Je suis désolé, j'avais complètement oublié avoir posté ce message! Merci pour ta réponse

[A voir en vidéo sur Futura]