Anna Ben-Hamou

Justin Salez

CUTOFF FOR NON-BACKTRACKING RANDOM WALKS ON SPARSE RANDOM GRAPHS

A finite ergodic Markov chain is said to exhibit cutoff if its distance to stationarity remains close to 1 over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Discovered in the context of card shuffling (Aldous-Diaconis, 1986), this phenomenon is now believed to be rather typical among fast mixing Markov chains. Yet, establishing it rigorously often requires a challengingly detailed understanding of the underlying chain.

Here we consider non-backtracking random walks on random graphs with a given degree sequence. Under a general sparsity condition, we establish the cutoff phenomenon, determine its precise window, and prove that the (suitably rescaled) cutoff profile approaches a remarkably simple, universal shape.

Introduction

is even, we construct a graph G with vertex set V and degrees (deg(v)) v∈V as follows. We form a set X by "attaching" deg(v) half-edges to each vertex v ∈ V :

X := {(v, i) : v ∈ V, 1 ≤ i ≤ deg(v)}.
We then simply choose a pairing π on X (i.e., an involution without fixed points), and interpret every pair of matched half-edges {x, π(x)} as an edge between the corresponding vertices. Loops and multiple edges are allowed. if y is a neighbour of π(x) 0 otherwise.

In this definition and throughout the paper, two half-edges x = (u, i) and y = (v, j) are called neighbours if u = v and i = j, and we let deg(x) := deg(u) -1 denote the number of neighbours of the half-edge x = (u, i). In words, the chain moves at every step from the current state x to a uniformly chosen neighbour of π(x).

x (x) u v

Figure 3. The non-backtracking moves from x (in red)

Note that the matrix P is symmetric with respect to π: for all x, y ∈ X , P (π(y), π(x)) = P (x, y). [START_REF] Aldous | Random walks on finite groups and rapidly mixing Markov chains[END_REF] In particular, P is doubly stochastic: the uniform law on X is invariant for the chain. The worst-case total-variation distance to equilibrium at time t ∈ N is

D(t) := max x∈X    1 2 y∈X P t (x, y) - 1 N    . ( 3
)
D is non-increasing, and the number of transitions that have to be made before it falls below a given threshold 0 < ε < 1 is known as the mixing time:

t mix (ε) := inf {t ∈ N : D(t) < ε} .
1.2. Result. The present paper is concerned with the typical profile of the function t → D(t) under the so-called configuration model, i.e. when the pairing π is chosen uniformly at random among the (N -1)!! possible pairings of X . In order to study large-size asymptotics, we let the vertex set V and degree function deg : V → N depend on an implicit parameter n ∈ N, which we omit from the notation for convenience. The same convention applies to all related quantities, such as N or X . All asymptotic statements are understood as n → ∞. Our interest is in the sparse regime, where the number N of half-edges diverges at a much faster rate than the maximum degree. Specifically, we assume that

∆ := max v∈V deg(v) = N o(1) . (4)
As the behaviour of the nbrw at degree-2 vertices is deterministic, we will also assume, without much loss of generality, that

min v∈V deg(v) ≥ 3. (5)
Remarkably enough, the asymptotics in this regime depend on the degrees through two simple statistics: the mean logarithmic degree of an half-edge

µ := 1 N v∈V deg(v) log (deg(v) -1) , ( 6
)
and the corresponding variance

σ 2 := 1 N v∈V deg(v) {log (deg(v) -1) -µ} 2 . ( 7
)
We will also need some control on the third absolute moment:

:= 1 N v∈V deg(v) |log (deg(v) -1) -µ| 3 . ( 8
)
It might help the reader to think of µ, σ and as being fixed, or bounded away from 0 and ∞. However, we only impose the following (much weaker) condition:

σ 2 µ 3 >> (log log N ) 2 log N and σ 3 √ µ >> 1 √ log N . ( 9
)
Our main result states that on most graphs with degrees (deg(v)) v∈V , the nbrw exhibits a remarkable behaviour, visible on Figure 1 and known as a cutoff : the distance to equilibrium remains close to 1 for a rather long time, roughly t := log N µ , [START_REF] Chen | The cutoff phenomenon for ergodic markov processes[END_REF] and then abruptly drops to nearly 0 over a much shorter time scale1 , of order

ω := σ 2 log N µ 3 . (11)
Moreover, the cutoff shape inside this window approaches a surprisingly simple function Φ : R → [0, 1], namely the tail distribution of the standard normal:

Φ(λ) := 1 2π ∞ λ e -u 2 2 du.
It is remarkable that this limit shape does not depend at all on the precise degrees.

Theorem 1.1 (Cutoff for the nbrw on sparse graphs). For every 0 < ε < 1,

t mix (ε) -t ω P - → Φ -1 (ε).
Equivalently, for

t = t + λω + o(w ) with λ ∈ R fixed, we have D(t) P - → Φ(λ).
1.3. Comments. It is interesting to compare this with the d-regular case (i.e., deg : V → N constant equal to d) studied by Lubetzky and Sly [START_REF] Lubetzky | Cutoff phenomena for random walks on random regular graphs[END_REF]: by a remarkably precise path counting argument, they establish cutoff within constantly many steps around t = log N/ log(d -1). To appreciate the effect of heterogeneous degrees, recall that µ and σ are the mean and variance of log D, where D is the degree of a uniformly sampled half-edge. Now, by Jensen's Inequality,

t ≥ log N log E[D]
,

and the less concentrated D, the larger the gap. The right-hand side is a wellknown characteristic length in G, namely the typical inter-point distance (see e.g., [START_REF] Van Der Hofstad | Distances in random graphs with finite variance degrees[END_REF]). One notable effect of heterogeneous degrees is thus that the mixing time becomes significantly larger than the natural graph distance. A heuristic explanation is as follows: in the regular case, all paths of length t between two points are equally likely for the nbrw, and mixing occurs as soon as t is large enough for many such paths to exist. In the non-regular case however, different paths have very different weights, and most of them actually have a negligible chance of being seen by the walk. Consequently, one has to make t larger in order to see paths with a "reasonable" weight. Even more remarkable is the impact of heterogeneous degrees on the cutoff width ω , which satisfies ω >> log log N against ω = Θ(1) in the regular case. Finally, the gaussian limit shape Φ itself is specific to the non-regular case and is directly related to the fluctuations of degrees along a typical trajectory of the nbrw.

