8.10 RANDOM WALK

 

 

EINFÜHRUNG

 

Im täglichen Leben sind viele Phänomene durch den Zufall bestimmt und du musst oft Entscheide auf der Basis von Wahrscheinlichkeiten fällen, beispielsweise ob du auf Grund einer Unfallwahrscheinlichkeit das eine oder andere Verkehrsmittel wählst. Der Computer kann in solchen Situationen ein wichtiges Hilfsmittel sein, dann mit ihm kannst du das Gefahrenpotential als Simulation untersuchen, ohne selbst gefährdet zu werden.

Im Folgenden gehst du davon aus, dass du dich verirrt hast und den Heimweg nicht kennst. Dabei betrachtest du eine Bewegung, Random Walk oder Irrfahrt genannt, die in einzelnen Zeitschritten erfolgt, wobei die Schritte in zufälliger Richtung gewählt werden. Obschon eine solche Bewegung nicht genau der Realität entspricht, lernst du wichtige Eigenschaften kennen, die sich nachher auf reale Systeme, beispielsweise in der Finanzmathematik zur Modellierung von Aktienkursen oder auf die Brownsche Molekularbewegung, anwenden lassen.

PROGRAMMIERKONZEPTE: Random Walk, Brownsche Bewegung

 

 

EINDIMENSIONALER RANDOM WALK
 

Wiederum eignet sich die Turtlegrafik hervorragend, um die Simulation grafisch zu untermalen. Die Turtle soll sich zur Zeit 0 an der Stelle x = 0 befinden und sich  mit gleich langen Schritten auf der x-Achse bewegen. Zu jedem Zeitschritt "überlegt" sie, ob sie einen Rechts- oder Linksschritt macht. In deinem Programm fällt sie den Entscheid mit der gleichen Wahrscheinlichkeit p = ½. (symmetrischer Random Walk).


 

 

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")
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

MEMO
 

Es erstaunt dich sicher, dass sich in den meisten Fällen die Turtle mit der Zeit vom Startpunkt wegbewegt, obschon sie bei jedem Schritt mit gleicher Wahrscheinlichkeit einen Rechts- oder Linksschritt macht. Allerdings kann sie sich dabei nach rechts oder links wegbewegen. Um dieses wichtige Ergebnis genauer zu untersuchen, bestimmst du im nächsten Programm für je 1000 Laufversuche den Mittelwert d der Distanz vom Startpunkt nach t Schritten.

 

 

DAS WURZEL-AUS-T-GESETZ
 

Du führst die Simulation für eine bestimmte feste Schrittzahl t an fester y-Position 1000 Mal durch und zeichnest die Endposition als Punkt ein. Damit du nicht zu lange auf die Resultate warten musst, versteckst du die Turtle und zeichnest auch keine Spuren. Bei jedem Simulationsversuch bestimmst du den  Abstand r der Endposition vom Startpunkt. Für jede Versuchsreihe mit einen bestimmten t ergibt sich so der Mittelwert d der Abtände r, den du  in einer GPanel-Grafik einträgst.

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")
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

 

MEMO
 

Wie du in der grafischen Darstellung siehst, nimmt der Mittelwert der Distanz zum Startpunkt mit zunehmender Schrittzahl bzw. Zeit t zu. In der Konsole berechnest du noch den Quotienten q = d / sqrt(t). Da dieser nahezu konstant ist, liegt die Vermutung nahe, dass d = q * sqrt(t) exakt gilt, oder:

Die mittlere Distanz zum Startpunkt nimmt mit der Wurzel aus der Zeit zu.

 

 

DRUNKEN MAN'S WALK
 

Noch etwas spannender wird es, wenn sich die Turtle in zwei Dimensionen bewegen kann. Man spricht dann von einem zweidimensionalen Random Walk. Dabei macht die Turtle immer noch gleich lange Schritte, wählt aber bei jedem Schritt eine zufällige Richtung.

Mathematiker und Physiker  kleiden das Problem oft in folgende nicht allzu erstzunehmende Geschichte ein.

