Matematik

Geometrisk distribution og sandsynlighed

09. oktober 2018 af Slashdash - Niveau: Universitet/Videregående

Hej SP. Har svært ved at se, hvordan nedenstående opgave skal løses idet der benyttes sandsynlighedsregning, hvilket ikke ligefrem er min stærke side. Alt hjælp er derfor værdsat.

En pyramide ABCDE har en kvadratisk grundflade ABCD og et toppunkt E. En myre bliver placeret i hjørnet A og en anden myre i hjørnet B. Hvert minut, så bevæger hver myre sig hen til et hosliggende hjørne. Det forventede antal minutter der vil gå, før myrerne lander ved samme hjørne er m/n, hvor m og n er indbyrdes primisk. Find m+n

Brugbart svar (0)

Svar #1
10. oktober 2018 af swpply (Slettet)

Tag et billed af hele opgaven og upload den til tråden.

• Hvad symbolisere m og n?
   • Kan de to myre besøge toppunktet E, eller er de begrænset til den kvadratiske grundflade ABCD ?
   • Er hjørnerne A og B hosliggende/naboer eller diagonale?
   • Hvilket kursus er denne opgave stillet i?

Brugbart svar (1)

Svar #2
10. oktober 2018 af VandalS

Opgaven kan løses som en Markovkæde, og du kan læse lidt om, hvordan et sådant problem løses på https://en.wikipedia.org/wiki/Stochastic_matrix, hvor der gennemgås et beslægtet eksempel.

Hvis du vil have en detaljeret gennemgang af din opgave må du lige vende tilbage med den fulde opgave - hvis teksten i #0 er hele opgaveteksten vil jeg mene, at problemet kan beskrives med fire tilstande og til kontrol finder jeg, at .

Svar #3
10. oktober 2018 af Slashdash

Dette er hele opgaven, og selvfølgelig tæller pyramidens hjørne med som et hosliggende hjørne myrerne kan besøge, da de ellers ikke kan lande ved samme hjørne. Opgaven er ikke fra et kursus. A og B er hosliggende hjørner til hinanden. M og n er somsagt indbyrdes primisk og m/n betegner det antal minutter, før de er landet ved samme hjørne.

Brugbart svar (0)

Svar #4
10. oktober 2018 af swpply (Slettet)

Dette svare til two uafhængige random walks på en Wheel graph med fem noder (W₅).

Antagelser:
• Alle hosligende noder er lige sandsynlige, hvorfor at overgangssandsynligheden for at bevæge sig til et
af nabo noderne er givet ved valensen af den pågældende node.
• De to myre kan frit passere hinanden.

Observation:
• Den eneste node hvorpå at begge myre kan være samtidig er node E (dvs. spidsen af pyramiden).

Fremgangsmåde:
   • Opskriv den stokastiske matrix $\mathbf{P}$ hørende til én enkelt myre.
   • Bestem den inverterbar matrix $\mathbf{S}$ fohvilken der gælder at $\mathbf{P} = \mathbf{S}\mathbf{D}\mathbf{S}^{-1}$ , hvor $\mathbf{D}$ er den til $\mathbf{P}$ hørende
   diagonal matrix.
   • Sandsynligheden for at myre nummer ét befinder sig på node E efter $n$ skridt er bestemt ved

$p_n = (\mathbf{P}^n)_{1,5}$ .

(hint, brug $\mathbf{S}$ og $\mathbf{D}$ til at lette ovenstående beregning)
• Ovenstående resultat kan nemt generaliseres til at gælde for den anden myre. Hvorfor at
sandsynligheden for at myre nummer to befinder sig på node E efter $n$ skridt er bestemt ved $(\mathbf{P}^n)_{2,5}$ .
Symetrien af opgaven giver at

$p_n = (\mathbf{P}^n)_{2,5}$ .

• Sandsynligheden for at både myre ét og myre to befinder sig på node E efter $n$ skridt er derfor givet ved
$p_n^2$ , hvorfor at det forventede antal skridt for at dette finder sted er bestemt ved

$\langle n\rangle = \sum_{n=1}^\infty np_n^2\,,$

hvilket du finde er en geometrisk række.

Svar #5
10. oktober 2018 af Slashdash

#4

Din fremgangsmåde er sikkert helt rigtig, og jeg takker mange gange for din hjælp, men jeg forstår dog ikke meget af din fremgangsmåde, da min viden inden for sandsynlighed er ikke stor. Jeg er bekendt med matricer (dog havde jeg ikke hørt om termet stokastisk matrice før), så den del er på plads. Kan du evt. uddybe eller pointe mig mod alternative løsningsmetoder, hvis du har overskud til det?

Brugbart svar (0)

Svar #6
11. oktober 2018 af VandalS

#5 Bemærk, at #4's observation ikke er korrekt, da myrerne godt kan mødes på andre hjørner end E, såfremt en eller begge af myrerne har bevæget sig igennem E før.

Nedenfor præsenterer jeg en lidt alternativ løsningsvinkel.

Da udfaldsrummet er tælleligt og udviklingen i tid er diskret kan vi modellere problemet med en Markovkæde. Hvis vi nummererer myrene og hjørnene er der $\small 5^2$ forskellige tilstandskombinationer, og vi kunne på baggrund af dette opstille en $\small 25 \times 25$ stokastisk matrix, der beskriver sandsynligheden for overgang fra en tilstand til en anden.
Vi er imidlertidigt ikke interesseret i at vide, præcis hvilken myre, der befinder sig hvor - vi er kun interesseret i at finde ud af, hvornår de mødes. Vi kan derfor udnytte et symmetriargument til at simplificere tilstandsrummet til følgende fire tilstande:

   1) De to myrer befinder sig på nabohjørner i grundfladen.
   2) De to myrer befinder sig overfor hinanden i grundfladen.
   3) Den ene myre er oppe på spidsen af pyramiden, mens den anden er i grundfladen.
   4) De to myrer befinder sig i samme hjørne.