Remark 1.2 (Simple graphs).

A classical result by Janson [START_REF] Janson | The probability that a random multigraph is simple. Combinatorics[END_REF] asserts that the graph produced by the configuration model is simple (no loops or multiple edges) with probability asymptotically bounded away from 0, as long as

(12) v∈V deg(v) 2 = O(N ) .
Moreover, conditionally on being simple, it is uniformly distributed over all simple graphs with degrees (deg(v)) v∈V . Thus, every property which holds whp under the configuration model also holds whp for the uniform simple graph model. In particular, under [START_REF] Cooper | Vacant sets and vacant nets: Component structures induced by a random walk[END_REF], the conclusion of Theorem 1.1 extends to simple graphs.

Remark 1.3 (IID degrees). A common setting consists in generating an infinite

iid degree sequence (deg(v)) v∈N from some fixed degree distribution Q and then restricting it to the index set V = {1, . . . , n} for each n ≥ 1. Let D denote a random integer with distribution Q. Assuming that P (D ≤ 2) = 0, Var(D) > 0, and E e θD < ∞ for some θ > 0, ensures that the conditions ( 4), ( 5) and ( 9) hold almost surely. Thus, Theorem 1.1 applies with the parameters µ, σ and N now being random. But the latter clearly concentrate around their deterministic counterparts, in the following sense:

N = nE[D] + O P n 1 2 µ = µ + O P n -1 2 with µ = E[D log(D -1)]/E[D] σ = σ + O P n -1 2 with σ 2 = E D {log(D -1) -µ } 2 /E[D].
Those error terms are small enough to allow one to substitute n, µ , σ for N, µ, σ without affecting the convergence stated in Theorem 1.1.

1.4. Related work. The first instances of the cutoff phenomenon were discovered in the early 80's by Diaconis and Shahshahani [START_REF] Diaconis | Generating a random permutation with random transpositions[END_REF] and Aldous [START_REF] Aldous | Random walks on finite groups and rapidly mixing Markov chains[END_REF], in the context of card shuffling: given a certain procedure for shuffling a deck of cards, there exists a quite precise number of shuffles slightly below which the deck is far from being mixed, and slightly above which it is almost completely mixed. The term cutoff and the general formalization appeared shortly after, in the seminal paper by Aldous and Diaconis [START_REF] Aldous | Shuffling cards and stopping times[END_REF]. Since then, this remarkable behaviour has been identified in a variety of other contexts, see e.g., Diaconis [START_REF] Diaconis | The cutoff phenomenon in finite Markov chains[END_REF], Chen and Saloff-Coste [START_REF] Chen | The cutoff phenomenon for ergodic markov processes[END_REF], or the survey by Saloff-Coste [START_REF] Saloff-Coste | Random walks on finite groups[END_REF] for random walks on finite groups. Interacting particle systems in statistical mechanics provide a rich class of dynamics displaying cutoff. One emblematic example is the stochastic Ising model at high enough temperature, for which the cutoff phenomenon has been established successively on the complete graph (Levin et al. [START_REF] Levin | Glauber dynamics for the mean-field ising model: cut-off, critical power law, and metastability[END_REF]), on lattices (Ding et al. [START_REF] Ding | The mixing time evolution of glauber dynamics for the mean-field ising model[END_REF], Lubetzky and Sly [START_REF] Lubetzky | Cutoff for general spin systems with arbitrary boundary conditions[END_REF]), and finally on any sequence of graphs (Lubetzky and Sly [START_REF] Lubetzky | Universality of cutoff for the ising model[END_REF]). Other examples include the Potts model (Cuff et al. [START_REF] Cuff | Glauber dynamics for the mean-field potts model[END_REF]), the East process (Ganguly et al. [START_REF] Ganguly | Cutoff for the east process[END_REF]), or the Simple Exclusion process on the cycle (Lacoin [START_REF] Lacoin | The Cutoff profile for the Simple-Exclusion process on the cycle[END_REF]).

The problem of singling out abstract conditions under which the cutoff phenomenon occurs, without necessarily pinpointing its precise location, has drawn considerable attention. In 2004, Peres [START_REF] Peres | American institute of mathematics (AIM) research workshop "sharp thresholds for mixing times[END_REF] proposed a simple spectral criterion for reversible chains, known as the product condition. Although counter-examples have quickly been constructed (see Levin et al. [25,Chapter 18] and Chen and Saloff-Coste [10, Section 6]), the condition is widely believed to be sufficient for "most" chains. This has already been verified for birth-and-death chains (Ding et al. [START_REF] Ding | Total variation cutoff in birth-and-death chains[END_REF]) and, more generally, for random walks on trees (Basu et al. [START_REF] Basu | Characterization of cutoff for reversible markov chains[END_REF]). The latter result relies on a promising characterization of cutoff in terms of the concentration of hitting times of "worst" (in some sense) sets. See also Oliveira [START_REF] Oliveira | Mixing and hitting times for finite markov chains[END_REF], Peres and Sousi [START_REF] Peres | Mixing times are hitting times of large sets[END_REF], Griffiths et al. [START_REF] Griffiths | Tight inequalities among set hitting times in markov chains[END_REF] and Hermon [START_REF] Hermon | A technical report on hitting times, mixing and cutoff[END_REF].

Many natural families of Markov chains are now believed to exhibit cutoff. Yet, establishing this phenomenon rigorously requires a very detailed understanding of the underlying chain, and often constitutes a challenging task even in situations with a high degree of symmetry. The historical case of random walks on the symmetric group for example, is still far from being completely understood: see Saloff-Coste [START_REF] Saloff-Coste | Random walks on finite groups[END_REF] for a list of open problems, and Berestycki and Sengul [START_REF] Berestycki | Cutoff for conjugacy-invariant random walks on the permutation group[END_REF] for a recent proof of one of them.

