Modèle d’Ewens

Souvent, lorsque nous faisons de l’analyse d’algorithmes dans le cas moyen nous considérons, par défaut, que l’entrée est distribuée selon une loi uniforme. En pratique, il n’est pas rare d’avoir une incertitude sur l’entrée et de considérer que cette dernière est bien aléatoire. Le choix de la distribution uniforme n’est cependant pas nécessairement un choix justifié si nous essayons de faire une analyse qui se veut proche de la réalité. Nous avons vu au cours du chapitre 4, qu’il existe des algorithmes de tri qui s’adaptent au désordre de la séquence d’entrée à trier. Ces algorithmes, comme c’est le cas de TimSort par exemple, se montrent efficaces en pratique. Cependant, si nous essayons de faire l’analyse en moyenne pour le cas uniforme de ces algorithmes, les résultats risquent de nous en apprendre peu sur ce qui se passe en pratique. Il est préférable de mettre plus de poids aux cas où le désordre est petit qui sont des cas favorables pour ces algorithmes. Pour le problème du tri, il y a des utilisations où ce genre de considérations ne sont pas déraisonnables. Par exemple, il est possible qu’un tri soit utilisé régulièrement pour trier certaines données qui ont subit de légères modifications par des ajouts de nouvelles clefs ou des altérations. Pour cet exemple, les données sont donc triées à la fin de chaque appel à ce tri et présentent donc peu de désordres. Nous avons vu qu’il existe des résultats qui mettent en évidence cette utilisation du désordre dans le pire cas, nous souhaiterions qu’il existe un équivalent pour le cas moyen. L’analyse lisse qui consiste à prendre le pire cas et de le perturber par un bruit (souvent gaussien), est un exemple d’analyse en moyenne qui n’utilise pas une distribution uniforme. Cette méthode a, par exemple, été utilisée pour l’algorithme du simplex qui permet de résoudre des programmes linéaires, et à montrer que lorsque l’entrée est bruitée par un bruit gaussien, l’algorithme se comportait en temps polynomiale (voir [41]). Cette méthode donne une bonne idée de la raison pour laquelle bien que le pire cas du simplex soit exponentielle, ce dernier se comporte souvent bien mieux en pratique. L’analyse lisse s’applique bien pour les cas où l’entrée appartient à un domaine continu. Or, nous nous intéressons pour notre part à l’ensemble des permutations de tailles n et dont le domaine est discret. Pour cette raison, nous n’allons pas dans ce chapitre appliquer une analyse lisse, mais nous allons nous intéresser à un type de distribution non-uniforme sur l’ensemble des permutations Sn. Le but étant de favoriser, si nous avons une mesure de désordre m(X) comme définit lors du chapitre 4, les cas où m(π) est petit pour π ∈ Sn. Plus concrètement, ce chapitre se base sur une distribution connue des probabilistes, à savoir la distribution d’Ewens. Cette distribution permet de favoriser l’apparition de permutations de Sn en fonction du nombre de cycles de ces derniers. Ce chapitre donne en détail les résultats de nos travaux publiés pour la conférence AofA de 2016 [7]. Dans ces travaux nous avons généralisé la distribution d’Ewens à de nouvelles statistiques. En particulier, nous avons étudié le cas du modèle d’Ewens qui dépend du nombre de max-records qui est comme nous l’avons vu au cours du chapitre 4 associé à une mesure de désordre.

Algorithme de tri optimal pour la mesure mrec

