Stap voor willekeurige stap: de randomwalk-modellen verkennen

In mijn eerste statistiekcursus op de universiteit, waarin we ook codeerden, stelde mijn docent een vraag: hoe kunnen we de Brownse beweging van één pollenkorrel in een schaaltje water modelleren? Na een paar mislukte pogingen kwamen mijn klasgenoten en ik uiteindelijk op het juiste antwoord uit: een random walk. Later leerde ik dat dit eenvoudige model voor van alles wordt gebruikt, van dierbewegingen tot schommelingen in aandelenkoersen.

In dit artikel verkennen we de wiskundige basis van random walks, bekijken we verschillende typen en bespreken we hun toepassingen. Wat de random walk zo interessant maakt, is dat hij in zoveel verschillende disciplines wordt gebruikt. Naast mijn voorbeeld helpt hij in de natuurkunde om de beweging van deeltjes te beschrijven; in de financiële wereld modelleert hij schommelingen in aandelenkoersen; en in de biologie verklaart hij bewegingspatronen van dieren. Random walks vangen de willekeur van de echte wereld, wat essentieel is voor het simuleren van stochastische processen.

Voor wie een stevige basis wil leggen in de statistiek achter de randomwalk-theorie, raden we aan te beginnen met de cursus Introduction to Statistics in R of de cursus Introduction to Statistics in Python.

Wat zijn random walks?

In de kansrekening is een random walk een model dat een reeks willekeurige stappen beschrijft die samen een pad vormen. Of anders gezegd: een random walk is een wiskundig model dat een pad beschrijft dat wordt gevormd door een reeks stappen, elk onafhankelijk en met een bepaalde kans bepaald. Deze stochastiek maakt random walks van nature onvoorspelbaar.

Stel je iemand voor die op elk moment een stap in een willekeurige richting zet. Na verloop van tijd vormt zijn of haar pad een onvoorspelbaar, kronkelig spoor. Ondanks de eenvoud heeft dit concept verrassende diepgang en veelzijdigheid, en modelleert het allerlei realistische scenario’s waarin willekeur voorkomt.

Een conceptuele uitleg van een random walk. Afbeelding met dank aan napkin.ai.

Het idee van random walks gaat terug tot de vroege kansrekening. Een van de bekendste voorbeelden, vaak de dronkemanswandeling genoemd, laat zien dat iemand die willekeurig stappen zet grillig ronddwaalt in plaats van voorspelbaar naar een bestemming te bewegen. Deze willekeur, gecombineerd met de aanname dat elke stap onafhankelijk is van eerdere, legde de basis voor moderne randomwalk-modellen.

De wiskunde achter random walks begrijpen

Om random walks te begrijpen, beginnen we met een eenvoudig geval: een eendimensionale (1D) random walk. Stel je een deeltje op een getallenlijn voor. Het kan bij elke stap +1 of -1 bewegen langs de lijn. Elke beweging wordt bepaald door een gelijke kans op een stap naar rechts of naar links. Na verloop van tijd vormt de positie van het deeltje een kansverdeling die uitwaaiert, wat de kans weergeeft om het op verschillende posities aan te treffen.

Dit principe kan worden uitgebreid naar twee of drie dimensies. In een tweedimensionale (2D) random walk beweegt het deeltje in een vlak en kan het met gelijke kans in een van de vier hoofdrichtingen (omhoog, omlaag, links, rechts) stappen. Evenzo beweegt het deeltje in een driedimensionale (3D) random walk in de ruimte en kan het met gelijke kans in een van de zes richtingen (omhoog, omlaag, links, rechts, vooruit, achteruit) stappen. Deze random walks in hogere dimensies vangen nog complexere en realistischer scenario’s.

Een kenmerkend aspect van random walks is hun stochastische aard: elke stap hangt alleen af van de huidige positie en niet van eerdere stappen. Daarmee zijn het een type Markov-proces—een wiskundig concept waarbij de toekomstige toestand uitsluitend afhangt van de huidige toestand, niet van de voorafgaande gebeurtenissen. Deze “geheugenloze” beweging, gecombineerd met kansverdelingen die mogelijke posities beschrijven, biedt een solide wiskundige basis om random walks te begrijpen.

We kunnen een random walk analyseren met statistische eigenschappen om het gedrag in de tijd te begrijpen. Daarbij kijken we naar zaken als de verwachte afstand tot het startpunt, de kansverdeling van mogelijke posities en de kans om naar de oorsprong terug te keren. Deze analyses helpen ons willekeur en voorspelbaarheid te kwantificeren, geven inzicht in patronen en ondersteunen voorspellingen.

