random walk

Random walk er i sandsynlighedsregning en stokastisk proces der beskriver bevægelsen af et punkt i et en- eller flerdimensionalt rum. Punktet kan i hvert trin bevæge sig en tilfældig afstand i en tilfældig retning, hvor afstand og retning har en given sandsynlighedsfordeling. Betegnelsen random walk skyldes Karl Pearson (1905). Vigtige problemer er bl.a. at undersøge, om punktet vender tilbage til sit udgangspunkt, og hvor lang tid det i givet fald tager.

Den præcise definition på en endimensional random walk \(S_n\) er \(S_0 = 0\) og for \(n \geq 1 \ S_n = X_1 + \dots + X_n\), hvor de tilfældige tal \(X_k\) alle har samme fordeling og er indbyrdes stokastisk uafhængige. Hvis \(X_k\) kun antager værdierne \(\pm 1\), kan \(S_n\) fortolkes som nettogevinsten efter \(n\) spil, hvor man i hvert spil kan vinde eller tabe \(1\) enhed. Er sandsynligheden for gevinst i ét spil \(p\), svarer det til, at punktet i hvert trin med sandsynligheden \(p\) går \(1\) til højre og med sandsynligheden \(1-p\) går \(1\) til venstre.

En random walk er en Markov-kæde der i eksemplet er rekurrent (dvs. vender tilbage til et givent sted med sandsynligheden \(1\)), hvis \(p = \frac{1}{2}\), og ellers er transient.

De første problemer i teorien for random walks løstes i en korrespondence mellem Pascal og Fermat, der studerede hasardspil. De var specielt interesserede i den forventede nettogevinst \(S_t\) efter et tilfældigt antal \(t\) af spil. Ca. 1950 blev det bl.a. påvist, hvorledes Wienerprocessen kan konstrueres ved grænseovergang fra random walks.