Exercice 1

Les questions 1 à 3 se résolvent simplement en calculant des puissances de la matrice de transition :

Le futur ne dépendant que de l'état courant, la probabilité que Gribouille joue à $t=8$ sachant qu'il dort à $t=5$ est la même que celle qu'il joue à $t=3$ sachant qu'il dort à $t=0$. Il suffit de regarder $P^3[1,2]$ (indices à partir de 1).

On observe numériquement la distribution stationnaire $w = (0.8839779, 0.0718232, 0.0441989)$. La convergence est en fait très rapide sur cet exemple. On peut aussi calculer $w$ en résolvant l'équation $w P = w$ :

$$\begin{align*} 0.9 w_1 + 0.8 w_2 + 0.7 w_3 &= w_1\\ 0.05 w_1 + 0.2 w_2 + 0.3 w_3 &= w_2\\ 0.05 w_1 &= w_3\\ \end{align*}$$

Le système admet une infinité de solutions car $P$ est de rang 2 : sa dernière colonne se déduit des autres étant donné que la somme par lignes vaut 1. On observe que le choix $w_1 = 0$ mène à $w = 0$ et n'est donc pas envisageable. Fixons alors arbitrairement $w_1 = 1$ : alors $w_3 = 0.05 = \frac{1}{20}$ et $0.8 w_2 = 1 - 0.9 - 0.7 \times 0.05$ donc $w_2 = \frac{0.065}{0.8} = \frac{13}{160}$. On normalise ensuite par $w_1 + w_2 + w_3 = \frac{181}{160}$ pour obtenir :

Pour la dernière question, il faut considérer l'état "manger" comme absorbant. On obtient

$$Q = \begin{pmatrix}0.9 & 0.05\\ 0.8 & 0.2\end{pmatrix} \quad \mbox{et} \quad N = \begin{pmatrix}0.05\\0.0\end{pmatrix}$$

Il faudra donc attendre un peu plus de 21 changements d'états en moyenne pour que Gribouille mange.

On peut aussi faire le calcul à la main dans ce cas simple : $I - Q = \begin{pmatrix}0.1 & -0.05\\ -0.8 & 0.8\end{pmatrix}$ puis $\mbox{det}(I-Q) = 0.08 - 0.04 = 0.04$, et donc $(I-Q)^{-1} = 25 \begin{pmatrix}0.8 & 0.05\\0.8 & 0.1\end{pmatrix} = \begin{pmatrix}20 & 1.25\\20 & 2.5\end{pmatrix}$.

Exercice 2

Choisir une stratégie revient à sélectionner une fonction $f$ de $[1, 7]$ dans lui-même, qui à un montant en euros associe l'argent parié. Bien sûr $f(x) \leq x$ : on ne peut pas parier plus que ce qu'on a. On ne définit pas $f(0)$ ou $f(8)$ car dans les états "0" et "8" le jeu est terminé : dans le premier cas on a perdu (ruine) et dans le second on a gagné (sortie de prison).

L'idée la plus simple consiste à toujours miser tout ce qu'on a : $f(x) = x$. Dans ce cas, on passe initialement de 3€ à 0 ou 6€, puis de 6€ à 0 ou 8€ (12 en fait, mais toute somme supérieure ou égale à 8 est ramenée à 8€ puisque 8 suffit). Il n'y a donc que 4 états et la mise en équation est très simple.

Rappel 1 : np.identity(n) construit une matrice carrée $I$ de taille $n$, contenant des 1 sur la diagonale et des 0 partout ailleurs. Elle vérifie $I X = X I = X$ pour toute matrice carrée $X$ de taille $n$ (d'où le nom "matrice [fonction] identité" : c'est l'élément neutre pour la multiplication).

Rappel 2 : l'inverse d'une matrice $M$, notée $M^{-1}$, est l'unique matrice $A$ vérifiant $A M = M A = I$ (identité).
Attention certaines matrices ne sont pas inversibles.

Calcul pratique : Pour une petite matrice (taille 2 ou 3) on peut appliquer la méthode des cofacteurs :
$M^{-1} = \frac{1}{\mbox{det}(M)} \mbox{t(com}(M))$
Pour une matrice contenant un grand nombre de zéros, on peut chercher à inverser le système $M X = Y$,
l'écrivant sous la forme $A Y = X$ : $A$ est alors l'inverse cherché.
Dans le cas général on peut appliquer l'algorithme du pivot de Gauss.

Ce calcul ne sera pas demandé à l'examen (je vous donnerai directement la matrice fondamentale $N$), mais comme toujours, c'est mieux si vous savez comment obtenir l'inverse d'une matrice à la main.

Le calcul devrait donner exactement 0.16, mais on observe une erreur d'arrondi. Explication courte : 0.4 = 4/10 = 2/5 n'est pas représentable de manière exacte en écriture binaire. Explication longue : voir par exemple ce document.

Voir aussi https://stackoverflow.com/a/16444778/12660887.

Bref, sur ce premier scénario simple, probabilité de sortir de prison = 0.16.
C'est ce qu'on obtient immédiatement en dessinant l'arbre de probabilités, mais dans un cas plus complexe l'écriture matricielle est préférable.

Remarque : miser 6 lorsqu'on a 6€ est moins intéressant que de miser 2 seulement (puisque tout montant de 8€ au moins suffit à sortir). En cas de défaite on peut alors rejouer à partir de 4€ au lieu d'avoir perdu.

C'est mieux. On obtient le même résultat avec un arbre : 0.4 0.4 + 0.4 0.6 * 0.4

Que dire de la stratégie "la plus prudente" consistant à toujours miser exactement 1€ ?

Pas terrible : moins bien que la stratégie naïve "tout miser".

Pour faire le calcul à l'aide d'un arbre, il faudrait envisager "tous" les chemins. Le souci est qu'ils sont ici en nombre infini : 1 -> 2 -> ... -> 8 en direct, mais aussi 1 -> 2 -> 1 -> 2 -> 3 etc. On ne s'en sort pas : le calcul matriciel est nécessaire.

Intuitivement on sent que moins il y a de tours mieux c'est, car on a toujours plus de chances de perdre (60%) que de gagner (40%). Cette stratégie "prudente" nécessite de gagner au moins 7 fois (1 -> 2, 2 -> 3 etc), et n'est donc pas du tout prudente. Qu'en est-il alors d'une stratégie intermédiaire ? Dans l'état "$n$€", disons qu'on mise min(max($1, n-1$),$8-n$), pour qu'une défaite ne soit pas nécessairement fatale et qu'on ne dépasse pas 8 :

Pas mieux que la stratégie "miser tout". Resterait à prouver qu'elle est optimale... (Je pense que oui).