Belangrijke eigenschappen van random walks

Random walks hebben een aantal belangrijke eigenschappen die helpen hun gedrag en toepassingen te begrijpen. Dit zijn enkele kernpunten om te overwegen:

Verwachting en variantie

In een eendimensionale random walk kunnen we de verwachte afstand (of gemiddelde positie) tot het startpunt in de tijd berekenen. Als elke stap evenveel kans heeft om naar links of rechts te gaan, blijft de verwachte positie na veel stappen nul, wat impliceert dat de wandelaar gemiddeld in de buurt van het startpunt blijft.

De variantie van de positie, die de spreiding van mogelijke posities meet, neemt echter toe bij elke stap. Specifiek groeit in een symmetrische random walk de variantie lineair met het aantal stappen, waardoor dit een nuttige indicator is voor de typische afstand tot de oorsprong in de tijd.

Autocorrelatie

Hoewel eenvoudige random walks geen correlatie tussen stappen hebben (elke stap is onafhankelijk van de vorige), introduceren bepaalde typen random walks autocorrelatie, waarbij eerdere stappen toekomstige beïnvloeden. In een gewaarde (biased) random walk is er bijvoorbeeld een lichte neiging in één richting, waardoor posities voorspelbaarder worden.

Autocorrelatie in een random walk beïnvloedt hoe we de voortgang modelleren en voorspellen. Dit is vooral relevant in toepassingen waar gedrag uit het verleden toekomstige stappen beïnvloedt, zoals in bepaalde financiële modellen.

Centrale limietstelling

De centrale limietstelling (CLT) vertelt ons dat de som van een groot aantal onafhankelijke willekeurige variabelen de neiging heeft een normale (of Gaussische) verdeling te volgen, ongeacht de oorspronkelijke verdeling. In de context van random walks betekent dit dat naarmate het aantal stappen toeneemt, de verdeling van posities op een normale verdeling gaat lijken. Dit is handig omdat we zo de kans kunnen benaderen om de wandelaar op bepaalde afstanden van het startpunt aan te treffen.

Wet van de grote aantallen

De wet van de grote aantallen (LLN) legt uit dat naarmate het aantal proeven of stappen toeneemt, het gemiddelde van de uitkomsten naar het werkelijke gemiddelde convergeert. Voor random walks betekent dit dat hoewel de gemiddelde positie nul blijft, de variantie en de bandbreedte van mogelijke posities voorspelbaar toenemen met elke extra stap. Dit principe slaat een brug tussen pure willekeur en voorspelbare statistische patronen in grote steekproeven.

Typen random walks

Random walks variëren sterk afhankelijk van de regels die elke stap aansturen. Deze typen beïnvloeden hoe de wandeling zich gedraagt. Sommige zijn ontworpen voor eenvoudige of gestructureerde omgevingen, terwijl andere geschikt zijn voor complexere, realistische fenomenen. Laten we een paar van de meest voorkomende typen random walks bekijken.

1D-, 2D- en 3D-random walks

De dimensionaliteit van een random walk speelt een fundamentele rol in het gedrag. In een 1D-random walk is elke stap een beweging vooruit of achteruit langs een lijn. Dit maakt het model relatief eenvoudig te modelleren en te voorspellen.

Maar bij 2D- (vlak) en 3D- (ruimte) wandelingen neemt het aantal mogelijke paden sterk toe, wat nieuw gedrag introduceert. Zo blijft in een 2D-random walk de kans om naar het startpunt terug te keren hoog, terwijl die kans in 3D afneemt.

Die verandering is belangrijk in vakgebieden als natuurkunde en scheikunde, waar deeltjes anders kunnen diffunderen afhankelijk van dimensionale beperkingen.

Rooster- (lattice) random walk

Bij een lattice random walk is de beweging beperkt tot discrete punten op een rooster. Dit type wordt veel gebruikt in de natuurkunde en netwerktheorie, waar knooppunten in een rooster zijn gerangschikt en beweging alleen naar naburige knooppunten kan plaatsvinden.

Een veelvoorkomend voorbeeld is een 2D-rooster, waar elke stap beweging naar aangrenzende punten op een Cartesisch rooster toestaat. Deze beperking vereenvoudigt het modelleren door de bewegingspaden te beperken, wat nuttig is bij het simuleren van complexe netwerken of moleculaire structuren.

