Percolation dirigée de dernier passage

Définition du modèle

On se place dans le plan discrétisé et plus précisément dans le premier cadrant Z ∗ + × Z ∗ +. On attribue à chaque point (i, j) de cet espace un poids aléatoire noté X (j) i et on considère l’ensemble Π(N, k) des chemins qui partent du point (1, 1) pour atteindre le point (N, K) en ne permettant que les pas vers la droite et vers le haut. Un chemin π appartenant à Π(N, k) est donc un ensemble de points π = ½ (i1, j1) = (1, 1), . . . ,(iN+k−1, jN+k−1) = (N, k) ¾ , tel que (il+1, jl+1) − (il , jl) vaut (1, 0) ou (0, 1) pour tout l entre 1 et N + k − 2.

Le terme percolation dirigée vient du fait qu’on oblige les chemins d’emprunter des directions sans d’autres, (voir Figure 3.2). Dans ce cadre là, on dénit le temps de dernier passage par la variable aléatoire réelle G(N, k) = max π∈Π(N,k) ½ X (i,j)∈π X (j) i ¾ . (2.1) Glynn et Whitt [GW91] utilisent cette version du modèle dans leurs travaux sur les les d’attente en série. En tenant compte du Théorème 1.12, il convient de bénécier d’une autre interprétation de ces chemins dirigés, et par suite d’une autre façon d’exprimer le temps du dernier de passage. Plus précisément, un chemin π ∈ Π(N, k) est caractérisé par un (k − 1)-uplet de (Z ∗ +) k−1 qui représente les abscisses des k − 1 sauts vers le haut de ce chemin. On a donc une bijection entre Π(N, k) et l’ensemble U(N, k) ∩ Z k+1 + où U(N, k) := © u = (u0, u1, . . . , uk) ∈ R k+1 + ; 0 = u0 ≤ u1 ≤ . . . ≤ uk = N ª . 

Percolation dirigée et applications

Comme on l’a mentionné auparavant, le modèle de percolation dirigée en dimension 2 suscite un intérêt particulier du fait de son lien avec la physique des particules et la théorie des les d’attente en série. On renvoie le lecteur vers le résumé de Seppäläinen [Sep09] et celui de König [Kön05] pour plus de détails et de références bibliographiques. Files d’attente en série : la variable G est apparue pour la première fois sous la forme (2.5) dans [TW74] dans l’étude des les d’attente en série et plus tard dans [GW91].

On considère la situation suivante : N clients font la queue avant de passer devant k guichets numérotés de 1 à k. Au temps t = 0, tout le monde attend devant le premier guichet et le premier client passe au guichet 1. Une fois servi, ce même client passe au guichet 2 et laisse sa place au deuxième client au guichet 1 et ainsi de suite. Dès que le client i quitte le guichet j, il se dirige vers le guichet j + 1. Si ce guichet est vacant, il l’occupe, sinon il fait la queue derrière le client i − 1. On note Y (j) i le temps de service du client i au guichet j.

Après un certain temps, la scène est constituée de k guichets avec une le d’attente plus ou moins grande devant chacun d’eux. On suppose que les clients sont tous là depuis le début. Cependant, considérer des arrivées aléatoires au guichet 1 revient à rajouter un guichet avec un temps de service de même loi que le temps d’arrivée des clients. En notant T(n, k) le temps passé avant que le client n ne quitte le guichet k, on remarque facilement que T(n, k) = T(n − 1, k) ∨ T(n, k − 1) + Y (k) n , avec les conditions aux bords T(n, 0) = T(0, k) = 0.

La variable T vérie alors la même formule de récurrence que G. Par suite, lorsque les (X (j) i )∞ i,j=1 et les (Y (j) i )∞ i,j=1 sont i.i.d. et X (1) 1 L= Y (1) 1 , alors T(N, k) et G(N, k) sont de même loi. On comprend ainsi l’appellation : temps de dernier passage. Glynn et Whitt [GW91] se servent de la propriété de superadditivité pour démontrer que lim N→∞ T(bγNc, N) N = g(γ), où g(γ) est une fonction déterministe. Comme la variable Y (j) i représente un temps de service, il convient de choisir une loi exponentielle pour un temps continu et une loi géométrique pour un temps discret.

Ce sont d’ailleurs les deux cas où l’on connaît le plus de résultats. Dans un cadre plus général, on peut supposer que chaque guichet fournit un service diérent des autres. Ainsi, le temps de service d’un client i va dépendre du guichet où il se trouve. Par suite, les Y (j) i sont toujours considérées indépendantes mais de loi exponentielle de paramètre λj qui varie avec les guichets. Là aussi, on connait plein de résultats sur la variable T(N, k), (voir [Joh08]).