Abba / abab

[Ben314]

Une question que l'on vient juste de me poser (et je vais bosser dans 2mn)
On tire au hasard une suite de N lettres 'a' ou 'b' indépendement les unes des autres (avec proba. =1/2... ou pas) et on regarde le nombre moyen d'apparition de deux 'mots' dans la série (par exemple 'abba' et 'abab')
qu l'on note X_N et Y_N.
X_N et Y_N sont ils "proches" lorsque N->oo, si oui, en quel sens ?

(évidement, généralisation à des mots différents....)


Bon, je vais bosser. A+

[alavacommejetepousse]

bonjour

pas sûr d avoir compris

on fixe une séquence déterminée = un mot

XN : nbre d apparitions du mot ds la série de N lettres

et on compare E(XN) et E(YN) pour N grand ou c est ça?

[Ben314]

Oui, c'est ça (i.e. c'est des proba discrètes)
Mais me demande si, formulé comme ça, ce n'est pas complètement con...
(i.e. E(XN)=E(YN) pour tout N si les mots ont la même longueur)

L'idée que j'aimerais formaliser, c'est que, sur les 8 tirages possibles de 'mots' de 3 lettres (avec 'a' ou 'b'), 4 contiennent 'ba' alors que seulement 3 contiennent 'aa'.
Sauf que, si tu compte le 'nombre d'aparitions' alors 'aa' apparait 4 fois car il apparait 2 fois dans 'aaa'...

Je me demande si ce qui m'interesse ne serait pas plutôt :
Soit P_X(N)= proba d'apparition d'au moins une fois le mot X dans une série de N lettres.
Evidement P_X(N) tend vers 1 lorsque N tend vers l'infini,
Mais est-ce que 1-P_X(N) et 1-P_Y(N) sont équivalents ?

Tout ça pour dire que, même la question n'est pas trés claire :
La proba d'avoir (au moins une fois) 'ab' et 'ba' dans un tirage de 3 lettre n'est pas la même.
Est-ce que "la même chose" (????) se produit pour N grand ?

[alavacommejetepousse]

ds la séquence

abbabba tu comptes donc deux fois le mot abba ?
dans ce cas le nombre moyen de mots ds une séquence de N lettres est

(N-3)(1/2)^4 quel que soit le mot de 4 lettres

[Ben314]

abbabba tu comptes donc deux fois le mot abba ?

à priori, j'était parti sur cette idée, mais cela ne m'étonne pas que, dans ce cas, la "fréquence d'apparition" ne dépende pas du mot (je te fait confiance, j'ai pas fat les calculs)

Ca veut dire que (peut-être) le problème interessant est sur la proba d'apparition du mot (au moins une fois) et pas sur la fréquence d'apparition .....

[Doraki]

Pour "aa" et "ab", les lois d'apparition au moins une fois sont différentes.

"aa" :

"ab" :

La probabilité que ab apparaisse au moins une fois tend plus vite vers 1 que pour aa. Intuitivement, dans le cas de aa, il y a plus de mots avec beaucoup de aa d'un seul coup (comme par exemple dans "aaaaaa")

J'ai pas fait les calculs mais je dirais que pour abba, ça tend plus vite vers 1 que pour abab (pour la même raison)

[Ben314]

C'est marrant je trouve (j'ai toujours pas fait le moindre calcul)
Doraki, tu as l'impression de "comprendre" suffisement le "pourquoi du comment" pour intuiter si deux séries comme 'abbaab' et 'aabbab' donnent le même résultat ?

[Doraki]

Ben si tu comptes seulement l'espérance du nombre d'occurences de telle ou telle séquence, cette espérance dépend seulement de la longueur de la séquence et pas de son contenu : c'est la même quelle que soit la longueur.

Ainsi, en écrivant tous les mots possibles de n lettres il y a au total autant de fois "aa" que de "ab".
Seulement, il y a plus de fois où on a un grand nombre de "aa" sur un seul mot.
dans "aaaaaaa" il y a 6 fois "aa" alors que dans "abababa" il y a que 3 fois "ab".
Ca veut dure que les "aa" sont absolument pas disposés "équitablement", comparé à la répartition des "ab".

Après, pour abbaab et aabbab, ben je conjecturerais qu'il faut regarder les recoupements entre le début et la fin de la séquence :
abbaabbaab contient 2 fois abbaab et il faut 10 lettres.
aabbabaabbab contient 2 fois aabbab et il faut 12 lettres.