Understanding the mixing properties of random walks on sparse random graphs constitutes an important theoretical problem, with applications in a wide variety of contexts (see e.g., the survey by Cooper [START_REF] Cooper | Random walks, interacting particles, dynamic networks: Randomness can be helpful[END_REF]). A classical result of Broder and Shamir [START_REF] Broder | On the second eigenvalue of random regular graphs[END_REF] states that random d-regular graphs with d fixed are expanders with high probability (see also Friedman [19]). In particular, the simple random walk (srw) on such graphs satisfies the product condition, and should therefore exhibit cutoff. This long-standing conjecture was confirmed only recently in an impressive work by Lubetzky and Sly [START_REF] Lubetzky | Cutoff phenomena for random walks on random regular graphs[END_REF], who also determined the precise cutoff window and profile. Their result is actually derived from the analysis of the nbrw itself, via a clever transfer argument. Interestingly, the mixing time of the srw is d/(d -2) times larger than that of the nbrw. This confirms the practical advantage of nbrw over srw for efficient network sampling and exploration, and complements a well-known spectral comparison for regular expanders due to Alon et al. [START_REF] Alon | Non-backtracking random walks mix faster[END_REF], as well as a recent result by Cooper and Frieze [START_REF] Cooper | Vacant sets and vacant nets: Component structures induced by a random walk[END_REF] on the cover time of random regular graphs. For other ways of speeding up random walks, see Cooper [START_REF] Cooper | Random walks, interacting particles, dynamic networks: Randomness can be helpful[END_REF].

In the non-regular case however, the tight correspondence between the srw and the nbrw breaks down, and there seems to be no direct way of transferring our main result to the srw. We note that the latter should exhibit cutoff since the product condition holds, as can be seen from the fact that the conductance of sparse random graphs with a given degree sequence remains bounded away from 0 (see Abdullah et al. [START_REF] Abdullah | Cover time of a random graph with given degree sequence[END_REF]). Confirming this constitutes a challenging open problem. In particular, it would be interesting to see whether the srw still mixes faster than the nbrw. To the best of our knowledge, no precise conjectural expression for the mixing time of the srw has been put forward2 .

Proof outline

The proof of Theorem 1.1 is divided into two (unequal) halves: for [START_REF] Cuff | Glauber dynamics for the mean-field potts model[END_REF] with λ ∈ R fixed, we will show that 1) , ( 14)

t = t + λw + o(w ),
E [D (t)] ≥ Φ(λ) -o(
D (t) ≤ Φ(λ) + o P (1). ( 15
)
The lower bound ( 14) is proved in Section 3. The difficult part is the upper bound [START_REF] Diaconis | Generating a random permutation with random transpositions[END_REF], due to the maximization over all possible initial states. Starting from state x ∈ X , the distance to stationarity is

D x (t) = y∈X 1 N -P t (x, y) + = y∈X 1 N -P t (x, π(y)) + ,
since π is an involution. Using the symmetry (2), we may re-write P t (x, π(y)) as

P t (x, π(y)) = (u,v)∈X ×X P t/2 (x, u)P t/2 (y, v)1 {π(u)=v} . ( 16
)
As a first approximation, let us assume that the balls of radius t/2 around x and y consist of disjoint trees, in agreement with Figure 2. This is made rigorous by a particular exposure process described in Section 5. The weight w(u) := P t/2 (x, u) (resp. w(v) := P t/2 (y, v)) can then be unambiguously written as the inverse product of degrees along the unique path from x to u (resp. y to v).

A second approximation consists in eliminating those paths whose weight exceeds some given threshold θ > 0 (the correct choice turns out to be θ ≈ 1 N ):

P t (x, π(y)) ≈ u,v w(u)w(v)1 w(u)w(v)≤θ 1 {π(u)=v} .
Conditionally on the two trees of height t/2, this is a weighted sum of weakly dependent Bernoulli variables, and the large-weight truncation should prevent it from deviating largely from its expectation. We make this argument rigorous in Section 6, using Stein's method of exchangeable pairs. Provided the exposure process did

N P t (x, π(y)) ≈ u,v w(u)w(v)1 w(u)w(v)≤θ .
Now, the right-hand side corresponds to the quenched probability (conditionally on the graph) that the product of the weights seen by two independent nbrw of length t/2, one starting from x and the other from y, does not exceed θ. The last step consists in approximating those trajectories by independent uniform samples from X , which we denote by X 1 , . . . , X t . We obtain

u,v w(u)w(v)1 w(u)w(v)≤θ ≈ P 1 deg(X 1 ) • • • 1 deg(X t ) ≤ θ ≈ P t k=1 (µ -log deg(X k )) σ √ t ≤ µt + log θ σ √ t ≈ 1 -Φ(λ) ,
by the central limit theorem, since θ ≈ 1/N and t ≈ t + λω . Consequently,

y 1 N -P t (x, π(y)) + ≈ Φ(λ) ,
as desired. This argument is made rigorous in Sections 7, 8 and 9.

The lower bound

Fix t ≥ 1, two states x, y ∈ X , and a parameter θ ∈ (0, 1). Let P t θ (x, y) denote the contribution to P t (x, y) from paths having weight less than θ. Note that P t θ (x, y) < P t (x, y) if and only if some path of length t from x to y has weight larger than θ, implying in particular that P t (x, y) > θ. Thus,

1 N -P t θ (x, y) ≤ 1 N -P t (x, y) + + 1 N 1 P t (x,y)>θ .
Summing over all y ∈ X and observing that there can not be more than 1/θ half-edges y ∈ X satisfying P t (x, y) > θ, we obtain 1 -

y∈X P t θ (x, y) ≤ D x (t) + 1 θN .
Now, the left-hand side is the quenched probability (i.e., conditional on the underlying pairing) that a nbrw {X k } 0≤k≤t starting at x satisfies t k=1 1 deg(X k ) > θ. Taking expectation w.r.t. the pairing, we arrive at

P t k=1 1 deg(X k ) > θ ≤ E[D x (t)] + 1 θN , ( 17
)
where the average is now over both the nbrw and the pairing (annealed law). A useful property of the uniform pairing is that it can be constructed sequentially, the pairs being revealed along the way, as we need them. We exploit this degree of freedom to generate the walk {X k } k≥0 and the pairing simultaneously, as follows. Initially, all half-edges are unpaired and X 0 = x; then at each time k ≥ 1, (i) if X k-1 is unpaired, we pair it with a uniformly chosen other unpaired halfedge; otherwise, π(X k-1 ) is already defined and no new pair is formed. (ii) in both cases, we let X k be a uniformly chosen neighbour of π(X k-1 ). The sequence {X k } k≥0 is then exactly distributed according to the annealed law. Now, if we sample uniformly from X instead of restricting the random choice made at (i) to unpaired half-edges, the uniform neighbour chosen at step (ii) also has the uniform law on X . This creates a coupling between the process {X k } k≥1 and a sequence {X k } k≥1 of iid samples from X , valid until the first time T where the uniformly chosen half-edge or its uniformly chosen neighbour is already paired. As there are less than 2k paired half-edges by step k, a crude union-bound yields

P (T ≤ t) ≤ 2t 2 N .
Consequently,

P t k=1 1 deg(X k ) > θ -P t k=1 1 deg(X k ) > θ ≤ 2t 2 N . ( 18
)
On the other hand, since {X 1 , . . . , X t } are iid, Berry-Esseen's inequality implies

P t k=1 1 deg(X k ) > θ -Φ µt + log θ σ √ t ≤ σ 3 √ t . ( 19
)
We may now combine ( 17), ( 18), [START_REF] Friedman | A proof of Alon's second eigenvalue conjecture and related problems[END_REF] to obtain

E[D x (t)] ≥ Φ µt + log θ σ √ t - 1 θN - 2t 2 N - σ 3 √ t .
With t as in ( 13) and θ = (log N )/N , the right-hand side is Φ(λ) + o(1), thanks to our assumptions on µ, σ, . This establishes the lower bound [START_REF] Diaconis | The cutoff phenomenon in finite Markov chains[END_REF].

The upper-bound

Following Lubetzky and Sly [START_REF] Lubetzky | Cutoff phenomena for random walks on random regular graphs[END_REF], we call x ∈ X a root (written x ∈ R) if the (directed) ball of radius h centered at x (denoted by B x ) is a tree, where

h := log N 10 log ∆ ∧ log log N . ( 20
)
Note that 1 << h << ω by assumptions ( 4) and [START_REF] Chatterjee | Stein's method for concentration inequalities[END_REF]. The first proposition below shows that we may restrict our attention to paths between roots. The second proposition provides a good control on such paths.

x∈X P h (x, X \ R) P - → 0.
Proposition 4.2 (Roots are well inter-connected). For t as in [START_REF] Cuff | Glauber dynamics for the mean-field potts model[END_REF],

min x∈R min y∈R\Bx P t (x, π(y)) ≥ 1 -Φ(λ) -o P (1) N .
Let us first see how those results imply the upper-bound [START_REF] Diaconis | Generating a random permutation with random transpositions[END_REF]. Observe that

D(t + h) ≤ max x∈X P h (x, X \ R) + max x∈R D x (t) .
The first term is o P (1) by Proposition 4.1. For the second one, we write

D x (t) = y∈R\Bx 1 N -P t (x, π(y)) + + y∈Bx∪(X \R) 1 N -P t (x, π(y)) + .
Proposition 4.2 ensures that the first sum is bounded by Φ(λ) + o P (1) uniformly in x ∈ R. To see that the second sum is o P (1) uniformly in x ∈ R, it suffices to bound its summands by 1/N and observe that 20), while

