Année 2023-24 - Equipe PEIPS (CMAP)¶
Groupe de Travail Discrete Random Objects: Limits and EStimates¶
Résumé de la séance 8 - La formule magique de Keane ¶
Orateur : Cyril Marzouk (résumé par Emmanuel Kammerer)¶
Sommaire¶
Marche aléatoire renforcée sur le digone (alias les urnes de Pólya)¶
On considère deux sommets reliés par deux arêtes $a$ et $b$ (non orientées). Ces arêtes sont équipées au départ de poids $a_0,b_0>0$. On effectue une marche aléatoire renforcée sur ce graphe : à chaque étape, on choisit d'emprunter une arête avec probabilité proportionnelle à son poids, et on incrémente de $1$ le poids de l'arête traversée. On note $a_n,b_n$ les poids des arêtes à l'étape $n$.
Solution
- $\frac{a_n}{a_n+b_n}$ est une martingale positive bornée donc converge p.s. et dans $\mathrm{L}^p$ pour tout $p\ge 1$.
- Le cas où $a_0=b_0=1$ correspond aux urnes de Pólya. Par récurrence, on voit que $a_n$ est uniforme sur $\{1, \ldots, n+1\}$.
- Dans le cas général, on calcule par récurrence $$ \mathbb{P}(a_n = a_0 +k) = \frac{ \binom{k+a_0-1}{a_0-1} \binom{n-k+b_0-1}{b_0-1}}{\binom{n+a_0+b_0-1}{a_0+b_0-1}}, $$ où $\binom{y-1}{x-1} = \Gamma(y)/(\Gamma(x)\Gamma(y-x+1))$. Puis par Stirling, on obtient un théorème local limite vers une loi Bêta de paramètres $a_0,b_0$.
Marche aléatoire renforcée sur le triangle¶
Soit un triangle $ABC$. On note respectivement $a,b,c$ les côtés opposés aux sommets $A,B,C$. Comme précédemment, on attribue des poids $a_0,b_0,c_0$ aux arêtes $a,b,c$, supposés égaux à $1$ pour simplifier. On effectue ensuite une marche renforcée sur les sommets du triangle comme dans le cas du digone. On note $k,\ell,m$ les nombres de traversées des arêtes $a,b,c$. À l'instant $n$, on a $k+\ell+m=n$.
Idées de Keane [Kea90]
- On note $$ M_n= \frac{k-\ell}{k+\ell} $$ à la $n$-ième visite de $C$. Alors $M_n$ est une martingale. Pour montrer cela, on distingue les chemins possibles entre deux visites de $C$: ils peuvent être de la forme $CB(AB)^iC$, $CB(AB)^iAC$, $CA(AB)^iC$, ou $CA(BA)^iBC$ pour un entier $i\ge0$. Dans chacun des cas, $\Delta M_n$ ne dépend pas de $i$ et vaut respectivement $$ \frac{k-\ell+2}{k+\ell+2} - \frac{k-\ell}{k+\ell}, \ \frac{k-\ell}{k+\ell+2} - \frac{k-\ell}{k+\ell}, \ \frac{k-\ell-2}{k+\ell+2} - \frac{k-\ell}{k+\ell}, \ \frac{k-\ell}{k+\ell+2} - \frac{k-\ell}{k+\ell}. $$ On calcule ensuite les probabilités d'observer chacun de ces chemins en faisant attention à bien incrémenter les poids. Ainsi, $M_n$ est une martingale à valeurs dans $[-1,1]$ donc elle converge p.s. Donc $(k-\ell)/(k+\ell)$ converge p.s. car il ne varie pas entre deux passages par $C$. Ainsi, $k/\ell$ converge p.s. dans $[0,\infty]$. Par symétrie, on conclut qu'il existe une variable aléatoire $(\alpha, \beta, \gamma)$ telle que $$ \left( \frac{k}{n}, \frac{\ell}{n}, \frac{m}{n}\right) \mathop{\longrightarrow}\limits_{n\to \infty}^{\mathrm{p.s.}} (\alpha, \beta, \gamma). $$
- Pour identifier la loi de la limite, il faut examiner de plus près les chemins qui partent de $A$ et traversent les arêtes $a,b,c$ respectivement $k,\ell,m$ fois. De tels chemins sont appelés des chemins $(k,\ell,m)$. L'orateur nie tout lien avec une certaine compagnie aérienne mais on peut émettre des doutes vu le nom de la revue. Remarquons que si $k\equiv \ell \equiv m \ \mathrm{mod} (2)$, alors au temps $n$ on est en $A$. Si $k\equiv \ell \not\equiv m \ \mathrm{mod} (2)$, alors au temps $n$ on est en $B$. $k\equiv m \not\equiv \ell \ \mathrm{mod} (2)$, alors au temps $n$ on est en $C$. Le dernier cas $m\equiv \ell \not \equiv k \ \mathrm{mod}(2)$ est impossible. "It is now easily seen that" la probabilité d'observer un chemin $(k,\ell,m)$ fixé arrivant en $A$ au temps $n$ est $$ \frac{k! \ell!m!}{2\times 4 \times \cdots \times(\ell+m) \times 3 \times 5 \times \cdots \times(k+m+1) \times3 \times 5 \times \cdots \times (k+\ell+1)}. $$ Par ailleurs, en notant $$ M= \begin{pmatrix} 0 & z & y \\ z& 0 & x \\ y& x & 0 \end{pmatrix}, $$ le nombre de chemins $(k,\ell,m)$ terminant en $A$ correspond au coeffient devant $x^ky^\ell z^m$ de $(M^n)_{1,1}$. Pour le calculer, une idée est de considérer $\sum_{n\ge 0} M^n = (\mathrm{Id}-M)^{-1}$, de calculer l'inverse à l'aide du déterminant et de la comatrice puis de redévelopper. Enfin, après quelques sommes de Riemann, on obtient que la densité de $(\alpha, \beta, \gamma)$ est $$ \frac{\sqrt{\alpha \beta +\alpha \gamma +\beta \gamma}}{(1-\alpha)(1-\beta)^{3/2} (1-\gamma)^{3/2}}. $$
Références¶
[Dia89] Diaconis, P. (1989), Problems 227 and 228, Statistica Neerlandica 43, 133-139.
[Kea90] Keane, M. S. (1990), Solution to problem 288, Statistica Neerlandica 44, 95–100.