Table des matières

1 Propriété de Markov, propriété de Markov forte

Voici deux propriétés proches de la propriété de Markov (simple ou forte).

• pour la “propriété de Markov” : si (X₁,X₂,…,X_n,…) est une suite i.i.d. selon la loi de X₁ alors (X_p+1,X_p+2,…,X_p+n,…) est aussi une suite i.i.d. selon la loi de X₁ indépendante de la tribu σ(X₁,X₂,…,X_p).
• pour la “propriété de Markov forte” : si τ est un temps d’arrêt par rapport à la filtration ℱ_n = σ(X₁,…,X_n) alors (X_τ+1,X_τ+2,…,X_τ+n,…) est aussi une suite i.i.d. selon la loi de X₁ indépendante de la tribu σ(X₁,X₂,…,X_τ).

Donnons en quelques applications simples à des tirages indépendants à pile (p) ou face (1 − p), (X₁,X₂,…,X_n,…).

Soit τ_P = inf{n ≥ 1,X_n = P}. On sait (ou on a oublié ...) que τ_P suit une loi géomètrique de paramètre p. Si on a oublié, voici une façon simple de retrouver la fonction génératrice, on a :

(1)

où τ′_P suit la même loi que τ_P et est indépendante de X₁ (c’est une conséquence de la propriété de Markov). On en déduit que :

Ce qui donne la fonction génératrice de τ_P (sans calculs pénibles)

Il est facile de vérifier que c’est bien la fonction génératrice de la loi géométrique.

On obtient aussi, sans calcul, l’espérance de τ_P en prenant l’espérance de l’équation (1) :

équation qui se résoud en E(τ_P ) = 1∕p. Pour la variance on élève l’équation (1) au carré et l’on prend l’espérance pour obtenir :

qui se résoud en E(τ_P ²) = (1 + 2(1 − p)E(τ _P ))∕p, puis Var(τ_P ) = (1 − p)∕p².

Lorsque p = 1∕2, on a ainsi E(τ_P ) = 2 et Var(τ_P ) = 2.

Les lois de τ_PF , τ_FP , τ_FF , τ_PP On peut aussi calculer les lois de temps d’atteinte de “mots” de longueur 2. Par exemple si τ_PF = inf{n ≥ 1,X_n−1 = P,X_n−1 = F}, il est facile de se convaincre (propriété de Markov forte) que

et d’en déduire la moyenne, la variance et la fonction génératrice de τ_PF (exercice). On en déduit, par exemple, immédiatement que lorsque p = 1∕2, E(τ_PF ) = 2 + 2 = 4 et Var(τ_PF ) = 2 + 2 = 4 !

Pour calculer la loi de τ_PP , c’est à peine plus compliqué, on écrit

où τ_PP ⁽¹⁾ est indépendant de X ₁ et de même loi que τ_PP et τ_PP ⁽²⁾ est indépendant de (X₁,X₂) et de même loi que τ_PP (propriété de Markov simple). On obtient la fonction génératrice, la moyenne ou la variance par les mêmes techniques que précédemment.

Nous allons voir que l’on peut systématiser ce genre de technique pour obtenir la loi des temps d’atteinte de tous les mots et ce pour tous les alphabets.

2 Le cadre général

On recherche un pattern M = (c₁,…,c_n), où n est la longueur du pattern, dans un chaine de caractères (S_i,i ≥ 1) supposé i.i.d. sur un alphabet fini E avec une loi donnée q = (q_i,i ∈ E), q_i > 0 est supposé non nul pour tout i (sinon il suffit de retirer le caractère de l’alphabet considéré).

On appelle τ le temps d’apparition du pattern dans la chaîne

Ce temps est fini presque sûrement, car plus petit que le produit de n fois une v.a. de loi géometrique de probabilité de succés q(M) := ∏ ₁ⁿq(c _i) > 0. Cela prouve aussi qu’il est de moyenne et de variance finie (et, plus généralement, que tous ses moments sont finis).

On va representer τ à l’aide d’une chaine de Markov (Z_n,n ≥ 0) dont les états sont (0,1,…,n). On identifie l’état j à la sous chaine de M, (c₁,…,c_j), où j represente le début du pattern M de longueur j dont la coïncidence a été déjà vérifiée à la position i, formellement :

