random walk

Random walk, (eng. 'tilfældig gang'), 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 og for n ≥ 1 S_n = X₁+ ∙∙∙ + 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 ±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 (se Markov-proces), der i eksemplet er rekurrent (dvs. vender tilbage til et givent sted med sandsynligheden 1), hvis p = ¹/₂, 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, jf. Littles formel. Ca. 1950 blev det bl.a. påvist, hvorledes Wienerprocessen kan konstrueres ved grænseovergang fra random walks.