Egyszerű véletlen bolyongás

Tételezzük fel, hogy

X X 1 X 2

független valószínűségi változóknak egy sorozata, mindegyikük 1 és

1

érétket vesz fel

p

és

1 p

valószínűséggel. Ebben a fejezetben tanulmányozni fogjuk az

X

-szel kapcsolatos

Y Y 0 Y 1 Y 2

részletösszeg folyamatot. Így

Y

sorozat egy

p

paraméterű, véletlen egyszerű bolyongás. Minden lépésnél a véletlen gyalogos (bolyongó) vagy jobbra megy egy egységet

p

valószínűséggel, vagy balra egy egységet

1 p

valószínűséggel. A sétáló ezt úgy valósítja meg, hogy egy (szabálytalan) pénzérmét feldob, amelyik

p

valószínűséggel esik fejre, ebben az esetben jobbra, ha írásra esik balra lép. A véletlen bolyongás más típusait a Markov láncok fejezetében tanulmányozzuk.

Jelölje $μ$ és $σ$ $X$ egy lépésének várható értékét és szórását Mutassuk meg, hogy

$μ 2 p 1$
$σ 2 4 p 1 p$

Legyen $I j 1 2 X j 1$ $j$ -ra. Mutassuk meg, hogy $I j 1$ ha $X j 1$ és $I j 0$ ha $X j 1$ .

Ennélfogva

I I 1 I 2

Bernoulli kísérleteknek egy sorozata . A véletlen bolyongással kapcsolatban

I j

az indikátor változója annak az eseménynek, hogy az

i

-edik lépés jobbra történik.

Legyen $Z n j 1 n I j$ $n$ -re.

Mutassuk meg, hogy $Y n 2 Z n n$ $n$ -re!
Mutassuk meg, hogy $Z n$ binomiális eloszlású $n$ és $p$ paraméterekkel!

A bolyongással kapcsolatban

Z n

az első

n

lépésben a jobbralépések száma.

Felhasználva az előző gyakorlat eredményeit mutassuk meg, hogy $Y n$ sűrűségfüggvénye

Y n k n n k 2 p n k 2 1 p n k 2, k n n 2 n 2 n!

Mutassuk meg, hogy

$Y n n 2 p 1!$
$Y n 4 n p 1 p$ !

A szimmetrikus egyszerű bolyongás

Tételezzük fel, hogy

p 1 2

. Ebben az esetben

Y Y 0 Y 1

vektorváltozót szimmetrikus, egyszerű bolyongásnak nevezzük. A szimmetrikus egyszerű bolyongást speciális és ügyes kombinatorikai okoskodásokkal tudjuk elemezni.

Mutassuk meg, hogy az $X n X 1 X 2 X n$ véletlen vektor egyenletes eloszlású az $S 11 n$ halmazon, és ezért

X n A A 2 n, A S

Mutassuk meg, hogy $Y n$ sűrűségfüggvénye:

Y n k n n k 2 1 2 n, k n n 2 n 2 n

Mutassuk meg, hogy $Y n$ várható értéke és szórásnégyzete

$Y n 0$
$Y n n$

A véletlen bolyongás szimulációban válasszuk meg a végső poziciót. Változtassuk a lépések számát és figyeljük meg a sűrűségfüggvény elhelyezkedését és alakját, valamint a várható érték/standard szórás grafikonját. A paraméter kiválasztott értékeire végezzükel a szimulációt 1000-szer, 10-esével frissítve. Figyeljük meg az empirikus sűrűségfüggvénynek és momentumoknak az elméleti sűrűségfüggvényhez és elméleti momentumokhoz való nyilvánvaló konvergenciáját.

A véletlen bolyongás szimulációban válasszuk meg a végső poziciót és legyen a lépések száma 50. Végezzük el a szimulációt 1000-szer, 10-esével frissítve. Számítsuk ki és hasonlítsuk össze a következőket:

$6 Y 50 10$
Az $6 Y 50 10$ esemény relatív gyakorisága.
A $6 Y 50 10 valószínűség normális approximációja.$

A maximum állapot