avec, par convention, Z_i = 0 lorsque l’ensemble est vide.

Lorsque et l’état Z_i = n on a trouvé la chaîne M : τ est le temps d’atteinte de n par ce processus.

Nous allons voir que Z est une chaîne de Markov et calculer sa matrice de transition.

Pour cela nous aurons besoin de la fonction overlap(x,y) qui à deux chaînes de caractères x et y fait correspondre le plus long postfixe de la chaîne y qui est un suffixe de la chaîne x (voir page 11 pour un code ScicosLab qui fait ce travail). Formellement, si n_y est la longueur de y et n_x celle de x :

Avec cette notation on a :

Z_i+1 est donc une fonction de Z_i et de S_i+1, ce qui prouve que c’est un chaîne de Markov et l’on peut calculer sa matrice de transition.

La matrice de transition Lorsque l’on est dans l’état i, à l’instant l, et que l’on considère le caractère suivant de la chaîne S(l + 1)

1.

soit S(l + 1) = M(i + 1) et l’on passe à l’état i + 1

2.

sinon, on ne revient pas forcèment à l’état 0, mais on doit calculer le plus long postfixe de (c(1),…,c(i),S(l+1)) qui est un prefixe de M (le résultat peut être vide, bien sûr, auquel cas on revient en 0). Cette chaîne correspond à l’un des états (0,…,l) et la transition se fait vers cet état.

On notera P(M,E,q) la matrice de transition ainsi obtenue et P lorsque le contexte n’exige pas plus de précisions. P est une matrice de taille (n + 1) × (n + 1), si n est la longueur du pattern. P est une généralisation de la matrice de la chaîne en “dents de scie”.

Voir le code page 11 pour le code qui réalise le calcul de la matrice de la chaîne à partir des données (la chaîne M, l’alphabet E et sa fréquence q).

Calcul de la fonction génératrice de la loi de τ Soit ϕ_k(z) = E_k, la fonction génératrice de la loi de τ, lorsque la chaîne de Markov démarre en k ∈{0, 1,…,n}. En utilisant la propriété de Markov, on vérifie que, pour tout k ∈{0, 1,…,n − 1}

(3)

En tenant compte du fait que si y = n, τ = 0 et ϕ_n(z) = 1, on obtient l’équation, pour x ∈{0, 1,…,n − 1}

On peut réécrire matriciellement cette équation sous la forme

(4)

où Q est la matrice n × n, Q = (P(i,j), 0 ≤ i ≤ n − 1, 0 ≤ j ≤ n − 1) ; ϕ_∙(z) est le vecteur colonne (ϕ_i(z), 0 ≤ i ≤ n − 1)′ et P(∙,n) le vecteur colonne (P(i,n), 0 ≤ i ≤ n − 1)′.

Nous allons voir que cette équation a une solution unique sur le corps de fractions rationnelles d’inconnu z. En effet, si l’on a une solution à (I − zQ)u(z) = 0 avec u vecteur de fractions rationnelles, on peut en multipliant u(z) par le produit des dénominateurs du vecteur u(z), obtenir un vecteur de polynôme v(z) solution de v(z) = zQv(z). Supposons un tel vecteur de polynome v de la forme v(z) = v₀ + v₁z + + v_nzⁿ alors zPv(z) = zQv₀ + z²Qv ₁ + + zⁿ⁺¹Qv _n, et donc par récurrence v₀ = = v_n = 0. (I − zQ) est donc injectif et donc surjectif si on le considère comme une matrice sur le corps des fractions rationnelles. Ce qui prouve l’existence et l’unicité d’une fraction rationnelle solution à l’équation (4). Ceci prouve aussi que ϕ_i(z) est une fraction rationelle pour tout i ∈.

Voir le code page 12 pour l’implementation de ce calcul en Scilab (qui permet de faire du calcul sur les fractions rationnelles sur R) et page 13 pour le même code en Sage (qui permet de faire de l’arithmétique en précision illimitée à la différence de Scilab).

3 Calcul des moments

Par dérivation il est facile d’obtenir une équation pour le calcul de la moyenne et de la variance.

Calcul de la moyenne Noter que ϕ_i(z) est un fraction rationelle donc peut toujours être dérivée comme fraction rationelle autant de fois que souhaité. Par ailleurs, si ϕ_i(z) est représenté sous la forme :

