Lors de la visite au laboratoire d'une brillante élève de seconde (salut Lena!), nous avons inventé un jeu: le jeu de l'urne. Le principe est simple: on a un nombre pair $N$ de balles (disons $8$), la motié sont rouges, l'autre moitié noires. Elles sont dans une urne opaque et donc on ne peut pas les voir à moins de les tirer une par une (sans remise dans l'urne). On peut tirer autant de balles qu'on veut pour les observer et le but est de décider le moment où on est prêt à deviner la couleur de la balle qu'on va prendre. Si on gagne (on a bien prédit la couleur), alors on gagne autant de points que le nombre de balles qui étaient dans l'urne au moment de la décision.Sinon on perd autant de points que l'on en aurait gagné!

Par exemple, je choisis de regarder une balle (rouge), puis un seconde (encore rouge), enfin une troisième (noire) - je décide de parier pour une noire, mais une rouge sort: j'ai perdu $8-3=5$ points.

Ce jeu parait simple (je suis curieux de savoir s'il existe, le contraire m'étonnerait) - mais son analyse mathématique implique des combinaisons dont le nombre grandit vite: quelle est la stratégie optimale? C'est ce que nous essayons de faire ici.

Note: ce jeu pourrait paraitre anodin, mais il est révélateur de notre capacité à prendre des décisions par rapport à ce que l'on sait et ce qui pourrait arriver: c'est la base de la théorie de la décision. Cette théorie est notamment essentielle pour comprendre le fonctionnement normal ou pathologique... et de le diagnostiquer.

Let's first initialize the notebook:

In [1]:
from __future__ import division, print_function
%load_ext autoreload
%autoreload 2

quelque bases de programmation

Nous allons ici utiliser un langage de programmation pour communiquer avec l'ordinateur et lui faire effectuer des séquences de calcul. Pour sa simplicité et son ouverture, nous allons utiliser le langage Python. C'est simple comme parelr en anglais, voici quelques exemples:

In [2]:
print('Bonjour Lena')
Bonjour Lena
In [3]:
2 * 5, 3 / 4 
Out[3]:
(10, 0.75)
In [4]:
2**0, 2**1, 4**1.5
Out[4]:
(1, 2, 8.0)

créons une liste d'objets

In [5]:
une_liste = [ 1, 4, 5 ]
In [6]:
print(une_liste)
[1, 4, 5]
In [7]:
une_liste.append(6)
In [8]:
une_liste
Out[8]:
[1, 4, 5, 6]

on peut donc aussi faire une liste pour notre jeu:

In [9]:
une_liste_B = []
In [10]:
une_liste_B.append(0)
In [11]:
une_liste_B.append(1)
In [12]:
une_liste_B.append(0)
In [13]:
une_liste_B.append(0)
In [14]:
une_liste_B
Out[14]:
[0, 1, 0, 0]

ou plutôt:

In [15]:
N_ballons  = 8

une_liste_C = []
for j in range(N_ballons):
    une_liste_C.append('B')
print(une_liste_C)
['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B']

il y a encore plein d'autres façons d'utiliser des listes:

In [16]:
liste_de_listes = [une_liste, une_liste_B, une_liste_C ]
print(liste_de_listes)
[[1, 4, 5, 6], [0, 1, 0, 0], ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'B']]
In [17]:
dico_français_anglais = dict(watch='montre', name='name', age='age')
In [18]:
dico_français_anglais['watch']
Out[18]:
'montre'

quelque bases de statistiques et de probabilités

pouyr analyser notre jeu, nous allons avoir besoin de quelques outils mathématiques. Une fonction importante est d'uiliser des générateurs de nombres aléatoires (dans la librairie numpy.random et de fonctions pour afficher des histogrammes plt.hist:

In [19]:
import numpy as np
np.set_printoptions(precision=6, suppress=True)
import os
%matplotlib inline
#%config InlineBackend.figure_format='retina'
%config InlineBackend.figure_format = 'svg'
import matplotlib.pyplot as plt
phi = (np.sqrt(5)+1)/2
fig_width = 10
figsize = (fig_width, fig_width/phi)
In [20]:
print('2 π =', 2 * np.pi)
2 π = 6.283185307179586

variable aléatoire uniforme:

In [21]:
fig, ax = plt.subplots(figsize=figsize)
ax.hist(5 * np.random.rand(1000000), bins=20);

variable aléatoire en cloche:

In [22]:
fig, ax = plt.subplots(figsize=figsize)
ax.hist(.3 * np.random.randn(1000000), bins=20);

si on prend un nombre aléatoire entre 0 et 1:

In [23]:
np.random.rand()
Out[23]:
0.8512663331621892

il est facile de le transformer en une valeur binaire aléatoire:

In [24]:
np.random.rand() > .5
Out[24]:
False

variable aléatoire binaire:

In [25]:
fig, ax = plt.subplots(figsize=figsize)
ax.hist(np.random.rand(100) > .5)
Out[25]:
(array([ 46.,   0.,   0.,   0.,   0.,   0.,   0.,   0.,   0.,  54.]),
 array([ 0. ,  0.1,  0.2,  0.3,  0.4,  0.5,  0.6,  0.7,  0.8,  0.9,  1. ]),
 <a list of 10 Patch objects>)
In [26]:
plt.step(np.arange(100), 2*(np.random.rand(100) > .5)-1)
Out[26]:
[<matplotlib.lines.Line2D at 0x109c7c940>]
In [27]:
fig, ax = plt.subplots(figsize=(15,8))
gains = np.cumsum(2*(np.random.rand(100, 20) > .5)-1, axis=0)
ax.plot(gains, alpha=0.2);

