PROBLEM MONTY HALL IN NJEGOVE POSPLOˇ SITVE

(1)

Univerza v Ljubljani Pedagoˇ ska fakulteta

Univerzitetni ˇstudijski program 1. stopnje: Dvopredmetni uˇcitelj

ALEN KOPI ´ C

Mentor : doc. dr. PRIMOˇ Z ˇ SPARL

PROBLEM MONTY HALL IN NJEGOVE POSPLOˇ SITVE

DIPLOMSKO DELO

Ljubljana, 2013

(2)

(3)

Kazalo

Povzetek Abstract

1 Uvod 1

1.1 Rojstvo problema . . . 1

1.2 Afera Parade . . . 2

1.3 Problem Monty Hall in njegove posploˇsitve . . . 3

2 Uvod v teorijo verjetnosti 5 2.1 Poskus, izidi, dogodki in verjetnost . . . 5

2.2 Pravili vsote in produkta . . . 8

2.3 Pogojna verjetnost in popolna verjetnost . . . 9

3 Problem Monty Hall 15 3.1 Opis osnovnega problema in reˇsitev . . . 15

3.2 Posploˇsitve problema Monty Hall . . . 18

4 Raˇcunalniˇska simulacija problema 29 4.1 Opis programa Monty Hall simulator . . . 29

4.2 Rezultati simulacije posploˇsitve Monty Hall 1.0 . . . 32

5 Zakljuˇcek 39

(4)

Slike

4.1 Videz aplikacije pri simuliranju razliˇcnih posploˇsitev . . . 30 4.2 Sporoˇcilno okno z rezultati simulacije Monty Hall 1.0 . . . 31 4.3 Polja za vnos ˇstevila odprtih vrat pred zamenjavo . . . 31 4.4 Sporoˇcilno okno, ki opozarja na neustreznost vnesenih podatkov 32

(5)

Tabele

4.1 Rezultati simulacije Monty Hall 1.0 (n = 1000000) . . . 34 4.2 Rezultati simulacije Monty Hall 2.0 (n = 1000000) . . . 36 4.3 Rezultati simulacije Monty Hall 3.0 (d = 13, c = 3, n =

1.000.000) . . . 38

(6)

(7)

Povzetek

T. i. problem Monty Hall je v svoji osnovni obliki uganka s podroˇcja verjetnosti, pri kateri imamo troje vrat, od katerih je za dvemi koza, za enimi pa avtomobil. Na zaˇcetku izberemo ena vrata. Nato voditelj odpre ena izmed preostalih vrat in to takˇsna, da je za njimi koza, in nam ponudi moˇznost zamenjave na zaˇcetku izbranih vrat s preostalimi zaprtimi vrati. Zanima nas, ali se nam izplaˇca zamenjati izbiro.

Namen tega diplomskega dela je razumljivo in logiˇcno predstaviti reˇsitev problema Monty Hall ter raziskati njegove posploˇsitve, v katerih nastopa poljubno ˇstevilo vrat, avtomobilov in zamenjav. Teoretiˇcni rezultati so podkre- pljeni tudi z raˇcunalniˇskimi simulacijami problema in njegovih posploˇsitev.

Kljuˇcne besede: teorija verjetnosti, problem Monty Hall, posploˇsitve problema Monty Hall, simulacija

(8)

(9)

Abstract

The so-called Monty Hall problem in its basic form is a probability puzzle where we initially have three doors, with a car behind one of the doors and goats behind the other two. We first choose one door. The game host, who knows behind which door the car is, then opens one of the remaining doors which has a goat behind it and offers us the opportunity to change our initial choice by picking the only remaining closed door. The question is whether it is better to change doors or not.

The purpose of this work is to present a solution to the Monty Hall problem in a clear and mathematically correct way and to explore its generalisations in which different numbers of doors, cars and door changes are possible. Also presented are results of computer simulations of the Monty Hall problem and its generalisations.

MSC (2010) Classification: 60A05, 60C05

Key words: probability theory, Monty Hall problem, generalisations of Monty Hall problem, simulation

(10)

(11)

Poglavje 1 Uvod

Zelo redko se zgodi, da se matematiˇcni problem znajde na naslovnici nedelj- ske izdaje ˇcasopisaNew York Times, vendar pa je problemu Monty Hall 21.

julija leta 1991 uspelo prav to. To je samo eden izmed primerov, ki priˇcajo o izjemni publiciteti, ki je je bil skozi leta deleˇzen omenjen problem, ki sicer velja za eno najzanimivejˇsih matematiˇcnih ugank sodobnega ˇcasa.

V tem poglavju, ki je povzeto po [6], predstavimo zgodovino tega problema in napovemo, o ˇcem bomo govorili v nadaljevanju.

1.1 Rojstvo problema

Med letoma 1963 in 1977 se je v Zdruˇzenih drˇzavah Amerike predvajala tele- vizijska igraLet’s Make a Deal, ki jo je vodil televizijski voditelj Monty Hall.

Igra, ki je navdihnila rojstvo matematiˇcnega problema Monty Hall, je, ˇce nekoliko poenostavimo, potekala na naslednji naˇcin. Igralec je moral izbrati ena izmed treh vrat. Za enimi vrati je bil avtomobil, za dvema pa koza. Iz- brana vrata se niso odprla takoj, temveˇc je voditelj najprej odprl tista izmed preostalih dveh vrat (ali ena izmed njih), za katerimi je bila koza, in nato igralcu ponudil moˇznost, da zamenja svojo zaˇcetno izbiro in izbere preostala zaprta vrata.

1

(12)

2 POGLAVJE 1. UVOD

Februarja leta 1975 je bilo v znanstveni reviji The American Statistician objavljeno pismo, ki ga je takratni matematik z univerze University of Cali- fornia, Berkeley, Steve Selvin naslovil na urednika revije. V njem je predsta- vil matematiˇcno uganko, ki je temelj matematiˇcnega problema Monty Hall, in njeno reˇsitev. Trdil je, da je verjetnost zmage veˇcja, ˇce se igralec odloˇci za zamenjavo vrat, svoje trditve pa je podprl s tabelo vseh moˇznih izidov, iz katere je bilo razvidno, da je verjetnost zmage po zamenjavi enaka ⁶₉ oziroma pribliˇzno 67 %. Poleg tega je v svojem pismu navedel tudi, da je prejel veliko pisem, v katerih so mu oporekali pravilnost njegove reˇsitve, med pisci pa ni manjkalo tudi uveljavljenih matematikov. Ne glede na to je minilo kar dese- tletje in pol, preden je problem Monty Hall zares pustil peˇcat v matematiˇcnih krogih.

1.2 Afera Parade

Septembra leta 1990 je Marilyn vos Savant v svoji kolumni v reviji P arade podala odgovor na vpraˇsanje bralca. Vpraˇsanje se je glasilo: “Denimo, da sodelujemo v televizijski igri, v kateri imamo na izbiro troje vrat. Za enimi vrati je avtomobil, za ostalima dvema pa koza. Izberemo vrata, npr. vrata ˇstevilka 1, nato voditelj igre, ki ve, za katerimi vrati je avtomobil, odpre ena izmed preostalih vrat, in sicer takˇsna, da je za njimi koza. Denimo, da so to vrata ˇsrevilka 3. Nato nas vpraˇsa, ali ˇzelimo namesto na zaˇcetku izbranih vrat izbrati vrata ˇstevilka 2. Ali se nam bolj izplaˇca zamenjati vrata ali ostati pri zaˇcetni izbiri?” Vos Savantova je v svojem odgovoru trdila, da se bolj izplaˇca zamenjati vrata, saj je verjetnost za zmago, ˇce ostanemo pri prvotni izbiri, enaka ¹₃, ˇce se odloˇcimo za zamenjavo, pa ²₃.

Njen odgovor je sproˇzil val kritik. Avtorica naj bi prejela okoli 10.000 pisem, od katerih so jih skoraj 1000 napisali bralci z doktorati. Med drugim so jo v njih pozivali, naj javno prizna svojo napako. Nekateri izmed odzivov, tudi

(13)

1.3. PROBLEM MONTY HALL IN NJEGOVE POSPLOˇSITVE 3

uveljavljenih matematikov, so bili zelo negativno nastrojeni in celo ˇzaljivi.

Marilyn vos Savant je kljub temu ˇse naprej vztrajala pri svojem odgovoru in kmalu je dobila potrditev pravilnosti svojih trditev, saj so jih potrdili rezultati mnogih simulacij problema, prav tako pa so bile podane tudi formalne matematiˇcne utemeljitve, ki so govorile v prid njenim trditvam.

Bralcu, ki bi o aferi L’affaire Parade in o problemu Monty Hall na sploˇsno rad izvedel veˇc, svetujem branje knjige [6].

1.3 Problem Monty Hall in njegove posploˇ sitve

Problem Monty Hall je bil snov za nastajanje mnogih strokovnih del iz naj- razliˇcnejˇsih podroˇcij. Poleg matematikov so zanimanje zanj pokazali tudi kognitivni znanstveniki in psihologi, ki jih je zanimalo, zakaj ga je ljudem tako teˇzko razumeti. Filozofi so ga uporabili neposredno za raziskovanje narave verjetnosti in tudi posredno za raziskovanje drugih, na videz nepove- zanih filozofskih vpraˇsanj, ekonomisti pa so preiskovali, kaj nam dognanja, ki nam jih nudi problem Monty Hall, povedo o ˇcloveˇskem odloˇcanju. Problem so raziskovali tudi mnogi drugi strokovnjaki z razliˇcnih podroˇcij.