Gaussiaanse random walk

In een Gaussiaanse random walk wordt de stapgrootte bepaald door een Gaussische (of normale) verdeling. In plaats van een vaste afstand te bewegen, varieert de stapgrootte volgens een klokvormige verdeling, met meestal kleine stappen en af en toe grotere sprongen. Dit type wordt vaak gebruikt in financiële modellen om de variabiliteit in veranderingen van activaprijzen te verklaren.

Heterogene en gewaarde random walks

Heterogene en gewaarde random walks laten variatie toe in staprichting en -grootte op basis van bepaalde kansen. Deze flexibiliteit maakt ze beter toepasbaar op realistische scenario’s.

In een heterogene random walk kan de kans om een bepaalde kant op te gaan veranderen afhankelijk van locatie of externe omstandigheden. Dieren die foerageren, kunnen bijvoorbeeld gebieden met bekende bronnen verkiezen, wat een gewaarde random walk oplevert. Deze wandelingen zijn nuttig om gedrag te bestuderen dat afhangt van contextuele factoren.

Random walk met drift

In een random walk met drift is er een consistente neiging om in één richting te bewegen. Aandelenkoersen vertonen bijvoorbeeld vaak een algemene opwaartse trend in de tijd ondanks dagelijkse schommelingen. De drift in deze wandelingen staat voor een externe kracht of trend die het pad beïnvloedt. Dit type zie je vaak in finance, waar modellen een driftterm opnemen om groei of krimp te representeren, wat een realistischer aanpak biedt voor het voorspellen van activaprijzen en markttrends.

Elk van deze typen random walk heeft een eigen doel en biedt verschillende manieren om willekeurig, maar toch gestructureerd gedrag te modelleren. De dimensionale beperkingen, de verdeling van stappen en de aanwezigheid van drift of bias maken random walks uiterst veelzijdig voor datamodellering en simulatie in uiteenlopende vakgebieden.

Toepassingen van random walks in de echte wereld

Random walks zijn meer dan louter theoretische constructies; ze spelen een essentiële rol in veel praktische toepassingen over verschillende disciplines. Laten we bekijken hoe random walks bijdragen aan het oplossen van echte problemen in diverse sectoren.

Toepassingen in data science en machine learning

Informatica

Random walks liggen ten grondslag aan verschillende algoritmen in de informatica, zoals willekeurig sampelen, webgraaf-traversal en beeldsegmentatie. Zo gebruikte Google’s PageRank-algoritme random walks om webpagina’s te rangschikken op relevantie, door te simuleren hoe een gebruiker willekeurig tussen links op internet navigeert.

Feature-extractie

In machine learning kunnen random walks helpen bij het extraheren van features door relaties binnen datapunten te benadrukken. In netwerkanalyse kunnen random walks bijvoorbeeld clusters of gemeenschappen blootleggen, wat helpt bij taken zoals aanbevelingssystemen en sociale-netwerkanalyse.

Anomaliedetectie

Random walks kunnen ook worden gebruikt om anomalieën in datasets op te sporen. Als datapunten bijvoorbeeld sterk afwijken van een typisch pad in een randomwalk-model, kunnen die punten duiden op ongewone gebeurtenissen of fouten in de data. Anomaliedetectie is vooral waardevol in bijvoorbeeld cybersecurity en fraudedetectie.

Stochastische processen simuleren

Random walks simuleren stochastische, of willekeurig bepaalde, processen, waardoor data scientists onvoorspelbare fenomenen uit de echte wereld kunnen modelleren. Door random walks te simuleren, krijgen we inzicht in systemen waar exacte voorspelling lastig is, zoals weerspatronen of klantgedrag.

Tijdreeksvoorspelling

In tijdreeksanalyse vormen random walks de basis voor bepaalde voorspellingsmodellen, waaronder de randomwalk-hypothese in finance. Deze modellen gaan ervan uit dat toekomstige waarden in een tijdreeks uitsluitend afhangen van de meest recente waarde, zonder correlatie met eerdere trends. Voor meer over tijdreeksvoorspelling, bekijk ARIMA for Time Series Forecasting: A Complete Guide. Volg ook onze cursus Forecasting in R met professor Hyndman, die randomwalk-modellen verbindt met naïeve en seizoensnaïeve voorspelmethoden.

Toepassingen in andere vakgebieden

Financiën

