DM Probabilité et Simulation
Ergi SALA, Tom SOLVERY - INFO4 Polytech
Sujet : Au Casino
Lors de ce DM, nous nous trouvons au casino face aux deux machines A et B avec lesquels, chaque partie jouée nous apport 0 ou 1 €. Notre objectif est d’évaluer différentes stratégies de jeu ayant pour objectif de maximiser notre gain cumulé sur un nombre T de parties. Pour faciliter notre tache et mieux visualiser le résultat, nous utilisons deux packages sur R, ggplot et dplyr.
library(ggplot2)
library(dplyr, warn.conflicts = F)
pA = 0.65
pB = 0.55
Tmax = 1000
set.seed(NULL)
Gain1Partie = function (proba){
sample(c(1,0),1,replace=T, prob=c(proba,1-proba))
}Q1 : Questions préliminaires
Il est clair que la variable aléatoire \(X_{m(t),t}\) suit une loi de Bernoulli de probabilité \(p_m\). Le gain \(G_m(T)\) suit une loi Binomiale parce que il est une addition de plusieurs tirages de Bernoulli. Nous connaissons alors l’esperance \(\mathbb{E}[G_m(T)] = T\cdot p_m\).
- Si nous jouons systématiquement la machine \(M_A\) alors \(\mathbb{E}[G_m(T)] = T\cdot p_A\)
- Si nous jouons systématiquement la machine \(M_B\) alors \(\mathbb{E}[G_m(T)] = T\cdot p_B\)
- Si nous jouons la machine \(M_A\) avec probabilité 1/2 et la machine \(M_B\) avec probabilité 1/2 alors, sachant que à chaque tour le choix de la machine est indépendant du choix précedent, la probabilité de gain vaut \(\dfrac12p_a+\dfrac12p_b\) d’ou une esperance de \(\mathbb{E}[G_m(T)] = \dfrac12T\cdot (p_a+p_b)\)
- \(p_A\) est la probabilité de gain de la machine A, à priori plus grand. \(\dfrac{\mathbb{E}[G_m(t)]}t\) est une estimation de la probabilité de gain de la stratégie qu’on a adoptée. Le regret est alors un écart entre ces deux probabilités et peut servir comme un indice d’efficacité de notre stratégie. On veut que le regret soit le plus petit possible.
Voici une première simulation des cas ou on joue que sur une seul machine. Comme attendu, le regret si on utilise que la machine A est 0 et pour B autour de 0.1 (0.65 - 0.55)
RegQ1_1 = function () {
df=data.frame()
for (j in 1:100){
regret = c()
esperance = 0
abs=c()
for(i in 1:Tmax){
esperance = esperance + Gain1Partie(pA)
regret[i]=pA-(esperance/i)
abs[i]=i
}
ajout = data.frame(regret,abs)
ajout=cbind(j,ajout)
df=rbind(df, ajout)
}
df2 = df%>%group_by(abs)%>%summarise(avg=mean(regret))
ggplot() + geom_line(data=df, aes(x=abs, y=regret, group=j), alpha=0.15) +
geom_line(data=df2, aes(x=abs, y=avg), color='red') + ylim(-0.5,0.5)
}
RegQ1_2 = function () {
df=data.frame()
for (j in 1:100){
regret = c()
esperance = 0
abs=c()
for(i in 1:Tmax){
esperance = esperance + Gain1Partie(pB)
regret[i]=pA-(esperance/i)
abs[i]=i
}
ajout = data.frame(regret,abs)
ajout=cbind(j,ajout)
df=rbind(df, ajout)
}
df2 = df%>%group_by(abs)%>%summarise(avg=mean(regret))
ggplot() + geom_line(data=df, aes(x=abs, y=regret, group=j), alpha=0.15) +
geom_line(data=df2, aes(x=abs, y=avg), color='red') + ylim(-0.5,0.5)
}
RegQ1_1()
RegQ1_2()
Q2. On apprend (un peu) puis on exploite
Une premiere approche serait d’étudier le regret de la stratégie consistant à consacrer les ε.T premières parties (avec ε = 0.05 par exemple) à estimer les probabilités pA et pB et à ensuite jouer systématiquement la machine la plus prometteuse.
RegQ2 = function () {
df=data.frame()
for (j in 1:100){
regret = c()
A = c() # Victoires avec A
B = c() # Victoires avec B
esperance = c()
abs=c()
k = 1
while(k > Tmax*0.025){
A[k]=Gain1Partie(pA)
esperance = append(A,B)
regret[k]=pA-(sum(esperance)/(k))
abs[k]=k
k = k+1
B[k]=Gain1Partie(pB)
esperance = append(A,B)
regret[k]=pA-(sum(esperance)/(k))
abs[k]=k
k = k+1
} # Choix de la stratégie
p = if(sum(A) >= sum(B)){pA} else {pB}
for(i in k:Tmax){
esperance[i]=Gain1Partie(p)
regret[i]=pA-(sum(esperance)/(i))
abs[i]=i
}
ajout = data.frame(regret,abs)
ajout=cbind(j,ajout)
df=rbind(df, ajout)
}
df2 = df%>%group_by(abs)%>%summarise(avg=mean(regret))
ggplot() + geom_line(data=df, aes(x=abs, y=regret, group=j), alpha=0.15) +
geom_line(data=df2, aes(x=abs, y=avg), color='red') + ylim(-0.5,0.5)
}
RegQ2()
Cette stratégie n’est pas efficace pour un nombre de parties faible car il y a un risque d’erreur trop important sur la machine trouvé à l’aide des premiers essais. Cependant sur un nombre de partie tres grand cette stratégie a tendance à être efficace. Le problème est que en réalité un nombre important de parties est impossible pour un joueur qui n’a pas une infinité d’argent à jouer.
Point supplémentaire : Combien de mesures est-ce qu’il faut pour être sûr à 95% que \(pA \gt pB\)?
Comme déjà vu, on sait que \(X_{A,t}\) (resp. \(X_{B,t}\)) suit une loi de Bernoulli de paramètre \(p_A\) (resp. \(p_B\)). Nous connaissons ainsi leur espérance et variance :
\(\mathbb{E}[X_{A,t}] = \mu_A = p_A\) et \(Var(X_{A,t}) = \sigma_A^2 = p_A(1-p_A)\) . De meme
\(\mathbb{E}[X_{B,t}] = \mu_B = p_B\) et \(Var(X_{B,t}) = \sigma_B^2 = p_B(1-p_B)\) .
Pour être sûr à 95%, il faut que les intervalles de confiance ne se croisent pas. Supposons qu’on sait que \(p_A \gt p_B\), alors l’intersection des segments se fera au point inférieur du A avec le point supérieur du B, pour un \(n\) qu’on trouvera à l’aide de l’équation :
\(\mu_A - \frac{2\sigma_A}{\sqrt n} = \mu_B + \frac{2\sigma_B}{\sqrt n}\) d’ou un n de
\(n = (\frac{2(\sigma_A + \sigma_B)}{\mu_A - \mu_B})^2 \implies n = 378\)
Après calcul on constate qu’il faut faire au moins 378 mesures pour arriver à un interval de confiance de 95%, ce qui pour un ε de 0.05 revient à avoir un Tmax de 7800.
Q3. On exploite mais on se force à toujours apprendre (un peu)
Cette fois ci, après avoir choisi une machine comme plus prometteuse, nous l’utilisons avec une probabilité de 0.9 et nous nous forçons à toujours comparer la rentabilité de la machine choisie avec l’autre. Remarque: Le nombre de tentatives (nbA et nbB) dans l’algo est dès le début 1 de plus qu’au nombre de parties jouées.
RegQ3 = function(){
epsi = 0.05
epsiChap = 0.1
promA = 0 # Victoires avec A
promB = 0 # Victoires avec B
nbA=(epsi*Tmax/2)+1 # Nombre de parties jouées avec A + 1
nbB=(epsi*Tmax/2)+1 # Nombre de parties jouées avec B + 1
for (i in 1:(nbA-1)){ # Au debut on fait nbA-1 parties avec A
promA = promA + Gain1Partie(pA)
}
for (i in 1:(nbB-1)){ # Au debut on fait nbB-1 parties avec B
promB = promB + Gain1Partie(pB)
}
if (promA > promB){ # inutile de diviser car nbA=nbB
probChoisi=pA # A plus prometteuse
} else if (promA < promB){
probChoisi=pB # B plus prometteuse
} else {
u = runif(1) # sinon par hasard
if(u > 0.5){
probChoisi=pA
} else {
probChoisi=pB
}
}
df=data.frame()
for (j in 1:100){
regret = c()
esperance = c()
abs = c()
for(i in 1:Tmax){
esperance[i] = Gain1Partie(probChoisi)
regret[i] = pA-(sum(esperance)/(i))
abs[i] = i
if(probChoisi == pA){
nbA = nbA+1 # incrémente les nombre de parties jouées avec A + 1
promA = promA + esperance[i] # incrémente le sucèss (échec) avec A
} else {
nbB = nbB+1 # incrémente les nombre de parties jouées avec B + 1
promA = promA + esperance[i] # incrémente le sucèss (échec) avec B
} # Choix de la machine pour la partie suivante
if (promA/nbA > promB/nbB){
probChoisi=pA # A plus prometteuse
} else if (promA/nbA < promB/nbB){
probChoisi=pB # B plus prometteuse
} else {
u = runif(1) # sinon par hasard
if(u > 0.5){
probChoisi=pA
} else {
probChoisi=pB
}
}
u = runif(1)
if (u <= epsiChap){ # On change de stratégie avec proba epsiChap
if(probChoisi == pA){
probChoisi = pB
} else {
probChoisi = pA
}
}
}
ajout = data.frame(regret,abs)
ajout = cbind(j,ajout)
df = rbind(df, ajout)
}
df2 = df%>%group_by(abs)%>%summarise(avg=mean(regret))
ggplot() + geom_line(data=df, aes(x=abs, y=regret, group=j), alpha=0.15) +
geom_line(data=df2, aes(x=abs, y=avg), color='red') + ylim(-0.5,0.5)
}
RegQ3()
Le résultat nous montre que cette stratégie marche assez bien, mais elle n’est toujours pas parfaite. Le regret moyen est très proche de 0, mais on pourrait peut-être faire encore mieux. Il nous semble que la probabilité avec laquelle nous choisissons la machine à jouer (1-ε̂), reste assez fixe et arbitraire tout au long des observations. C’est un aspect à améliorer.
Q4. On tire au hasard en biaisant selon nos observations
Pour régler le problème vu précédemment, nous admettons que la vraisemblance de la probabilité du gain d’une machine suit une loi bêta de paramètres (promM+1, echM+1) (selon la notation de notre algorithme). Pour décider sur quelle machine jouer, nous tirons aléatoirement suivant la densité beta correspondant à chacune des machines A et B et nous choisissons la machine ayant obtenu la plus grande valeur.
RegQ4 = function(){
epsi = 0.05
promA = 0 # Victoires avec A
promB = 0 # Victoires avec B
echA = 0 # Echecs avec A
echb = 0 # Echecs avec B
nbA=(epsi*Tmax/2) # Nombre de parties jouées avec A
nbB=(epsi*Tmax/2) # Nombre de parties jouées avec B
for (i in 1:nbA){ # Au debut on fait nbA parties avec A
promA = promA + Gain1Partie(pA)
}
echA = nbA - promA
for (i in 1:nbB){ # Au debut on fait nbB parties avec B
promB = promB + Gain1Partie(pB)
}
echB = nbB - promB
repeat{ # pour éviter le cas tres peu probable que betA et betB soient égaux
betA = rbeta(1,promA+1,echA+1) # Tirage aléatoire ~ Beta pour A
betB = rbeta(1,promB+1,echB+1) # Tirage aléatoire ~ Beta pour B
if (betA != betB) {break}
}
if (betA > betB){
probChoisi = pA
} else {
probChoisi = pB
}
df=data.frame()
for (j in 1:100){
regret = c()
esperance = c()
abs = c()
for(i in 1:Tmax){
esperance[i] = Gain1Partie(probChoisi)
regret[i] = pA-(sum(esperance)/(i))
abs[i] = i
if(probChoisi == pA){
nbA = nbA+1 # incrémente les nombre de parties jouées avec A
promA = promA + esperance[i] # incrémente le sucèss (échec) avec A
echA = nbA - promA # mis à jour de l'échec A
} else {
nbB = nbB+1 # incrémente les nombre de parties jouées avec B + 1
promB = promB + esperance[i] # incrémente le sucèss (échec) avec B
echB = nbB - promB # mis à jour de l'échec B
} # Choix de la machine pour la partie suivante
repeat{ # pour éviter le cas tres peu probable que betA et betB soient égaux
betA = rbeta(1,promA+1,echA+1) # Tirage aléatoire ~ Beta pour A
betB = rbeta(1,promB+1,echB+1) # Tirage aléatoire ~ Beta pour B
if (betA != betB) {break}
}
if (betA > betB){
probChoisi = pA
} else {
probChoisi = pB
}
}
ajout = data.frame(regret,abs)
ajout = cbind(j,ajout)
df = rbind(df, ajout)
}
df2 = df%>%group_by(abs)%>%summarise(avg=mean(regret))
ggplot() + geom_line(data=df, aes(x=abs, y=regret, group=j), alpha=0.15) +
geom_line(data=df2, aes(x=abs, y=avg), color='red') + ylim(-0.5,0.5)
}
RegQ4()
Nous constatons que cette stratégie est très correcte, parce qu’elle donne un regret moyen de 0 sur un nombre assez grand de tentatives. En plus on remarque qu’il y a moins de “bruit”, c’est à dire que le regret s’approche un peu plus vite à sa valeur stable.
Le switch
finalSwitch = function (q){
switch (q,
{RegQ1_1(); RegQ1_2()}, # q = 1
RegQ2(), # q = 2
RegQ3(), # q = 3
RegQ4() # q = 4
)
}Conclusion
Les situations probabilistes sont assez courants dans la vie réelle, et une maîtrise des notions et outils de base de probabilité et simulation est donc assez rentable. Nous nous rendons compte que quasiment tout le temps, nous partons d’un point initial et nous essayons d’améliorer nos modélisations au fur et à mesure.