Puce (saut de)

Imaginez une puce posée sur la case 0 d’une ligne d’entiers. À chaque tour, une pièce décide de son prochain saut : une case à droite pour pile, une case à gauche pour face. Après plusieurs tours, sa position dépend de toute la succession des résultats.

Ce déplacement au hasard est une marche aléatoire. Le modèle décrit les positions possibles et la probabilité de chaque saut, puis étudie notamment si la puce revient souvent à son point de départ ou finit par s’en éloigner.

Un saut de puce est un processus aléatoire observé à des instants discrets. La variable X_n désigne la position après n sauts et prend ses valeurs dans un ensemble discret, souvent l’ensemble ℤ des entiers. Dans le modèle voisin le plus simple, depuis l’entier i, la puce va vers i + 1 ou i − 1 selon des probabilités fixées. Ces probabilités peuvent être identiques ou dépendre de la position.

Lorsque le prochain saut ne dépend du passé qu’à travers la position actuelle, les positions forment une chaîne de Markov. Si i₀, …, i_n désignent une suite possible de positions et j la position suivante, cette propriété s’écrit Si p_ij désigne la probabilité de passer de l’état i à l’état j, p_ij est nul dès que j n’est ni i − 1 ni i + 1 dans un jeu limité aux voisins.

Un état est récurrent si, en partant de lui, la probabilité d’y revenir au moins une fois à un instant strictement positif vaut 1. Il est transient si cette probabilité est strictement inférieure à 1 ; le nombre de ses visites est alors presque sûrement fini. Ces propriétés concernent la loi du processus entier, pas l’allure d’une seule trajectoire. Au sens plus large donné par la source, l’expression couvre aussi des processus à sauts sur tout espace d’états discret, sans obligation de rester sur ℤ ni de ne visiter que des voisins.

Une puce part de l’entier 0. Les lancers sont indépendants : chaque saut vaut +1 ou −1, chacun avec la probabilité 1/2. On observe quatre lancers successifs : droite, gauche, droite, droite. Les données sont donc la position initiale 0, quatre sauts et la même loi symétrique à chaque étape.

1. Le premier saut ajoute 1 : la puce passe de 0 à 1.
2. Le deuxième retranche 1 : elle revient à 0.

3. Les deux derniers sauts ajoutent chacun 1. La trajectoire complète est Un diagramme temps-position rend visibles les quatre déplacements de cette trajectoire.

4. Pour contrôler le retour après deux sauts, deux suites sont possibles : droite puis gauche, ou gauche puis droite. Chacune a pour probabilité 1/2 × 1/2 = 1/4. Leur somme donne donc

Le résultat observé après quatre sauts est la position 2. Le contrôle de parité est refaisable immédiatement : après un nombre pair de déplacements de longueur 1 depuis 0, la position doit être paire ; 2 satisfait bien cette contrainte.

Pour modéliser un déplacement aléatoire sur une ligne, on choisit les états possibles, la position de départ et la loi des sauts. Le saut de puce convient lorsque les changements ont lieu par étapes séparées et que les positions sont discrètes. Un modèle continu est préférable si le mouvement doit être décrit à tout instant.

Pour simuler le jeu, on tire un résultat à chaque étape, on ajoute le déplacement correspondant, puis on conserve la suite des positions. Répéter de nombreuses trajectoires permet d’estimer une probabilité de retour ou d’atteinte. Un calcul exact reste préférable lorsque le petit nombre d’étapes permet d’énumérer toutes les suites.

Pour reconnaître une chaîne de Markov, on vérifie si la loi du prochain état est entièrement déterminée par l’état actuel. Si elle dépend aussi du saut précédent, il faut employer un processus avec mémoire ou agrandir l’état afin d’y inclure l’information nécessaire.

Une suite déterministe. Dans une suite définie par une règle sans hasard, la position suivante est imposée. Dans le saut de puce, plusieurs positions suivantes peuvent avoir une probabilité positive. Depuis 0, la règle « toujours ajouter 1 » donne 1 à coup sûr ; une pièce équilibrée donne 1 ou −1.

Une chaîne de Markov quelconque. Une chaîne de Markov peut passer entre des états qui ne sont pas des entiers voisins. Le jeu de la puce sur ℤ est un modèle particulier lorsque seuls les passages de i vers i − 1 ou i + 1 sont autorisés.

La densité des nombres rationnels. Cette propriété topologique affirme qu’entre deux réels distincts se trouve un rationnel. Elle ne décrit ni une trajectoire aléatoire ni des probabilités de transition ; le simple partage du mot « puce » dans certains problèmes ne suffit pas à identifier la même notion.

Probabilités 0 ou 1. Si le saut vers la droite a toujours la probabilité 1, la trajectoire devient déterministe. Le processus reste descriptible dans le même cadre, mais il n’illustre plus un choix aléatoire entre deux voisins. Il faut alors signaler ce cas dégénéré plutôt que parler d’une marche symétrique.

Bord de l’espace d’états. Sur un segment d’entiers, une puce placée à une extrémité n’a pas deux voisins dans le segment. La règle doit préciser si elle reste sur place, rebondit, est absorbée ou quitte l’espace ; sans cette convention, le modèle est incomplet.

Une trajectoire ne prouve pas la récurrence. Voir la puce revenir plusieurs fois dans une simulation ne suffit pas à conclure. Il faut étudier la probabilité de retour sur l’ensemble des trajectoires, ou estimer cette probabilité avec une incertitude explicitée.

Sauts plus longs ou espace différent. Dans l’usage général, un processus à sauts discret peut relier des états non voisins. Il faut alors donner son espace d’états et toutes les transitions autorisées au lieu de reprendre sans vérification la règle i ± 1 du modèle sur les entiers.

chaîne de Markov — Pour formaliser les probabilités de transition lorsque le prochain état ne dépend que de l’état actuel.

Transiente (marche aléatoire) — Pour approfondir le cas où un état risque de n’être visité qu’un nombre fini de fois.