Random Walk

Peter spiller mange spil plat - og - krone med Klavs. Viser mønten plat, får Peter 1 point af Klavs; ellers mister han et til Klavs. Intuitivt forventer vi, at Peter fører ca. halvdelen af tiden, og at stillingen er uafgjort med jævne mellemrum, men...

Emner

• Spillet
• Spejlsætningen
• Arcussinusloven
• Lange føringer
• Stirlings formel
• Beviser

Spillet

Ved hvert spil øges n med 1 og y med ±1, så n + y øges med 0 eller 2. Heraf følger, at n + y altid er et lige tal. Desuden er n ≥ 0 og |y| ≤ n. Alle gitterpunkter (n, y), der opfylder disse 3 betingelser, kan ligge på grafen.

Antallet af veje (kastserier), der fører fra (0, 0) til (n, y), kalder vi N((0, 0) , (n, y)). En sådan vej må indeholde y overskydende p og altså bestå af ½(n + y) plat og ½(n – y) krone; tilsammen n kast. Antallet af veje bliver antallet af måder at vælge ½(n + y) blandt n.

N((0, 0) , (n, y)) = K(n, ½(n+y)).

Er mønten symmetrisk, har alle n - skridtsveje samme sandsynlighed ½ⁿ, så sandsynligheden for at nå fra (0, 0) til (n, y) er

P((0, 0) , (n, y)) = K(n, ½(n+y)) ½ⁿ.

Et tilsvarende argument leder til

N((n₁, y₁) , (n₂, y₂)) = K(n₂–n₁, ½(n₂–n₁+y₂–y₁))
P((n₁, y₁) , (n₂, y₂)) = K(n₂–n₁, ½(n₂–n₁+y₂–y₁)) ½^n₂–n₁.

[ Hovedmenu ] [ Ordliste ]

Spejlsætningen

Har y₁ og y₂ samme fortegn, vil nogle af vejene blandt N((n₁, y₁) , (n₂, y₂)), være uden punkt(er) på 1 - aksen. Det svarer til, at samme spiller fører fra n₁ til n₂. Vi kalder antallet af sådanne veje N_s((n₁, y₁) , (n₂, y₂)). Vi har altså

N_s((n₁, y₁) , (n₂, y₂)) = N((n₁, y₁) , (n₂, y₂)) – N((n₁, –y₁) , (n₂, y₂)) =
K(n₂–n₁, ½(n₂–n₁+y₂–y₁)) – K(n₂–n₁, ½(n₂–n₁+y₂+y₁)).

Blandt de N((0, 0) , (2n, 0)) = K(2n, n) veje, der forbinder to punkter på 1 - aksen, vil N_s((1, 1) , (2n–1, 1)) = K(2n–2, n–1) – K(2n–2, n) = K(2n–2, n–1) / n forløbe over 1 - aksen.

Tænker vi os, at 1 - aksen lå i nivau 1, er K(2n–2, n–1) / n også antallet af 2n – 2 - lange veje, der ligger på eller over den nye 1 - akse. Antallet af 2n - lange veje, hvor Peter ikke kommer bagefter er altså K(2n, n) / (n+1).

I nogle af de 2²ⁿ 2n - skridts veje fra (1, 1) vil Peter føre hele tiden. Dette antal er

Dette resultat kan fortolkes på 2 måder: I halvdelen af disse veje fører Peter 2n skridt fra (0, 0). Vi slutter, at

Der er K(2n, n) 2n - skridts veje fra (0, 0), der ikke vender tilbage til 1 - aksen (y ≠ 0).

Den anden fortolkning: Starter vi med at tælle skridt fra (1, 1), ser vi, at

Der er K(2n, n) 2n - skridts veje fra (0, 0), hvor Peter ikke er bagefter (y ≥ 0).

[ Hovedmenu ] [ Ordliste ]

Arcussinusloven

Vi søger antallet N(2n, 2k) af veje blandt 2n - skridtsvejene fra (0, 0), hvor Peter fører i 2k af skridtene. (Vi siger, at Peter fører i et skridt, hvis y > 0 ved enten starten eller slutningen eller begge af skridtet). Vi giver et lidt tyndt argument for, at N(2n, 2k) = K(2k, k) K(2n–2k, n–k).