"Ein Betrunkener versucht nach einer Wirtshaustour nach Hause zurückzukehren. Da er die Orientierung verloren hat macht er dabei immer einen Schritt in zufälliger Richtung. Wie weit bewegt er sich dabei (im Mittel) vom Wirtshaus weg?

Du brauchst das vorhergehende Programm nur leicht abzuändern. Dabei untersuchst du wieder, wie der Mittelwert der Distanz von der Zeit abhängt.


   

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")
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

MEMO
 

Auch in zwei Dimensionen gilt das Wurzel-aus-t-Gesetz. Für Gasteilchen hat kein geringerer als Albert Einstein diese Gesetzmässigkeit 1905 in seiner berühmten Abhandlung "Über die von der molekularkinetischen Theorie der Wärme geforderte Bewegung von in ruhenden Flüssigkeiten suspendierten Teilchen" bewiesen und damit eine theoretische Erklärung für die Brownsche Bewegung gegeben. Ein Jahr später hat M. Smoluchowski mit einer anderen Überlegung dasselbe Resultat gefunden.

 

 

BROWNSCHE BEWEGUNG
 

Bereits 1827 hatte der Biologe Robert Brown beim Mikroskopieren beobachtet, dass Pollenkörner in einem Wassertropfen unregelmässige zuckende Bewegungen machen. Er vermutete als Ursache eine in den Pollen innewohnende Lebenskraft. Erst mit der Entdeckung der molekularen Struktur der Materie wurde klar, dass die thermische Bewegung der Wassermoleküle, die mit dem Pollen zusammenstossen, für das Phänomen verantwortlich ist.

Die Brownsche Bewegung lässt sich sehr schön in einem Computerexperiment demonstrieren, wo die Moleküle als kleine Kugeln modelliert werden, die beim Zusammenstoss ihre Geschwindigkeit austauschen. Mit JGameGrid lässt sich die Simulation einfach realisieren, da du eine Teilchenkollision als Ereignis auffassen kannst. Dazu leitest du die Klasse CollisionListener von GGActorCollisionListener ab und implementierst den Callback collide(). Jedem Partikel fügst du mit addActorCollisionListener() den Listener hinzu. Die Art und die Grösse der Kollisionsarea kannst du mit setCollisionCircle() einstellen. Du teilst die 40 Teilchen zu Beginn in 4 Geschwindigkeitsgruppen ein.



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()
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

MEMO
 

Die Moleküle sind in der Klasse Particle modelliert, die von Actor abgeleitet ist. Sie haben zwei Spritebilder, ein rotes und ein grünes für ein besonders ausgezeichnetes Molekül, dessen Bahn du verfolgst. Das grüne Bild entspricht der Sprite-ID = 1, auf die du in act() testest, um mit drawLine() die Spur zu zeichnen.

 

 

AUFGABEN
 

1.


Bei einem eindimensionalen Random Walk mit 100 Schritten bewegt sich die Person ausgehend von x = 0 mit gleicher Wahrscheinlichkeit p = ½ nach rechts und q = ½ nach links. Führe die Simulation 10000 mal aus und bestimme die Häufigkeitsverteilung der Endposition. Stelle sie in einem GPanel dar.


2.


Wie du in Aufgabe 1 siehst, ist die Wahrscheinlichkeit, sich nach hundert Schritten wieder am Startpunkt zu befinden, am grössten. Wie lässt sich dies mit dem Wurzel-aus-t-Gesetz vereinbaren?

3.


Führe die gleiche Simulation durch, wenn die Wahrscheinlichkeit für einen Rechtschritt p = 0.8 und für einen Linksschritt q = 0.2 ist.

4*.


Die Theorie liefert beim eindimensionalen Random Walk eine Binomialverteilung. Die Wahrscheinlichkeit, sich nach n Schritten an der Koordinate x zu befinden, beträgt für gerade n und x:

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

Trage den theoretischen Verlauf als Kurve in das Histogramm aus Aufgabe 1 ein.