Random walks: als een groep dronken studenten door de straten

01 juni 2021

Wiskundige Oliver Nagy kan zich nog levendig herinneren dat hij voor het eerst leerde over ‘random walks’. ‘De docent liet ons denken aan een groep dronken studenten die door de straten dwaalden. Bij elk kruispunt draaien ze één van hen in de rondte en gaan ze in de richting waar diegene tot stilstand komt.’ In zijn blog op The Network Pages treedt de lezer in de voetstappen van deze benevelde vrienden.

Een hoop processen in het dagelijks leven, lijken op zo’n random walk, ook wel dronkemanswandeling genoemd. Daarom zijn er veel wiskundigen die ze bestuderen. Nagy: ‘Door modellen te maken van dit soort wandelingen, kunnen we bijvoorbeeld onderzoek doen naar de aandelenkoersen, bewegende pollendeeltjes in de lucht of kansspelen.’

Verdwenen studenten

Nagy onderzoekt bijvoorbeeld hoe lang het duurt voordat je een dronken groep studenten écht kwijt bent. ‘Als de groep net uit de kroeg vertrokken is, en rondom die kroeg zijn drie kruispunten, heb je op elk van die drie kruispunten een kans van 1/3 om ze daar te vinden. Maar als je te lang wacht, kunnen ze overal in de stad zijn. Het maakt dan zelfs niet meer uit dat het beginpunt bekend is: we zijn ze kwijt.’

Wiskundigen spreken in dat geval van het bereiken van de stationaire verdeling. De periode waarin de verdeling steeds meer op de stationaire verdeling begint te lijken, heet de mixing time. ‘Deze mixing time is bijvoorbeeld belangrijk voor natuurkunde, cryptografie en ook het schudden van een spel kaarten’, legt Nagy uit. ‘Hoeveel schudbeweging zijn er nodig voordat je een echt willekeurig deck hebt?’

Verdeling van de random walk aan het begin van de wandeling en vervolgens na één, twee en veel te veel stappen. De rode cirkel geeft de startpositie aan. Blauwe stippen stellen de kruispunten voor waar de wandelaar terecht kan komen en de getallen ernaast geven de kans weer dat de wandelaar zich daar bevindt. In de laatste figuur zijn de kansen evenredig met het aantal straten dat verbonden is met een bepaald kruispunt. De verschillende waarschijnlijkheden in deze eindfiguur zijn met kleuren gecodeerd. Credits: Oliver Nagy

Veranderende straten

Over mixing time is echter al een hoop gezegd en geschreven. Nagy gaat nog een stapje verder: hij kijkt wat er gebeurt met onze dronken vriendengroep als de straten beginnen te veranderen! Denk hierbij aan de trappen in Zweinstein, de school van Harry Potter. De straten bewegen en komen plots uit op een ander kruispunt. Wat doet dit met de mixing time? Duurt het langer of juist korter voordat we onze vriendengroep kwijtraken?

Dat legt Nagy uit in zijn blogpost op The Network Pages - Stumbling around in a changing world

The Network Pages is een website met informatie en infotainment over de wetenschap achter netwerken: network science. Dit project is geïnitieerd door leden en partners van de NWO Gravitatiebeurs NETWORKS, maar iedereen die graag wil bijdragen is welkom.