Vizsgáljuk meg újra az egyszerű, szimmetrikus véletlen bolyongást. Legyen

M n Y 0 Y 1 Y n

a maximális helyzet az első

n

lépés után. Megjegyezzük, hogy

M n

értékei a

01 n

halmazból származnak.

M n

eloszlását a tükrözési elv néven ismert egyszerű és csodálatos ötlet segítségével vezethetjük le.

Mutassuk meg, hogy $M n m$ akkor és csak akkor, ha $Y i m$ valamilyen $i 01 n$ -re!

Tételezzük fel, hogy $k m n$ . Mutassuk meg, hogy minden olyan útvonal esetén, amely kielégíti az $M n m$ és az $Y n k$ feltételeket, létezik egy másik útvonal, amely kielégíti az $Y n 2 m k$ feltételeket. Útmutatás: a második útvonalat úgy kapjuk az elsőből, hogy az első útvonalat tükrözzük az $y m$ egyenesre, miután az első útvonal eléri az $m$ értékét.

Felhasználva az előző két gyakorlat eredményeit és azt a tényt, hogy az útvonalak egyformán valószínűek, mutassuk meg, hogy

M n m Y n k Y n 2 m k, k m n

Felhasználva az előző gyakorlat eredményét, mutassuk meg, hogy

M n m Y n k Y n 2 m k Y n 2 m 1 k, k m n

Felhasználva az előző gyakorlat eredményét, mutassuk meg, hogy $n$ és $m 01 n$ esetén

M n m Y n m n m n 2 1 2 n m és n ugyanolyan paritású (mindkettő páros, vagy mindkettő páratlan) Y n m 1 n m n 1 2 1 2 n m és n ellentétes paritású (egyik páros és másik páratlan)

A véletlen bolyongás szimulációjában válasszuk a maximális érték változót. Változtassuk a lépések számát és jegyezzük fel a sűrűségfüggvény elhelyezkedését és alakját, valamint a várható érték/standard szórás grafikonját. Változtassuk a lépések számát 30-ig és végezzük el a szimulációt 1000-szer, 10-esével frissítve a gakoriságot. Vegyük észre a relatív gyakoriságfüggvénynek és empirikus momentumoknak az elméleti sűrűségfüggvényhez és a momentumokhoz való konvergenciáját.

Mutassuk meg, hogy minden $n$ esetén $M n$ sűrűségfüggvénye csökkenő.

A 17. gyakorlat eredménye egy kicsit meglepő; speciálisan, a maximum legvalószínűbb értéke egyedül a 0!

Számítsuk ki $M 5$ sűrűségfüggvényét, várható értékét és standard szórását.

Egy szabályos pénzérmét 10-szer feldobunk. Adjuk meg annak valószínűségét, hogy a fejek száma és az írások száma közötti különbség sohasem nagyobb, mint 4.

A 0-ba való utolsó lépés - Az utolsó visszatérés a 0-hoz

Vizsgáljuk újra az egyszerű, szimmetrikus bolyongást. A következő témánk a 0-hoz való utolsó visszatérés eloszlásának vizsgálata az első

2 n

lépés folyamán:

Megjegyezzük, hogy mivel a 0-ba való lépés páros sokszor következik be,

L 2 n

értékeit a

02 2 n

halmazból veszi. Ez a véletlen változó különös és érdekes eloszlás és mint diszkrét arcus sinus eloszlás ismert. A továbbiakban a levezetésünkben felfedezünk néhány egyéb, érdekes eredményt is.

Mutassuk meg, hogy

L 2 n 2 k Y 2 k 0 Y 2 k 1 0 Y 2 n 0, k 01 n

Felhasználva a szimmetriát és az előző gyakorlat eredményét mutassuk meg, hogy

L 2 n 2 k Y 2 k 0 Y 1 0 Y 2 0 Y 2 n 2 k 0, k 01 n

Y 2 k

eloszlásából jobboldalon levő első tényezőt ismerjük. Így nekünk a második tényezőt kell kiszámítanunk, annak valószínűségét, hogy véletlen bolyongásunk soha nem tér vissza a 0 pontba.

