Imaginez un crabe. Il s’appelle Robert. C’est un crabe comme on en trouve sous n’importe quel rocher. Mais Robert a un problème : il ne sait pas tourner. Il ne peut faire que des pas de côté. Et il s’ennuie. Comme tous les gens qui s’ennuient, il décide donc de faire un petit jeu mathématique : toutes les secondes, il lance une pièce. Si c’est pile il fait un pas à droite, si c’est face il fait un pas à gauche. À votre avis, combien de temps met-il (en moyenne) pour revenir à son point de départ ?
Il est assez facile d’écrire un programme de 38 lignes qui simule Robert faisant des pas vers la gauche ou vers la droite et calculer la durée moyenne entre deux passages par le point de départ. J’ai essayé et la moyenne ne converge apparemment pas, mais semble augmenter avec le temps de simulation, ce qui n’est pas rassurant. Il reste donc a trouver un moyen de formaliser tout ça pour être sûr.
Commençons par nous intéresser à toutes les trajectoires que Robert peut parcourir en secondes.
:
dd dg gg gd
Les deux trajectoires rouges sont celles qui ramènent Robert à son point de départ. Il y en a deux, sur quatre trajectoires possibles, soit .
:
dddd dddg ddgd ddgg dgdd dgdg dggd dggg gddd gddg gdgd gdgg ggdd ggdg gggd gggg
Ah ! On dirait qu’il se passe des trucs. Pour commencer, les trajectoires qui commencent par gd ou dg sont « impossibles » : elles sont déjà passées une fois au point de départ ( pour ) et peuvent être ignorées. Parmi les huit qui restent, seules deux ramènent Robert à sont point de départ, soit
.
:
dddddd dddddg ddddgd ddddgg dddgdd dddgdg dddggd dddggg ddgddd ddgddg ddgdgd ddgdgg ddggdd ddggdg ddgggd ddgggg dgdddd dgdddg dgddgd dgddgg dgdgdd dgdgdg dgdggd dgdggg dggddd dggddg dggdgd dggdgg dgggdd dgggdg dggggd dggggg gddddd gddddg gdddgd gdddgg gddgdd gddgdg gddggd gddggg gdgddd gdgddg gdgdgd gdgdgg gdggdd gdggdg gdgggd gdgggg ggdddd ggdddg ggddgd ggddgg ggdgdd ggdgdg ggdggd ggdggg gggddd gggddg gggdgd gggdgg ggggdd ggggdg gggggd gggggg
Ça devient long à taper, ces bêtises. Cette fois, il y a encore plus de trajectoires qui sont déjà repassées par la case départ pour ou
. Parmi les vingt-quatre qui restent, quatre ramènent Robert à son point de départ, soit
.
Vous remarquez un pattern ? Moi aussi : la proportion des trajectoires qui s’arrêtent après secondes parmi celles qui ne se sont pas encore arrêtées vaut
. J’ai vérifié jusqu’à
et ça a l’air de tenir :
n valides finales proportion 2 4 2 1/2 = 2/4 4 8 2 1/4 = 2/8 6 24 4 1/6 = 4/24 8 80 10 1/8 = 10/80 10 280 28 1/10 = 28/280 12 1008 84 1/12 = 84/1008 14 3696 264 1/14 = 264/3689 16 13728 858 1/16 = 858/13728 18 51480 2860 1/18 = 2860/51480 20 194480 9724 1/20 = 9724/194480
Avec dans la colonne ‘valides’ le nombre de trajectoires qui ne sont pas encore passées par le point de départ après secondes et ‘finales’ le nombre de trajectoires qui sont au point de départ après
secondes. Par contre, je n’ai aucune idée comment ces proportions valent toujours
, donc si vous avez une illumination, n’hésitez pas à me le dire.
On avance : on veut savoir quelle proportion des trajectoires reviennent au point de départ en exactement secondes. Mais on a seulement cette proportion parmi les trajectoires qui ne sont jamais repassées par le point de départ durant les
secondes précédentes. Pas de problème ! Si on prend
la proportion des trajectoires qui ne sont jamais repassées par le départ après
secondes, alors :
Toutes les deux secondes, des trajectoires restantes reviennent au point de départ. Wolfram a la gentillesse de trouver une relation directe pour
:
Donc ! Après secondes, il y a
des trajectoires qui ne sont jamais repassées par le point de départ. Après exactement
secondes, Robert est revenu à son point de départ pour la première fois dans
des trajectoires. Donc pour avoir le temps moyen
que Robert met pour revenir au point de départ, il suffit de sommer pour tous les
pairs la proportion
fois le temps écoulé
.
Voilà qui est suspicieusement sympathique, surtout que Wolfram nous dit (avec ) :
Où est le temps moyen entre deux passages par le point de départ après
secondes. Et enfin si on suppose
grand, on peut utiliser la Formule de Stirling :
qui donne :
Donc le temps moyen entre deux passages par le point de départ diverge effectivement. C’est dommage, mais pas inattendu. En fin de compte, après secondes, on peut s’attendre à ce que Robert soit repassé environ
fois par le point de départ. Mais en moyenne, plus le temps passe, plus Robert s’éloigne vers l’infini et au-delà.