Singe savant

[Vassillia]

Bonjour à tous, d'après mon expérience, vous aimez les probas (et les chaines de Markov) donc...

Un singe tape au hasard sur une machine à écrire, à raison d'une lettre par seconde. Toutes les 26 lettres ont même probabilité, et le choix de chacune est indépendant des précédentes.
On appelle t1 le temps moyen qu'il faut attendre pour que le singe tape pour la première fois le mot « ABRACADABRA », et t2 le temps moyen pour le mot « ABCDEFGHIJK »

Est-ce que t1=t2 ou t1>t2 ou t1<t2 ?
Vous pouvez répondre à l'instinct et je vous y invite vivement mais pour me convaincre il faudra faire le calcul de t1 et de t2

[lyceen95]

Les 4 premières lettres et les 4 dernières lettres d'abracadabra sont les mêmes.

ABRACADABRA, 11 lettres , et les 4 premières lettres coïncident avec les 4 dernières : ABRA???ABRA. Soit l'ensemble tous les mots de ce type ; Tous les mots ayant cette particularité ont le même temps moyen d'attente, qu'on va noter .
Avec ces notations, ABCDEFGHIJK est donc dans l'ensemble

Et ABCDEFGHIJA serait dans l'ensemble , AAAAAAAAAAA serait dans l'ensemble

Pour tout couple i,j ,

[azf]

Bonjour Lycéen 95

J'ai un doute* car alors le mot ABRACCDABRA aurait aussi le même temps moyen d'attente ?
Il fait partie de ce type

*mon doute est très très faible (je vous fait confiance quand même par définition)

[Vassillia]

Et bien vous avez tous les 2 raisons, joli, il ne reste plus qu'à faire le petit calcul pour le justifier.

Juste un petit détail Lyceen95, tu ne peux pas dire que ABRCCADABRC aura le même temps moyen d'attente que ABRACADABRA et pourtant ils appartiennent tous les deux à tel que je le comprends par contre ABRACCDABRA aura bien le même temps moyen d'attente que ABRACADABRA

[GaBuZoMeu]

Bonjour,

Si on a déjà écrit ABCD et qu'on se trompe en tirant une lettre qui n'est pas E :
- soit on a tiré A et on repart de là (une lettre bonne)
- soit on n'a tiré ni E ni A, et on repart à zéro.

Si on a déjà écrit ABRA et qu'on se trompe en tirant une lettre qui n'est pas C :
- soit on a tiré B et on repart de AB (deux lettres bonnes)
- soit on a tiré A et on repart de là
- soit on n'a tiré ni C, ni B, ni A et on repart à zéro.

ABRACADBRA a ainsi un avantage indéniable.

[GaBuZoMeu]

D'un autre côté si on a déjà écrit ABR et qu'on se trompe en tirant une lettre qui n'est pas A, on repart forcément à zéro.
Su ce coup, ABRACADABRA a un désavantage indéniable

[Vassillia]

Ah ben justement, j'étais en train de taper un message comme quoi je n'étais pas trop convaincue par ton argument du coup, je te laisse te mettre en accord avec toi-même.
En plus, en vrai, autant j'ai compris comment on fait le calcul avec les martingales autant je n'arrive pas à l'intuiter, j'ai vraiment beaucoup de mal à visualiser les choses dès que l'infini s'en mêle.

[lyceen95]

Si aux tirages n° 75, 76, 77,78, je tire ABRA, chouette, je suis en bonne voie pour faire ABRACADABRA...

