Bonjour,
Voici un problème assez concret pour une analyse de risque:
 
J'ai une chaîne de n caractères X. X peut prendre 35 valeurs aléatoirement. Quelle est la probabilité de trouver une chaîne de p caractères inscrite dans la chaîne de n caractères?
 
 
Si quelqu'un a une démo succincte et percutante je suis preneur!

C'est pas des stats c'est des probas .

Pas très compliqué comme pb, tu comptes le nombres de chaînes de p caractères, le nombre de combinaisons possibles au total et tu fais ta division. Si tu as tout bien écris sous forme de factorielles ça devrait se simplifier un peu en plus.

Ok pour l'ensemble des possibles c'est n^35. Facile.
 
Mais pour l'ensemble des favorables c'est plus difficile.
 
Caylayron j'aimerais connaitre un peu plus en détail ta méthode pour calculer le nombre de combi possibles. Que veux tu dire par "écrire sous forme de factorielles"? Considères tu l'ensemble des permutations S du groupe G = {chaine p, X1, X2...} -> #S = (n-p)! ? Le problème est au niveau de la généralisation pour tout X1, X2... :X1, X2... peuvent former des "chaines p" (et à ce moment on compte des éléments plusieurs fois).
 
Je n'arrive pas par à attaquer le problème par dénombrement direct des favorables. Peut être en dénombrant les défavorables c'est plus facile??

Bon, par les "factorielles" voici mon approche:
 
on considère la chaine p: P1,P2,P3,P4... Pp = P
on considère la chaine n: P, X1, X2, X3... Xn
L'ensemble des permutations pour une chaine p et pour un ensemble de caractères n-p est:
s = (n-p+1)!
On généralise pour tout Xn compris entre 1 et 35:  
S'(p,n) = (n-p+1)! 35^(n-p)
Le problème de S'(p,n) c'est que:
- lorsque la chaine n comprend 2 chaines p, le cas est compté 2 fois
- lorsque la chaine n comprend 3 chaines p, le cas est compté 3 fois
...
- lorque la chaine n comprend k chaines p, le cas est compté
k fois
 
Et max(k)= E(n/p) (E=partie entière)
 
Il faut donc retrancher les cas "chaine p multiple". -> S"(p,n)
S(p,n) = S'(p,n) - S"(p,n)
S'(p,n) =  (n-p+1)!35^(n-p)
S"(p,n) =  Sigma(2 <= k <= E(n/p))(k-1)(n-k(p-1))! 35^(n-kp)
 
et donc
P(p,n) = (S'(p,n) - S"(p,n)) / 35^n
 
C'est une formule qui me parait très lourde. J'ai beaucoup de doutes.
Quelqu'un pourrait confirmer / infirmer ce résultat?  
Je suis preneur d'une solution plus sexy.

Euh aiola le nombre des possibles c'est 35^n et non n^35?

Peut-etre était-ce pour voir si tu suivais ?
Effectivement, c'est bien 35^n...

Pour supprimer les cas où on compte deux fois, il faut bien voir qu'il s'agit de retrancher le nombre de combinaisons palyndromes (qui peuvent être lu indifféremment de gauche à droite et de droite à gauche) pour ne pas les compter 2 fois en permuttant et non pas retrancher pas toutes celles contenant plusieures chaînes p (une chaîne ne contenant que des caractères identiques contient une chaîne p et doit être compté une fois).
C'est compliqué j'en conviens (bcp plus que ce que j'avais pensé en lisant le sujet rapidement ) mais je ne vois pas trop d'autre méthode.

Oui effectivement j'ai oublié pas mal de cas à retrancher. Mais cette approche est trop compliqué.
 
Si l'on prend l'ensemble des défavorables le problème de dénombrement se résume au calcul du nombre de chaine n ne contenant pas la chaine p. Peut être c'est plus facile de cette manière?
Des idées?

Avec une petite relation de recurrence... ça le fait peut être

Putain je ne vais pas en dormir du week end!
Donc p fixé pour n>p  
Xn=#{chaines de longueur n contenant au moins une fois la chaine de longueur p}
Zn=#{chaines de longueur n ne contenant pas la chaine de longueur p}
On a
Xn + Zn = 35^n
et
Xn+1 - Xn = Z(n-(p-1))
Donc
Xn+1 - Xn = 35^(n-(p-1)) - X(n-(p-1))
pour n>=p
Xn+1 = 35^(n-(p-1)) + (Xn - X(n-(p-1))
reste à trouver Xp et X2p+1

En fait il n'y a pas de solution au probleme. Ca dépend de la chaîne de longueur p.

Par exemple pour p = 2, n= 3 et les caractères 1 et 2

les tirages possibles sont :
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

On constate qu'il y a 3 chaînes avec (1 1), alors qu'il y a 4 chaînes pour (1 2)

PS : c'est pour ça que c'était si dur à trouver

Par contre, si on considère que la chaîne de longueur p est constituée uniquement d'un symbole donné, ça se resout.
 
Avec une bonne chaîne de Markov ça se fait, au moins numériquement

Bon si on ne trouve pas une solution, pourrait on au moins trouver un encadrement au plus près quelquesoit la chaîne?..

en fait (après réflexion) pour toutes les chaines il y a un calcul exact qui peut se faire grâce aux chaines de Markov. Si p est petit c'est pas trop dur, si p est grand faut un peu programmer pour écrire le calcul.
 
Tu as un exemple précis?

Non l'idée est d'avoir un encadrement quelquesoit p.

on peut minorer la probabilité car je crois que le moins probable est d'avoir une suite de symboles identiques.