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

Beklager; din browser kan ikke vise applets!

Vi holder rede på Peters points spillet igennem v.h.a. et koordinatsystem, hvor spillets nummer n sættes af på 1 - aksen, og Peters points y på 2 - aksen. Grafen er en stykkevis lineær graf, der starter i (n, y) = (0, 0), og hvis stykker har hældningskoefficienter ±1. Eksemplet viser kastserien p, p, k, p, k, k, k.

Tast OK for at se et spil på 4000 kast.

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.

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

Et tilsvarende argument leder til

[ Hovedmenu ] [ Ordliste ]

Spejlsætningen

Beklager; din browser kan ikke vise applets!

Har y1 og y2 samme fortegn, vil nogle af vejene blandt N((n1, y1) , (n2, y2)), (måske) have punkt(er) på 1 - aksen. Dette antal kalder vi N0((n1, y1) , (n2, y2)). Til enhver sådan vej svarer netop n vej fra (n1, –y1) til (n2, y2); og omvendt. Vi slutter, at

    N0((n1, y1) , (n2, y2)) = N((n1, –y1) , (n2, y2)).

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

Blandt de N((0, 0) , (2n, 0)) = K(2n, n) veje, der forbinder to punkter på 1 - aksen, vil Ns((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 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 22n 2n - skridts veje fra (1, 1) vil Peter føre hele tiden. Dette antal er

Ns((1, 1) , (2n+1, 1)) + Ns((1, 1) , (2n+1, 3)) + Ns((1, 1) , (2n+1, 5)) + ... + Ns((1, 1) , (2n+1, 2n+1)) =
K(2n, n) – K(2n, n+1) + K(2n, n+1) – K(2n, n+2) + K(2n, n+2) – K(2n, n+3) + ... + K(2n, 2n) – K(2n, 2n+1) =
K(2n, n).

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

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

Beklager; din browser kan ikke vise applets! Beklager; din browser kan ikke vise applets!

Figuren til venstre (Pascals trekant) viser de punkter, der kan nås i op til 8 skridt. Antallet af veje til et punkt findes ved at addere antallet af veje til de foregående punkter. Der er ialt 28 = 256 forskellige 8 - skridts veje.
Vi ser, at der er K(8, 4) = 70 veje fra (0, 0) til (8, 0).

Figuren til højre viser, at der er 1 + 7 + 20 + 28 + 14 = 70 = K(8, 4) 8 - skridts veje, hvor Peter ikke er bagefter, og 1 + 6 + 14 + 14 = 35 = K(8, 4) 8 - skridts veje, hvor Klavs fører.

[ 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) 2n √(πn) → 1   for   n → ∞ og finder frekvensfunktionen

Denne frekvensfunktion integeres til fordelingsfunktionen

Beklager; din browser kan ikke vise applets!

a er den brøkdel af spillene, hvor Peter ikke er bagefter.

Dette resultat viser, hvor meget vor intuition snyder os. De fleste tror, at Peter og Klavs fører ca 50% af tiden hver. Men det modsatte er tilfældet. F. eks. er der 20% sandsynlighed for, at Peter fører højest 9.5% af tiden.

[ Hovedmenu ] [ Ordliste ]

Lange føringer

Vi vender tilbage til resultatet:

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

Vi beregner middelværdien af buelængden

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

μ = Σ K(2n, n) 2n, 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) 2n er (Her er detailler).

2n·(2n–1)·(2n–2) ... 2·1
(2n·(2n–2)·(2n–4) ... 4·2)2
= (2n–1)·(2n–3) ... 3·1
2n·(2n–2)·(2n–4) ... 4·2
= 2
π
1

0
x2n dx
√(1–x2)
, så
μ = 2
π
1

0
Σx2n dx
√(1–x2)
= 2
π
1

0
x2 dx
(1–x2)3/2
= 2
π
π/2

0
sin2(t) cos(t) dt
cos3(t)
= ∞.

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

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

[ Hovedmenu ] [ Ordliste ]

Beviser

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

1

0
x2n dx
√(1–x2)
= π/2

0
sin2n(t) cos(t) dt
cos(t)
= π/2

0
sin2n(t) dt = π/2

0
sin(t) sin2n–1(t) dt =
[ –cos(t) sin2n–1(t) ] π/2

0
+ π/2

0
cos(t) (2n–1) sin2n–2(t) cos(t) dt =
(2n–1) π/2

0
sin2n–2(t) (1–sin2(t) dt = (2n–1) π/2

0
sin2n–2(t) dt – (2n–1) π/2

0
sin2n(t) dt .
Heraf ses, at 2n π/2

0
sin2n(t) dt = (2n–1) π/2

0
sin2n–2(t) dt , eller
π/2

0
sin2n(t) dt = 2n–1
2n
π/2

0
sin2n–2(t) dt = (2n–1)·(2n–3) ... 3·1
2n·(2n–2)·(2n–4) ... 4·2
π/2

0
sin0(t) dt =
(2n–1)·(2n–3) ... 3·1
2n·(2n–2)·(2n–4) ... 4·2
π
2
.
Desuden ved vi fra kvotientrækker, at
Σ
n=1
xn = x
1 – x
, eller
Σ
n=1
x2n = x2
1 – x2
.

[ Hovedmenu ] [ Ordliste ] [ Tilbage til hovedsiden ]