Keywords:

This thesis focuses on the rapid mixing of graph-related Markov chains.

The main contribution concerns graphs with local edge dynamics, in which the topology of a graph evolves as edges slide along one another. We propose a classification of existing models of dynamic graphs, and illustrate how evolving along a changing structure improves the convergence rate. This is complemented by a proof of the rapid mixing time for one such dynamic. As part of this proof, we introduce the partial expansion of a graph. This notion allows us to track the progression of the dynamic, from a state with poor expansion to good expansion at equilibrium.

The end of the thesis proposes an improvement of the Propp and Wilson perfect sampling technique. We introduce oracle sampling, a method inspired by importance sampling that reduces the overall complexity of the Propp and Wilson algorithm. We provide a proof of correctness, and study the performance of this method when sampling independent sets from certain graphs.

Cette thèse porte sur la rapidité du temps de mélange de chaînes de Markov sur des graphes.

La contribution principale concerne les graphes avec des dynamiques locales sur les arêtes, la topologie du graphe évoluant au fur et à mesure que les arêtes glissent les unes le long des autres. Nous proposons une classification des différents modèles existants de graphes dynamiques, tout en illustrant l'importance des transitions le long d'une structure mouvante pour améliorer la vitesse de convergence. Cette étude est complétée par la preuve, pour l'une de ces dynamiques, d'un temps de mélange rapide. Nous définissons notamment l'expansion partielle d'un graphe. Celle-ci permet de suivre l'avancement de la dynamique, partant d'un état de faible expansion, jusqu'à obtention d'une bonne expansion à l'équilibre.

La fin de cette thèse porte sur une amélioration de l'algorithme de simulation parfaite de Propp et Wilson. Nous introduisant un oracle pour les transitions, inspiré de l'échantillonnage préférentiel, qui permet de réduire la complexité de l'algorithme. Nous fournissons une preuve de correction, ainsi qu'une étude de l'impact de cette méthode sur la vitesse d'échantillonnage d'ensembles indépendants pour certains graphes.

iii Contents 1 Introduction 1 This chapter review concepts and results on Markov chains that will be used throughout the following chapters. It focuses on methods for establishing upper bounds on the mixing time of Markov chains. The end of this chapter is dedicated to presenting the main results of this thesis.

Taxonomy of Dynamic Graphs 21

This survey presents a number of possible models for dynamic graphs, and establishes some classifications based on several design choices. By establishing patterns between known bounds on the mixing time and the features of each dynamic, it gives some insight as to the ingredients that make up a rapidly converging graph dynamic. The key observation is a need for bootstrapped transitions in order to obtain fast mixing with local dynamics.

Rapid Mixing of Local Dynamic Graphs 45

Comprising the main result of this thesis, this section presents a proof of rapid convergence for a specific local graph dynamic. Starting from an arbitrary configuration, the topology of the graph has mixed after only a polylogarithmic number of updates per vertex. This proof introduces the notion of partial graph expansion, which plays an essential role in tracking the evolution of the graph throughout the transient phase.

Oracle Sampling 65

This last section presents an extension of the perfect sampling algorithm by Propp and Wilson. It introduces a method for ignoring unnecessary transitions throughout the simulation, while at the same time compensating for the bias that this approach introduces. The algorithm is given, along with a proof of correctness and case study of its performance when sampling random independent sets over certain graphs.

Je tiens tout d'abord à remercier mes directeurs de thèse : Laurent Massoulié, pour avoir été particulièrement disponible et m'avoir maintes fois conseillé de nouvelles pistes à explorer, et Ana Bušić, pour nos nombreux et enrichissants échanges depuis mes premiers pas chez TREC il y a maintenant six ans.

Ensuite, des remerciements qui se doivent d'être rédigés en anglais. I would like to thank my reviewers, George Giakkoupis and Adrian Kosowski, for taking the time to work their way through this thesis, and for their personal contributions: George and I had a most constructive discussion at the IHP back in 2016, and Adrian provided numerous constructive ideas on how to improve the thesis as a whole. This gratitude extends to Giovanni Neglia and Milan Vojnovic, who immediately accepted to be part of the jury.

Je ne serais pas là sans la contribution de certains professeurs, qui m'ont accompagné depuis de longues années. Je pense notamment à François Baccelli, grâce à qui je me suis intéressé de plus près aux réseaux ; à Marc Lelarge, qui m'a conseillé pour cette thèse ; et à Anne Bouillard, pour son co-encadrement en Master et son suivi régulier. Une mention toute particulière à Ana, Anne et Marc, pour qui j'ai eu la chance d'assurer des TDs à l'ENS durant ces trois années.

La thèse au quotidien, c'est aussi une équipe de recherche. Ou deux. Un grand merci, donc, à tous les membres d'Infine et de Dyogene : Lennart, Christelle, Loïc, Pierre, Rafael, Léo, Raul, Alexandre, Hirah, Bartek, Francisco, Émilie, Guangshuo, Thomas, Cédric, Anastasios, Aline, Paul, Alexandre, Virag, Benoit, Sean, et tous les autres habitués des lieux, qu'ils soient adeptes de la caféine chez SpecFun, fidèles du DLP au SED, ou encore ornithoryncophiles au Lincs. Et comme il n'y pas que des chercheurs, je souhaiterai exprimer ma gratitude envers Isabelle Delais et Hélène Bessin-Rousseau, sans qui cette thèse aurait été un cauchemar administratif.

Les nouveaux collègues, aussi, pour qui VOId est un nom de classe acceptable : Nicolas, Pierre, Ludovic, Mathieu, Richard, Dinh Thai, François, Michel, Vincent, Natalya, Fabien, Marc-Olivier, Serge, Matthews, Nesrine et Imaran.

Une pensée aussi à tous ceux qui ont subi cette thèse en dehors de tout contexte professionnel : l'ATR de chez Connexion Swing, et plus généralement les chroniqueurs du Rémi point ; les aventuriers hauts et courts, hobbits comme chasseurs de géants, qui veulent clairement ma peau ; les adeptes du 41-30 et du squeeze cardiaque ; les fidèles du séminaire de l'Abbé Mole et du C6 ; les planteurs de clous ; les bétonneurs de lemmings ; vous tous. Tenter une liste exhaustive est un pari trop osé pour que je m'y risque, donc voici très officiellement une liste non-exhaustive : les Camomilles, Émilie, Delphine, Sand & Ludo, Audrey, Philippe, VéroNike, Pedro, Chaton, Sam, Chacha, Albin, Iron Man, Pierrot, Karine, SimJay, Marine, Matthieu, Anne, Éric, Silvain, Catherine, Max, Fathi, Marie, David, i Julia, Bastien, Yasmine, Jack, Quentin, Olivier, Baptiste, Adeline, Jean-Baptiste, Adeline, Denise, Ismaël, Igor, Céline, Vincent, Valérie, Vincent, Marie, Nicolas, Benjamin, Christine, Juliette, Iryna.

Un très grand merci à Dominique et Roland pour leurs accueils réguliers en terres volcaniques, à Floriane et Anouk avec qui nous avons parcouru l'Écosse, et à Aymeric et Jordane qui m'ont fait voir les lunes de Jupiter et les anneaux de Saturne. À ma famille aussi : les cousins et petits-cousins, les oncles et tantes, les grands-parents. Patrick, qui travaille tellement dans l'ombre qu'on ne sait pas trop ce qu'il fait ; Estelle, qui suit de si près mes pas que nos discussions font fuir la famille ; et Gabby, sans qui le nid familial eût été injoignable durant tout ce temps. À François, dont les jeux de plateaux indénombrables ne sont sans doute pas pour rien dans mon intérêt pour les graphes, et à Laurence, dont les parties de rail ont changé à tout jamais ma définition du plus court chemin et de la connexité.

Il ne me reste plus qu'à remercier chaleureusement Daphné de sa présence à mes côtés tout au long de ce voyage. [START_REF] Berestycki | Mixing times of markov chains: Techniques and examples[END_REF] Markov chains were introduced at the start of the 20th century by A. Markov [START_REF] Andreyevich | Extension of the law of large numbers to dependent quantities[END_REF], who used them to prove that the weak law of large numbers did not necessarily require independence-the established result is comparable to modern versions of the ergodic theorem-and to study the correlation between successive vowel and consonant occurrences in Russian literature. The scope of Markov chains has since then expanded to domains such as sampling and simulation, the study of dynamic systems, or combinatorial optimization. It is namely the theoretical basis for the acclaimed Markov chain Monte Carlo (MCMC) algorithm. The results presented in Sections 1 to 5 of this chapter are for the most part standard results, that can be found in works such as Markov Chains and Mixing Times [START_REF] Asher | Markov chains and mixing times[END_REF], Reversible Markov Chains and Random Walks on Graphs [START_REF] Aldous | Reversible markov chains and random walks on graphs[END_REF] and Finite Markov Chains and Algorithmic Applications [START_REF] Häggström | Finite Markov chains and algorithmic applications[END_REF]. They are adapted here to best reflect their use in the following chapters.

The main contributions of this thesis are presented in Section 6.

Throughout this chapter, we consider a finite set , which we refer to as the state space.

Markov Chains

A Markov chain is a memoryless stochastic process over a countable state space. The memoryless property, also known as Markov property, establishes that the distribution of the process at any given time only depends on its last known position, and is independent of its trajectory prior to that.

Formally, one defines discrete and continuous time Markov chains as follows.

Definition 1 (Discrete Time Markov Chain). A (discrete time) Markov chain over is a random sequence (X t ) t ∈ ∈ ⊗ that satisfies the Markov property P(X t +1 = x t +1 | X t = x t , . . . , X 0 = x 0 ) = P(X t +1 = x t +1 | X t = x t ).

If P(X t +1 = x | X t = x ) does not depend on t , i.e.

P X t +1 = x X t = x = P X 1 = x X 0 = x ,
the Markov chain is said to be time homogeneous. The transition matrix of a time homogeneous Markov chain is the matrix P such that P (x , x ) = P X 1 = x X 0 = x .

For S ,S ⊆ , it is often convenient to also denote P (S ,S ) =

x ∈S x ∈S P (x , x ).

We have the following analogous definition for the continuous setting.

Definition 2 (Continuous Time Markov Chain).

A continuous time Markov chain over is a process (X t ) t ∈ such that, for any increasing non-negative sequence (t i ) i ∈ and n ∈ , P X t n+1 = x t n +1 X t n = x t n , . . . , X t 0 = x t 0 = P X t n+1 = x t n+1 X t n = x t n and, for all t ≥ 0 and x = x , P(X t +h = x | X t = x ) h converges to a finite value as h goes to 0.

If P(X t = x | X s = x ) = P(X t -s = x | X 0 = x ) for all 0 < s < t , the Markov chain is time homogeneous. We then define the infinitesimal generator of the Markov chain as the matrix Q such that Q (x , x ) = lim t →0 P(X t = x | X 0 = x ) t for all x = x , and Q (x , x ) = -

x =x Q (x , x ).

MARKOV CHAINS

The distributions of time homogeneous Markov chains at time t , starting from state x ∈ , are respectively

P t (x , •) and H t (x , •) = e t Q (x , •)
in the discrete and continuous settings. H t is called the heat kernel of Q . All Markov chains studied in this thesis are time-homogeneous.

A classical example of a Markov chain is the birth and death process detailed below. It is also known as the M/M/1 queue in queueing theory [START_REF] Kendall | Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded markov chain[END_REF].

Example 1 (The Birth and Death Process). Let N ∈ , and consider a group of individuals whose total population evolves between 0 and N over time.

For the discrete setting, we have that, at each time step, either a new individual is born (unless the population count is already N ), or an individual dies. Births occur with probability p ∈ (0, 1), and deaths with probability q = 1p .

Denote (X t ) t ∈ the number of individuals at instant t . (X t ) t ∈ is a time homogeneous Markov chain over = 0, N , and its transition matrix is

P =          q p 0 • • • 0 q 0 p . . . . . . 0 q . . . . . . 0 . . . . . . . . . 0 p 0 • • • 0 q p          .
In the continuous setting, consider instead that births occur at rate λ > 0, and deaths at rate µ > 0. Consider an i.i.d. sequence of random variables (t i ) i ∈ , exponentially distributed with parameter λ + µ., and denote s i = i j =1 t i . Define (X t ) t ∈ as being constant except at instances (s i ) i ∈ , and that at each such instance, either a birth occurs (with probability λ λ+µ ), or a death occurs (with probability µ λ+µ ). The population is once more clamped to 0, N . The infinitesimal generator of this Markov chain is

Q =          -λ λ 0 • • • 0 µ -(λ + µ) λ . . . . . . 0 µ . . . . . . 0 . . . . . . . . . -(λ + µ) λ 0 • • • 0 µ -µ          .
Notice that a discrete time Markov chain is the stochastic equivalent of a sequence defined by a recurrence relation. As such, it is often convenient to define them through a recurrence relation map: Definition 3 (Random Mapping Representation). Let P be a transition matrix over , and θ be a random variable in a set Θ. A random mapping representation of P is a function f : × Θ → such that, for all x , x ∈ , P f (x , θ ) = x = P (x , x ).

Given a random mapping representation f of P , it is possible to define a Markov chain (X t ) t ∈ with transition matrix P recursively as

X t +1 = f (X t , θ t +1 ),
where (θ t ) t ∈ is a sequence of i.i.d. random variables with the same distribution as θ .

In the case of Example 1, a possible random mapping representation would be to have θ be equal to 1 with probability p , -1 otherwise, and f be defined as f (x , θ ) = max(min(x + θ , 0), N ).

While random mapping representations are powerful in expressing the evolution of a Markov chain, they can quickly lead to cumbersome notations:

X 3 = f (f (f (X 0 , θ 1 ), θ 2 ), θ 3 ).
(1.1)

To avoid this pitfall, we make use of an alternate representation: Markov automata [START_REF] Pin | Acceleration of perfect sampling by skipping events[END_REF].

Definition 4 (Markov automaton). Let P be a transition matrix over . Let be a finite set, and D be a distribution over . Finally, let • : × → be a transition function such that, for all x , x ∈ ,

P x • A = x = P (x , x ),
where A is distributed according to D .

The quadruple A = ( , , D, •) is called a Markov automaton. is the alphabet of A, and its elements are referred to as letters or events. A sequence of letters is called a word.

A Markov chain (X t ) t ∈ with transition matrix P can now be defined recursively as

X t +1 = X t • A t +1 ,
where (A t ) t ∈ is a sequence of i.i.d. random events distributed according to D . With this formalism, Equation (1.1) becomes

X 3 = X 0 • A 1 • A 2 • A 3 .
A natural Markov automaton for Example 1 would be

A =    = 0, N = {b , d } D : b → p , d → q • : (x , a ) →      x + 1 if a = b and x < N x -1 if a = d and x > 0 x otherwise    . (1.2)
Finally, a common method of representing both discrete and continuous time Markov chains is by means of a graph.

Definition 5 (Transition graph).

For a transition matrix P over state space , consider the directed weighted graph G = (V , E , w ) where • E = (x , x ) ∈ 2 P (x , x ) > 0 , and

• V = , 0 1 2 • • • N -1 N p p p p p q q q q q q p 0 1 2 • • • N -1 N λ λ λ λ λ µ µ µ µ µ
• w : E → + such that w (x , x ) = P (x , x ).

G is the graph representation of P .

For a continuous time Markov chain with infinitesimal generator Q , the graph representation is defined similarly, but contains no self-loops.

Conversely, given a graph, one can define the Markov chain represented by this graph, called the random walk on the graph. Definition 6 (Random walk). Given a directed weighted graph G = (V , E , w ), define the out-degree of a vertex as the sum of the weights of outgoing edges:

deg + x = x :(x ,x )∈E w x , x .
The discrete time random walk on G is the Markov chain (X t ) t ∈ such that, for every t ∈ , X t +1 is distributed according to

P (X t , •) = w (X t , •) deg + X t .
Similarly, the continuous time random walk on G is the Markov chain (X t ) t ∈ that spends an average time of deg + x = -Q (x , x ) in a state x , then jumps to a new state distributed according to Q (x , •).

In this case of an unweighted graph, the Markov chain is referred to as the simple random walk.

The graph representations of the Markov chains from Example 1 are given in Figure 1.1.

Stationary Distribution

One of the key properties of Markov chains is the existence, in most cases, of a unique stationary distribution, and the convergence of the chain to that distribution. This is the basis for the Monte Carlo sampling method presented in Section 3.

Recall that, throughout this chapter, we restrain ourselves to a finite state space .

Definition 7 (Stationary distribution).

Let P be a transition matrix over . A distribution π, represented as a line vector (π(x )) x ∈ , is said to be a stationary distribution of P if π = πP .

Similarly, a stationary distribution π of an infinitesimal generator Q is one that satisfies 0 = πQ .

Going back once more to Example 1, denoting r = p q and ρ = λ µ , one can easily check that the distributions

π p (k ) = r k 1 -r 1 -r N +1 with π 1 2 (k ) = 1 N +1 and π λ,µ (k ) = ρ k 1 -ρ 1 -ρ N +1 or π λ,µ (k ) = 1 N +1 if λ = µ
are stationary distributions of P and Q , respectively.

To establish the existence and uniqueness of a stationary distribution, and the convergence of the Markov chain to that stationary distribution, the most common approach is to check for irreducibility and aperiodicity.

Definition 8 (Irreducible Markov Chains). Let P be transition matrix over .

If, for all x , x ∈ , there exists t ∈ such that P t (x , x ) > 0, P is said to be irreducible.

An infinitesimal generator Q is irreducible if, for all x , x ∈ , there exists t ∈ such that H t (x , x ) > 0.

Alternatively, a Markov chain is irreducible if its graph representation is strongly connected. Explicitly giving a path between two states is probably the most common method of proving irreducibility.

Property 1. An irreducible transition matrix or infinitesimal generator has a unique stationary distribution.

Note that irreducibility is not necessarily required in order to have uniqueness. The stationary distribution can be unique despite the presence of transient states (i.e. states to which the Markov chain will eventually never return), in which case the transition matrix is not irreducible. Definition 9 (Aperiodic Markov chain). Let P be transition matrix over . For each x ∈ , define the period of x as

T x = gcd t ∈ P t (x , x ) > 0 . P is aperiodic if, for all x ∈ , T x = 1.
For irreducible Markov chains over finite state spaces, this is equivalent to asking that there exists t ∈ such that, for all x , x ∈ , P t (x , x ) > 0.

There is no analog of periodicity for infinitesimal generators. More precisely, for any x , x ∈ , if there exists t ∈ such that H t (x , x ) > 0, then for all s > 0, H s (x , x ) > 0.

Property 2. If the transition matrix P of a Markov chain (X t ) t ∈ is irreducible and aperiodic, then for all x ∈ , lim t →+∞

P(X

t = x ) = π(x ),
where π is the unique stationary distribution of P .

If the infinitesimal generator Q of a Markov chain (X t ) t ∈ is irreducible, then the same convergence holds, with π the unique stationary distribution of Q .

Note that neither of these conditions is very strong. To prove irreducibility, one generally picks a base state and shows that, for any other state, it is possible to reach and be reached by this base state. Constructing such paths is often quite straightforward. Similarly, aperiodicity can be established by finding a single x ∈ such that P (x , x ) > 0. If this is not feasible, it is also possible to consider the "lazy" version of the Markov chain, i.e. given by the transition matrix 1 2 (P + I ), where I is the identity matrix over . Another possibility is to consider a continuous time equivalent of that Markov chain.

In the case of Example 1, any state x can be reached from state 0 with x successive births, and can reach state 0 with x deaths, proving the chain to be irreducible. Furthermore, since P (0, 0) = q > 0, the chain is aperiodic.

For discrete time random walks on bipartite graphs, the period of every state is even; this is a typical example of a situation in which a lazy or continuous time random walk is required in order to have convergence in distribution.

We finish by presenting a specific category of Markov chains, called reversible Markov chains. Property 3. Let P be a transition matrix over , and π be a distribution over . If, for all x , x ∈ , π satisfies π(x )P (x , x ) = π(x )P (x , x ), then π is a stationary distribution of P , and P is said to be reversible.

For an infinitesimal generator Q , we ask that π satisfy

π(x )Q (x , x ) = π(x )Q (x , x ) instead.
Working with reversible Markov chains is often convenient, because the stationary distribution is easily determined (up to a normalization constant).

Note that the Markov chains presented in Example 1 are reversible: for all x ∈ 0, N -1 , we have that

π p (x + 1) π p (x ) = p q = P (x , x + 1) P (x + 1, x ) and π λ,µ (x + 1) π λ,µ (x ) = λ µ = Q (x , x + 1) Q (x + 1, x ) .

Markov Chain Mixing Time

