4.4 Les configurations stables
Avant de conclure ce chapitre sur les réseaux à préférences acycliques, je propose de répondre, au moins partiellement et pour les graphes d’acceptabilité Erdős-Rényi, à la deuxième question majeure des systèmes à préférences acycliques : quelles sont les propriétés de la configuration stable ?
Pour , il est possible d’étudier la distribution des partenaires grâce à une approche (simplifiée) de type champ moyen. Pour les préférences globales, on peut prouver l’existence d’une limite fluide avec solution explicite, qui montre en particulier que la distribution de la valeur du partenaire d’un pair est centrée autour de la valeur de ce pair, avec une décroissance exponentielle : c’est l’effet de stratification [37]. Pour des préférences acycliques aléatoires ou géométriques, la solution de la limite fluide décroît en loi de puissance. Bien que je ne sois pas en mesure de prouver l’approche champ moyen, je propose de valider cette approche en la comparant avec la solution exacte (pour les préférences globales) ou à l’aide de simulations.
Enfin, je propose d’étendre les résultats à . Les équations fluides ne semblent alors plus admettre de solution explicite, mais on observe le même comportement asymptotique que pour (exponentiel pour les préférences globales, en loi de puissance sinon). Une conséquence inattendue est que pour les préférences géométriques, la configuration stable est un petit-monde si les quotas sont suffisants.
La plupart des résultats présentés ici sont rassemblés dans l’article The Stable Configuration in Acyclic Preference-Based Systems [57], dont une version étendue est disponible sous forme de rapport de recherche [58].
4.4.1 Notation spécifique
Comme je propose d’étudier en détail la configuration stable dans cette section, quelques notations supplémentaires sont nécessaires, pour décrire en particulier la distribution des partenaires. Si et sont acceptables, désigne le rang acceptable de selon ( étant le meilleur rang). est le classement acceptable de . Si a plus de voisins (acceptables), est le ième meilleur voisin acceptable de . De même, pour tout , désigne le rang de dans le graphe complet, sans tenir compte de la notion d’acceptabilité8. est le classement complet de . Pour , est le ième meilleur voisin, acceptable ou non, de .
Dans tout ce qui suit, désigne la distribution du, ou des, partenaires stables. Afin d’alléger l’écriture, je propose d’utiliser une notation lâche, où le sens de est spécifié à l’aide d’indices et d’exposants à chaque fois que cela est nécessaire. Ainsi, indique la probabilité que ait son pair de rang complet comme partenaire ; est la probabilité que et soient partenaires s’il y a pairs avec une acceptabilité Erdős-Rényi de degré moyen ; si , est la probabilité que le ème meilleur partenaire stable de ait un rang acceptable …
La distribution cumulative complémentaire (Complementary Cumulative Distribution Function, ou CCDF) de est notée , et les versions normalisées de et sont respectivement notées et .
4.4.2 Équations acycliques
Pour le cas du couplage simple (), je propose une méthode générique pour décrire le rang complet de , s’il existe, dans la configuration stable . La généralisation au -couplage sera faite en Section 4.4.5.
Équation exacte
Soit la probabilité que , c’est-à-dire que le partenaire de , s’il existe, ait le rang complet . La CCDF de est définie par , i.e. la probabilité que ait un partenaire de rang complet plus grand ou égal à () ou n’ait pas de partenaire du tout (notation courte pour la disjonction des deux événements : ). En s’inspirant de l’approche utilisée dans [37], je propose une équation exacte décrivant avant de donner une version simplifiée issue d’une approche de type champ moyen.
Pour exprimer , on peut observer que pour que soit stable avec son pair de rang complet , noté , il faut (et il suffit de) vérifier les trois conditions suivantes :
- doit être une arête acceptable, ce qui se produit avec probabilité si est un graphe Erdős-Rényi ;
- ne doit pas avoir de meilleur partenaire stable que () ;
- ne doit pas avoir de meilleur partenaire stable que ().
Cela mène à l’équation exacte suivante :
Équation approchée
La principale difficulté de l’Équation (4.1) est la probabilité conditionnelle, délicate à manier à cause des corrélations qui peuvent exister entre et . La solution est de tenir ces corrélations pour négligeables :
Approximation 4.1.
Les événements « n’est pas avec meilleur que » et « n’est pas avec meilleur que » sont indépendants.
Cette approximation, que j’appelle parfois un peu abusivement « hypothèse de champ moyen », est raisonnable pour assez petit9. L’Équation (4.1) peut alors se simplifier en
Pour aller plus loin, il faut prendre en compte le type de préférences.
4.4.3 Préférences globales
Comme les préférences globales sont caractérisées par un ordre total sur les pairs, on peut se passer de la matrice de valeurs en étiquetant les pairs de à , étant le meilleur. On considère ainsi directement la probabilité que et soient partenaires. En remarquant que le rang complet de pour est si et si (un pair ne se classe pas lui-même), on obtient la relation entre et :
En posant , on obtient la déclinaison de l’Équation (4.2) pour les préférences globales :
Cette équation10, qui se résout numériquement par une double itération, donne une très bonne approximation de la distribution empirique [37].
Normalisation
Une limite fluide explicite vers laquelle les distributions discrètes convergent est un atout certain pour la description de la configuration stable. Cela permet en effet de donner une description complète, immédiate et globale de la distribution pour tous et , ce qui n’est pas le cas de l’Équation (4.4).
Afin d’obtenir cette limite, il faut pouvoir comparer des distributions pour des valeurs arbitraires de . Il est donc nécessaire de normaliser . Une manière assez simple de le faire consiste à représenter chaque pair par un rang normalisé , avec . Plus précisément, on associe à chaque le réel , et réciproquement à chaque réel positif l’entier . La version normalisée de , notée , est alors définie par
est une fonction en escalier (à deux variables), qui prend les valeurs . Le facteur permet d’exprimer simplement comme une intégrale de :
La distribution cumulative complémentaire normalisée est définie par
et la relation entre et est
Convergence des distributions normalisées
Si le degré moyen reste constant, j’ai montré l’existence d’une limite continue des distributions . La première étape est de régler le problème d’une discontinuité intrinsèque le long de la diagonale principale (), due au fait que . C’est un problème mineur car cette discontinuité est juste là pour rappeler la non-réflexivité du couplage. Il se résout en introduisant une fonction plus « continue », obtenue en prolongeant sur la diagonale principale à l’aide de l’Équation (4.4) :
La limite fluide, à degré constant, des fonctions est alors donnée par le théorème qui suit :
Théorème 4.9.
Soit une constante. Si , avec , les fonctions convergent uniformément vers
Ce résultat montre qu’asymptotiquement, la distribution des partenaires ne dépend que du degré moyen de (supposé Erdős-Rényi). Cela permet de décrire quantitativement l’effet de stratification [37] : à fixé, la distribution du partenaire stable de décroît exponentiellement en , avec intensité ( pour assez grand). Autrement dit, un pair de rang normalisé tend à avoir pour partenaire un pair de même rang, à plus ou moins .
Démonstration.
La preuve du Théorème 4.9 comporte quatre étapes [58] :
- montrer que les fonctions sont uniformément Cauchy sur ;
- utiliser la convergence de Cauchy pour montrer que et admettent des limites et ;
- donner une EDP vérifiée par ;
- résoudre l’EDP11, et déduire de la solution.
□
L’existence de cette limite fluide avait été proposée comme conjecture dès [37], et prouvée pour le cas , mais ce n’est que plus tard que la preuve et l’expression complètes ont été trouvées [58].
Le Théorème 4.9 permet d’obtenir trois corollaires immédiats qui complètent la compréhension de la configuration stable.
Corollaire 4.1.
En considérant , la probabilité qu’un pair de rang normalisé soit célibataire dans la configuration stable est .
Corollaire 4.2.
Pour (cas discret), une bonne approximation de est
Corollaire 4.3.
Soit une suite de distributions normalisées à degré croissant non borné (). On a
Ce dernier corollaire généralise un théorème proposé dans [37], qui montrait l’existence d’une limite faible de Dirac dans le cas d’une suite de distributions à constant. Il signifie que dès que le degré tend vers l’infini (par exemple en ), alors asymptotiquement, un pair a pour partenaire un pair de même rang normalisé (pas de déviation), et la probabilité de célibat devient nulle.
Validation
Pour valider les résultats précédents, il faut comparer des résultats de simulations à l’Équation (4.4) (récurrence sous l’approximation d’indépendance), puis à l’Équation (4.11). C’est ce qui a été fait [37, 58].
Comme indiqué précédemment, on observe pour l’Équation (4.4) une très bonne précision, de l’ordre de .
Pour la limite fluide, mis à part le prolongement continu sur la diagonale principale, la précision est également très bonne, sauf pour des valeurs de faibles et de élevées. Ces observations sont consistantes avec la preuve complète du Théorème 4.9 [58], qui montre une convergence en . Elles seraient même plutôt en faveur d’une convergence en , qui est d’après moi la vraie borne, même si cela reste à prouver12.
Résolution exacte
Dans la situation que je viens de proposer (, préférences globales, acceptabilité ), il est en fait inutile de recourir à l’approximation d’indépendance, car il existe une récurrence qui permet d’obtenir la distribution exacte [58].
J’ai pu obtenir cette récurrence en conditionnant le fait que et soient partenaires selon le rang du partenaire du pair (plus petit que , entre et , plus grand que ou pas de partenaire).
Tout comme pour la formule approchée, la formule exacte admet une limite fluide, qui obéit à une certaine EDP. Bien que les deux EDP (exacte et approchée) soient extrêmement différentes13, elles donnent la même solution, à savoir Équation (4.10).
Le fait que dans ce cas particulier, la récurrence donnée par l’approximation d’indépendance ait exactement la même limite fluide que la récurrence exacte est un argument de poids (à défaut d’être rigoureux) pour justifier l’utilisation de cette approximation dans les autres cas. Car un inconvénient majeur de la récurrence exacte est que la « ruse » utilisée ne s’applique pas pour les autres préférences, ni pour . Si jolie soit cette récurrence, l’hypothèse d’indépendance reste donc incontournable si l’on veut généraliser les résultats.
4.4.4 Préférences acycliques et géométriques
Je propose maintenant de m’intéresser aux préférences acycliques (aléatoires) et géométriques. Pour ces préférences, on peut remarquer que les pairs sont non différenciés. Sur l’ensemble des réalisations possibles, on peut donc considérer que tous les pairs suivent la même distribution de partenaire : est indépendant de , et peut donc être noté .
Comme pour les préférences globales, il s’agit de trouver la distribution du rang complet en simplifiant l’Équation (4.1) avant de la résoudre. Je donne aussi rapidement la distribution des distances et des éléments de résolution de la distribution du rang relatif.
Distribution du rang complet
Pour les préférences géométriques ou aléatoires, l’Approximation 4.1 n’est pas suffisante, c’est pourquoi je propose une approximation supplémentaire :
Approximation 4.2.
Le rang complet est symétrique : .
Je suppose donc que n’est pas une si mauvaise approximation de pour les préférences considérées. Cela donne une équation très simple pour :
peut donc être obtenue par une récurrence simple :
Et est directement donnée par .
Limite fluide.
Comme pour les préférences globales, peut être normalisée. Pour , on pose . Le facteur de normalisation est maintenant car c’est la valeur maximale de ( était celle de et en Section 4.4.3). s’exprime comme une intégrale de :
est alors naturellement définie par :
Théorème 4.10.
Soit une constante. Si , avec , les fonctions convergent uniformément vers
En particulier, la probabilité qu’un pair soit célibataire dans la configuration stable est asymptotiquement , et une bonne approximation de est
Démonstration.
La preuve est la même que pour le Théorème 4.9, en plus facile. Il faut d’abord montrer que les sont uniformément Cauchy (ce qui est plus facile ici car il n’y a qu’une seule variable et pas besoin d’introduire un prolongement sur la diagonale principale). On a alors la convergence uniforme vers une fonction continue . On déduit alors de l’Équation (4.14) une équation différentielle ordinaire vérifiée par :
avec la condition initiale . La solution de Équation (4.19) est Équation (4.17), ce qui achève la preuve.
□
Validation.
Compte tenu des approximations faites, il est nécessaire de vérifier sur quelques exemples la précision de l’Équation (4.18). J’ai donc testé sa validité pour quelques valeurs de et de [58].
Pour , on ne peut pas vraiment dire que l’hypothèse d’indépendance soit vérifiée. Les simulations montrent que les distributions sont affectées par le type particulier de préférences, et la limite fluide n’est pas très précise, en particulier aux limites ( proche de ou de ). On peut entre autres remarquer que la probabilité de célibat donnée par l’Équation (4.18) est clairement sur-estimée si est pair (puisqu’elle est alors nulle en réalité), mais exacte pour impair. La limite fluide réussit quand même à donner le comportement en commun à toutes les préférences considérées. De ce point de vue, elle est meilleure que l’équation récursive (4.14) (dont elle dérive pourtant), qui donne pour .
Au fur et à mesure que diminue, les courbes empiriques et la limite donnée par le Théorème 4.10 se rejoignent très vite. Dès , elles sont presque indistinguables, ce qui valide l’utilisation de la limite fluide comme approximation de la distribution du rang complet.
Distribution des distances
Il peut être intéressant de considérer d’autres distributions que celle du rang complet. Par exemple, pour des préférences géométriques, la distribution des distances entre partenaires stables peut être intéressante si les performances d’un couplage sont liées aux distances. Or, cette distribution peut être déduite de celle du rang complet :
Théorème 4.11.
Soit la probabilité qu’un pair n’ait pas de partenaire stable à distance inférieure à dans le tore unitaire de dimension . Soit le volume d’une boule de rayon dans ce tore. Sous la limite fluide, on a
Démonstration.
Une boule de rayon , centrée sur un pair quelconque, contient à peu près pairs puisqu’elle occupe une proportion du tore (qui est supposé unitaire). Le pair le plus éloigné à l’intérieur de cette boule devrait donc avoir un rang complet d’à peu près pour le pair central, tout en étant à une distance d’environ . On obtient ainsi la relation , et il ne reste plus qu’à utiliser l’Équation (4.18) pour conclure.
□
La fonction dépend de la dimension et de la norme utilisée. Pour la norme infinie, on a tout simplement . L’écriture des autres normes peut être un peu plus compliquée à cause de possibles effets de recouvrement sur les bords. Remarquons que si j’avais choisi (avec densité homogène) au lieu du tore unitaire, aurait juste été la taille d’une boule de rayon , sans effets de bord.
Comme à l’accoutumée, la précision de l’Équation (4.20) a été vérifiée empiriquement, et le résultat est qu’elle a quasiment la même zone de validité que l’Équation (4.18) [58].
Distribution du rang relatif
Pour les préférences acycliques aléatoires et géométriques, je me suis également intéressé à la distribution du rang relatif, donnée par la fonction et sa distribution cumulée complémentaire .
J’ai donc essayé d’adapter la méthode utilisée pour le rang complet. Les conditions à remplir pour que le partenaire stable de soit son ième voisin acceptable sont les suivantes :
- doit avoir au moins voisins (si le ième voisin existe, il est acceptable par définition),
- ne doit pas être avec un pair meilleur que ,
- ne doit pas être avec un pair meilleur que .
En adaptant les approximations d’indépendance et de symétrie au rang relatif, on obtient alors la formule de récurrence suivante [58] :
où est la fonction bêta incomplète normalisée.
Hélas, l’Équation (4.21) est beaucoup moins précise que ne l’est l’Équation (4.18) pour le rang complet, en particulier pour [58]. La raison en est que les corrélations sont beaucoup plus présentes lorsque c’est le rang acceptable que l’on considère (en particulier si l’on considère le voisinage proche).
À titre d’exercice, je me suis donc demandé s’il était possible d’affiner l’estimation du rang relatif, et j’ai partiellement réussi : pour , il est possible d’avoir une meilleure estimation en limite fluide, qui s’obtient en conditionnant sur le rang complet normalisé du premier partenaire acceptable [58]. On obtient alors
où est l’exponentielle intégrale.
Cette valeur est très bonne dans à peu près tous les cas pour les préférences acycliques aléatoires. Pour les préférences géométriques, il est en revanche nécessaire d’être dans de bonnes conditions, c’est-à-dire petit et grand [58].
4.4.5 Généralisation au -couplage
Je propose maintenant d’étendre les résultats précédents au problème du -couplage. est toujours supposé constant sur les pairs pour plus de simplicité. Je ne propose ici que des résultats sur le rang complet, bien qu’il soit a priori possible de réutiliser les techniques vues précédemment pour le rang relatif ou les distances.
Équations sous l’hypothèse d’indépendance
Un pair peut maintenant avoir jusqu’à partenaires. On note donc, pour , la distribution du rang complet du ième meilleur partenaire stable, et la CCDF correspondante. Tout comme pour le cas , il est possible de donner les conditions nécessaires et suffisantes pour que soit le ième meilleur partenaire stable de :
- le couple doit être acceptable,
- le ième meilleur partenaire de (si ) doit être strictement meilleur que , tandis que le ième (s’il existe) ne doit pas l’être,
- le ième partenaire de , s’il existe, ne doit pas être meilleur que .
En étendant l’hypothèse d’indépendance Approximation 4.1, on obtient ainsi une formule générique pour le -couplage :
Pour être utilisable, cette formule doit être adaptée au type de préférences considéré.
Pour les préférences globales, si désigne la probabilité que le ième partenaire stable de soit 14, on obtient le système récursif suivant, qui se résout par une triple itération sur , et [37] :
De même, pour les préférences acycliques aléatoires et géométriques, on obtient le système suivant à partir de l’Approximation 4.2 (symétrie du rang complet) [58] :
En utilisant et , le système Équation (4.25) se résout facilement par une double itération sur et .
Les simulations montrent que les deux systèmes coïncident très bien avec les distributions empiriques tant que et vérifient les conditions usuelles [58]. Le comportement est qualitativement très similaire à celui du couplage simple : décroissance exponentielle pour les préférences globales (mais à cause de la multiplicité des partenaires, des décalages apparaissent entre les pics de densité des et la valeur du pair d’origine), distribution en aile lourde pour les préférences géométriques et acycliques aléatoires.
Pour , des limites fluides existent aussi. Hélas, contrairement au couplage simple, je n’ai pas réussi à trouver de solutions explicites pour les décrire (et le temps passant, je doute de plus en plus que de telles solutions existent). Il est néanmoins possible de donner les EDP vérifiées par ces limites.
Pour les préférences globales, les limites fluides vérifient
avec les conditions initiales .
De même, en préférences acycliques et géométriques, les limites vérifient
avec les conditions initiales .
Même si ces équations ne peuvent pas être résolues complètement, la limite fluide a quand même plusieurs intérêts.
Tout d’abord, l’existence même d’une limite permet de la calculer numériquement avec précision et d’utiliser le résultat pour de multiples valeurs de et de . Prenons par exemple le cas des préférences globales (le même raisonnement pouvant être fait pour les préférences acycliques et géométriques). On suppose fixé. Soit le degré moyen maximal des distributions que l’on veut évaluer, et une taille fixée d’échantillonnage de la limite fluide (plus est grand, plus l’évaluation sera précise). On peut alors poser et calculer les (une fois pour toutes) en utilisant Équation (4.24). Pour un degré , on pose ( n’est pas nécessairement entier). En s’inspirant de la normalisation Équation (4.5), on obtient l’approximation suivante pour :
On peut alors en retour utiliser cette estimation de la limite fluide pour des distributions discrètes. Ainsi, pour tout entier et pour tout , alors on a, pour (ce qui revient à si )
Un autre intérêt des limites fluides est que les EDP qu’elles vérifient nous renseignent sur leur comportement. On peut par exemple s’en servir pour montrer que (et l’équivalent en préférences globales) et comprendre ainsi pourquoi le comportement en -couplage reste similaire à celui du couplage simple.
4.4.6 Quelques applications
Ayant mis beaucoup d’efforts dans la simple étude des distributions, je dois reconnaître n’avoir pas encore consacré énormément de temps aux propriétés évoluées des configurations stables, c’est-à-dire à celles susceptibles d’aider à comprendre les systèmes existants et à en développer de nouveaux. En voici néanmoins deux : la stratification des préférences globales et la « petit-mondisation » des préférences géométriques.
Stratification
Comme nous venons de le voir, en préférences globales, les partenaires stables d’un pair donné ont, en moyenne, le même rang que . C’est la stratification, qui garantit une certaine équité dans la configuration stable [37] : en terme de rang, ce que donne un pair devrait être à peu près égal à ce qu’il reçoit. Il faut aussi se rappeler que les ont une décroissance exponentielle avec déviation en , étant le degré moyen du graphe d’acceptabilité. On s’aperçoit alors qu’il faut résoudre le compromis suivant :
- si est trop petit la déviation est élevée. En particulier, si les entrées de la matrice des valeurs (par exemple les bandes passantes d’un système à la BitTorrent) suivent une distribution non-uniforme, il peut y avoir une très grande différence entre l’espérance du gain et ce que l’on donne. Ce problème a été mis en évidence dans [37] pour expliquer des failles potentielles de la technique de Tit-for-Tat employée par BitTorrent ;
- un grand permet à l’opposé de renforcer l’équité. Mais en pratique, augmenter la taille du graphe d’acceptabilité a un coût pour les pairs : temps de convergence, place mémoire, maintenance du graphe… Un grand raccourcit aussi la déviation (jusqu’au Dirac dans la limite fluide), et donc augmente le diamètre de la configuration stable, ce qui peut être problématique si l’on veut propager de l’information à travers les arêtes stables.
Pour le quota , qui représente le degré maximal dans la configuration stable, un compromis similaire existe : un grand peut améliorer l’équité et diminuer le diamètre, mais va être coûteux en ressources.
Cela suggère que pour la plupart des systèmes à préférences globales (i.e. basés sur le partage de la bande passante, de la capacité de stockage ou de calcul, de l’uptime…), il devrait exister un couple (ou plus généralement un couplage entre un graphe d’acceptabilité et un vecteur de quotas) optimal pour la configuration stable, dont la valeur exacte dépendrait de l’importance donnée à des paramètres comme le diamètre, l’équité, le temps de convergence ou le coût de maintenance.
Petit-mondisation
Un petit monde est un graphe creux (degré moyen en voire en ) avec un plus court chemin moyen (average shortest path length ou ASPL) en et un coefficient de clustering élevé (il existe beaucoup plus de cycles courts que pour un graphe aléatoire de même taille). Par exemple, Kleinberg a montré il y a quelques années qu’une grille de dimension pouvait être transformée en petit-monde à condition d’ajouter des arêtes longues suivant une distribution en [49].
Regardons maintenant ce qui se passe pour une configuration stable, avec un en pour que la configuration soit « creuse ». S’il s’agit de préférences globales, le clustering est bien là comme conséquence de la stratification, mais le diamètre a tendance à croître linéairement [36]. De même, pour les préférences acycliques aléatoires, le petit diamètre est vérifié mais il n’y a pas de grand clustering (la configuration stable se comporte comme un -graphe aléatoire incomplet). Par contre, pour les préférences géométriques, la distribution en aile lourde permet d’avoir les deux propriétés : d’un côté, la plupart des partenaires stables ont un petit rang complet ; ils sont donc « géographiquement » proches ce qui donne le clustering ; de l’autre, il existe des liens longs qui rendent le diamètre petit. Les préférences géométriques sont donc propices à la génération de configurations en petit-monde, et c’est effectivement ce qui se produit [36]. Cela ouvre un certain nombre de perspectives sur l’utilisation de la configuration stable, à commencer par un générateur de petits-mondes facile à utiliser.
Ce qui est étonnant dans cette petit-mondisation en préférences géométriques, c’est qu’elle est uniquement créée par la manière dont les pairs se classent les uns les autres : les distances réelles sont utilisées pour construire ces classements, mais les valeurs en elles-mêmes ne jouent aucun rôle direct dans le système à préférences en général et dans sa configuration stable en particulier. Ceci amène à penser que des caractéristiques topologiques d’un système peuvent donc être contenues dans un ensemble de préférences.
Comme exemple de caractéristiques, je me suis amusé à calculer numériquement les paramètres de petit-monde des préférences sur les tores pour quelques dimensions, le résultat étant que le diamètre et le clustering tendent à baisser quand la dimension augmente [58]. J’ai ensuite regardé ce que donnaient les latences Meridian, et les paramètres obtenus se sont révélés proches de ceux du tore de dimension . J’aime particulièrement ce résultat inattendu, car il semble suggérer qu’il existe une dimension d’Internet au sens des préférences, qui vaut à peu près . Je peux ainsi rajouter ma pierre au mur des efforts fournis un peu partout pour estimer une dimension d’Internet (voir par exemple [11]).
- 8Je suppose l’existence d’un prolongement naturel de la matrice des valeurs aux paires non acceptables. Ce prolongement est immédiat pour les préférences globales (la valeur intrinsèque) et géométriques (la distance). Pour les préférences acycliques aléatoires, il s’obtient en attribuant des valeurs aléatoires « fantômes » aux arêtes non-acceptables.
- 9Quelques exemples simples semblent indiquer une erreur en , confirmée par les simulations [37].
- 10Pour la petite histoire, l’Équation (4.4) a été proposée par Julien Reynier sur une idée originale de Fabien de Montgolfier. Chronologiquement elle est à l’origine de l’Équation (4.2) (équation générale), et non l’inverse.
- 11Pour le lecteur avide d’équations « exotiques », il s’agit de résoudre , avec la condition initiale . Bien que d’apparence innocente, la résolution de cette équation non-locale m’a donné pas mal de fil à retordre, alors même que je connaissais par ailleurs sa solution. Je remercie en passant François Baccelli qui m’a aiguillé sur la piste de la dé-non-localisation.
- 12Le facteur vient de l’utilisation du lemme de Grönwall [12], qui amplifie une erreur de quantification incompressible en . Mais en pratique, l’Équation (4.4), qui sert de base à la construction des distributions, est auto-stabilisante (une erreur dans un sens à un moment donné est compensée dans l’autre sens à l’itération suivante), ce que le lemme de Grönwall ne permet pas de prendre en compte.
- 13L’EDP exacte est relativement classique, et se résout par la méthode des caractéristiques, alors qu’il a fallu résoudre l’EDP approchée, décrite en note plus haut, de manière moins conventionnelle.
- 14Je me permets de souligner au passage que n’est plus symétrique, alors que c’était le cas pour .