\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection, NoEqCountersInSection,published]{cedram}
\setcounter{tocdepth}{2}
%\XUPScorrections

\graphicspath{{xups16-03_figures}}

\let\subsection\Subsection

\theoremstyle{plain}
\newtheorem{theorem}{Théorème}
\newtheorem{lemma}{Lemme}

\theoremstyle{definition}
\newtheorem{definit}{Définition}
\newtheorem{remarq}{Remarque}
\newtheorem{exercice}{Exercice}

\newcommand{\lcr}{[\![}
\newcommand{\rcr}{]\!]}

\hyphenation{dimen-sion dimen-sions indi-ca-tion indi-ca-tions métho-de faci-le-ment}

\datepublished{2024-08-06}
\begin{document}
\frontmatter
\title{La marche auto-évitante}
\author[\initial{V.} \lastname{Beffara}]{\firstname{Vincent} \lastname{Beffara}}
\address{Université Grenoble Alpes, CNRS, Institut Fourier}
\email{vincent.beffara@ujf-grenoble.fr}
\urladdr{http://vbeffara.perso.math.cnrs.fr/}

\thanks{Journées X-UPS 2016. Arbres et marches aléatoires. Éditions de l'École polytechnique, 2016}

\begin{abstract}
Ce texte présente quelques propriétés de la marche auto-évitante
uniforme sur un réseau, ainsi qu'une preuve complète du résultat de
Duminil-Copin et Smirnov calculant la constante de connectivité du
réseau hexagonal.
\end{abstract}

\maketitle
\centerline{\includegraphics[angle=90,width=\hsize]{SAW-big}}
\tableofcontents
\mainmatter

\section{Introduction}

La loi de probabilité la plus élémentaire est certainement la
\emph{loi uniforme sur un ensemble fini $\Omega$}, qui associe à
chaque éventualité $\omega\in\Omega$ la même probabilité
$|\Omega|^{-1}$; cette mesure devient intéressante dès qu'on donne à
$\Omega$ une structure supplémentaire, et le but de ce texte est de
décrire en détail ce que l'on sait (et on sait peu de choses!) sur un
cas particulièrement naturel, où $\Omega$ est un ensemble de chemins
sur un réseau.

\subsection{Un petit échauffement}

Soit $n$ un entier positif, et notons $S_n$ l'ensemble des chemins de
longueur $n$ dans $\mathbb Z$ faisant des pas $\pm1$. Plus précisément:
\begin{equation}
S_n:= \left\{ (\omega_k)_{0\leq k\leq n} \in \mathbb Z^{n+1}:
\omega_0=0 \text{~et~} \forall i<n, |\omega_{i+1}-\omega_i| = 1
\right\}.
\end{equation}
Il est facile de voir que le cardinal de $S_n$ est égal à $2^n$. La
mesure uniforme $P_n$ sur $S_n$ décrit exactement les $n$ premiers pas
d'une \emph{marche aléatoire simple sur $\mathbb Z$}, autrement dit
sous la loi $P_n$ les accroissements $(\omega_{i+1}-\omega_i)$ sont
indépendants et de même loi. En particulier tous les résultats
classiques sur les tirages indépendants s'appliquent: la loi de
$\omega_n$ est à transformation affine près une loi binomiale
$\mathcal B(n,1/2)$, et quand~$n\to\infty$ on a une loi des grands
nombres, un théorème central limite, une loi du logarithme itéré, des
estimées de grandes déviations...

Une propriété fondamentale des mesures $P_n$ est leur
\emph{compatibilité}: pour $n<m$, si on regarde la loi de
$(\omega_k)_{k\leq n}$ sous la mesure $P_m$ (en oubliant les $m-n$
derniers pas) on trouve exactement $P_n$. Cela entraîne, par le
théorème d'extension de Kolmogorov, l'existence d'un analogue de $P_n$
pour $n=+\infty$, donc une mesure de probabilités sur les chemins
infinis à valeurs dans $\mathbb Z$ sous laquelle la loi des $n$
premiers pas est $P_n$. Tout cela n'est bien sûr qu'une manière
pompeuse de dire qu'on peut regarder la marche aléatoire simple
$(X_n)$ pour $n\in\mathbb N$!

\subsection{Le modèle}

Il est temps de définir l'objet central de ce texte. Fixons une
dimension entière $d\geq1$, et considérons l'ensemble des chemins
auto-évitants de longueur $n$ dans $\mathbb Z^d$:
\begin{equation}
\Omega_n^d:= \left\{ (\omega_k)_{0\leq k\leq n} \in (\mathbb
Z^d)^{n+1}:
\begin{array}{l}
\omega_0=0 \\
\forall i<n, |\omega_{i+1}-\omega_i| = 1 \\
\forall i<j, \omega_i \neq \omega_j
\end{array}
\right\}
\end{equation}
(en notant $|\cdot|$ la norme euclidienne, ce qui revient à dire que
$\omega$ est un chemin par plus proches voisins dans $\mathbb Z^d$).

\begin{definit}
On notera $P_n^d$ la mesure de probabilité uniforme sur
$\Omega_n^d$; on appelle \emph{marche auto-évitante de longueur $n$
sur $\mathbb Z^d$} un chemin aléatoire de loi $P_n^d$.
\end{definit}

En dimension $d=1$ il ne se passe rien d'extraordinaire, $\Omega_n^1$
a exactement deux éléments (le chemin qui marche vers la droite et
celui qui marche vers la gauche), et le modèle est trivial. Dans toute
la suite on supposera donc $d\geq2$, et on l'omettra le plus souvent
dans les notations (on écrira donc $\Omega_n$ pour $\Omega_n^d$ etc.).

Bien sûr le modèle peut être défini dans une généralité beaucoup plus
grande, dès que l'on dispose d'un graphe infini de degré partout fini
on peut définir les objets dont il est question ici. Le réseau
$\mathbb Z^d$ a l'avantage d'être à la fois facile à définir et non
trivial du point de vue de la marche auto-évitante. On verra dans la
partie~\ref{sec:DCS} que le réseau hexagonal joue aussi un rôle
particulier dans la théorie.

Du point de vue de la physique, la marche auto-évitante en dimension
$3$ est une modélisation raisonnable du comportement d'un polymère
linéaire en solution: un tel polymère est une longue chaîne de
monomères identiques, chacun étant à distance fixée de ses voisins le
long de la chaîne, et satisfaisant la contrainte que deux monomères ne
peuvent pas occuper la même position dans l'espace. Le choix de la
mesure uniforme, plutôt que de tenir compte d'interactions à plus
longue portée, est une restriction dont les physiciens conjecturent
qu'elle a (dans un certain régime) peu d'effet sur le comportement
asymptotique qualitatif de la chaîne; Cf.~\ref{sec:polymer} pour plus
de détails.

\subsection{La constante de connectivité}

Soit $c_n=|\Omega_n|$ le nombre de chemins auto-évitants de longueur~$n$. La première question naturelle qui se pose est celle du calcul de~$c_n$. La remarque cruciale est la suivante: si on se donne un chemin
$\omega\in\nobreak\Omega_{m+n}$, on peut le découper en un \emph{préfixe} de
longueur $m$ et un \emph{suffixe} de longueur $n$, qui sont deux
chemins auto-évitants. Ceci construit une injection de $\Omega_{m+n}$
dans $\Omega_m \times \Omega_n$, et on obtient l'inégalité
\begin{equation}
\label{eq:subadd}
c_{m+n} \leq c_m c_n.
\end{equation}

D'autre part, l'encadrement suivant est immédiat:
\begin{equation}
\label{eq:apriori}
d^n \leq c_n \leq (2d)^n
\end{equation}
(la première inégalité provient du fait que si les sauts de $\omega$
ont toutes leurs coordonnées positives, alors $\omega$ est
automatiquement auto-évitant). La suite $(\log c_n)$ est par
conséquent sous-additive, et bornée inférieurement et supérieurement
par deux suites arithmétiques: c'est un exercice classique de montrer
que cela implique l'existence de la limite de $n^{-1} \log c_n$. En
reprenant l'exponentielle:

\begin{definit}
On appelle \emph{constante de connectivité} du réseau $\mathbb
Z^d$ la limite
\begin{equation*}
\mu_d:= \lim_{n\to\infty} c_n^{1/n} \in [d,2d].
\end{equation*}
\end{definit}

\begin{remarq}
La sous-additivité fournit également une borne inférieure:
\begin{equation}
\forall n, \quad c_n \geq \mu^n.
\end{equation}
On ne connaît pas de bonnes bornes supérieures en toute généralité.
Cf.~\ref{sec:HW} pour une majoration un peu brutale, la
section~\ref{sec:lace} pour le cas $d\gg1$ et~\ref{sec:1132} pour
des conjectures en dimension $2$. Une borne supérieure légèrement
meilleure sur $\mu$ peut être obtenue en remarquant qu'une marche
auto-évitante ne peut jamais revenir sur ses pas, ce qui implique
qu'à part en $0$ on a au plus $2d-1$ continuations possibles à
chaque pas, et entraîne $\mu \leq 2d-1$. Il est possible de faire
encore un peu mieux:
\end{remarq}

\begin{exercice}
Montrer les inégalités strictes: $d < \mu_d < 2d-1$.
\end{exercice}

\subsection{La suite}
\label{sec:plan}

Le reste de ce texte est subdivisé en parties essentiellement
indépendantes. La partie~\ref{sec:more} est consacrée à des résultats
généraux sur la marche auto-évitante, valables en assez grande
généralité, avec des indications de preuves mais sans toujours de
démonstration complète, on pourra se référer au
livre~\cite{madras-self} pour la plupart des détails. La
partie~\ref{sec:DCS} contient une preuve complète du théorème de
Duminil-Copin et Smirnov, qui calcule la valeur de la constante de
connectivité du réseau hexagonal. La partie~\ref{sec:variant} liste
quelques variantes du modèle, qui sont plus ou moins facile à étudier.
La partie~\ref{sec:lace} décrit la théorie du \emph{développement en
lacets} qui permet d'étudier le modèle en grande dimension, et donne
(sans preuve) les principaux résultats. Enfin, la~partie~\ref{sec:conj} fait le point sur quelques conjectures et
questions ouvertes.

Pour ce qui est de la bibliographie, la référence habituelle est le
livre de Madras et Slade~\cite{madras-self}, mais il ne contient pas
la preuve de Duminil-Copin et Smirnov. Les notes de cours de Slade à
l'école d'été de Buzios~\cite{Bauerschmidt2010} constituent une
excellente entrée en matière, et recouvrent une grande partie des
résultats mentionnés ici.

\section{Résultats un peu moins élémentaires}
\label{sec:more}

\subsection{La suite \texorpdfstring{$(c_n)$}{cn}}
\label{sec:cn}

On a vu que par sous-additivité, $c_n^{1/n} \to \mu$. Il est facile
d'en dire un petit peu plus sur cette suite, par exemple on peut
montrer que pour $n>0$, $$c_{n+2} > c_n.$$ L'argument est astucieux
mais simple: étant donnée une marche $\omega$ de longueur $n$, on
localise le point $\omega_k$ de la trajectoire qui est le plus grand
pour l'ordre lexicographique (première coordonnée maximale, deuxième
coordonnée maximale parmi les points de première coordonnée maximale,
etc.) et on remplace le pas $(\omega_k, \omega_{k+1})$ par un petit
chemin de longueur $3$, $(\omega_k,\eta_1,\eta_2,\omega_{k+1})$ qui
complète ce pas en un carré.

Le chemin que l'on obtient est de longueur $n+2$. Il est auto-évitant
si on oriente le petit carré ajouté de telle sorte que le nouveau
sommet maximal pour l'ordre lexicographique soit $\eta_1$ ou $\eta_2$.
Par ailleurs, sous cette condition, on obtient une injection de
$\Omega_n$ dans $\Omega_{n+2}$ car il est possible d'identifier sur la
nouvelle trajectoire la position de l'ajout.

Il est encore vrai que pour tout $n>0$ on a $c_{n+1} > c_n$. La
construction ci-dessus ne permet toutefois pas de changer la parité de
la longueur de $\omega$, et la preuve~\cite{OBrien1990} est beaucoup
plus technique. Il est aussi sans doute vrai que la suite
$c_{n+1}/c_n$ converge vers $\mu$ (la convergence de $\sqrt[n]{c_n}$
vers $\mu$ en découlerait par Cesáro), mais il s'agit d'une question
ouverte. On ne sait prouver que la convergence entre des termes de
même parité \cite{kesten1963,kesten1964a}, \emph{i.e.}
\begin{equation}
\label{eq:convn2n}
\frac{c_{n+2}}{c_n} \mathop{\longrightarrow}_{n\to\infty} \mu^2.
\end{equation}

On connaît par ailleurs la valeur exacte de $c_n$ pour les \og petites\fg
valeurs de~$n$. Le calcul nécessite des algorithmes
astucieux~\cite{Jensen2004a}, et par exemple dans le réseau
$\mathbb Z^2$ on connaît le nombre de marches auto-évitantes de
longueur jusqu'à la valeur $n=71$:
$$c_{71} = 4\,190\,893\,020\,903\,935\,054\,619\,120\,005\,916.$$
La connaissance de ces valeurs permet de trouver une valeur approchée
de la constante de connectivité en dimension $2$: $\mu \simeq 2.638$.

\subsection{L'algorithme du pivot}

Une question naturelle est de savoir comment, en pratique, tirer au
hasard un élément de $\Omega_n$ de loi uniforme. On ne dispose pas
d'algo\-rithme réalisant ce tirage de manière exacte et efficace (ce qui
\hbox{traduit} le manque de compréhension mathématique que nous avons du
\hbox{modèle}).

Il y a une procédure qui réalise un tirage exact, et qui consiste en
une application de la \emph{méthode du rejet}: on tire au sort un
chemin de longueur $n$ dans $\mathbb Z^d$, et s'il est auto-évitant on
le conserve, sinon on l'ignore et on en tire au sort un nouveau, et
ainsi de suite jusqu'à tomber sur un élément de $\Omega_n$. Cette
construction s'arrête en temps fini, et fournit un élément de
$\Omega_n$ dont la loi est uniforme. Mais la méthode est extrêmement
mauvaise en pratique car le nombre moyen de tirages qu'il faut
réaliser est égal à $(2d)^n / c_n$ qui est exponentiellement grand.

On sait toutefois fabriquer des chemins aléatoires de longueur $n$,
auto-évitants, dont la loi est \emph{presque} uniforme, en itérant un
grand nombre de fois une transformation simple qui est définie de la
manière suivante. Si $\omega\in\Omega_n$, et si on se donne une paire
$(k,\theta) \in \{0,\ldots,n\} \times \{ \pi/2, \pi, 3\pi/2 \}$,
notons $\tilde R_{(k,\theta)}(\omega)$ le chemin obtenu à partir de
$\omega$ en ne touchant pas ses $k$ premiers pas, et en appliquant aux
$n-k$ suivants la rotation d'angle $\theta$ autour de $\omega_k$.
Puis, notons $$R_{(k,\theta)} (\omega) = \begin{cases}
\tilde R_{(k,\theta)} (\omega) & \mbox{si $\tilde R_{(k,\theta)}
(\omega) \in \Omega_n$,} \\
\omega & \mbox{sinon}.\end{cases}$$
Autrement dit, on essaye de déformer $\omega$ par une opération de
pivot, mais on ne le fait que si le chemin obtenu est auto-évitant.

L'algorithme du pivot consiste à répéter l'opération
$R_{(k_i,\theta_i)}$ un grand nombre de fois, pour des paires
$(k_i,\theta_i)$ aléatoires, pour construire une suite de chemins
$(\omega^i)_{i\geq0}$ dans $\Omega_n$ récursivement en
posant $$\omega^i = R_{(k_i,\theta_i)} (\omega^{i-1}).$$ Il est simple
de montrer que la loi de $\omega^i$ converge vers la mesure uniforme
sur $\Omega_n$: en fait $(\omega^i)$ est une chaîne de Markov sur
$\Omega_n$, et la mesure uniforme $P_n$ est \emph{réversible} pour
cette chaîne, ce qui implique qu'elle soit invariante ; la seule étape
subtile de la preuve est l'exercice suivant.

\begin{exercice}
Soient $\omega$ et $\omega'$ deux éléments de $\Omega_n$: montrer
que l'on peut passer de l'une à l'autre par des opérations de pivot,
\emph{i.e.} qu'il existe $(k_i,\theta_i)_{1\leq i\leq m}$ tels
que
$$\omega' = R_{(k_m,\theta_m)} \circ \cdots \circ R_{(k_1,\theta_1)}
(\omega).$$ Montrer que cet énoncé devient faux si on n'autorise pas
la valeur $\pi$ pour les angles de rotation $\theta_i$.
\end{exercice}

\begin{figure}
\centering
\includegraphics[width=\hsize]{SAW}
\caption{Une marche auto-évitante obtenue par l'algorithme du pivot
(longueur $n=1000$, $10^6$ opérations élémentaires).}
\label{fig:saw}
\end{figure}

La situation n'est pas satisfaisante pour autant, car on ne sait pas
précisément quelle est la vitesse de convergence de l'algorithme. Il
est probable que le nombre d'opérations élémentaires nécessaires pour
obtenir une bonne approximation se comporte comme une puissance de
$n$, mais il n'y a pas de conjecture sur la valeur de l'exposant.

\subsection{La borne de Hammersley-Welsh}
\label{sec:HW}

On a vu que par un argument de sous-multiplicativité, on a facilement
une minoration de $c_n$ par une suite géométrique. Trouver une borne
supérieure est beaucoup plus ardu. On conjecture un majorant de la
forme $\mu^n n^A$ pour une certaine puissance $A$ dépendant de la
dimension, mais une telle borne n'est connue que pour $d$ grand (\cf
section~\ref{sec:lace}). Le seul résultat dans ce sens qui soit prouvé
en toute généralité est beaucoup moins précis:

