Problema cunoscuta sub numele Monty Hall sau Let's make a deal este o problema de probabilitati a carei solutie pare nefireasca. Ea este legata de emisiunile/spectacolele TV cu aceste nume.
Formularea problemei:
Emisiune concurs: in spatele a trei usi este plasata o masina (sau un bilet de vacanta, o suma mare de bani), respectiv doua capre (sau orice altceva avand o valoare cu mult mai redusa fata de oferta din spatele usii cu valoare).
Concurentul alege o usa, dar nu o deschide. Prezentatorul in schimb deschide o alta usa in spatele careia stie sigur ca este o capra si apoi il intreaba pe concurent: vrei sa schimbi usa?
Intrebarea careia incercam sa-i raspundem teoretic si prin simularea jocului este urmatoarea: ar trebui sa schimbe concurentul usa pentru a-si mari sansa de a o nimeri pe cea "valoroasa"?
Video-ul urmator prezinta ideea de baza a concursului Let's make a deal:
In [1]:
from IPython.display import YouTubeVideo
YouTubeVideo('mhlc7peGlGg#t=15')
Out[1]:
Codificam masina cu "m" si capra cu "c". Avem $3$ posibilitati de plasare a masinii si celor doua capre in trei incaperi:
$\Omega=\{(m, c, c), (c, m, c), (c, c, m)\}$
Daca concurentul alege o usa la intamplare el are sansa de a castiga de $1/3$.
Dupa ce i s-a aratat o usa in care este o capra, suntem tentati sa spunem ca sansa de a castiga, alegand oricare din usile ramase este:
$P(\mbox{castig}|U_d=c)=1/2$, unde $(U_d=c)$ este evenimentul ca in spatele usii deschise de prezentator sa fie o capra.
Cu alte cuvinte, rationamentul comun conduce la ideea ca n-are importanta daca concurentul pastreaza usa aleasa sau schimba usa. Dar este incorect!!!!!
Notam cu $H_k$, $k=1,2,3$, ipotezele privind amplasarea premiilor in spatele celor trei usi, si anume $(m,c,c)$, $(c,m,c)$, $(c,c,m)$.
Probabilitatile apriori ale acestor ipoteze sunt $P(H_k)=1/3$, $k=1,2,3$.
Presupunem pentru simplitatea prezentarii ca concurentul alege usa 1, iar prezentatorul deschide usa 2, in spatele careia stie sigur ca este o capra.
Conform formulei lui Bayes, probabilitatea ca masina sa fie plasata in spatele usii alese de concurent, rectificata de informatia ca in spatele usii $2$ e o capra este:
$P(H_1|U_2)=\displaystyle\frac{P(H_1)P(U_2|H_1)}{P(H_1)P(U_2|H_1)+P(H_2)P(U_2|H_2)+P(H_3)P(U_2|H_3)}$
Deoarece $P(U_2|H_2)=0$ (adica stiind ca masina este in spatele usii 2, probabilitatea ca prezentatorul sa deschida aceasta usa este 0), avem:
$P(H_1|U_2)=\displaystyle\frac{P(H_1)P(U_2|H_1)}{P(H_1)P(U_2|H_1)+P(H_3)P(U_2|H_3)}$
$P(U_2|H_1)=1/2$, deoarece stiind ca masina este in spatele usii 1 (avem conditionare de evenimentul $H_1)$) prezentatorul alege uniform intre cele doua usi $2$ si $3$.
Daca deschiderea unei usi este conditionata de $H_3$, adica stie ca in spatele usii 3 este masina, iar concurentul a ales usa 1, nu-i ramane decat sa deschida usa 2, si nici intr-un caz usa 3. Prin urmare avem $P(U_2|H_3)=1$.
Inlocuind in formula lui Bayes rezulta ca:
$P(H_1|U_2)=\displaystyle\frac{(1/3)(1/2)}{(1/3)(1/2)+(1/3) 1}=\displaystyle\frac{1/6}{1/6+1/3}=1/3$
Deoarece $H_1\cup H_2\cup H_3=\Omega$, avem ca: $P_{U_2}(H_1\cup H_2\cup H_3)=P_{U_2}(\Omega)=1$.
Ipotezele $H_1, H_2, H_3$ fiind mutual exclusive, iar functia $P_{U_2}$ fiind o functie de probabilitate, rezulta ca:
$P(H_1|U_2)+P(H_2|U_2)+P(H_3|U_2)=1$.
Evident, $P(H_2|U_2)=0$ si astfel probabilitatea ca masina sa fie in spatele usii 3, stiind ca in spatele celei de-a doua este o capra, este:
$P(H_3|U_2)=1-P(H_1|U_2)=1-1/3=2/3$.
Deci daca concurentul se hotaraste sa schimbe usa 1, aleasa initial, cu unica posibilitate, adica usa 3, atunci sansa de a castiga masina este dubla fata de cazul in care pastreaza usa initiala.
Rationamentul si rezultatul este identic pentru orice alta alegere a concurentului si respectiv a prezentatorului.
Sa ilustram acest rezultat prin simulare in Python a jocului. Adica repetam experimentul alegerii
de un numar $Nr$ de ori, fie cu optiunea de schimabare a usii alese initial, fie fara schimbare si numaram de cate ori castiga, adica nimereste usa ce are in spatele ei o masina.
In [2]:
import random as rnd
from __future__ import division # importand division m/n este evaluat ca float(m)/n
In [3]:
def alegeUsa(A): #alege dintr-o lista de 3 elemente din care doua sunt setate pe 'c' si una pe'm'
Conc=A.pop(rnd.randint(0, 2))#alegerea concurentului
Prez= A.pop(A.index('c'))#alegerea prezentatorului emisiunii
return Conc, Prez
De exemplu, daca amplasarea premiilor este A=['c', 'm', 'c'] atunci rnd.randint(0,2) genereaza aleator un indice $i$ al
elementelor listei $A$.
A.pop(i) returneaza
elementul A[i] si il sterge din lista (vezi
aici metode pentru liste).
Ilustrarea prin rularea liniilor de cod aferente:
In [4]:
A=['c', 'm', 'c']
Conc=A.pop(rnd.randint(0, 2))
print Conc
print A
A.index('c') returneaza indicele primului element din lista ramasa, care este egal cu 'c' si astfel prezentatorul
alege o usa in spatele careia este o capra: Prez=A.pop(A.index('c')).
Dupa executia acestei linii in lista A
ramane doar un singur element.
In [5]:
def Monty_Hall(A, schimba=True):
#A este tripletul ce da amplasarea obiectelor in spatele usilor
Conc, Prez=alegeUsa(A)# Concurentul si prezentatorul aleg cate o usa conform regulii jocului
if (schimba):
alegerea=A[0]#in lista mai exista un singur element si aceasta este alegerea noua
else:
alegerea=Conc
return alegerea
In [6]:
def simulare_MH(Nr, optiune):#repeta experimentul MH de Nr ori cu optiunea schimba (True sau False)
nrcastig=0
for n in range(Nr):
A=rnd.choice([['m', 'c', 'c'],['c', 'm', 'c'],['c', 'c', 'm']])# alege la intamplare o amplasare
# a premiilor din cele 3 posibile
rez=Monty_Hall(A, schimba=optiune)
if rez=='m':
nrcastig+=1
return nrcastig
Inainte de a experimenta jocul sintetizam principiul de implementare:
Nr ori, fie cu optiunea alege o noua usa dupa ce prezentatorul a deschis usa cu capra, fie nu alege.alegeUsa face alegerea aleatoare a usii pentru concurent si pentru prezentator.
In [7]:
opt_schimb=True# optiunea schimba sau nu
Nr=1000
nrc=simulare_MH(Nr, opt_schimb)
print "Probabilitatea sa castige daca schimba usa aleasa=", nrc/Nr
nrc=simulare_MH(Nr, False)
print "Probabilitatea sa castige daca nu schimba usa aleasa=", nrc/Nr
Orice varianta ati incerca, probabilitatea de castig este aproximativ 0.33, daca nu schimba usa aleasa initial si respectiv aproximativ 0.66, daca o schimba.
Deci daca jucati, alegeti sa schimbati usa!!
... si in final, solutia data de xkcd
In [8]:
from IPython.display import Image
Image(url='http://imgs.xkcd.com/comics/monty_hall.png')
Out[8]:
In [9]:
from IPython.core.display import HTML
def css_styling():
styles = open("./custom.css", "r").read()
return HTML(styles)
css_styling()
Out[9]: