Partiel de probabilités et applications à l’algorithmique Natacha Portier le 17 avril 2002

Notes de cours et de TD autorisées Rédaction soignée indispensable !

Question 1 : Marche aléatoire en dimension k ≥ 3 Soit S = Z^{k} l’espace des états. Le point y = (x_{1}, ..., x_{j−1}, x_{j} ± 1, x_{j+1}, ..., x_{k}) est dit voisin de x = (x_{1}, ..., x_{k}). La probabilité de transition d’un état x à un état voisin y est p_{xy} = 1/2k. Question 1,1 Pour k = 3, donner la probabilité P_{2n} de revenir à son point de départ en 2n coups. Question 1,2 Soit c_{n} le maximum de n!/(n_{1}!n_{2}!n_{3}!) quand n_{1}, n_{2} et n_{3} sont des entiers naturels tels que n_{1} + n_{2} + n_{3} = n et soient N_{1}, N_{2} et N_{3} les entiers pour lesquels il est réalisé. Montrer que pour tout i compris entre 1 et 3 on a

⌊n/3⌋ ≤ N_{i} ≤ ⌊n/3⌋ + 1

Question 1,3 Donner la valeur exacte de c_{n}. Question 1,4

Montrer que ∑_{n_{1}+n_{2}+n_{3}=n} \frac{n!}{n_{1}!n_{2}!n_{3}!} \frac{1}{3^{n}} = 1 et en déduire ∑_{n_{1}+n_{2}+n_{3}=n} (\frac{n!}{n_{1}!n_{2}!n_{3}!} \frac{1}{3^{n}} )^{2} ≤ \frac{c_{n}}{3^{n}}

et une borne pour P_{2n} dans le cas k = 3. Question 1,5 L’état 0 est-il transitoire ou récurrent dans le cas k = 3 ? Question 1,6 L’état 0 est-il transitoire ou récurrent pour un entier k > 3 quelconque ? On reprendra les questions précédentes dans le cas k > 3 quelconque pour y répondre.

Question 2 : Tables de hachage

On considère un ensemble d’objets auxquels on associe bijectivement des clés (clef(x) est la clé de x). Les clés sont choisies dans un ensemble U de grande taille appelé univers. On veut ranger n objets dans un tableau. Lorsque U est grand on ne peut pas réserver un tableau de taille suffisante pour toutes les clés potentielles. Une fonction de hachage h est alors une fonction de U dans {0; 1; …; m − 1} et la table de hachage T est un tableau T [0 … m − 1]. Lorsque deux clefs différentes utilisées k et k′ ont la même image, on dit qu’il y a collision.

Question 2,1 : hachage avec chaînes

La première façon de résoudre les collisions est d’utiliser des chaînes. La case T [j] contient un pointeur vers une liste chaînée. C’est NIL si la liste est vide. La procédure inserer(T, x) insère x à la tête de la liste T [h(clef(x))]. La procédure rechercher(T, k) recherche l’élément de clé k dans la liste T [h(k)]. La procédure effacer(T, x) efface x de la liste T [h(clef(x))].

On choisit au hasard les n objets à insérer dans la table. Soit n_{j} la variable aléatoire représentant la longueur de la chaîne T [j]. On a n = n_{0} + ⋯ + n_{m−1}. On suppose que pour tout j l’espérance de n_{j} est α = n/m.

Les opérations suivantes comptent un temps 1 : calcul de h(k) pour une clé k, comparaison entre deux clés ou entre deux variables, assignation d’une valeur à une clé ou à une variable.

Question 2,1,1

Soit k la clé d’un élément, choisi au hasard hors de la table et t_{1} la variable aléatoire qui représente le temps de calcul de rechercher(T, k). Calculer l’espérance de t_{1}.

Question 2,1,2