Regardons toutes les séries de 1000 Milliards de lettres consécutives ( Je tire 1000 Milliards de lettres, et je regarde combien de fois j'ai ABCDEFGHIJK et/ou ABRACADABRA, et je répète ça quelques milliards de fois).

La proba d'avoir ABRA aux rangs numéros n, n+1,n+2,n+3, c'est la même que celle d'avoir ABCD aux rangs numéros n, n+1, n+2 et n+3.

Donc égalité.
Mais , quand j'ai ABRA aux tirages n, n+1, n+2 et n+3, peut être que les 7 lettres prédentes étaient ABRACAD.
Et dans ce cas, quel gachis. J'étais tout heureux de tirer ABRA dans cet ordre, ça tient presque du miracle, mais ça ne me sert à rien, parce que j'avais déjà eu un autre miracle encore plus grand, j'avais déjà eu ma séquence de 11 lettres ABRACADABRA, aux positions n-7 à n+3.
Au moins quand je recherche ABCDEFGHIJK, j'ai l'assurance de ne pas avoir ces doubles-comptes.

[Vassillia]

J'imagine que c'est un truc comme ça qui se passe car c'est exactement la configuration que tu décris qui pose problème et qui "augmente" le temps moyen d'attente, je vais y réfléchir pour voir si j'arrive à me l'approprier. En tout cas le calcul n'est pas trop difficile et au moins c'est fiable.
A ce soir, faut que je bosse un peu quand même

[GaBuZoMeu]

Mon petit calcul donne :

3670344487444778 pour l'espérance du temps d'attente de "ABRACADABRA"

3670344486987776 pour l'espérance du temps d'attente de "ABCDEFGHIJK"

3670344486987776 pour l'espérance du temps d'attente de "ABRACAABRAD"

[lyceen95]

Donc effectivement un temps plus long pour les cas où les 4 dernières lettres coïncident avec les 4 premières.
Et 2 fois le même résultat quand il n'y a pas téléscopage.

Peux tu tester le ABRCCADABRC proposé par Vassilia ?

Pour moi, il est de la famille , donc comme ABRACADABRA, mais Vassilia disait qu'on n'aurait pas le même résultat que pour ABRACADABRA.

[GaBuZoMeu]

3670344487444752

[lyceen95]

C'est sûr ? Non négociable ?

Du coup, j'avais conjecturé ceci :
Les éléments de type 1234xyz1234 ont tous le même profil, le même temps d'attente.
Et j'étais assez certain de cette histoire.
Et donc, parmi les éléments de type 1234xyz1234, il y aurait un sous-goupe, les éléments de type 12344yx1234.
J'ai beaucoup de mal à concevoir pourquoi ces éléments de type 12344yz1234 arriveraient un peu plus tôt que les éléments 1234xyz1234.
Je ne vois pas ce que la duplication du 4ème caractère apporte.

Même si la différence est extrèmement petite.

Ou alors, ok, vu, c'est autre chose... ce n'est pas le 5ème caractère identique au 4ème qui crée l'écart.
C'est parce qu'on a d'une part une chaine du type 1234xyz1234 et d'autre part une chaine du type 1231xyz1231.
Et là, effectivement, je peux imaginer que ça génère une différence.
1231xyz1231 pourrait avoir un temps d'attente plus long que 1234xyz1234.
On a un premier téléscopage, avec les 4 premiers caractères identiques aux 4 derniers ; et on a un autre téléscopage avec le premier caractère identique au dernier.
Pas totalement clair encore, mais plausible.

[Vassillia]

Tu as fort bien conjecturé Lyceen95 avec ton telescopage même si en intuition, je t'avoue que j'ai encore du mal à le saisir vraiment.
Je ne sais pas comment GaBuZoMeu a fait ses calculs, calcul matriciel où système sur les esperances mais en tout cas il a raison et ce que je vous propose (largement inspiré d'un TD de l'ENS que j'ai trouvé)

On fabrique une martingale et juste avant chaque seconde ... un joueur arrive pour miser 1 banane sur l'événement {la nième lettre tapée est la première du mot recherchée} qu'il donne au singe.
- S'il perd, il part et le singe garde la banane
- S'il gagne, il reçoit bananes du singe (car probabilité 1/26 d'avoir la bonne lettre et il faut que le jeu soit équilibré) qu'il remise immédiatement sur {la ème lettre tapée est la deuxième du mot}
- S'il gagne, il reçoit bananes du singe qu'il remise immédiatement sur la { ème lettre tapée est la troisième du mot}
- S'il gagne, il reçoit bananes du singe qu'il remise immédiatement sur la { ème lettre tapée est la quatrième du mot}
...
On continue jusqu'à ce que le mot sorte.

On applique le joli théorème d'arret de Doob qui dit que la variation de bananes dans le sac du singe au temps d'arret est [edit:d'espérance] nulle. L'espérance des gains du singe (qui correspondent au temps d'attente puisque chaque joueur a donné une banane) est égale à l'espérance de ses pertes.

pour ABRACADABRA, il ne reste que les joueurs qui sont entrés au moment des lettres en rouge qui vont gagner respectivement , et bananes donc les pertes du singe seront

pour ABCDEFGHIJKL, il ne reste qu'un seul joueur, celui entré au tout début donc les pertes du singe seront
Et voilà, sans artillerie lourde vous pouvez calculer le temps d'attente moyen de n'importe quel mot !

[GaBuZoMeu]

Très jolie, l'utilisation du théorème d'arrêt de Doob.

Quelques petites précisions :

le joli théorème d'arret de Doob qui dit que la variation de bananes dans le sac du singe au temps d'arret est nulle.

C'est bien l'espérance de la variation qui est nulle, n'est-ce pas ?

l'espérance de ses pertes

Ses pertes sont en fait toujours les mêmes au temps d'arrêt, n'est-ce pas ?

J'ai procédé de ma manière bourrin habituelle : chaîne de Markov absorbante.

Code: Tout sélectionner

import string as st
alphabet=list(st.ascii_uppercase)

def coin(L,M) :
    n=len(L)
    i = 0
    while L[:n-i] != M[i:] :
        i += 1
    return n-i

def tramat(mot) :
    L=list(mot)
    n=len(L)
    P=matrix(QQ,n+1)
    for i in range(n) :
        for l in alphabet :
            A = L[:i+1]
            B = L[:i] + [l]
            j = coin(A,B)
            P[i,j] += 1/26
    P[n,n]=1
    return P

def attente(mot) :
    n=len(mot)
    P=tramat(mot)
    Q = P[:-1,:-1]
    N = (identity_matrix(QQ,n)-Q)^(-1)
    temps=sum(N[0,i] for i in range(n))
    return temps

[Vassillia]

Oui tu as raison, c'est bien de l'espérance dont on parle dans le théorème d'arrêt mais comme on s'est bien débrouillé et que les pertes sont toujours les mêmes, cela rend le calcul aisé puisque l'espérance des pertes vaut cette constante et on en déduit immédiatement l'espérance des gains. En tout cas, c'est ce que j'ai compris.

J'étais sûre que tu ferai ta manière habituelle, je finirai peut-être par te convaincre de ne pas la faire systématiquement à force Ceci-dit, elle fait le taf, rien à redire.