Pour motiver le choix de ces distributions, nous allons nous intéresser à un algorithme de tri qui s’adapte au nombre de records. Pour rappel, si une séquence X a rec(X) max-records, alors sa mesure est donnée par mrec(X) = |X| − rec(X). Nous pouvons également démontrer qu’il existe une borne inférieure pour les algorithmes de tri par comparaisons. Cette borne est donnée dans la Proposition 22. Proposition 22. Le problème du tri d’une séquence X, de taille n, telle que mrec(X) = k admet une borne inférieure de Ω(n + k log k) comparaisons. Démonstration. Il suffit d’appliquer le théorème 7 qui, pour rappel, nous dit dans le cas de mrec que le problème du tri admet une borne inférieure de la forme Ω(max(n, log|below(X, mrec))|) avec below(X, mrec) qui sont les permutations σ de taille n telles que mrec(σ) ≤ k. Pour obtenir le résultat, il ne nous reste donc qu’à déterminer ce qu’est le cardinal de cet ensemble. En particulier, nous allons démontrer l’inégalité |below(X, mrec)| ≥ k! Construisons l’ensemble Λ = {σ ∈ Sn |σ(1) = 1, σ(2) = 2, . . . , σ(n−k) = n−k} qui est l’ensemble des permutations pour lesquelles les n − k premiers éléments sont des points fixes. Observons que ces points fixes sont également des maxrecords dans ce cas et donc mrec(σ) ≤ k pour σ ∈ Λ. Ainsi, nous avons la relation Λ ⊂ below(X, mrec). Comme les k derniers éléments peuvent être fixés indépendamment pour toute permutation de Λ, nous avons que son cardinal est égal à k!. Cette égalité nous permet de démontrer l’inéquation. En utilisant cette inéquation nous prouvons le résultat annoncé. Un algorithme adaptatif qui atteint cette borne est alors considéré comme optimal pour cette mesure d’après les travaux de Mannila. L’algorithme 18 tri une séquence en s’adaptant à cette mesure de désordre. Cette algorithme fonctionne en plusieurs étapes. La première étape est l’extraction des max-records qui sont stockés dans l’ordre dans une sous-séquence temporaire que nous nommons ici Y . Comme ils sont dans l’ordre et par définition de ce qu’est un max-records, la séquence Y est donc triée. La deuxième étape est l’utilisation d’une fonction de 163 tri auxiliaire pour trier les éléments restants dans X qui ne sont pas des records. La troisième étape est la fusion des deux séquences triées X et Y qui permet d’obtenir la sortie. La proposition qui suit montre que l’algorithme est optimal pour la mesure mrec. Proposition 23. L’algorithme 18 peut trier une séquence X de taille n, tel que mrec(X) = k en O(n + k log k) comparaisons. Démonstration. Pour la première étape, il est suffisant de faire un balayage de la séquence en retenant le dernier max-record qui a été rencontré. Cet étape est donc équivalent à la recherche du maximum de X et nécessite n − 1 comparaisons. Pour la deuxième étape, le nombre d’éléments à trier restant dans X est exactement mrec(X) = k. Si l’algorithme de tri auxiliaire utilisé est en O(k log k), comme par exemple le tri fusion, alors cet étape nécessite O(k log k) comparaisons. La troisième étape est une fusion de X et Y ce qui demande n − 1 comparaisons dans le pire des cas. En combinant la contribution de ces trois étapes, nous obtenons le résultat annoncé. L’étude d’une distribution qui favorise l’apparition de records dans une permutation est en partie motivée par le souhait de pouvoir analyser en moyenne l’Algorithme 18 qui joue le rôle d’exemple jouet. 6.2 Distribution d’Ewens Nous allons dès à présent donner une définition d’une distribution connue dans la littérature par les probabilistes, à savoir la distribution d’Ewens. Il s’agit d’une distribution non-uniforme qui a l’avantage de favoriser les permutations qui ont un petit ou un grand nombre de cycles. Concrètement, cette distribution est paramétrée par une valeur réelle positive que nous noterons par la suite θ. Ce paramètre va favoriser l’apparition de cycles si θ > 1 et va, au contraire, favoriser les permutations qui présentent peu de cycles si θ < 1. Le cas où θ = 1 donne la distribution uniforme. Voyons maintenant comment est définie la probabilité d’avoir une permutation σ ∈ Sn sous cette distribution. Définition 24. Nous définissons la fonction wθ,n : Sn → R + qui associe pour tout paramètre θ > 0 un poids à une permutation de taille n. La fonction est définie par l’équation suivante pour tout σ ∈ Sn, wθ,n(σ) = θ cyc(σ) . (6.1) Nous notons par la suite le poids total Wθ,n qui est la somme de tous des poids de toutes les permutations de taille n, soit Wθ,n = X σ∈Sn wθ,nσ. (6.2) Définition 25. Pour toutes permutations σ ∈ Sn, la fonction définie par la relation Pθ,n(σ) = wθ,n(σ) Wθ,n 164 est une mesure de probabilité. La distribution engendrée par cette mesure de probabilité est nommée la distribution d’Ewens. Remarque. Comme cette distribution fait intervenir le nombre de cycles, il est naturel de voir apparaitre les nombres de Stirling de la première espèce nonsignés pour certaines identités. Ces nombres de Stirling comptent le nombre de permutations de taille n qui sont composées d’exactement k cycles. Nous notons ces nombres sn,k. Une identité évidente que nous avons est donnée par l’équation suivante : Wθ,n = Xn k=0 sn,kθ k . (6.3) De cette remarque nous pouvons facilement démontrer le Lemme 17. Lemme 17. Soit x (n) = Qn−1 k=0 x + k La fonction de Pochhammer, le poids total admet l’expression Wθ,n = θ (n) . (6.4) Démonstration. Comme Wθ,n = Pn k=0 sn,kθ k , il suffit d’appliquer directement le Lemme 2 vu au cours du chapitre 3. 6.3 Généralisation à d’autres statistiques Nous venons de voir le modèle classique de la distribution d’Ewens. Il est naturel de généraliser cette distribution pour toute statistique χn : Sn → R +. L’idée est de remplacer la définition du poids en remplaçant les apparitions de cyc(σ) par la statistique χ(σ). Nous modifions donc nos définitions en conséquence. Définition 26. Nous définissons la fonction wθ,n,χ : Sn → R + qui associe pour tout paramètre θ > 0 un poids à une permutation de taille n. La fonction est définie par l’équation suivante pour tout σ ∈ Sn, wθ,n,χ(σ) = θ χ(σ) . (6.5) Le poids total Wθ,n,χ est la somme de tous des poids de toutes les permutations Wθ,n,χ = X σ∈Sn wθ,n,χσ. (6.6) Définition 27. Pour toutes permutations σ ∈ Sn, la fonction définie par la relation Pθ,n,χ(σ) = wθ,n,χ(σ) Wθ,n,χ est une mesure de probabilité. La distribution engendrée par cette mesure de probabilité est nommée la distribution d’Ewens généralisée à la statistique χ. Remarque. Si θ = 1, la distribution d’Ewens est encore une fois équivalente à la distribution uniforme. Chaque permutation ayant le même poids égal à 1. Il est possible dans la littérature de trouver une distribution d’Ewens généralisée aux inversions connue sous le nom de distribution de Mallow. Cette distribution a été introduite par le statisticien Mallow, plus de détails sur cette distributions peuvent être trouvés dans l’article de Gladkich et Peled.