\begin{theorem}[Hammersley, Welsh, 1962 \cite{Hammersley1962}]
\label{thm:hw}
On a l'encadrement suivant du nombre de chemins auto-évitants:
$$\mu^n \leq c_n \leq \mu^n e^{\mathcal O(\sqrt n)}.$$
\end{theorem}

L'idée de la preuve est la suivante (en dimension $2$, mais l'argument
se généralise facilement). Un \emph{pont} de longueur $n$ est une
marche auto-évitante $\omega \in \Omega_n$ tel que pour tout $i>0$,
l'abscisse de $\omega_i$ soit strictement positive, prenant sa valeur
maximale pour $\omega_n$ (et éventuellement d'autres); notons
$\Lambda_n$ l'ensemble des ponts de longueur $n$ et
$b_n = |\Lambda_n|$ leur nombre. Clairement
\begin{equation}
\label{eq:ponttriv}
b_n \leq c_n.
\end{equation}
D'autre part, étant donnés deux ponts de longueurs respectives $m$ et~$n$, il est toujours possible de les concaténer pour obtenir un pont
de longueur $m+n$: cela entraîne l'inégalité
\begin{equation}
\label{eq:pontsub}
b_{m+n} \geq b_m b_n,
\end{equation}
autrement dit la sous-multiplicativité de $(c_n)$ marche dans l'autre
sens pour la suite $(b_n)$. Il existe donc une constante de
connectivité~$\mu'$ pour les ponts, et on a \og gratuitement\fg la
majoration $b_n \leq (\mu')^n$. Par ailleurs, on a aussi
immédiatement $\mu' \leq \mu$.

Il reste à obtenir une borne supérieure pour $c_n$ en termes des
$b_n$. C'est là qu'il faut être un peu astucieux \ldots\ l'idée
consiste à partir d'une marche auto-évitante et à la \og déplier\fg
autour de ses pas d'abscisses maximales et minimales jusqu'à pouvoir
l'écrire comme concaténation de ponts (\cf Figure~\ref{fig:hw}). Les
largeurs $(\ell_k)$ des ponts obtenus forment deux suites
décroissantes, une de chaque côté, et leur somme est inférieure ou
égale à $n$: le nombre de telles paires de suites peut alors être
contrôlé par le nombre de \emph{partitions} de $n$ en entiers, qui se
comporte \cite{Hardy1917} comme $e^{\mathcal O(\sqrt n)}$. La marche
ainsi dépliée est elle-même un pont, et elle permet de retrouver la
marche initiale connaissant les $(\ell_k)$.

On obtient ainsi une application de $\Omega_n$ vers $\Lambda_n$, pour
laquelle chaque pont a au plus $e^{\mathcal O(\sqrt n)}$ antécédents:
il s'ensuit que
\begin{equation}
\label{eq:pre}
c_n \le b_n e^{\mathcal O(\sqrt n)}.
\end{equation}
En combinant \eqref{eq:ponttriv} et \eqref{eq:pre}, on obtient bien
$\mu = \mu'$ et l'encadrement du théorème~\ref{thm:hw}.

\begin{figure}
\centering
\includegraphics{HW}
\caption{La preuve du théorème~\ref{thm:hw}: dépliage d'une marche
auto-évitante de longueur $n=46$ en ponts, et notation utilisée}
\label{fig:hw}
\end{figure}

\subsection{Contrôle des fluctuations}

Nous terminons cette partie par l'énoncé (sans preuve) de deux
résultats récents sur le comportement d'une longue marche
auto-évitante uniforme. Ces résultats sont loin d'être optimaux, et le
fait qu'ils ne datent que de quelques années est une indication
supplémentaire de notre manque de compréhension du modèle. Dans tout
le reste de cette section on suppose implicitement que $d\geqslant2$
(le cas $d=1$ étant trivial et qualitativement différent).

Le premier énoncé montre que le diamètre de la marche ne croît pas
linéairement en le nombre de pas, ce qui est à comparer au
comportement de la marche aléatoire simple pour laquelle le même
diamètre se comporte de manière diffusive (c'est-à-dire comme
$\sqrt n$):

\begin{theorem}[Duminil-Copin, Hammond, 2013
\cite{Duminil-Copin2013a}] Pour tout $v>0$ il existe $\varepsilon>0$
tel que pour tout $n>0$,
$$P_n \left[ \max_{0\leq k\leq n} \|\omega_k\| \geqslant vn \right]
\leqslant e^{-\varepsilon n}.$$ Cela entraîne que
$E[\|\omega_n\|^2] = o(n^2)$.
\end{theorem}

Encore une fois on sait ce qui se passe en grande dimension, et pour
$d\geqslant 5$ la marche auto-évitante se comporte comme la marche
simple. En dimension $2$, on n'a que des conjectures,
cf.~\ref{sec:1132} ; en dimension $3$, on ne sait absolument rien de
plus.

Terminons par deux énoncés reliés, qui indiquent d'une certaine façon
que la marche auto-évitante est \og vraiment aléatoire\fg au sens où la
loi de son point final est de plus en plus dispersée quand $n$ est
grand \cite{Duminil-Copin2016a}:

\begin{theorem}[Duminil-Copin, Glazman, Hammond, Manolescu, 2016] En toute dimension $d\geq2$, pour tout
$\varepsilon>0$ il existe $N>0$ tel que pour tout $n\geqslant
N$, $$P_n[|\omega_n| = 1] \leqslant n^{-1/4+\varepsilon}.$$
\end{theorem}

\begin{theorem}[Duminil-Copin, Glazman, Hammond, Manolescu, 2016] En toute dimension $d\geq2$,
$$\lim_{n\to\infty} \sup_{x \in \mathbb Z^d} P_n[w_n=x] = 0.$$
\end{theorem}

Ici encore, le cas de la grande dimension est mieux connu puisqu'on
sait prouver un théorème de la limite centrale et une borne supérieure
sur ces probabilités qui est de l'ordre de $n^{-d/2}$.

\section{La constante de connectivité du réseau hexagonal}
\label{sec:DCS}

Dans toute cette partie, on se place au lieu de $\mathbb Z^d$ sur le
réseau hexagonal $\mathbb H$, qui est un réseau planaire périodique
dont tous les sommets sont de degré $3$ et toutes les faces sont des
hexagones. Une des principales avancées récentes dans l'étude de la
marche auto-évitante est le calcul de la constante de connectivité de
ce réseau:

\begin{theorem}[Duminil-Copin, Smirnov, 2010 \cite{DS-saw}]
\label{thm:DCS}
La constante de connectivité du réseau hexagonal est égale à
$$\mu_{\mathbb H} = \sqrt {2 + \sqrt 2} = 2\cos (\sfrac \pi 8).$$
\end{theorem}

Cette valeur était conjecturée par Nienhuis depuis les années 80
\cite{Nienhuis1982,Nienhuis1984} mais sa prédiction était basée sur
des méthodes mathématiquement non rigoureuses ; comme on va le voir,
la preuve de Duminil-Copin et Smirnov est \og élémentaire\fg, même si
l'intuition qui y a mené provient de théories plus profondes.

\begin{exercice}
En échauffement, montrer qu'on a bien
$\displaystyle2 \cos (\sfrac \pi 8) = \sqrt {2 + \sqrt 2}$.
\end{exercice}

\subsection{Notations}
\label{sec:DCSdef}

Nous utiliserons les mêmes notations que l'article
original~\cite{DS-saw}, dont cette section est essentiellement une
traduction. On considère le réseau hexagonal $\mathbb H$ plongé dans
le plan complexe $\mathbb C$ de telle sorte que ses faces soient des
hexagones réguliers, et on note $H$ l'ensemble des milieux des arêtes
de $\mathbb H$; il sera plus agréable de considérer des chemins
auto-évitants entre des points de $H$, et d'aligner $H$ de telle sorte
qu'il contienne l'origine du plan.

Si $\gamma$ est un chemin, on notera $\ell(\gamma)$ sa longueur. Par
ailleurs on reprend la notation précédente $\Omega_n$ pour l'ensemble
des chemins auto-évitants $\gamma$ de longueur $\ell(\gamma)=n$, leur
nombre $c_n = |\Omega_n|$ et on note~$\Omega$ la réunion des
$\Omega_n$. L'objet central de l'argument est la \emph{fonction de
partition}: pour $x\in\mathbb R_+$,
\begin{equation}
\label{eq:fp}
Z(x) = \sum_{\gamma \in \Omega} x^{\ell(\gamma)} = \sum_{n
\geq 1} c_n x^n \in [0,+\infty].
\end{equation}
Il s'agit d'une série entière dont le rayon de convergence est égal à
$1/\mu_{\mathbb H}$. En notant
\begin{equation}
\label{eq:xc}
x_c:= \frac 1 {\sqrt {2 + \sqrt2}},
\end{equation}
le théorème revient donc à l'énoncé que le rayon de convergence de~$Z$
est égal à $x_c$.

\subsection{L'observable de Smirnov}
\label{sec:DCSobs}

Si $\gamma$ est un chemin auto-évitant et si $a$ et $b$ sont deux
milieux d'arêtes sur $\gamma$, le \emph{nombre d'enroulements} de
$\gamma$ entre $a$ et $b$, qu'on notera $W_\gamma(a,b)$, est égal à
$\pi(n_+-n_-)/3$, où $n_+$ (\resp $n_-$) est le nombre de fois que le
chemin $\gamma$ tourne à gauche (\resp à droite) entre~$a$ et~$b$. On
peut le voir comme une version discrète de la variation de l'angle du
vecteur unitaire tangent le long de la courbe entre les points~$a$ et~$b$.

\begin{definit}
Soient $\Omega$ un domaine de $\mathbb H$, $a$ un milieu d'arête
fixé sur le bord de $\Omega$, $\sigma = 5/8$ et $x\in\mathbb R_+$.
L'\emph{observable parafermionique} $F = F_{\Omega,a,x}$ est
définie en tout milieu d'arête $z$ par $$F(z):= \sum_{\gamma: a
\to z} x^{\ell(\gamma)} e^{-i\sigma W_\gamma(a,z)}$$ (où la somme
porte sur tous les chemins auto-évitants de $a$ à $z$ qui sont
contenus dans le domaine $\Omega$).
\end{definit}

\begin{figure}[ht!]
\centering
\includegraphics[width=.9\hsize]{DCS-SAWpicture}
\caption{Un domaine de $\mathbb H$, et la définition de
l'enroulement.}
\end{figure}

La première étape de la preuve est un énoncé d'\emph{analyticité
discrète} de $F$:

\begin{lemma}
\label{lem:discharm}
Soit $v$ un sommet de $\Omega$, et $p$, $q$, $r$ les milieux des
arêtes incidentes à $v$ (tous identifiés à leurs affixes complexes).
Si $x=x_c$, alors $$(p-v) F(p) + (q-v) F(q) + (r-v) F(r) = 0.$$
\end{lemma}

\begin{proof}
On prouve en fait un résultat un peu plus fort. Si $\gamma$ est un
chemin auto-évitant issu de $a$, sa \emph{contribution}
est
$$c(\gamma):= (\gamma_{\ell(\gamma)} - v) x_c^{\ell(\gamma)} e^{-i
\sigma W_\gamma(a, \gamma_{\ell(\gamma)})}$$ (qui dépend du point
final $\gamma_{\ell(\gamma)}$ du chemin $\gamma$). Le membre de
gauche dans l'énoncé du lemme~\ref{lem:discharm} est la somme des
contributions de tous les chemins aboutissant en $p$, $q$ et $r$; on
va grouper cette somme en paquets qui seront tous de somme nulle, de
la façon suivante:
\begin{itemize}
\item Si $\gamma_1$ est un chemin auto-évitant arrivant en $p$, mais
qui passe auparavant en $q$ et $r$ (et donc ferme presque une
boucle), on peut lui associer un autre chemin $\gamma_2$ qui
utilise les mêmes sommets mais parcourt la boucle dans l'autre
sens (et qui arrive donc soit en $q$, soit en $r$) --- \cf
Figure~\ref{fig:contrib}, dessin de gauche. On vérifie alors
que $$c(\gamma_1) + c(\gamma_2) = 0.$$ En effet, $\gamma_1$ et
$\gamma_2$ ont la même longueur, et leur enroulement diffère de
$8\pi/3$ alors que les arguments des préfacteurs ($p-v$ et soit
$q-v$, soit $r-v$) diffère de $2\pi/3$: par conséquent, en tenant
compte de l'orientation,
$$\frac {c(\gamma_1)} {c(\gamma_2)} = e^{-2i\pi/3} e^{(5/8)
(8i\pi/3)} = e^{5i\pi/3 - 2i\pi/3} = -1.$$
\item Si par contre $\gamma_1$ ne visite ni $q$ ni $r$, on peut le
prolonger d'un pas de deux façons, en lui ajoutant soit $q$ soit
$r$, pour obtenir deux chemins $\gamma_2$ et $\gamma_3$. Encore
une fois on vérifie que
$$c(\gamma_1) + c(\gamma_2) + c(\gamma_3) = 0.$$ En effet,
$\ell(\gamma_2) = \ell(\gamma_3) = \ell(\gamma_1)+1$, les
enroulements de $\gamma_2$ et $\gamma_3$ diffèrent de celui de
$\gamma_1$ de $\pm \pi/3$ et les arguments des préfacteurs de~$\mp
2i\pi/3$:\vspace*{-3pt}
\begin{align*}
\frac {c(\gamma_1) + c(\gamma_2) + c(\gamma_3)}
{c(\gamma_1)} &= 1 + x_c (e^{2i\pi/3 + (5/8)i\pi/3} +
e^{-2i\pi/3 - (5/8)i\pi/3}) \\
&= 1 + 2 x_c \cos (21 \pi/24) = 1 - 2 x_c \cos
(\pi/8).
\end{align*}
Il n'y a plus qu'à utiliser le fait que $\cos (\pi/8) = \frac12
\sqrt{2+\sqrt2}$.
\end{itemize}

Tous les chemins contribuant au membre de gauche de l'énoncé
apparaissent dans exactement un de ces cas, ce qui conclut la preuve
du lemme.
\end{proof}

\begin{figure}[ht]
\centering
\includegraphics[width=\hsize]{DCS-pairs}
\caption{La preuve du lemme~\ref{lem:discharm}.}
\label{fig:contrib}
\end{figure}

\subsection{Une estimée dans une bande}
\label{sec:strip}

Un domaine où il est instructif de considérer l'observable est la
bande verticale $S_T$ de largeur $T$, ou sa troncature $S_{T,L}$ de
hauteur $L$ finie (\cf Figure~\ref{fig:STL}). En reprenant toujours
les notations de~\cite{DS-saw}, soit~$\alpha$ le bord de gauche de
$S_T$, $\beta$ son bord de droite, et $\varepsilon$ et
$\bar \varepsilon$ les bords haut et bas de $S_{T,L}$ respectivement.
Ici $a$ sera pris au milieu de $\alpha$. On peut regarder des sommes
partielles de la fonction de partition $Z$ dans $S_{T,L}$:\vspace*{-3pt}\enlargethispage{\baselineskip}
$$A_{T,L}^x:= \sum_{\gamma: a \to \alpha\setminus\{a\}}
x^{\ell(\gamma)}, \quad B_{T,L}^x:= \sum_{\gamma: a \to \beta}
x^{\ell(\gamma)}, \quad E_{T,L}^x:= \sum_{\gamma: a \to \varepsilon
\cup \bar\varepsilon} x^{\ell(\gamma)}$$ (où la notation
$\gamma:a\to\beta$ par exemple signifie que l'on somme sur tous les
chemins auto-évitants partant de $a$, contenus dans $S_{T,L}$ et dont
le dernier point est dans $\beta$).

\begin{lemma}\label{lem:strip}
Pour le paramètre $x_c$ on a l'égalité\vspace*{-3pt}
$$c_\alpha A_{T,K}^{x_c} + B_{T,L}^{x_c} + c_\varepsilon
E_{T,L}^{x_c} = 1,$$ où l'on a posé $c_\alpha = \cos(3\pi/8)$ et
$c_\varepsilon = \cos(\pi/4)$.
\end{lemma}

\begin{proof}
Sommons l'égalité du lemme précédent en tous les sommets dans
$S_{T,L}$. Tous les termes correspondant aux milieux d'arêtes hors
du bord apparaissent deux fois avec des signes différents, et
disparaissent de la somme: il reste donc les termes de bord,
\begin{equation}\label{eq:boundary}
0=-\sum_{z\in \alpha}F(z)+\sum_{z\in \beta}F(z)+j\sum_{z\in
\epsilon}F(z)+\bar{j}\sum_{z\in \bar{\epsilon}}F(z)
\end{equation}
avec $j=e^{2i\pi/3}$. Évaluons chacune de ces sommes séparément, en
remarquant que par symétrie on a partout $F(\bar z) = \bar F(z)$ et
que l'enroulement d'un chemin en une demi-arête du bord ne dépend
que de la position de cette demi-arête (et coïncide avec
l'enroulement du bord lui-même).
\begin{itemize}
\item La somme sur $\alpha$ consiste en $F(a) = 1$ et en une partie
symétrique:
\begin{align*}
\sum_{z\in \alpha} F(z) &= 1 + \sum_{z\in \alpha\setminus \{a\}}
F(z) = 1 + \sum_{z\in \alpha \setminus
\{a\}} \frac {F(z)+F(\bar z)} 2 \\
&= 1 + \frac {e^{5i \pi/8} + e^{-5i
\pi/8}}{2}A^x_{T,L}=1-\cos
(\sfrac{3\pi}{8}) A^x_{T,L}.
\end{align*}
\item La somme sur $\beta$ fait intervenir des enroulements tous
nuls: $$\sum_{z\in \beta}F(z)=B^x_{T,L}.$$
\item Enfin le long des bords obliques, on trouve de manière
similaire
$$j\sum_{z \in \epsilon} F(z) + \bar{j} \sum_{z \in
\bar{\epsilon}} F(z) = \cos (\sfrac\pi 4) E^x_{T,L}.$$
\end{itemize}
En sommant ces trois termes on obtient bien l'identité annoncée.
\end{proof}

\begin{figure}[ht]
\centering
\includegraphics[width=0.50\hsize]{DCS-domain}
\caption{Notations du lemme~\ref{lem:strip}.}
\label{fig:STL}
\end{figure}

\subsection{Minoration de \texorpdfstring{$\mu$}{mu}}
\label{sec:min}

Les sommes $A_{T,L}^x$ et $B_{T,L}^x$ sont des fonctions croissantes
de $L$ et $x$; d'autre part le lemme~\ref{lem:strip} leur donne une
borne supérieure uniforme pour tous les paramètres $x \leqslant x_c$.
On peut donc définir les limites
$$A_T^x:= \lim_{L\to\infty} A_{T,L}^x \quad \text{et} \quad B_T^x:=
\lim_{L\to\infty} B_{T,L}^x.$$ Par ailleurs, toujours par le
lemme~\ref{lem:strip}, $E_{T,L}^{x_c}$ est une fonction décroissante
de $L$, et on peut aussi définir sa limite $E_T^{x_c}$ quand
$L\to\infty$. On~obtient l'identité
\begin{equation}
\label{eq:ident}
c_\alpha A_T^{x_c} + B_T^{x_c} + c_\varepsilon E_T^{x_c} = 1.
\end{equation}

Supposons un instant que l'on ait $E_T^{x_c}>0$. Alors tous les
$E_{T,L}^{x_c}$ sont uniformément minorés, et leur somme (pour $L>0$)
est un minorant de $Z(x_c)$. On aurait donc $Z(x_c) = +\infty$, ce qui
implique que le rayon de convergence de la série qui définit $Z$ est
au plus égal à $x_c$. Autrement dit, on aurait la borne $\mu \geqslant
\sqrt{2+\sqrt2}$.

Supposons à présent à l'inverse que l'on ait $E_T^{x_c}=0$ pour tout
$T$. Alors la conclusion du lemme~\ref{lem:strip} se récrit
$c_\alpha A_T^{x_c} + B_T^{x_c} = 1$. Faisons alors la remarque
combinatoire suivante: un chemin auto-évitant $\gamma$ qui est compté
dans $A_{T+1}^{x_c}$ mais pas dans $A_T^{x_c}$ doit atteindre
l'abscisse~$T$, et peut donc se décomposer en deux traversées
$\gamma_1$ et $\gamma_2$ de largeur $T+1$. On obtient ainsi la borne\vspace*{-3pt}
$$A_{T+1}^{x_c} - A_T^{x_c} \leqslant x_c (B_{T+1}^{x_c})^2$$ (le
facteur $x_c$ supplémentaire provient du premier pas de $\gamma_2$,
qui ne fait pas partie de $\gamma$). Par le lemme~\ref{lem:strip}, on
obtient alors\vspace*{-3pt}
$$c_\alpha x_c (B_{T+1}^{x_c})^2 + B_{T+1}^{x_c}
\geqslant B_T^{x_c}.$$ Un récurrence facile donne alors une borne
inférieure pour $B_T^{x_c}$ de la forme $C/T$, donc la somme des
$B_T^{x_c}$ est infinie, et elle minore $Z(x_c)$: à nouveau on obtient
$Z(x_c)=+\infty$ et la même conclusion que précédemment.

\subsection{Majoration de \texorpdfstring{$\mu$}{mu}}
\label{sec:maj}

On appelle \emph{pont} un chemin auto-évitant qui contribue à la somme $B_T^x$ (et on appelle $T$ sa \emph{largeur}). La majoration de $Z$, et
donc de $\mu$, est basée sur une décomposition de marches en ponts,
comme dans la preuve de l'inégalité de Hammersley-Welsh. Remarquons
d'abord que la longueur d'un pont de largeur $T$ est au moins égale à~$T$: par conséquent, pour $x<x_c$, on a\vspace*{-3pt}
$$B_T^x \leqslant (x/x_c)^T
B_T^{x_c} \leqslant (x/x_c)^T$$ (la borne $B_T^{x_c} \leqslant 1$
provient une fois de plus du lemme~\ref{lem:strip}). En particulier,
la somme des $B_T^x$ est convergente pour $x<x_c$.

Une reformulation de l'étape principale de la démonstration de
l'inégalité de Hammersley-Welsh avec nos notations actuelles est
alors\vspace*{-3pt}
$$Z(x) \leqslant 2 \sum \prod_{k=-i}^j B_{T_k}^x,$$ où l'on
somme sur toutes les valeurs positives de $i$ et $j$ et sur toutes les
familles de largeurs $T_0>T_1>\cdots>T_j$ et
$T_0>T_{-1}>\cdots>T_{-i}$. On reconnaît dans le terme de droite le
développement du produit\vspace*{-3pt}
$$2 \prod_{T>0} (1+B_T^x)^2,$$ qui est
convergent par l'estimée précédente: par conséquent\vspace*{-3pt}
\[
Z(x)<\nobreak\infty\quad \text{dès que $x<x_c$}, 
\]
ce qui fournit bien la borne supérieure
$\mu \leqslant \sqrt{2+\sqrt2}$. Le théorème~\ref{thm:DCS} est prouvé.

\section{Variantes du modèle}
\label{sec:variant}

La mesure uniforme sur $\Omega_n$ est naturelle mais c'est bien sûr
loin d'être la seule loi de probabilité sur des chemins auto-évitants.
En voici quelques-unes.

\subsection{Mesure de polymère}
\label{sec:poly}

Au lieu de considérer des chemins de longueur fixée, il peut être plus
pratique de rendre leur longueur elle-même aléatoire. Une bonne façon
de faire cela est de considérer un domaine connexe borné fixé $D$ dans
$\mathbb R^d$, avec deux points marqués $a$ et $b$ sur son bord, et
pour une maille de réseau $\delta>0$ de regarder l'ensemble (fini)
$\Omega_{D,\delta}$ des chemins auto-évitants dans
$D \cap \delta \mathbb Z^d$ reliant le sommet le plus proche de $a$ au
sommet le plus proche de $b$. Pour tout $x>0$, on peut définir une
mesure $P_{D,\delta,x}$ sur $\Omega_{D,\delta}$ en posant\vspace*{-3pt}\enlargethispage{.5\baselineskip}
$$P_{D,\delta,x}[\{\omega\}] = \frac {x^{\ell(\omega)}}
{Z_{D,\delta,x}} \quad \text{où} \quad Z_{D,\delta,x} = \sum_{\omega
\in \Omega_{D,\delta}} x^{\ell(\omega)}$$ (et où $\ell(\omega)$ est
la longueur du chemin $\omega$).

Si $x$ est inférieur à l'inverse $1/\mu$ de la constante de
connectivité du réseau, la mesure $P_{D,\delta,x}$ a tendance à
charger des chemins \og plus courts que des marches auto-évitantes
typiques\fg; quand $\delta\to0$, toute sa masse se concentre sur le
plus court chemin de $a$ vers $b$ dans $D$, et la limite d'échelle est
déterministe. Si en revanche $x \mu > 1$, les chemins \og plus longs que
des marches auto-évitantes typiques\fg (qui sont plus nombreux) sont
favorisés, et on conjecture que quand $\delta\to0$, la mesure
$P_{D,\delta,x}$ converge vers une probabilité portée par des courbes
de type Peano aléatoires (surjectives sur $\overline D$).

Enfin le cas $x=1/\mu$ est sans doute le plus intéressant; en
dimension $2$ la principale conjecture est la convergence de
$P_{D,\delta,1/\mu}$ vers un processus SLE(6) chordal de $a$ vers $b$
dans $D$. Cf.\ \cite{werner-saw} pour plus de détails.

\subsection{Polymères interagissants}
\label{sec:polymer}

Si on cherche un modèle plus satisfaisant du point de vue de la
modélisation d'un \og vrai\fg objet physique, la condition d'être
auto-évitant est pertinente mais une mesure qui ne dépend pas de la
forme du chemin ne l'est pas. En effet, des monomères qui sont
spatialement proches ont tendance à interagir plus que s'ils sont
lointains. Une façon de tenir compte de la physique est de définir sur
$\Omega_n$ la mesure $P_{n,\beta,J}$ en posant
\begin{equation}
\label{eq:PnJ}
P_{n,\beta,J} [\{\omega\}] = \frac 1 {Z_{n,\beta,J}} \exp \biggl[ -
\beta \sum _{0\leq i < j \leq n} J(\omega(j)-\omega(i))\biggr]
\end{equation}
où $Z_{n,\beta,J}>0$ est la \emph{fonction de partition} choisie de
telle sorte que $P_{n,\beta,J}$ soit bien une mesure de probabilité:
\begin{equation}
\label{eq:Z}
Z_{n,\beta,J} = \sum_{\omega \in \Omega_n} \exp \biggl[ -
\beta \sum _{0\leq i < j \leq n} J(\omega(j)-\omega(i))\biggr].
\end{equation}
Le coefficient $\beta>0$ joue le rôle de l'inverse de la température,
et le \emph{potentiel d'interaction} $J$ décrit la physique du
système.

Il s'agit d'une généralisation à la fois de la marche aléatoire simple
et de la marche auto-évitante: en effet,
\begin{itemize}
\item Pour $\beta=0$ on retrouve la mesure uniforme sur tous les
chemins;
\item Si on pose formellement $J(0)=+\infty$ la mesure se concentre
sur des chemins auto-évitants --- et si de plus on impose $J(r)=0$
pour $r\neq0$ on obtient exactement $P_{n,\beta,J}=P_n$ et
$Z_{n,\beta,J}=c_n$.
\end{itemize}
On peut même s'approcher de la modélisation de protéines en donnant à
chaque monomère de la chaîne un \og type\fg $\eta(i)$ et en faisant
dépendre le potentiel d'interaction de ces types.

Le \og méta-théorème de la physique statistique\fg énonce que la fonction
de partition contient toute l'information sur le modèle. On peut par
exemple en extraire à quel point un chemin de loi $P_{n,\beta,J}$ est
auto-évitant:
\begin{align*}
\frac {\partial Z_{n,\beta,J}} {\partial J(0)} &= \sum_{\omega \in \Omega_n} \frac {\partial} {\partial J(0)} \exp \biggl[ -\beta \sum _{0\leq i < j \leq n} J(\omega(j)-\omega(i)) \biggr] \\
&= \sum_{\omega \in \Omega_n} \sum_{\substack{i<j:\\ \omega(i)=\omega(j)}} (-\beta) \exp \biggl[ -\beta \sum _{0\leq i < j \leq n} J(\omega(j)-\omega(i)) \biggr]\\
&= -\beta \sum_{\omega \in \Omega_n} \bigl|\{ i<j: \omega(i)=\omega(j) \}\bigr|\, Z_{n,\beta,J}\, P_{n,\beta,J}[\{\omega\}]
\end{align*}
d'où en reconnaissant à droite l'expression d'une espérance:
\begin{equation}
\label{eq:ijZ}
\begin{split}
E \big[ |\{ i<j: \omega(i)=\omega(j) \}| \big] &= \frac {-1} {\beta
Z_{n,\beta,J}} \frac {\partial Z_{n,\beta,J}} {\partial J(0)}\\
&=\frac {-1} {\beta} \frac {\partial \log Z_{n,\beta,J}} {\partial J(0)}.
\end{split}
\end{equation}

De plus, si toutes les valeurs de $J$ sont positives, on retrouve la
sous-multiplicativité que l'on avait pour la marche auto-évitante
uniforme dans la fonction de partition:
\begin{equation}
\label{eq:Zsousadd}
Z_{m+n,\beta,J} \leq Z_{m,\beta,J} Z_{n,\beta,J}
\end{equation}
par le même argument que précédemment. On peut alors définir
l'\emph{énergie libre} du modèle,
\begin{equation}
\label{eq:H}
H(\beta,J):= \lim_{n\to\infty} \frac 1 n \log Z_{n,\beta,J}
\end{equation}
qui contient à nouveau \og toute l'information sur le modèle\fg dans ses
dérivées. Ainsi, la proportion moyenne d'auto-intersection peut se
voir comme la dérivée de $H$ par rapport au coefficient $J(0)$.

La littérature sur ces modèles est vaste et la décrire même
partiellement dépasserait le cadre de ces notes. Caricaturalement, le
comportement \og typique\fg est similaire d'un cas sur l'autre: pour une
interaction $J$ fixée, on observe le plus souvent une transition de
phase selon la valeur du paramètre $\beta$, et $\omega$ ressemble à
une marche sans interaction pour $\beta$ petit et à une marche
fortement interagissante pour~$\beta$ grand.

Il faut se méfier du cas où $J$ prend des valeurs négatives (ce qui
correspond à des interactions \emph{attractives} entre monomères, qui
sont omniprésentes pour des molécules organiques par exemple),
puisqu'alors on peut dans certains cas obtenir une borne inférieure
sur $Z_{n,\beta,J}$ qui est de l'ordre de $\exp(\Theta(n^2))$, et par
conséquent une énergie libre infinie. Pour obtenir un modèle non
trivial il faut alors considérer une température inverse $\beta$ de
l'ordre de $1/n$ (et perdre alors la sous-multiplicativité). On peut
alors obtenir des \emph{transitions de dénaturation} entre un polymère
replié et localisé à basse température, et une chaîne désordonnée et
délocalisée au-dessus d'une température critique.

\subsection{Marche aléatoire à boucles effacées}

Au lieu de compliquer le modèle, il peut être tentant de le
simplifier, non pas au niveau de sa définition (aucune mesure ne sera
plus simple à décrire que la mesure uniforme) mais en choisissant des
lois de probabilités sur $\Omega_n$ pour lesquelles on dispose de plus
d'outils.

Une façon simple d'obtenir un chemin auto-évitant de longueur $n$ est
la suivante: on part d'un chemin infini quelconque, on en efface les
boucles dès qu'elles apparaissent, et on s'arrête quand le chemin
obtenu est de la bonne longueur. En dimension $d \geq 3$ (où la marche
aléatoire est transiente), on peut formaliser la construction en
partant d'une marche aléatoire simple $(X_n)_{n \geq 0}$ et en
définissant par récurrence les temps $(\tau_k)$ par $\tau_0=0$
et
\begin{equation}
\label{eq:tauk}
\tau_{k+1} = \max \; \{ n: X_n = X_{\tau_k+1} \} < \infty.
\end{equation}
On obtient alors un chemin $\omega(k) = X_{\tau_k}$ qui est
automatiquement auto-évitant, et la loi de ses $n$ premiers pas
fournit une mesure de probabilité sur $\Omega_n$.

La mesure qu'on obtient ainsi s'appelle la \emph{marche à boucles
effacées}. La construction peut se généraliser à la dimension $2$ en
prenant quelques précautions dues au fait que comme la marche aléatoire
est récurrente, la définition~\eqref{eq:tauk} donnerait
$\tau_k=+\infty$ pour tout $k>0$. On peut par exemple regarder la
marche aléatoire jusqu'à ce qu'elle sorte d'une région fixée.

La mesure qu'on obtient sur $\Omega_n$ n'est \emph{pas} la mesure
uniforme, et on la connaît beaucoup mieux parce qu'elle est intimement
liée à la marche aléatoire simple, qui est extrêmement bien comprise.
Par exemple, en dimension $2$ on sait que $E[\|\omega_n(n)\|]$ se
comporte comme $n^{8/5}$: en comparant cela aux conjectures sur la
marche auto-évitante~(\cf \ref{sec:1132}), l'inégalité $8/5 > 3/2$
signifie que la marche à boucles effacées va plus loin en $n$ pas, et
est donc d'une certaine façon \og plus lisse\fg.

Historiquement la marche à boucles effacées est le premier pour
laquelle une limite d'échelle de type $\mathrm{SLE}$ a été démontrée,
dans l'article~\cite{schramm-UST} où Schramm donne la première
définition du processus qui depuis porte son nom.

\section{Développements en lacets}
\label{sec:lace}

En grande dimension ($d>4$), la marche aléatoire simple est transiente
et il lui devient plus facile d'être déjà auto-évitante à grande
échelle, et de n'avoir que des auto-intersections locales. Il est
alors naturel de conjecturer que la marche simple et la marche
auto-évitante ont le même comportement asymptotique, et c'est en effet
le cas:

\begin{theorem}[Hara, Slade \cite{Slade1987,Hara1992}]
En toute dimension supérieure ou égale à $5$, on a
$E[\|\omega_n(n)\|^2] \asymp n$. De plus, $\omega_n(n)$ satisfait un
théorème central limite: il existe $\sigma_d \in (0,1)$ tel
que
$$n^{-1/2} \omega_n(n) \To{(d)}\mathcal N(0, \sigma_d
I_d).$$
\end{theorem}

La preuve de ce théorème est extrêmement technique, et repose sur la
technique connue sous le nom de \emph{développement en lacets}. Nous
donnons juste ici le point de départ de la construction, dû à Brydges
et Spencer~\cite{Brydges1985}. Considérons la \emph{marche faiblement
auto-évitante} de paramètre $\lambda\in[0,1]$ ($\lambda=0$
correspondra à la marche aléatoire simple, et $\lambda=1$ à la marche
auto-évitante) et de longueur $n$, définie par sa fonction de
partition
$$C(n):= \sum_{\omega \in S_n}
\prod_{0 \leqslant i<j \leqslant n} (1 - \lambda
1_{\omega(i)=\omega(j)}).$$ (On somme bien sur toutes les marches par
plus proches voisins, et pas seulement sur les marches auto-évitantes,
mais la somme se restreint à $\Omega_n$ pour $\lambda=1$.) Posons
$$U_{ij} = - \lambda 1_{\omega(i)=\omega(j)},\quad
E_n = \{ (i,j): 0 \leqslant i < j \leqslant n\}$$ et développons le
produit: on obtient
$$C(n) = \sum_{\omega \in S_n}
\prod_{(i,j)\in E_n} (1+U_{ij}) = \sum_{\omega \in S_n} \sum_{E
\subset E_n} \prod_{(i,j)\in E} U_{ij}.$$ Un peu de terminologie:
on appellera \emph{graphe} une partie $E \subset E_n$ (et~\emph{arêtes} de $E$ ses éléments); \emph{temps de renouvellement} de
$E$ un entier $k \in \lcr 1,n \rcr$ tel qu'aucune arête
$(i,j)\in E$ ne satisfasse aux inégalités \hbox{$i<k<j$}; graphe \emph{primitif} un graphe
sans temps de renouvellement et dont une arête contient $0$; et
\emph{laçage} un graphe primitif minimal pour l'inclusion.

\begin{exercice}
Pourquoi utilise-t-on le mot \og laçage\fg ? (Réponse: voir \cite[p.\,129]{Brydges1985}.)
\end{exercice}

On notera $\bar E_n$ l'ensemble des graphes primitifs, $L_n$
l'ensemble des laçages et $\bar C(x,n)$ la somme précédente restreinte
aux graphes primitifs. Comme tout graphe se décompose en union de
graphes primitifs mis bout à bout, on voit facilement que
$$C(n) = \sum_{k \leq n} \bar C(k)
C(n-k)$$ ce qui permet d'estimer $C$ à partir d'estimées pour $\bar C$
(par exemple par des méthodes de séries génératrices). On se
restreindra par la suite à l'étude de la fonction $\bar C(n)$. Si $E$
est un graphe primitif, on notera $L(E)$ le laçage contenu dans $E$
qui contient le moins d'arêtes:
\begin{align*}
\sum_{E \subset \bar E_n} \prod_{(i,j)\in E} U_{ij} &= \sum_{\ell \in
L_n} \sum_{E: L(E) = \ell} \prod_{(i,j) \in E} U_{ij}\\
&= \sum_{\ell
\in L_n} \prod_{(i,j)\in \ell} U_{ij} \sum_{E: L(E) = \ell}
\prod_{(i,j) \in E} U_{ij}.
\end{align*}
En refactorisant la dernière somme de
l'expression en sens inverse de la première étape du développement de
$\bar C(n)$, on obtient
$$\sum_{E \subset \bar E_n} \prod_{(i,j)\in E} U_{ij} = \sum_{\ell
\in L_n} \prod_{(i,j)\in \ell} U_{ij} \prod_{(i,j) \prec \ell}
(1+U_{ij}),$$ où la notation $(i,j)\prec \ell$ signifie que
$L(\ell \cup \{(i,j)\})=\ell$ (on dit que $(i,j)$ est \emph{compatible
avec $\ell$}). En resommant sur $\omega \in S_n$:
$$\bar C(n) = \sum_{\ell
\in L_n} \bar C(n,\ell) \quad \text{avec} \quad \bar C(n,\ell) =
\sum_{\omega \in S_n} \prod_{(i,j)\in \ell} U_{ij} \prod_{(i,j) \prec
\ell} (1+U_{ij}).$$

La somme définissant $\bar C(n,\ell)$ ne porte que sur des
trajectoires rendant le produit des $U_{ij}$ non nul, autrement dit
sur des marches qui passent au même sommet aux temps $i$ et $j$, pour
chaque $(i,j)\in\ell$, et elle porte un facteur $\lambda^{|\ell|}$.
Par ailleurs, le dernier produit, si on le restreint aux paires
$(i,j)$ qui sont \og sous\fg une arête $(i_0,j_0) \in \ell$, est du même
type que $C(j_0-i_0)$. On peut voir la dernière égalité comme une
équation permettant un calcul de $\bar C(n)$ par récurrence, et qui au
moins en principe contient toute l'information dont on a besoin sur le
modèle.

Si $\lambda$ est assez petit et $d$ assez grand, seuls les premiers
termes contribuent; en rapprochant ce développement de celui obtenu
pour la marche simple (le cas $\lambda\to0$), au bout d'une
cinquantaine de pages on obtient le résultat annoncé. Pour tous les
détails, on pourra se reporter à
\cite{Brydges1985,Hara1992,madras-self}; pour des approches plus
\og modernes\fg, \cite{Bolthausen2001,Bolthausen2015}.

\section{Quelques questions ouvertes}
\label{sec:conj}

\subsection{La marche auto-évitante de longueur infinie}
\label{sec:infty}

Comme on l'a mentionné au début de ce texte, il est facile de définir
une marche aléatoire simple de longueur infinie, et cela permet
d'énoncer les théorèmes limites de manière plus agréable (quand on dit
que $\omega_n/n$ tend vers $0$, il n'y a qu'une suite $(\omega_n)$).

La situation est beaucoup moins claire dans le cas de la marche
auto-évitante: en effet, si $\omega \in \Omega_n$ est choisi avec la
loi uniforme, et si on note
$\omega^{[m]} = (\omega_k)_{0 \leq k \leq m}$ le préfixe de longueur
$m$ de $\omega$ (pour $m < n$), on a bien $\omega^{[m]} \in \Omega_m$
mais sa loi n'est pas du tout la loi uniforme. Cela n'est pas
difficile à voir, par exemple parce qu'il existe dans $\Omega_m$ des
chemins qui n'ont pas d'extension de longueur $n$ (qui sont
\og piégés\fg).

Si on se restreint à des marches auto-évitantes en dimension $2$ et
contenues dans le demi-plan supérieur, la construction suivante est
due à Kesten~\cite{kesten1963,kesten1964a}. Notons $\tilde P_n$ la
mesure uniforme sur les chemins auto-évitants de longueur $n$ contenus
dans le demi-plan, et pour \hbox{$m\!<\!n$}, notons $\tilde P_{m,n}$ la loi de
$\omega^{[m]}$ pour $\omega$ de loi $\tilde P_n$. Comme on vient de le
voir \smash{$\tilde P_{m,n} \neq \tilde P_m$}; mais quand $n\to\infty$
la loi \smash{$\tilde P_{m,n}$} converge vers une mesure de
probabilité $Q_m$ et il est alors facile de voir que si $\omega$ est
de loi $Q_m$ et si $m'<m$ alors $\omega^{[m']}$ est bien de loi
$Q_{m'}$, on dit que la famille de mesures $(Q_n)_{n\geq0}$ est
\emph{compatible}. La convergence elle-même est difficile à prouver,
et repose sur une description précise des chemins en termes de \og ponts
irréductibles\fg.

Le théorème d'extension de Kolmogorov entraîne alors l'existence d'une
mesure de probabilité $Q$ sur l'ensemble des chemins auto-évitants de
longueur infinie dans le demi-plan, qui vérifie la propriété suivante:
pour tout $n>0$, si $\omega$ est de loi $Q$, son préfixe
$\omega^{[n]}$ est de loi $Q_n$.

Si on ne se restreint pas au demi-plan, ou à la dimension $2$, on ne
sait pas en général prouver la convergence de $\tilde P_{m,n}$ quand
$n\to\infty$.

\subsection{Comportement en dimension \texorpdfstring{$2$}{2}}
\label{sec:1132}

Un des avantages de l'existence de la marche auto-évitante de longueur
infinie dans le demi-plan est qu'elle permet de poser la question de
l'existence d'une \emph{limite d'échelle}, qui est la suivante. Pour
tout $\delta>0$ on peut définir la mesure $Q^{(\delta)}$ sur le réseau
$\delta \mathbb Z^2$ dont les arêtes sont de longueur $\delta$. On
peut voir un chemin sur $\delta \mathbb Z^2$ comme un chemin continu
dans le demi-plan supérieur et se demander ce qui se passe quand
$\delta\to0$. Dans le cas de la marche aléatoire simple, on obtiendrait
le \emph{mouvement brownien}, qui est un objet très bien compris.

Si on ne disposait que des mesures en longueur finie, il faudrait
faire tendre cette longueur vers l'infini en même temps que $\delta$
tend vers $0$, pour ne pas obtenir une limite qui soit simplement le
point~$\{0\}$, et comme on l'a vu la façon dont le diamètre de
$\omega_n$ croît avec $n$ n'est pas bien connue.

L'existence de la limite d'échelle de $Q^{(\delta)}$ est une des
questions ouvertes majeures du domaine. D'une certaine façon on sait à
quoi s'attendre, au sens où si on suppose l'existence de cette limite
et sa propriété d'\emph{invariance conforme}, alors il doit s'agir du
processus de Schramm-Loewner $\mathrm{SLE}(\kappa)$ pour
$\kappa = 8/3$. Le problème est que l'on ne dispose essentiellement
d'aucun outil adapté au problème ; essentiellement aucun progrès n'a
été fait sur la question depuis l'introduction du processus
$\mathrm{SLE}$, et le panorama~\cite{werner-saw} est toujours
d'actualité pour plus de détails.

Si on savait prouver la convergence de la marche auto-évitante quand
$\delta\to0$, on obtiendrait des informations précises sur le
comportement des mesures $P_n$ quand $n\to\infty$. Pour en citer deux:
\begin{itemize}
\item On aurait une meilleure asymptotique pour le nombre de marches
auto-évitantes:
\begin{equation}
\label{eq:1132}
c_n \sim C n^{11/32} \mu^n
\end{equation}
pour une certaine constante $C>0$ inconnue et dépendant du choix
particulier du réseau. L'exposant $11/32$ qui apparaît est en
revanche \emph{universel} et ne dépend que du fait que la question
soit posée en dimension $2$. En particulier on obtiendrait une
majoration bien plus précise que celle de Hammerley et Welsh
(\ref{eq:pre}).
\item On en saurait beaucoup plus sur la géométrie de $\omega_n$: en
particulier, on obtiendrait pour le dernier point du chemin
\begin{equation}
\label{eq:diff}
E \big[ \|\omega_n(n)\|^2 \big] = n^{3/2 + o(1)}
\end{equation}
avec à nouveau un exposant qui ne dépendrait que de la dimension.
\end{itemize}

\backmatter
\bibliographystyle{jepplain+eid}
\bibliography{xups16-03}
\end{document}