V diplomskem delu se bom osredotoˇcil na matematiˇcni vidik problema in raziskal dodatne posploˇsitve prvotne razliˇcice. Za to bom potreboval nekaj teoretiˇcnih orodij iz teorije verjetnosti. Temu sta namenjeni poglavji 2 in 3.

V poglavju 4 opiˇsem osnovno razliˇcico problema in podam formalno reˇsitev.

Nato sledijo posploˇsitve problema in njihove reˇsitve ter primerjava med njimi.

V poglavju 5 je opisan program, s pomoˇcjo katerega smo simulirali osnovni problem Monty Hall in njegove posploˇsitve. Nato sledijo rezultati simulacij in njihova interpretacija.

(14)

4 POGLAVJE 1. UVOD

(15)

Poglavje 2

Uvod v teorijo verjetnosti

Problem Monty Hall je uganka s podroˇcja verjetnosti, zato bomo na zaˇcetku spoznali tri najpomembnejˇse pojme v teoriji verjetnosti. To so poskus, dogodek in verjetnost. Nato sledi pregled nekaterih pomembnejˇsih pravil in iz- rekov, ki nam bodo priˇsli prav pozneje, ko bomo obravnavali problem Monty Hall in njegove posploˇsitve.

Pri obravnavi se v razdelkih 2.1 in 2.3 naslonimo na knjigi [1] in [4], v razdelku 2.2 pa na knjigo [5].

2.1 Poskus, izidi, dogodki in verjetnost

Okoli nas je veliko pojavov, ki jih dojemamo kot nakljuˇcne in nepredvidljive.

Naˇs cilj je, da te pojave opiˇsemo z izidi nekega poskusa. V tem kontekstu obravnavamo pojemposkus zelo sploˇsno, in sicer kot nek proces, ki ga lahko opravimo pod natanko doloˇcenimi pogoji, pri tem pa so vnaprej znani vsi moˇzni izidi. Izidi so elementi prostora izidov, torej mnoˇzice, ki jo obiˇcajno oznaˇcimo z S, podmnoˇzice prostora izidov pa imenujemo dogodki. Dogodku doloˇcimo verjetnost, ki je ˇstevilo med 0 in 1 in izraˇza, kako gotovo je, da se bo ta dogodek dejansko zgodil.

5

(16)

6 POGLAVJE 2. UVOD V TEORIJO VERJETNOSTI

2.1.1 Prostor izidov in dogodki

Definicija: Prostor izidov je mnoˇzica, katere elementi opisujejo vse moˇzne izide poskusa, ki nas zanima.

ZGLED: Poglejmo si preprost poskus meta kovanca. ˇCe predvidimo, da ko- vanec ne bo nikoli obstal na stranskem robu, obstajata dva moˇzna izida tega poskusa: cifra in grb. To pomeni, da lahko za prostor izidov tega poskusa vzamemoS ={C, G}.

ZGLED: Imejmo poskus, pri katerem iz vreˇce, v kateri so rdeˇca, zelena in bela ˇzogica, zaporedoma izvleˇcemo vse tri ˇzogice. Prostor izidov za ta poskus je mnoˇzica vseh moˇznih zaporedij izvleˇcenih ˇzogic:

S ={RZB, RBZ, ZRB, ZBR, BRZ, BZR}.

Obiˇcajno nas ne zanimajo le posamezni izidi, temveˇc nas zanima, kdaj se na primer zgodi vsaj en izmed izidov danega nabora.

Definicija: Dogodek je vsaka podmnoˇzica prostora izidov. ˇCe je izid neke konkretne izvedbe poskusa element mnoˇzice A, pravimo, da se je zgodil do- godekA.

Ce se dogodekˇ A zgodi v vsaki ponovitvi poskusa, ga imenujemo gotov dogodek (ˇce je torej A= S), ˇce se ne zgodi v nobeni ponovitvi poskusa, ga imenujemonemogoˇc dogodek (ˇce je torej A=∅), ko pa se v doloˇcenih pono- vitvah poskusa zgodi, v doloˇcenih pa ne, ga imenujemo sluˇcajen dogodek.

Nad dogodki lahko izvajamo obiˇcajne operacije, ki jih lahko izvajamo nad mnoˇzicami.

ZGLED: V zgoraj omenjenem poskusu z ˇzogicami bi nas lahko zanimali vsi izidi, pri katerih je bila prva izvleˇcena bela ˇzogica. To pomeni, da bi nas

(17)

2.1. POSKUS, IZIDI, DOGODKI IN VERJETNOST 7

zanimalo, ˇce se je zgodil dogodekL={BRZ, BZR}.

ZGLED: ˇCe je R = {ZBR, BZR} dogodek, ki ustreza vsem izidom, ko je bila rdeˇca ˇzogica izvleˇcena zadnja, potem je presek dogodkov LinR enak L∩R = {BZR} in se zgodi, ˇce se zgodi tako dogodek L kot tudi dogodek R (prva je izvleˇcena bela, zadnja pa rdeˇca ˇzogica). Dogodek, ki predstavlja njuno unijo, jeL∪R={BRZ, BZR, ZBR}in se zgodi, ˇce se zgodi vsaj eden od dogodkov L in R (bodisi je prva izvleˇcena bela ˇzogica bodisi je zadnja izvleˇcena rdeˇca ˇzogica ali pa se zgodi oboje).

Poleg unije in preseka dveh dogodkov je pogosta operacija nad dogodki tudi komplement. Dogodek A^c={s∈S :s /∈A} je komplement dogodka A in se zgodi natanko tedaj, ko se dogodek A ne zgodi. Imenujemo ga tudi nasprotni dogodek dogodku A in ga oznaˇcujemo z ¯A. Komplement prostora izidov S je prazna mnoˇzica (S^c = ∅) in predstavlja nemogoˇc dogodek. Do- godkaAinB sta disjunktna, ˇce je njun presek nemogoˇc dogodek (A∩B =∅).

2.1.2 Verjetnost

Zelimo si izraziti, kakˇsna je gotovost, da se bo zgodil nek dogodek. To sto-ˇ rimo tako, da vsakemu dogodku priredimo neko ˇstevilo med 0 in 1, pri ˇcemer tistik, ki so bolj verjetni priredimo veˇcjo verjetnost, tistik, ki so manj verjetni, pa manjˇso. Ob tem se je potrebno drˇzati doloˇcenih pravil.

Definicija: Verjetnostna funkcija (tudi verjetnost) P na prostoru izidov S je funkcija, ki vsakemu dogodku A⊆S doloˇci realno ˇstevilo P(A)∈[0,1]

tako, da velja

i) P(S) = 1 in

ii) za vsako ˇstevno neskonˇcno druˇzino {A_n:n∈N} paroma disjunktnih dogodkov velja P(S∞

n=1An) = P∞

n=1P(An).

(18)

Steviloˇ P(A) imenujemo verjetnost, da se zgodi dogodek A. ˇCe je i izid nekega poskusa, potem navadno namesto P({i}) piˇsemo kar P(i), dogodku i pa reˇcemo elementarni dogodek. Zaradi aditivnosti verjetnostne funkcije velja, da je verjetnost dogodka kar vsota verjetnosti elementarnih dogodkov, ki dogodek sestavljajo.

ZGLED: Za zgled vzemimo poskus meta poˇstenega kovanca. To pomeni, da je verjetnost, da pade cifra ali grb, enaka. Prostor izidov je S ={C, G}.

V tem poskusu so mogoˇci ˇstirje dogodki, in sicer∅,{C},{G}inS. Verjetno- sti za te dogodke so P(∅) = 0, P({C}) = 1/2, P({G}) = 1/2 in P(S) = 1. S tem smo definirali verjetnost na prostoru izidovS.

Glede na to, da je verjetnost aditivna funkcija, lahko iz dejstva, da velja A∪A^c =S, izpeljemo tudi verjetnost nasprotnega dogodka oz. komplementa:

P( ¯A) = 1−P(A).

2.2 Pravili vsote in produkta

V nadaljevanju bomo obravnavali dva osnovna kombinatoriˇcna prijema, ki sta nam v pomoˇc pri raˇcunanju verjetnosti. Gre za pravilo produkta in pravilo vsote.

Pravilo produkta se nanaˇsa na situacijo, ko izbiranje poteka v k zaporednih stopnjah: na prvi izbiramo med n₁ moˇznostmi, na drugi med n₂ moˇznostmi ..., na zadnji, k-ti, pa med nk moˇznostmi. Pri tem je na vsaki stopnji izbira- nja ˇstevilo moˇznosti neodvisno od izbranih moˇznosti na prejˇsnjih stopnjah.

ˇStevilo vseh moˇznih izborov je tedaj enako n=n₁ ·n₂· · ·n_k.

V jeziku teorije mnoˇzic to pravilo pove, da je kardinalnost karteziˇcnega pro- duktaA₁×A₂× · · · ×A_k mnoˇzic A₁, A₂ . . .A_kenaka produktu kardinalnosti teh mnoˇzic, to je: |A1×A2× · · · ×Ak|=|A1| · |A2| · · · |Ak|.

(19)

