Forum de mathématiques - Bibm@th.net

passant

Membre

Inscription : 09-05-2020

Messages : 8

Probabilités. Coïncidences entre chaines binaires.

Bonjour,

Je cherche à déterminer la probabilité de trouver une séquence donnée de 0 et de 1, de longueur p, dans une séquence aléatoire de 0 et de 1 de longueur n, avec n>p.

Mon raisonnement est le suivant:

A partir d'un point a1 de la chaine aléatoire, je considère la séquence des p chiffres qui commence en a1, soient  a1 a2 ... ap

Si je trouve une coïncidence avec le motif m cherché, alors  a_1 = m_1, a_2 = m_2, ... a_p = m_p

La probabilité que cela arrive c'est la probabilité que a_i soit identique au chiffre m_i recherché, soit 1/2

Comme ce sont p évènements indépendants les probabilités se multiplient, donc la probabilité est  1/2 à la puissance p

Mais dans une chaine de longueur n il existe n-p possibilités de trouver une coïncidence, en partant du premier chiffre de la suite aléatoire, puis le second, etc. jusqu'au chiffre de rang n-p.

Ces évènements sont incompatibles entre eux, donc les n-p probabilités s'additionnent.

La formule que je cherche c'est donc ( 1/2 à la puissance p) x (n-p)

Ce résultat est visiblement faux, car il suffit d'augmenter suffisamment n pour que la probabilité dépasse 1.

Mais je ne comprends pas comment je me suis trompé ?

Question subsidiaire: quelle serait la solution ?  Et merci d'avance.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 349

Re : Probabilités. Coïncidences entre chaines binaires.

Bonjour,

  Là où tu t'es trompé : tes événements ne sont pas incompatibles!
Comment faire pour trouver la solution : considérer l'événement contraire!

F.

passant

Membre

Inscription : 09-05-2020

Messages : 8

Re : Probabilités. Coïncidences entre chaines binaires.

Exact. On peut avoir deux coïncidences en même temps. Merci.

passant

Membre

Inscription : 09-05-2020

Messages : 8

Re : Probabilités. Coïncidences entre chaines binaires.

Si je considère la probabilité que deux motifs soient différents c'est [tex]1-\frac{1}{2^p}[/tex]

Comme j'ai n-p motifs différents dans la séquence aléatoire cela devient  [tex](1-\frac{1}{2^p})^{(n-p)}[/tex]

L'évènement inverse c'est de trouver au moins un motif qui coïncide ce qui donne

[tex]1-(1-\frac{1}{2^p})^{(n-p)}[/tex]

Mais cette fois j'ai considéré que c'étaient des évènements indépendants pour multiplier, ce qui me parait bizarre car les n-p motifs de la chaine aléatoire se chevauchent ?

passant13

Invité

Re : Probabilités. Coïncidences entre chaines binaires.

Re-bonjour,

A la réflexion ma formule semble vraiment fausse.

J'ai calculé la probabilité de coïncidences entre des séquences de p bits qui se chevauchent et donc leurs probabilités ne sont pas indépendantes.

Si quelqu'un a un indice pour ce type de problème.

passant00

Invité

Re : Probabilités. Coïncidences entre chaines binaires.

Salut,

Mon exercice n'a pas attiré les foules. C'est préférable parce que finalement cet exercice est impossible !

Démonstration.

Soit n = 4 et p = 2

On écrit la suite des 16 chaines binaires possibles de longueur 4 puis on calcule la probabilité de trouver les sous chaines 00 et 01

Elles sont différentes.

Donc dans le cas général il est impossible de déterminer la probabilité d'une sous chaine quelconque puisque cette probabilité dépend de la sous chaine recherchée.

Une recherche sur internet montre que l'on peut seulement calculer le "temps d'atteinte d'une première occurrence d'un motif" en utilisant des chaines de Markov.