Antallet K(2k, k) K(2n–2k, n–k) vil vi opfatte som produktet N(samtlige 2k - veje fra 1 - aksen, hvor Peter fører) · N(samtlige 2n–2k - veje fra 1 - aksen, hvor Klavs fører).

Er k = n eller k = 0, følger af anden fortolkning ovenfor, at antallet er K(2k, k) K(2n–2k, n–k).

Vi ser nu på 1 ≤ k ≤ n–1, hvor en vej mindst ét sted krydser 1 - aksen. Lad det ske efter 2r, 2s, 2t, ... skridt. Antallet af mulige veje er produktet af antallet af vejstumper N((0, 0), (2r, 0)) · N((2r, 0), (2s, 0)) · N((2s, 0), (2t, 0)) · ... · N((2u, 0), (2v, y)). I nogle af disse veje fører Peter; i andre Klavs. Sorterer vi produktet i de faktorer, hvor Peter fører for sig, bestå det af antallet af 2k - lange veje fra 1 - aksen, hvor Peter fører. Resten af produktet svarer til antallet af 2n-2k - lange veje fra 1 - aksen, hvor Klavs fører.

Herefter tror vi på , at der blandt 2n - skridtsvejene fra (0, 0) er K(2k, k) K(2n–2k, n–k), hvor Peter ikke er bagefter i 2k af skridtene.

Vi benytter grænsesætningen K(2n, n) ½²ⁿ √(πn) → 1   for   n → ∞ og finder frekvensfunktionen

f(k) = K(2k, k) ½2k K(2n–2k, n–k) ½2n–2k ≈

1 π √(k (n–k))

.

Denne frekvensfunktion integeres til fordelingsfunktionen

F(k) =

∫

k 0

f(k) dk =

∫

k 0

dk π √(k (n–k))

= ½ –

1 π

sin–1(

n – 2k n

) eller med k = a n

F(a) =

1 2

–

1 π

sin–1(1 – 2a) .

[ Hovedmenu ] [ Ordliste ]

Lange føringer

Vi vender tilbage til resultatet:

Blandt de N((0, 0) , (2n, 0)) = K(2n, n) veje, der forbinder to punkter på 1 - aksen, vil K(2n–2, n–1) / n forløbe over 1 - aksen.

Det betyder, at sandsynligheden for at møde en "bue" af længde 2n er P(2n) = 2 K(2n–2, n–1) / n ½²ⁿ.

Vi beregner middelværdien af buelængden

μ = Σ2n P(2n) = Σ4 K(2n–2, n–1) ½²ⁿ = Σ K(2n–2, n–1) ½^2n–2, hvor n løber fra 1 til ∞, eller

μ = Σ K(2n, n) ½²ⁿ, hvor n løber fra 0 til ∞. (Det n-te led er netop sandsynligheden for at ramme 1-aksen i det 2n-te skridt.) Summens n-te led K(2n, n) ½²ⁿ er (Her er detailler).

Også dette resultat støder vor intuitive opfattelse af, at spillet med jævne mellemrum er uafgjort. Når middelværdien er "uendelig", må der optræde "uendelig" lange buer, hvor den ene spiller fører.

[ Hovedmenu ] [ Ordliste ]

Stirlings formel

Stirlings formel er en måde at finde tilnærmede værdier for n!. Den siger, at

n! ≈ nne–n

√(2nπ)

for store   n.

Den giver tilnæmede værdier for K(2n, n)

K(2n, n) =

(2n)! n! · n!

≈

(2n)2ne–2n√(4nπ) nne–n√(2nπ) nne–n√(2nπ)

=

22n √(nπ)

for store   n.

[ Hovedmenu ] [ Ordliste ]

Beviser

I følgende integrale anvendes først substitutionen x = sin(t) og derefter delvis integration

[ Hovedmenu ] [ Ordliste ] [ Tilbage til hovedsiden ]