8.10 MARCHE ALÉATOIRE

 

 

INTRODUCTION

 

Dans la vie quotidienne, de nombreux phénomènes sont déterminés par le hasard et il est souvent nécessaire de prendre des décisions sur la base de probabilités. On pourrait par exemple être amenés à préférer un mode de transport à un autre sur la base de leur probabilité respective d’être impliqué dans un accident. Dans de telles situations, l’ordinateur peut se révéler être un outil important permettant d’examiner les dangers potentiels à l’aide simulations, en ne prenant absolument aucun risque.

Imaginons qu’une personne se soit perdue et qu’elle ne trouve plus le chemin pour rentrer à la maison. Elle va se mettre à effectuer une marche aléatoire consistant à se déplacer d’une même distance à chaque intervalle de temps, mais en choisissant une direction aléatoire. Même si un tel mouvement ne correspond pas nécessairement à la réalité, il permet de découvrir des caractéristiques importantes applicables à des systèmes réels comme la modélisation de marchés boursiers en mathématiques financières ou du déplacement de molécules.

CONCEPTS DE PROGRAMMATION: Marche aléatoire, mouvement brownien

 

 

MACHE ALÉATOIRE À UNE DIMENSION

 

Une fois encore, les graphiques tortues sont très utiles pour représenter la simulation graphiquement. Au temps 0, la tortue se trouve à la position x = 0 et se déplace le long de l’axe Ox par pas d’égale longueur. À chaque pas, la tortue "décide" de faire un pas vers la gauche ou vers la droite de manière aléatoire. Dans le programme suivant, les deux choix surviennent avec la même probabilité p = ½ (marche aléatoire symétrique).


 

 

from gturtle import *
from gpanel import *
from random import randint

makeTurtle()
makeGPanel(-50, 550, -480, 480)
windowPosition(880, 10)
drawGrid(0, 500, -400, 400)
title("Mean distance versus time")
lineWidth(2)
setTitle("Random Walk")

t = 0
while t < 500:
    if randint(0, 1) == 1:
        setHeading(90)
    else:
        setHeading(-90)
    forward(10)
    x = getX()
    draw(t, x)
    t += 1
print("All done")
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Vous êtes peut-être surpris d’observer que, dans la plupart des cas, la tortue s’éloigne peu à peu de son point de départ alors même qu’elle fait, à chaque étape, un pas de même longueur à gauche ou à droite avec la même probabilité. Afin d’examiner ce résultat de manière plus minutieuse, notre prochain programme va déterminer la distance moyenne séparant la tortue du point de départ après t étapes parmi 1'000 marches aléatoires.

 

 

LA LOI DE LA RACINE CARRÉE DU TEMPS

 

Le programme ci-dessous permet de visualiser de quelle distance une marche aléatoire de t pas s’éloigne de l’origine en moyenne pour t valant 100, 200, 300, …, 1000. Pour chaque nombre de pas t, la simulation est répétée 1000 fois (1000 marches aléatoires) dont le point d’arrivée est représenté à l’écran. La coordonnée y correspond au nombre de pas que comporte la marche aléatoire. Afin d’accélérer l’obtention des résultats, il est conseillé de cacher la tortue et d’éviter d’en dessiner la trace. Chacune de ces simulations permet de déterminer une distance r séparant le point final du point initial. Pour chaque jeu d’expériences avec un t donné, on obtiendra ainsi une distance d’éloignement moyenne avec le point de départ qui est reportée dans un graphique GPanel muni d’un repère orthonormé.

from gturtle import *
from gpanel import *
from math import sqrt
from random import randint

makeTurtle()
makeGPanel(-100, 1100, -10, 110)
windowPosition(850, 10)
drawGrid(0, 1000, 0, 100)
title("Mean distance versus time")
ht()
pu()

for t in range(100, 1100, 100):
    setY(250 - t / 2)
    label(str(t))    
    count = 0
    repeat 1000:
        repeat t: 
           if randint(0, 1) == 1:
               setHeading(90)
           else:
               setHeading(-90)
           forward(2.5)
        dot(3)
        r = abs(getX())
        count += r
        setX(0)
    d = count / 1000   
    print("t =", t, "d =", d, "q = d / sqrt(t) =", d / sqrt(t))  
    draw(t, d)
    fillCircle(5)