Lad os dobbelttjekke, at disse tilstande dækker alle de oprindelige 25:

Tilstand 1) dækker kombinationerne AB, BC, CD, DA samt BA, CB, DC, AD.
Tilstand 2) dækker kombinationerne AC, BD samt CA, DB.
Tilstand 3) dækker kombinationerne AE, BE, CE, DE samt EA, EB, EC og ED.
Tilstand 4) dækker kombinationerne AA, BB, CC, DD, EE.

Tilsammen er der dækket af kombinationerne; altså er hele tilstandsrummet indkluderet. Vi ønsker nu at opstille en stokastisk matrix tilhørende de nye tilstande.

Givet at en myre altid bevæger sig til et hosliggende hjørne på pyramiden med lige stor sandsynlighed kan vi opstille følgende skema:

   • Fra A bevæger myren sig til B, D eller E, hver med1/3 chance.
   • Fra B bevæger myren sig til A, C eller E, hver med 1/3 chance.
   • Fra C bevæger myren sig til B, D eller E, hver med 1/3 chance.
   • Fra D bevæger myren sig til A, C eller E, hver med 1/3 chance.
   • Fra E bevæger myren sig til A, B, C eller D, hver med 1/4 chance.

Hvis vi befinder os i tilstand 1) har hver myre tre forskellige steder, de kan gå hen, hvilket vil sige, at der kan besøges 9 forskellige kombinationer af hjørner. 4 af disse tilhører tilstand 1) som opnås ved en af følgende overgange:

   • Begge myrer bevæger sig med uret rundt i grundfladen.
   • Begge myrer bevæger sig mod uret rundt i grundfladen.
   • Begge myrer bevæger sig til den modsatte side af pyramiden.
   • Myrerne bytter plads.

Yderligere 4 kombinationer tilhører tilstand 3), som opnås ved at
• Den første myre går til E, mens den anden går enten til venstre eller højre (tilsammen 2 udfald)
• Den anden myre går til E, mens den første går enten til venstre eller højre (tilsammen 2 udfald)

Den sidste mulighed er, at de begge går til E samtidig, og systemet går til tilstand 4). Der er ingen mulig direkte overgang mellem tilstand 1) og tilstand 2).

Vi samler sandsynlighederne som en rækkevektor,

$\small \bold{p_1} = \left(\frac{4}{9}, 0, \frac{4}{9}, \frac{1}{9} \right)$ ,

der beskriver overgangen fra tilstand 1) til en anden tilstand. Detaljerne for de øvrige tilstandsovergange vil jeg lade dig selv udlede, men jeg får, at

$\small \bold{p_2}= \left(0, \frac{2}{9}, \frac{4}{9}, \frac{3}{9} \right)$
$\small \bold{p_3} = \left(\frac{4}{12}, \frac{2}{12}, \frac{4}{12}, \frac{2}{12} \right)$
$\small \bold{p_4} = \left(0, 0, 0, 1 \right)$

Saml vektorerne til en stokastisk matrix $\small \bold{P}$ .

Da vi vil finde ud af, hvor lang tid der går, inden myrerne mødes lader vil tilstand 4) være en absorberende tilstand, hvorfra systemet ikke kan undslippe. Tiden der går, inden vi ankommer til den absorberende tilstand, følger nu en såkaldt discrete phase-type distribution. Da tilstand 4) ikke bidrager til overlevelsestiden dropper vi fra $\small \bold{P}$ den tilsvarende række og søjle og får undermatricen

$\bold{\tilde{P}} = \begin{bmatrix} \frac{4}{9} & 0 & \frac{4}{9}\\ 0 & \frac{2}{9} & \frac{4}{9}\\ \frac{1}{3} & \frac{1}{6} & \frac{1}{3} \end{bmatrix}$

Denne matrix beskriver overgangen fra en "levende" tilstand til en ny "levende" tilstand. Sandsynligheden for, at systemet overlever det første tidsskridt kan findes ved

$p_1 = \bold{a} \cdot \bold{\tilde{P}} \cdot \bold{1}$ , hvor og

$\small \bold{1} = \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}$ .

$\small \bold{a}$ beskriver den tilstand, vi starter i (tilstand 1) og $\small \bold{1}$ fungerer som en summation over alle de mulige udfald.
Sandsynligheden for, at systemet overlever de første $\small n$ tidsskridt, er givet ved

$\small p_n = \bold{a} \cdot \bold{\tilde{P}}^n \cdot \bold{1}$ ,

som blot er en matrixrepræsentation af den almindelige geometriske distribution. For at finde den forventede overlevelsestid t for systemet skal vi summere over alle $\small n$ , som ved lidt manipulation kan skrives som:

$\small E[t] = \bold{a} \cdot \left(\sum_{n=0}^\infty \bold{\tilde{P}}^n \right) \cdot \bold{1}$

Bemærk, at og stemmer med, at vi efter 0 tidsskridt skal befinde os i tilstanden beskrevet med $\small \bold{a}$ .

Da Frobenius-normen af $\small \bold{\tilde{P}}$ er mindre end 1 konvergerer matrixsummen ovenfor, og vi beregner resultatet til at være

$\small E[t] = \bold{a} \cdot \left( \bold{I} - \bold{\tilde{P}} \right)^{-1} \cdot \bold{1} = \frac{105}{16}$ ,

hvorfor $\small n+m = 121$ .

Hvis du har spørgsmål til min besvarelse er du velkommen til at skrive; det blev til noget af en smøre =)

Skriv et svar til: Geometrisk distribution og sandsynlighed

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.