février | 2016 | Solutions et Dissolutions

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 $n$ secondes.

$n=2$ :

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 $\frac{2}{4}=\frac{1}{2}$ .

$n=4$ :

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 $n=2$ ) et peuvent être ignorées. Parmi les huit qui restent, seules deux ramènent Robert à sont point de départ, soit $\frac{2}{8}=\frac{1}{4}$ .

$n=6$ :

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 $n=2$ ou $n=4$ . Parmi les vingt-quatre qui restent, quatre ramènent Robert à son point de départ, soit $\frac{4}{24}=\frac{1}{6}$ .

Vous remarquez un pattern ? Moi aussi : la proportion des trajectoires qui s’arrêtent après $n$ secondes parmi celles qui ne se sont pas encore arrêtées vaut $\frac{1}{n}$ . J’ai vérifié jusqu’à $n=20$ 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 $n -1$ secondes et ‘finales’ le nombre de trajectoires qui sont au point de départ après $n$ secondes. Par contre, je n’ai aucune idée comment ces proportions valent toujours $\frac{1}{n}$ , 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 $n$ secondes. Mais on a seulement cette proportion parmi les trajectoires qui ne sont jamais repassées par le point de départ durant les $n-1$ secondes précédentes. Pas de problème ! Si on prend $U_n$ la proportion des trajectoires qui ne sont jamais repassées par le départ après $n$ secondes, alors :

$U_2=\frac{1}{2}$

$U_{n+2} = U_n \times \left (1-\frac{1}{n} \right )$

Toutes les deux secondes, $\frac{1}{n}$ des trajectoires restantes reviennent au point de départ. Wolfram a la gentillesse de trouver une relation directe pour $U_n$ :

$U_n = \frac{ \left ( n-2 \right ) ! }{ 2^{n-1} \: ( \frac{n-2}{2} ! )^2 }$

Donc ! Après $n -1$ secondes, il y a $U_n$ des trajectoires qui ne sont jamais repassées par le point de départ. Après exactement $n$ secondes, Robert est revenu à son point de départ pour la première fois dans $\frac{U_n}{n}$ des trajectoires. Donc pour avoir le temps moyen $T$ que Robert met pour revenir au point de départ, il suffit de sommer pour tous les $n$ pairs la proportion $\frac{U_n}{n}$ fois le temps écoulé $n$ .

$T = \sum_{ \substack{ n=2, \\ n \: \text{pair}} }^{+\infty} \frac{U_n}{n} \times n = \sum_{ \substack{ n=2, \\ n \: \text{pair}} }^{+\infty} U_n$

Voilà qui est suspicieusement sympathique, surtout que Wolfram nous dit (avec $n=2k$ ) :

$\begin{equation*} \begin{split} T_n & = \sum_{ \substack{ n=2, \\ n \: \text{pair}} }^{n} U_n = \sum_{k=1}^{\frac{n}{2}} U_{2k} \\[0ex] T_n & = \sum_{k=1}^{\frac{n}{2}} \frac{ \left ( 2k-2 \right ) ! }{ 2^{2k-1} \: ((k-1) ! )^2 } \\[1ex] T_n & = \frac{n \, n!}{2^{n+1}(\frac{n}{2}!)^2} \end{split} \end{equation*}$

Où $T_n$ est le temps moyen entre deux passages par le point de départ après $n$ secondes. Et enfin si on suppose $n$ grand, on peut utiliser la Formule de Stirling : $n! \sim \, \sqrt{2\pi n} \, \left ( \frac{n}{e} \right )^n$ qui donne :

$\begin{equation*} \begin{split} T_n & \sim \frac{n \sqrt{2 \pi n} \left ( \frac{n}{e} \right )^n}{2^{n+1} ( \sqrt{\pi n} ( \frac{n}{2e} )^{\! \frac{n}{2}} )^2} \\[0ex] T_n & \sim \frac{ \sqrt{2 n} \left ( \frac{n}{e} \right )^n}{2^{n+1} \: \sqrt{\pi} \ ( \frac{n}{e} )^n \ 2^{-n}} \\[1ex] T_n & \sim \frac{ \sqrt{n} }{\sqrt{2 \pi}} \ \xrightarrow[\: n \to +\infty \:]{ } \: + \infty \end{split} \end{equation*}$

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 $n$ secondes, on peut s’attendre à ce que Robert soit repassé environ $\frac{n}{\sqrt{n} / \sqrt{2 \pi}}=\sqrt{2 \pi n}$ fois par le point de départ. Mais en moyenne, plus le temps passe, plus Robert s’éloigne vers l’infini et au-delà.

Publicités

Solutions et Dissolutions

|| Les brouillons de Sylvain ||

Archives Mensuelles: février 2016

L’ami Robert