print("all done")
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

 

MEMENTO

 

Comme la visualisation graphique le montre, la distance moyenne séparant le point d’arrivée du point de départ croît avec le nombre de pas de la marche aléatoire. Dans la console, on calcule également le quotient q = d / sqrt(t). Du fait qu’il est toujours pratiquement constant, on peut raisonnablement supposer que la relation d = q * sqrt(t) est vraie :

La distance moyenne entre le point de départ et le point d’arrivée de la marche aléatoire augmente selon la racine carrée du temps (nombre d’étapes).

 

 

LA MARCHE DU MEC BOURRÉ

 

Les choses deviennent encore plus intéressantes lorsque la tortue peut se déplacer dans deux dimensions. Elle effectue alors une marche aléatoire à deux dimensions. La tortue effectue des pas de longueur identique mais dans des directions aléatoires.

Les mathématiciens et physiciens évoquent souvent ce problème par une histoire à ne pas prendre trop au sérieux.

"Un homme rond comme une barrique tente de regagner son domicile après une longue tournée de bars. Comme il est complètement désorienté, il fait chaque nouveau pas dans une direction aléatoire. En moyenne, à quelle distance se trouve-t-il du bar pour un nombre de pas donné ? "

Il suffit de modifier l égèrement le programme précédent. On examine à nouveau comment la distance moyenne dépend du temps (du nombre de pas effectués).


 

from gturtle import *
from gpanel import *
from math import sqrt

makeTurtle()
makeGPanel(-100, 1100, -10, 110)
windowPosition(850, 10)
drawGrid(0, 1000, 0, 100)
title("Mean distance versus time")
ht()
pu()

for t in range(100, 1100, 100):
    count = 0
    clean()
    repeat 1000:
        repeat t: 
           fd(2.5)
           setRandomHeading()
        dot(3)
        r = math.sqrt(getX() * getX() + getY() * getY())
        count += r
        home()
    d = count / 1000   
    print("t =", t, "d =", d, "q = d / sqrt(t) =", d / sqrt(t))
    draw(t, d)
    fillCircle(5)
    delay(2000)
print("all done")
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

La loi de la racine carrée du temps s’applique également aux marches aléatoires à deux dimensions. En 1905, Albert Einstein en personne a démontré cette loi pour les particules de gaz dans son fameux article « Über die von der molekularkinetischen Theorie der Wärme geforderte Bewegung von in ruhenden Flüssigkeiten suspendierten Teilchen » qui fournit en passant une explication théorique au phénomène du mouvement Brownien. Une année plus tard, M. Smoluchowski est parvenu au même résultat en utilisant une idée différente.

 

 

MOUVEMENT BROWNIEN

 

En 1827 déjà, le biologiste Robert Brown observa au microscope des grains de pollen en suspension dans une goutte d’eau effectuer des mouvements irréguliers de secousses. Il a interprété cette observation en attribuant une force vitale inhérente aux grains de pollen. Il a fallu attendre la découverte de la structure moléculaire de la matière pour pouvoir attribuer ce phénomène au mouvement thermique des molécules d’eau entrant en collision avec les grains de pollen.

Le mouvement brownien peut être joliment montré dans une simulation informatique modélisant les molécules comme de petites sphères en mouvement qui échangent leur vitesse lors des collisions. Cette simulation peut être facilement implémentée à l’aide de JGameGrid puisqu’il est possible de gérer les collisions avec les événements. Pour ce faire, on crée une classe CollisionListener qui dérive de GGActorCollisionListener et on implémente le gestionnaire d’événements en redéfinissant la méthode collide(). On ajoute chaque particule à l’auditeur (listener en anglais) en utilisant addActorCollisionListener(). Il est possible de régler le type et la taille de la zone de collision à l’aide de la méthode setCollisionCircle(). Dans un souci de simplicité, les 40 particules sont réparties en quatre groupes de vitesses différents.



from gamegrid import *