application au jeu de l'urne

essayons de dénombrer tous les jeux possibles (il y en a $2^{\mathrm nombre~de~ballons}$):

In [28]:
for i in range(2**N_ballons):
    if i >250: print('la représentation binaire de ', i, ' est ' , bin(i))
la représentation binaire de  251  est  0b11111011
la représentation binaire de  252  est  0b11111100
la représentation binaire de  253  est  0b11111101
la représentation binaire de  254  est  0b11111110
la représentation binaire de  255  est  0b11111111

utilisons une autre stratégie: réalisons plein de tirages au hasard (c'est la méthode de Monte Carlo). d'abord pour un "test":

In [29]:
help(np.random.permutation)
Help on built-in function permutation:

permutation(...) method of mtrand.RandomState instance
    permutation(x)
    
    Randomly permute a sequence, or return a permuted range.
    
    If `x` is a multi-dimensional array, it is only shuffled along its
    first index.
    
    Parameters
    ----------
    x : int or array_like
        If `x` is an integer, randomly permute ``np.arange(x)``.
        If `x` is an array, make a copy and shuffle the elements
        randomly.
    
    Returns
    -------
    out : ndarray
        Permuted sequence or array range.
    
    Examples
    --------
    >>> np.random.permutation(10)
    array([1, 7, 4, 3, 0, 9, 2, 5, 8, 6])
    
    >>> np.random.permutation([1, 4, 9, 12, 15])
    array([15,  1,  9,  4, 12])
    
    >>> arr = np.arange(9).reshape((3, 3))
    >>> np.random.permutation(arr)
    array([[6, 7, 8],
           [0, 1, 2],
           [3, 4, 5]])

In [30]:
def generate_test(N_ballons, N_test=1):
    assert (N_ballons/2 == N_ballons//2)
    tests = np.zeros((N_test, N_ballons))
    N_foot = N_ballons//2
    tests[:, N_foot:] = 1.
    for i_test in range(N_test):
        tests[i_test, :] = np.random.permutation(tests[i_test, :])
    return tests

test = generate_test(N_ballons)            
print(test)
[[ 1.  0.  1.  0.  1.  0.  1.  0.]]

puis pour plein:

In [31]:
N_test = 1000
tests = generate_test(N_ballons, N_test)

test = tests[N_test//13, :]
print(test)
[ 1.  1.  0.  0.  1.  1.  0.  0.]
In [32]:
print('nombre de valeurs True = ', np.mean(tests.sum(axis=1)), ' +/- ', np.std(tests.sum(axis=1)))
nombre de valeurs True =  4.0  +/-  0.0

Adoptons la stratégie d'un agent qui de façon tétue se dirait qu'il allait regarder un nombre fixe de ballons (par exemeple 2) puis se décider pour la solution la plus probable:

In [33]:
N_ballons_vus = 1
information = test[:N_ballons_vus]
information
Out[33]:
array([ 1.])
In [34]:
N_ballons_restant = N_ballons - N_ballons_vus
print ('on a vu ', N_ballons_vus, ' ballon(s), in en reste',  N_ballons_restant, " dans l'urne")
on a vu  1  ballon(s), in en reste 7  dans l'urne
In [35]:
N_ballons_restant = N_ballons - N_ballons_vus
print ('on en a vu ', sum(information), ' de basket (=True=Droite) donc in reste',  N_ballons//2 - sum(information), " ballons de basket  dans l'urne")
on en a vu  1.0  de basket (=True=Droite) donc in reste 3.0  ballons de basket  dans l'urne
In [36]:
proba_True_restant = (N_ballons/2 - sum(information)) / N_ballons_restant 
print ('la probabilité de tirer un de basket est ', proba_True_restant*100, '%, contre ', (1-proba_True_restant)*100, "% pour l'autre choix ")
la probabilité de tirer un de basket est  42.8571428571 %, contre  57.1428571429 % pour l'autre choix 
In [37]:
choix = proba_True_restant > .5 
#choix = proba_True_restant > np.random.rand()
print(choix)
False
In [38]:
gain_esperé = N_ballons_restant # N_ballons - N_ballons_restant -1
print(gain_esperé)
7
In [39]:
réussite = (test[N_ballons_vus] == choix)
réussite, réussite*2 - 1
Out[39]:
(False, -1)
In [40]:
gain = gain_esperé * (réussite*2 - 1)
#gain = gain_esperé * réussite 
gain
Out[40]:
-7

information vide:

In [41]:
test[:0]
Out[41]:
array([], dtype=float64)

regardons d'abord un seul ballon:

In [42]:
N_test = 1024
tests = generate_test(N_ballons, N_test)

gains = np.zeros(N_test)
for i_test in range(N_test):
    information = tests[i_test, :1]
    N_ballons_restant = N_ballons - 1
    proba_True_restant = (N_ballons//2 - np.sum(information)) / N_ballons_restant 
    if proba_True_restant==.5:
        choix = np.random.rand() > .5
    else:
        choix = proba_True_restant > .5
    réussite = (tests[i_test, 1] == choix)
    gain_esperé = N_ballons_restant #- 1
    gains[i_test] = gain_esperé * (réussite*2 - 1)
    #print(proba_True_restant, test[N_ballons_vus], choix, réussite)

plt.hist(gains)
Out[42]:
(array([ 440.,    0.,    0.,    0.,    0.,    0.,    0.,    0.,    0.,  584.]),
 array([-7. , -5.6, -4.2, -2.8, -1.4,  0. ,  1.4,  2.8,  4.2,  5.6,  7. ]),
 <a list of 10 Patch objects>)
In [43]:
ax = plt.pcolormesh(tests.T);