2.3. POGOJNA VERJETNOST IN POPOLNA VERJETNOST 9

Pravilo vsote se nanaˇsa na situacijo, ko imamo pri izbiranju na voljo k paroma disjunktnih mnoˇzic. To pomeni, da so izbori iz poljubne mnoˇzice nezdruˇzljivi z izbori iz vseh drugih mnoˇzic. V tem primeru lahko izberemo eno od n1 moˇznosti iz prve mnoˇzice izborov ali eno odn2 moˇznosti iz druge mnoˇzice itd. ˇStevilo vseh moˇznih izborov je takrat enakon =n₁+n₂+· · ·+n_k. V jeziku teorije mnoˇzic to pomeni, da je v primeru, ko so konˇcne mnoˇzice A₁, A₂. . .A_k paroma disjunktne, kardinalnost njihove unije enaka vsoti kardinalnosti teh mnoˇzic, to je: A_i ∩A_j =∅,∀i 6= j ⇒ |A₁∪A₂∪ · · · ∪A_k| =

|A1|+|A2|+· · ·+|Ak|.

ZGLED: V tovarni oblaˇcil izdelujejo bombaˇzne majice v velikostih S, M, L, XL in XXL, vsako velikost v ˇstirih razliˇcnih barvah in z dvema oblikama ovratnika. Zanima nas, koliko razliˇcnih majic izdelujejo.

Glede na to, da so izbira velikosti, barve in tipa ovratnika med seboj neod- visne, v tem primeru uporabimo pravilo produkta: 5·4·2 = 40. V tovarni torej izdelujejo 40 razliˇcnih majic.

ZGLED: Na koliko naˇcinov lahko med 6 moˇskimi, 5 ˇzenskami in 3 otroki izberemo eno osebo?

Oˇcitno je, da v tem primeru uporabimo pravilo vsote, saj lahko izberemo bodisi enega moˇskega bodisi eno ˇzensko bodisi enega otroka. Reˇsitev je torej 6 + 5 + 3 = 14.

2.3 Pogojna verjetnost in popolna verjetnost

Vˇcasih dejstvo, da se je zgodil nek dogodek, vpliva na verjetnost nekega drugega dogodka. Govorimo o tako imenovani pogojni verjetnosti. Ce jeˇ pogojna verjetnost enaka prvotni verjetnosti dogodka, to pomeni, da sta

(20)

dogodka neodvisna.

V tem razdelku si pobliˇze pogledamo ta dva pojma, na koncu razdelka pa obravnavamo ˇse izrek o popolni verjetnosti.

2.3.1 Pogojna verjetnost

Na nek naˇcin bi lahko rekli, da je raˇcunanje pogojne verjetnosti dogodka A pri pogoju, da se je zgodil dogodekB, iskanje deleˇza verjetnosti dogodkaB, ki je vsebovan tudi v dogodkuA.

ZGLED: Denimo, da na ulici sreˇcamo neko osebo in se vpraˇsamo, v katerem mesecu je rojena. Konkretno se spraˇsujemo o tem, ali je rojena v katerem izmed “dolgih” mesecev (dogodek D) in ali ima mesec, v katerem je rojena, v imenu ˇcrko “r” (dogodekR).

D={jan, mar, maj, jul, aug, okt, dec}

R={jan, f eb, mar, apr, sep, okt, nov, dec}

Ce malce poenostavimo in privzamemo, da so meseci rojstva enako verje-ˇ tni, je verjetnost dogodkov D in R preprosto izraˇcunati, saj delimo ˇstevilo mesecev v dogodku s ˇstevilom vseh mesecev: P(D) = ₁₂⁷ in P(R) = ₁₂⁸ . Predstavljajmo si, da vemo, da je oseba, ki smo jo sreˇcali, rojena v enem izmed “dolgih” mesecev. Zanima nas, kakˇsna je verjetnost, da je rojena v mesecu, ki ima v svojem imenu ˇcrko “r”.

Ugotovimo, da se v tem primeru prostor vseh moˇznih izidov zmanjˇsa za 5 izidov, saj lahko izloˇcimo mesece februar, april, junij, september in no- vember. Ostane sedem moˇznih izidov, od katerih so samo ˇstirje v preseku D∩R ={jan, mar, okt, dec}. To pomeni, da je pogojna verjetnost dogodka R pri pogoju, da se je zgodil D, enaka ⁴₇; to zapiˇsemoP(R|D) = ⁴₇.

Vpeljimo pojem pogojne verjetnosti ˇse formalno.

(21)

Definicija: Naj bo S prostor izidov za nek poskus, naj bo P verjetnost na S in naj bosta A, B ⊆ S taka dogodka, da je P(B) > 0. Tedaj pogojno verjetnost dogodka A pri pogoju, da se je zgodil dogodekB, definiramo kot P(A|B) = ^P_P^(A∩B)_(B) .

2.3.2 Neodvisnost dogodkov

Obravnavali smo primer, ko dejstvo, da se je zgodil doloˇcen dogodek, vpliva na verjetnost, da se je zgodil nek drug dogodek. To ne velja vedno. V primeru, ko en dogodek ne vpliva na verjetnost drugega, govorimo o neodvi- snosti dogodkov.

Definicija: Naj bo S prostor izidov za nek poskus in P verjetnost na S. Pravimo, da sta dogodka A, B ⊆ S neodvisna, ˇce velja P(A|B) = P(A) aliP(B|A) = P(B).

Iz definicije pogojne verjetnosti je mogoˇce izpeljati uporabno pravilo, ki nam vˇcasih olajˇsa raˇcunanje verjetnosti preseka dveh dogodkov.

Trditev 2.1 Naj bo S prostor izidov za nek poskus in P verjetnost na S.

Tedaj za dogodka A, B ⊆S velja P(A∩B) = P(A|B)·P(B).

V primeru, ko staA inB neodvisna dogodka, velja P(A|B) = P(A), zato je verjetnost preseka dogodkov kar enaka produktu verjetnosti dogodkov (P(A∩

B) = P(A)·P(B)).

Zgornjo trditev zlahka posploˇsimo na veˇc dogodkov. Kot bomo videli, nam bo ta posploˇsitev priˇsla ˇse kako prav v nadaljevanju.

Izrek 2.2 Naj bo S prostor izidov za nek poskus in P verjetnost na S. Naj bodo A₁, A₂. . . A_n taki dogodki, da je P(A₁ ∩A₂ ∩ · · · ∩An−1) > 0. Tedaj velja

P(A₁∩A₂∩· · ·∩A_n) = P(A₁)·P(A₂|A₁)·P(A₃|A₁∩A₂)· · ·P(A_n|A₁∩A₂∩· · ·∩An−1).

(22)

Dokaz: Po definiciji pogojne verjetnosti veljaP(A|B) = ^P(A∩B)_P(B) , zato velja

P(A₁ ∩A₂∩ · · · ∩A_n) = P(A₁)·P(A₂|A₁)·P(A₃|A₁∩A₂)· · ·P(A_n|A₁ ∩A₂∩ · · · ∩An−1)

=P(A1)

·

P(A₁ ∩A₂)

P(A₁)

·⁽⁽⁽⁽⁽⁽