One of the most common uses of Markov chains is the Monte Carlo sampling method, presented in Algorithm 1. It generates random samples from a target distribution π by computing the successive terms of an irreducible aperiodic Markov chain with stationary distribution π, up to a predefined rank T , and returning X T . The distribution of X T can be arbitrarily close to π, provided that T is large enough.

Algorithm 1 Monte Carlo Sampling Algorithm

function MONTECARLO(A = ( , , D, •), x 0 , T ) X ← x 0 t ← 0 while t < T do A ← DRAW(D) X ← X • A t ← t + 1 end while return X end function
How big does T need to be to achieve a desired precision? This is generally determined by computing the mixing time of the Markov chain.

In order to properly define the mixing time, we must first decide upon a metric between distributions. Multiple possibilities have been introduced in the literature, but we will focus on the most common approach: the total variation distance.

Definition 10 (Total Variation Distance). Let µ and ν be two probability distributions over a finite set . The total variation distance between µ and ν is defined as

µ -ν TV = max S ⊆ µ(S ) -ν(S ) .
The right-hand side of this equation is not always easy to use, however, and we therefore often rely on the two following equivalent formulae instead:

µ -ν TV = 1 2 x ∈ µ(x ) -ν(x )
and

µ -ν TV = x ∈ µ(x )≥ν(x ) (µ(x ) -ν(x )).
Definition 11 (Distance to stationarity). For a transition matrix P , the distance to stationarity at time t is defined as

d (t ) = max x ∈ P t (x , •) -π TV .
For an infinitesimal generator with heat kernel H t , this becomes

d (t ) = max x ∈ H t (x , •) -π TV .
An important property of the distance to stationarity (see [START_REF] Asher | Markov chains and mixing times[END_REF], Lemma 4.12) is that, for any c > 0,

d (c t ) ≤ (2d (t )) c .
This implies that, if we know of a t > 0 such that 2d (t ) < 1, then for all ε > 0, by setting

t ε = log ε log(2d (t )) t ,
we have that

d (t ε ) < ε.
Coming back to the Monte Carlo algorithm, we are then able to provide a termination time t ε such that the distribution P t ε (x 0 , •) of the output satisfies

P t ε (x 0 , •) -π TV < ε.
Rather than having the definition of t ε depend on the choice of t , we use a standardized value: Definition 12 (Mixing Time). Let t mix be the first instant at which the distance to stationarity is at most 1 4 , i.e.

t mix = min t > 0 d (t ) ≤ 1 4 .
t mix is called the mixing time of the Markov chain.

We can now redefine t ε as

t ε = log ε log 1 2 t mix = log 2 1 ε × t mix .
Directly computing the mixing time is often not feasible. We present some common techniques used to establish an upper bound instead.

Spectral Methods

One of the fundamental results concerning Markov chains is the following: Theorem 1 (Perron-Frobenius). Let P be a transition matrix, and denote its eigenvalues

λ 1 ≥ λ 2 ≥ • • • ≥ λ | | . • λ 1 = 1,
• P has non-negative left and right eigenvectors associated to λ 1 , and

• every (complex) eigenvalue λ of P satisfies |λ| ≤ 1.

Furthermore:

• if P is irreducible, then λ 1 has multiplicity 1, and • if P is also aperiodic, then every other eigenvalue λ satisfies |λ| < 1.

For an infinitesimal generator Q , let L = -Q be the Laplacian matrix of the Markov chain, and denote its eigenvalues

λ 1 ≤ λ 2 ≤ • • • ≤ λ | | (
notice that the order is the opposite of that for transition matrices).

• λ 1 = 0,

• L has non-negative left and right eigenvectors associated to λ 1 , and

• every (complex) eigenvalue λ of L satisfies R(λ ) ≥ 0, where R(λ ) denotes the real part of λ .
Furthermore, if Q is irreducible, then λ 1 has multiplicity 1, and every other eigenvalue λ satisfies R(λ ) > 0.

Notice that a non-negative left eigenvectors of λ 1 and λ 1 are the (scaled) stationary distribution; this theorem proves the existence of such a distribution for any Markov chain over a finite state space. In both cases, the right eigenvector is necessarily the vector 1 = (1, . . . , 1) T .

The second half of the theorem furthermore proves Properties 1 and 2.

Definition 13 (Spectral Gap and Relaxation Time). The spectral gap is equal to

γ = λ 1 -max λ 2 , λ | | > 0
for an irreducible aperiodic transition matrix P , and

γ = λ 2 > 0
for an irreducible infinitesimal generator Q . The relaxation time is then

t rel = 1 γ .
The relaxation time is closely linked to the mixing time. As such establishing bounds on the spectral gap is a common means of bounding the mixing time.

The relation between t rel and t mix is as follows:

Property 4. (see [START_REF] Asher | Markov chains and mixing times[END_REF], Theorems 12.3 and 12.4) For an irreducible aperiodic Markov chain with stationary distribution π, mixing time t mix and relaxation time t rel . We have that

(t rel -1) log 2 ≤ t mix ≤ t rel × log 4 π min ,
where π min = min x ∈ π(x ) and log denotes the natural logarithm.

Consider the case where π is the uniform distribution over . The above result tells us that the mixing time and the relaxation time differ by at most a factor log | |:

Ω(t rel ) ≤ t mix ≤ O t rel × log | | .
Aside from bounding the mixing time, the spectral gap can also serve to directly bound the distance to stationarity. Property 5 (From [42]). For a reversible Markov chain with spectral gap γ and stationary distribution π, we have that

d (t ) ≤ 1 2 π min e -γt .
Proof. We prove this result in the continuous setting.

Let Q be the infinitesimal generator of the Markov chain, and L = -Q . Denote D = Diag(π), and

A = D 1 2 Q D -1 2 .
Since Q is reversible, A is necessarily symmetric, and can therefore be decomposed as

A = i (-λ i )u i u T i ,
where the u i form an orthonormal basis. Notice that the λ i are precisely the eigenvalues of L , and namely that λ 1 = 0 and u 1 = D 1 2 1. Let h t be the distribution of the Markov chain at time t , i.e. h t = h 0 e t Q .We have that

h t = h 0 D -1 2 e t A D 1 2 = h 0 D -1 2 i e -t λ i u i u T i D 1 2 .
Our goal is to bound

d (t ) = 1 2 x ∈ |h t (x ) -π(x )|. Notice that, for i = 1, h 0 D -1 2 e -t λ 1 u 1 u T 1 D 1 2 = h 0 D -1 2 u 1 u T 1 D 1 2 = 1 × π.
Denoting v T t = h t -π, we therefore have that

v t = D 1 2 i ≥2 e -t λ i u i u T i D -1 2 h T 0 . Let 〈v t , v t 〉 π -1 = v T t D -1 v t .
We can bound 〈v t , v t 〉 π -1 as follows:

〈v t , v t 〉 π -1 = h 0 D -1 2 i ≥2 e -t λ i u i u T i D 1 2 D -1 D 1 2 i ≥2 e -t λ i u i u T i D -1 2 h T 0 = h 0 D -1 2 i ≥2 e -2t λ i u i u T i D -1 2 h T 0 ≤ e -2γt i ≥2 h 0 D -1 2 u i u T i D -1 2 h T 0 = e -2γt i ≥2 D -1 2 h T 0 , u i 2 ≤ e -2γt D -1 2 h T 0 2 2 = e -2γt x ∈ h 0 (x ) 2 π(x ) ≤ 1 π min e -2γt .
We now use the Cauchy-Schwartz inequality to conclude.

d (t ) = 1 2 x ∈ |v t (x )| = 1 2 x ∈ |v t (x )| π(x ) π(x ) ≤ 1 2 x ∈ v 2 t (x ) π(x ) x ∈ π(x ) = 1 2 〈v t , v t 〉 π -1 ≤ 1 2 π min e -γt
Note that this proof works in the discrete setting as well, using P rather than Q . The bound is then

d (t ) ≤ 1 2 π min 1 -γ t ,
from which we derive the same conclusion by observing that, for all x ∈ , 1

-x ≤ e -x .
Direct computation of the spectral gap is not always computationally feasible. There are however a number of practical methods for establishing bounds on the spectral gap. We present one of these: Cheeger's inequality. Definition 14 (Edge measure). The edge measure µ of a Markov chain is defined as the rate at which each edge is traversed under the stationary distribution, i.e. µ(x , x ) = π(x )P (x , x ) for a transition matrix P , and

µ(x , x ) = π(x )Q (x , x )
for an infinitesimal generator Q .

We also denote µ(S ,S ) =

x ∈S x ∈S µ(x , x )
for all S ,S ⊂ .

Definition 15 (Isoperimetric Constant). Let µ be the edge measure of a Markov chain over state space , and π be its stationary distribution. For every set S ⊆ such that S = , define the expansion of S as

φ(S ) = µ(S , \ S ) π(S ) .
The isoperimetric constant of the Markov chain as a whole is

Φ = min 1≤|S |≤ | | 2 φ(S ).
The isoperimetric constant is sometimes referred to as the bottleneck ratio, the Cheeger constant, the conductance, or the expansion ratio.

For the simple, discrete time random walk on a graph G = (V , E ), the isoperimetric constant of a set of vertices S ⊆ V can be rewritten

φ(S ) = |E (S , V \ S )| x ∈S deg x
, where E (S ,S ) is the set of edges between S and S , or even

φ(S ) = |E (S , V \ S )| ∆|S |
for ∆-regular graphs.

For the continuous time simple random walk, we instead have that