Een van de bekendste toepassingen van random walks is in financiële modellering, vooral voor het voorspellen van aandelenkoersen. De efficiënte-markthypothese suggereert dat koersbewegingen in wezen willekeurig zijn, omdat nieuwe informatie onmiddellijk wordt verwerkt, waardoor toekomstige prijzen onvoorspelbaar worden. Random walks kunnen worden gebruikt om koersveranderingen in de tijd te modelleren en te laten zien hoe prijzen fluctueren zonder voorspelbaar pad.

Wiskunde

In de zuivere wiskunde bieden random walks oplossingen voor complexe problemen. Ze zijn bijvoorbeeld nuttig bij het oplossen van de vergelijking van Laplace, het analyseren van netwerken en het verkennen van combinatoriek.

Natuurkunde en scheikunde

In de bètawetenschappen zijn random walks cruciaal voor het modelleren van diffusieprocessen, zoals hoe moleculen zich door een medium verspreiden. Brownse beweging, waarbij deeltjes in een vloeistof onvoorspelbaar bewegen door botsingen met omliggende moleculen, is een klassiek voorbeeld dat nauwkeurig kan worden gesimuleerd met random walks. Zo heb ik zelf voor het eerst over random walks geleerd.

Biologie

Random walks zijn waardevol in de ecologie om bewegingspatronen van dieren te bestuderen. Dieren die foerageren lijken soms volgens een random walk te bewegen, soms met een bias richting gebieden met bekende bronnen. Andere biologische concepten, zoals verspreiding van populaties of genen, kunnen vaak met randomwalk-principes worden gemodelleerd, wat helpt bij het begrijpen en voorspellen van veranderingen in ecosystemen.

Speciale gevallen en varianten van random walks

Naast de klassieke random walk zijn er geavanceerde varianten die het concept uitbreiden voor gespecialiseerde toepassingen.

Zelfmijdende (self-avoiding) walks

Een zelfmijdende wandeling is een random walk waarbij het pad geen positie opnieuw bezoekt die al is gepasseerd. Deze variant is bijzonder nuttig in bijvoorbeeld polymeerchemie, waar hij kan modelleren hoe polymeerketens zich vormen zonder zichzelf te kruisen. Omdat elke stap eerder bezochte punten vermijdt, is dit type meer beperkt dan traditionele random walks. Daardoor zijn ze computationeel uitdagend, maar nuttig om niet-overlappende paden in beperkte ruimtes te begrijpen.

Vertakkend (branching)

Bij vertakkende random walks kan het pad zich opsplitsen in meerdere takken, waarbij elke tak een eigen random walk volgt. Dit type is belangrijk voor het modelleren van vertakkingsprocessen zoals celdeling of de verspreiding van informatie door netwerken. Elke “tak” vertegenwoordigt een onafhankelijk willekeurig pad dat uit een gemeenschappelijke bron voortkomt.

Gecorreleerde walks

Gecorreleerde wandelingen gaan een stap verder: de richting van elke stap wordt deels beïnvloed door de vorige. Deze variant is nuttig om traagheid te modelleren in systemen waar veranderingen geleidelijk in plaats van volledig willekeurig plaatsvinden. Gecorreleerde walks worden vaak toegepast in finance om prijstrends te simuleren of in movement ecology om te begrijpen hoe dieren zich voortbewegen met enig geheugen van hun vorige richting.

Loop-erased walks

Een loop-erased walk is een variant waarbij lussen—paden die zichzelf kruisen—worden verwijderd zodra ze ontstaan. Elke keer dat een stap een positie opnieuw bezoekt, wordt de tussenliggende lus gewist, waardoor een gestroomlijnd, niet-herhalend pad overblijft. Loop-erased walks worden vaak toegepast in netwerkanalyse en algoritmen voor doolhofgeneratie, omdat ze paden creëren die redundantie vermijden.

Random walks implementeren in Python

Laten we een random walk in Python implementeren. Zorg ervoor dat je Python geïnstalleerd hebt (we gebruiken Python 3.10) en dat de benodigde libraries beschikbaar zijn. Je kunt ontbrekende libraries installeren met pip. Dit gebruiken we:

import numpy as np # for numerical operations and generating random steps
import matplotlib.pyplot as plt # for plotting and visualizing the random walks

1D-random walk

We beginnen met een eenvoudige eendimensionale random walk, waarbij elke stap of +1 of -1 is, willekeurig gekozen.

# Parameters
n_steps = 100  # Number of steps