(((

P(A₁ ∩A₂∩A₃)

P(A₁∩A₂) ...

·(((((((((((((

P(A₁ ∩A₂∩ · · · ∩An−1)

(((((((((((((

P(A₁ ∩A₂∩ · · · ∩A_n−2)

· P(A₁∩A₂∩ · · · ∩A_n)

(((((((((((((

P(A₁ ∩A₂∩ · · · ∩An−1) .

2

2.3.3 Izrek o popolni verjetnosti

Izrek o popolni verjetnosti nam omogoˇca, da v primeru, ko imamo celoten prostor izidov razdeljen s ˇstevno particijo, verjetnost poljubnega dogodka raˇcunamo s pomoˇcjo ustreznih pogojnih verjetnosti.

Izrek 2.3 Naj bo S prostor izidov za nek poskus in P verjetnost na S. Naj bodoC₁, C₂. . . C_m takˇsni paroma disjunktni dogodki, kjer je P(C_i)>0 ∀i, da velja C₁∪C₂∪. . .∪C_m =S. Tedaj za poljuben dogodek A⊆S velja

P(A) =P(A|C₁)·P(C₁) +P(A|C₂)·P(C₂) +· · ·+P(A|C_m)·P(C_m).

Dokaz: Ker je S

iC_i =S inA ⊆S, velja P(A) =P

A∩[

iC_i

=P [

i(A∩C_i) .

Glede na to, da so vsi presekiA∩C_i disjunktni, velja enakost P[

i(A∩C_i)

=X

iP(A∩C_i),

(23)

to pa lahko po definiciji pogojne verjetnosti napiˇsemo tudi kot X

iP(A|C_i)P(C_i).

2 ZGLED: Izmed 1000 elektriˇcnih ˇzarnic jih je 400 izdelanih v prvi tovarni, 350 v drugi in 250 v tretji tovarni. Verjetnosti, da so ˇzarnice standardne kakovosti, so za posamezne tovarne zaporedoma 0,95, 0,92, 0,96. Kolikˇsna je verjetnost, da je sluˇcajno izbrana ˇzarnica izmed vseh 1000 ˇzarnic standardne kakovosti?

Ce zˇ A₁ oznaˇcimo dogodek, da je bila ˇzarnica izdelana v prvi, z A₂, da je bila izdelana v drugi, in z A₃, da je bila izdelana v tretji tovarni, je {A₁, A₂, A₃} particija prostora izidov. ˇCe oznaˇcimo z B dogodek, da je bila izbrana ˇzarnica standardne kakovosti, potem je po izreku o popolni verjetnosti P(B) = P(B|A₁)·P(A₁) +P(B|A₂)·P(A₂) +P(B|A₃)·P(A₃) = 0,95·0,4 + 0,92·0,35 + 0,96·0,25 = 0,942.

(24)

(25)

Poglavje 3

Problem Monty Hall

Kot smo ˇze omenili, je osnovno obliko problema Monty Hall leta 1975 zastavil Steve Selvin, ˇsirˇsi javnosti pa je postal znan leta 1990 po zaslugi kolumnistke Marilyn vos Savant. Od takrat so se s problemom Monty Hall oz. s pro- blemi, izpeljanimi iz njega, ukvarjali mnogi strokovnjaki iz mnoˇzice razliˇcnih podroˇcij.

V tem poglavju bomo predstavili matematiˇcno formulacijo in reˇsitev osnovnega problema Monty Hall in njegovih treh posploˇsitev. V razdelku 3.1 in podrazdelku 3.2.1 bomo sledili ˇclanku [7], v podrazdelku 3.2.2 ˇclanku [2], v podrazdelku 3.2.3 pa ˇclanku [3].

3.1 Opis osnovnega problema in reˇ sitev

V najosnovnejˇsi razliˇcici problema igramo igro, pri kateri se znajdemo pred tremi zaprtimi vrati. Za dvemi vrati je koza, za enimi pa avtomobil. ˇZelimo si osvojiti avtomobil. Na zaˇcetku izberemo ena vrata. Nato voditelj igre, ki ve, za katerimi vrati je avtomobil, odpre ena izmed preostalih dveh vrat, in sicer vrata, za katerimi je koza. Nato nas vpraˇsa, ali ˇzelimo zamenjati vrata.

Zanima nas, ali se nam bolj izplaˇca zamenjati vrata ali ostati pri zaˇcetni izbiri.

15

(26)

16 POGLAVJE 3. PROBLEM MONTY HALL

Veliko ljudi je zmotno prepriˇcanih, da je povsem vseeno, za katero moˇznost se odloˇcimo, saj naj bi bila verjetnost za zmago vselej enaka ¹₂. Svoje staliˇsˇce pogosto utemeljujejo s tem, da gre v tem primeru za izbiro enih izmed preostalih dveh zaprtih vrat. Takˇsno razmiˇsljanje je napaˇcno. V resnici je verjetnost za zmago, ˇce zamenjamo izbiro, dvakrat tolikˇsna, kot ˇce ostanemo pri prvotni izbiri.

V nadaljevanju sledi matematiˇcna utemeljitev te trditve.

Igro lahko obravnavamo kot poskus, pri katerem so mogoˇci izidi a₁ (avtomobil je za prvimi vrati),a₂ (avtomobil je za drugimi vrati) ina₃ (avtomobil je za tretjimi vrati). Izidi so med seboj paroma disjunktni in skupaj tvorijo prostor izidov S ={a₁, a₂, a₃}. Ker je avto za nakljuˇcno izbranimi vrati, so vsi trije enako verjetni. Velja torej P(a₁) = P(a₂) =P(a₃) = ¹₃.

Zato je pri zaˇcetni izbiri vrat verjetnost, da se za njimi skriva avtomobil, enaka P(A₀) = ¹₃, verjetnost, da se skriva za enimi izmed preostalih vrat pa P(A₀) = 1 − ¹₃ = ²₃. Ko voditelj odpre ena izmed preostalih vrat in vidimo, da je za njimi koza, se verjetnost, da je za prvotno izbranimi vrati avtomobil, ne spremeni, saj nismo dobili nobenih dodatnih informacij o tem ali se za naˇsimi vrati skriva avtomobil ali ne. Verjetnost, da je avtomobil za naˇsimi vrati, torej ostane ¹₃. To pomeni, da je verjetnost, da se avto skriva za katerimi izmed preostalih dveh vrat, ˇse vedno enaka ²₃. Glede na to, da so ena izmed preostalih dveh vrat ˇze odprta in za njimi ni avtomobila, to pomeni, da verjetnost ²₃ pripada zadnjim vratom. Verjetnost avtomobila po zamenjavi je tako ²₃. ˇCe zamenjamo svojo prvotno izbiro, je torej verjetnost za zmago dvakrat tolikˇsna, kot ˇce vztrajamo pri zaˇcetni izbiri.

Bralec, ki je kljub zgornji razlagi ˇse vedno v dvomih, se lahko o pravilnosti reˇsitve prepriˇca ob ogledu naslednje, nekoliko bolj formalne utemeljitve.

Oznaˇcimo zAdogodek, da smo pri zaˇcetni izbiri izbrali vrata, za katerimi se skriva avtomobil, z A pa njegov nasprotni dogodek, torej dogodek, da smo

(27)

3.1. OPIS OSNOVNEGA PROBLEMA IN REˇSITEV 17

pri zaˇcetni izbiri izbrali vrata, za katerimi se skriva koza. Oˇcitno je, da ta dva dogodka skupaj tvorita popoln sistem dogodkov. Dogodek, da smo osvojili avtomobil, bomo oznaˇcili z Z.

Z uporabo izreka o popolni verjetnosti bomo izraˇcunali verjetnost dogodka Z za strategijo, ko vztrajamo pri zaˇcetni izbiri, in tudi za strategijo, ko izbiro vrat zamenjamo. Velja namreˇc P(Z) = P(Z|A)P(A) +P(Z|A)P(A).

Kot smo omenili ˇze v prejˇsnji razlagi, je ne glede na strategijo, P(A) = ¹₃ in P(A) = ²₃.

Oglejmo si najprej primer, ko vztrajamo pri zaˇcetni izbiri. Ce vemo, daˇ smo pri zaˇcetni izbiri izbrali vrata, za katerimi je avtomobil, bomo na koncu zagotovo zmagali, ker bomo vztrajali pri tej izbiri. To pomeni, da je pri tej strategiji P(Z|A) = 1.

Ce vemo, da smo pri zaˇˇ cetni izbiri izbrali vrata, za katerimi ni avtomobila, bomo seveda zagotovo izgubili. torej jeP(Z|A) = 0. Po zgornji formuli torej dobimoP(Z) = 1· ¹₃ + 0· ²₃ = ¹₃.

Na enak naˇcin lahko izraˇcunamo verjetnost dogodka Z v primeru, ko se odloˇcimo za zamenjavo. Tedaj je verjetnost za zmago, ˇce vemo, da smo pri zaˇcetni izbiri izbrali vrata, za katerimi je avtomobil, enaka 0, saj bomo ta vrata zamenjali in izbrali ena izmed preostalih dveh vrat, za katerimi sta kozi. To pomeni, da je pri tej strategiji P(Z|A) = 0.

Verjetnost za zmago, ˇce vemo, da smo pri zaˇcetni izbiri izbrali vrata, za katerimi ni avtomobila, je enaka 1, saj bomo v tem primeru zagotovo zmagali.

Ko namreˇc voditelj odpre ena vrata s kozo, je avtomobil za edinimi preostalimi vrati, ki jih bomo izbrali zaradi naˇse strategije. To pomeni, da je P(Z|A) = 1. Po zgornji formuli tako dobimo P(Z) = 0· ¹₃ + 1· ²₃ = ²₃. Velja opomniti na ne tako zelo oˇcitno dejstvo. Pri obravnavi smo privzeli, da voditelj igre ve, za katerimi vrati je avtomobil, in vedno odpre vrata, za katerimi se skriva koza. Izkaˇze se, da je to kljuˇcni pogoj za to, da naˇs premislek

(28)

velja. V nasprotnem primeru bi bilo namreˇc zares vseeno, ˇce se potem, ko voditelj po nakljuˇcju odpre vrata, odloˇcimo za zamenjavo vrat ali ne. Verje- tnost za osvojitev avtomobila bi bila v obeh primerih enaka ¹₂. Razlog tiˇci v tem, da tedaj dogodek, da voditelj odpre takˇsna vrata, za katerimi se skriva koza, ni gotov, temveˇc je sluˇcajen dogodek. Bralec lahko za vajo poskuˇsa samostojno utemeljiti to trditev.

3.2 Posploˇ sitve problema Monty Hall

V osnovni razliˇcici problema imamo troje vrat in en avtomobil. Oˇcitno je, da je to minimalno ˇstevilo vrat in avtomobilov za obstoj problema.

V nadaljevanju bomo obravnavali nekatere posploˇsitve in strategije odloˇcanja v razliˇcnih primerih. Konkretno si bomo ogledali posploˇsitve na poljubno ˇstevilo vseh vrat, avtomobilov in vrat, ki jih na vsakem koraku odpre voditelj.

S stopnjo posploˇsitve se poveˇcuje tudi zahtevnost problema.

3.2.1 Monty Hall 1.0

V tem podrazdelku se bomo posvetili posploˇsitvi, pri kateri poveˇcamo le ˇstevilo vrat. Pri tem lahko vrata menjamo veˇckrat, vendar vrat, ki smo se jim enkrat odrekli, ne moremo veˇc izbrati, pa tudi voditelj jih ne bo nikdar odprl.

ˇStevilo vrat bomo oznaˇcili z d. Glede na to, da v primeru sodega ˇstevila vrat ne moremo izvesti zadnje zamenjave, se bomo osredotoˇcili na primere, ko je d liho ˇstevilo.

Naj bo d≥3 liho ˇstevilo. Igra se igra na naslednji naˇcin:

1. Izberemo ena vrata iz mnoˇzice zaprtih vrat, ki ˇse niso bila izbrana.

2. Voditelj odpre nakljuˇcna vrata iz mnoˇzice zaprtih vrat, ki ˇse niso bila izbrana in ne skrivajo avtomobila. ˇCe takˇsna vrata ne obstajajo, potem je igre konec in odprejo se vrata, ki so bila izbrana nazadnje. ˇCe

(29)

3.2. POSPLOˇSITVE PROBLEMA MONTY HALL 19

obstajajo, nas po njihovem odprtju vpraˇsa, ali ˇzelimo zamenjati svojo izbiro.

3. V primeru, ko se odloˇcimo, da vrat ne ˇzelimo zamenjati, se odprejo zadnja izbrana vrata. Sicer ponovno sledi korak 1.

Posploˇsitev osnovnega problema, pri kateri veljajo takˇsna pravila igranja, bomo poimenovali Monty Hall 1.0. V nadaljevanju si bomo ogledali, kakˇsna je najboljˇsa strategija igranja, ˇce ˇzelimo osvojiti avtomobil. Najprej si oglejmo konkreten primer.

ZGLED: Igramo igro po pravilih Monty Hall 1.0, kjer je d = 5. Verje- tnosti, da je za trenutno izbranimi vrati avtomobil, bomo rekli “verjetnost avtomobila”.

Verjetnost avtomobila pri prvotni izbiri je (po analogiji z osnovnim problemom) enaka P(A₀) = ¹₅. Potem ko voditelj odpre ena izmed preostalih ˇstirih vrat in pokaˇze, da za njimi ni avtomobila, lahko z zamenjavo vrat izboljˇsamo verjetnost avtomobila. Takrat je namreˇc verjetnost avtomobila preostalih treh vrat enaka P(S)−P(A₀) = 1− ¹₅ = ⁴₅. Glede na to, da je verjetnost avtomobila za vsa tri preostala vrata enaka, dobimo verjetnost poljubnih preostalih vrat tako, da celotno verjetnost delimo s 3. Verjetnost avtomobila po prvi zamenjavi je torej enaka P(A₁) = ₁₅⁴, to pa je veˇc kot prvotnih ¹₅. Z morebitno naslednjo zamenjavo potem, ko voditelj odpre ˇse ena vrata, lahko ˇse dodatno poveˇcamo verjetnost avtomobila. Pred drugo menjavo je namreˇc verjetnost, da je avtomobil za naˇsimi vrati, ₁₅⁴ , da je za enimi izmed preostalih dveh zaprtih vrat, pa ₁₅⁸ . To- rej je po odprtju drugih vrat verjetnost, da je avto za edinimi preostalimi vrati, ₁₅⁸. Verjetnost avtomobila zadnjih vrat je torej enaka verjetnosti prostora izidov, zmanjˇsani za verjetnosti avtomobila pri obeh predhodnih izbirah P(A₂) =P(S)−(P(A₀) +P(A₁)) = 1−(¹₅ + ₁₅⁴) = 1− ₁₅⁷ = ₁₅⁸.

Posvetimo se sedaj problemu Monty Hall 1.0 v vsej sploˇsnosti.

(30)

Izrek 3.1 V primeru, ko igramo igro po pravilih Monty Hall 1.0, se verjetnost, da se za izbranimi vrati skriva avtomobil, poveˇca z vsako zamenjavo vrat. ˇCe z m oznaˇcimo ˇstevilo vrat in velja m >2n, je verjetnost, da so n-ta izbrana vrata prava, enaka

P(An) = (m−1)(m−3)· · ·(m−2n+3) m(m−2)· · ·(m−2n+4)(m−2n+2).

Dokaz: Igramo igro po pravilih Monty Hall 1.0, in sicer tako, da ob vsaki priloˇznosti v igri zamenjamo vrata. ˇStevilo vrat naj bo enakom in naj velja m > 2n. Z A_n oznaˇcimo dogodek, da so n-ta izbrana vrata prava. Pri tem je A₁ dogodek, da so prvotno izbrana vrata prava.

Zanima nas verjetnost dogodka A_n, ki ga lahko zapiˇsemo tudi kot A_n = A_n∩A_n−1 ∩A_n−2 ∩ · · · ∩A₁. To je res zato, ker so dogodki A_i paroma disjunktni in je zato An⊆A1∩A2∩ · · · ∩An−1. Njegovo verjetnost lahko torej izraˇcunamo s pomoˇcjo izreka 2.2 kot P(A_n) =P(A₁)·P(A₂|A₁)·P(A₃|A₁∩ A₂)· · ·P(An−1|A₁∩A₂ ∩ · · · ∩An−2)·P(A_n|A₁∩A₂ ∩ · · · ∩An−1).

Posamezne verjetnosti iz zgornjega produkta lahko relativno preprosto izraˇcunamo na naslednji naˇcin:

• P(A₁) = ^m−1_m , saj je verjetnost, da na zaˇcetku ne izberemo vrat, za katerimi se skriva avtomobil, enaka ˇstevilu vseh vrat, za katerimi ni avtomobila (m −1), deljenemu s ˇstevilom vseh vrat, ki so na izbiro (m).

• P(A2|A1) = ^m−3_m−2, saj je verjetnost, da po prvi menjavi ne izberemo vrat, za katerimi se skriva avtomobil, enaka ˇstevilu vseh preostalih vrat, za katerimi ni avtomobila ((m−1)−2 = m −3), deljenemu s ˇstevilom vseh vrat, ki so ˇse na izbiro (m−2). Na tem mestu namreˇc ˇze vemo (ker se je zgodilA₁), da za prvotno izbranimi vrati in tistimi, ki jih je odprl voditelj, ni avtomobila. Na takˇsen naˇcin lahko izrazimo tudi ostale pogojne verjetnosti iz zgornjega produkta.

(31)

• P(A₃|A₁∩A₂) = ^m−5_m−4 ...

• P(An−1|A₁ ∩A₂∩ · · · ∩An−2) = ^m−2n+3_m−2n+4

• P(A_n|A₁∩A₂∩· · ·∩A_n−1) = ^m−2n+1_m−2n+2 =⇒ P(A_n|A₁∩A₂∩· · ·∩A_n−1) = 1−P(An|A1∩A2∩ · · · ∩An−1) = _m−2n+2¹

Ce zdaj te verjetnosti vstavimo v zgornji produkt, dobimo formulo iz izrekaˇ 3.1.

P(A_n) = m−1

m ·m−3

m−2· · ·m−2n+ 3

m−2n+ 4 · 1 m−2n+ 2

= (m−1)(m−3)· · ·(m−2n+ 3) m(m−2)· · ·(m−2n+ 4)(m−2n+ 2)

Dokaˇzimo zdaj ˇse prvi del izreka, ki pravi, da se verjetnost za osvojitev avtomobila po vsaki zamenjavi vrat poveˇca. To sledi neposredno iz dejstva, da velja P(A_n+1) =P(A_n)· ^m−2n+1_m−2n , saj poslediˇcno velja ^P_P^(A_(Aⁿ⁺¹⁾

n) = ^m−2n+1_m−2n >1

oz. P(An+1)> P(An). 2

V primeru, ko imamo poljubno ˇstevilo vrat (d ≥ 3) in en avtomobil, si torej z zamenjavo vrat na vsakem koraku izboljˇsamo verjetnost za zmago, zato je najboljˇsa strategija vedno zamenjati vrata.

ZGLED: Izraˇcunajmo konˇcno verjetnost avtomobila, ˇce izvedemo maksi- malno ˇstevilo zamenjav v primeru s petimi vrati ˇse z uporabo zgornje formule:

P(5) = ^2·4_3·5 = ₁₅⁸.

(32)

3.2.2 Monty Hall 2.0

Do zdaj smo obravnavali le primere z enim samim avtomobilom. Zdaj si bomo ogledali nadaljnjo posploˇsitev problema s poljubnim ˇsevilom vrat (d), avtomobilov (c) in vrat, ki jih pred zamenjavo odpre voditelj (o). Tokrat so pravila igre sledeˇca.

Naj bo d≥3 in 1≤c≤d−2. Igra se igra na naslednji naˇcin:

1. Izberemo ena vrata iz mnoˇzice vseh d vrat.

2. Voditelj odpre skupinoo nakljuˇcno izbranih vrat iz mnoˇzice preostalih d− 1 vrat, ki ne skrivajo avtomobila. Nato nas vpraˇsa, ali ˇzelimo zamenjati svojo izbiro.

3. V primeru, ko se odloˇcimo, da ne ˇzelimo zamenjati, se odprejo prvotno izbrana vrata. V nasprotnem primeru se odpro vrata, ki jih izberemo izmed preostalihd−2 vrat.

Posploˇsitev problema, pri kateri veljajo takˇsna pravila igranja, bomo poime- novaliMonty Hall 2.0. Od posploˇsitve Monty Hall 1.0 se razlikuje po tem, da lahko voditelj odpre veˇc kot ena vrata in da lahko imamo avtomobile za veˇc kot enimi vrati. Poleg tega se pri posploˇsitvi Monty Hall 2.0 osredotoˇcamo na primer, ko se zgodi najveˇc ena zamenjava.

Ponovno nas zanima, kakˇsna je najboljˇsa strategija za zmago. Povedano drugaˇce, zanima nas, ali naj zamenjamo vrata ali ne, ko imamo za to priloˇznost.

Ce ˇˇ zelimo odgovoriti na to vpraˇsanje, moramo za oba primera poznati verjetnosti, da bomo osvojili avtomobil, torej za primer, ko jih zamenjamo, in za primer, ko jih ne.

Verjetnost osvojitve avtomobila v primeru, ko vrat ne menjamo, je vnaprej znana in je enaka razmerju med ˇstevilom ugodnih izidov in ˇstevilom vseh moˇznih izidov oz. konkretno razmerju med ˇstevilom vrat, za katerimi je avtomobil (c), in ˇstevilom vseh vrat (d). ˇCe svoje izbire vrat ne spremenimo,

(33)

je torej verjetnost osvojitve avtomobila enaka P₀ = ^c_d.

V primeru, ko zamenjamo izbiro, je verjetnost osvojitve avtomobila enaka P₁ = _d(d−1−o)^c(d−1) .

V nadaljevanju bomo razloˇzili, kako pridemo do tega rezultata.

Denimo, da igramo igro po pravilih Monty Hall 2.0. ˇStevilo vrat oznaˇcimo z d, ˇstevilo avtomobilov scin ˇstevilo vrat, ki jih odpre voditelj, zo. Odloˇcili se bomo za zamenjavo vrat. Dogodek, da smo ob zaˇcetni izbiri izbrali vrata, za katerimi se skriva avtomobil, bomo oznaˇcili s C₀, njegov nasprotni dogodek, torej dogodek, da smo ob zaˇcetni izbiri izbrali vrata, za katerimi je koza, pa s C0. Dogodek, da smo ob zamenjavi izbrali vrata, za katerimi se skriva avtomobil, bomo oznaˇcili s C₁, njegov nasprotni dogodek, torej dogodek, da smo ob zamenjavi izbrali vrata, za katerimi je koza, pa s C₁.

Zanima nas verjetnost, da po zamenjavi izberemo vrata, za katerimi je avtomobil, torej P(C₁). Glede na to, da je {C₀, C₀} popoln sistem dogodkov, lahko uporabimo izrek o popolni verjetnosti in zapiˇsemo

P(C₁) = P(C₁|C₀)P(C₀) +P(C₁|C₀)P(C₀).

Pogojno verjetnost dogodka C₁ pri pogoju, da se je zgodil dogodek C₀, zlahka izraˇcunamo kot razmerje med ˇstevilom ugodnih in ˇstevilom vseh izidov pri zamenjavi. Namreˇc ˇce vemo, da se je zgodil dogodekC₀ in smo torej ˇze ob zaˇcetni izbiri izbrali vrata, za katerimi je bil avtomobil, je pri zamenjavi vrat za vsemi vrati, med katerimi izbiramo, en avtomobil manj. ˇStevilo ugodnih izidov je takrat c−1. ˇStevilo vseh vrat, med katerimi izbiramo, se zmanjˇsa za ˇstevilo vrat, ki jih je voditelj odprl, odˇsteti pa je treba ˇse vrata, ki smo jih izbrali na zaˇcetku, zato je vseh moˇznih izidov d−1−o. Tako dobimoP(C₁|C₀) = _d−1−o^c−1 . Da je P(C₀) = _d^c, smo utemeljili ˇze zgoraj.

Pogojno verjetnost dogodkaC₁ pri pogoju, da se je zgodil dogodekC₀, lahko izraˇcunamo na enak naˇcin. ˇCe vemo, da se je zgodil dogodekC₀ in smo torej ob zaˇcetni izbiri izbrali vrata, za katerimi ni bilo avtomobila, je pri zamenjavi vrat na voljo isto ˇstevilo avtomobilov kot na zaˇcetku. ˇStevilo ugodnih

(34)

izidov je takrat ˇse vednoc. ˇStevilo vseh vrat, med katerimi izbiramo, je kot v prejˇsnjem primeru d−1−o. Tako dobimo P(C₁|C₀) = _d−1−o^c . Seveda je P(C₀) = 1−P(C₀) = ^d−c_d .

Verjetnost, da bomo pri zamenjavi izbrali vrata, za katerimi je avtomobil, je torej enaka

P(C₁) = c(c−1)

d(d−1−o) + c(d−c)

d(d−1−o) = c(c−1 +d−c)

d(d−1−o) = c(d−1) d(d−1−o). Enaˇcbo lahko zapiˇsemo kot produktP₁ = _d^c·_d−1−o^d−1 =P₀·_d−1−o^d−1 . Opazimo, da je verjetnost osvojitve avtomobila v primeru, ko vrata zamenjamo, enaka verjetnosti v primeru, ko vrat ne zamenjamo, pomnoˇzeni s faktorjem _d−1−o^d−1 . V posebnem primeru, ko voditelj ne odpre nobenih vrat, je faktor enak ^d−1_d−1 = 1 in velja P1 =P0. To pomeni, da se verjetnost pri zamenjavi v tem primeru ne spremeni, kar je seveda tudi intuitivno jasno. Nasprotno pa se vedno, ko se vrata odprejo in torej velja o > 0 ter poslediˇcno _d−1−o^d−1 > 1, verjetnost osvojitve avtomobila po menjavi vrat poveˇca.

Zato je najboljˇsa strategija pri igranju igre po pravilu Monty Hall 2.0 zamenjati vrata.

ZGLED: Imamo deset vrat in dva avtomobila (d = 10, c = 2). Oglejmo si, kako se spremeni verjetnost osvojitve avtomobila, ˇce zamenjamo vrata.

Verjetnost osvojitve avtomobila ob zaˇcetni izbiri vrat je enaka _d^c = ₁₀². ˇCe vrata zamenjamo potem, ko voditelj odpre ena vrata (o = 1), je verjetnost osvojitve avtomobila enaka 10·(10−1−1)^2·(10−1) = ¹⁸₈₀ = ₄₀⁹, kar pomeni izboljˇsanje za 12,5 %. ˇCe vrata zamenjamo potem, ko voditelj odpre dvoje vrat (o = 2), je verjetnost osvojitve avtomobila enaka 10·(10−1−2)^2·(10−1) = ¹⁸₇₀, kar pomeni izboljˇsanje za 28,6 %. ˇCe bi voditelj odprl troje vrat, bi bila verjetnost osvojitve avtomobila po zamenjavi vrat enaka ¹⁸₆₀ = ₁₀³ , kar pomeni izboljˇsanje za 50 %.

Lahko se vpraˇsamo, kakˇsna je verjetnost za osvojitev avtomobila, ˇce se igra nadaljuje in voditelj ponovno odpre nekaj vrat, za katerimi so koze, ter nas

(35)

vpraˇsa, ali ˇzelimo zamenjati vrata. Ta primer bomo obravnavali v naslednjem podrazdelku.

3.2.3 Monty Hall 3.0

Pri posploˇsitvi Monty Hall 2.0 smo privzeli, da je najveˇcje moˇzno ˇstevilo zamenjav 1. Zdaj bomo obravnavali nadaljnjo posploˇsitev, pri kateri je moˇznih veˇc zamenjav.

Naj bo d≥3 in 1≤c≤d−2. Igra se igra na naslednji naˇcin:

1. Izberemo ena vrata iz mnoˇzice zaprtih vrat, ki ˇse niso bila izbrana. ˇCe takˇsnih vrat ni, je igre konec in odprejo se zadnja izbrana vrata.

2. Voditelj odpre skupino o_k nakljuˇcno izbranih vrat iz mnoˇzice zaprtih vrat, ki ˇse niso bila izbrana in ne skrivajo avtomobila. ˇCe takˇsnih vrat ni dovolj, je igre konec in odprejo se zadnja izbrana vrata. Sicer pa nas voditelj po odprtju vrat vpraˇsa, ali ˇzelimo zamenjati svojo izbiro.

3. V primeru, ko se odloˇcimo, da ne ˇzelimo zamenjati vrat, se odprejo zadnja odprta vrata, sicer ponovno sledi korak 1.

Posploˇsitev problema, pri kateri veljajo takˇsna pravila igranja, bomo poimenovali Monty Hall 3.0.

Denimo zdaj, da igramo igro po pravilih Monty Hall 3.0, v kateri je d vrat in c avtomobilov. Potem ko smo na zaˇcetku izbrali neka vrata, je voditelj igre odprl o₁ vrat, za katerimi so bile koze. Ko nam je ponudil moˇznost zamenjave, smo vrata zamenjali. Nato je voditelj odprl o2 vrat, za katerimi so prav tako bile koze, in mi smo ponovno zamenjali vrata. V tretjem in naslednjih korakih se je potek igre ponovil. Zanima nas, kakˇsna je verjetnost avtomobila po s-ti zamenjavi.

(36)

Izrek 3.2 Verjetnost za osvojitev avtomobila po s-ti zamenjavi v igri, ki jo igramo po pravilih Monty Hall 3.0, je

P_s= c(d−1)(d−2−o1)· · ·(d−s−o1− · · · −os−2−os−1) d(d−1−o₁)(d−2−o₁−o₂)· · ·(d−s−o₁− · · · −os−1−o_s). Izreka 3.2 ne bomo dokazovali v sploˇsnem. V nadaljevanju si bomo ogledali zgolj dokaz za primer, ko je s = 2. Sploˇsni dokaz gre z indukcijo na ˇstevilo zamenjav.

Oglejmo si torej primer, ko se zgodita dve zamenjavi. S C_k bomo oznaˇcili dogodek, da smo pok-ti menjavi izbrali vrata, za katerimi je avtomobil, in s Ck dogodek, da smo pok-ti menjavi izbrali vrata, za katerimi ni avtomobila.

Zanima nas verjetnost, da po drugi zamenjavi izberemo vrata, za katerimi je avtomobil, torejP(C₂). Glede na to, da je{C₀∩C₁, C₀∩C₁, C₀∩C₁, C₀∩C₁} popoln sistem dogodkov, lahko uporabimo izrek o popolni verjetnosti in zapiˇsemo

P(C₂) =P(C₂|C₀∩C₁)P(C₀ ∩C₁) +P(C₂|C₀∩C₁)P(C₀ ∩C₁) +P(C₂|C₀∩C₁)P(C₀ ∩C₁) +P(C₂|C₀∩C₁)P(C₀ ∩C₁), oziroma

P(C₂) = P(C₂∩C₁∩C₀) +P(C2∩C1∩C0) +P(C₂∩C₁∩C₀) +P(C₂∩C₁∩C₀).

Vsakega izmed teh ˇstirih ˇclenov zlahka izraˇcunamo s pomoˇcjo izreka 2.2.

Tako je na primer P(C₂∩C₁∩C₀) =P(C₀)·P(C₁|C₀)·P(C₂|C₀∩ ∩C₁) =

d−c

d ·^{d−c−1−o}_d−1−o ¹

1 ·_d−2−o^c

1−o₂, saj je verjetnost, da pri zaˇcetni izbiri izberemo kozo enaka razmerju med ˇstevilom koz (d−c) in ˇstevilom vseh vrat (d), verjetnost,

(37)

da nato ponovno izberemo kozo, pa prav tako to razmerje s to razliko, da je pri zamenjavi ena koza manj zato, ker smo jo izbrali ˇze na zaˇcetku, in ˇse o₁ koz manj, saj jih je razkril voditelj igre. ˇStevilo koz ob prvi zamenjavi je zato enako d−c−1−o₁, ˇstevilo vseh vrat, med katerimi izbiramo, pa je zmanjˇsano za na zaˇcetku izbrana vrata in vrata, ki jih je odprl voditelj, ter znaˇsa d−1−o₁. Tudi pogojno verjetnost P(C₂|C₀∩C₁) lahko izrazimo kot razmerje med ˇstevilom preostalih avtomobilov (c) in ˇstevilom vseh preostalih vrat, med katerimi izbiramo, torej ˇstevilom vrat na zaˇcetku, zmanjˇsanim za ˇstevilo do tedaj izbranih vrat (2), in ˇstevilom vrat, ki jih je voditelj odprl pred prvo (o₁) in pred drugo zamenjavo (o₂). DobimoP(C₂|C₀∩C₁) = _d−2−o^c

1−o2. Na enak naˇcin izraˇcunamo tudi preostale tri ˇclene vsote.

• P(C₂∩C₁∩C₀) = ^d−c_d · ^{d−c−1−o}_d−1−o ¹

1 · _d−2−o^c

1−o2

• P(C₂∩C₁∩C₀) = ^d−c_d · _d−1−o^c

1 · _d−1−o^c−1

1−o2

• P(C₂∩C₁∩C₀) = ^c_d· ^d−c−o_d−1−o¹

1 · _d−2−o^c−1

1−o2

• P(C₂∩C₁∩C₀) = ^c_d· _d−1−o^c−1

1 · _d−2−o^c−2

1−o2

Verjetnost, da po drugi zamenjavi izberemo vrata, za katerimi je avtomobil, je torej:

P(C₂) = c[(d−c)(d−c−1−o1) + (d−c)(c−1) + (d−c−o1)(c−1) + (c−1)(c−2)]

d(d−1−o₁)(d−2−o₁−o₂)

= c[(d−c)(d−c−1−o₁+c−1) + (c−1)(d−c−o₁+c−2)]

d(d−1−o₁)(d−2−o₁−o₂)

= c[(d−c)(d−2−o₁) + (c−1)(d−2−o₁)]

d(d−1−o₁)(d−2−o₁−o₂)

= c(d−2−o1)(d−c+c−1) d(d−1−o₁)(d−2−o₁ −o₂)

= c(d−2−o₁)(d−1) d(d−1−o₁)(d−2−o₁ −o₂)

= c(d−1)(d−2−o₁) d(d−1−o₁)(d−2−o₁ −o₂), kar se ujema s formulo iz izreka 3.2.

(38)

ZGLED: Igramo igro po pravilih Monty Hall 3.0, v kateri je 15 vrat in 6 avtomobilov. Pred prvo zamenjavo voditelj igre odpre 3 vrata, pred drugo zamenjavo 1 vrata in pred tretjo zamenjavo dvoje vrat. Kakˇsna je najboljˇsa strategija pri tej igri?

Najboljˇsa strategija je seveda tista, ki nam zagotovi najveˇcjo verjetnost za osvojitev avtomobila. Glede na to, da je verjetnost pri zaˇcetni izbiri enaka P₀ = 0,4, po prvi zamenjavi P₁ = _15·11^6·14 ≈ 0,509, po drugi P₂ = ^6·14·10_15·11·9 ≈ 0,566 in po tretji P₃ = ^6·14·10·8_15·11·9·6 ≈ 0,754, je najboljˇsa strategija vsakokrat zamenjati vrata.

V igri Monty Hall 3.0 je menjava vrat ob vsaki priloˇznosti vedno najboljˇsa strategija. Verjetnost za osvojitev avtomobila se na n-tem koraku poveˇca za faktor _(d−o^(d−o¹^−o²^{−···−o}ⁿ⁻¹⁻ⁿ⁾

1−o2−···−on−1−on−n) >1.

(39)

Poglavje 4

Raˇ cunalniˇ ska simulacija problema

V tem poglavju bomo predstavili program Monty Hall simulator (beta) in rezultate raˇcunalniˇskih simulacij problema Monty Hall oz. njegovih po- sploˇsitev.

4.1 Opis programa Monty Hall simulator

Simulacije so bile izvedene z uporabo programaMonty Hall simulator (beta), ki sem ga napisal v programskem jezikuC#. Namen programa je, da simulira posploˇsitve problema Monty Hall, ki jih obravnavamo v tem diplomskem delu. Dostopen je na naslednjem spletnem naslovu:

https://www.dropbox.com/s/pcpc3g9xz3qlrp0/Monty%20Hall.exe.

4.1.1 Videz in gradniki aplikacije

Po zagonu se program odpre v oknu, ki vsebuje menijsko vrstico, dva radijska gumba, ˇstiri vnosna polja za ˇstevila in gumb za zaˇcetek simulacije.

S pritiskom na ustrezen radijski gumb izberemo, katero posploˇsitev problema ˇzelimo simulirati. ˇCe izberemo posploˇsitev Monty Hall 2.0 oz. Monty Hall 3.0, se prikaˇzejo ˇse vnosna polja, ki omogoˇcajo vnos ˇstevila odprtih vrat

29

(40)

30 POGLAVJE 4. RA ˇCUNALNIˇSKA SIMULACIJA PROBLEMA

na vsakem koraku igre. Slika 4.1 prikazuje videz aplikacije v naˇcinu, ko simuliramo posploˇsitev Monty Hall 1.0 in posploˇsitvi Monty Hall 2.0 oz.

Monty Hall 3.0.

Slika 4.1: Videz aplikacije pri simuliranju razliˇcnih posploˇsitev

4.1.2 Uporaba in delovanje

V ˇstirih osnovnih vnosnih poljih nastavimo ˇstevilo vrat, avtomobilov, zamenjav in zaporednih poskusov, ki jih ˇzelimo simulirati. Privzete vrednosti teh parametrov so najmanjˇse moˇzne vrednosti, pri katerih je igra ˇse smiselna, to je troje vrat in en avtomobil. Program onemogoˇca nastavitev neveljavnih vrednosti parametrov.

Simuliranje posploˇsitve Monty Hall 1.0

Pri posploˇsitvi Monty Hall 1.0 nastopa vedno samo en avtomobil, zato je vnosno polje za vnos ˇstevila avtomobilov onemogoˇceno, njegova vrednost pa je vedno 1. Nastaviti moramo samo ˇstevilo vrat in ˇstevilo zamenjav. Nato vnesemo ˇstevilo poskusov, ki jih ˇzelimo simulirati. Privzeta vrednost tega parametra je 1.000.000.

Ko zakljuˇcimo z vnosom podatkov o simulaciji, kliknemo gumb “Zaˇcni simu- lacijo”. Po zakljuˇcku simulacije se v sporoˇcilnem oknu izpiˇsejo verjetnost za osvojitev avtomobila v simulaciji in verjetnost, izraˇcunana po formuli iz pod- razdelka 3.2.1 za uporabljene parametre, ter razlika med obema podatkoma,

(41)

4.1. OPIS PROGRAMA MONTY HALL SIMULATOR 31

izraˇzena v odstotkih. Primer sporoˇcilnega okna z rezultati pri simulaciji po- sploˇsitve Monty Hall 1.0 je prikazan na Sliki 4.2.

Slika 4.2: Sporoˇcilno okno z rezultati simulacije Monty Hall 1.0

Simuliranje problemov Monty Hall 2.0 in Monty Hall 3.0

Ce izberemo posploˇsitvi Monty Hall 2.0 in Monty Hall 3.0, se prikaˇˇ ze 6 dodatnih vnosnih polj za vnos ˇstevil na desni strani okna, kot je prikazano na Sliki 4.3.

Slika 4.3: Polja za vnos ˇstevila odprtih vrat pred zamenjavo

Ta polja so na zaˇcetku, ko je ˇstevilo zamenjav nastavljeno na 0, onemogoˇcena.

(42)

ˇStevilo omogoˇcenih polj je nato enako ˇstevilu zamenjav. V njih nastavimo, koliko vrat naj se odpre pred vsako zamenjavo. Vsota teh vrednosti mora biti ob zaˇcetku simulacije manjˇsa kot ˇstevilo vrat, ki skrivajo koze, saj je v nasprotnem primeru poskus nesmiseln. Na to nas opozori sporoˇcilno okno, ki je prikazano na Sliki 4.4.

Slika 4.4: Sporoˇcilno okno, ki opozarja na neustreznost vnesenih podatkov Poleg tega je mogoˇce nastavljati tudi ˇstevilo avtomobilov. Izpis rezultatov je enak kot pri simulaciji posploˇsitve Monty Hall 1.0.

4.2 Rezultati simulacije posploˇ sitve Monty Hall 1.0

Simulacije smo izvedli za primere, ko je vrat 3, 5, 7, 9 in 11. Za primer, ko je vrat d, smo izvedli posamezne simulacije za ˇstevilo zamenjav od 0 do ^d−1₂ . V prvem stolpcu tabele rezultatov simulacije se nahaja podatek o ˇstevilu vrat (d), v drugem pa podatek o ˇstevilu zamenjav (z). V tretjem stolpcu je verjetnost osvojitve avtomobila, izraˇcunana po formuliP_f = (d−1)(d−3)···(d−2·(z−1)−1) d(d−2)···(d−2·(z−1)) ·

1

d−2·(z−1)−2, v petem pa verjetnost osvojitve avtomobila v simulaciji glede na relativno frekvenco zmag (P_s). Ta verjetnost je izraˇcunana po formuli P_s = st.ugodnihposkusov

st.vsehposkusov . V ˇcetrtem in ˇsestem stolpcu je podatek o spremembi verjetnosti glede na primer z za ena manjˇsim ˇstevilom zamenjav (+/−). V zadnjem stolpcu je podatek o odstopanju verjetnosti iz simulacije od dejanske verjetnosti, izraˇcunane po formuli (Razlika [%]). Ta podatek je izraˇzen v odstotkih glede na verjetnost 1. Pri vsaki simulaciji je bilo izvedenih 1.000.000

(43)

4.2. REZULTATI SIMULACIJE POSPLOˇSITVE MONTY HALL 1.0 33

poskusov.

Razlika med obema verjetnostima je bila zanemarljiva. Verjetnost osvojitve avtomobila v simulaciji se je v povpreˇcju od verjetnosti, izraˇcunane po formuli, razlikovala za 0,29 h, najviˇsja pa je bila 0,72 h.

Rezultati simulacije potrjujejo, da je pri posploˇsitvi Monty Hall 1.0 zamenjava vrat pri vsaki priloˇznosti vselej najboljˇsa strategija, saj se je za vse simulirane primere verjetnost osvojitve avtomobila po vsaki zamenjavi vrat poviˇsala.

(44)

Tabela 4.1: Rezultati simulacije Monty Hall 1.0 (n = 1000000)

d z P_f +/− P_s +/− Razlika [%]

3 0 0,33333 / 0,33405 / 0,072

3 1 0,66667 0,33334 0,66641 0,33236 −0,026

5 0 0,2 / 0,20009 / 0,009

5 1 0,26667 0,06667 0,26649 0,0664 −0,018 5 2 0,53333 0,26666 0,53327 0,26678 −0,006

7 0 0,14286 / 0,14305 / 0,019

7 1 0,17143 0,02857 0,17114 0,02809 −0,029 7 2 0,22857 0,05714 0,22839 0,05725 −0,018 7 3 0,45714 0,22857 0,45746 0,22907 0,032

9 0 0,11111 / 0,11133 / 0,022

9 1 0,12698 0,01587 0,12693 0,0156 −0,005 9 2 0,15238 0,0254 0,15211 0,02518 −0,027 9 3 0,20317 0,05079 0,20335 0,05124 0,018 9 4 0,40635 0,20318 0,40686 0,20351 0,051

11 0 0,09091 / 0,09125 / 0,034

11 1 0,10101 0,0101 0,10127 0,01002 0,026 11 2 0,11544 0,01443 0,11528 0,01401 −0,016 11 3 0,13853 0,02309 0,138 0,02272 −0,053 11 4 0,1847 0,04617 0,1842 0,0462 −0,05 11 5 0,36941 0,18471 0,36997 0,18577 0,056

(45)

4.3. REZULTATI SIMULACIJE POSPLOˇSITVE MONTY HALL 2.0 35

4.3 Rezultati simulacije posploˇ sitve Monty Hall 2.0

Simulacije smo izvedli za primer z 10 vrati in 1, 2 oz. 3 avtomobili. Za vsak csmo izvedli posamezne simulacije za ˇstevilo vrat, odprtih pred zamenjavo, od 0 do 10−(c+ 1).

V prvem stolpcu tabele rezultatov simulacije se nahaja podatek o ˇstevilu vrat (d), v drugem podatek o ˇstevilu avtomobilov (c) in v tretjem podatek o ˇstevilu vrat, odprtih pred zamenjavo (o). V ˇcetrtem stolpcu je verjetnost osvojitve avtomobila, izraˇcunana po formuli P_f = _d(d−1−o)^c(d−1) , v ˇsestem pa verjetnost osvojitve avtomobila v simulaciji glede na relativno frekvenco zmag (P_s). V petem in sedmem stolpcu je podatek o spremembi verjetnosti glede na primer z za ena manjˇsim ˇstevilom odprtih vrat (+/−). V zadnjem stolpcu je podatek o odstopanju verjetnosti iz simulacije od dejanske verjetnosti, izraˇcunane po formuli (Razlika[%]). Ta podatek je izraˇzen v odstotkih glede na verjetnost 1. Pri vsaki simulaciji je bilo izvedenih 1.000.000 poskusov.

Razlika med obema verjetnostma je bila zanemarljiva. Verjetnost osvojitve avtomobila v simulaciji se je v povpreˇcju od verjetnosti, izraˇcunane po formuli, razlikovala za 0,18 h, najviˇsja pa je bila 0,52 h.

V rezultatih simulacije se je verjetnost osvojitve avtomobila po menjavi vrat potem, ko so bila odprta vsaj ena vrata, vselej poveˇcala v primerjavi s prime- rom, ko se zamenjava vrat ni zgodila (o = 0). Iz rezultatov je razvidno, da z viˇsanjem ˇstevila odprtih vrat pred menjavo naraˇsˇca tudi verjetnost osvojitve avtomobila.

(46)

Tabela 4.2: Rezultati simulacije Monty Hall 2.0 (n = 1000000) d c o P_f +/− P_s +/− Razlika [%]

10 1 0 0,10000 / 0,09970 / −0,03

10 1 1 0,11250 0,01250 0,11248 0,01278 −0,002 10 1 2 0,12857 0,01607 0,12858 0,01610 0,001 10 1 3 0,15000 0,02143 0,15038 0,02180 0,038 10 1 4 0,18000 0,03000 0,17966 0,02928 −0,034 10 1 5 0,22500 0,04500 0,22498 0,04532 −0,002 10 1 6 0,30000 0,07500 0,29998 0,07500 −0,002 10 1 7 0,45000 0,15000 0,44980 0,14982 −0,02 10 1 8 0,90000 0,45000 0,90014 0,45034 0,014

10 2 0 0,20000 / 0,20011 / 0,011

10 2 1 0,22500 0,02500 0,22448 0,02437 −0,052 10 2 2 0,25714 0,03214 0,25704 0,03256 −0,01 10 2 3 0,30000 0,04286 0,30012 0,04308 0,012 10 2 4 0,36000 0,06000 0,36009 0,05997 0,009 10 2 5 0,45000 0,09000 0,44982 0,08973 −0,018 10 2 6 0,60000 0,15000 0,60026 0,15044 0,026 10 2 7 0,90000 0,30000 0,90016 0,29990 0,016

10 3 0 0,30000 / 0,29990 / −0,01

10 3 1 0,33750 0,03750 0,33774 0,03784 0,024 10 3 2 0,38571 0,04821 0,38547 0,04773 −0,024 10 3 3 0,45000 0,06429 0,44977 0,06430 −0,023 10 3 4 0,54000 0,09000 0,54014 0,09037 0,014 10 3 5 0,67500 0,13500 0,67499 0,13485 −0,001 10 3 6 0,90000 0,22500 0,89968 0,22469 −0,032