# =================== class Particle ====================
class Particle(Actor):
    def __init__(self):
        Actor.__init__(self, "sprites/ball.gif", 2)
 
    # Called when actor is added to gamegrid
    def reset(self):
        self.oldPt = self.gameGrid.toPoint(self.getLocationStart())
   
    def advance(self, distance):
        pt = self.gameGrid.toPoint(self.getNextMoveLocation())
        dir = self.getDirection()
        # Left/right wall
        if pt.x < 5 or pt.x > w - 5:
            self.setDirection(180 - dir)
        # Top/bottom wall
        if pt.y < 5 or pt.y > h - 5:
            self.setDirection(360 - dir)
        self.move(distance)

    def act(self):
        self.advance(3)
        if self.getIdVisible() == 1:
            pt = self.gameGrid.toPoint(self.getLocation())
            self.getBackground().drawLine(self.oldPt.x, self.oldPt.y, pt.x, pt.y)
            self.oldPt.x = pt.x
            self.oldPt.y = pt.y

# =================== class CollisionListener =========
class CollisionListener(GGActorCollisionListener):
   # Collision callback: just exchange direction and speed
    def collide(self, a,  b):
        dir1 = a.getDirection()
        dir2 = b.getDirection()
        sd1 = a.getSlowDown()
        sd2 = b.getSlowDown()
        a.setDirection(dir2)
        a.setSlowDown(sd2)
        b.setDirection(dir1)
        b.setSlowDown(sd1)
        return 10  # Wait a moment until collision is rearmed
    
# =================== Global section ====================
def init():
    collisionListener = CollisionListener()
    for i in range(nbParticles):
        particles[i] = Particle()
        # Put them at random locations, but apart of each other
        ok = False
        while not ok:
            ok = True
            loc = getRandomLocation()

        for k in range(i):
            dx = particles[k].getLocation().x - loc.x
            dy = particles[k].getLocation().y - loc.y
            if dx * dx + dy * dy < 300:
                ok = False
        addActor(particles[i], loc, getRandomDirection())
        # Select collision area
        particles[i].setCollisionCircle(Point(0, 0), 8)
        # Select collision listener 
        particles[i].addActorCollisionListener(collisionListener)
        # Set speed in groups of 10
        if i < 10:
            particles[i].setSlowDown(2)
        elif i < 20:
            particles[i].setSlowDown(3)
        elif i < 30:
            particles[i].setSlowDown(4)
    #  Define collision partners
    for i in range(nbParticles):
        for k in range(i + 1, nbParticles):
            particles[i].addCollisionActor(particles[k])
    particles[0].show(1)        

w = 400
h = 400
nbParticles = 40
particles = [0] * nbParticles

makeGameGrid(w, h, 1, False)
setSimulationPeriod(10)
setTitle("Brownian Movement")
show()
init()
doRun()
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Les molécules sont modélisées par la classe Particle dérivée de la classe Actor. Elles possèdent deux images de sprite, l’une rouge et l’autre verte, pour permettre de distinguer une molécule particulière dont on voudrait suivre le trajet. L’image verte correspond à spriteID = 1 qui est testé dans la méthode act() pour dessiner la trace avec drawLine().

 

 

EXERCICES

 

1.


Une personne effectue une marche aléatoire de 100 pas en partant de x = 0 avec une probabilité p = ½ de marcher vers la droite et une probabilité q = ½ de marcher vers la gauche. Exécuter la simulation 10'000 fois et déterminer la distribution de fréquences de la position finale en l’affichant dans un GPanel.


2.


Comme le montre l’exercice 1, la probabilité de se trouver au point de départ à la fin de la marche est la plus élevée. Comment cela peut-il s’accorder avec la loi de la racine carrée du nombre de pas ?


3.


Effectuer la même simulation mais en prenant les probabilités p = 0.8 de se déplacer à droite et q = 0.2 de se déplacer à gauche.


4*.


Il est possible de prouver que la distribution des fréquences de la position finale correspond à une loi binomiale. La probabilité de se trouver à la coordonnée x après n pas est donnée, pour un nombre de pas n ainsi qu’une position x pairs :

  P(x, n) = (              n!             )/ ((n + x)/2)!((n - x)/2)! p(n+x)/2q(n-x)/2  

Représenter graphiquement la courbe de la distribution théorique dans l’histogramme obtenu à l’exercice 1.