# Generate random steps: +1 or -1
steps = np.random.choice([-1, 1], size=n_steps)

# Calculate positions
positions = np.cumsum(steps)

# Plot the random walk
plt.figure(figsize=(10, 6))
plt.plot(positions, marker='o', linestyle='-', markersize=4)
plt.title("1D Random Walk")
plt.xlabel("Step")
plt.ylabel("Position")
plt.grid(True)
plt.show()

Dit genereert een eenvoudige random walk en visualiseert de voortgang in de tijd. Dit is de output wanneer ik deze code uitvoer:

Onthoud: we draaien een stochastisch model. Dat betekent dat de output er elke keer dat je het uitvoert iets anders uitziet.

2D-random walk

Laten we de random walk nu uitbreiden naar twee dimensies. Bij elke stap wordt de richting willekeurig gekozen.

# Parameters
n_steps = 500

# Generate random steps in x and y directions
x_steps = np.random.choice([-1, 1], size=n_steps)
y_steps = np.random.choice([-1, 1], size=n_steps)

# Calculate positions
x_positions = np.cumsum(x_steps)
y_positions = np.cumsum(y_steps)

# Plot the 2D random walk
plt.figure(figsize=(8, 8))
plt.plot(x_positions, y_positions, marker='o', linestyle='-', markersize=2, label='Random Walk')
plt.plot(x_positions[0], y_positions[0], 'ro', markersize=8, label='Start')  # Red dot for start
plt.plot(x_positions[-1], y_positions[-1], 'ko', markersize=8, label='End')  # Black dot for end
plt.title("2D Random Walk")
plt.xlabel("X Position")
plt.ylabel("Y Position")
plt.grid(True)
plt.axis('equal')  # Ensures equal scaling for both axes
plt.legend()
plt.show()

Deze code creëert een visueel aansprekend pad in twee dimensies.

Dit type tweedimensionale random walk kun je aanpassen voor toepassingen als deeltjesbeweging of ruimtelijke modellering.

Gewaarde random walk

Tot slot bekijken we een iets complexer voorbeeld: een gewaarde random walk. Om bias te introduceren, passen we de kansen per staprichting aan. We kunnen bijvoorbeeld opwaartse stappen waarschijnlijker maken.

# Parameters
n_steps = 100
bias = 0.7  # Probability of stepping +1

# Generate biased random steps in x and y directions
x_steps = np.random.choice([-1, 1], size=n_steps, p=[1-bias, bias])
y_steps = np.random.choice([-1, 1], size=n_steps, p=[1-bias, bias])

# Calculate positions
x_positions = np.cumsum(x_steps)
y_positions = np.cumsum(y_steps)

# Plot the biased 2D random walk
plt.figure(figsize=(8, 8))
plt.plot(x_positions, y_positions, marker='o', linestyle='-', markersize=2, label='Random Walk')
plt.plot(x_positions[0], y_positions[0], 'ro', markersize=8, label='Start')  # Red dot for start
plt.plot(x_positions[-1], y_positions[-1], 'ko', markersize=8, label='End')  # Black dot for end
plt.title("Biased 2D Random Walk")
plt.xlabel("X Position")
plt.ylabel("Y Position")
plt.grid(True)
plt.axis('equal')  # Ensures equal scaling for both axes
plt.legend()
plt.show()

Door de bias te veranderen, zie je hoe de wandeling de neiging krijgt een bepaalde richting te kiezen, wat realistische scenario’s simuleert zoals drift in aandelenkoersen of migratiepatronen van dieren.

Als we de bias-parameter wijzigen naar 0,55, zie je een dramatisch verschil in het gedrag van het model. Hoewel er nog steeds een voorkeur is om omhoog te gaan, is die minder sterk, wat leidt tot meer lussen en omwegen.

Conclusie

Random walks zijn een waardevol modelleringsinstrument voor data scientists, toepasbaar van natuurkunde tot finance en verder. Doordat ze complexe, stochastische processen kunnen modelleren, zijn ze onmisbaar in veel realistische scenario’s.

Zin in meer? Bekijk DataCamps aanbod aan cursussen over kansrekening en statistiek. Je vindt allerlei goede cursussen in zowel Python als R. Als je geïnteresseerd bent in meer geavanceerde content, bekijk dan DataCamps cursus Statistical Simulation in Python en de tutorial Introduction to Machine Learning. Of als je je kennis wilt testen, ga dan aan de slag met deze probability puzzles.