Felhasználva az eredményeket a maximum pozicióra mutassuk meg, hogy

Y 1 0 Y 2 0 Y 2 j 0 M 2 j 0 2 j j 1 2 2 j

Felhasználva a szimmetriát (amely éppen az $y 0$ egyenesre vonatkozó tükrözési elv), mutassuk meg, hogy

Y 1 0 Y 2 0 Y 2 n 0 2 n n 1 2 2 n

Mutassuk meg, hogy $Y 1 0 Y 2 0 Y 2 j 0 Y 1 1 Y 2 1 Y 2 j 1$

Felhasználva a szimmetriát, az előző gyakorlat eredményét mutassuk meg, hogy

Y 1 0 Y 2 0 Y 2 j 0 Y 1 1 Y 1 0 Y 2 0 Y 2 j 1 0

Mutassuk meg, hogy $Y 2 j 1 0$ magába foglalja az $Y 2 j 0$ egyenlőtlenséget.

Felhasználva az előző gyakorlatok eredményét mutassuk meg, hogy

Y 1 0 Y 2 0 Y 2 j 0 2 j j 1 2 2 j 1

Felhasználva a szimmetriát és az előző gyakorlat eredményét mutassuk meg, hogy

Y 1 0 Y 2 0 Y 2 j 0 2 j j 1 2 2 j

Felhasználva a 22. gyakorlat és a 28. gyakorlat eredményét mutassuk meg, hogy $L 2 n$ sűrűségfüggvénye

L 2 n 2 k 2 k k 2 n 2 k n k 1 2 2 n, k 01 n

A véletlen bolyongás szimulációban válasszuk valószínűségi változónak a 0-ba való utolsó visszatérés sorszámát, majd változtassuk a lépések számát a görgetősávval. Figyeljük meg a sűrűségfüggvény helyzetét és alakját és a várható érték/standard szórás grafikonját. A paraméter különböző értékei esetén végezzük el a szimulációt 1000-szer, 10-esével frissítve a gyakoriságot és figyeljük meg az empirikus sűrűségfüggvénynek és a momentumoknak az elméleti sűrűségfüggvényhez és a momentumokhoz való nyilvánvaló konvergenciáját.

Mutassuk meg, hogy

$L 2 n 2 k L 2 n 2 n 2 k$ ilymódon a sűrűségfüggvény $n$ -re nézve szimmetrikus.
$L 2 n 2 j L 2 n 2 k$ akkor és csak akkor, ha $j k$ és $2 k n$ , ilymódon a sűrűségfüggvény $u$ -alakú.

Speciálisan 0 és

2 n

a legvalószínűbb értékek. Az arcus sinus eloszlás teljesen meglepő. Mivel egy szabályos pénzérmét dobunk fel annak eldöntésére, hogy a bolyongás merre történjen, könnyen gondolhatjuk, hogy a véletlen bolyongás az idő felében pozitív, a másik felében negatív és hogy gyakran visszatér a 0-ba. De valójában az arcus-sinus törvény magába foglalja, hogy

1 2

valószínűséggel nem fog visszatérni a 0 pontba a bolyongás második felében, az

n 1

és

2 n

időpontok között, tekintet nélkül

n

-re, és az sem ritka, hogy pozitív (vagy negatív) marad az 1-től

2 n

-ig terjedő teljes időben.

Számoljuk ki explicit módon $L 10$ sűrűségfüggvényét, várható értékét és szórásnégyzetét.

A szavazási probléma és az első 0-ba való visszatérés

A szavazási probléma

Tételezzük fel, hogy egy választásban az

A

jelölt

a

szavazatot kap és a

B

jelölt

b

szavazatot kap, ahol

a b

. Feltételezve a szavazatok véletlen sorrendjét mekkora annak a valószínűsége, hogy

A

mindig megelőzi

B

-t a szavazatok számlálásakor. Ez történetileg egy híres probléma, ami Szavazási probléma néven ismert, és Joseph Louis Bertrand oldotta meg a problémát 1887-ben. A szavazási probléma szoros kapcsolatban van az egyszerű véletlen bolyongással.