Donc aabbab est mieux réparti que abbaab et la probabilité qu'on l'ait au moins une fois approche 1 plus vite pour aabbab que pour abbaab

[Ben314]

Je sais pas comment tu as fait les calculs, mais je vient de me rappeller que, pour ce genre de trucs, le plus simple c'est un modèle avec un graphe et des "matrices de transitions" (c'est plus ou moins des chaines de Markoff, il me semble)

Ca me rapelle un "paradoxe" que j'avais lu dans un bouquin :

On vous propose un jeu type pile ou façe : avant de commencer à jouer, vous et votre adversaire choisissez une série de 3 de long (par exemple PPF et FPF), les deux séries devant bien évidement être différentes. Ensuite, on jette la piece j'usqu'à ce que l'une des deux séries sorte
(exemple PFFPPPPF) celui qui a parié sur cette série gagne la mise.
Votre adversaire vous propose poliment de choisir votre série en premier.
Laquelle choisisez vous ? Pourquoi ?

[Ben314]

Allez, tient, je fait remonter ce post...
Qu'est-ce que vous chosissez comme série de 3 ? (les jeux sont fait, rien ne vas plus...)

[beagle]

Si j'écoute Doraki,
cela pourrait ètre bien de choisir FFF ou PPP,
mais bon j'ai lu vite et pas trop regardé.

[Ben314]

Si tu prend FFF, je prend PFF.
Quelles sont tes chances de gagner ?
(attention, par rapport au p.b. de départ, ce n'est pas la même question : ici on s'arrète dés qu'une des deux série sort et le nombre de tirages n'est pas limité...)

[beagle]

Bonsoir Ben,
bon, ça m'apprendra à (mal) copier sur les bons.
Je suis pas dans une forme extra ce jour, et pas sur d'ètre au niveau.
Je passe pour ce soir.
juste un joker:
il y a un meilleur choix?
ou bien le choix du premier permet le meilleur choix pour le deuxième?
(c'est de la parano, je me méfie de ta phrase, par politesse on laisse choisir en premier,...)

[Ben314]

Effectivement le mot "politesse" est trés mal choisi :
Le coté "paradoxal" de cette "amusette" est que, quelque soit le choix de la série de 3 du premier joueur, le second joueur pourra trouver une série de 3 qui lui permette de gagner (strictement) plus d'une fois sur 2.
En plus, le choix FFF est le pire possible, si l'autre prend PFF, tes chances de gagner sont de 1/8 et c'est assez façile à voir...

[Pafapafadidel]

Tes deux derniers choix doivent être les deux premiers de l'adversaire, et ton premier choix doit faire en sorte que tes deux premiers choix ne soient pas les deux derniers de l'adversaire. Ainsi il y a toutes les chances que ton mot tombe en premier (plus d'une chance sur deux en tout cas).

[Ben314]

Tes deux derniers choix doivent être les deux premiers de l'adversaire, et ton premier choix doit faire en sorte que tes deux premiers choix ne soient pas les deux derniers de l'adversaire. Ainsi il y a toutes les chances que ton mot tombe en premier (plus d'une chance sur deux en tout cas).

Je ne comprend pas ce que tu veut dire : tu ne choisis qu'une série de 3...

[Pafapafadidel]

Ba oui, je parle de "tes deux derniers choix" et "ton premier choix", ce qui fait trois choix.

[Ben314]

Oui, je n'avais pas compris comme ça le mot "choix" (donc j'avais rien compris") c'est effectivement la bonne idée, mais normalement la "régle" stipule que tu choisi tes trois 'choix' puis l'adversaire choisi les 3 siens.
En résumé, à tout les coup tu est cuit...

P.S. n'empèche que les calculs ne sont pas trop faciles : si je choisi premier PFP quel sera ton choix et quelle sont mes chances de gagner ?

[Pafapafadidel]

Mon choix sera alors PPF en suivant ma règle. Pour les chances de gagner, c'est pas immédiat de savoir comment s'y prendre avec les calculs. Déjà si deux piles sortent je gagne direct, alors qu'il n'y a pas de telle combinaison gagnante pour mon adversaire, ce qui montre bien mon avantage. Après, savoir quelles sont mes chances précisément, faut un peu travailler.

[Ben314]

Ton choix est le bon et ton début de preuve montre que tu as... plus d'une chance sur 4 de gagner.
Aprés, effectivement je ne sais donner la valeur exacte (et montrer qu'elle est > 1/2) qu'aprés un peu de calcul...
Si ça te tente, tu peut essayer (il faut déjà trouver quels calculs faire...)