random walk

Artikelstart

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 Sn er S0 = 0 og for n ≥ 1 Sn = X1+ ∙∙∙ + Xn, hvor de tilfældige tal Xk alle har samme fordeling og er indbyrdes stokastisk uafhængige. Hvis Xk kun antager værdierne ±1, kan Sn 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 = 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 St 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.

Kommentarer

Din kommentar publiceres her. Redaktionen svarer, når den kan.

Du skal være logget ind for at kommentere.

eller registrer dig