φ(S ) = |E (S , V \ S )| |S | .
Property 6 (Cheeger's Inequality [START_REF] Jerrum | Approximating the permanent[END_REF]). Let Φ be the isoperimetric constant of a Markov chain with spectral gap γ. Then

Φ 2 2 ≤ γ ≤ 2Φ.
Combining Properties 4 and 6, we get that

1 2Φ -1 log 2 ≤ t mix ≤ log 4 π min 2 Φ 2 .
Applying this to situations where π min is of order 1 | | (e.g. when π is uniformly distributed), this yields that

Ω 1 Φ ≤ t mix ≤ O log | | Φ 2 .
Note that, if Φ is bounded away from 0, the mixing time is at most logarithmic in the state space. Graphs which possess this property are often referred to as expanders [START_REF] Hoory | Expander graphs and their applications[END_REF].

The Coupling and Path Methods

Another classical method for bounding the mixing time of discrete time Markov chains is the coupling method. First, we give a method for generating coupled Markov chains over a same probability space.

Definition 16 (Grand Coupling). Let A = ( , , D, •) be a Markov automaton with transition matrix P , and (A t ) t ∈ be an infinite random word, i.e. a sequence of i.i.d. random variables distributed according to D . For every x ∈ , denote

X x t = x • A 1 • A 2 • . . . • A t .
The Markov chains in X x t t ∈ x ∈ each have transition matrix P , but are correlated. They are referred to as a grand coupling.

Note that the correlation is such that, for all x , x ∈ and s , t ∈ , s < t ,

X x s = X x s ⇒ X x t = X x t .
The usefulness of grand couplings in bounding the mixing time is a direct consequence of the following result: Property 7. Let P be a transition matrix, and X x t t ∈ x ∈ be a grand coupling of P . Then d (t ) ≤ max

x ,x ∈ P X x t = X x t .

(1.3)

Equation (1.
3) suggests that time it takes for a grand coupling to have all of its trajectories merge must somehow bound the mixing time. We therefore focus on the first instance at which this is the case.

Definition 17 (Coupling time). Let P be a transition matrix, and X x t t ∈ x ∈ be a grand coupling of P . The coupling time τ of the grand coupling is defined as the first instance at which all chains have merged:

τ = min t ∈ ∀x , x ∈ , X x t = X x t .
Note that, unlike the mixing time, the coupling time is a random variable.

Corollary 1. Let P be a transition matrix, X x t t ∈ x ∈ be a grand coupling of P , and τ be the coupling time of X x t t ∈ x ∈ . Then

d (t ) ≤ P(τ ≥ t ),
and, by means of Markov's inequality,

t mix ≤ 4E[τ].
Consider Example 1, with a grand coupling X x t t ∈ x ∈ 0,N defined by the Markov automaton from (1.2). Notice that, for all x ∈ 0, N and t ∈ , X x t ≥ X 0 t . This implies that if, for some t , X 0 t = N , then τ ≤ t . For all x ∈ 0, N , let t x be the first instant at which X x t x = 0, such that τ ≤ t N . Let s x = t xt x -1 . We have that

E[t x ] = 1 + 1 2 E[t x -1 ] + 1 2 E[t x +1 ] ⇒ E[s x ] = 2 + E[s x +1 ] (1.4)
for 0 < x < N , and

E[t N ] = 1 + 1 2 E[t N -1 ] + 1 2 E[t N ] ⇒ E[s N ] = 2.
Summing (1.4) up to x yields that E[s x ] = E[s 1 ] -2(x -1). Substituting for x = N , we get that E[s 1 ] = 2N , and therefore E[s x ] = 2N + 2 -2x . By summing over x :

E[τ] ≤ E[t N ] = N x =1 E[s x ] = N 2 + 3N .
We conclude using Corollary 1:

t mix ≤ 4E[τ] ≤ 4N 2 + 12N = O N 2 .
On a side note, notice that, unlike what one might expect, X x τ is not distributed according to the stationary distribution of the Markov chain, since its value is either 0 or N .

A similar technique can be used for continuous-time Markov chains. This is best achieved by means of a uniformization [START_REF] Grassmann | Transient solutions in markovian queueing systems[END_REF] of the Markov chain, and by coupling the resulting discrete time Markov chain and Poisson process.

We give one final technique, similar to coupling, for bounding the mixing time of discrete time Markov chains. It is used to compare the spectral gaps of two Markov chain, effectively bounding one with the other.

Consider two irreducible and aperiodic Markov chains over a same state space . We denote their transition matrices P and P , and their stationary distributions π and π. The aim is to establish a lower bound on the spectral gap γ of P , knowing the spectral gap γ of P .

In order to de this, we decompose every transition of P as a sequence of transitions of P , called paths. Formally, let E (resp. Ẽ ) be the set of edges e = (x , x ) ∈ 2 such that P (x , x ) > 0 (resp. P (x , x ) > 0). For every ( x , x ) ∈ Ẽ , we choose a path Γ ( x , x ) = (x 0 , x 1 , . . . , x k ) ∈ such that:

• x 0 = x and x k = x , and

• for all i ∈ 1, k , (x i -1 , x i ) ∈ E .
For Γ = (x 0 , x 1 , . . . , x k ), we denote |Γ | = k , and write that e ∈ Γ if there exists i ∈ 1, k such that e = (x i -1 , x i ).

Given this set of paths, let the congestion ratio be

B = max e ∈E    1 µ(e ) ẽ ∈ Ẽ Γ ẽ e μ( ẽ )|Γ ẽ |    .
Property 8 (See [START_REF] Asher | Markov chains and mixing times[END_REF], Theorem 13.23). Given the above setup, we have that

γ ≥ min x ∈ π(x ) π(x ) B -1 γ.
The efficiency of this method relies heavily on the ability to construct an efficient set of paths: these must be kept short, and be distributed evenly over E .

Contributions

In this thesis, we present three main contributions: a generalization of Cheeger's inequality to partial isoperimetric constants; a proof of rapid mixing for a given local edge dynamic, and an enhancement of the Propp and Wilson perfect sampling technique.

Partial Isoperimetric Constants

Consider a simple, continuous time random walk over a multi-graph G = (V , E ), and let N = |V | and ∆ be the maximum degree of G . Definition 18 (Partial Isoperimetric Constants). Let k ∈ 1, 1 2 N . The k -th partial isoperimetric constant of G is

Φ k = min 1≤|S |≤k φ(S ).
In particular, Φ N 2 = Φ. We have seen that, by using Cheeger's inequality, we can bound the spectral gap using the isoperimetric constant. Using Property 5, we can then use this to bound the distance to stationarity. The following result shows how it is possible to directly use the partial isoperimetric constants to bound the distance to stationarity over small sets.

Theorem 2 (Reformulated from Theorem 9). For all k ≤ N 2 and S ⊂ V such that

|S | ≤ k , H t (•,S ) ≤ |S | k + 1 + k + 1e -γ * t , where γ * = 1 2∆ Φ 2 k .
For comparison, combining Properties 5 and 6 gives the following result for the continuous time simple random walks:

H t (•,S ) ≤ |S | N + N e -γt with γ ≥ Φ 2 2 .

Rapid Mixing of a Local Edge Dynamic

We consider graphs in which the edge sets evolve over time, forming a Markov chain (X t ). Such dynamics are presented extensively in Chapter 2. We focus primarily on local dynamics, i.e. in which every modification affects only a small, connected portion of the graph. Most dynamics we shall consider converge to the uniform distribution, under which Φ is bounded away from 0 with probability 1o (1). This may not be the case for the initial state, however, for which Φ could be of order 1 N . The question this raises is the following: can the mixing time of the graphvalued Markov chain be small, despite the poor initial conditions? Namely, can mixing occur with only a O (polylog N ) updates per edge, where O (polylog N ) = O (log k N ) for some fixed k ?

We give a specific dynamic, represented in Figure 1.2, for which we prove this to be the case. The vertex set is denoted [N ] = 1, N , and the edge set is split into three: a set

E • = {(x , x + 1) | x ∈ [N ]}, with N +1 ≡ 1, that forms a static cycle; a set of blue edges E b = {(x , b x ) | x ∈ [N ]}; and a set of red edges E r = {(x , r x ) | x ∈ [N ]},
with b and r two permutations that evolve over time. The blue and red edges are called pointers, in the sense that one of their endpoints, referred to as their The dynamic proceeds through alternating blue and red phases. In essence, edges of the active phase with adjacent destinations will repeatedly swap their destinations over time.

During a blue phase, only blue edges move, and red edges are static. Every static edge (y , y ) ∈ E • ∪ E r maintains an exponential clock with rate 1; at every tick, the two blue edges (x , b x = y ) and (x , b x = y ) are replaced with (x , y ) and (x , y ). This boils down to applying the transposition (x , x ) to b .

When the blue phase ends and the red phase begins, the roles of the red and blue edges are reversed. The dynamic is illustrated in Figure 1 We prove the following result for this dynamic: Theorem 3 (Adapted from Theorem 8). Let T = log a N where a > 8 is a constant. After log 2 N phases of length T , with high probability, the sets of blue and red pointers are uniformly and independently distributed permutations over the symmetric group S N .

This in turn gives that the number of modifications per edge required to mix is polylogarithmic in N , as stated in Corollary 2.

Oracle Sampling

Coupling from the past (CFTP) is a perfect sampling algorithm introduced by Propp and Wilson in 1996 [START_REF] Gary | Exact sampling with coupled Markov chains and applications to statistical mechanics[END_REF]. To perform well, it requires the use of monotonous Markov chains or bounding chains [START_REF] Huber | Perfect sampling using bounding chains[END_REF]. The details of these different approaches are given in Chapter 4.

In this thesis, we present an improvement of this algorithm, based on bounding chains.

Definition 19 (Bounding Chain). Let A = ( , , D, •) be a Markov automaton. A bounding chain for A is a pair ( , •) such that is a subset of the power set of , and • : × → is such that, for all a ∈ , x ∈ and B ∈ ,

x ∈ B ⇒ x • a ∈ B • a .
The usual bounding chains method is presented in Algorithm 2.

Algorithm 2 Coupling From the Past with Bounding Chains

function BOUNDEDCFTP(A = ( , , D, •), ( , •)) k ← 1 U ← ε Initialize with the empty word B ← repeat V ← DRAW(D ⊗k ) Draw a k letter prefix V U ← V U Prepend V to U B ← • U Compute the bounding chain k ← 2k Double the period until |B | = 1 return UNIQUEELEMENTOF(B ) end function
The key feature in our approach is the ORACLESAMPLE function. First, introduce a new letter, , such that

∀x ∈ , x • = x and ∀B ∈ , B • = B.
For every p ∈ (0, 1), let D p be the distribution such that D p ( ) = p and, for all a ∈ , D p (a ) = (1p )D (a ).

Let p ∈ (0, 1) and + ⊆ . ORACLESAMPLE(p , + ) returns a random letter, distributed according to D p conditioned on being in + .

For every bounding state B ∈ , define the set of active letters in state B as

B + = {a ∈ A | B • a = B } ∪ .
We propose Algorithm 3. The structure is similar to that of the previous algorithm. It differs in regards to how the prefix is generated (DRAWPREFIX) and prepended to the previous word (UPDATE).

DRAWPREFIX constructs a prefix in which only active letters appear. This requires computing transitions at the same time as the letters are drawn. Notice that, if every letter are always active, the expected length of DRAWPREFIX(k ) is 2 k , mimicking the period doubling of the base algorithm.

UPDATE is somewhat trickier. It modifies the word from the previous iteration, to which the prefix is to be prepended, so that the final word is also composed of Algorithm 3 Coupling From the Past with Oracle Sampling

function ORACLECFTP(A = ( , , D, •), ( , •)) k ← 1 U ← ε B ← repeat (V , B ) ← DRAWPREFIX(k ) (U , B ) ← UPDATE(U , k -1, B , B ) U ← V U k ← k + 1 until |B | = 1 return UNIQUEELEMENTOF(B ) end function function DRAWPREFIX(k ) V ← ε B ← repeat A ← ORACLESAMPLE(2 -k , B + ) V ← V A B ← B • A until A = return (V , B ) end function function UPDATE(U , k , B , B ) if k = 0 then return (ε, B ) end if A ← ORACLESAMPLE(2 -k , B + ∪ B + ) if A ∈ B + then return A UPDATE(U , k , B , B • A) end if H ← HEAD(U ), T ← TAIL(U ) H is the first letter of U , T is the rest of U if H = then return UPDATE(T, k -1, B , B ) else if H ∈ B + then return H UPDATE(T, k , B • H , B • H ) else return UPDATE(T, k , B • H , B ) end if end function
only active letters. At the same time, it introduces new letters in such a way as to produce an unbiased output.

These operations are detailed in depth in Chapter 4. We also prove the correctness of the algorithm. More specifically, we show the following result.

Theorem 4 (Transcribed from Theorem 12). If there exists u ∈ * such that •u is a singleton, then 1. ORACLECFTP terminates in finite expected time.

2. The output of ORACLECFTP distributed according to π, the stationary distribution of A.

Along with the proof of this result, we give some indications as to how to bound the running time of the algorithm. We also provide some experimental results for generating random independent sets from a graph.

Chapter 2

Taxonomy of Dynamic Graphs

Introduction

Dynamic graphs have received a large amount of interest over the past years, in great part due to the central role they play in the design and analysis of distributed networks. This is especially true in fields such as social networks and communication infrastructures akin to peer-to-peer networks, but also in other domains, including biochemistry and statistical physics.

The resulting models have led to a better understanding of some key observations of real-world networks. Notorious examples include the power-law degree distribution [START_REF] Albert | Statistical mechanics of complex networks[END_REF], the small-world property [START_REF] Watts | Collective dynamics of "smallworld" networks[END_REF], and high clustering [START_REF] Holland | Transitivity in structural models of small groups[END_REF]. This has served as a basis for the analysis and optimization of common algorithms such as gossiping [START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF][START_REF] Giakkoupis | Tight bounds for rumor spreading with vertex expansion[END_REF] and load balancing [START_REF] Sauerwald | Tight bounds for randomized load balancing on arbitrary network topologies[END_REF].

For the most part, research has been aimed at designing efficient algorithms for constructing a target topology. This approach is most common for distributed communication networks, such as peer-to-peer networks, in which the geometry of the overlay network plays a crucial role. In [START_REF] Aspnes | Skip graphs[END_REF], for example, the authors consider the Skip Graph data structure for improving the resiliency of peerto-peer queries in a faulty environment, and [START_REF] Jacob | A distributed polylogarithmic time algorithm for self-stabilizing skip graphs[END_REF] gives an efficient distributed algorithm for constructing such structures. Such studies often make the implicit assumption that the network nodes are cooperative and follow a consensual strategy.

Conversely, non-committed dynamics, in which the evolution of the system is not specifically engineered to favor any given feature, have also had their share of attention. These serve to justify the observed properties of networks with unspecified evolutions, such as social networks. In this situation, dynamics are often presented as naturally-arising Markov chains over a broad set of admissible graphs (e.g. the set of connected graphs over N vertices). This is namely the case in [START_REF] Bhamidi | Mixing time of exponential random graphs[END_REF], which considers a Glauber dynamic over the set of connected graphs with a natural bias in favor of triangles and other small connected subgraphs. Another notable example is [START_REF] Allen Zhu | Expanders via local edge flips[END_REF], which focuses on local edge flips over ∆-regular graphs, and proves that such a dynamic converges in O (n 2 ∆ 2 log n ) iterations. It is worth mentioning that with this dynamic, the limit distribution is the uniform distribution over ∆-regular graphs, which is known give expanders with high probability.

Regardless of the nature of the dynamic, most studies aim to better understand the causality between the local characterization of the model, i.e. the dynamic, and its consequences on a global scale.

The survey This chapter aims to give the reader an overview of different possible models for dynamic graphs. It focuses on simple, randomized dynamics which yield the usual global properties one has come to expect: power-law degree distribution, small-world phenomenon, good expansion, etc.

Section 2, the Zoo, introduces a wide range of dynamics. The aim is twofold: to present the different parameters that can be adjusted when choosing the dynamic that best suits ones needs, and to familiarize the reader with the consequences such dynamics have on the global topology of the graph. Sections 3.1 and 3.2 then take this a step further. In Section 3.1, dynamics are studied at a microscopic level, grouping design decisions together to form genotypes. This is complemented by Section 3.2, in which recurring macroscopic features are categorized as phenotypes. Finally, Section 4 states a number results concerning the mixing time of a selection of models from Section 2. The aim is to give some insight as to the impact of the choice of the dynamic on the convergence rate of the resulting dynamic graph, further bridging the gap between genotypes and phenotypes.

The Zoo

In this section, we present a wide variety of dynamic graphs. Note that, throughout this work, we only consider graphs over a fixed vertex set of size N ; the study of dynamic vertex sets falls outside of the scope of this paper. In a similar manner, we do not always require graphs to be simple: the appearance of multi-edges and self loops is demeed acceptable in most situations. Should the reader wish to enforce such a property, most of the dynamics presented here can be easily adapted (for example via rejection sampling) so as to satisfy that constraint.

The Erdős-Rényi Dynamic

The Erdős-Rényi random graph [START_REF] Erdős | On the evolution of random graphs[END_REF] is widely accepted as the simplest model of random graphs. We present here what we believe to be its dynamic counterpart.

Given an undirected simple graph G = (V , E ) and a fixed parameter p in ]0; 1[, the dynamic is the following: Choose two vertices x and y uniformly and independently at random in V . With probability p , add (x , y ) to E (if the edge was already there, do nothing), otherwise remove (x , y ) from E (likewise, if the edge was already absent, do nothing). Applying this dynamic over and over again yields a Markov chain whose stationary distribution is the alternate Erdős-Rényi distribution (N , p ).

x y G 1 x y G 2 P G 1 ,G 2 = 2 N (N -1) p P G 2 ,G 1 = 2 N (N -1) (1 -p ) Transition probabilities Figure 2.1 -The Erdős-Rényi Dynamic
This dynamic can easily be modified to converge to the original Erdős-Rényi distribution, (N , M ), i.e., the uniform distribution over graphs with N vertices and M edges. This is achieved by selecting not only x and y uniformly at random, but also an independent uniform edge e in E . If (x , y ) is an edge, do nothing, otherwise remove e from E and add (x , y ) in its place.

On a final note, recall that, in order to obtain a connected graph with high probability, p should be at least

(1+ε) log n n
for some positive ε [START_REF] Erdős | On the evolution of random graphs[END_REF].

Exponential Random Graphs

This model, studied thoroughly in [START_REF] Bhamidi | Mixing time of exponential random graphs[END_REF], is similar to the (N , p ) model in that, at each iteration, an edge is chosen uniformly at random, and either added to or removed from the graph. Rather than fixing a probability p of including the edge, however, the chances of accepting the new edge depend on its impact on the local graph structure. Formally, consider a finite set of small graphs (g i ) i ∈I , called configurations. The most common configurations include the edge (2-clique) and the triangle (3-clique). Each configuration is furthermore assigned a weight α i . For all i ∈ I , denote c i (G ) the number of occurrences of g i in G , and define the energy of the graph as

H (G ) = i α i c i (G ).
When updating edge e , denote G e + and G e -the graphs consisting of G with and without edges e , respectively, and

∂ e H (G ) = H (G e + ) -H (G e -).
The probabilities of including e or not are (G ) .

P(include e ) = e ∂ e H (G ) 1 + e ∂ e H (G ) , P(exclude e ) = 1 1 + e ∂ e H
Note that computing ∂ e H (G ) can be achieved by only enumerating the number of occurrences of configurations that contain edge e . As such, if all configurations have diameter at most δ, than these probabilities can be computed by considering only the ball of radius δ around edge e .

The stationary distribution is then

π(G ) = 1 Z e H (G ) ,
where Z is a normalization constant, called the partition function. These type of distributions and update rules are respectively referred to as Gibbs measures and Glauber dynamics.

Pointer Models for Peer-to-Peer and Social Networks

Consider a model in which every node maintains a fixed number of outgoing edges, called pointers, which it updates over time. In this model, each edge has one fixed extremity, its source, and one dynamic end, its destination. Also, whereas every node is the source of a fixed number of edges, it can serve as a destination for a varying number of these. Note that, despite pointers having an

2. THE ZOO x y G 1 x y G 2
Consider g 1 to be the edge graph and g 2 the triangle graph. This structure naturally arises in peer-to-peer networks, where every client maintains a limited number of connections that it then manages on its own. The overall layout of the network is thus constructed in a distributed manner. The same is true in social networks, where individuals have a certain budget of attention [START_REF] Jiang | How to Optimally Allocate Your Budget of Attention in Social Networks[END_REF], which they must distribute amongst their contacts.

∂ e H (G ) = α 1 + 2α 2 P G 1 ,G 2 = 1 M e α 1 +2α 2 1 + e α 1 +2α 2 P G 2 ,G 1 = 1 M 1 1 + e α 1 +2α 2 Transition probabilities
Regarding the dynamic, a uniformly distributed pointer (x , p x ) is updated at each time step. Its new destination p x is chosen according to a distribution P , which depends on the current configuration of graph. Generally, the probability P (x , p x , p x ) of the destination going from p x to p x is a function of the degree of p x in the graph; if it decreases with the degree, then the stationary distribution will tend to have a balanced degree distribution, whereas if it increases with the degree, the asymptotic degree distribution is likely to be exponential.

If P is the uniform distribution over the vertices, then the destination of each edge is uniformly distributed under the stationary distribution, and the overall inbound degree distribution is a multinomial with parameters M and N , where M is the total number of edges. The inbound degree of a given vertex is therefore asymptotically a Poisson random variable of parameter M N . This model can be extended by having each node maintain a dynamic number of pointers, rather than keeping a fixed number of these.

Sliding Edges

In the previous models, our edge update rules rely on the fact that the global structure of the graph is known, and namely that the vertex set is accessible. This is often too strong of an assumption, however, which this fourth model aims to For any graph G and vertex x , denote N G (x ) the set of neighbors of x in G , and deg G (x ) = |N G (x )| its degree. The dynamic is as follows: choose an oriented edge (x , y ) uniformly at random, and replace it with an edge (x , y ), where y is chosen uniformly at random over N G (y ) ∪ {y } \ {x }, i.e., the set comprising y and its neighbors, x excluded. With this policy, the updated edge need only know its local surroundings to change its target.

x p x p x G 1 x p x p x G 2 P G 1 ,G 2 = 1 M 1 N P G 2 ,G 1 = 1 M 1 N Transition probabilities
x y y G 1 x y y G 2 P G 1 ,G 2 = 1 2M 1 deg G 1 (y ) P G 2 ,G 1 = 1 2M 1 deg G 2 (y ) Transition probabilities Figure 2.

-Sliding Edges

The stationary distribution for this dynamic is of the form

π(G ) = 1 Z x ∈V deg G (x )!
This gives an exponential degree distribution. Other distributions can be obtained by drawing y according to a non-uniform distribution P over N G (y ) ∪ {y } \ {x }, as in the previous model. For example, take

P (y ) = 1 deg(y ) -1 1 deg(y )
for every y ∈ N G (y ) \ {x }, and

P (y ) = 1 - y ∈N G (y )\{x } P (y ).
The first factor in the expression of P (y ) consists in choosing y uniformly as before, but the second factor indicates that the transition is only accepted with a probability inversely proportional to the destination's current degree. Using the distribution P rather than the uniform one at each iteration gives a dynamic whose stationary distribution is uniform over all regular connected graphs with the same number of edges.

The Interchange Process

The previous model can furthermore be adapted to preserve the degrees of individual vertices. This can for in particular be used to construct a dynamic over the set of ∆-regular graphs, in which case we refer to this dynamic as the ∆-regular interchange process.

The transition differs in that rather than having one edge slide along another, two edges are moved along a third one, in opposite directions. Formally, chose an edge (y , y ) uniformly at random, and some neighbors x and x of y and y respectively, chosen uniformly at random (y and y excluded). Replace the edges (x , y ) and (x , y ) by (x , y ) and (x , y ). If either of these edges was already present in the graph, you can choose to systematically accept or refuse the change, respectively allowing for or preventing multi-edges and self-loops.

A simplified version of this dynamic, the non-local interchange process, is obtained by sampling (x , y ) and (x , y ) uniformly at random, without requiring that y and y be neighbors. Both of these dynamics have been widely studied [START_REF] Cooper | The flip markov chain and a randomising p2p protocol[END_REF][START_REF] Feder | A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks[END_REF][START_REF] Allen Zhu | Expanders via local edge flips[END_REF][START_REF] Mahlmann | Peer-to-peer networks based on random transformations of connected regular undirected graphs[END_REF][START_REF] Mahlmann | Distributed random digraph transformations for peer-to-peer networks[END_REF], often referred to as the flip (local) and switch (non-local) dynamics.

This simple dynamic converges to the uniform distribution over the set of connected graphs with the degree distribution of the original graph.

Static Structures

One of the inherent risks of local dynamics is the loss of connectivity. The locality constraint implies that, in such cases, this connectivity cannot be restored.

A possible enhancement to the previous models is the use of static edges, i.e., edges which are never moved. By choosing these edges so that they alone We now give a sample dynamic based on a static structure. Consider that V = {1, 2, . . . , N } to ease notation, and that the edges are partitioned into a static ring R = {(i , i + 1) | i ∈ V }, with N +1 ≡ 1, and a dynamic set

y x y x G 1 y x y x G 2 P G 1 ,G 2 = 1 M (∆ -1) 2 P G 2 ,G 1 = 1 M (∆ -1) 2
C σ = {(i , σ(i )) | i ∈ V },
where σ is a permutation over V . The dynamic, thoroughly studied in [START_REF] Debray | Temps de mélange de processus de markov distribués sur des graphes réguliers[END_REF], is the following: choose a static edge (i , i + 1) uniformly at random, and denote τ σ(i ),σ(i +1) the transposition of σ(i ) and σ(i + 1). Replace C σ with C σ , where

σ = σ • τ σ(i ),σ(i +1) .
As always for such symmetric dynamics, the stationary distribution is the uniform distribution.

THE ZOO

i i + 1 σ(i + 1) σ(i ) G 1 i i + 1 σ (i + 1) σ (i ) G 2 P G 1 ,G 2 = 1 N P G 2 ,G 1 = 1 N Transition probabilities

Dynamic Triangulations

This last dynamic somewhat differs from the previous ones in that it deals with planar graphs, namely triangulations. The proposed update scheme converges to the uniform distribution over all triangulations over N vertices. At each iteration, an edge (x , y ) is chosen uniformly at random. Denote u and v the two vertices such that (x , y , u ) and (x , y , v ) are faces of the triangulation. Remove (x , y ) from the set of edges, and replace it with (u, v ). The resulting graph is still a triangulation.

x y G 1 u v G 2 P G 1 ,G 2 = 1 M P G 2 ,G 1 = 1 M Transition probabilities Figure 2.

-Planar Triangulations

This dynamic converges to the stationary distribution over the set of planar triangulations over N vertices.

Genotypes and Phenotypes

The examples from the previous section outline the need for a formal description of dynamic graphs. This could then allow us to classify these models, and possibly identify classes over which certain properties can be generalized. Such descriptions often fall in one of the following two categories.

• On the one hand, those that describe the nature of the dynamics themselves, i.e., the set of rules which dictate the evolution of the graph. These often operate at a microscopic level, around a single vertex or edge, and form what we hereon refer to as the graph's genotype.

• On the other hand, there is the set of macroscopic properties of the graph, which do not define the dynamic as such, but a rather a consequence of the microscopic evolution. These form the graph's phenotype.

Genotypes can include things like fixed vertex degrees, static edges and interchange dynamics, whereas phenotypes refer to properties such as a uniform stationary distribution, degree power laws and mixing times.

We still consider that all our dynamics operate over graphs with N vertices and, for fixed edge counts, M edges.

Genotypes

A dynamic graphs genotype is primarily defined by the nature of its vertices, its edges and its transitions.

Vertices

As we limit our study to the case of graphs over fixed vertex sets, describing the evolution of vertices is quite straightforward.

Fixed degrees

This category encompasses all dynamics where individual vertices' degrees are fixed. A typical example would be the ∆-regular interchange process, and most dynamics that fall under this heading make use of some variation of the interchange process to preserve degree distributions.

Non-homogeneous degrees

Whereas most dynamics make no distinction between different vertices, taking only into account their degrees, some models partition the vertex sets into subsets with differing behaviors. In social networks, for example, studies often distinguish between content creators, relayers and consumers, each with their distinct behavioral patterns. This is the basis for models with underlying communities. Note that this partition can be replaced with continuous properties, such as different probabilities of accepting new neighbors, differing affinities for a set of features, etc.

Underlying geometry Some dynamics have their vertices embedded inside a metric space, which allows for defining dynamics with attraction or repulsion phenomena: edges can be more or less likely to link two given vertices depending on their embedded positions.

Edges

The nature of edges is somewhat richer than that of vertices, namely because they form the dynamic component of the graph.

Fixed edge count vs. birth-and-death One of the major distinctions between dynamics is the edge count. With fixed edge counts, the dynamic moves edges around, and it is often possible to map edges before the transition to edges after it. With unconstrained edge counts, edges can also be added and removed, and one quickly loses the ability to track individual edges.

Static edges, dynamic edges and pointers

In the case of a fixed edge count (typically when moving edges around), one can distinguish between three types of edges:

Static edges, with two fixed ends, Pointers, with one fixed end and one dynamic extremity, and Dynamic edges, with two dynamic extremities.

These edges generally serve very distinct roles and carry different implications: static edges serve as a base structure over which the dynamic unfolds; pointers are maintained by a source vertex, allowing for vertexdriven dynamics; finally, dynamic edges cover a larger scope than pointers, but are also harder to keep track of, and therefore to analyze and interpret.

Multi-graphs

Simple graphs are often more convincing by nature, as it is not always clear how multi-edges and self-loops should be interpreted. Nonetheless, multi-graphs can be easier to manipulate from a mathematical standpoint. The passage from multi-graphs to simple graphs can often be achieved by simply rejecting transitions which would violate the structural constraints.

Oriented edges

The use of oriented edges can have an important impact not only on dynamics, e.g. by allowing sliding edges to follow other edges in only one direction, but also on macroscopic considerations, such as connectivity and expansion.

Labeled edges Just as vertices can differ in nature, edges need not all be identical. A graph can contain multiple edge sets, each with their own dynamic. These dynamics can naturally be linked, for example by imposing that two edge sets never cover a same vertex, that edges never slide along other edges of the same set, or by changing the nature of an edge during a transition.

Transitions

While the possibilities for designing transitions are near endless, certain recurrent patterns can be identified.

Local vs. non-local

Looking at the examples from the previous section, there is a clear distinction between dynamics which operate in a localized portion of the graph, and others which can span the entire graph. Formally, we say a dynamic is local if their exists a fixed integer r such that, for every transition from a state G 1 to a new state G 2 , there exists a vertex x that satisfies

G 1 \B r G 1 (x ) = G 2 \B r G 1 (x ), where B r G (x ) is the ball of radius r centered on x in G . x G 1 x G 2 G 1 \ B 2 G 1 (x ) = G 2 \ B 2 G 1 (x )
The dynamic is local Half-edge transitions When moving an edge, some common dynamics keep one extremity of the edge unmodified. It is often more practical to model these dynamics as operating on half-edges, i.e., a single edge extremity, rather than on full edges. Dynamics dealing with pointers naturally fall under the scope of this definition, whereas edge additions or removals never do.

With each half-edge attached to a single vertex, the set of half-edges at a given vertex can be represented as a set of labels; transitions can then be interpreted as moving these labels.

Sliding edges Amongst local dynamics, sliding edges are possible the most natural approach. These are half-edge transitions in which the original and updated vertices to which the half-edge is attached are linked by another edge. The modified half-edge effectively slides along this other edge.

Interchanging edges

The interchange process is the adaptation of halfedge transitions to graphs with fixed degree distributions: rather than move a single half-edge, select two of these and swap their positions. If these two vertices are guaranteed to always be connected by yet another edge, as is the case for sliding edges, than this dynamic is local. The most common occurrence is the ∆-regular interchange process detailed in the previous section.

Degree-dependant transitions

As shown in some of the examples from the previous section, it is often possible to tinker with a given dynamic through accepting or rejecting simple transitions. The most common decision factor is the respective degrees of the intervening vertices. This is a recurrent means of adapting dynamics to a given target distribution.

Update distribution

All of the update mechanisms presented in the previous section share a common aspect: at each iteration, one starts by selecting one or more edges or vertices at random, often following a uniform distribution. This initial decision of what to update plays a crucial role in reversibility.

Another essential role of the update distribution is when considering continuous time equivalents of the dynamics presented here. For a dynamic where edges were chosen uniformly at random, an exponential timer is now associated to each edge, and a transition occurs when that timer expires. For dynamics based on uniformly distributed vertices, the timers are placed on the vertices. Choosing the right expiration rate for vertex timers is primordial in order to ensure the reversibility of these continuous time dynamic graphs.

Combinatorial updates

To finish, some dynamics rely on some form of combinatorial structure underlying the edge set. This was the case for the example comprising a static ring and a permutation. Such structures imply additional constrains on dynamics, and should be considered with care.

They furthermore highlight an important caveat in our definition of local dynamics. Consider the following model: a graph consisting of a static ring and a cycle {(σ(i ),

σ(i + 1) | i ∈ {1, 2, • • • , N }}, with N + 1 ≡ 1.
The dynamic consists in selecting an vertex i uniformly at random, then setting

σ 2 = 1 2 ••• σ -1 1 (i ) σ -1 1 (i )+1 ••• σ -1 1 (i +1)-1 σ -1 1 (i +1) ••• N σ 1 (1) σ 1 (2) ••• i σ 1 (σ -1 1 (i +1)-1) ••• σ 1 (σ -1 1 (i )+1) i +1 ••• σ 1 (N ) .
As one can see on Figure 2.10, this dynamic is local according to our definition (everything outside of B 2 G 1 (i ) is unaltered), yet a global update of the permutation is required.

Phenotypes

The phenotype of a dynamic graph is the set of global properties of the dynamic that one can quantify. It results from the choice of the genotype, and the later can often be retro-engineered to achieve certain global properties.

Stationary Distribution

The most common question when studying a Markov chain certainly consists in determining if it converges to a stationary distribution, and what that distribution might be. In every example from Section 2, the dynamic is reversible, which immediately answers the question. The most common application is with ergodic Markov chains for which we have P i , j = P j ,i for all pair of states i and j ; their stationary distribution is then necessarily the uniform distribution over the state space. This applies to most of our examples. For the others, checking that the stated distribution satisfies the detailed balance equation suffices.

1 2 i i + 1 G 1 1 2 i i + 1 G 2 σ G 1 = 1 2 3 4
The stationary distribution in itself is also often studied, though this falls somewhat outside of the scope of this survey. The following properties are often considered:

Degree Distribution Depending on the interpretation given to a dynamic, the desired degree distribution may vary. This includes things such as exponential distributions for online social networks and global communication networks, balanced distributions for local communication networks such as sensor networks, or even constant degrees, as with peer-to-peer networks.

Edge Count Distribution Most dynamics deal with sparse graphs, in which the number of edges, M , is quasi-linear in the number of vertices N : M = O (N log k N ) for some fixed integer k . Controlling this distribution is therefore essential when constructing a model.

Note that, in the case of dynamics with a fixed edge count, the question is dealt with from the start. This property is therefore mostly relevant for dynamics with a variable edge count.

Stationary Expansion

Expansion is an important aspect of network models.

It is a useful indicator of how well information travels in graphs, and is essential in studying epidemic propagation, rumor spreading, network capacity and resiliency, and more.

Define the expansion ratio of a strict subset S of V as

φ(S ) = E (S ,S ) x ∈S deg x , (2.1)
where E (S ,S ) is the set of edges between S and its complementary. The expansion ratio of the graph as a whole is then defined as

Φ = min S ⊂V 1≤|S |≤ N 2 φ(S ).
(2.

2)

The higher the expansion ratio of the graph, the faster the simple random walk on that graph converges to its stationary distribution. For a rapid convergence rate, it is generally required that Φ be at least of order Ω(log -k N ) for some fixed integer k , as opposed to a rate of order O (N -ε ), which yields a slow convergence rate.

For stationary distributions such as the Erdős-Rényi model or uniform ∆-regular graphs, the random graph is an expander with high probability.

Mixing Time

Whereas the stationary distribution studies the asymptotic behavior of the dynamic, another point of interest is the convergence itself. Understanding the transitive phase can yield important insight into how dynamics operate, and can help engineer them to better suit ones needs. One of the most common features of this transitive phase is the mixing time. Recall that the total variation distance between two distributions ρ and ν over the state space S is defined as

ρ -ν TV = 1 2 x ∈S ρ(x ) -ν(x ) ,
and let π t x be the distribution of the dynamic at time t , starting in x at time 0. Denoting d (t ) = max

x ∈S π t x -π TV the distance to stationarity, the mixing time of the Markov chain is defined as

t mix = min t > 0 d (t ) ≤ 1 4 .
t mix is the first instant at which, regardless of the initial distribution, the current state is within a predefined distance of the stationary distribution (here 1 4 , but any ε < 1 2 would serve).

Case Analysis

In this section, we analyze the mixing time of some of the examples from Section 2. We say a dynamic converges rapidly if its mixing time is of order at most O (N log k N ) for some integer k , and that it mixes slowly if its mixing time is of order at least Ω(N 2 ). Note that rapid convergence implies at most O (log k N ) updates per vertex; in vertex-driven dynamics, this can be interpreted having a local complexity that scales well with the network.

Erdős-Rényi dynamic

In the sparse setting, the two models of Erdős-Rényi dynamics behave very differently. 1. The Erdős-Rényi dynamic for (N , p ) converges slowly, i.e. in at least Ω(N 2 ) steps.

2. The Erdős-Rényi dynamic for (N , M ) converges rapidly, reaching equilibrium in at most O (N log 2 N ) steps.

Note that with these values, the resulting graph is connected with high probability. We now prove both results separately.

Slow Mixing of (N , p )

We show that the (N , p ) dynamic converges slowly.

Proof. Observe that, given an initial configuration G with M edges, the probability that a graph G distributed according to (N , p ) shares M 2 edges with G goes to 0 as N goes to infinity. As such, as long as M 2 edge of G remains untouched, the total variation distance is close to 1. More specifically, denoting X the number of edges that G and G have in common, we have that E[X ] = M p = 2 N N -1 log 2 N . Using Markov's inequality, this gives that

P X ≥ M 2 ≤ 4 log N N -1 -→ N →+∞ 0.
This implies that the mixing time is at least the time required to modify half of the initial edges. Since a modification to any of these edges happens on average once every

N 2 M = N -1 2 log N transitions, it takes at least M 2 N -1 2 log N = N (N -1) 4
steps before this requirement is met. The mixing time is therefore at least of order Ω(N 2 ).

Rapid Mixing of (N , M )

We now show that, unlike (N , p ), (N , M ) converges rapidly to its stationary distribution.

Proof. The proof is very close to the previous one: we show that, once every edge has been touched at least once, we have reached the stationary distribution. Note that it is far quicker to modify all edges in this context than in the previous one.

Recall that, at each iteration, a pair of vertices (x , y ) is chosen uniformly at random, alongside an independent edge uniformly distributed over the edges of the current configuration. If (x , y ) was not already an edge, we then remove e , and replace it with (x , y ).

Suppose that, as you do this, you also tag edges as follows: if (x , y ) was not previously an edge, it is now tagged, regardless of whether e was tagged or not; if (x , y ) was already an edge, then

• if neither e nor (x , y ) was tagged, tag (x , y ) but not e (if e = (x , y ), tag it);

• if e was tagged, but not (x , y ), untag e and tag (x , y );

• otherwise do nothing.

All of the edges of the starting configuration are initially untagged.

We show by induction that, at all times, the set of tagged edges is distributed according to (N , | |). This is clearly true at initialization. Two cases can arise at each iteration:

• e was already tagged. If it was left unchanged ((x , y ) was a tagged edge), the distribution is unchanged, i.e. uniform. If it was replaced (untagged or removed), the new tagged edge is uniformly distributed over the edges not in , and the new distribution is once more uniform. Notice that the fact that (x , y ) was or wasn't already an edge makes no difference.

• e was untagged. If (x , y ) was a tagged edge, than and its distribution remain unchanged. Otherwise, (x , y ) is tagged. Since it is uniformly distributed over the edges not in , the new set of edges is necessarily distributed according to (N , | | + 1).

All that is left to show is that the edges are rapidly all tagged. For all i , denote

T i = min{t ≥ 0 | | t | ≥ i } the
time required before is of size i , and δT i = T i +1 -T i the duration for which is of size exactly i . We are interested in bounding

T M = i δT i .
If t is of size i , then the probability of its size increasing at time t + 1 is that of selecting an untagged e and choosing (x , y ) not in :

P( t +1 = t + 1) = M -i M • N 2 -i N 2
.

δT i is therefore geometrically distributed with the above parameter, and its average is

E[δT i ] = M M -i • N 2 N 2 -i . Summing yields that E[T M ] = M -1 i =0 E[δT i ] = M -1 i =0 M M -i • N 2 N 2 -i ≤ N 2 N 2 -M • M M -1 i =0 1 M -i = N 2 N 2 -M • M M i =1 1 i ∼ N 2 N 2 -M • M log M ∼ 1 1 - 2 log N N -1 • N log N • log(N log N ) (M = N log N ) ∼ N log 2 N .
This result could easily be foreseen, in that it is a modified instance of the coupon collector problem over the M edges, which would require O (M log M ) iterations to complete.

T M is what is known as a strong stationary time, a stopping time such that G T M is uniformly distributed, independently of T M . We make use of the following property: Property 9 (see [START_REF] Asher | Markov chains and mixing times[END_REF], Proposition 6.10). If T is a strong stationary time, then d (t ) ≤ max P(T > t ), where the max is taken over all initial states.

Applying this property here yields that

d (t ) ≤ max P(T M > t ) ≤ N log 2 N t + o (1). (Markov's inequality)
From this, we can deduce that

d (4N log 2 N ) ≤ 1 4 + o (1),
and therefore that

t mix = O (N log 2 N ).
The difference in convergence rate of these very similar models serves to outline the fact that there is no simple recipe to inferring the mixing time of given dynamics.

The Interchange Process

We now consider the interchange process. As mentioned in the previous section, it is best to consider half-edges when analyzing such a dynamic. For M initial edges, there are always 2M half-edges present in the graph, or ∆N for ∆-regular graphs.

Mixing Time of a Non-Local Dynamic

We first consider the non-local variant of the dynamic presented in Section 2. Recall that at each iteration, two half-edges are chosen uniformly and independently at random, and swapped. Formally, suppose the selected half edges correspond to the edges (x , y ) and (x , y ), attached to vertices y and y respectively. Replace these edges with (x , y ) and (x , y ). Multi-edges and self-loops are considered acceptable and greatly simplify considerations.

To establish an upper bound on the mixing time of this dynamic, number the edges e 1 , . . . , e M , and denote e • i and e • i the two half-edges of edge e i . Now consider the 2M -dimensional vector

X = (e • 1 , e • 1 , e • 2 , e • 2 , . . . , e • M , e • M ).
The graph can be reconstructed from X alone by grouping the half-edges two by two to form edges. Furthermore, swapping two half-edges in the graph is reflected in X as a simple transposition. As such, the mixing time of the dynamic is upper-bounded by the mixing time of the random transposition process on X .

Property 10 (see [START_REF] Asher | Markov chains and mixing times[END_REF], Corollary 8.10). The mixing time of the random transposition process for permutations of size N is of order O (N log N ).

The proof of this property is very similar to that used for the (N , M ) model: tagging some of the coordinates of X as they are transposed allows us to keep track of a growing subset of coordinates whose values are uniformly distributed among themselves. A coupon collector argument then concludes the proof.

For the non-local interchange process, this implies that t mix = O (M log(M )), and namely O (∆N log(N )) in the case of ∆-regular graphs.

x y x y G 1 x y x y G 2 P G 1 ,G 2 = 1 2M 2 P G 2 ,G 1 = 1 2M 2
Transition probabilities

Mixing Time of the Local Dynamic

Recall that the local dynamic differs from the previous one in that the half-edge swap occurs between two vertices y and y selected conditioned on (y , y ) being an edge. Bounding the mixing time in this scenario turns out to be far more difficult. To the extent of our knowledge, the best know result in this sense is the following Theorem 6 (Allen-Zhu et al. [START_REF] Allen Zhu | Expanders via local edge flips[END_REF]). If ∆ > 100 log N , then after Θ(∆ 2 N 2 log N ) iterations of the local interchange dynamic, the resulting graph is an expander with high probability, namely

∃γ > 0, P Φ > γ ≥ 1 -N -2 .
This result does not directly yield the mixing time; once the graph is an expander, however, the Markov chain is conceivably close to having mixed. As such, this suggests an upper bound on the convergence rate of no more than

O (∆ 2 N 2 log N ), i.e. O (N 2 log 5 2 N ) if ∆ = Θ(log N ).
Note that this last bound is of order o (N 3 ). In Section 4.3, we show that the mixing time of the interchange process on static graphs is at least Ω(N 3 ) in the worst cases. As such, though the above result still gives a somewhat slow upper bound, it does prove that the local dynamic does fundamentally better than the very similar interchange process.

Pointers on Rings

We finish with a last model, which mixes pointers and a static ring. While its construction may seem somewhat artificial, it gives some useful insight as to some necessary conditions in order to obtain rapidly mixing local dynamics.

The basic model is the following: let V = {1, . . . , N } and K ≥ 1 be a fixed integer. The edge set E consists of a static ring R = {(i , i + 1) | i ∈ V }, with N +1 ≡ 1, and K N pointers, such that each vertex is the source and destination of exactly K pointers. Considering these pointers to be undirected edges, the resulting multigraph is 2(K + 1)-regular.

All the dynamics are interchange processes: choose two pointers, and swap their destinations. This preserves the number of source and destination halfedges at each iteration. The difference results from the joint distribution of the two selected pointers:

Non-local dynamic The pointers are independent and uniformly distributed.

Ring dynamic

The pointers are uniformly distributed, conditioned on having adjacent destinations in R .

Bootstrap dynamic

The pointers are uniformly distributed, conditioned on having adjacent destinations in E .

Once more, multi-edges and self-loops may occur, but this is not a major concern, and simplifies proofs.

Theorem 7. Within this framework, one has the following results:

1. The non-local dynamic converges in O (K N log(N )).

The ring dynamic converges in Ω(K N 3 ), and, for K

= 1, in O (N 3 log N ).
A conjecture concerning the mixing time of the bootstrap dynamic is given at the end of this section.

Non-Local Dynamic

Bounding the mixing time of the non-local dynamic is straightforward with an approach identical to that used for the interchange process over ∆-regular graphs Proof. Consider the vector

X = (p 1 1 , . . . p K 1 , p 1 2 , . . . , p K n )
containing the destinations p j i of each pointer (for p j i , the j -th pointer with source i ). An iteration is a transposition of two coordinates in that vector, and the previous results therefore tell us that t mix = O (K N log(N )).

Ring Dynamic

We now constrain our dynamic, requiring that swapped pointers have their destinations be adjacent along the ring. Intuitively, this should notably increase its mixing time. We show that this is indeed the case, and that t mix = Ω(K N 3 ).

Proof. Denote (x t ) the destination of the first pointer of vertex 1. (x t ) is a lazy random walk over the ring, the probability of it staying in place is p = 1 -2 K N , and the probabilities of moving to the previous (-1) or next (+1) vertices are both 1 K N . Call xy R the distance between x and y along the ring:

x -y R = min( x -y , N -x -y ).
Consider the random walk y t over such that y 0 = x 0 and the transitions (+1, 0, or -1) are the same for both chains. Notice that y t = x t mod N ; this implies that x tx 0 R ≤ y ty 0 , and therefore that

P x t -x 0 R ≥ N 4 ≤ P y t -y 0 ≥ N 4 .
Since y ty 0 is the sum of t i.i.d random variables with mean 0 and variance 2 K N , its mean is 0 and its variance t 2 K N . Chebyshev's inequality gives that

P y t -y 0 ≥ N 4 ≤ t 2 K N 16 N 2 , hence P x t -x 0 R ≥ N 4 ≤ t 32 K N -3 .
Under the stationary distribution, x is uniformly distributed, and therefore

P x -x 0 R ≥ N 4 = 1 2 .
The mixing time must therefore satisfy

P x t mix -x 0 R ≥ N 4 ≥ 1 4 ,
as below this threshold,

d (t ) = max x 0 P x 0 (x t = •) -π TV ≥ 1 4 .
Combining the above inequalities, we obtain that t mix ≥ K 128 N 3 .

We furthermore show that this bound is close to tight, as the mixing time of the ring-based shortcut dynamic with K = 1 is of order at most N 3 log 2 N . For this, we use the following result from [START_REF] Berestycki | Mixing times of markov chains: Techniques and examples[END_REF]: Property 11. (see [START_REF] Berestycki | Mixing times of markov chains: Techniques and examples[END_REF], Theorem 4.6, p. 47) For every pair of vertices x and y , denote Γ x y a path from x to y . Let

Λ = max x ,y Γ x y ,
where γ designates the length of path Γ , and

B = max e ∈E (x , y ) ∈ V 2 : e ∈ Γ x y .

Then the mixing time for the interchange of labels between adjacent vertices is of order at most O (ΛB log N ).

Taking the Γ x y to be the shortest paths between x and y along the cycle, we immediately have that Λ = N 2 . Furthermore, the number of paths of length l crossing a single edge e is at most 2l , hence

B ≤ N 2 l =1 2l ≈ N 2 .
This concludes the proof.

Bootstrap Dynamic

We finally introduce a local dynamic with a rapid empirical mixing time. Consider the non-local dynamic, and constrain it so that the destinations of the swapped pointers are adjacent in the graph, connected by any pointer or ring edge, other than the two pointers themselves (so as to preserve reversibility).

Conjecture 1.

The mixing time of the bootstrap dynamic is of order O (K N log k N ) for some fixed k .

Chapter 3 is devoted to proving an analogous result for a similar continuoustime model.

Discussion

We give a brief overview as to why this result is somewhat surprising, and what makes it feasible.

Φ poor = 1 N Φ good = Ω(log -k N ) Expansion ratio Figure 2.

-Expansion of Pointers on Rings

Notice that the worst initial conditions are those such as that presented in Figure 2.12a. For these, the initial rate of convergence is at least cubic, since it closely mirrors that of the ring dynamic. However, the limit distribution gives good expanders w.h.p. (namely Φ = Ω(log -k N ) for some k ), and the rate of convergence should therefore improve as the dynamic proceeds. Since the rate of convergence of the interchange process over expanders has convergence rate O (N log N ), one can easily conjecture that the rate of convergence starting from an expander is of order O (K N log N ), i.e. the same as for the non-local dynamic.

The convergence rate of the bootstrap dynamic starting from an arbitrary position is therefore somewhere between Θ(K N 3 log N ) and Θ(K N log N ). Our conjecture, backed by Theorem 9, is that local bootstrap dynamics are nearly as efficient as non-local dynamics.

Proof of Theorem 9

A brief announcement containing the main results of this chapter was presented at DISC 2017. This chapter was recently submitted to Random Structures & Algorithms.

Introduction

Distributed systems typically cannot operate efficiently unless their constituting parts are interconnected via a network with suitable properties. In the context of peer-to-peer systems, desirable properties of the interconnection graph between peers include having a small diameter, small node degrees, and requiring many failures to disconnect a sizeable part of the network. Yet another useful property is the ability to obtain at low cost and via a distributed algorithm uniform samples of nodes in the system.

As mentioned in the first chapter, all these properties hold if the interconnection graph is an expander. By definition, the unoriented graph G = (V , E ) is a γ-expander for some constant γ > 0 if each set S ⊂ V of vertices with size |S | no larger than 1 2 |V | is such that at least γ|S | distinct edges in E connect S to its complement S in V . It is an expander if it is a γ-expander for some γ ≥ Ω(1).

For instance, when the graph is an expander, close-to-uniform samples are obtained in a distributed manner and at low cost by running a random walk on the peer-to-peer graph: It being an expander then ensures that only few steps (on the order of the logarithm of the system size, measured in number of nodes) of the walk suffice.

Because peer-to-peer systems are volatile, i.e. subject to node arrivals and departures, it is not possible to determine once and for all an expander graph to interconnect participating peers. Instead the graph must constantly evolve, with the aim to preserve or restore the desired expander property. Moreover, the graph evolution must rely on local adjustments, since by design no central controller has knowledge of the whole graph.

This has prompted research on dynamics for continuous modification of graphs that would (i) rely only on local modifications of the current graph, (ii) produce expander graphs at equilibrium, and (iii) reach equilibrium quickly. More precisely, considering graphs on a set of N nodes, by quickly we mean requiring a number of modifications per node that scales poly-logarithmically in N before equilibrium is attained.

The main contribution of this chapter is to propose a new graph dynamics together with the proof that it meets these three requirements. Its organization is as follows. Section 2 describes our proposed dynamics together with the main result, Theorem 8. It also highlights Theorem 9, our technical result controlling the spread of laws of random walks on graphs at short times. Section 3 explains the proof strategy. Section 4 explains how to deduce bounds with high probability on isoperimetric ratios from bounds on corresponding expectations, using negative dependence properties. Section 5 derives the necessary bounds on expectations, leveraging in particular Theorem 9. The proof of the later constitutes Section 6.

We now review relevant prior work.

Related Work

Markovian local graph dynamics for peer-to-peer systems have been considered in [START_REF] Massoulié | Network awareness and failure resilience in self-organizing overlay networks[END_REF][START_REF] Cooper | A randomized algorithm for the joining protocol in dynamic distributed networks[END_REF][START_REF] Cooper | The flip markov chain and a randomising p2p protocol[END_REF][START_REF] Feder | A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks[END_REF]. In all these papers the stationary regime for the proposed dynamics has been identified; in the last three references, loose bounds on the mixing time (defined below), or time to achieve equilibrium, have been obtained.

The tightest bounds available prior to the present article on the time before such local graph dynamics produce an expander graph were obtained in [START_REF] Allen Zhu | Expanders via local edge flips[END_REF]. Specifically, it is shown in [START_REF] Allen Zhu | Expanders via local edge flips[END_REF] that a discrete time Markov chain on the set of connected ∆-regular graphs on N vertices creates with high probability an expander graph after a time of O N 2 ∆ 2 log N with ∆ of order O (log N ). This implies the realization of this property after each node has performed a number of updates of order O (N log 5 2 N ), i.e. a number that is quasi-linear in the system size N . Graph dynamics have also been considered in different contexts. [START_REF] Schweinsberg | An o(n2) bound for the relaxation time of a markov chain on cladograms[END_REF] considers local dynamics for producing so-called cladograms uniformly at random, and bounds their mixing time. [START_REF] Jerrum | Approximating the permanent[END_REF] considers dynamics of matchings in bipartite graphs and controls their mixing time. The motivation of [START_REF] Jerrum | Approximating the permanent[END_REF] is the estimation of graph descriptors using a Markov chain Monte-Carlo approach. Finally, nonlocal graph dynamics together with their mixing time have been considered in [START_REF] Bhamidi | Mixing time of exponential random graphs[END_REF] in order to sample from so-called exponential random graph distributions.

Main results

In the sequel, we consider graphs over vertex set [N ], asymptotic results being with respect to N .

Consider the following setting. The vertices in [N ] are connected by edges of three distinct types: a fixed cycle, blue edges and red edges. The cycle is constituted of a fixed set of edges We now consider the following continuous-time dynamics. The graph evolves through alternating blue and red phases. During each phase, only the edges of a given color evolve, while those of the other color are kept fixed. During a blue phase, for example, blue pointers are swapped along graph G r constituted of the edges in both E • and E r . Note that G r is a 4-regular multigraph.

E • = {(n, n + 1) | i ∈ [N ]}, with N + 1 ≡ 1. Each node n ∈ [N ]
The dynamics for a blue phase are defined as follows. Each edge e = (i , j ) of G r maintains an internal clock, in which the time between ticks are exponentially . Such a process has been studied in the literature, where it is known as the interchange process. See for instance Jonasson [START_REF] Jonasson | Mixing times for the interchange process[END_REF] or N. Berestycki [START_REF] Berestycki | Mixing times of markov chains: Techniques and examples[END_REF], where the discrete time version of this process is analyzed.

For the red phases, the roles of blue and red pointers are swapped; the graph containing the edges in E • and E b is denoted G b . To clarify notations, we denote E f the fixed edge set during phase f , i.e. E b if f is a red phase, E r otherwise, and G f the fixed graph, i.e. containing the edges in E • and E f . We finally write

E • f = E f ∪ E • .
Our main result is then as follows Theorem 8. Let T = log a N where a > 8 is a constant. After F = log 2 N phases of length T , with high probability, the sets of blue and red pointers are uniformly and independently distributed permutations over the symmetric group S N .

Corollary 2. After each node has undergone a number of local connectivity modifications that is polylogarithmic in N , the process has produced an expander with high probability.

Proof. By time τ = F T , a given node n ∈ [N ] has seen under these dynamics a number of connectivity modifications that is at most a Poisson random variable with mean 8τ. Indeed, at any given time, the rate at which a transition might occur is at most 8, corresponding to the rate at which the pointer b n (for the blue phase) issued from n moves (equal to the number of edges of G r adjacent to b n , i.e. 4) plus the rate at which the blue pointer ending at n moves (also 4). The probability that this number M n of connectivity modifications exceeds 16τ is then, by Chernoff's bound for deviations of Poisson random variables from their mean, bounded by 2) , where h (x ) = x log xx + 1 is the Cramér transform of a unit mean Poisson random variable. Since τ is at least of order log a +1 N with a > 0, the last term is o (N -1 ). Thus the probability that at least one node n ∈ [N ] undergoes more than 16τ = polylog(N ) local modifications by time τ is, by the union bound, no more than N • o (N -1 ) = o (1).

P(M n ≥ 16τ) ≤ e -8τh ( 16τ 8τ ) = e -8τh (
The fact that the resulting graph G F is an expander will be shown in Section 4, in which we introduce the necessary technical lemmas. Note that results in [START_REF] Bollobas | Modern Graph Theory[END_REF][START_REF] Friedman | On the second eigenvalue of random regular graphs[END_REF] establish for very similar (although not identical) random graph models that these are expanders with high probability.

We now state another result, which will be instrumental in Section 5, and proven in Section 6, but which we believe could be of independent interest: Theorem 9. Let G = ([N ], E ) be an undirected multi-graph with maximum degree ∆, and (X t ) t ∈ the continuous time random walk on G , i.e. the Markov jump process on [N ] with jump rates q i j equal to the multiplicity of (i , j ) in E . The infinitesimal generator of (X t ) t ∈ is -L , where L is the Laplacian matrix of G . Let (π i (t )) i ∈[N ] denote its law at time t . For an arbitrary initial distribution of the random walk, for any k ≤ N 2 and S ⊂ [N ] such that |S | ≤ k and any t ≥ 0, one has:

i ∈S π i (t ) ≤ |S | k + 1 + k + 1e -λ * 2 t , (3.1)
where

λ * 2 = Φ k (G ) 2 2∆ . (3.2)
Remark 1. The quantity λ * 2 is of the same form as the lower bound on the spectral gap λ 2 of the Laplacian that the celebrated Cheeger inequality gives when k = N 2 . In fact for k = N 2 , the expression of Φ k (G ) coincides with this lower bound. In this classical situation, instead of (3.1), one has the conclusion that

π(t ) -[N ] TV ≤ 1 2 N e -λ * 2 t ,
as shown in Property 5.

Proof strategy

To proceed, we first introduce some definitions.

Definition 20. The collection

(Φ k (G )) 1≤k ≤ N 2 of isoperimetric constants of graph G constitutes its isoperimetric profile.
The graph is said to be a

(γ, c )-expander if, for all k ≤ N 2 , Φ k (G ) ≥ min γ, c k .
Note that a graph is a γ-expander according to the classical notion if it is a γ, N 2 -expander according to the above definition. Our proof consists in controlling the evolution of the isoperimetric profile of the graph along which pointers move from one phase to the next, establishing lower bounds on this profile in an iterative manner.

Let β be a constant such that 1 < β < a -4 4 . Such β exists by our assumption that a > 8. Let γ = log -β N . We show the following Lemma 1. Suppose that, during phase f , the graph G f is a (γ, c )-expander for some integer c . Then, with probability at least 1o (N -1 ), the graph G f +1 is a (γ, 2c )-expander.

Notice that if G f contained blue edges, G f +1 contains red edges, and vice versa.

To prove this, we first show a stronger lower bound on the average number of shortcuts leaving any given set S : Lemma 2. If, for a given phase f and integer c , G f is a (γ, c )-expander, then for all S ⊂

[N ] with |S | ≤ N 2 , E E f +1 S ,S ≥ 1 2γ min(γ|S |, 2c ). (3.3)
Lemma 1 is then deduced from Lemma 2 by invoking some concentration inequalities together with union bounds. Details are given in Section 4.2.

An easy consequence of Lemma 1 is the following:

Corollary 3. After F = log 2 (N ) phases, with high probability both G b and G r are (γ, N 2 )-expanders.

Proof. Clearly, G 1 is a (γ, 2)-expander. Indeed, any subset S ⊂ [N ] of size |S | ≤ N 2
is connected by at least two edges (that come from the cycle) to its complement S , so that

E • 1 S ,S ≥ 2 ≥ min(γ|S |, 2).
Denote by f the event that G f is a γ, 2 f -expander. Thus we have just established that event 1 holds with certainty, and Lemma 1 entails that, for all f ≥ 1,

P f +1 f ≤ o (N -1 )
.

Thus P f +1 = P f +1 f P f + P f +1 f P f ≤ o (N -1 ) + P f .
By induction on f , this yields

P f +1 ≤ o f N .
For F = log 2 (N ), the right-hand side of this expression is o (1), so that with high probability, the graphs G F -1 and G F are γ, N 2 -expanders. As the color of these two graphs differ, this concludes the proof.

The proof of Theorem 8 is then concluded as follows:

Proof. By Corollary 3, after F = log 2 (N ) phases, the Cheeger constants Φ N 2 (G b ) and Φ N 2 (G r ) are at least γ. We show that, for any graph G , Φ N 2 (G ) ≥ γ implies that the interchange processes on G mixes in less than T steps, so that with high probability, in two more phases our process will have reached stationarity.

Our main tool to this end is Theorem 4.3, p. 39 in Berestycki [START_REF] Berestycki | Mixing times of markov chains: Techniques and examples[END_REF], which gives a sufficient condition for the discrete time interchange process on a graph G to mix in time T . The continuous time analogous result reads The continuous time interchange process on G will have mixed in time T provided

T ≥ 8Υ K log N N . ( 3.4)
According to Lemma 3 below, for a ∆-regular γ, N 2 -expander with ∆ constant, we can choose these paths such that

Υ = O log N γ 2 and K = O N log 2 N γ 2 .
Plugged into (3.4), these evaluations imply that mixing has occurred by time T provided T is large compared to log N γ 4 , i.e provided log a N = ω(log 4+4β N ). This condition holds since β < a -4 4 .

Lemma 3. Let G be a ∆-regular graph with vertex set

[N ], such that Φ N 2 (G ) ≥ γ. One can construct a set of paths Γ = γ i j i , j ∈ [N ] such that the γ i j each have length at most Υ = 2 d 2 γ 2 log N ,
regular graph G with Φ N 2 (G ) ≥ γ is at least γ 2 2∆ 2 .
Thus the total variation distance between the distribution of the random walk at time Υ = 2 ∆ 2 γ 2 log N and the uniform distribution on G is o (N -1 ) (this follows e.g. by Theorem 2.2, p. 18 in [START_REF] Berestycki | Mixing times of markov chains: Techniques and examples[END_REF]). As a result, for any i ∈ [N ], the probability that the walk started at i hits j at time Υ is at least 1 2N . Consider then the following randomized construction. For each i , create 5N log N independent walks of length Υ started at i . The probability that for some particular j ∈ [N ], no such walk issued from i hits j is then at most

1 - 1 2N 5N log N ≤ e -5 2 log N = o (N -2 ).
Using the union bound, we can therefore conclude that, with high probability, the collection of paths thus created joins every node i to every node j .

Let us now evaluate the number of times a given edge e = (u, v ) of G is traversed by this collection of paths. This is no larger than the number of times these paths visit node u . For t ≤ 5N log N , denote by X i (t ) the number of visits to u by the t -th path sampled with starting point i . Clearly, X i (t ) ≤ Υ . Also,

E   i ∈[N ] t ≤5N log N X i (t )   = 5N log N i ∈[N ] Υ l =0 P (l ) i u ,
where P (l ) i u denotes the transition probability from i to u in l steps of the walk. However the walk is symmetric, so that P (l )

i u = P (l )
ui . The above expection thus reads

E   i ∈[N ] t ≤5N log N X i (t )   = 5(Υ + 1)N log N . Let Z = i ∈[N ] t ≤5N log N X i (t )
denote the total number of visits to u by all paths. For any C > 0, Hoeffding's inequality then gives

P Z ≥ E[Z ] + C N Υ log N ≤ exp - C 2 N 2 Υ 2 log 2 N 5Υ 2 N 2 log N = e -C 2 5 log N .
Taking C = 3, the right-hand side is o (N -1 ). Thus, by the union bound, with high probability, no node u is visited more than 9Υ N log N = 18 d 2 γ 2 N log 2 N times by the collection of constructed paths.

From bounds in expectation to bounds with high probability 4.1 Proof of Lemma 1

Assume that G f is a (γ, c )-expander. By Lemma 2, for each fixed set S ⊂ [N ] with |S | ≤ N 2 , we have that

E E f +1 S ,S ≥ 1 2γ min(γ|S |, 2c ). Fix k ≤ N 2 .
We further restrict ourselves to k > 2 γ , since E • S ,S ≥ 2 and therefore one always has that Φ k ≥ γ for k ≤ 2 γ . For some set S of size k , let l ∈ 1, k be the number of contiguous portions of the cycle it is made of. Clearly E • S ,S = 2l , and therefore

E • f +1 S ,S = E f +1 S ,S + 2l .
Recall (see e.g. Dubashi and Ranjan [START_REF] Dubhashi | Balls and bins: a study in negative dependence[END_REF], and Borcea et al. [START_REF] Borcea | Negative dependence and the geometry of polynomials[END_REF]) that a set of random variables (X i ) i ∈I is said to be negatively associated if for any two functions f , g : I → that are non-decreasing in each of their coordinates, and depend on disjoint sets of variables X i , the two random variables f ((X i ) i ∈I ) and g ((X i ) i ∈I ) are negatively correlated, i.e.

E f ((X

i ) i ∈I )g ((X i ) i ∈I ) ≤ E f ((X i ) i ∈I ) E g ((X i ) i ∈I ) .
We will need the following two results. Lemma 4. Conditionally on the shortcut configuration at the beginning of the considered phase, the random variable E f +1 S ,S consists of the sum of negatively associated Bernoulli random variables. Consequently, for any r ∈ (0, 1), it holds that

P E f +1 S ,S ≤ r 1 2γ min(γ|S |, 2c ) ≤ e -1 2γ min(γ|S |,2c )h (r ) , (3.5)
where h (r ) = r log rr + 1.

Proof. Represent the collection of termination points of pointers through the binary variables

ξ i ∈ {0, 1}, i ∈ [N ]
where ξ i = 1 if and only if one pointer issued from S points towards i . The variables (ξ i ) i ∈[N ] evolve, under the interchange process dynamics, as a symmetric exclusion process. Given that we condition on the initial configuration, applying Proposition 5.1 in [START_REF] Borcea | Negative dependence and the geometry of polynomials[END_REF] gives that the collection of indicator variables (ξ i (t )) i ∈[N ] satisfies the strong Rayleigh property [START_REF] Liggett | Negative correlations and particle systems[END_REF] for all t ≥ 0. This is namely true for (ξ i (T )) i ∈[N ] , i.e. at the end of the phase. Since the strong Rayleigh property implies negative association (see again [START_REF] Borcea | Negative dependence and the geometry of polynomials[END_REF], Section 2, Figure 1), it then follows from Dubhashi and Ranjan [START_REF] Dubhashi | Balls and bins: a study in negative dependence[END_REF] that

E f +1 S ,S = i ∈S ξ i (T )
verifies the same Chernoff bounds that it would if the ξ i (T ) were mutually independent. The announced result (3.5) then follows from classical evaluations of Chernoff bounds.

Lemma 5. The number of sets S ⊂ [N ] of size k that consist of l contiguous portions of the cycle is at most N 2l . It is also upper-bounded by N

k -1 l -1 N -k -1 l -1 .
Proof. We may enumerate such sets S by scanning the cycle [N ] starting from 1, and identifying the first time we find a starting point of an interval in S , then the end point of that interval, and so on. Clearly this will produce 2l numbers in 1, N , which characterize S , hence the upper bound N 2l .

To obtain the other upper bound, note that the number of strictly positive sequences of l integers x 1 , . . . , x l such that x 1 + • • • + x l = k equals the number of non-negative sequences of such integers such that x 1 + • • • + x l = kl , and this number is well known to equal

k -l + l -1 l -1 .
Similarly, the number of strictly positive sequences of integers y 1 , . . . , y l such that

y 1 + • • • + y l = N -k equals N -k -1 l -1 . Given a set S ⊂ [N ]
of size k and made of l distinct intervals, let z ∈ 0, N -1 be the smallest number of clockwise rotations of the set such that i = 1 corresponds exactly to the beginning (in clockwise order) of a contiguous segment of the set. The set is then fully specified by the lengths of its constituting segments, x 1 , . . . , x l , in clocqkwise order, together with the lengths of the segments separating its own segments, y 1 , . . . , y l . Since this construction forms an injection from the collection of considered sets S to a set of size

N k -1 l -1 N -k -1
l -1 , the announced upper bound follows. The union bound gives us, using the first upper bound in this last lemma, the following bound on the probability p k that for some set S of size k , one does not have the desired property E • f +1 S ,S ≥ min(γk , 2c ):

p k ≤ k l =1 N 2l P E f +1 S ,S ≤ min(γk , 2c ) -2l .
We now distinguish according to whether γk ≤ 2c or not.

Case 1: γk ≤ 2c We then have, by (3.5):

p k ≤ γk 2 l =1 N 2l exp - 1 2γ γk h γk -2l 1 2γ γk ≤ N exp γk log N - 1 2γ γk h (o (1))
= exp 1 + γkγk

2 log β -1 N • h (o (1)) log N .
The term in the inner parenthesis is asymptotically equivalent toγk 2 log β -1 N , because h (o (1)) tends to 1 and β > 1. Moreover, since γk > 2, the whole exponent is large compared to log N . Thus p k = o (N -r ) for any fixed r > 0.

Case 2: γk > 2c We then have

p k ≤ c l =1 N 2l exp - 1 2γ 2c h 2c -2l 1 2γ 2c ≤ N exp 2c log N - 1 2γ 2c h (o (1)) = exp 1 + 2c -c log β -1 N • h (o (1)) log N .
We can then conclude as in the previous case.

Proof of expansion at equilibrium

To complete the proof of Corollary 2, we now show that the graph G F obtained after F = log 2 N phases is an expander, i.e. an ε-expander for some fixed ε ≥ Ω(1), thereby strengthening the statement that it is a γ-expander. The graph G F is, with high probability made of a cycle plus a uniform random permutation. We place ourselves in the remainder of this section on the event where it consists precisely of a cycle plus a uniform random permutation.

For a set S ⊂ [N ] of size k , the number of edges from the permutation starting at nodes in S and ending at nodes in S reads k i =1 ξ i , for Bernoulli random variables ξ i with mean 1 -k N . Moreover, these random variables are negatively associated, as follows from [START_REF] Dubhashi | Balls and bins: a study in negative dependence[END_REF]. Chernoff bound on their deviation from the mean is then stronger than the corresponding bound obtained assuming they are independent. This entails that, for r ≤ 1 -k N ,

P k i =1 ξ i ≤ r k ≤ e -k D ( r 1-k N ) ,
where

D (r s ) = r log r s + (1 -r ) log 1 -r 1
s is the Kullback-Leibler divergence between Bernoulli distributions with parameters r and s .

Fix ε > 0 a small positive constant, and let k ≤ N 1 3 . In particular, one has that k N ≤ 1 -ε. We thus have, in view of the first bound in Lemma 5, the upperbound on the probability p k that there exists some set S ⊂ [N ] of size k such that E • F S ,S < εk :

p k ≤ k l =1 N 2l P E f S ,S < εk -2l ≤ ε k 2 -1 l =1 N 2l e -k D ( ε-2l k 1-k N ) .
Since D ε -2l k 1 -k N increases with l , we may upper-bound each term in this last summation by

N k ε exp -k D ε 1 -k N . Its logarithm C reads C = εk log N -k D ε 1 - k N = εk log N -k ε log ε 1 -k N -k (1 -ε) log 1 -ε k N . The second term is O (k ), while the third term is for large enough N no larger than -k (1 -ε) log N = -k 1-ε 2 log N . It follows that C ≤ k ε - 1 -ε 2 log N + O (1)
and, assuming ε < 1/3, this is no larger than -r ε log N , where r ε = 1-3ε 4 > 0. This yields for all k ≤ N 1 3 :

p k ≤ k e -r ε k log N .
As

N 1 3 k =1 k e -r ε k log N = o (1), with high probability no subset S ⊂ [N ] of size |S | ≤ N 1 3 is such that E • F S ,S < ε|S |. For |S | = k ∈ N 1 3 , N
2 , we use the second upper bound of Lemma 5 on the number of size k sets made of l segments. Since this bound increases with l for l ≤ εk 2 , we obtain

p k ≤ k N k -1 εk 2 N -k -1 εk 2 e -k D ( ε 1-k N ) .
Stirling's formula implies that the logarithm of this upper bound is no larger than

log(k N ) + εk 2 log k -1 εk 2 + k -1 - εk 2 log k -1 k -1 -εk 2 + εk 2 log N -k -1 εk 2 + N -k -1 - εk 2 log N -k -1 N -k -1 -εk 2 -k ε log ε 1 -k N -k (1 -ε) log 1 -ε k N . The first term is at most 2 log N since k ≤ N 2 .
Using the inequality log u ≤ u -1, the last term in the second line is no larger than εk 2 . It follows that the sum of the last two terms in the first line, the last term in the second line and the first term in the last line is upper-bounded by k f (ε) for a function

f of ε such that f (ε) = O ε log ε -1 . Thus, log p k ≤ 2 log N + k f (ε) + εk 2 log N -k -1 εk 2 -k (1 -ε) log 1 -ε k N = 2 log N + k f (ε) + εk 2 log 1 -k +1 N ε 2 + εk 2 log N k -k (1 -ε) log(1 -ε) -k (1 -ε) log N k = 2 log N + k g (ε) -k (1 - 3 2 ε) log N k for some function g (ε) such that g (ε) = O (ε log ε -1
). This readily implies that for small enough ε > 0, there exists a constant s ε > 0 such that, for k ∈ N 1 3 , N 2 , p k ≤ e -s ε k . The corresponding sum is o (1). Therefore, graph G F is with high probability an ε-expander for some fixed constant ε > 0.

Controlling the mean

The goal of this section is to prove Lemma 2. Let G f be the static graph during phase f . G f is a 4-regular undirected graph on [N ], and we assume it is a (γ, c )expander:

∀k ≤ N 2 , Φ k (G ) ≥ min γ, c k .
Our goal is to prove that for any fixed set S of size k ≤ N 2 , by the end of phase f (i.e. after T time steps), the expected number of pointers connecting S to S satisfies

E E f +1 S ,S ≥ 1 2γ
min(γk , 2c ).

CONTROLLING THE MEAN

The proof is divided into two parts, arguing differently depending on the size k of S . Let k c = 4c γ ; sets of size k with k ≤ k c (respectively k > k c ) will be referred to as small sets (respectively large sets).

Small sets: from partial expansion to partial spread

Let us now use Theorem 9 to prove the conclusion of Lemma 2 for small values of k .

For a fixed set S of size k ≤ k c , and a fixed node i ∈ S , let X i (t ) denote the location of the pointer issued from i at time t . Under the dynamics we consider, X i (t ) corresponds to an ordinary random walk on the graph G . Moreover, the assumptions of Lemma 2 guarantee that the graph G f satisfies

Φ 3k (G f ) ≥ min γ, c 3k ≥ min γ, c 3k c = γ 12 .
By Theorem 9, one therefore has

P(X i (T ) ∈ S ) ≤ |S | 3k + 3k + 1e -λ * 2 T ,
where

λ * 2 = 1 2∆ Φ 3k (G f ) 2 ≥ γ 2
1152 . Recall that T = log a N and that γ = log -β N . Furthermore, 1 < β < a -4 4 , implying that a -2β > 1. We then have

P(X i (T ) ∈ S ) ≤ 1 3 + exp - log a -2β N 1152 ≤ 1 2 .
Summing over i ∈ S , we obtain that the expected number of pointers issued from S that point into S at the end of the phase is no larger than k 2 , and therefore that

E E f +1 S ,S ≥ k 2 ≥ 1 2γ
min(γk , 2c ).

Large sets

Consider a fixed set S of size k such that k c < k ≤ N 2 , and define π i (t ) to be 1 k times the probability that a pointer issued from S targets i , conditionally on the initial configuration of these pointers at the beginning of the phase (corresponding

to t = 0). Let π (i ) (t ) denote the i -th largest value in π j (t ) j ∈[N ] , and π [m ] (t ) = m i =1 π (i ) (t )
denote the cumulative mass that the probability distribution π(t ) puts on the m nodes where its mass is the largest.

One clearly has that

π (i ) (0) = 1 k 1 i ≤k .
We now establish a property of the time derivative d dt π [m] (t ): Lemma 6. Under the assumptions of Lemma 1 that Φ m (G f ) ≥ min(γ, c m ) for all m ∈ 1, N , one has the inequalities

d dt π [m ] (t ) ≤ -4 c m j =1 π (m -j +1) -π (m -j +1+c m ) , (3.6)
where c m = 1 4 min(γm , c ) .

Proof. Assume to simplify notation that the permutation which sorts nodes i in [N ] in decreasing order of π i is the identity, so that

π i (t ) = π (i ) (t ). The time derivative of π [m ] then reads d dt π [m ] (t ) = i ≤m j >m 1 (i , j )∈E • f (π j -π i ).
Indeed, changes in the mass π [m ] result from interchange of pointer extremities i , j with i ≤ m and j > m, which occur at unit rate for (i , j ) ∈ E • f ; when one such interchange occurs, the expected change to π [m ] is precisely π j -π i . Now the number of such edges is by assumption at least min(γm , c ). Moreover, the number of such edges adjacent to any node is at most 4, because the graph has degree bounded by 4.

The value of the right-hand side in the above equation, because the π i are sorted in decreasing order, is minimized when the edges crossing the cut between [m ] are adjacent to nodes with index closest to m . The degree constraint then implies the upper bound (3.6).

Let c = c

4 and

I = k -2 3 k c , k + 2 3 k c . We now introduce an auxiliary pro- cess (ν i (t )) i ∈[N ],t ∈ defined for all i ∈ [N ] via: ν i (0) = 1 k 1 i ∈[k ] d dt ν i (t ) = 41 i ∈I [(ν i -c (t ) -ν i (t ))1 i -c ∈I + 4(ν i +c -ν i )1 i +c ∈I ] .
The probability distribution ν(t ) is readily interpreted as the law at time t of a random walk started with uniform distribution on [k ], that jumps from i to i + c (resp., ic ) at rate 4, provided both i and the destination i ± c lie in I .

Denoting ν [m] (t ) = m j =1 ν j (t ) for all m ∈ 1, N , we then have the following

Lemma 7. For all t > 0, m ∈ [N ], it holds that π [m ] (t ) ≤ ν [m ] (t ).
Proof. Introduce the differences δ m (t

) := π [m ] (t ) -ν [m ] (t ). It is readily seen that δ m (0) = 0 for all m ∈ [N ]. Inequality (3.6) of Lemma 6 implies that d dt π [m ] (t ) ≤ -4 c j =1 1 m -j +1∈I 1 m -j +1+c ∈I π (m -j +1) -π (m-j +1+c ) . (3.7)
Indeed, each term in the summation of the right-hand side of (3.6) is nonnegative. The j -th term in the summation in the right-hand side of (3.7) is included only if mj + 1 ∈ and mj + 1 + c ∈ I . The first condition implies that

m -j + 1 ≥ k - 2 3 k c ≥ 1 3 k c = 4 3 c γ .
In turn this implies that γm ≥ c , so that c m = c . Thus the summation in the right-hand side of (3.7) runs over a subset of indices in the summation in the right-hand side of (3.6), and (3.7) follows from (3.6).

By definition of ν i (t ), one has

d dt ν [m] (t ) = -4 c j =1 1 m-j +1∈I 1 m -j +1+c ∈I ν (m -j +1) -ν (m -j +1+c ) . (3.8)
For all m ∈ 1, N , there thus exists an integer

i m ≥ 0 such that m -i m ≥ 1, m + i m ≤ N and d dt π [m ] (t ) ≤ -4 2π [m] -π [m-i m ] -π [m +i m ] , d dt ν [m ] (t ) = -4 2ν [m ] -ν [m -i m ] -ν [m +i m ] , so that d dt δ m ≤ -4 2δ m -δ m -i m -δ m +i m .
In the above, as is easily seen, necessarily i 1 = 0, so that we have the boundary condition δ 1 ≤ 0. Also, since π [N ] = ν [N ] = 1, we have δ N = 0. The previous equation then implies that necessarily, the supremum over m ∈ 1, N of δ m cannot become positive, because its derivative is always non-positive.

By the previous lemma, an upper bound on π [k ] (T ) is provided by ν [k ] (T ). However the latter quantity is simpler to analyze. It can be interpreted as 1 k times the average number of points of 2 3 k c random walks initialized at each point in k -2 3 k c , k which fall within [k ] at time T . These walks proceed with jumps of size ±c at rate 4, constrained to not leave interval

I = k -2 3 k c , k + 2 3 k c . For a given initial condition i ∈ [k -2 3 k c ],
the number of sites it can visit is of the order of 4 3 k c c = Θ(log β N ). Classical results on the nearest neighbor random walk on an interval 1, M state that it mixes in time of the order of M 2 [START_REF] Asher | Markov chains and mixing times[END_REF]. Thus each of the random walks just introduced mix in time O (log 2β N ) = o (T ), because 2β < a . We therefore have the following evaluation:

π [k ] (T ) ≤ ν [k ] (T ) ≤ 1 - 2 3 k c k 1 2 -o (1)
.

The expected number E E f +1 S ,S is then lower-bounded by

E E f +1 S ,S ≥ 2 3 k c 1 2 -o (1) = 4 c γ 1 3 -o (1) ≥ 1 2γ 2c .
The announced result follows.

6 Proof of Theorem 9

Proof. In vector form the law π(t ) of the random walk on G at time t reads π(t ) = e -t L π(0), where L is the graph's Laplacian. Its entries π i (t ) are thus linear combinations of n functions of the form e -λ j t , where λ j are the eigenvalues of L , and so is the difference π i (t ) -π j (t ). It can be shown by induction on N that such linear combinations of N distinct exponential functions are either identically zero in t , or admit at most N -1 distinct roots in t . Thus for any i = j , either π i (t ) = π j (t ) except perhaps for finitely many t , or else π i (t ) = π j (t ) for all t ≥ 0. We can thus split + into finitely many intervals I (1) = [0, t 1 ), I (2) = [t 1 , t 2 ), . . ., and on each interval I ( j ) determine a particular permutation σ ( j ) ∈ S N such that for all j , and all t ∈ I ( j ) , one has

π σ ( j ) (1) (t ) ≥ π σ ( j ) (2) (t ) ≥ • • • ≥ π σ ( j ) (N ) (t ).
For t in any given interval I ( j ) , we will maintain an auxiliary probability distribution on 1, k + 1 , denoted

(ν i (t )) i ∈[k +1]
. This distribution can be interpreted as that of a random walk on a graph G ( j ) with node set [k + 1], obtained from G as follows. We identify node σ ( j ) (i ) in G with node i in G ( j ) for all i ∈ [k ], and collapse all nodes σ ( j ) (u ), u > k to form node k + 1. All edges are then preserved, so that the adjacency matrix A ( j ) of G ( j ) is given by

A ( j ) u,v = A σ ( j ) (u ),σ ( j ) (v ) , u , v ∈ [k ], A ( j ) u ,k +1 = N v =k +1 A σ ( j ) (u ),σ ( j ) (v ) , u ∈ [k ],
where A is the adjacency matrix of G . For convenience, we denote by π (i ) (t ) the i -th largest entry of distribution π(t ). Thus for t ∈ I

( j ) , π (i ) (t ) = π σ ( j ) (i ) (t ).
The result of the theorem will then follow from the combination of two ingredients. We first show in Lemma 8 below that, for all t , one has the following bound:

π (i ) (t ) ≤ ν min(i ,k +1) (t ), i ∈ [N ], t ≥ 0. (3.9)
We then establish in Lemma 9 below that for all j , the second smallest eigenvalue λ ( j ) 2 of the Laplacian of G ( j ) is lower-bounded by λ * 2 given in (3.2), where crucially ∆ is the largest node degree in G , not in G ( j ) . This readily implies the

L 2 control i ∈[k +1] ν i (t ) - 1 k + 1 2 ≤ e -2λ * 2 t .
Cauchy-Schwarz inequality then gives the following control on variation distance:

i ∈[k +1] ν i (t ) - 1 k + 1 ≤ k + 1e -λ * 2 t .
Together, these two results entail that for all s ≤ k ,

i ∈[s ] π (i ) (t ) ≤ s k + 1 + k + 1e -λ * 2 t , (3.10)
which is the announced result.

Lemma 8. The distributions π(t ) and ν(t ) verify bound (3.9).

Proof. The bound trivially holds at t = 0. We can establish it by induction on each interval I ( j ) . Let us consider one such interval, and assume that the property holds at its left end. For notational simplicity we will assume that σ ( j ) is the identity, so that on this interval π i (t ) = π (i ) (t ). Introduce the notation

δ i (t ) = π i (t ) -ν min(i ,k +1) (t ), i ∈ [N ].
For any pair of vertices (i , j ) in [N ], write i ∼ j if i and j are neighbors in G . One has the following time derivatives

d dt π i = j ∈[k ] j ∼i (π j -π i ) + j / ∈[k ] j ∼i (π j -π i ) i ∈ [N ] d dt ν i = j ∈[k ] j ∼i (ν j -ν i ) + j / ∈[k ] j ∼i (ν k +1 -ν i ) i ∈ [k ] d dt ν k +1 = i / ∈[k ] j ∈[k ] j ∼i (ν j -ν k +1 ).
By the previous display one has for i ∈ [k ]:

d dt δ i = j ∈[n] j ∼i (δ j -δ i ). (3.11)
Note that, because the values π i are sorted, for all j / ∈ [k ], π j -π k +1 ≤ 0. This together with the expression for the time derivative of Assume then that i = k + 1. Then on J one has that, for all j ∈ [k ], since the π j are sorted,

π k +1 yield d dt π k +1 ≤ j ∈[k ] j ∼k +1 (π j -π k +1 ). Thus d dt δ k +1 ≤ j ∈[k ] j ∼k +1 (π j -π k +1 ) - i / ∈[k ] j ∈[k ] j ∼i (ν j -ν k +1 ) = j ∈[k ] j ∼k +1 (δ j -δ k +1 ) - i / ∈[k +1] j ∈[k ] j ∼i (ν j -ν k +1 ). ( 3
ν k +1 = π k +1 -δ k +1 ≤ π k +1 ≤ π j = ν j + δ j ≤ ν j + δ k +1 .
Thus for all j ∈ [k ], ν k +1 -ν j ≤ δ k +1 . It then follows from (3.12) that

d dt δ k +1 ≤ 0 + αδ k +1 , where α = i / ∈[k +1] j ∈ [k ] j ∼ i .
Gronwall's lemma (see e.g. [START_REF] Khalil | Nonlinear Systems[END_REF]) then implies that δ k +1 ≤ 0 on J , a contradiction.

Remark 2. When we move from interval I ( j ) to I ( j +1) one can check that the meaning of distribution ν is preserved: we may change the permutation sorting the entries π i , which results in a change in the graph used to define the evolution of ν, but while the vertex to which ν i refers may change, in that case the corresponding mass does not change. Proof. Without loss of generality we assume nodes k + 1, . . . , N of G have been collapsed into node k + 1 of G . Let f be an eigenvector of L associated with its second smallest eigenvalue λ 2 . We can always choose f such that f k +1 ≤ 0. For v ∈ [k + 1], define g v = max(f v , 0), and thus g k +1 = 0. Let

W = v ∈ [k + 1] f v > 0 .
Letting (a u v ) u,v ∈[N ] denote the adjacency matrix of graph G , one has

λ 2 u∈W f 2 u = u∈W (L f ) u f u = u∈W d u f u - v ∈[k +1] a u v f v f u = u∈W v ∈[k +1] a u v f u -f v f u = u∈W v ∈W a u v f u -f v f u + u∈W v / ∈W a u v f u -f v f u ≥ u∈W v ∈W a u v f u -f v f u + u∈W v / ∈W a u v f 2 u = L g , g Thus λ 2 ≥ L g , g g , g = K .
On the other hand,

(u v )∈E a u v (g u + g v ) 2 = 2 (u v )∈E a u v g 2 u + g 2 v - (u v )∈E a u v g u -g v 2 ≤ 2 v ∈V d v g 2 v ≤ 2∆ g , g ,
where we have used the fact that g k +1 = 0 to upper bound each product d v g 2 v by ∆g 2 v . By Cauchy-Schwarz inequality,

(u v )∈E a u v g 2 u -g 2 v 2 ≤ (u v )∈E a u v g u -g v 2 (u v )∈E a u v g u + g v 2 .
Combined, these bounds give

K = (u v )∈E a u v g u -g v 2 (u v )∈E a u v g u + g v 2 g , g (u v )∈E a u v g u + g v 2 ≥ (u v )∈E a u v g 2 u -g 2 v 2 2∆ g , g 2 .
Let 0 = t 0 < t 1 • • • < t m be the distinct values taken by the g v . For i = 0, . . . , m , let

V i = v ∈ V g v ≥ t i . Thus for i > 0, k + 1 / ∈ V i . Let M := (u v )∈E a u v g 2 u -g 2 v = m i =1 (u v )∈E g v <g u =t i a u v g 2 u -g 2 v = m i =1 u :g u =t i v :g v =t j j <i a u v t 2 i -t 2 i -1 + • • • -t 2 j +1 + t 2 j +1 -t 2 j = m i =1 u ∈V i v / ∈V i a u v t 2 i -t 2 i -1 = m i =1 E V i , V i t 2 i -t 2 i -1 ≥ Φ k (G ) m i =1 |V i | t 2 i -t 2 i -1 = Φ k (G ) m i =1 t 2 i (|V i | -|V i +1 |) = Φ k (G ) g , g .
Combined, these results yield

λ 2 ≥ K ≥ Φ k (G ) g , g 2 2∆ g , g 2 = λ * 2 .

Introduction

The Monte Carlo Markov chain (MCMC) scheme is used in many domains, from statistical physics [START_REF] Galvin | Slow mixing of glauber dynamics for the hard-core model on regular bipartite graphs[END_REF] to combinatorial optimization [START_REF] Huber | Perfect sampling using bounding chains[END_REF], to telecommunication networks [START_REF] Shah | Randomized scheduling algorithm for queueing networks[END_REF][START_REF] Jiang | Fast mixing of parallel glauber dynamics and low-delay CSMA scheduling[END_REF] and information theory [START_REF] El | Network information theory[END_REF]. The method often requires solving two problems. The first consists in constructing a Markov chain whose stationary distribution is the target sampling distribution. There exist many techniques to achieve this goal, such as Metropolis-Hastings [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF][START_REF] Hastings | Monte carlo sampling methods using markov chains and their applications[END_REF] and Gibbs sampling [START_REF] Geman | Stochastic relaxation, gibbs distributions, and the bayesian restoration of images[END_REF].

The second is termination. With the classical MCMC algorithm [START_REF] Asmussen | Stochastic Simulation: Algorithms and Analysis[END_REF], the Markov chain is simulated for a predefined number of iterations, after which the current state is returned. Determining the required number iterations consists in computing the mixing time of the Markov chain, something which has proven to be very difficult to do. Other methods, such as the Coupling From The Past (CFTP) algorithm by Propp and Wilson [START_REF] Gary | Exact sampling with coupled Markov chains and applications to statistical mechanics[END_REF], are perfect sampling algorithms: they terminate without the need for any additional parameter, and the output follows the exact target distribution.

One of the key features that makes CFTP a viable algorithm is monotonicity [START_REF] Gary | Exact sampling with coupled Markov chains and applications to statistical mechanics[END_REF]. By using a monotone Markov chain and period doubling, we remove the linear dependency of the running time of the algorithm on the size of the state space. The resulting complexity is then comparable to the mixing time of the Markov chain.

For non-monotonous Markov chains, a similar technique can be used, based on bounding chains [START_REF] Huber | Perfect sampling using bounding chains[END_REF]. By creating a simplified envelope that encompasses all possible trajectories, the above technique can still be used. The efficiency of the resulting algorithm depends on the complexity and tightness of the bounding chain.

We present a new method for reducing the running time of the CFTP algorithm: oracle sampling. With bounding chains, many events do not actually change the state of the chain. In an approach similar to importance sampling, we remove these transitions, focusing only on those that participate in the evolution of this bounding state. In order to preserve the correct stationary distribution, the algorithm must dynamically add random events so as to prevent the appearance of any bias.

Oracle sampling is most efficient when addressing local dynamics, for example when using Gibbs samplers. These are situations in which is sampling transitions is computationally efficient. We test the algorithm on one such model, independent sets, and compare its performance with that of the original CFTP algorithm.

This chapter is organized as follows. Section 2 gives an overview of the basic CFTP algorithm and of the use of bounding chains. Our main contribution is presented in Section 3. We start in Section 3.1 by introducing the notion of active and passive events. Section 3.2 contains a detailed explanation on how to correctly skip events in the context of CFTP, resulting in Algorithm 8. The validity of the algorithm is provided by Theorem 12, which constitutes the main result of this paper. We apply this algorithm in the context of random independent sets in Section 4.

In this section, we give the original coupling from the past algorithm, as introduced by Propp and Wilson [START_REF] Gary | Exact sampling with coupled Markov chains and applications to statistical mechanics[END_REF], as well as some usual variations.

Since CFTP relies on the ability to couple Markov chains, we use a Markov automata representation.

The usual notations are used: * for the set of finite words, ω for the set of infinite words, and ∞ for all finite and infinite words. Words are denoted u i → j = u i , . . . , u j , or the empty word ε if i > j , and the length of a word u is |u |.

To simplify notation, we write x • u i → j for x • u i • . . . • u j . The concatenation of two words u and v is u v , and, for i ≤ j , we denote 1) . . . u (1) .

j k =i u (k ) = u (i ) u (i +1) . . . u ( j ) and i k = j u (k ) = u ( j ) u ( j -
Coupling from the past Recall that, for a grand coupling X x t t ∈ x ∈ with coupling time τ, X x τ is not distributed according to the stationary distribution of the Markov automaton. Coupling from the past consists is constructing a similar sequence which does yield the correct distribution.

Consider a negatively indexed infinite word U -∞→-1 distributed according to D ⊗ . For all x ∈ and i ∈ , let

Y (x ) i = x • U -i • . . . • U -1 = x • U -i →-1
and

S -i = Y (x ) i
x ∈ , which we also denote

S -i = • U -i →-1 .
Call τ b the smallest index such that S -τ b is a singleton. τ b is called the backward coupling time.

For all x ∈ and i ∈ , Y (x ) i can be interpreted as the state at time 0 of the Markov chain starting in x at time -i . τ b is the first instant i such that the grand coupling started at time -i has coupled at time 0.

The CFTP algorithm is based on the following result.

Theorem 11 ([45]). The unique element of S -τ b is almost surely distributed according to π, and

E[τ b ] = E[τ].
Notice also that for all j ≥ i , S -j ⊆ S -i , and namely that the S -i are therefore all equal to S -τ b for i ≥ τ b .

This result can be used to generate samples distributed according π, as illustrated in Algorithm 4. Note that it is important to reuse the previous sequence of letters at each iteration, prepending the newly generated letter; if the whole word is re-sampled, the output of the algorithm is incorrect, as detailed in [START_REF] Häggström | Finite Markov chains and algorithmic applications[END_REF].

The

for x ∈ do Z (x ) ← Y x • U -(i +1) Compute Y i +1 from Y i and U -(i +1) end for Y ← Z until |Y ( )| = 1
Repeat until all Y (x ) are equal return UNIQUEELEMENTOF(Y ( )) end function Bounding chains The above complexity is often limiting: even though Γ (•) is generally a constant, and E[τ] is of order t mix , the size of can be exponentially large. Variants of the CFTP algorithm have been introduced to overcome this dependence on | |. The most common of these is the use of bounding chains [START_REF] Huber | Perfect sampling using bounding chains[END_REF].

Formally, consider a pair ( , •) such that is a subset of the power set of containing , and

• : × → is a transition function which bounds •, in the sense that ∀x ∈ , ∀B ∈ , ∀a ∈ , x ∈ B ⇒ x • a ∈ B • a .
Such a pair is called a bounding chain for A.

As with (S -i ) i ∈ , define (B -i ) i ∈ as

B -i = • U -i • . . . • U -1 = • U -i →-1 .
Notice that, for all i ∈ , S -i ⊆ B -i , which implies that if B -i is a singleton, so is S -i . We can therefore adapt the CFTP algorithm to keep track of the bounding chain (B -i

) i ∈ instead of (S -i ) i ∈ . The complexity of this new algorithm is O E τ 2 B Γ (•)
, where Γ (•) is the complexity of the transition function •, and is generally either constant or logarithmic in the size of the state space . The random variable τ B is the forward coupling time of the bounding chain, i.e. the smallest i such that •U -i →-1 is a singleton. The square factor is due to the fact that B -(i +1) cannot be computed from B -i and U -(i +1) , and the whole chain must therefore be recomputed at each iteration.

This square factor can be overcome by starting from more than one step back in time at each iteration: if the number of prepended letters is doubled at each iteration, rather than adding one unique letter, then the complexity drops down to O (E[τ B ]Γ (•)). This technique is referred to as period doubling [START_REF] Gary | Exact sampling with coupled Markov chains and applications to statistical mechanics[END_REF], and its implementation is given in Algorithm 5.

Note that, in doing this, the final word U -i →-1 may be such that i > τ B . Theorem 11 states that this does not change the output, which is therefore still distributed according to π.

0 -i -2i -4i a i s a c t i v e a i s p a s s i v e a i s a c t i v e • U -4i →-j U -k = a
Notice that the letter U -k = a , is initially active when the bounding chain starts from -i , then passive when starting from -2i , and active again when starting from -4i . The process is not as straightforward as for the forward case, since the state of the bounding chain at a given moment -i changes each time the algorithm starts from further back in time. The letter U -i can therefore be active at first, then become passive later on in the unwinding of the algorithm, then active again, etc. This is illustrated in Figure 4.1.

Removing letters as they become passive is simple enough, but the reverse is not true: letters that were removed or initially skipped must be accounted for when starting the bounding chain from further back in time. Keeping these letters in memory rather than discarding them is not viable, as it would require actually drawing the skipped letters, thereby defeating the purpose of this entire method. We must therefore reinsert such letters back in at random to compensate for their removal.

Recall, however, that re-sampling previously generated letters in the classical CFTP algorithm yields incorrect results in most cases. We must therefore be careful when inserting new letters, taking care to compensate for the inherent bias this introduces so as to ensure that the output is still distributed according to π.

Geometric increments

To achieve this, we rely heavily of the use of geometric increments for the word lengths. The memoryless property of the geometric distribution is vital due to the following observation: suppose that the initial word U -i →-1 was distributed according to G p ; the probability of a letter having been removed after a given positionj only depends on • U -i →-j and p , not on the actual letters drawn before or after, nor on the length of the word.

One caveat is that, when running the geometric CFTP algorithm, the parameter p is not the same throughout the word used to generate the bounding chain. In order to be able to keep track of which parameter was used to generate each portion of this word, we rely on the presence of the letter , which delimits portions of the word that were generated using a same parameter. Note that these must never be removed or reinserted once added to the word. They are therefore treated as active letters throughout the algorithm, despite the fact that they do not modify the state of the bounding chain: ∀B ∈ , ∈ B + .

is independent of what comes after this . We can therefore construct a coupling between

[U ] B B p and [V ] B B p such that [U ] B B p = [V ] B B p . Using Property 12, we have that [V ] B B p is distributed according to D ⊗ p , and [U ] B B
p is therefore distributed according to G p . Finally, using the same argument as in the previous proof,

[U ] B = [V ] B = [V ] B B p B = [U ] B B p B , from which we can conclude that U B ≡ [U ] B B p .
Property 14 (Equivalence in the case of R n ). Let n ∈ , B ∈ be a bounding state, and U be distributed according to R n . Contracting then expanding from B yields an equivalent word with respect to B :

[U ] B B B ≡ U .
Proof. We first point out some simple preliminary results. Let B ∈ , n ∈ and (u (i ) ) n≥i ≥1 , (v (i ) ) n≥i ≥1 be two sequences of words in ∞ .

1. For all m such that n > m ≥ 1, contraction and concatenation can be interchanged as follows:

m i =n u (i ) B = m i =n u (i ) B • i +1 j =n u ( j ) . ( 4.3)
2. If each u (i ) ends with its only , then expansion and concatenation can also be swapped by using 2 -i -expansions:

1 i =n u (i ) B = 1 i =n u (i ) B • i +1 j =n u ( j ) 2 -i . ( 4.4)
3. Finally, if, for all n ≥ i ≥ 1,

u (i ) B • i +1 j =n u ( j ) ≡ v (i ) ,
then the concatenations are equivalent:

1 i =n u (i ) B ≡ 1 i =n v (i ) . ( 4

.5)

Consider the unique decomposition

U = 1 i =n U (i )
such that, for all i , U (i ) ends with its only . By construction of R n , each U (i ) is distributed according to G 2 -i . Using the above results and Property 13, we have that

We now move on to prove the correctness of the algorithm.

A rapid induction shows that the U (n) are distributed according to R n :

U (n+1) = V (n+1) U (n) •V (n +1) = V (n +1) 2 -(n+1) U (n) •V (n +1) •V (n +1) ≡ V (n+1) G 2 -(n +1) U (n) R n
The two elements in the last line being independent, U (n+1) is distributed according to R n+1 . Notice however that it is not equivalent to

1 i =n+1 V (i ) , since U (n ) is expanded from , not • V (n+1) . More importantly, U (N ) itself is not distributed according to R N , as N is defined in such a way that • U (N ) is necessarily a singleton.
Let > 0, and n be an integer such that P(N > n ) < . Since U (n ) is distributed according to R n , removing the from U (n+1) results in a random word W whose letters are i.i.d. according to D , and whose length is independent of these letters. Consider a state Y distributed according to π. Since every state is invariant under

x → x • , we have that Y • U (n ) = Y • W , which is distributed according to π. We also have that Y • U (n ) ∈ • U (n ) = • U (n ) . As such, if ever • U (n )
is a singleton, then its unique element is distributed according to π. For any n ∈ , notice that

• U (n+1) = • V (n+1) • U (n) ⊆ • U (n) ( • V (n+1) ⊆ ) = • U (n ) . A direct consequence of this is that, whenever N ≤ n , • U (n ) ⊆ • U (N ) . Since • U (N )
is a singleton, and • U (n ) cannot be the empty set, we even have equality. Since N ≤ n holds with probability at least 1 -, and since the unique element of • U (n ) is distributed according to π, we then have that the output of the Oracle CFTP algorithm is correctly distributed with probability at least 1 -. This being true for all > 0, the proof is complete.

Complexity

When considering a specific Markov automaton, it is a common practice to bound the complexity of the CFTP algorithm for that specific usage. For the base CFTP algorithm, Theorem 11 states that E[τ b ] = E[τ]. This makes it possible to bound the complexity of the original algorithm by bounding the forward coupling time of the Markov automaton. While this still holds when using bounding chains with constant or geometric increments (so long as the forward coupling time is computed for the transition function • rather than •), it is no longer valid when considering oracle sampling.

To better understand the extra difficulty, consider the following toy example: a Markov automaton with = {x 0 , x 1 } and = {s , z }, such that

• x i • s = x 1-i (swap states); • x i • z = x 0 (go to zero); • D (z ) = (z is a rare letter).
The bounding chain is defined as

• {x 0 , x 1 } • s = {x 0 , x 1 } (
s is passive so long as we have not coupled);

• {x 0 , x 1 } • z = {x 0 } (z means coupling); • {x i } • s = {x 1-i } (s is active once we have coupled); • {x i } • z = {x 0 }.
With oracle sampling, the forward coupling time is 1: since s is passive, we draw z , and we have automatically coupled. For Oracle CFTP, i.e. the backward coupling time, we have to go back until we can find a z . At this point, s becomes active, and the expansion phase adds approximately -1 occurrences of s . The complexity is therefore of order -1 . This illustrates how there can be an arbitrarily large factor between forward and backward coupling times for oracle sampling.

The key observation is the above example is that, whereas the forward coupling time only depends on the quality of contraction for uncoupled states (|B | > 1), the backward coupling time must also take into account the quality of contraction after coupling (when B is a singleton). Property 15. Let γ(n ) ≥ max x ∈ E [U 1→n ] {x } be an upper bound on the expected contracted size of a random word of length n . The running time Γ O of the algorithm satisfies

E[Γ O ] = O E[τ O ] + E γ(τ B ) + log(E[τ B ]) × log(E[τ B ]) ,
where τ O and τ B are the forward coupling times of the bounding chains with and without oracle sampling. Sketch of proof. Notice that the complexity at each iteration n of the algorithm is linear in the number of letters of V (n) : each letter is read at most once, as well as being possibly added or removed only once. We can therefore state that the overall complexity Γ O of the algorithm satisfies

E[Γ O ] = O E N n=1 V (n) .
The expected length of the V (n) is increasing, and it can be shown that

E[N ] = E V (N ) ≤ log(E[τ B ]),
from which we deduce that

E[Γ O ] = O E V (N ) × log(E[τ B ]) . 0 τ O ≤ γ(τ B ) V (N )
The final coupling word V (N ) can be split into a coupling subword (left) and a coupled subword (right). ) can be split into a coupling subword, whose length is upper-bounded by τ O , and a coupled subword, whose length is at most γ(τ B ). Adding the number V (N ) of occurrences of the letter , which we have omitted so far, we get that

E V (N ) ≤ E[τ O ] + E γ(τ B ) + log(E[τ B ]).
Note the implications of the term log(E[τ B ]): though this is only an upper bound, it suggests that the complexity of the oracle CFTP algorithm is at least logarithmic in the complexity of the initial bounding chain algorithm.

Variants of Oracle Sampling

Incremental Sampling Though oracle sampling is a convenient model from a theoretical standpoint, we have underlined the issue of sampling active letters when implementing such a method. A more convenient approach, similar to what was introduced in [START_REF] Pin | Acceleration of perfect sampling by skipping events[END_REF], is to discover passive events as they are drawn; this is referred to as incremental sampling.

The basis for incremental sampling is to construct the distribution D i from which V i is to be drawn using what we have learned from the previous letters:

• If V i -1 was active, D i is reset to D, since the state of the bounding chain has changed and we do not know which letters are active or passive anymore;

• If V i -1 was passive, D i is taken to be D i -1 conditioned on not being V i -1 , i.e. V i -1 is removed from the set of known passive letters.

The new bounding chain B I i i ∈ defined by B I i = •V 1→i for all i ∈ is no longer a Markov chain, but it can nonetheless be used in CFTP to sample from π. Its coupling time τ I is a trade-off between that of the usual bounding chains and that of oracle sampling:

E[τ O ] ≤ E[τ I ] ≤ E[τ].
Hybrid Sampling It is possible to combine oracle and incremental sampling to improve performance or simplify implementations. For example, if it is easy to acquire a subset of the passive letters for a given state, then these can be immediately removed from the distribution when the bounding chain changes to that state. On the contrary, if a letter is known to rarely be passive, we can choose to never check whether it is active or not and always keep it in the distribution.

Independent Sets

Let G = (V , E ) be a simple undirected graph. Recall that a subset I of V is called an independent set if no two vertices in I are connected by an edge, i.e. if ∀x , y ∈ I , x , y / ∈ E .

Let be the set of independent sets of G and, for any vertex v ∈ V , denote N (v ) the set of neighbors of v , that is to say the w ∈ V such that (v, w ) ∈ E .

We study the performance of the CFTP algorithm with oracle sampling when generating independent sets according to the distribution

P λ (I ) = λ |I | Z λ , λ ∈ ,
where Z λ is a normalizing constant, often called the partition function. We focus on the case where λ is very large. In the spirit of Property 15, we restrict our analysis to the complexity for the forward coupling.

Sampling algorithms

We compare the coupling time our sampling algorithm with oracle sampling with two other approaches described in [START_REF] Huber | Perfect sampling using bounding chains[END_REF]: Gibbs sampling and the Dyer-Greenhill chain [START_REF] Dyer | On Markov chains for independent sets[END_REF].

Gibbs sampling

Let us first define a Gibbs sampler for P λ . At each iteration, independently draw a vertex v uniformly at random and u uniformly over [0, 1].

• If u > λ λ+1 , then remove v from I if v ∈ I , otherwise do nothing.

• If 0 ≤ u ≤ λ λ+1 , then add v to I if N (v ) ∩ I = , otherwise do nothing.

This dynamics allows us to use Monte Carlo and CFTP methods to generate independent sets according to P λ . The CFTP approach can be greatly improved by using the following bounding chain for the Glauber dynamics defined in [START_REF] Huber | Perfect sampling using bounding chains[END_REF]. we have that A ⊆ 〈B , D 〉. In other words, B is the set of vertices common to every independent set in A, C is the set of vertices that are in none of the independent sets of A, and D is the set of vertices that are in some but not all of the independent sets of A. The couples (〈B i , D i 〉) i ∈ define a bounding chain for the Glauber dynamics (A i ) i ∈ . The initial state of this bounding chain is 〈B 0 , D 0 〉 = 〈 , V 〉.

The Gibbs sampler for the bounding chain is defined as follows: at each iteration, independently draw a vertex v uniformly at random and u uniformly over [0, 1]. Suppose the initial state is 〈B , D 〉, and write B + v for B ∪ {v } and Bv for B \ {v }; the arrival state 〈B , D 〉 is constructed as follows:

• If u > λ λ+1 , we remove v from all independent sets:

B = B -v D = D -v C = C + v • If 0 ≤ u ≤ λ λ+1
, we attempt to add v to the independent sets:

if N (v ) ∩ B = , then we do nothing (we necessarily have that v ∈ C ); -if N (v ) ⊆ C , we can add v to all independent sets:

B = B + v D = D -v C = C -v
otherwise, we can only add v to some independent sets:

D = D + v C = C -v
The Dyer-Greenhill scheme

The coupling time of the above bounding chain can be reduced through the Dyer-Greenhill scheme. The main idea is to allow one element to slide to an adjacent feasible vertex. Given p s ∈ [0, 1], if, in the Gibbs sampler, an attempt to add v to the independent set I fails due to the presence of a unique neighbor u already in I , then with probability p s , the independent set becomes I + vu . A bounding chain can easily be defined for this new scheme.

Oracle sampling scheme

Now consider oracle sampling for the bounding chain of the Gibbs sampler. For each vertex v , we have two events: adding v to I , denoted a v , and removing v from I , denoted r v . The active events are:

• the r v for which v / ∈ C ,

• the a v for which v ∈ C and N (v ) ∩ B = ,

• the a v for which v ∈ D and N (v ) ⊆ C .

Let V r and V a be the set of vertices for which removal and addition are respectively active in 〈B , D 〉. For the Gibbs sampler, events are drawn according to the conditional distribution by picking an event uniformly at random in V z , where z = a with probability λ|V a | λ|V a | + |V r | , and z = r otherwise. For a vertex v ∈ V , the fact that a v and r v are active is only modified when v , or one of its neighbors, is modified. It is therefore possible to locally update the conditional distribution at each iteration by simply updating the "activeness" of events for the modified vertex and its neighbors. This justifies using oracle sampling rather than incremental sampling in this context.

Note that those three samplers can be adapted to the case of weighted vertices and product-form stationary processes of the form

P Λ (I ) = 1 Z Λ v ∈I λ(v ),
where Λ = (λ v ) v ∈V is a weight-vector of the vertices. For the Gibbs sampler, λ is replaced by the λ(v ) of the selected vertex. The other samplers are modified accordingly.

Star graph

In this paragraph, we study the graph G n = 0, n , (0, i ) i ∈ 1, n , called star graph. We focus mainly on the performance of the oracle sampling scheme for large values of λ, such as when λ n . The independents of this graph are = {{0}} ∪ 1, n .

First, we consider the coupling time τ B of the Glauber dynamics of the bounding chains without oracle sampling, both in the case of the Gibbs sampler and of the Dyer-Greenhill sampler.

Since at most one vertex is removed from D at each iteration, and the algorithm finishes when D = , this coupling time is lower bounded by the hitting time of {〈B , {0}〉} ∪ {〈B , D 〉 | 0 / ∈ D }.

Furthermore, since no vertex can be added to B so long as D contains both 0 and an element in 1, n , B = until one of those states is reached.

In the case of the Gibbs sampler, if λ > 1, the expected hitting time of 〈 , {0}〉 is O (λ n ). Furthermore, before reaching this state, the probability of removing 0 from D is exactly This is due to the fact that the first attempt to swap a vertex other than 0 will immediately remove 0 from D , since it is the only neighbor of the selected vertex. On the other hand, for the bounding chain to couple, every vertex must be selected at least once for addition or removal. As at each step, the modified vertex is chosen uniformly and independently at random Let us first focus on the hitting time of {〈B , D 〉 | 0 / ∈ D }. Construct a birth-anddeath process on 0, n , where state i represents the cardinal of C , supposing 0 has not yet been added to C . In state i , the active events are those that move vertices between D and C . As a consequence, the probabilities p i ,i +1 and p i +1,i to go respectively from state i to state i + 1 and from i + 1 to i are given by p i ,i +1 = ni ni + i λ and p i +1,i = (i + 1)λ ni -1 + (i + 1)λ . (4.7)

Computations show that the stationary distribution π of this birth-and-death process satisfies, for all i ∈ 0, n ,

π(i ) = n -1 i -1 λ -(i -1) + n -1 i λ -i π(0).
This yields that π(0)

≥ 1 2 1 + 1 λ -n .
The bounding chain can be bounded by the following process: when in state 0, vertex 0 can be removed with probability 1 n +1 (all events are active for removal, none for addition). Keeping in mind that λ ≥ n , the expected time τ 1 for reaching a state 〈B , D 〉 where 0 / ∈ D is therefore

E[τ 1 ] = (n + 1) π(0) ≤ 2e (n + 1).
For the second step, consider the birth-and-death process on 0, n where state i represents the sets 〈B , D 〉 for which |B | = ni and 0 / ∈ D . For i > 0, i vertices are active for addition and at least ni are active for removal. The transitions probabilities are exactly the probabilities p i , j defined in Eq. (4.7).

Simple computations show that the hitting time τ 2 of state 0 from state n satisfies Finally, note that in state n , vertex 0 is active for addition, and in case this event is generated (which happens with probability 1 n+1 ), we have to take into account the return time from the first step (0 ∈ D ) to the second step (0 / ∈ D ). By the Markov inequality, the probability that state n is visited again before state 0 is at most π(n) π(0) = λ -n . As a consequence, the expected coupling time satisfies Notice that the coupling time does not depend on λ and is linear in n . It therefore does better than the other samplers presented above.

Numerical experiments

We now do an experimental comparison of the three samplers described in Section 4.1 for two models: the star graph, that has been precisely analysed in Paragraph 4.2, and the Barabási-Albert model [START_REF] Albert | Statistical mechanics of complex networks[END_REF].

Star graph

We performed experiments for a star graph with 100 vertices and for different values of λ. For each value of λ and each sampler, 1000 experiments have been performed, and the average number of transitions computed is depicted in Figures 4. The first remark is that both Dyer-Greenhill and oracle sampling samplers outperform the Gibbs sampler. Second, the Dyer-Greenhill sampler seams insensitive to the value of λ, which conforms to the bound n ln n + O (1) given in Section 4.2. Finally, the oracle sampling scheme is always the most efficient algorithm. It is noticeable that the number of event generated decreases with λ. This can be explained the following way: large independent sets are favored when λ grows. Then, after reaching the independent set 1, n , whose probability grows with λ, the probability that the next event is active is less than 1 1+λ . As a consequence, many events are skipped.

The difference in behavior between the Dyer-Greenhill and oracle sampling samplers is more obvious with the star graph with 1000 vertices, as depicted in

Barabási-Albert model

We now generate a random graph with preferential attachment. Start from a clique with 5 vertices and at each step add one new vertex v and two edges (v, w 1 ) and (v, w 2 ), where w 1 and w 2 are chosen at random with probability proportional to their degree. Figure 4.6 compares the average number of events generated for 100 experiments with the three samplers, for graphs with 100 vertices. Similarly to the star graph, Dyer-Greenhill and oracle sampling samplers outperform the Gibbs sampler, and the oracle sampling sample is sensitively better than the Dyer-Greenhill one. For large values, those two samplers are not sensitive to λ (or slightly improve when λ grows).

Résumé

Cette thèse porte sur la rapidité du temps de mélange de chaînes de Markov sur des graphes.

La contribution principale concerne les graphes avec des dynamiques locales sur les arêtes, la topologie du graphe évoluant au fur et à mesure que les arêtes glissent les unes le long des autres. Nous proposons une classification des différents modèles existants de graphes dynamiques, tout en illustrant l'importance des transitions le long d'une structure mouvante pour améliorer la vitesse de convergence. Cette étude est complétée par la preuve, pour l'une de ces dynamiques, d'un temps de mélange rapide. Nous définissons notamment l'expansion partielle d'un graphe. Celle-ci permet de suivre l'avancement de la dynamique, partant d'un état de faible expansion, jusqu'à obtention d'une bonne expansion à l'équilibre.

La fin de cette thèse porte sur une amélioration de l'algorithme de simulation parfaite de Propp et Wilson. Nous introduisant un oracle pour les transitions, inspiré de l'échantillonnage préférentiel, qui permet de réduire la complexité de l'algorithme. Nous fournissons une preuve de correction, ainsi qu'une étude de l'impact de cette méthode sur la vitesse d'échantillonnage d'ensembles indépendants pour certains graphes.

Mots Clefs

Réseaux sociaux Graphes dynamiques Chaînes de Markov

Figure 1 . 1 -

 11 Figure 1.1 -Discrete and Continuous Time Birth-and-Death Processes

Figure 1 . 2 -

 12 Figure 1.2 -Bi-color local dynamic model

  .

  3.

Figure 1 . 3 -

 13 Figure 1.3 -Swapping two red pointers along a blue edge (red phase)

Figure 2 .

 2 Figure 2.2 -Exponential Graphs

Figure 2 . 3 -

 23 Figure 2.3 -The Peer-to-Peer Model

Figure 2 . 7 -

 27 Figure 2.7 -Static Ring (dashed) with Permutation

Figure 2 . 9 -

 29 Figure 2.9 -Local Dynamic

5 Permutations with i = 4 Figure 2 . 10 - 1 -

 542101 Figure 2.10 -Static Ring (dashed) with Cycle

Theorem 5 .

 5 Let M = N log N and p = 2 log N N -1 , such that the expected number of edges in the (N , p ) model is M .

Figure 2 . 11 -

 211 Figure 2.11 -The 4-Regular Non-Local Interchange Process

5 Controlling the mean 5 . 1

 51 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Proof of expansion at equilibrium . . . . . . . . . . . . . . . . Small sets: from partial expansion to partial spread . . . 5.2 Large sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  furthermore maintains two pointers, one blue and one red, with respective destinations b n , r n in [N ]. The destinations of the pointers are such that (b n ) n∈[N ] and (r n ) n ∈[N ] are permutations: each node n is the destination of exactly one blue pointer and one red pointer. The blue edges and red edge sets are respectively E b = {(n, b n ) | n ∈ [N ]} and E r = {(n, r n ) | n ∈ [N ]}. All edges are considered to be unoriented.

Figure 3 . 1 -

 31 Figure 3.1 -Bi-color pointer interchange model

Figure 3 . 2 -

 32 Figure 3.2 -Swapping two red pointers along a blue edge (red phase)

9

 9 Results are mentioned in the sections in which they are proved.

Figure 3 . 3 -

 33 Figure 3.3 -Outline of proof

  by contradiction, and assume that there exists t ∈ + and i ∈[N ] for which δ i (t ) > 0. Let δ(t ) = sup δ j (t ) j ∈ [N ] .As the π j are sorted in decreasing order, one also hasδ(t ) = sup δ j (t ) j ∈ [k + 1] .Since the δ j (t ) are linear combinations of finitely many exponentials, we can then identify an interval J = [a , b ] such that on J , for some i ∈ [k +1], δ(t ) = δ i (t ), and moreover δ(a ) = 0 and δ(t) > 0 for t ∈ (a , b ]. Assume that i ∈ [k ].From expression (3.11), we see that on J , d dt δ = d dt δ i ≤ 0. This contradicts the fact that δ > 0 on (a , b ].

Lemma 9 .

 9 Given a graph G on vertex set [N ] with maximal degree ∆ and for fixed k ≤ N 2 , associated isoperimetric constant Φ k (G ), consider the graph G obtained by collapsing Nk nodes into a single node as previously described. Then the resulting Laplacian matrix L has spectral gap at least λ 2 ≥ λ * 2 , where λ * 2 := Φ k (G ) 22∆ .

Algorithm 4

 4 complexity of this algorithm is O (E[τ]| |Γ (•)), where Γ (•) is the complexity of the transition function •. Coupling From the Past (CFTP) function CFTP(( , , D , •)) for x ∈ do Y (x ) ← x Initialize Y 0 , which is the identity vector end for repeat U -(i +1) ← DRAW(D) Draw a new random letter U -(i +1)

Figure 4 . 1 -

 41 Figure 4.1 -Letters can change between being active and passive

Figure 4 . 3 -

 43 Figure 4.3 -Bounding Complexity

  Consider a family of independent setsA ⊆ . Set B = I ∈A I , D = I ∈A I \ B and C = I ∈A (V \ I ) = V \ (B ∪ D ). Denoting 〈B , D 〉 = {I ∈ | B ⊆ I ⊆ B ∪ D },

1 (

 1 λ+1)(n+1) at each time step. For n large enough, this gives thatE[τ B ] ≥ (n + 1)(λ + 1).For the Dyer-Greenhill sampler, the coupling time τ D G B is greatly reduced: the hitting time H of {〈B , D 〉 | 0 / ∈ D } has expectation

  , a coupon collector argument gives that E τ D G B ≥ n ln n + O (1). Now, let us consider the (forward) coupling time τ O of the coupling chain with oracle sampling. The coupling time is at most the hitting time of 〈B , 〉. We have two main steps to consider: 1. The hitting time of {〈B , D 〉 | 0 / ∈ D };2. From there, the hitting time of {〈B , 〉}.

E[τ 2

 2 ] = 1 + λ λ n + n ≤ n + e n λ = n + O (1).

E

  [τ O ] ≤ E[τ 1 ] + E[τ 2 ] + O (1) ≤ (2e + 1)n + O (1).

4

 4

  .

Figure 4 . 4 -

 44 Figure 4.4 -Number of events generated by CFTP algortihms for the star graph with 100 vertices for different values of λ.

Figure 4 . 5 (

 45 100 experiments are run for each value of λ).

Figure 4 . 5 -

 45 Figure 4.5 -Number of events generated by CFTP algortihms for the star graph with 1000 vertices for different values of λ.

Figure 4 . 6 -

 46 Figure 4.6 -Number of events generated by CFTP algortihms for the Barabási-Albert model with 100 vertices for different values of λ.

1 Introduction 2 The Zoo 2

.1 The Erdős-Rényi Dynamic . . . . . . . . . . . . . . . . . . . . . . 2.2 Exponential Random Graphs . . . . . . . . . . . . . . . . . . . . 2.3 Pointer Models for Peer-to-Peer and Social Networks . . 2.4 Sliding Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 The Interchange Process . . . . . . . . . . . . . . . . . . . . . . . 2.6 Static Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Dynamic Triangulations . . . . . . . . . . . . . . . . . . . . . . . 3 Genotypes and Phenotypes 3.1 Genotypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Phenotypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Case Analysis 4.1 Erdős-Rényi dynamic . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 The Interchange Process . . . . . . . . . . . . . . . . . . . . . . . 4.3 Pointers on Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  and such that each edge e of G is crossed by at most18 d 2 γ 2 N log 2 N paths.Proof. The celebrated Cheeger's inequality (see e.g. Berestycki [6] Theorem 3.5, p. 30) ensures that the spectral gap for the discrete time random walk on a ∆-

Remerciements

We now formally define the removal and insertion operations, referred to as contracting and expanding.

Random increments

The period doubling technique can be generalized. One possible modification is to randomize the number of new letters at each iteration. We present here the case of geometrically distributed increments, as it will serve for the basis of our own algorithm.

Fix a probability p . We extend the alphabet by adding a new letter, , which serves as a delimiter. The new alphabet is denoted . Call D p the distribution over such that D p = p and, for all a ∈ , D p (a ) = 1p D(a ). Enhance the transition operators • and • so that x • = x and B • = B . Finally, let |u| denote the number of occurrences of the letter in u .

Drawing letters i.i.d. according to D p until a is drawn gives a word of geometric length, whose letters are i.i.d. according to D (with the exception of the final ). The distribution of this word is denoted G p .

We can prepend such words during our algorithm, halving p at each iteration, to obtain a CFTP algorithm with geometric increments. The word used at the n -th iteration of the algorithm is therefore of the form U (n) = 1 i =n V (i ) , with the V (i ) independently distributed according to G 2 -i , and its distribution is denoted R n .

If the are omitted in the increments, then the sequence of letters at each iteration is i.i.d. according to D, so the final output is distributed according to π. Since the do not change the state of the chain, including them in the increments does not change the output of the algorithm, nor its distribution. Though including these may seem unnecessary, their presence is essential in our own algorithm, so we include them here.

The CFTP algorithm with geometric increments is given in Algorithm 6. Its complexity is the same as that for deterministic increments:

Oracle Sampling

In this section, we present our contribution: a variation of the CFTP algorithm based on a technique similar to that introduced in [START_REF] Pin | Acceleration of perfect sampling by skipping events[END_REF], called oracle sampling. Just like regular CFTP, this method allows us to sample random variables according to a stationary distribution π. However, the overall complexity of the algorithm can be arbitrarily smaller, depending on the Markov automaton. This is illustrated in Section 4.

This gain is achieved by sampling only "active" letters throughout the algorithm, i.e. letters which modify the state of the bounding chain.

Oracle Sampling with Bounding Chains

We first consider a simple "forward" bounding chain, outside of the context of the CFTP algorithm: let U 1→+∞ be distributed according to D ⊗ , and (B i ) i ∈ be the bounding chain such that ∀i ∈ , B i = • U 1→i .

We say a letter a is passive with respect to B i if B i • a = B i , and that it is active otherwise. Let B i + be the set of active letters with respect to B i , and

-the set of passive letters.

Consider a new sequence V 1→+∞ such that the

, but has a smaller coupling time τ O . This gain in speed comes at a price, however, as the limit distribution of the asymptotically unique element of B O i i ∈ is no longer π. This method of speeding up convergence is referred to as oracle sampling. The term "oracle" is due to the fact that we consider sampling active letters to have constant complexity, a strong assumption requiring namely that the set of active letters be known at each step.

Oracle Sampling in CFTP

We now adapt the CFTP algorithm to make use of oracle sampling.

Contracting Contracting a word consists in removing all the passive letters from that word. Given a state of the bounding chain B ∈ and a word u ∈ ∞ , the contraction of u from B is the word [u ] B defined recursively by

Expanding Expansion is the key feature of this paper. It inserts letters at random in a contracted word in a way that preserves the stationary distribution of the output of the CFTP algorithm. Consider a state B ∈ and a word u ∈ * ending with . The expansion of u from B is the random word 〈u 〉 B defined recursively by

Contraction and expansion are illustrated in Figure 4.2. Notice that both of these operations preserve transitions from B : The geometric CFTP algorithm enhanced with these features is given in Algorithm 7. At each iteration of the outer loop, a contracted prefix V is drawn, to which we attach an expansion of the previous word U . The result is then contracted. The proof that this algorithm does indeed return a sample distributed according to π is not straightforward, and constitutes the main result of this paper, stated in Theorem 12.

Algorithm 7 Geometric CFTP with Contraction and Expansion

Rerooting One downside of Algorithm 7 is that the word U is expanded at each iteration. However, in order to have oracle sampling actually reduce the overall complexity of the algorithm, it is important to always work with contracted words. We therefore introduce one last operation, rerooting, which combines contraction and expansion so as to never fully expand the word being processed.

Formally, consider two states B , B ∈ . Rerooting a word u ∈ ∞ ending in from B to B consists in computing

so as to never fully expand u. One way to do this is to define [ 〈u 〉] B B recursively as follows:

Then -If A ∈ B -(and therefore A ∈ B + ), we expand:

+ , u i is active for both chains, so we keep it:

-, u i is no longer active, so we contract:

Notice that letters passive for both B and B are not drawn. This would correspond to adding and removing the same letter, as is the case when we expand and contract separately. The conditional distribution ensures this does not happen, and that the complexity is linear in the size of the contracted word (the first case can arise at most once per letter in [ 〈u 〉] B B , the other two at most once per letter in u ).

Once more, we make the strong assumption that we can draw random variables from distributions such as

in constant time. This is not unreasonable, especially in cases such as Gibbs sampling [START_REF] Geman | Stochastic relaxation, gibbs distributions, and the bayesian restoration of images[END_REF], where at most a constant number of letters can change between being active and passive at each step.

The final algorithm is given in Algorithm 8.

The rerooting occurs here

Proof of Correctness

We now prove the correctness of Algorithm 8.

Equivalence with Respect to B One of the key tools of this proof is the use of the following equivalence: given a bounding state B ∈ , two random words U and V are considered equivalent with respect to B if they have the same distribution and the same contractions from B (i.e.

The motivation behind the precise definition of expansion is the following: given a word U , distributed according to R n , and a bounding state B ∈ , con-tracting then expanding U gives an equivalent word with respect to B :

We begin by showing a similar equivalence when U is distributed according to D ⊗ p , for any fixed p . From there, we extend the result to G p , and finally to R n . The definition of expansion in the previous section was specifically tailored to work with the distribution R n . To show the first two results, we therefore generalize expansion to operate on words with a fixed rate of occurrences of the letter , as is the case when sampling from D ⊗ p . For any probability p and bounding state B , the p -expansion 〈u 〉 B p of u ∈ ∞ from B is defined recursively by

We now show the following result:

Property 12 (Equivalence in the case of D ⊗ p ). Let p be a fixed probability, B ∈ be a bounding state, and U be distributed according to D ⊗ p . Contracting then p -expanding from B yields an equivalent word with respect to B :

p , n ∈ and u 1→n ∈ A n . We have that

If we can show that, for all i ∈ ,

then we have that, for all n ∈ , V 1→n is distributed according to D ⊗n p , and we can therefore conclude that V is distributed according to D ⊗ p . We now show (4.2) by conditioning on whether V i is or is not in

if and only if it was added during expansion. By definition, this occurs with probability D p B •u 1→i -1 -, so we have that

.

Consider the case where V i is passive. It was inserted during expansion, and its distribution is therefore the restriction of D p to

Similarly, if V i is known to be active, then it was already in U and was not removed during contraction. Its distribution was therefore D p , conditioned on being in

Combining all these results gives that

This concludes the proof that V is distributed according to D ⊗ p , i.e. has the same distribution as U .

To finish, notice that

. Since the outer contraction removes all the letters added during expansion (they are by definition passive), and none of the letters present before that ([U ] B contains only active letters), we have that

We now extend this result to words of geometric lengths.

Property 13 (Equivalence in the case of G p ). Let p be a fixed probability, B ∈ be a bounding state, and U be distributed according to G p . Contracting then p -expanding from B yields an equivalent word with respect to B :

Proof. For any word u, denote u the truncation of u after the first occurrence of the letter . Notice that U can be constructed by taking an infinite random word V distributed according to D ⊗ p , and setting U = V . Since both contracting and p -expanding operate recursively from left to right, what letters are removed or added before the first when going from

Eq. (4.4)

Eq. ( 4.3)

Eq. (4.1)

Prop. 13

Eq. (4.5)

which concludes the proof.

Convergence and distribution

We now go back to proving the correctness of Oracle CFTP. Recall that the algorithm operates by iteratively computing

where the V (i ) are independent and distributed according to G 2 -i . The algorithm terminates when U (N ) is such that • U (N ) is a singleton {X }, returning X .

Theorem 12. If there exists u ∈ * such that • u is a singleton, then 1. Oracle CFTP terminates: N is a.s. finite and of finite expectation; and 2. Oracle CFTP is correct: X is distributed according to π.

Proof. We begin by proving that Oracle CFTP terminates. Let u ∈ * be such that • u is a singleton. Notice that, for any n ∈ , if V (n) begins with u , then •U (n) is a singleton, and therefore N ≤ n . The probability that u is a prefix of V (n) is equal to the probability that there are no in the first |u | letters, i.e. at least 2 -|u| , times the probability of these letters being those of u knowing they are not , D ⊗|u | (u ):

Such an event will necessarily happen, and N is therefore a.s. finite. Its expectation is furthermore upper-bounded by

.

Abstract

This thesis focuses on the rapid mixing of graph-related Markov chains.

The main contribution concerns graphs with local edge dynamics, in which the topology of a graph evolves as edges slide along one another. We propose a classification of existing models of dynamic graphs, and illustrate how evolving along a changing structure improves the convergence rate. This is complemented by a proof of the rapid mixing time for one such dynamic. As part of this proof, we introduce the partial expansion of a graph. This notion allows us to track the progression of the dynamic, from a state with poor expansion to good expansion at equilibrium.

The end of the thesis proposes an improvement of the Propp and Wilson perfect sampling technique. We introduce oracle sampling, a method inspired by importance sampling that reduces the overall complexity of the Propp and Wilson algorithm. We provide a proof of correctness, and study the performance of this method when sampling independent sets from certain graphs.