On fait de plus l’hypothèse de hachage uniforme simple : {h(u)|u ∈ U} est un ensemble de variables aléatoires indépendantes et identiquement distribuées, de loi uniforme sur {0; 1; …; m − 1}. Quelle est l’espérance du nombre de collisions dans la table, i.e. du cardinal de {{i, j}|k_{i} ≠ k_{j} et h(k_{i}) = h(k_{j})} ? On pourra utiliser pour le calcul les variables aléatoires X_{i,j}, fonctions indicatrices de {h(k_{i}) = h(k_{j})}.

Question 2,1,3

On fait l’hypothèse de hachage uniforme simple. On choisit la clé k uniformément sur les clés de tous les éléments présents dans la table. Soit t_{2} la variable aléatoire qui représente le temps de calcul de rechercher(T, k). Calculer l’espérance de t_{2}.

Indication : On pourra considérer les objets présents dans la table x_{1}, ..., x_{n} dans l’ordre où ils y ont été insérés, puis exprimer t_{2} en fonction des X_{i,j}.

Question 2,2 : adressage ouvert

Soit α = n/m < 1. La fonction de hachage h est maintenant une fonction de U × {0; 1; …; m − 1} dans {0; 1; …; m − 1} telle que pour toute clé k la suite h[k] = h(k, 0); …; h(k, m − 1) soit une permutation de {0; 1; …; m − 1}. On stocke et on recherche les clés dans le tableau de la manière suivante :

inserer(T,k)
i<-0
répéter j<-h(k,i)
   si T[j] est vide alors T[j]=k et on s'arr^ete en retournant j
                    sinon i<-i+1
jusqu'à ce que i>m
erreur : capacité de la table dépassée
rechercher(T,k)
i<-0
répéter j<-h(k,i)
  si T[j]=k alors on s'arr^ete en retournant j
            sinon i<-i+1
jusqu'à ce que T[j] vide ou i>m
retourner NIL

On n’efface pas de clé. On fait l’hypothèse de hachage uniforme : {h[u]|u ∈ U} est un ensemble de variables aléatoires indépendantes et identiquement distribuées, de loi uniforme sur les permutations de {0; 1; …; m − 1}.

Question 2,2,1

Soit k la clé d’un élément, choisi au hasard hors de la table et t_{1} la variable aléatoire qui représente le temps de calcul de rechercher(T, k). Borner l’espérance de t_{1} en fonction de α.

Indication : soit X le nombre de cases du tableau visitées lors d’une recherche infructueuse. Montrer que la probabilité que X soit supérieur ou égal à i compris entre 1 et m est majorée par α^{i−1}.

Montrer que l’insertion d’un élément choisi au hasard hors de la table demande un temps en moyenne au plus 1/(1 − α).

Question 2,2,3

On suppose qu’on recherche chaque clef de la table avec égale probabilité. Montrer que la recherche fructueuse visite un nombre de cases du tableau moyen au plus \frac{1}{α} ln \frac{1}{1−α}. On pourra de nouveau considérer les clés dans l’ordre où elles ont été insérées dans la table.

Question 3

Hervé, dont le maigre salaire passe dans le paiement des traites de sa chambre de bonne, en est réduit à consommer des hamburgers. Il a le choix entre deux officines voisines de son immeuble : deux fois sur trois il va chez Mac Mickey’s et le reste du temps il fréquente le Hamburger Prinz. Son estomac fragile l’expose à une gastrite avec une probabilité de 0,10 chez Mac Mickey’s et une probabilité de 0,15 au Hamburger Prinz. Sachant qu’il a une gastrite, calculer la probabilité d’avoir pris son dernier hamburger chez Mac Mickey’s.

Question 4

Quand il vente sur le Pont des Arts le nombre de chapeaux que le vent emporte suit une loi de Poisson. Parmi les victimes éventuelles de ce petit jeu du vent une proportion p se rend sur la rive droite. On note X le nombre de chapeaux perdus par ces piétons-ci. Établir la loi de probabilité de X, préciser la variance et l’espérance. (précisions : les événements “perdre son chapeau” et “aller vers la rive droite” sont indépendants ; on notera m le paramètre de la loi de X ; chaque piéton qui est sur le pont se rend sur la rive droite avec probabilité p et indépendamment des autres piétons.)