WisFaq!

Hemel of hel

Mijn neef gaf mij laatst het volgende wiskundige raadseltje:

Er staan tien bomen naast elkaar; een persoon staat bij de derde boom; Links van de eerste boom bevindt zich de 'hel'. Rechts van de tiende boom bevindt zich de 'hemel'. bij elke boom trekt de persoon een lot. trekt hij een lot met daarop het woord 'rechts', dan schuift hij een plaats op naar rechts, bijvoorbeeld van boom 6 naar boom 7. Trekt hij daarentegen een lot met daarop het woord 'links', dan gaat hij een plaats naar links. De kans om een lot met het woord 'links' te trekken = 0,4. De kans om een lot met het woord rechts te trekken is dus 0,6.

Vragen:
Wat is de kans dat de persoon terecht komt in de 'hel'?
Is er ook een kans groter dan nul dat de persoon eeuwig in het 'bos' blijft dwalen?

m.vr.gr.

R.Trienekens
2-12-2003

Antwoord

Dit heeft te maken met Markov-ketens. In de volgende matrix komen de rijen overeen met de beginplaats. Dus rij 1 bevat de kansen dat je op elke plek terechtkomt als je in de hel start. Het is logisch dat eens je in de hel bent, je daar blijft. Dus kans 1 op kolom 1 (de hel)
rij 2 geeft de kansen om op de verschillende plaatsen de komen als je vanaf boom 1 vertrekt. Dit is kans 0.4 op de hel (kolom 1) en kans 0.6 op boom 2 (kolom 3). De andere kansen op die rij zijn nul omdat je niet naar een niet-naburige boom kan in één stap. En bij dezelfde boom blijven staan mag ook niet.



Om nu dezelfde kansen te kennen na n stappen (n keer lotje trekken en van boom wisselen), moet je deze matrix n keer met zichzelf vermenigvuldigen. Dit is met de hand een heel karwei, dus ik heb het met de PC gedaan.

Voor n voldoende groot kan de matrix stabiliseren... Die limietwaarden geven dan het antwoord op de vraag.

na een 10-tal keer vermenigvuldigen krijg je al een bevredigend resultaat.

Dit is de matrix na 50 stappen.


Wat betekent dat de kans dat je in het bos blijft naar nul nadert, onafhankelijk van de beginpositie, en de kansen gegeven de plaats waar je vertrekt (de rij van de matrix) dat je in de hel of de hemel terecht komt, staan links en rechts van elke rij.

Dus de kans dat als je bij boom 3 vertrekt in de hel terecht komt is 0.2880656084 en in de hemel 0.7119343912.
Merk op dat de som van elke rij in de matrix (bij benadering) 1 moet geven.

Koen Mahieu

PS: Een toevoeging van cl:

"Noem p(i) de kans dat je uiteindelijk in de hel terecht komt als je vertrekt bij boom i. Dan geldt voor i=1,...,10

p(i) = (4/10)p(i-1) + (6/10)p(i+1)

als je p(0)=1 en p(11)=0 definieert. Dat geeft een stelsel van 10 vergelijkingen in 10 onbekenden. Zo is p(1) bijvoorbeeld 116050/175099 = 0.66276791986...

Dat kan je herhalen voor de kansen q(i) dat je in de hemel terecht komt als je vertrekt aan boom i. p(i)+q(i)=1 voor alle i bewijst dan het tweede gevraagde. Waar je ook vertrekt, je komt OF in de hemel OF in de hel met probabiliteit 1 (wat andere mogelijkheden niet uitsluit, alleen hebben die een totale kans nul)."

Zie Een analoge vraag [http://www.wisfaq.nl/showrecord3.asp?id=17419]

km
2-12-2003