|B x | ≤ ∆ h = o(N ) by (
|X \ R| = x∈X P h (x, X \ R),
(P is doubly stochastic), which is o P (N ) uniformly in X by Proposition 4.1.

Proof of Proposition 4.1. Define r := log N 5 log ∆ and fix x ∈ X . The ball of radius r around x can be generated sequentially, its half-edges being paired one after the other with uniformly chosen other unpaired half-edges, until the whole ball has been paired. Observe that at most k = ∆((∆-1) r -1) ∆-2 pairs are formed. Moreover, for each of them, the number of unpaired half-edges having an already paired neighbour is at most ∆(∆-1) r and hence the conditional chance of hitting such an half-edge (thereby creating a cycle) is at most p = ∆(∆-1) r -1 N -2k-1 . Thus, the probability that more than one cycle is found is at most

(kp) 2 = O (∆ -1) 4r N 2 = o 1 N .
Summing over all x ∈ X (union bound), we obtain that with high probability, no ball of radius r in G(π) contains more than one cycle.

To conclude the proof, we now fix a pairing π with the above property, and we prove that the nbrw on G(π) starting from any x ∈ X satisfies P (X t is not a root) ≤ 2 1-t , [START_REF] Griffiths | Tight inequalities among set hitting times in markov chains[END_REF] for all t ≤ r -h. The claim is trivial if the ball of radius r around x is acyclic. Otherwise, it contains a single cycle C, by assumption. Write d(z, C) for the minimum length of a non-backtracking path from x to some z ∈ C. The nonbacktracking property ensures that if d(X t , C) < d(X t+1 , C) for some t < r-h, then X t+1 , X t+2 , . . . , X r-h are all roots. By ( 5), the conditional chance that d(X t+1 , C) = d(X t , C) + 1 given the past is at least 1/2 (unless d(X t , C) = 1, which can only happen once). This shows [START_REF] Griffiths | Tight inequalities among set hitting times in markov chains[END_REF]. We then specialize to t = h.

The exposure process

The remainder of the paper is devoted to the proof of Proposition 4.2. Fix two distinct half-edges x, y ∈ X . We describe a two-stage procedure that generates a uniform pairing on X together with a rooted forest F keeping track of certain paths from x and y. Initially, all half-edges are unpaired and F is reduced to its two roots, x and y. We then iterate the following three steps:

1. An unpaired half-edge z ∈ F is selected according to some rule (see below). 2. z is paired with a uniformly chosen other unpaired half-edge z .

3. If neither z nor any of its neighbours was already in F, then all neighbours of z become children of z in the forest F. The exploration stage stops when no unpaired half-edge is compatible with the selection rule. We then complete the pairing by matching all the remaining unpaired half-edges uniformly at random: this is the completion stage.

The condition in step 3 ensures that F remains a forest: any z ∈ F determines a unique sequence (z 0 , . . . , z h ) in F such that z 0 is a root, z i is a child of z i-1 for each 1 ≤ i ≤ h, and z h = z. We shall naturally refer to h and z 0 as the height and root of z, respectively. We also define the weight of z as

w(z) := h i=1 1 deg(z i ) .
Note that this quantity is the quenched probability that the sequence (z 0 , . . . , z h ) is realized by a nbrw on G starting from z 0 . In particular, w(z) ≤ P h (z 0 , z). [START_REF] Hermon | A technical report on hitting times, mixing and cutoff[END_REF] Our rule for step 1 consists in selecting an half-edge with maximal weight 3 among all unpaired z ∈ F with height h(z) < t/2 and weight w(z) > w min , where

w min := N -2
3 . The only role of this parameter is to limitate the number of pairs formed during the exploration stage. As outlined in Section 2, we shall be interested in

W := (u,v)∈Hx×Hy w(u)w(v)1 w(u)w(v)≤θ ,
where H x (resp. H y ) denotes the set of unpaired half-edges with height t 2 and root x (resp. y) in F at the end of the exploration stage, and where

θ := 1 N (log N ) 2 . ( 23
)
Write W for the quantity obtained by replacing ≤ with > in W, so that

W + W = (u,v)∈Hx×Hy w(u)w(v) ≥ z∈Hx∪Hy w(z) -1, thanks to the inequality ab ≥ a + b -1 for a, b ∈ [0, 1]
. Now, let U denote the set of unpaired half-edges in F. By construction, at the end of the exploration stage, each z ∈ U must have height t/2 or weight less than w min , so that

W + W ≥ z∈U w(z) - z∈F w(z)1 (w(z)<wmin) -1.
Therefore, Proposition 4.2 follows from the following four technical lemmas. Lemma 5.1. For every ε > 0,

P P t (x, π(y)) ≤ W -ε N = o 1 N 2 .
Lemma 5.2. For every ε > 0,

P   z∈F w(z)1 (w(z)<wmin) > ε   = o 1 N 2 .
Lemma 5.3. For every ε > 0,

P W > Φ(λ) + ε = o 1 N 2 .
3 For definiteness, let us say that we use the lexicographic order on X to break ties.

Lemma 5.4. For every ε > 0,

P   x ∈ R, y ∈ R \ B x , z∈U w(z) < 2 -ε   = o 1 N 2 .
6. Proof of Lemma 5.1

Combining the representation ( 16) with the observation ( 22) yields

P t (x, π(y)) ≥ (u,v)∈Hx×Hy w(u)w(v)1 w(u)w(v)≤θ 1 π(u)=v .
The right-hand side can be interpreted as the weight of the uniform pairing chosen at the completion stage, provided we define the weight of a pair (u, v) as

w(u)w(v)1 u∈Hx 1 v∈Hy 1 w(u)w(v)≤θ . ( 24
)
Lemma 5.1 now follows from the following general concentration inequality, which we apply conditionally on the exploration stage, with I being the set of half-edges that did not get paired, and weights being given by [START_REF] Lacoin | The Cutoff profile for the Simple-Exclusion process on the cycle[END_REF]. Lemma 6.1. Let I be an even set, {w i,j } (i,j)∈I×I an array of non-negative weights, and π a uniform random pairing on I. Then for all a > 0,

P i∈I w i,π(i) ≤ m -a ≤ exp - a 2 4θm ,
where m = 1

|I|-1 i∈I j =i w i,j and θ = max i =j (w i,j + w j,i ).

Note that in our case, m = W |I|-1 . Lemma 5.1 follows easily by taking a = ε |I|-1

and observing that |I| -1 ≤ N and W ≤ 1.

Proof. We exploit the following concentration result for Stein pairs due to Chatterjee [START_REF] Chatterjee | Stein's method for concentration inequalities[END_REF] (see also Ross [33,Theorem 7.4]): let Y, Y be bounded variables satisfying

(i) (Y, Y ) d = (Y , Y ); (ii) E[Y -Y |Y ] = -λY ; (iii) E[(Y -Y ) 2 |Y ] ≤ λ(bY + c),
for some constants λ ∈ (0, 1) and b, c ≥ 0. Then for all a > 0,

P (Y ≤ -a) ≤ exp - a 2 c and P (Y ≥ a) ≤ exp - a 2 ab + c .
We shall only use the first inequality. Consider the centered variable

Y := i∈I w i,π(i) -m,
and let Y be the corresponding quantity for the pairing π obtained from π by performing a random switch: two indices i, j are sampled uniformly at random from I without replacement, and the pairs {i, π(i)}, {j, π(j)} are replaced with the pairs {i, j}, {π(i), π(j)}. This changes the weight by exactly (25) ∆ i,j := w i,j + w j,i + w π(i),π(j) + w π(j),π(i) -w i,π(i) -w π(i),i -w j,π(j) -w π(j),j .

It is not hard to see that (π, π ) d = (π , π), so that (i) holds. Moreover,

E[Y -Y |π] = 1 |I|(|I| -1) i∈I j =i ∆ i,j = 4 |I|(|I| -1) i∈I j =i w i,j - 4 |I| i∈I w i,π(i) = - 4 |I| Y.
Regarding the square ∆ 2 i,j = |∆ i,j ||∆ i,j |, we may bound the first copy of |∆ i,j | by 2θ and the second by changing all minus signs to plus signs in [START_REF] Levin | Markov chains and mixing times[END_REF], yielding

E (Y -Y ) 2 |π = 1 |I|(|I| -1) i∈I j =i ∆ 2 i,j ≤ 8θ |I|(|I| -1) i∈I j =i w i,j + 8θ |I| i∈I w i,π(i) = 8θ |I| (2m + Y ) .
Note that taking conditional expectation with respect to Y does not affect the right-hand side. Thus, (ii) and (iii) hold with λ = 4 |I| , b = 2θ and c = 4mθ.

7. Proof of Lemma 5.2

We may fix z 0 ∈ {x, y} and restrict our attention to the halved sum

Z := z∈F w(z)1 (w(z)<wmin) 1 (z has root z 0 ) .
Consider m = log N independent nbrws on G(π) starting at z 0 , each being killed as soon as its weight falls below w min , and write A for the event that their trajectories form a tree of height less than t/2. Clearly, P (A|π) ≥ Z m . Taking expectation and using Markov inequality, we deduce that

P (Z > ε) ≤ P (A) ε m
, where the average is now taken over both the walks and the pairing. Recalling that m = log N , it is more than enough to establish that P(A) = (o(1)) m . To do so, we generate the m killed nbrws one after this other, revealing the underlying pairs along the way, as described in Section 3. Given that the first -1 walks form a tree of height less than t/2, the conditional chance that the th walk also fulfils the requirement is o(1), uniformly in 1 ≤ ≤ m. Indeed,

• either its weight falls below η = (1/log N ) 2 before it ever reaches an unpaired half-edge: thanks to the tree structure, there are at most -1 < m possible trajectories to follow, so the chance is less than mη = o(1).

• or the remainder of its trajectory after the first unpaired half-edge has weight less than ∆w min /η: this part consists of at most t/2 half-edges which can be coupled with uniform samples from X for a total-variation cost of mt 2 /N , as in Section 3. Thus, the conditional chance is at most

mt 2 N + P   t/2 k=1 deg(X k ) ≥ η ∆w min   = o(1), by Chebychev's inequality, since log η ∆wmin -µt 2 >> σ t 2 .
8. Proof of Lemma 5.3

Set m = log N . On G(π), let X (1) , . . . , X (m) and Y (1) , . . . , Y (m) be 2m independent nbrws of length t/2 starting at x and y respectively. Let B denote the event that their trajectories form two disjoint trees and that for all 1 ≤ k ≤ m,

t/2 =1 1 deg(X (k) ) t/2 =1 1 deg(Y (k) ) > θ.
Then clearly, P (B|π) ≥ W m . Averaging w.r.t. the pairing π, we see that

P W > Φ(λ) + ε ≤ P (B) (Φ(λ) + ε) m .
Thus, it is enough to establish that P(B) ≤ (Φ(λ) + o(1)) m . We do so by generating the 2m walks X (1) , Y (1) , . . . , X (m) , Y (m) one after the other along with the underlying pairing, as above. Given that X (1) , Y (1) , . . . , X ( -1) , Y ( -1) already satisfy the desired property, the conditional chance that X ( ) , Y ( ) also does is at most Φ(λ) + o(1), uniformly in 1 ≤ ≤ m. Indeed,

• either one of the two walks attains length s = 2 log log N before reaching an unpaired half-edge: there are at most -1 < m possible trajectories to follow for each walk, so the conditional chance is at most 2m2 -s = o(1).

• or at least t -2s unpaired half-edges are encountered, and the product of their degrees falls below 1 θ with conditional probability at most 4mt

2 N + P t-2s k=1 deg(X k ) < 1 θ = Φ(λ) + o(1),
by the same coupling as above and Berry-Essen's inequality [START_REF] Friedman | A proof of Alon's second eigenvalue conjecture and related problems[END_REF]. 9. Proof of Lemma 5.4

We denote by τ the (random) number of pairs formed during the exploration stage. For k ≥ 0, we let U k denote the set of unpaired half-edges in the forest after k ∧ τ pairs have been formed, and we consider the random variable

W k := z∈U k w(z).
Initially W 0 = 2, and this quantity either stays constant of decreases at each stage, depending on whether the condition appearing in step 3 is satisfied or not. More precisely, denoting by z k (resp. z k ) the half-edge selected at step 1 (resp. chosen at step 2) of the k th pair, we have for all k ≥ 1,

W k = W k-1 -1 (k≤τ ) w(z k )1 (z k ∈U + k-1 ) + w(z k )1 (z k ∈U k-1 )
, where U + k-1 is the union of U k-1 and the set of unpaired neighbours of the roots. Now, let {G k } k≥0 be the natural filtration associated with the exploration stage. Note that τ is a stopping time, that w(z k ) is G k-1 -measurable, and that the conditional law of z k given G k-1 is uniform on X \ {z 1 , . . . , z k , z 1 . . . , z k-1 }. Thus,

E[W k -W k-1 |G k-1 ] = -1 (k≤τ ) w(z k )(|U + k-1 | -2) + W k-1 N -2k + 1 . E (W k -W k-1 ) 2 |G k-1 = 1 (k≤τ )
w(z k ) 2 (|U + k-1 | -4) + 2w(z k )W k-1 + z∈U k-1 w(z) 2 N -2k + 1 .

To bound those quantities, observe that each half-edge in U k-1 has weight at least w(z k ) ∆

because its parent has been selected at an earlier iteration and our selection rule ensures that the quantity w(z k ) is non-increasing with k. Consequently,

|U k-1 | w(z k ) ∆ ≤ z∈U k-1 w(z) ≤ 2.
Combining this with the bound |U + k-1 | ≤ |U k-1 | + 2∆, we arrive at

E[W k -W k-1 |G k-1 ] ≥ -1 (k≤τ ) 4∆ N -2k + 1 E (W k -W k-1 ) 2 |G k-1 ≤ 1 (k≤τ ) 4∆w(z k ) + 2 N -2k + 1 .
Now recall that w(z k ) ≥ w min and h(z k ) < t 2 as per our selection rule, implying w min τ ≤ k≥1 w(z k )1 (τ ≥k) ≤ z∈F w(z)1 (h(z)< t

2 ) ≤ t.

The right-most inequality follows from the fact that the total weight at a given height in F is at most 2 (the total weight being preserved from a parent to its children, if any). We conclude that

τ k=1 E[W k -W k-1 |G k-1 ] ≥ -
M k := k i=1 (W i-1 -W i ) ∧ ε -E (W i-1 -W i ) ∧ ε G i-1 .
Then the increments of {M k } k≥0 are bounded by ε by construction, and the above computation guarantees that almost-surely,

τ k=1 E (M k -M k-1 ) 2 G k-1 ≤ v = N -1 3 +o(1) .
Thus, the martingale version of Bennett's inequality due to Freedman [START_REF] Freedman | On tail probabilities for martingales[END_REF] yields

P (M τ > 7ε) ≤ ev v + 7ε

Figure 1 .

 1 Figure 1. Distance to stationarity along time for the nbrw on a random graph with 10 6 degree 3-vertices and 10 6 degree 4-vertices

Figure 2 .

 2 Figure 2. A set of half-edges X , a pairing π and the resulting graph G The non-backtracking random walk (nbrw) on the graph G = G(π) is a discretetime Markov chain with state space X and transition matrix

Figure 4 .

 4 Figure 4. The tree-approximation

Proposition 4 . 1 (

 41 Roots are quickly reached).

  max

E

  (W k -W k-1 ) 2 |G k-1 ≤ 4∆tw min + 2t N w min -2t := v.Now, fix ε > 0 and consider the martingale {M k } k≥0 defined by M 0 = 0 and

2

 2

7 = N - 7 3

 77 +o[START_REF] Abdullah | Cover time of a random graph with given degree sequence[END_REF] .[START_REF] Levin | Glauber dynamics for the mean-field ising model: cut-off, critical power law, and metastability[END_REF] But on the event {x ∈ R, y ∈ R \ B x }, all paths from the set {x, y} to itself must have length at least h, and since h → ∞, we must have asymptotically{x ∈ R, y ∈ R \ B x } ⊆ max k (W k-1 -W k ) ≤ ε ⊆ {W 0 -W τ ≤ M τ + m}With (26), this proves Lemma 5.4 since W 0 -W τ = 2 -z∈U w(z) and m = o(1).

The fact that ω << t follows from condition (4).

During the finalization of the manuscript, a solution to this problem has been announced[START_REF] Berestycki | Random walks on the random graph[END_REF].


Patrick Ferrand
email: patrick.ferrand@fresnel.fr

GPScan.VI: A general-purpose LabVIEW program for scanning imaging or any application requiring synchronous analog voltage generation and data acquisition

Keywords: scanning imaging, high-speed data acquisition, analog output, synchronization, LabVIEW, NI-DAQmx PACS: 07.05.Dz, 07.05.Hd, 07.79.-v Program scanning imaging, high-speed data acquisition, analog output, analog input, pulse counting, synchronization, LabVIEW, NI-DAQmx. Classification: 20

A large number of measurement techniques involve the scanning of a probe, while a physical quantity is measured. This is for instance the case for all scanning imaging methods. Data acquisition therefore requires high acquisition rates, together with an accurate synchronization between the probe control and the measurement. The GPScan.VI program is a general purpose LabVIEW program for the control of National Instruments high-speed data acquisition boards, allowing to design scanning imaging systems. Analog output voltages are used to drive a two-dimensional scanning device, while acquisition of analog voltages and TTL pulse counting are run in parallel. Acquisition of megapixel images with pixel dwell times down to the microsecond can be reached with negligible I/O transfer time. The design can be generalized to any situation requiring high speed synchronous generation and acquisition.

Introduction

A large number of microscopy techniques, including atomic force microscopy, electron microscopy, confocal and nonlinear optical microscopy, rely on a scanning scheme. In this operating mode, a probe (tip, electron beam, light spot, etc.) is scanned over an object, while a physical quantity is measured, allowing subsequently to build a digital image of this object. Technically, because this acquisition scheme is sequential and thus intrinsically slow, it requires high acquisition rates, together with an accurate synchronization between the probe control and the measurement. Such control and acquisition devices are available for a while on the market and operate in many commercial scanning imaging systems. In addition, several implementation of such devices for research instruments have been described in the past [START_REF] Pologruto | Scanimage: flexible software for operating laser scanning microscopes[END_REF][START_REF] Nguyen | Mpscope: A versatile software suite for multiphoton microscopy[END_REF][START_REF] Hartell | Simple windows-based software for the control of laser scanning confocal microscopes[END_REF][START_REF] Bettiol | A new data acquisition and imaging system for nuclear microscopy based on a field programmable gate array card[END_REF][START_REF] Kim | A labview based template for user created experiment automation[END_REF]. However, the proposed solutions are complete softwares that are often very specific, may appear complicated to the novice programmer because optimized for versatility, or may be based on devices and/or drivers that are now obsolete. As a consequence, adapting such software to an existing experimental bench remains a challenge for many research labs.

In this article, I describe the GPScan.VI program that allows to configure and use National Instruments (NI) multifunction acquisition boards for this purpose. I focus on providing the technical details of the necessary building blocks in a comprehensive way, and on detailing the critical issues of device configuration, triggering and acquisition rate. The program is built into modular blocks, so that basic tasks such as initializing, measuring and releasing the devices are easy to adapt to any user needs.

Program overview

Requirements

The program GPScan.VI is written in LabVIEW using DAQmx functions, and exploits the features of NI all-in-one high-speed multifunction acquisition boards. It requires the presence of two analog output (AO) channels that are exploited for a high-speed (up to several millions of samples per second) and device-independent control of the two-dimensional scanning, since most scanning devices (piezo scanners, galvanometric mirrors, etc.) can be driven by analog voltages. Data acquisition can involve several analog input (AI) channels and/or counters in parallel. AI channels suit for most detectors and sensors, which output voltages, while counters can exploit specific detectors that deliver TTL pulses, such as single photon counting modules.

In the NI product portfolio, suitable acquisition devices will be found among the X [START_REF]National Instruments, DAQ X Series user manual[END_REF] or the S [7] series multifunction data acquisition boards. The choice of device [8] will be dictated by the required acquisition rate, internal computer bus (USB, PCIe, PXI or PCI), and available budget.

Subprograms

The tasks corresponding to synchronous scanning and image acquisition are first configured using the Init.VI program, which is depicted in Fig. 1, where the total number of points of the image, together with the pixel dwell time are set. The AO (2 channels) and AI (user defined number of channels) tasks are configured to deliver and measure, respectively, voltages series at the appropriate pixel rate. The counter acquisition is performed using the so-called pulse duration mode in a roundabout way: this measurement mode was indeed originally designed in NI-DAQmx to measure the duration of unknown pulses in terms of number of ticks of a reference clock [START_REF]National Instruments, LabVIEW measurements manual[END_REF]; here the unknown pulses are replaced by a known pulse train generated by one counter (called pixel clock), while the sample clock is replaced by the TTL pulses coming from the detector. In this way, the "pulse duration" values that are returned are actually the number of TTL pulses measured at each pixel coordinate. Finally, in order to ensure a perfect synchronization, AI, pixel clock generation and counters tasks are configured to start at the rising digital edge signal of the AO start trigger terminal.

The scanning of an entire frame is performed according to the Scan.VI program, depicted in Fig. 2. First, counter acquisition, pixel clock generation, and AI acquisition are armed, meaning that they are waiting for the triggering signal. Then, based on the scanning parameters (number of pixels in each dimension, scanning amplitude) and voltage factors (which associate a voltage value to a desired scanning amplitude), the values of the AO series corresponding to a 2D raster scan are computed by RasterScanXY.VI (see Fig. A.6) and written on the device. When ready, the AO generation starts, together with the trigged data acquisitions. Then, the complete series of AI and counter measurements are transferred to the computer, when available. Iterative image acquisition is performed by means of a while loop. In this case, AO series are updated to the board only if the scanning amplitudes have changed since the last iteration. Note that although this does not appear on the program, data transfers involve internal buffers and are bidirectional so that AO generation and data acquisition partially overlap in time. Finally, the Close.VI, depicted in Fig. 3 clears all tasks, and releases all the device resources reserved by the tasks.

Main program

The program GPMain.VI as depicted in Fig. 4 is a basic example of complete scanning and acquisition program, in the case of two AI channels and two counting channels, that illustrates how to manipulate the data series so that they can be displayed as digital images. correspond to a relatively fast image acquisition (1 fps), with a reduced scanning field definition (15×15 µm 2 ), providing a sufficient signal to noise ratio and fast response for an efficient focus optimization, for instance.

In practice, the acquisition speed depends strongly on the scanning device. Standard galvanometric mirrors usually possess a low inertia so they can routinely operate in a raster scanning mode with dwell times down to tens of microseconds [START_REF] Beiser | Unified optical scanning technology[END_REF], with a possible delay which may induce an artificial shift of the reconstructed image and flyback artifact [1; 10]. Piezo scanning stages, unless specifically designed for speed, work in the millisecond range [START_REF] Mudry | Isotropic diffraction-limited focusing using a single objective lens[END_REF].

Another factor limiting speed is the required signal to noise ratio. This issue could be critical when using photon counting modules. Because of their specific design, these devices are often limited to count rates of a few millions of counts per seconds, i.e., a few counts per microseconds. In these conditions, scanning with pixel dwell times below 10 µs is redhibitory in terms of signal to noise ratio.

Finally, when the application requires a high frame rate, a legitimate concern is the time that is needed to transfer (i) the scanning parameters from the computer to the board, (ii) the measured signal to the computer. This time, which I refer to as "I/O data transfer time", has to be considered as an incompressible extra delay, in addition to the duration of the measurement itself. It has been measured on NI-USB-6353 device connected to a 3 GHz-CPU laptop (USB2 port) for various scanning conditions and typical values are given in Tab. 1. Predictably, this I/O transfer time is mostly dependent on the amount of data to transfer, i.e., on the total number of pixels, irrespectively of the pixel dwell time. Remarkably, it remains usually small compare to the measurement time, even when AO series are updated from one frame to the next. In usual conditions of imaging, which involve a large number of pixels, one could reasonably consider that the I/O data transfer time is negligible compare to the measurement itself.

Conclusion

In conclusion, GPScan.VI can be used as a core program to develop high-speed raster scanning systems using a multifunction device, and can be adapted for any other arbitrary scanning scheme. More generally, it can be used in all kind of instrument which necessitate high speed synchronous signal generation and acquisition.

Figure 1 :

 1 Figure 1: Block diagram of Init.VI.

Figure 3 :

 3 Figure 3: Block diagram of Close.VI.

Figure 4 :

 4 Figure 4: Block diagram of the main program GPScan.VI. In this example, images are acquired in parallel on two AI channels and two counting channels.

Figure 5 :

 5 Figure 5: Front panel of the main program GPScan.VI when operating. In this example, images are acquired in parallel on one counting channel and one AI channel. Note that the difference between the two obtained images is due to the different signals acquired by the two channels, namely two-photon fluorescence and coherent anti-Stokes Raman scattering, respectively [15]. Image field of view is 15 × 15 µm 2 .

Table 1 :

 1 Measured value of the I/O transfer time (in addition to the measurement itself). Although not critical, dwell time and low time were set to 10 µs and 1 µs, respectively. Measurements were performed on a NI-USB-6353 device.

	Number of pixels	I/O data transfer time (ms)
		w/o AO series update w/ AO series update
	10 × 10	138	138
	100 × 100	138	142
	500 × 500	148	196
	1000 × 1000	176	420

Acknowledgments

The author is grateful to H. Rigneault for stimulating discussions. This work has been funded by Agence Nationale de la Recherche under contracts ANR-2010-BLAN-150902, ANR-10-INBS-04-01, ANR-11-INSB-0006, ANR-11-IDEX-0001-02, by Fondation pour la Recherche Médicale, under contract DBS20131128448 and by Conseil Régional Provence Alpes Côte d'Azur.

CPC Program Library, Queens University, Belfast, N. Ireland

://cpc.cs.qub.ac.uk/summaries/AEWG v1 0.html Program obtained from:

How to use the program

The front panel of the program GPScan.VI is depicted in Fig. 5. The left frame contains the scanning settings, including pixel duration, scanning range, and voltage factors, that allow to adjust the scaling between the scanning physical units and the control voltages. The top panel is used to set the two AO channels, together with the terminal which is used to trig every frame scanning. The middle frame corresponds to the two counter channels, whose parameters are taken into account only if the front panel button "Use counters" is activated. Similarly, the bottom frame deals with AI acquisition and display, when "Use analog inputs" is on.

The block diagram of GPScan.VI, as shown in Fig. 4, corresponds to the case of two AI channels and two counter channels. The first AI channel is extracted by selecting the first row (i.e., of index 0) of the 2D analog data array that is output by GPScan.VI, the second AI channels corresponds to row of index 1, etc. Counter channels data are extracted in the same way from the 2D count data array. Adapting the number of AI and/or counter channels can therefore be done easily by deleting or by duplicating the desired pieces of diagram, with the appropriate index number.

Acquisition rate

The program GPScan.VI can typically operate acquisition of megapixel images with pixel dwell times down to the microsecond, the ultimate value of which being dictated by the specifications of the update/acquisition rate of the NI device in use. The 16-bit analog to digital converters allow a precision for the AO generation of AI acquisition that is usually high enough to cover all usual experimental needs. GPScan.VI has been used as core program of advanced scanning microscopy softwares [START_REF] Ferrand | A versatile dual spot laser scanning confocal microscopy system for advanced fluorescence correlation spectroscopy analysis in living cell[END_REF][START_REF] Mudry | Isotropic diffraction-limited focusing using a single objective lens[END_REF][START_REF] Brustlein | Optical parametric oscillatorbased light source for coherent Raman scattering microscopy: practical overview[END_REF][START_REF] Saint-Jalm | Fiber based ultra-short pulse delivery for nonlinear imaging using high energy solitons[END_REF][START_REF] Ferrand | Ultimate use of two-photon fluorescence microscopy to map orientational behavior of fluorophores[END_REF]. The screen capture presented in Fig. 5, has been taken when GPScan.VI operates a multimodal microscopy system detailed in [START_REF] Duboisset | Molecular orientational order probed by coherent anti-stokes raman scattering (cars) and stimulated raman scattering (srs) microscopy: A spectral comparative study[END_REF], combining here one counter channel and one AI channel. The working parameters used here