P_i et Q_i étant deux polynômes sans facteurs communs, Q_i(1) ⁄= 0 (car si Q_i(1) = 0, P_i(1) ⁄= 0 et ϕ_i(1) = 1 est alors impossible). Il est facile d’en déduire que toutes les dérivées de ϕ_i(z) calculé en z = 1 sont finies. Ce qui prouve que τ a des moments de tout ordre (ce que l’on a déjà obtenu en majorant par un temps géométrique).

On dérive l’équation 1 pour obtenir

où ϕ′_∙(z) est le vecteur colonne (ϕ′₀(z),…,ϕ′_n−1(z)). En prenant z = 1, on obtient en tenant compte de ϕ_i(1) = 1

où 1 désigne le vecteur colonne (1,…, 1)′. Ce que l’on peut réécrire (il faut toutefois vérifier que 1 n’est pas valeur propre de Q¹ )

Calcul de la variance En dérivant une deuxième fois l’équation (1) on obtient, pour i ∈

où ϕ′′_∙(z) le vecteur colonne (ϕ′′₀(z),…,ϕ′′_n−1(z))′. Et en z = 1, on obtient

et donc (en tenant compte du fait que Q et (I − Q)⁻¹ commutent

Noter que (Q1)_i = 1 pour i = 0,…,n − 2 et que (Q1)_n−1 = 1 − P(n − 1,n).

Pour les programmes qui suivent, on utilise plutôt la forme

Lorsque P est à coefficient rationnel on peut faire des calculs exacts à l’aide d’un logiciel de calcul formel. (I − P) étant souvent difficile à inverser numériquement, ça peut être utile.

Voici page 11 pour le code correspondant en ScicosLab ainsi que pour quelques exemples d’utilisation.

4 Vers un algorithme efficace de recherche de pattern (Knuth-Morris-Pratt)

En s’inspirant de l’approche précédente, on peut concevoir un algorithme (proche de l’algorithme KMP) qui permet de rechercher une chaîne de caractère dans un texte en parcourant le texte séquentiellement (c’est à dire en avancant toujours de 1 caractère sans jamais avoir à revenir en arrière ou à sauter en avant dans le texte, ce qui est commode voire indispensable pour certain type de hardware). le programme qui suit n’est pas exactement l’algorithme KMP, mais il en donne l’idée essentielle.

Pour rendre ce schéma d’algorithme efficace et obtenir l’algorithme KMP, il faut être plus précis voir par exemple https://fr.wikipedia.org/wiki/Algorithme\_de\_Knuth-Morris-Pratt pour les détails.

5 TP en Scilab

• Ecrire la fonction qui calcule le prefixe de longueur maximale de x qui est un suffixe de y (ou de façon équivalente le suffixe de longueur maximale de y qui est un préfixe de x).
    function res=overlap(x,y)
      // Calcule un prefixe de longueur maximale de x qui est un suffixe de y
      for i=length(x):-1:1 do
        //QUESTION: prefixe = le prefixe de x de longueur i
        //REPONSE: prefixe = part(x,1:i);
        //QUESTION: suffixe = le suffixe de j de longueur i
        //REPONSE: suffixe = part(y,max(1,length(y)-i+1):length(y));
        if (prefixe==suffixe) then
          res=prefixe;return;
        end
      end
      res='';
    endfunction
• Calculer la matrice de transition de la chaîne de markov en fonction du pattern M, de l’alphabet E et de la loi de probabilité de cet alphabet q.
    function res=inc(n)
      // sert à décaler de 1 les indices des matrices commencant en 0
      res=n+1;
    endfunction
    
    function Matrice=markov_chain(M,E,q)
      // Calcule la matrice de transtion de la chaine de Markov
      //   M : la chaîne recherchée,
      //   E: l'aphabet,
      //   q: la probabité de chaque lettre supposée i.i.d. selon cette loi
      card_alphabet=length(E);
    
      // Construction de la matrice de transition
      Matrice=zeros(length(M)+1,length(M)+1);
      for i=0:length(M)-1 do
        for j=1:card_alphabet do
          // On rajoute la lettre E(j) à l'état courant
          proposition=part(M,1:i)+part(E,j);
          // on calcule le nouvel etat grâce à la fonction overlap
          to=overlap(M,proposition);
          indice_etat=length(to);// l'indice de l'etat, c'est sa longueur
          // rajout de la probabilité q(j) à la transition de i -> "to"
          //QUESTION: Matrice(inc(i), inc(indice_etat)) = <À COMPLÉTER>
          //REPONSE: Matrice(inc(i), inc(indice_etat)) =  ...
          //REPONSE:            Matrice(inc(i), inc(indice_etat)) + q(j);
        end
      end
      // Lorsque l'on a atteint l'etat "length(M)", c'est gagné, on s'arrête.
      Matrice(inc(length(M)),inc(length(M)))=1;
    endfunction
    function [moyenne,V]=moyenne_variance_tau(M,E,q)
      // Calcule la moyenne et la variance de |$\tau$|
      P=markov_chain(M,E,q);
      N=max(size(P))-1;
      Q=P(1:N,1:N);
    
      M=eye(N,N)-Q;
      M_moins_1=M^(-1);// calcule l'inverse la matrice M
    
      // Calcul de la moyenne |$\E(\tau)$|
      moyennes=M_moins_1*ones(N,1);
      //QUESTION: moyenne=<À COMPLÉTER>;
      //REPONSE: moyenne=moyennes(1,1);
    
      // Calcul de la variance
      //QUESTION: VV = <À COMPLÉTER>;// Calcul de |$\E(\tau(\tau-1))$|
      //REPONSE: VV = (M^(-1)) * 2 * Q * moyennes;// Calcul de |$\E(\tau(\tau-1))$|
      V=VV(1,1)+moyenne-moyenne^2;// On en déduit la variance.
    endfunction;
    // Tirage à Pile  ou Face
    alphabet="PF";proba_alphabet=[1/2,1/2];
    
    W='P';
    // loi géomètrique on doit trouver 2 et 2
    [m,v]=moyenne_variance_tau(W,alphabet,proba_alphabet)
    
    W='FP';
    // on doit trouver 4 et 4
    [m,v]=moyenne_variance_tau(W,alphabet,proba_alphabet)
    
    W='PP';
    // on doit trouver 6 et 22
    [m,v]=moyenne_variance_tau(W,alphabet,proba_alphabet)
    // Cette loi est différente de la précedente
    // Le génome, 4 bases CATG
    alphabet="CATG";proba_alphabet=[1/4,1/4,1/4,1/4];
    
    W='CCTAAGGA'
    [m,v]=moyenne_variance_tau(W,alphabet,proba_alphabet)
    // Alphabet de 27 lettres
    alphabet="abcdefghijklmnopqrstuvwwyz"+' ';
    N=length(alphabet);
    proba_alphabet=ones(1,N)/N;
    W='bonjour';
    [m,v]=moyenne_variance_tau(W,alphabet,proba_alphabet)
    function phi=fonction_generatrice(M,E,q)
      // Calcule la fonction génératrice de la loi de |$\tau$|
      // P est la matrice de transition de taille |$N+1\times N+1$|
      P=markov_chain(M,E,q);
      N=max(size(P))-1;
    
      // On resoud l'equation dans le corps des fractions rationnelles
      Q=P(1:N,1:N);
      Id=eye(N,N);
      z=poly(0,"z");
      M=Id-z*Q;
      A=(1/M)*z*P(1:N,N+1);// 1/M calcule l'inverse la matrice M
      phi=A(1,1);
    endfunction;

6 Listing Sage

Malheureusement, on ne peut traiter que des chaînes de caractères longueur petite (≈ 10) si l’on se contente de l’arithmétique en précision limitée standard. Pour traiter des chaînes plus longues il faut faire du calcul en précision illimitée dans Q. Voici une implementation en sage (on peut télécharger librement sage pour linux, macos ou windows sur le site http://www.sagemath.org) pour un cas où M est plus long (longueur l = 43, on néglige accents et majuscules mais on rajoute le ' ' à l’alphabet, de 27 lettres donc).

Cette chaîne est plutôt simple, puisque, lorsque l > 0 soit on passe de l à l + 1 avec proba 1∕27, on retourne en 1 avec proba 1∕27 (cas d’échec mais avec comme nouvelle lettre 'l'), sinon on retourne en 0 avec proba 25∕27. Le cas l = 0 est particulier, la probabilité de rester en 0 est de 26∕27 et d’aller en 1 de 1∕27.