Temps d'attente pour un motif

Reinhard

Hello tout le monde.

Dans le livre de Williams : https://www.amazon.co.uk/Probability-Martingales-Cambridge-Mathematical-Textbooks/dp/0521406056 [ Probability with martingales ] , il y a un exercice fameux ou on cherche le temps d’arrêt pour le motif ABRACADABRA. On tape sur un clavier à 26 touches jusqu’à ce que le motif ABRACADABRA apparaisse.

Du point de vue des chaînes de Markov absorbantes, le problème devient plutôt facile. On crée une chaîne de Markov absorbante aux états :
Null, A, AB, ABR, ABRA, ..., ABRACADABRA , avec les probabilités de transitions associées (bref vous avez tous compris), et un état absorbant pour ABRACADABRA. On en déduit la matrice du graphe $\Gamma =
\begin{pmatrix} M & B \\ 0 & 1 \end{pmatrix} $ donc la matrice fondamentale $N = (I - M)^{-1} $ et on multiplie $N$ par le vecteur avec que des $1$, que je note $e$, et $N \cdot e $ nous donne les temps d’arrêts (en espérance) pour rejoindre ABRACADABRA depuis chacun des états.

Mais dans le livre de Williams, il propose de résoudre le probleme avec des martingales et je n'ai pas tres bien compris.Il nous propose de parier de sorte a ce qu'on soit dans une position $-k$ si on échoue au $k$-e pari. En gros, imaginons que je suis en ABRA, je veux passer en ABRAC alors que je suis au tirage de lettre numéro 12, et bien si j'échoue a tirer C, je me retrouve avec une position $-12$. Enfin c'est ce que j'en ai compris.

Je me demandais si quelqu'un d'un peu plus versé que moi en proba et théorie des jeux pourrait m'aider à m'éclairer sur l'approche de Williams. À la place de miser sur ABRACADABRA, imaginons qu'on veuille appliquer l'approche de Williams jusqu’à obtenir le motif Face Face Face Face pour un jeu de lancer de pièce.
Merci d'avance ! :)o

lourrran

Je n'ai pas lu le livre, je n'ai pas la réponse à ta question, mais ...
Toute l'astuce avec cette histoire d'ABRACADABRA réside dans :

en gros, imaginons que je suis en ABRA, je veux passer en ABRAC
Cette phrase doit être reformulée pour refléter l'exercice.
En gros, imaginons que je suis en ABRA, et que les 7 lettres précédentes n'étaient pas ABRACAD, je veux passer en ABRAC.

Les 4 dernières lettres d'ABRACADABRA sont les mêmes que les 4 premières. Et du coup, le temps moyen pour atteindre ABRACADABRA est plus long que le temps moyen pour atteindre ABRACADABRB par exemple.

Reinhard

Oui bien sur, ca se voit lorsqu'on dessine le graphe de la chaîne de Markov décrite dans mon message. À la place de lettres, prenons des pièces et cherchons le temps d'attente pour Face Face Face et Face Pile Face.

Dans le cas 1, on a les états Null - F - FF - FFF et si on échoue à passer d'un état au suivant, on retourne à Null. Dans le cas 2, on a les états Null - F - FP - FPF, et à l'étape F, on ne peut que progresser vers FP ou rester en F, on ne retourne pas en Null. Donc on sait que le temps d'attente pour FPF sera plus court que le temps d'attente pour FFF.

Reinhard

Up au cas ou les gens auraient manqué la question, blasés par le confinement. :-P

Lucas

Bonjour Reinhard,

En copie je joins un exo corrigé avec des calculs d'espérance d'arrivées de motifs de taille 3 en utilisant les martingales.