70
4 Chaˆ ınes de Markov en auto-interaction
4.2 Les pi` eges du renforcement
Un touriste anglais rˆ eve de passer ses vacances en Aquitaine. Il se rend ` a
Bordeaux, et d´ ecide d’explorer tous les pubs de la ville. La strat´ egie qu’il se
propose de suivre est assez simple. Le premier apr` es midi, il choisit un pub
au hasard parmi les p pubs de Bordeaux ordonn´ es de 1 `
a p dans son agenda.
Autrement dit, il choisit un indice de pub selon la mesure uniforme
μ =
1
p
p
j=1
1 j
sur l’ensemble des pubs rang´ es de 1 `
a p
E = {1, . . . , p}
Apr` es quelques heures pass´ ees dans ce pub, notre touriste est assez attach´ e ` a
l’endroit. Le jour suivant il h´ esitera ` a changer. Le pub visit´ e le premier jour
n’a d´ ej` a plus la mˆ eme importance ! Notons X 0 le num´ ero du pub visit´ e le
premier jour. Le jour suivant, il choisira un pub d’indice X 1 choisi selon la loi
P(X 1 = i | X 0 ) = 1 X0 (i) + (1 − ) μ(i)
o` u ∈ [0, 1] d´ esigne le coefficient de renforcement du touriste. Autrement dit,
il retournera directement dans le pub X 0 , sans mˆ eme examiner les autres avec
une probabilit´ e . Dans le cas contraire, il choisira au hasard et uniform´ ement
l’un des pubs comme au premier jour selon la loi μ. Le troisi` eme jour, notre
touriste d´ eja visit´ e les pubs X 0 et X 1 . Ces premiers pubs sont d´ ej` a dans son
agenda ! Ce jour l` a, il choisira un pub d’indice X 2 selon la loi
P(X 2 = i | X 0 , X 1 ) =
1
2
1 X0 (i) +
1
2
1 X1 (i)
+ (1 − ) μ(i)
Deux cas se pr´ esentent : 1) Le touriste est d´ eja all´ e deux jours cons´ ecutifs
dans le mˆ eme pub X 0 = X 1 . Dans ce cas, il retournera `
a nouveau dans le pub
X 0 sans examiner les autres avec une probabilit´ e . Dans le cas contraire, il
choisira au hasard et uniform´ ement l’un des pubs comme au premier jour. 2)
Le touriste a visit´ e deux pubs distincts X 0 = X 1 . Dans ce cas il retournera
` a nouveau, et au hasard dans l’un de ces pubs X 0 ou X 1 , sans examiner les
autres avec une probabilit´ e . Dans le cas contraire, il choisira au hasard et
uniform´ ement l’un des pubs selon la loi μ. En it´ erant ce proc´ ed´ e d’exploration,
l’individu choisit al´ eatoirement l’un des pubs X n avec la distribution suivante
P(X n = i | X 0 , . . . , X n−1 ) =
1
n
n−1
k=0
1 X k (i) + (1 − ) μ(i)
En terme des transitions de probabilit´ es introduites dans l’introduction, nous
avons
a
4 Chaˆ ınes de Markov en auto-interaction
4.2 Les pi` eges du renforcement
Un touriste anglais rˆ eve de passer ses vacances en Aquitaine. Il se rend ` a
Bordeaux, et d´ ecide d’explorer tous les pubs de la ville. La strat´ egie qu’il se
propose de suivre est assez simple. Le premier apr` es midi, il choisit un pub
au hasard parmi les p pubs de Bordeaux ordonn´ es de 1 `
a p dans son agenda.
Autrement dit, il choisit un indice de pub selon la mesure uniforme
μ =
1
p
p
j=1
1 j
sur l’ensemble des pubs rang´ es de 1 `
a p
E = {1, . . . , p}
Apr` es quelques heures pass´ ees dans ce pub, notre touriste est assez attach´ e ` a
l’endroit. Le jour suivant il h´ esitera ` a changer. Le pub visit´ e le premier jour
n’a d´ ej` a plus la mˆ eme importance ! Notons X 0 le num´ ero du pub visit´ e le
premier jour. Le jour suivant, il choisira un pub d’indice X 1 choisi selon la loi
P(X 1 = i | X 0 ) = 1 X0 (i) + (1 − ) μ(i)
o` u ∈ [0, 1] d´ esigne le coefficient de renforcement du touriste. Autrement dit,
il retournera directement dans le pub X 0 , sans mˆ eme examiner les autres avec
une probabilit´ e . Dans le cas contraire, il choisira au hasard et uniform´ ement
l’un des pubs comme au premier jour selon la loi μ. Le troisi` eme jour, notre
touriste d´ eja visit´ e les pubs X 0 et X 1 . Ces premiers pubs sont d´ ej` a dans son
agenda ! Ce jour l` a, il choisira un pub d’indice X 2 selon la loi
P(X 2 = i | X 0 , X 1 ) =
1
2
1 X0 (i) +
1
2
1 X1 (i)
+ (1 − ) μ(i)
Deux cas se pr´ esentent : 1) Le touriste est d´ eja all´ e deux jours cons´ ecutifs
dans le mˆ eme pub X 0 = X 1 . Dans ce cas, il retournera `
a nouveau dans le pub
X 0 sans examiner les autres avec une probabilit´ e . Dans le cas contraire, il
choisira au hasard et uniform´ ement l’un des pubs comme au premier jour. 2)
Le touriste a visit´ e deux pubs distincts X 0 = X 1 . Dans ce cas il retournera
` a nouveau, et au hasard dans l’un de ces pubs X 0 ou X 1 , sans examiner les
autres avec une probabilit´ e . Dans le cas contraire, il choisira au hasard et
uniform´ ement l’un des pubs selon la loi μ. En it´ erant ce proc´ ed´ e d’exploration,
l’individu choisit al´ eatoirement l’un des pubs X n avec la distribution suivante
P(X n = i | X 0 , . . . , X n−1 ) =
1
n
n−1
k=0
1 X k (i) + (1 − ) μ(i)
En terme des transitions de probabilit´ es introduites dans l’introduction, nous
avons
a