Magyarázzuk meg azt a feltevést, hogy a szavazók véletlenszerűen rendezettek egy valódi választáson.

A szavazási probléma megoldható egy egyszerű feltételes valószínűséges okoskodással, hogy megkapjuk a rekurzív relációt. Jelölje

f a b

annak valószínűségét, hogy

A

mindig megelőzi

B

-t a szavazatszámláláskor.

Mutasuk meg, hogy a jelölttel kapcsolatos feltétel, hogy ő kapja az utolsó szavazatot

f a b a a b f a 1 b b a b f a b 1

Felhasználva a kezdő feltételt $f 10 1$ és a szavazók számára ( $n a b$ ) vonatkozó indukciót, mutassuk meg, hogy

f a b a b a b

A szavazási kísérletben, változtassuk az $a$ és $b$ paraméterket és figyeljük meg a szavazási valószínűség változását. A kiválasztott paraméterekre végezzük el a kísérletet 1000-szer, 10-esével frissítve és figyeljük meg a relatív gyakoriságnak az elméleti valószínűséghez való nyilvánvaló konvergnciáját.

Egy választásban egy kisváros polgármestere, Mr. Smith 4352 szavazatot kapott, míg Ms. Jones 7543-at. Számítsuk ki annak valószínűségét, hogy Jones mindig megelőzte Smith polgármestert a szavazatszámláláskor.

A véletlen bolyongással való kapcsolat

Adott $Y n k$ , mutassuk meg, hogy

Létezik $n k 2$ lépés jobbra $n k 2$ lépés balra.
A jobbra és balra lépések minden lehetséges sorrendjének valószínűsége azonos.

Felhasználva az előző gyakorlatot és a szavazási valószínűséget mutassuk meg, hogy $k 0$ esetén,

Y 1 0 Y 2 0 Y n 1 0 Y n k k n

A szavazási kísérletben, változtassuk az $a$ és $b$ paramétereket és figyeljük meg a szavazási valószínűség változását. A paraméterek kiválasztott értékeire végezzük el a kísérletet 1000-szer, a gyakoriságot 10-esével frissítve és figyeljük meg a relatív gyakoriságnak az elméleti valószínűséghez történő nyilvánvaló konvergenciáját.

Egy amerikai rulettkeréknek 38 nyílása van; 18 piros, 18 fekete és 2 zöld. Fred 1$-t tesz a pirosra és a párosra, ötvenszer, 22-szer nyer és 28-szor veszít. Adjuk meg annak valószínűségét, hogy Fred nettó nyreménye mindig negítív.

Az első nulla eloszlása

Vizsgáljuk újra az egyszerű

p

paraméterű véletlen bolyongást. Jelölje

T

a 0-ba való első visszatérés idejét:

Megjegyezzük, hogy a 0-ba való visszatérés csak páros időben történhet meg; az is lehetséges, hogy a 0-ba soha nem tér vissza. Így

T

értékeit a

24

halmaból veszi.

Mutassuk meg, hogy

T 2 n T 2 n Y 2 n 0 T 2 n Y 2 n 0 Y 2 n 0

Felhasználva a szavazási problémát, mutassuk meg, hogy

T 2 n Y 2 n 0 1 2 n 1

Felhasználva a két előző gyakorlat eredményét mutassuk meg, hogy

T 2 n 2 n n 1 2 n 1 p n 1 p n, n

Fred és Vilma szabályos pénzérmét dobálnak. Fred nyer egy pontot, ha fejet dob, Vilma, ha írást dob. Adjuk meg annak valószínűségét, hogy pontjaik száma egyenlő az első $n$ dobás után az alábbi esetekre: $n 246810$ .

6. Egyszerű véletlen bolyongás

Alapeljárások

A szimmetrikus egyszerű bolyongás

A maximum állapot

A 0-ba való utolsó lépés - Az utolsó visszatérés a 0-hoz

A szavazási probléma és az első 0-ba való visszatérés

A szavazási probléma

A véletlen bolyongással való kapcsolat

Az első nulla eloszlása