Francis Comets
email: comets@math.jussieu.fr

François Delarue
email: delarue@unice.fr

René Schott
email: schott@loria.fr

Information Transmission under Random Emission Constraints

Keywords: Information transmission, epidemic model, complete graph, Galton-Watson tree, coupon collector problem, large deviations AMS subject classifications: Primary 90B30; secondary 05C81, 60F05, 60F10, 60J20, 92D30

We model the transmission of a message on the complete graph with n vertices and limited resources. The vertices of the graph represent servers that may broadcast the message at random. Each server has a random emission capital that decreases at each emission. Quantities of interest are the number of servers that receive the information before the capital of all the informed servers is exhausted and the exhaustion time. We establish limit theorems (law of large numbers, central limit theorem and large deviation principle), as n → ∞, for the proportion of visited vertices before exhaustion and for the total duration. The analysis relies on a construction of the transmission procedure as a dynamical selection of successful nodes in a Galton-Watson tree with respect to the success epochs of the coupon collector problem.

Introduction

Transmission of information and dissemination of viruses in computer networks gave rise to many practical as well as theoretical investigations over the two last decades (see [START_REF] Baccelli | Optimal paths on the space-time SINR random graph[END_REF][START_REF] Ding | Modeling wireless sensor networks using random graph theory[END_REF][START_REF] Jia | Wireless networks and random geometric graphs[END_REF][START_REF] Kawahigashi | Modeling ad-hoc sensor networks using random graph theory[END_REF][START_REF] Kesten | Sidoravicius: The spread of a rumor or infection in a moving population[END_REF][START_REF] Kurtz | Limit theorems for an epidemic model on the complete graph[END_REF]).

In this paper, we model the transmission of a message on the complete graph with n vertices and limited ressources. Every vertex represents a server, which can be in one of three states: inactive (it did not receive the message yet), active (it has already received it, and is able to transmit it), exhausted (it has already received it, but cannot transmit it anymore because it has exhausted its own capital of emissions). Each server S i has a random emission capital K i . The message is initially received from outside by one server, which is then turned from the inactive state to the active one (if it has a positive emission capital) or exhausted (if its emission capital is 0), though the n -1 other servers are inactive. At each integer time, one of the active servers (say S i ) casts the message, it looses one unit of its own emission capital K i , and it selects the target at random among the n servers. If the target is inactive, it discovers the information, it becomes itself active or exhausted according to its own emission capital. If not, this broadcast is unsuccessful and nothing else happens. When an active server exhausts its emission capital, it enters the exhausted state. The transmission ends at a finite time τ n , which is at most equal to n plus the sum of all initial capitals.

From a practical point, the graph may be thought as a wireless network, the vertices of which are battery powered sensors with a limited energy capacity. We refer the reader to [START_REF] Baccelli | Optimal paths on the space-time SINR random graph[END_REF][START_REF] Ding | Modeling wireless sensor networks using random graph theory[END_REF][START_REF] Jia | Wireless networks and random geometric graphs[END_REF][START_REF] Kawahigashi | Modeling ad-hoc sensor networks using random graph theory[END_REF] for applications of graph theory to the performance evaluation of information transmission in wireless networks. We mention that the transmission process can be also interpreted as the busy period of a queue when the probability that a new customer enters the queue decays linearly as the number of past arrivals increases and finally vanishes after the nth arrival.

Here we describe the asymptotic behavior of the proportion of visited vertices at the end of the process when n tends to the infinity. The mathematical analysis relies on a twofold structure: a subtree of the Galton-Watson tree, which models the vertices reached by the emission procedure, and the success epochs of the coupon collector problem, which model the successful transmissions. Phrased in a probabilistic way, we propose a coupling of the transmission model as a marginal tree of the Galton-Watson tree, obtained by pruning some of the nodes according to the coupon collector problem. Such a coupling provides a direct interpretation of the scenarios when the network ceases broadcasting at the very beginning of the process: basically, these scenarios correspond to the extinction event in the Galton-Watson tree. On the survival event, we manage to specify the first-order behavior (in n) of the exhaustion time τ n and of the proportion of visited nodes. Under suitable integrability conditions on the distribution of the capital of a given vertex, the fluctuations of both the exhaustion time and the proportion of visited nodes are also investigated: a central limit theorem is proved under a square-integrability condition and a somewhat involved large deviation principle is established under an exponential-integrability condition. In particular, when the distribution of the capital of a given vertex is of finite expectation, the probability that all the servers be reached before exhaustion (also referred to as the probability of full transmission) converges to 0 as n tends to the infinity; as a consequence of the large deviation principle we prove here, it decays exponentially fast when the capital has a finite exponential moment. In some cases when the distribution of the capital has a heavy tail, we prove that the limit of the probability of full transmission is different from 0 and, in particular, may coincide with the entire probability of survival of the Galton-Watson tree. We refer to [START_REF] Baum | Asymptotic distributions for the coupon collector's problem[END_REF][START_REF] Boucheron | Bins and balls: large deviations of the empirical occupancy process[END_REF][START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF][START_REF] Kan | The martingale approach to the coupon collection problem[END_REF] for specific results concerning the coupon collector problem.

The papers [START_REF] Machado | CLT for the proportion of infected individuals for an epidemic model on a complete graph[END_REF] and [START_REF] Kurtz | Limit theorems for an epidemic model on the complete graph[END_REF] study closely related transmission models. Machado et al. [START_REF] Machado | CLT for the proportion of infected individuals for an epidemic model on a complete graph[END_REF] consider the case where K i = 2 and prove partial transmission results. Obviously, our approach extends this result, as constant capitals are a particular case of random ones. A specific interest of random capitals consists in allowing K i to be 0 with a non-trivial probability: as we shall see below, a quick stop of the transmission process then occurs with a positive probability, as the extinction event of the Galton-Watson tree. As in [START_REF] Machado | CLT for the proportion of infected individuals for an epidemic model on a complete graph[END_REF], Kurtz et al. [START_REF] Kurtz | Limit theorems for an epidemic model on the complete graph[END_REF] investigate the case where the K i 's are constant, but possibly larger than 2, time running continuously. In their model, there is one particle at each vertex of the graph at time 0; one of them is active, the others are inactive. The active particle begins to move as a continuous-time, rate 1, random walk on the graph; as soon as any active particle visits an inactive one, the latter becomes active and starts an independent random walk. Each active particle dies at the instant it reaches a total of L jumps (consecutive or not) without activating any particle. Each active particle starts with L lives and looses one life unit whenever it jumps on a vertex which has already been visited by the process. For simultaneous jumps in discrete time, the number of informed servers has fluctuations of order n 3/4 [START_REF] Zhukovskiï | The law of large numbers for an epidemic model[END_REF].

We also emphasize that the dynamics of the present model is very similar, except for the asynchronisation, to the frog model on the complete graph with finite lifetimes: the earliest reference is [START_REF] Alves | Random walks systems on complete graphs[END_REF], addressing the question of final coverage. In the frog model on Z d , there is a phase transition between almost-sure extinction and survival with positive probability according to the underlying death rate [START_REF] Alves | Phase transition for the frog model[END_REF], and similarly for a time-continuous model [START_REF] Kesten | Sidoravicius: A phase transition in a model for the spread of an infection[END_REF]. Shape theorems are proved in [START_REF] Alves | The shape theorem for the frog model[END_REF], and also in [START_REF] Ramírez | Asymptotic behavior of a stochastic combustion growth process[END_REF] and [START_REF] Kesten | Sidoravicius: The spread of a rumor or infection in a moving population[END_REF] in continuous time. Fluctuations are gaussian in one dimension [START_REF] Comets | Fluctuations of the front in a stochastic combustion model[END_REF][START_REF] Comets | Fluctuations of the front in a one dimensional model of X + Y → 2X[END_REF], but unknown when d ≥ 2.

The paper is organized as follows. The basic model is presented in Section 2 together with the main results. In Section 3, we provide an alternative construction based on a pruning procedure of the Galton-Watson tree. Law of large numbers and related fluctuation limit theorems are investigated in Section 4, including the case of heavy tails. The large deviation principle is established in Section 5.

The model and main results

A Markovian definition of the dynamics

From a modeling point of view, we assume that the servers emit between consecutive integers. The global state of the whole system before and after emissions is thus described at integer times. At any time t ∈ N, N n (t) denotes the number of servers which have already received the message and the so-called 'total emission capital' S n (t) the number of available attempts that can be used to deliver the message to a server which has not received it yet. At time 0, only one server detains the information. Its own capital, that is S n (0) with our notation, is a random variable, the distribution of which is denoted by µ.

The dynamics of the pair process (N n (t), S n (t)) t∈N are then assumed to be Markovian. Conditionally on the states up to time t, the values of N n (t + 1) and S n (t + 1) are then given by:

S n (t + 1) = S n (t) + -1 K(t + 1) -1 with probability N n (t)/n 1 -N n (t)/n , (1)
where K(t + 1) is a random variable, with µ as distribution and independent of the past up until time t; respectively, in the above cases,

N n (t + 1) = N n (t) N n (t) + 1 . ( 2
)
From a practical point of view, the interpretation is the following. During the emission that occurs between times t and t+1, one server is chosen at random among the n ones; it is referred to as the 'target'. If the target is a server that has already received the information, then the number of informed servers remains the same and the total emission capital decreases by one. Such a scenario happens with the conditional probability N n (t)/n. If the target is a noninformed server, then the number of informed servers increases by one and the total emission capital increases by the own emission capital of the target which has just been activated. This happens with conditional probability 1-N n (t)/n and K(t+1) then denotes the initial emission capital of the target activated between time t and time t+1. It is worth noting that the process (N n (t)) t∈N is a Markov process itself, known as the 'coupon collector process' in the standard probability literature. It describes the collect, with replacement, of n equally likely coupons. With such a modeling, the variables K(t), t ∈ N, are i.i.d., with µ as common distribution, K(0) being equated with S n (0) and the sequences (K(t)) t∈N and (N n (t)) t∈N being independent (we emphasize that, when the emission between t and t + 1 is a failure, the variable K(t + 1) has no role in the description of the dynamics of the pair process (N n (t), S n (t)) t∈N ). By independence of the two sequences, the sum of all the capitals revealed up until time t has the same law as R(N n (t)) where

R(t) = t s=1 K(s), t ∈ N \ {0}. (3)
The transmission process lasts for a duration τ n which is the first time t when the emission capital is equal to 0,

τ n = min{t ∈ N : S n (t) = 0}. (4)
A natural question consists in determining whether the information will reach all servers, or a proportion of them only. We then define the event of full transmission,

Trans n = {N n (τ n ) = n},
which occurs when all the servers finally receive the information. Then, three regimes of interest can be distinguished, according to P(Trans n ) = 0, or 1, or ∈ (0, 1), which naturally corresponds to different tails behavior of K. In all these cases, one is interested in the large-n asymptotics of τ n and N n (τ n ).

Then, the sequence (S n (t ∧ τ n ), N n (t ∧ τ n )) t∈N is a Markov chain on N × {0, 1, . . . , N } with a non-decreasing second component, and absorption on the vertical axis. The harmonic equations for absorption probabilities are rather intricate for a general K, a natural route being to approximate the process by a differential equation. Here, our analysis will rely on a specific construction of the dynamics obtained by considering the Galton-Watson tree of reproduction law µ.

Construction as a labeled Galton-Watson tree

In Section 3, we construct the information transmission process with a Galton-Watson tree with degree K ∼ µ and an independent coupon collector process with n coupons. We only give a quick account here. For each n, we prune the tree using the events of the n-coupon collector. Given a realization of the Galton-Watson tree, we visit successively all the nodes starting from the root, we keep [resp., erase] the current node if a new coupon is obtained at that time [resp., if we do not collect a new coupon; then, the whole subtree below the current node is deleted]. This results into a subtree of the original one, with size

N n (τ n ) ≤ n.
Here is a precise statement. We denote by Z GW k the cardinality of the k-th generation of the Galton-Watson tree and by Surv GW the survival event Surv GW = {Z GW k ≥ 1, ∀k}. It is well known that P(Surv GW ) > 0 if and only if EK > 1 or P(K = 1) = 1.

Proposition 2.1 Let (Ω, A, P) be a probability space where are defined: (i) a Galton-Watson tree with offspring distribution µ, (ii) for each integer n, a coupon collector process with n coupons, independent of the tree.

Then, there exist sequences (S n (t), t ∈ N) and (N n (t), t ∈ N) defined on this probability space with N n (0) = 1, S n (0) ∼ µ, and such that ((N n (t), S n (t)), t ∈ N) is a Markov chain with transitions as in (1), [START_REF] Alves | Phase transition for the frog model[END_REF].

Letting

Z GW tot = k≥0 Z GW k ,
the full transmission event is 'asymptotically included' in the survival event in the sense that

Trans n ⊂ Z GW tot ≥ n where Z GW tot ≥ n ց Surv GW as n ր ∞, and conversely, the event of termination at time o(n) in the information process converges to extinction in the Galton-Watson process: denoting by ∆ the symmetric difference,

lim ǫ→0 + lim n→∞ P {τ n ≥ nǫ}∆Surv GW = 0. ( 5
)
The construction is simple and natural, but it seems to be new and it turns out to be a powerful tool to analyze the information process. In all our results below, we consider this particular coupling of the information process with the Galton-Watson tree and the coupon collector.

Limit for the information coverage and duration

For EK > 1, define θ ∈ (0, ∞) as the unique root of the equation

1 -e -θ θ = 1 EK . (6)
Extend this definition by setting

θ = 0 if EK ≤ 1, θ = ∞ if EK = ∞. The function EK → θ is increasing from [0, ∞] to [0, ∞]. Let also p = 1 -e -θ ∈ [0, 1], (7)
and note from [START_REF] Billingsley | Convergence of probability measures[END_REF], that when EK ∈ (1, ∞), p = 1e -θ ∈ (0, 1) is the unique solution of

p EK = -ln(1 -p), (8)
whereas p = 1 when θ = ∞.

Theorem 2.2 Let EK ∈ (0, ∞]. (i) As n → ∞, τ n /n -→ θ 1 Surv GW
in probability, with θ defined by ( 6), though

N n (τ n )/n -→ p 1 Surv GW in probability, with p = 1 -e -θ . (ii) If EK ≤ 1 (P(K = 1) < 1 by assumption), then lim n→∞ [τ n + 1] = lim n→∞ N n (τ n ) = Z GW tot in probability.
As a straightforward consequence, we observe that P(Trans n ) → 0 as n → ∞ whenever EK is finite, as p is strictly less than 1 in this case. In Theorem 2.8 we shall prove that the rate of decay is exponential in the case when K has a finite exponential moment.

Gaussian fluctuations in the case of a light tail

Theorem 2.3 Assume EK > 1 and EK 2 < ∞. Let σ 2 K denote the variance of K. As n → ∞, conditionnally on Surv GW , we have the convergence in law:

n -1/2 τ n -nθ law -→ N (0, σ 2 τ ), with σ 2 τ = [(1 -p)EK -1] -2 [pσ 2 K + (EK) 2 σ N (θ) 2
] and σ N (s) 2 = e -s (1e -s )se -2s . Similarly, conditionnally on Surv GW , we have the convergence in law:

n -1/2 N n (τ n ) -np law -→ N (0, σ 2 p ), with σ 2 p = [(1 -p)EK -1] -2 [pσ 2 K e -2θ + σ N (θ) 2 ].
Theorem 2.3 extends results in [START_REF] Kurtz | Limit theorems for an epidemic model on the complete graph[END_REF][START_REF] Machado | CLT for the proportion of infected individuals for an epidemic model on a complete graph[END_REF]. We do not study the random fluctuations any further such as the corrections to the law of large numbers, but we prefer to explore the resulting regimes of full transmission. From Theorem 2.2, when EK = ∞, N n (τ n )/n → 1 in probability, conditionnally on survival: This leaves open the asymptotics of the probability P(Trans n ). Some cases are investigated in the next subsection.

Probability of full transmission in the case of a heavy tail

When K has a fat tail, fluctuations will serve the transmission process. The next result shows that the full transmission event converges to the survival event if the tail is very heavy.

Proposition 2.4 If there exist c > 0 and α ∈ (0, 1) such that lim inf ℓ→∞ [ℓ α P(K ≥ ℓ)] ≥ c, then, P(Trans n ) -→ P(Surv GW ) as n → ∞.

Hence, fluctuations of sums of K's variables play a crucial role for the occurence of full transmission. When µ has a heavy tail, one of the servers activated during the transmission process has a large enough capital K allowing it to contact all the other servers. We now turn to the critical case, when K belongs to the domain of attraction of a stable law of index 1.

Theorem 2.5 Assume there exists c > 0 such that

P(K ≥ ℓ) ∼ c ℓ , ℓ → ∞.
Then, as n → ∞,

P(Trans n ) -→ P(Surv GW ) ×    E(exp(-e -S )) , c = 1, 1 , c > 1, 0 , c < 1,
where, in the case c = 1, S = lim n→∞ n -1 (R(n)n ln n) is a totally asymmetric Cauchy variable, the centering parameter of which depends on the distribution of K (see [START_REF] Alves | The shape theorem for the frog model[END_REF] for the definition of R).

The particular form of the limit relates to the celebrated result of Erdös and Rényi [START_REF] Erdös | On a classical problem of probability theory[END_REF] for the coupon collector, that is the time to collect all coupons has a Gumbel limit law.

Large deviations

Following Chapter 1 in [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF], we recall that a random sequence (Z n , n ≥ 1), with values in some Polish space Z, obeys a large deviation principle (LDP) with rate function I and speed n if

• I : Z → [0, ∞] is lower semi-continuous; • for all closed subset F ⊂ Z, lim sup n→∞ n -1 ln P(Z n ∈ F ) ≤ -inf{I(z); z ∈ F }; • for all open subset O ⊂ Z, lim inf n→∞ n -1 ln P(Z n ∈ O) ≥ -inf{I(z); z ∈ O}.
Assume all through this section that K has exponentially small tails: E exp(a 0 K) < ∞ for some a 0 > 0. Then, by Cramer's theorem (e.g., Subsection 2.2.1 in [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF]), R(n)/n obeys a LDP with rate I,

I(u) = sup{au -ln E exp(aK); a ∈ R}, u ∈ [0, ∞), (9)
and I(u) = ∞ for u < 0. The function I is convex, lower semicontinuous and has compact level sets {u ∈ R :

I(u) ≤ c}, for c ∈ [0, ∞).
The domain of the rate function I is defined as the set Dom(I) of reals u with finite I(u). Here, we have Dom(

I) = [k * , k * ] R, with k * = min{k : P(K = k) > 0}, k * = sup{k : P(K = k) > 0}.
We also recall the large deviations principle for the coupon collector process with n coupons from Boucheron et al. [START_REF] Boucheron | Bins and balls: large deviations of the empirical occupancy process[END_REF], Dupuis et al. [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF]: for all t > 0, we have:

N n (nt)/n obeys a LDP with speed n and rate function J t .

From (2.7) and Section 4.1 in [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF], the rate function J t is convex, it is finite if and only if r ∈ (0, t ∧ 1], with lim rց0 J t (r) = ∞, and it has a finite limit as r → t ∧ 1. For r ∈ (0, t ∧ 1), it is given by J t (r) = (1r) ln(1r) + (tr) ln ρ(r, t) + te -tρ(r,t) , [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF] where ρ(r, t) denotes the unique solution in (0, ∞) of

1 -e -tρ ρ = r. (12)
With these ingredients we define the function

F : R 2 + → [0, ∞] by F(r, t) =    rI(t/r) + J t (r) if r > 0, ∞ if r = 0, t > 0, 0 if r = t = 0. ( 13
) Lemma 2.6 (i) The function F, is lower semi-continuous on R 2 + with compact level sets {(r, t) : F(r, t) ≤ c} for nonnegative c. Its domain is equal to Dom(F) = (r, t) ∈ R 2 + : 0 < r ≤ t ∧ 1, (k * ∨ 1)r ≤ t ≤ k * r ∪ (0, 0) .
It is continuous on Dom(F)\{(0, 0)}. It is continuous at the origin if and only if K is bounded.

(ii) Moreover,

F 1 -e -t , t = (1 -e -t )I t 1 -e -t ,
and when k * ≤ 1 < k * , we have F(1e -t , t) ∼ tI(1) as t → 0.

(iii) When EK > 1, the function F is not convex, as it takes the value 0 at points (p, θ) and (0, 0), and is positive elsewhere. When EK ≤ 1, F is positive everywhere except at 0. The domain of F might be rather degenerate. For example, in the Bernoulli case K ∈ {0, 1}, it reduces to the segment {(r, r), 0 ≤ r ≤ 1}. This function is an intricate combination of the rate functions of the coupon collector process and of the Galton-Watson process. This makes it an interesting rate function in its own. Theorem 2.7 The sequence (n -1 N n (τ n ), τ n ) n∈N\{0} , obeys a LDP with rate function F and speed n.

As a corollary, we obtain a variational formula for the probability of full transmission.

Theorem 2.8 The decay of the probability for all servers to be reached before exhaustion is exponential and given by:

lim n→+∞ n -1 ln P(Trans n ) = -inf s≥0 I λ(s) + (λ(s)-1) ln 1-e -s + λ(s)e -s ,
with λ(s) = s/(1-e -s ) (with λ(0) = 1). The above right-hand side is negative.

Construction from a labeled Galton-Watson tree

Let W = ∪ k≥0 (N * ) k be the set of all finite words on the alphabet {1, 2, . . .}. Its elements are of the form w 1 w 2 . . . w k , w i ∈ N * when k ≥ 1, and, for k = 0, (N * ) k reduces to the empty word ∅, that we call the root. We then denote by |w| = k the length of w = w 1 w 2 . . . w k ∈ W (with

|∅| = 0.) For w, w ′ ∈ W, we write w < w ′ if: |w| < |w ′ |, or |w| = |w ′ |
and w≤ lex w ′ in the lexicographic order. We denote by the usual predecessor relation in W, that is w w ′ if w is a prefix of w ′ .

Let (K(w), w ∈ W) be a family of i.i.d. random variables on N = {0, 1, 2, . . .} with common law µ (pay attention that the notation K(t), t ∈ N, is also used in Subsection 2.1; we here use the same letter K, but a different index, no confusion being possible in the sequel). Assume µ(0) < 1 and µ(1) < 1 for a nontrivial setup. The associated Galton-Watson tree T GW is the set of w ∈ W such that w = ∅ or, for all i = 1, . . . , |w|, w i ≤ K(v) with v the predecessor of w of length i -1 (in other words, given a parent w ′ at the (i -1)th generation, that is w ′ is a word of length i -1, the children of w ′ are the words w ′ 1, . . . , w ′ K(w ′ ), of length i, obtained by concatenation). Denote by Z GW k the size of the kth generation of this tree,

Z GW k = card {w ∈ T GW : |w| = k}, which is given by Z GW k+1 = v∈T GW ,|v|=k K(v), Z GW 0 = 1.
Recalling that µ(1) < 1, it is well known that the survival event

Surv GW = k {Z GW k ≥ 1} = {card T GW = ∞} has complement probability σ GW = 1 -P(Surv GW ) = = 1 if EK ≤ 1, < 1 if EK > 1.
On the same probability space, we consider an independent coupon collector process with n images (n ≥ 1): Let ∆ i,n , i = 1, . . . n -1, be independent, geometrically distributed r.v.'s on N * with parameter 1i/n (success probability) respectively. The success epochs are

T 1,n = 0, T i,n = i-1 j=1 ∆ j,n , i = 2, . . . n,
and the counting function is

N n (t) = n i=1 1 {T i,n ≤t} , t = 0, 1, . . .
In fact, N n (t) represents the number of servers having received the information by time t (note that 1 ≤ N n (t) ≤ min{t + 1, n}).

For any fixed integer n, with these two ingredients, we can define the transmission process together with the transmission time length τ n . Let us start with an informal description. We browse a part of the Galton-Watson tree following the order <, and we paint the nodes in • or in △ according to the coupon collector process (success or failure); we only browse nodes which are in stand-by; as soon as a node is painted in •, its number of children nodes in T GW is revealed, and these children are put in stand-by. We then move to the next node in stand-by (next for <). The procedure runs until there are no nodes in stand-by anymore.

Here is a precise definition. Recursively for t = 0, 1, . . ., we construct X(t) ∈ T GW , and disjoint T • (t), T ⊠ (t), T △ (t) ⊂ T GW as follows (X(t) encodes the vertex where the t-th tentative emission takes place, T • (t) denotes the set of servers already informed by time t, T ⊠ (t) is the set of tentative emissions scheduled but not yet performed at time t, T △ (t) is set of failed emissions, i.e. those performed before time t for which the target was already informed). Start with

X(0) = ∅, T • (0) = {∅}, T ⊠ (0) = {w ∈ T GW : |w| = 1, 1 ≤ w 1 ≤ K(∅)}, T △ (0) = ∅,
with ∅ denoting the empty set. With the process (X(t), T • (t), T ⊠ (t), T △ (t)) at time t, its value at the next step t + 1 is defined by:

• If T ⊠ (t) is nonempty, we let X(t + 1) be its first element, X(t + 1) = inf{w ∈ T ⊠ (t)}, denoted by v to ease the notations, and we perform a test: [START_REF] Duquesne | Random trees, Lévy processes and spatial branching processes[END_REF] the notation vk denoting the word of length |v| + 1 obtained by concatenation.

-If N n (t + 1) = N n (t) + 1, we define T • (t + 1) = T • (t) ∪ {v}, T ⊠ (t + 1) = T ⊠ (t) \ {v} ∪ v1, v2, . . . , vK(v) , T △ (t + 1) = T △ (t),
-If N n (t + 1) = N n (t), we define

T • (t + 1) = T • (t), T ⊠ (t + 1) = T ⊠ (t) \ {v}, T △ (t + 1) = T △ (t) ∪ {v}. (15)
• If T ⊠ (t) is empty, we set τ n = t, and the construction is stopped (as well as the transmission). The set

T • (t) = T • (τ n ) = T • (∞) is the set of servers finally informed. Note that τ n ≤ T n,n is a.s. finite.
We observe that for all t, T • (t) is a tree, as well as

T • (t) ∪ T ⊠ (t). Moreover, T ⊠ (t) ∪ T △ (t) is a cutset of T GW for its own graph structure. ∅ X(t)
Figure 1. The Galton-Watson tree is represented up to the 4th generation.

T • (t), T ⊠ (t) and T △ (t) and X(t) are represented at time t = 10. Figure 1 provides an example of construction of the sets T • (t), T ⊠ (t) and T △ (t), t ∈ {0, 1, . . . , 10}, according to the rules prescribed in ( 14) and [START_REF] Durrett | Probability. Theory and Examples[END_REF]. At time 0, the capital of the initial server is K(∅) = 4, so that the root of the tree has four children. Between times 0 and 1, the first emission is a success as the server which is revealed in the tree is painted in •. This server reads as the first child (starting from the left) at the first generation of the tree; it has two children, that is K('1') = 2, where '1' is here understood as a one-letter word. At time 1, the total emission capital is thus S(1) = 4 + 2 -1 = 5, and T ⊠ (2) contains the three last children at the first generation and the two first children at the second generation. Since the second child at the first generation is painted in △, the emission between times 1 and 2 fails, which means that the children of this node are not considered for the sequel of the construction. At time 2, S(2) = 4 + 2 -2 = 4. Then, the emission between times 2 and 3 is a success but the server which is informed has no children (third child in the first generation) and the emission between times 3 and 4 is a success as well, with K('4') = 3. At time 4, T ⊠ (4) contains 5 nodes, all of them at the second generation of the tree. The node X( 5) is then the first child at the second generation: as it is painted in △, the emission between times 4 and 5 fails. And so on up until time 10. Then, T ⊠ (10) contains 5 nodes: two of them at the fourth generation and three of them at the third generation. With the lexicographic order, X(11) = '411'.

We now relate the above construction to the dynamical model for transmission. Consider a new, independent, i.i.d. sequence ( Ki ) i≥1 with law µ, and define, for i = 1, . . . n,

K i = K(X(T i,n )) if i ≤ card T • (∞), Ki if i > card T • (∞), (16)
and also

S n (t) := Nn(t) i=1 K i -t, t ∈ N \ {0}. (17)
Below, we also write

S n (t) = R (N n (t)) -t, t ∈ N, with R(m) := m i=1 K i , m ∈ N \ {0}. ( 18
)
Pay attention that the letter R is also used in (3), but as proved right below the two R's have the same distribution. In the sequel, we will always refer to [START_REF] Jia | Wireless networks and random geometric graphs[END_REF] for the precise definition of R.

By construction, we have

N n (t) = card T • (t), S n (t) = card T ⊠ (t). ( 19
)
Proposition 3.1 The variables (K i ) 1≤i≤n are independent, identically distributed with law µ, and (K i ) 1≤i≤n is independent of (T i,n ) 1≤i≤n . Moreover,

τ n = min{t ∈ N : S n (t) = 0}. ( 20
)
The formula for τ n directly follows from [START_REF] Kawahigashi | Modeling ad-hoc sensor networks using random graph theory[END_REF], and the fact that τ n is finite. We now investigate the distribution of the sequence (K i , i ≤ n). Below, we denote by

F w = σ(K(w ′ ), w ′ ≤ w) for w ∈ W. On the event A = {(T 1,n , . . . , T i,n ) = (k 1 , . . . , k i ), X(k i -1) = w, τ n ≥ k i }, 0 = k 1 < • • • < k i and w ∈ W, |w| ≤ k i -1, X(T i,n
) coincides with an F w -measurable r.v., denoted by χ, which satisfies w < χ almost-surely (this follows from the monotonicity of the browsing procedure). Similarly, all the variables K(X(T j,n )), 1 ≤ j ≤ i -1 coincide with F w -measurable r.v.'s on A. Clearly, K(χ) is independent of F w ∨ σ(T 1,n , . . . , T n,n ) and has µ as distribution, since the r.v.'s (K(w ′ ), w ′ ∈ W) are i.i.d and are independent of the success epochs (T 1,n , . . . , T n,n ). Obviously, the event A belongs to F w ∨ σ(T 1,n , . . . , T n,n ). This proves that, for any bounded and measurable Borel function φ,

E φ(K i )1 {T i,n ≤τn} |(T j,n , 1 ≤ j ≤ n), (K j , 1 ≤ j ≤ i -1) = 1 {T i,n ≤τn} N φdµ.
On the event {(T 1,n , . . . , T i,n ) = (k 1 , . . . , k i ), τ n < k i }, K i coincides with Ki , which is obviously independent of σ((T j,n , 1 ≤ j ≤ n), (K j , 1 ≤ j ≤ i -1)), so that the above equality also holds with T i,n ≤ τ n replaced by T i,n > τ n .

Then the process we have constructed here corresponds to the description of the information transmission process given in Subsection 2.1.

Proof of Proposition 2.1: (5) follows from Lemma 4.2 below and {τ n ≥ nǫ} ⊂ {Z GW tot ≥ nǫ}. The other claims directly follow from the construction and Proposition 3.1.

Proofs of law of large numbers and fluctuations

In all the proofs, we use the following convention: for any discrete process (V t , t ∈ N), (V t , t ≥ 0) stands for (V ⌊t⌋ , t ≥ 0), where ⌊•⌋ is the floor function. We will also use the ceiling function, denoted by ⌈•⌉.

Proofs of the law of large numbers

Lemma 4.1 We have the following convergence in law of sequences of processes on the Skorohod space (endowed with the standard J1 topology, keeping in mind that convergence for the J1 topology implies uniform convergence on compacts when the limit function is continuous):

(i) On D([0, 1)),

n -1/2 T ⌊nq⌋,n -n ln 1 1 -q 0≤q<1 law -→ B σ T (q) 2 0≤q<1 as n → ∞,
with B a standard Brownian motion, and

σ T (q) 2 = q 1 -q + ln(1 -q) > 0. (ii) On D(R + ), n -1/2 N n (ns) -n(1 -e -s ) s≥0 law -→ B σ N (s) 2 s≥0
as n → ∞, with B a standard Brownian motion, and

σ N (s) 2 = e -s (1 -e -s ) -se -2s > 0.
Both limits are independent increments Gaussian processes with zero mean, and they are martingales.

Assertion (i) is a direct application of the invariance principle for triangular array of independent, but not i.d., square-integrable r.v.'s, see Dacunha-Castelle and Duflo [10, Théorème 7.4.28] or Jacod and Shiryaev [17, Chapter VII, Theorem 5.4]. The variance is computed as the limit of a Riemann sum,

σ T (q) 2 = lim n→∞ 1 n qn i=1 Var(∆ i,n ) = lim n→∞ 1 n qn i=1 i/n (1 -i/n) 2 = q 0 y (1 -y) 2 dy.
Assertion (ii) follows from (i), using that N n (•) and T ⌊n•⌋,n are reciprocal in a generalized sense. With f (q) =ln(1q), f -1 (s) = 1e -s , we have σ N (s

) 2 = σ T (f -1 (s)) 2 × [f ′ • f -1 (s)] -2 , see Billingsley [6, Theorem 17.3].
The next lemma is one of the key argument of the whole analysis. It shows that when the Galton-Watson tree is infinite transmission takes place on a macroscopic time level. Lemma 4.2 There exists ε 0 > 0 such that for all ε ∈ (0, ε 0 ),

lim n→∞ P(τ n ≥ nε, Surv GW ) = P(Surv GW ) = 1 -σ GW .
The claim being trivial for σ GW = 1, we just need to consider the case when EK > 1. Letting here k = ⌊ln 2 n⌋, we estimate

P(τ n ≤ nε, Surv GW ) ≤ P(N n (k) ≤ k) + P(k ≤ τ n ≤ nε, Surv GW ), (21)
using that {N n (k) = k + 1, Surv GW } ⊂ {τ n ≥ k, Surv GW } which implies that P N n (k) ≤ k, Surv GW ≥ P τ n < k, Surv GW .
We start with

P(N n (k) ≤ k) = 1 -(1 -1/n) × . . . (1 -k/n) ≤ 1 -(1 -k/n) k ∼ k 2 /n as k 2 /n → 0. ( 22
)
Let ε 0 = (1/2)(1 -1/EK) > 0. Fix ε ∈ (0, ε 0 ), and note that (1 -2ε)EK > 1. It remains to prove the convergence

P(k ≤ τ n ≤ nε, Surv GW ) = nε i=k P(τ n = i, Surv GW ) ≤ nε i=k P(S n (i) ≤ 0) → 0, ( 23
)
where the inequality holds by definition of τ n (4). We start to show that there exists a constant C ε > 0, independent of n, such that

P (N n (i) < ⌈(1 -2ε)i⌉) ≤ exp (-C ε i) , ∀i ≤ nε.
Indeed, the above probability is equal to

P (N n (i) < ⌈(1 -2ε)i⌉) = P T ⌈(1-2ε)i⌉,n > i ≤ P T ε (1-2ε)i > i with T ε (1-2ε)i a sum of ⌈(1 -2ε)i⌉ of i.i.d. geometric r.v.
's with parameter 1ε; now, the desired estimate follows from Chernov's bound. Next, we note that, for z ∈ (0, 1), i ≤ nε and

G(z) = Ez K , P S n (i) ≤ 0, N n (i) ≥ ⌈(1 -2ε)i⌉ ≤ E z Sn(i) ; N n (i) ≥ ⌈(1 -2ε)i⌉ ≤ z -i E z R(⌈(1-2ε)i⌉) ; N n (i) ≥ ⌈(1 -2ε)i⌉ ≤ z -i G(z) ⌈(1-2ε)i⌉ ≤ z -i G(z) (1-2ε)i ,
where we have used

S n (i) = R(N n (i))-i ≥ R(⌈(1-2ε)i⌉)-i on the event {N n (i) ≥ ⌈(1-2ε)i⌉}
to pass from the first to the second line, R being given by [START_REF] Jia | Wireless networks and random geometric graphs[END_REF]. Since (1 -2ε)EK > 1, we have r := z -1 G(z) (1-2ε) < 1 by picking z < 1 close enough to 1 and then by expanding G(z) as G(z) = 1 + EK(z -1) + o(z -1) (o(•) standing for the Landau notation). Thus, the left-hand side of ( 23) is bounded by

P(k ≤ τ n ≤ nε, Surv GW ) ≤ nε i=k [r i + exp(-C ε i)] ≤ 2(1 -r 1 ) -1 r k+1 1 ,
with r 1 = max{r, exp(-C ε )} < 1. Collecting the above estimates in [START_REF] Kesten | A limit theorem for multidimensional Galton-Watson processes[END_REF] and taking k = ⌊ln 2 n⌋, we conclude that P(τ n ≤ nε, Surv GW ) = O(n -a ) for all a ∈ (0, 1) (O(•) standing for the Landau notation).

Proof of Theorem 2.2. We start with the proof of (i). We assume first EK < ∞. Then, we can apply the law of large numbers to the process

R(m) = m i=1 K i (24)
in [START_REF] Jia | Wireless networks and random geometric graphs[END_REF], to show that P-a.s., R(nq)/n → qEK uniformly on [0, 1]. Recall from ( 18) that

S n (t) = R(N n (t)) -⌊t⌋. (25)
In addition to Lemma 4.1, this shows that, in probability,

S n (ns)/n -→ (1 -e -s )EK -s, uniformly on compacts of R + (26)
as n → ∞. As a consequence, for any δ > 0,

P (τ n > n(θ + δ)) ≤ P (inf [S n (ns), s ∈ [0, θ + δ]] ≥ 0) → 0 as n → ∞, (27)
since (1e -s )EKs < 0 for s > θ. Now, we write

P (|τ n -nθ 1 Surv GW | > nδ) = P |τ n -nθ| > nδ, Surv GW + P τ n > nδ, (Surv GW ) ∁ ≤ P τ n < nε, Surv GW + P |τ n -nθ| > nδ, Surv GW , τ n ≥ nε +P τ n > nδ, (Surv GW ) ∁ ,
where the first term of the right-hand side tends to 0 (as n → ∞) from Lemma 4.2. The last term vanishes because τ n is smaller than the extinction time of the Galton-Watson process, which is a.s. finite on the extinction event. Since τ n is the first time such that S n (τ n ) = 0, the second term also tends to 0 by [START_REF] Machado | CLT for the proportion of infected individuals for an epidemic model on a complete graph[END_REF]. Indeed, (27) yields:

lim sup n→∞ P |τ n -nθ| > nδ, Surv GW , τ n ≥ nε ≤ lim sup n→∞ P nε ≤ τ n ≤ nθ -nδ, Surv GW , τ n ≥ nε ≤ lim sup n→∞ P (inf [S n (ns), s ∈ [ε, θ -δ]] = 0) = 0, since (1 -e -s )EK -s > 0 for s ∈ [ε, θ -δ].
This ends the proof of the first claim in (i) when EK is finite. The second claim in (i) is then a straightforward consequence of the first one and of (ii) in Lemma 4.1, from which N n (ns)/n → 1e -s in probability, uniformly on compacts of R + .

When EK = ∞, we consider K (L) (w) = min{K(w), L} for a truncation level L > 0. By the above proof, we obtain lim n→∞ τ

(L) n /n = θ (L) 1 Surv GW (L) with obvious notations. Since τ (L) n ≤ τ n , lim L→∞ θ (L) = θ = ∞
and Surv GW (L) ր Surv GW as L ր ∞, we deduce that τ n /n → θ on Surv GW by letting L tend to ∞. On the extinction event (Surv GW ) ∁ , we obviously have τ n /n → 0 since τ n is less than the total number of nodes in the tree. This proves the first claim in (i). For the second one, we note in the same way that lim n→∞ N n (τ

(L) n )/n = p (L) 1 Surv GW (L)
and lim L→∞ p (L) = 1 (pay attention that the coupon collector does not feel the truncation). Since, N n (τ

(L) n ) ≤ N n (τ n ) ≤ n,
we deduce that lim n→∞ N n (τ n )/n = 1 on Surv GW . On the extinction event, it obviously holds N n (τ n )/n → 0.

We now turn to the proof of assertion (ii). By construction, it must hold

N n (τ n ) ≤ τ n + 1 ≤ Z GW
tot , which is a.s. finite when EK ≤ 1. By [START_REF] Kesten | Sidoravicius: The spread of a rumor or infection in a moving population[END_REF], for any A ≥ 0, lim n→∞ P(N n (τ n ) ≤ τ n , Z GW tot ≤ A) = 0, which proves that, asymptotically, all the emissions before exhaustion of the capital are (almost surely) successful on the event {Z GW tot ≤ A}. Therefore, asymptotically, all the emissions before exhaustion are (almost surely) successful, which is to say that, asymptotically with probability 1, every node of the tree receives the information.

Proof of the Gaussian fluctuations in the case of a light tail

Proof of Theorem 2.3. By the invariance principle, (n -1/2 R(nq) -nqEK law -→ B(qσ 2 K )) q≥0 in D(R + ) with B a Brownian motion. By independence of (K i ) i and (∆ i,n ) i , we have from Lemma 4.1:

n -1/2 (R(nq) -nqEK) q≥0 (N n (ns) -n(1 -e -s )) s≥0 law -→ B qσ 2 K q≥0 B σ N (s) 2 s≥0 (28)
as n → ∞, in D(R + ) 2 endowed with the product topology generated by the J1 topology (the convergence holding true as well for the uniform topology), where B and B are independent. Then, the convergence

n -1/2 R(N n (ns)) -n(1 -e -s )EK s≥0 law -→ B (1 -e -s )σ 2 K + B (EK) 2 σ N (s) 2 s≥0 (29)
holds in the Skorohod space. Actually, we claim that (29) also holds conditionally on Surv GW , that is under P(•|Surv GW ). The reason is that the process n -1/2 R(N n (ns))-n(1-e -s )EK s≥0 and the event Surv GW are asymptotically independent, see Lemma 4.3 right below. Now, by Theorem 2.2,

L n = τ n -nθ is such that L n /n → 0 as n → ∞ in probability under P(•|Surv GW ). Using (29) with ns = τ n = nθ + L n , we get n -1/2 R(N n (τ n )) -n(1 -e -θ-Ln/n )EK law -→ B pσ 2 K + B (EK) 2 σ N (θ) 2 (30)
under P(•|Surv GW ). Now, we emphasize from (6) that

τ n -n(1 -e -θ-Ln/n )EK = nθ + L n -n(1 -e -θ )EK -ne -θ (1 -e -Ln/n )EK = L n -ne -θ (1 -e -Ln/n )EK. ( 31
)
Since P(R(N n (τ n )) = τ n |Surv GW ) → 1 as n → ∞, we deduce from ( 30) and (31) that, conditionally on survival,

n -1/2 L n -ne -θ (1 -e -Ln/n )EK law -→ B(pσ 2 K ) + B((EK) 2 σ N (θ) 2 ). ( 32
)
Since

n -1/2 L n = n -1/2 (L n -ne -θ (1 -e -Ln/n )EK) 1 -e -θ EK(1 + O(L n /n)) ,
where O stands for the Landau notation (in the neighborhood of 0 in the current setting), we deduce from (32) that

n -1/2 L n law -→ (1 -e -θ EK) -1 [ B(pσ 2 K ) + B((EK) 2 σ N (θ) 2 )] under P(•|Surv GW ). ( 33
)
Noting that 1e -θ EK = 1 -(1p)EK, this proves the first claim and the value of σ 2 τ . To prove the second claim, we note that the left-hand sides in (33) and in the second line of (28) jointly converge as a 2-dimensional vector under the conditional law P(•|Surv GW ). Therefore, 2 under P(•|Surv GW ), and also

n -1/2 N n (τ n ) -n(1 -e -θ ) -e -θ L n law -→ B σ N (θ)
n -1/2 N n (τ n ) -n(1 -e -θ ) law -→ (1 -e -θ EK) -1 e -θ B(pσ 2 K ) + B(σ N (θ) 2 ) ,
conditionally on Surv GW . This completes the proof.

We finally prove Lemma 4.3 Under the assumptions of Theorem 2.3, the process (n -1/2 (R(nq) -nqEK)) q≥0 has the same limits in law under P(•|(Surv GW ) ∁ ) and P.

. It is sufficient to prove that, when P(Surv GW ) < 1, the process (n -1/2 (R(nq) -nqEK)) q≥0 has the same limits in law under P(•|(Surv GW ) ∁ ) and P. From ( 16), we know that, on the event {Z GW tot ≤ A}, for A ≥ 0, the variable K i in the definition of R (see ( 18)) coincides with Ki for i > A, so that the process ⌊nq⌋ j=A Kj = R(nq) -A j=1 K j is independent of the Galton-Watson tree. Therefore, the event {Z GW tot ≤ A} and the process (n -1/2 (R(nq) -nqEK)) q≥0 are asymptotically independent, which is to say that (Surv GW ) ∁ and (n -1/2 (R(nq) -nqEK)) q≥0 are asymptotically independent. Therefore, the process (n -1/2 (R(nq) -nqEK)) q≥0 has the same limits in law under P(•|(Surv GW ) ∁ ) and P.

Proof of the fluctuations in the case of a heavy tail

Proof of Proposition 2.4. Clearly, EK = ∞. By Theorem 2.2, for any ε > 0, as n → ∞,

P(N n (τ n )/n ≥ 1 -ε, Surv GW ) -→ P(Surv GW ). Moreover, {N n (τ n ) = n} ⊃ {N n (τ n ) ≥ n/2, R(⌊n/2⌋) ≥ T n,n } since R(⌊n/2⌋) ≥ T n,n ⇒ R(k) ≥ k for any k ∈ {⌊n/2⌋, . . . , T n,n }. Thus, for any β ∈ (1, 1/α), lim inf n→∞ P N n (τ n ) = n, Surv GW ≥ lim inf n→∞ P R(n/2) ≥ n β , T n,n ≤ n β , Surv GW .
By Markov inequality, P(T n,n > n β ) → 0 as n → ∞, since ET n,n = n-1 i=1 n/(ni) ∼ n→∞ n ln(n). Moreover, P(K 1 ≥ n β ) ≥ (c/2)n -αβ for n large enough, so that, for n large,

P ⌊n/2⌋ i=1 {K i < n β } ≤ 1 - c 2n αβ ⌊n/2⌋ ∼ exp - c 4 n 1-αβ -→ 0 as n → ∞.
Therefore, P(

⌊n/2⌋ i=1 K i ≥ n β ) → 1.
We deduce that lim inf n→∞ P(N n (τ n ) = n, Surv GW ) = P(Surv GW ). Finally, on (Surv GW ) ∁ , we have N n (τ n )/n → 0 in probability, so that P(N n (τ n ) = n,(Surv GW ) ∁ ) → 0.

Proof of Theorem 2.5. By a celebrated result of [START_REF] Erdös | On a classical problem of probability theory[END_REF] (see [START_REF] Durrett | Probability. Theory and Examples[END_REF] pp. 130-132, for a short account),

G (n) = n -1 T n,n -n ln n law -→ G , (34)
where the variable G has a Gumbel distribution,

P(G ≤ x) = e -e -x , x ∈ R. ( 35
)
On the other hand, from the tail assumption for K,

S (n) c = n -1 R(n -1) -cn ln n law -→ S c , (36)
where S c is a totally asymmetric, stable law with index 1 (Cauchy law), depending upon the parameter c. We define S = S 1 . Precisely, the law of S is given by

Ee iuS = exp 1 0 (e iux -1 -iux)x -2 dx + ∞ 1 (e iux -1)x -2 dx + iuc 0 , u ∈ R, where i 2 = -1 and c 0 ∈ R is defined by c 0 = lim n→∞ (E[K; K ≤ n] -c ln n).
Recall from Theorem 2.2 that P(Trans n ∩ Surv GW ) -P(Trans n ) → 0. We have

Trans n ∩ Surv GW = {τ n ≥ T n,n } ∩ Surv GW ⊂ {R(n -1) ≥ T n,n } ∩ Surv GW ⊂ {G (n) -S (n) c ≤ (c -1) ln n} ∩ Surv GW ,
where we have used τ n ≥ T n,n ⇒ R(n -1) = R(N n (T n,n -1)) > T n,n -1 to pass from the first to the second line. The random vector (G (n) , S

c ) converges in law to a couple (G, S c ) with independent components (independence follows from the independence of the processes N n and R).

If c < 1, then P(G (n) -S (n) c ≤ (c -1) ln n) → 0 so that P(Trans n ) → 0. If c > 1,
it obviously holds lim sup n→∞ P(Trans n ) ≤ P(Surv GW ). To tackle the case when c = 1, we observe from Lemma 4.4 below that Surv GW and S (n) 1 are asymptotically independent as n → ∞, so that the random vector (G (n) , S (n) 1 , 1 Surv GW ) converges in law to a triple (G, S, 1 A ) with independent components, where P(A) = P(Surv GW ). As the random variable G -S has a continuous cumulative distribution function, we get: (-e -S )), the last equality following from (35).

lim sup n→∞ P(Trans n ) ≤ lim sup n→∞ P {G (n) -S (n) 1 ≤ 0} ∩ Surv GW = P(Surv GW )P(G ≤ S) = P(Surv GW )E(exp
We now turn to the reverse bound in the case when c ≥ 1 (when c < 1, the proof is over). Consider ε ∈ (0, 1) and a positive sequence (δ n ) n≥1 such that

δ n ln n → 0, nδ n → ∞,
as n → ∞. We write

Trans n ∩ Surv GW ⊃ {R(n(1 -δ n )) > T n,n , Surv GW } ∩ {N n (τ n ) ≥ n(1 -ε), Surv GW } ∩ {R(n(1 -ε)) > T n(1-δn),n }, the right-hand side being denoted A ∩ B ∩ C. Indeed, on B ∩ C, τ n < T n,n ⇒ τ n = R(N n (τ n )) > T n(1-δn)
,n so that τ n > T n(1-δn),n . Then, by the same argument, it must hold

τ n ≥ T n,n on A ∩ B ∩ C as otherwise τ n would be equal to R(N n (τ n )) ≥ R(N n (T n(1-δn),n )) = R(n(1 -δ n )) > T n,n
, yielding to a contradiction. Below we will use the estimate

P(A ∩ B ∩ C) ≥ P(A) -P(B ∁ ∩ A) -P(C ∁ ).
As above, we write

{R(n(1 -δ n )) > T n,n , Surv GW } as {n -1 (R(n(1 -δ n )) -cn ln n) -G (n) > -(c -1) ln n, Surv GW }. Lemma 4.4 says that n -1 (R(n(1 -δ n )) -cn ln n) -G (n) converges in law towards S c -G as n → ∞. Therefore, when c > 1, we get lim n→∞ P R(n(1 -δ n )) > T n,n , Surv GW = P(Surv GW ).
When c = 1, we make use of Lemma 4.4 again. By asymptotic independence, we get as in the proof of the upper bound:

lim n→∞ P R(n(1-δ n )) > T n,n , Surv GW = lim n→∞ P ( R(n(1-δ n )) n -ln n) -G (n) > 0, Surv GW = P(Surv GW )P(G < S) = P(Surv GW )E(exp(-e -S )). By Theorem 2.2 with EK = ∞, P(N n (τ n ) ≤ n(1 -ε), Surv GW ) → 0 as n → ∞. It remains to show that P R(n(1 -ε)) > T n(1-δn),n → 1 as n → ∞.
We have

E T n(1-δn),n = ⌊n(1-δn)⌋-1 i=1 n n -i ∼ n ln 1/δ n , Var T n(1-δn),n ≤ ⌊n(1-δn)⌋ i=1 n 2 (n -i) 2 ∼ n/δ n = o(n 2 ),
as nδ n → ∞. Tchebyshev inequality implies that T n(1-δn),n = o(n ln n) for nδ n → ∞. On the other hand, R(n(1ε)) is of order n ln n, which ends the proof.

We finally prove Lemma 4.4 Under the assumptions of Theorem 2.5. Given a sequence of positive reals

(δ n ) n≥1 such that δ n ln n → 0 as n → ∞, the sequence (n -1 R(n(1 -δ n )) -c ln(n)) n≥1 converges in law towards S c . Moreover, as n → ∞, the event Surv GW and the variable n -1 R(n(1 -δ n )) -c ln n become independent.
. In order to prove that the sequence (n

-1 R(n(1 -δ n )) -c ln(n)) n≥1 converges in law towards S c , it is sufficient to check that (n -1 [R(n -1) -R(n(1 -δ n ))]
) n≥1 converges towards 0 in probability. For any ε > 0 and A > 0, we have:

P R(n -1) -R(n(1 -δ n )) ≥ nε ≤ P ∃ℓ = ⌊n(1 -δ n )⌋ + 1, . . . , n -1 : K ℓ ≥ A + P n i=⌈n(1-δn)⌉ K i 1 {K i ≤A} ≥ nε ≤ P ∃ℓ = ⌊n(1 -δ n )⌋ + 1, . . . , n -1 : K ℓ ≥ A + ε -1 δ n E K1 {K≤A} ≤ 1 -1 -P(K ≥ A) nδn + c ′ ε -1 δ n ln(A),
for some constant c ′ independent of n and A. For A = n, we have 1 -P(K ≥ n) ∼ 1c/n by assumption and thus (1

-P(K ≥ n)) nδn ∼ exp(-cδ n ), which tends to 1 as n → ∞. As δ n ln n → 0 as n → ∞, we deduce that (n -1 [R(n -1) -R(n(1 -δ n ))]) n≥1 indeed converges towards 0 in probability.
The asymptotic independence is proved as in the proof of Lemma 4.3.

Proofs of large deviations

Before starting the proofs we recall a few facts about the LDP for the coupon collector. As r is increased from 0 to t ∧ 1, the function r → ρ(r, t) in ( 12) decreases from +∞ to zero when t ≤ 1 or to a positive value otherwise. The value ρ = 1 corresponds to the typical case r = 1e -t ; and ρ > 1 (resp. ρ < 1) to large deviations with N n (nt) much smaller (resp. larger) than E[N n (nt)] (cf Appendix A.2.1 of [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF]). The LDP holds at the process level for (N (nt); t ≥ 0), and the overwhelming contribution to the probability of the event {N n (nt) ∈ n(rε, r + ε)} occurs in the neighborhood of the optimal path N n (ns) = ng(s) with

g(s) = 1 -e -sρ ρ , s ∈ [0, t], (37)
and ρ = ρ(r, t) as before (see also Lemma 5.1 below for the uniqueness of the optimal path).

Proof of Lemma 2.6. (i) Lower semi-continuity is easily checked. Boundedness of the level sets follows from the lower bound

rI t r ≥ r a 0 t r -ln E exp(a 0 K) ≥ a 0 t -ln E exp(a 0 K) ,
which implies for a well-chosen value of a 0 that t must be bounded when F(r, t) is bounded; boundedness of r easily follows since r ≤ t when F(r, t) is finite.

To determine the domain of F, we recall the expression of Dom(I) in terms of k * , k * , and write Dom(F) = {t/r ∈ Dom(I), r/t ∈]0, 1]} ∪ {(0, 0)}.

Continuity on the first set in the above union follows from that of I on its domain. If k * = ∞, F is unbounded in any neighborhood of the origin, so it is not continuous at this point. If k * < ∞, then I is bounded on its domain and continuity at the origin of F easily follows.

(ii) trivially holds. (iii) Finally, roots of F must satisfy r = 0 or t/r = EK, for 0 < r ≤ t∧1, as EK is the only zero of I. When r = 0, t must be zero as well. When 0 < r ≤ t ∧ 1, the condition t/r = EK requires EK to be strictly greater than 1. (When EK = 1, the condition t = r > 0 implies t ≤ 1 and J t (r) = J t (t) = t > 0.) When EK > 1, t/r = EK implies tρ = θ (compare with ( 6)) and J t (r) = 0 implies r = 1e -t , that is ρ = 1 and thus t = θ and r = p (see [START_REF] Boucheron | Bins and balls: large deviations of the empirical occupancy process[END_REF]). Conversely, it is well-checked that 0 is a root of F and that (p, θ) is a root as well when EK > 1.

Proof of Theorem 2.7. Upper bound. We start with the case when r, t satisfy 0 < r < t ∧ 1. Given ε, δ > 0, we are to prove the local upper bound lim sup

ε,δ→0 + lim sup n→∞ 1 n ln P N n (τ n )/n ∈ [r -ε, r + ε], τ n /n ∈ [t -δ, t + δ] ≤ -F(r, t). (38)
We first tackle the case r < 1e -t , t/r < EK, which is relevant only when EK > 1. Without any loss of generality, we can assume that ε and δ satisfy

r + ε < 1 -e -(t-δ) , (t + δ)/(r -ε) < EK. (39)
We then define the events

A = {N n (n(t -δ)) ≤ n(r + ε)}, B = {R(n(r -ε)) ≤ n(t + δ)}. (40)
Since N n , R are nondecreasing,

N n (τ n ) ∈ [n(r -ε), n(r + ε)], τ n ∈ [n(t -δ), n(t + δ)] ⊂ A ∩ B,
and by independence of the processes N n and R, we get

P N n (τ n )/n ∈ [r -ε, r + ε], τ n /n ∈ [t -δ, t + δ] ≤ P(A)P(B). (41)
From the LDP's ( 9) and ( 10), and by (39), we have lim sup

n→∞ 1 n ln P N n (τ n )/n ∈ [r -ε, r + ε], τ n /n ∈ [t -δ, t + δ] ≤ -J t-δ (r + ε) -(r -ε)I((t + δ)/(r -ε)).
By lower semi-continuity of I on the whole R and by continuity of (r, t) → J t (r) at the prescribed value of (r, t), we obtain (38). With similar arguments, one easily obtain the same result in all other cases of 0 < r < t ∧ 1.

We are now left with proving the local upper bound on the boundary. For (r, t) = (0, 0), there is nothing to prove since the rate function is zero. The case r = 0 < t is simple since it is enough to bound

P N n (τ n )/n ≤ ε, τ n /n ∈ [t -δ, t + δ] ≤ P N n (n(t -δ))/n ≤ ε ,
to get a rate of decay J t-δ (ε) which tends to ∞ as both δ and ε vanish. The cases r = 1 < t and r = t ≤ 1 use similar arguments as above in the general case.

We have proved the upper bound for compact sets. To extend it to closed sets, it is enough to show that lim

t→∞ lim sup n→∞ 1 n ln P τ n /n ≥ t = -∞. (42)
For this, we observe that

{τ n ≥ nt} ⊂ {R(N n (nt)) ≥ ⌊nt⌋} ⊂ {R(n) ≥ ⌊nt⌋}.
For t > EK, the probability of the last event can be estimated by Cramér's bound, yielding

P(τ n ≥ nt) ≤ exp(-nI(t)).
Since I(t) tends to ∞ as t → ∞, we obtain (42).

Lower bound. The lower bound is subtle. It sufficient to show that, for all r, t with F(r, t) < ∞ and all η > 0, lim inf

n→∞ 1 n ln P N n (τ n )/n ∈ [r -η, r + η], τ n /n ∈ [t -η, t + η] ≥ -F(r, t). ( 43
)
We start with the general case when r, t satisfy 0 < r < t∧1 and I(t/r) < ∞. (If I(t/r) = ∞, the lower bound above is trivial.)

First Step. The proof holds in several steps. The first one is to bound from below the lefthand side above by the probability of an event depending in a separate way on the dynamics of the coupon collector on the one hand and on the capitals of the servers and the Galton-Watson tree on the other hand. We are thus given 0 < η ′ < η < r and 0 < ε ′ < 2ε such that r + η + ε < 1 ∧ t, ε < rη/(4t) < η/4, η ′ < (1r/t)η and η ′ (1 + t/r) < ε ′ . For an integer m ∈ [nε ′ , n(εε ′ )], we define the events

A = {N n (nt + nη) ≤ nr + nε}, A ′ = {N n (nε) = ⌊nε⌋ + 1}, A ′′ = {N n (ℓ) ≥ ℓr/t + nε(1 -r/t) -nη ′ ; nε ≤ ℓ ≤ nt -nη} ∩ {N n (nt -nη) ≤ nr + nε}, B = {R(nr + nε) -R(m) ≤ nt + nη/2}, B ′′ = {R(ℓ) -R(m) ≥ (ℓ -m)t/r -nη ′ ; m ≤ ℓ ≤ nr + nε}.
Recall that N n (s) = N n (⌊s⌋) and similarly for R. We also define

B ′ = {R(m) ∈ [nε, 2nε], Z GW tot ≥ nε}. (44)
On A ′ , it holds T i+1,n = i(i ≤ nε), so that the emission process cannot stop before nε unless the total size of the Galton-Watson tree is strictly less than nε. Therefore,

A ′ ∩B ′ ⊂ {τ n ≥ nε}. Further, A ′ ∩ A ′′ ∩ B ′ ∩ B ′′ ⊂ {τ n > n(t -η)}. Indeed, on A ′ ∩ A ′′ ∩ B ′ ∩ B ′′ , for nε ≤ ℓ ≤ nt -nη, R N n (ℓ) ≥ R ℓr/t + nε(1 -r/t) -nη ′ ≥ ℓr/t + nε(1 -r/t) -nη ′ -m t/r + R(m) -nη ′ ≥ ℓ + (nε -m)(t/r -1) + R(m) -m -nη ′ (1 + t/r) > ℓ + nε ′ -nη ′ (1 + t/r) > ℓ, (45)
where, to pass from the second to the third line, we use the fact that, for the prescribed values of ℓ, ℓr/t

+ nε(1 -r/t) -nη ′ ∈ [m, nr + nε]. Moreover, on A ∩ B ∩ B ′ , R N n (nt + nη) ≤ R nr + nε ≤ nt + nη/2 + R(m) ≤ nt + nη/2 + 2nε < nt + nη, so that, τ n ≤ n(t + η) on A ∩ B ∩ B ′ . Therefore, A ∩ A ′ ∩ A ′′ ∩ B ∩ B ′ ∩ B ′′ ⊂ {N n (τ n ) ∈ [n(r -η), n(r + η)], τ n ∈ [n(t -η), n(t + η)]}, (46) since, on A ∩ A ′ ∩ A ′′ ∩ B ∩ B ′ ∩ B ′′ , N n (τ n ) ≥ N n (n(t -η)) ≥ n(t -η)r/t + nε(1 -r/t) -nη ′ ≥ nr -nηr/t -nη ′ ≥ nr -nη, N n (τ n ) ≤ N n (n(t + η)) ≤ nr + nε ≤ nr + nη. (47)
By independence of the processes N n and R, we get

P(N n (τ n )/n ∈ [r -η, r + η], τ n /n ∈ [t -η, t + η]) ≥ P A ∩ A ′ ∩ A ′′ P B ∩ B ′ ∩ B ′′ . ( 48
)

Second

Step. We estimate the first factor in the right-hand side by using Markov's property:

P A ∩ A ′ ∩ A ′′ ≥ inf i∈ Î P A| Âi P A ′′ |A ′ P A ′ , with Âi = N n (nt -nη) = i , Î = {⌈n(r -ηr/t) + nε(1 -r/t) -nη ′ ⌉, . . . , ⌊nr + nε⌋}. (49)
Clearly, P(A ′ ) is bounded from below by the probability for the binomial distribution with parameters ⌊nε⌋ and ε to be equal to zero. We get

P A ′ ≥ e -nε| ln(1-ε)| . (50)
Similarly, inf i∈ Î P(A| Âi ) is bounded from below by the probability for the binomial distribution with parameters ⌊2nη⌋ + 1 and 1r + ηr/tε(1r/t) + η ′ < 1r + η to be equal to 0. Therefore, inf

i∈ Î P A| Âi ≥ e -(2nη+1)| ln(r-η)| . (51)
We now turn to P(A ′′ |A ′ ). We observe that the conditional probability P • |A ′ is (up to a shift in time) the law of the coupon collector with n images when starting from nε different images, already collected at the initial time. Since n(r-ηr/t)+nε(1-r/t)-nη ′ ≤ nr+n(ε-ηr/t)-nη ′ ≤ nrnη ′ , we deduce from the large deviation lower bound in [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF]:

P Â|A ′ ≥ exp{-nJ ε t-(η+ε) (r) + o(n)} with  = n(r -ηr/t) + nε(1 -r/t) -nη ′ ≤ N n (nt -nη) ≤ nr + nε = i∈ Î Âi , (52)
the rate function J ε t-(ε+η) (r) being given by Theorem 2.7 in [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF] (with I = 0, α 0 = 1ε and ω 0 = 1r therein). Precisely, (52) follows from the LDP for the "time-shifted" variable N n (n(t -(η + ε))) with N n (0) = ⌊nε⌋ + 1 as initial condition. Using the same notations as in [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF], J ε t (r) may be expressed as the relative entropy:

J ε t (r) = (1 -ε) 1 -r 1 -ε ln 1 -r (1 -ε)e -t + (1 -ε)C ε j≥1 P j (ρ ε t) ln C ε P j (ρ ε t) P j (t)
+ ε j≥0 P j (ρ ε t) ln P j (ρ ε t) P j (t) ,

where P j (α) is the jth weight of the Poisson distribution of parameter α, ρ ε is the unique root of 1r

1 -ε + 1 -ερ ε (1 -ε)ρ ε (1 -e -ρ ε t ) = 1, (53)
and C ε reads:

C ε = 1 -ερ ε (1 -ε)ρ ε .
It is plain to check that, as ε tends to 0, ρ ε converges towards ρ = ρ(r, t) and C ε towards 1/ρ. Moreover, standard computations yield j≥0 P j (ρ ε t) ln P j (ρ ε t)

P j (t) = -(ρ ε -1)t + ρ ε ln(ρ ε )t j≥1 P j (ρ ε t) ln P j (ρ ε t) P j (t) = -(ρ ε -1)t + ρ ε ln(ρ ε )t + (ρ ε -1)te -ρ ε t ,
so that, by the definition of ρ(r, t),

lim ε→0 J ε t (r) = (1 -r) ln(1 -r) + (1 -r)t - ln ρ ρ 1 -e -ρt - ρ -1 ρ t + t ln ρ + ρ -1 ρ te -ρt = J t (r).
Similarly, it holds J ε t-(η+ε) (r) -→ J t-η (r), as ε → 0.

Therefore, (52) may be expressed as

P Â|A ′ ≥ exp{-n[J t (r) + δ(η) + δ ′ (ε; η)] + o(n)}, (54)
where δ(η) is a generic term that tends to 0 with η and δ ′ (ε; η) is a generic term that tends to 0 with ε when η > 0 is given. We then claim that P(A ′′ |A ′ ) satisfies the same lower bound, that is

P A ′′ |A ′ ≥ exp{-n[J t (r) + δ(η) + δ ′ (ε; η)] + o(n)}. (55)
Basically, it comes from the fact that the optimal path explaining the LD of the random variable N n (n(tη)) in the neighborhood of r given the initial condition in A ′ is lying above the linear constraint in A ′′ . As already explained, the right optimal path to consider is the one when the collector has already collected ⌊nε⌋ + 1 coupons at (rescaled) time ε. We denote it by g ε : [ε, tη] → R. By Theorem 2.8 in [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF] and Lemma 5.1 right below, the optimal limit path on [0, t] (as n → ∞) for the coupon collector running from the proportion ε to the proportion r of collected coupons in time t is unique and reads (we put a tilde over g ε below to emphasize that the interval is shifted in time and that the terminal time is t and not t -(η + ε)):

gε : [0, t] ∋ s → ε + 1 -ερ ε ρ ε 1 -e -ρ ε s , (56)
which is equal to r at time t. By concavity of gε ,

ng ε (s) ≥ n s t gε (t) + n 1 - s t gε (0) = n s t (r -ε) + nε, 0 ≤ s ≤ t.
Coming back to g ε , we deduce from the inequality t -(ε + η) ≤ ttε/r that

ng ε (s) ≥ n s -ε t -(ε + η) (r -ε) + nε ≥ n (s -ε)r t + nε, ε ≤ s ≤ t -η, (57)
which proves that g ε is strictly above the linear constraint in A ′′ . Optimality of g ε then says that (compare with (52))

lim sup n→∞ n -1 ln P Â, ∃s ∈ [ε, t -η] : N n (ns) ≤ n(g ε (s) -η ′ )|A ′ < -J ε t-(η+ε) (r). ( 58
)
Following the proof of (54), we deduce from (57) and ( 58) that (55) holds. From (49,50,51,55), we deduce that

P A ∩ A ′ ∩ A ′′ ≥ exp{-n[J t (r) + δ(η) + δ ′ (ε; η)] + o(n)}, (59)
with δ(η) → 0 as η → 0 and δ ′ (ε; η) → 0 as ε → 0 for a given η > 0.

Third Step. We now provide a lower bound for P(B ∩ B ′ ∩ B ′′ ) in (48). To this end, we shall use the stopping time T m,n = inf{t ≥ 0 : N n (t) = m} together with the set [START_REF] Erdös | On a classical problem of probability theory[END_REF] for the notations). Therefore, on C, R(m) has the form:

C = {τ n ≥ T m,n }. On C, it holds N n (τ n ) ≥ m, that is m ≤ card T • (∞) (see
R(m) = m i=1 K(X(T i,n )).
In particular, on C, R(m) ≥ nε ⇒ Z GW tot ≥ nε, which implies that C ∩ B ′ = C ∩ {R(m) ∈ [nε, 2nε]}. Since C may be also expressed as C = {R(N n (ℓ)) > ℓ; ℓ = 0, . . . , T m,n -1} and ℓ < T m,n ⇒ N n (ℓ) ≤ m, we deduce that

C ∩ B ′ ∈ σ(T 1,n , . . . , T n,n ) ∨ σ(K 1 , . . . , K m ). ( 60
)
By Proposition 3.1, we deduce that C ∩ B ′ is independent of B ∩ B ′′ , so that

P B ∩ B ′ ∩ B ′′ ≥ P C ∩ B ′ P B ∩ B ′′ . (61)
Now, we emphasize that τ n = N n (τ n ) on C ∁ (which means that the capital is exhausted at some time less than or equal to n). Thus, on C ∁ ,

τ n = N n (τ n ) ≤ N n (T m,n ) = m ≤ nε.
Therefore, by Lemma 4.2, for ε < ε 0 ,

lim n→∞ P C ∁ ∩ Surv GW = 0.
Finally, since P(E ∩ F ) ≥ P(E) -P(F c ),

P C ∩ B ′ ≥ P C ∩ Surv GW ∩ {R(m) ∈ [nε, 2nε]} ≥ P(C ∩ Surv GW ) -P R(m) ∈ [nε, 2nε] = P(Surv GW ) -P C ∁ ∩ Surv GW -P R(m) ∈ [nε, 2nε] , (62)
the second term in the last line converging to 0 as n tends to ∞.

Fourth

Step. We now complete the proof when EK > 1, which is a simpler case to handle than the opposite case EK ≤ 1. We then choose

m = ⌊ ζ EK nε⌋, with ζ = min 1 + EK 2 , 3/2 .
Clearly, m ∈ [nε/EK, (1 + EK)/(2EK)ε] ⊂ [nε ′ , n(εε ′ )] as required, for some well-chosen ε ′ . Moreover, the typical values of R(m) are in the neighborhood of ζnε ∈ (nε, 2nε). Therefore, by the law of large numbers, the third term in the right-hand side in (62) tends to 0 as n → ∞. We deduce lim inf

n→∞ P C ∩ B ′ ≥ P(Surv GW ) > 0, (63)
since EK > 1. Moreover, by Mogulskii's Theorem (see Theorem 5.1.2 in [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF]), we have a lower bound for the probability that the process (n -1 R(ns)) 0≤s≤r+ε is in the neighborhood of the path [0, r + ε] ∋ s → st/r. We then observe that

B ∩ B ′′ ⊃ (ℓ -m)t/r -nη ′ ≤ R(ℓ) -R(m) ≤ (ℓ -m)t/
P(B ∩ B ′′ ) ≥ exp{-n(r + ε)I(t/r) + o(n)}. (64)
Collecting (48,59,61,63,64), we deduce that (for a possibly new choice of δ ′ (ε; η))

lim n→∞ n -1 ln P N n (τ n )/n ∈ [r -η, r + η], τ n /n ∈ [t -η, t + 2η] ≥ -J t (r) + rI(t/r) -δ(η) -δ ′ (ε; η),
which tends to -[J t (r) + rI(t/r)]δ(η) as ε ց 0. Since η can be chosen as small as needed, we complete the proof of (43) in the case EK > 1.

Fifth

Step. We now investigate the case EK ≤ 1. The above argument fails since m cannot be chosen as ⌊ζnε/EK⌋ on the one hand and since P(Surv GW ) = 0 on the other hand. We are thus to give a relevant version of the previous step. We tackle first the case P(K ≥ 2) > 0. The point is to change the probability measure in order to switch back to the case EK > 1. The change of probability relies on the same trick as in the proof of Cramer's theorem. Since k * = 0 and k * ≥ 2, it is standard that, for any ξ ∈ (1, 2), there exists α ∈ R such that ϕ ′ (α) = ξ, where ϕ(α) = ln E exp(αK) .

We now choose ξ = 1 + ε and set ζ ′ = (1 + ξ)/2 ∈ (1, 3/2). For m = ⌊ζ ′ nε/ξ⌋ (m playing below the same role as in the first step -note in particular that m is in [nε ′ , n(εε ′ )] for some well-chosen ε ′ -), we then define P as

d P dP = exp m i=1 {αK i -ϕ(α)} .
It is plain to see that, under P, the variables (K i ) i≥1 are independent, the variables (K i ) i≥m+1 having the same distribution as they have under P and the variables (K i ) 1≤i≤m being identically distributed with ẼK i = ξ, i = 1, . . . , m, where Ẽ denotes the expectation under P. Following (61), we write

P(C ∩ B ′ ) = Ẽ dP d P 1 C∩B ′ = Ẽ exp -αR(m) + mϕ(α) 1 C∩B ′ ≥ exp -2nαε + mϕ(α) P(C ∩ B ′ ). (65)
By (60), the probability of C ∩ B ′ under P coincides with the probability of C ∩ B ′ under P when the expectation of the reproduction law of the Galton-Watson tree is strictly larger than 1. Since m = ⌊ζ ′ nε/ ẼK⌋, with ζ ′ = min[(1 + ẼK)/2, 3/2], we know from the case EK > 1 that

lim n→∞ P(C ∩ B ′ ) = σ > 0,
where σ stands for the probability that the Galton-Watson tree survives when the reproduction is governed by the law of K under P. Finally, we get from (65):

lim inf n→∞ n -1 ln P C ∩ B ′ ≥ -εξ -1 2αξ -ζ ′ ϕ(α) = εG(ξ), (66)
where G(ξ) remains bounded as ξ ranges over any compact subset of [START_REF] Alves | Random walks systems on complete graphs[END_REF][START_REF] Alves | Phase transition for the frog model[END_REF]. In particular, the right hand side in (66) tends to 0 with ε. The end of the proof is then the same as in the case when P(Surv GW ) > 0.

In the case P(K ≤ 1) = 1, it holds I(t/r) = ∞ and thus F(t, r) = ∞ as well, so that the lower bound is obvious.

Final

Step. Now we prove the lower bound on the boundary. For r = t = 0, we introduce k 0 = min{k ≥ 0 : P(K = k) > 0}, and we write

P N n (τ n )/n ≤ η, τ n /n ≤ η ≥ P(K 1 = k 0 , N n (k 0 ) = 1) = P(K = k 0 )n -k 0 ,
showing the bound with F(0, 0) = 0.

It remains to tackle the cases 0 < r = t ≤ 1 and 0 < r = 1 < t. Without any loss of generality, we can assume that I(t/r) < ∞ as otherwise the bound is obvious. Given an open set O ∋ (r, t) (O ∋ (0, 0)), we deduce from Lemma 2.6 that F is continuous on

O ∩ {(r ′ , t ′ ) ∈ R 2 : 0 < r ′ ≤ t ′ ∧ 1, t ′ /r ′ ∈ Dom(I)}.
If 0 < r = 1 < t, then we can find a sequence (r n , t n ) n≥1 , converging towards (r, t), such that r n ր r, t n ր t and t n /r n = t/r, with r n < 1 < t n for any n ≥ 1. Thus,

F(r, t) ≥ inf F(r ′ , t ′ ), (r ′ , t ′ ) ∈ O ′ , O ′ = O ∩ (r ′ , t ′ ) ∈ R 2 : 0 < r ′ < t ′ ∧ 1 . (67)
Assuming without any loss of generality that

O ⊂ {(r ′ , t ′ ) ∈ R 2 : 1 -η < r ′ < 1 + η < t -η < t ′ < t + η}, for some η > 0, we deduce that lim inf n→∞ n -1 ln P (N n (τ n )/n, τ n /n) ∈ O ≥ lim inf n→∞ n -1 ln P (N n (τ n )/n, τ n /n) ∈ O ′ ≥ -inf F(r ′ , t ′ ), (r ′ , t ′ ) ∈ O ′ = -inf F(r ′ , t ′ ), (r ′ , t ′ ) ∈ O , (68)
the second line following from the LDP we proved above for (r, t) satisfying 0 < r < t ∧ 1. This is enough to conclude. Assume 0 < r = t ≤ 1, and I(1) < ∞ since otherwise the bound is obvious. If in addition k * ≥ 2, (67) still holds, and we can repeat (68).

It thus remains to handle the case when K has a Bernoulli distribution of parameter p ∈ (0, 1] (if p = 0, K ≡ 0 and the lower bound is obvious) and O is an open set containing some point (r, t) with 0 < r = t ≤ 1. As above, O might intersect the line (1, t ′ ) for t ′ in the neighborhood of 1; thanks to (68), this has no real consequences. Then, for some small η > 0,

P N n (τ n ) ∈ [n(t-η), n(t+η)], τ n ∈ [n(t-η, t+η)] ≥ P N n (⌊n(t -η)⌋) = ⌊n(t -η)⌋ + 1, N n (⌊n(t + η)⌋) ≤ ⌊n(t + η)⌋ × P R(⌊n(t -η)⌋ + 1) = ⌊n(t -η)⌋ + 1 . (69) Clearly, P R(⌊n(t-η)⌋+1) = ⌊n(t-η)⌋+1 = p ⌊n(t-η)⌋+1 ≥ p n(t-η) = exp -n(t-η)I(1) , (70)
as

I(x) = x ln(x/p) + (1-x) ln[(1-x)/(1-p)], for x ∈ [0, 1], in the Bernoulli case. Moreover, P N n (⌊n(t -η)⌋) = ⌊n(t -η)⌋ + 1, N n (⌊n(t + η)⌋) ≤ ⌊n(t + η)⌋ ≥ (t -η -1/n) ⌊n(t-η)⌋ i=1 (1 -i/n) = (t -η -1/n) exp ⌊n(t-η)⌋ i=1 ln(1 -i/n) . (71)
It remains to see that

lim n→∞ -n -1 ⌊n(t-η)⌋ i=1 ln(1 -i/n) = - t-η 0 ln(1 -u)du = (1 + η -t) ln(1 + η -t) + t -η -→ (1 -t) ln(1 -t) + t = J t (t) as η → 0, (72)
using ρ(t, tδ) ∼ 2t -2 δ for t ≤ 1 and δ ց 0 in [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF]. By (69,70,71,72), the proof is easily completed.

We finally prove:

Lemma 5.1 The path g in (37) is the only optimal path minimizing the limit cost for getting r as proportion of collected coupons over the rescaled time interval [0, t].

The proof is an adaptation of Subsection A.4 in [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF]. It is sufficient to prove that the function ε → G[ε] therein (see also the expression right below) is strictly convex in the neighborhood of 0 + whenever γ is different from γ, where γ = 1g and γ stands for the proportion of non-collected coupons along another path with the same boundary conditions as γ at times 0 and t. We notice that G[ε] has the form (see Subsection A.1.2 in [START_REF] Dupuis | Large deviation asymptotics for occupancy problems[END_REF]):

G[ε] = t 0 -γs + ε ηs ln - γs + ε ηs γ s + εη s + 1 + γs + ε ηs ln 1 + γs + ε ηs 1 -(γ s + εη s ) ds,
where η = γγ. Therefore, G[ε] can be splitted into three terms:

G[ε] = t 0
γs + ε ηs lnγsε ηs + 1 + γs + ε ηs ln 1 + γs + ε ηs ds

+ t 0 γs + ε ηs ln γ s + εη s -γs + ε ηs ln 1 -(γ s + εη s ) ds - t 0 ln 1 -(γ s + εη s ) ds = G 1 [ε] + G 2 [ε] + G 3 [ε].
It is well seen that G ′′ 1 [ε] is well-defined in the neighborhood of 0 and is always (strictly) positive unless η ≡ 0. Similarly, G ′′ Therefore, G(r) = 0 if r = 0, and G(r) = ∞ if r > 1, as announced. In the case r ∈ (0, 1], the infimum above can be restricted to the values of t in [r, ∞). Then, F(r, t) reads F(r, t) = (1r) ln(1r) + r I(λ) + (λ -1) ln(tρ/λr) + λ exp(-tρ) , The point is thus to prove the lower bound, which cannot be proved from the LDP directly since the lower bound in the LDP holds for open subsets only. Then, we can focus on the case P(K ≥ 1) > 0 as otherwise both sides in the statement of Theorem 2.8 are infinite. We then follow the proof of the lower bound in the proof of Theorem 2.7. With the same notation as in the first step of the proof (in particular, given 0 < r < 1 ∧ t), we already know that lim inf Thus,

P(N n (τ n ) = n) ≥ P A ′ ∩ A ′′ ∩ A ′′′ ∩ B ′ ∩ B ′′ ∩ B ′′′ ≥ P A ′ ∩ A ′′ ∩ A ′′′ P B ′ ∩ B ′′ ∩ B ′′′ ≥ P A ′ ∩ A ′′ ∩ A ′′′ P C ∩ B ′ ∩ B ′′ ∩ B ′′′ , (74)
with C as in the third step of the proof of the lower bound in Theorem 2.7. From (47), it is plain to see that By the proof of the lower bound in Theorem 2.7, we know that lim inf n→∞ n -1 ln P(A ′ ∩ A ′′ ) + ln P(C ∩ B ′ ∩ B ′′ ) ≥ -F(r, t) + δ(η) + δ ′ (ε; η).

P A ′′′ |A ′ ∩ A ′′ ≥ exp
In the end we deduce that lim inf n→∞ n -1 ln P N n (τ n ) = n ≥ -F(r, t) + δ(η) + δ ′ (ε; η) + δ ′′ (r, η), for 0 < r < t ∧ 1. Assume then that t > 1 and t ∈ Dom • (I) (interior of Dom(I)). Then, by continuity of F (see Lemma 2.6), we can let r tend to 1. Letting η and ε also tend to 0, we get: It thus remains to tackle the case when Dom • (I) ∩ (1, ∞) = ∅. Actually, this is the case when K is a Bernoulli random variable. Then, we can follow the special case we discussed in the final step of the proof of Theorem 2.7. Indeed, for 0 < r < 1, we deduce from (69,70,71) (with t = 1 and r = tη therein), P N n (τ n )/n ≥ r ≥ (r -1/n) exp - It then remains to check that it is equal to -G(1). Clearly, the infimum in the definition of G( 1) is reduced to the s's such that λ(s) = 1, that is to s = 0. We easily deduce that G(1) = 1+I(1).

lim inf n→∞ n -1 ln P N n (τ n ) = n ≥ -F(1, t).
This completes the proof of the variational formula. Since it has compact level sets, the lower semi-continuous function F, when restricted to the set of points (r, t) with r = 1, achieves its minimum, and the value of the minimum is non zero. Hence G(1) > 0.

Figure 1 :

 1 Figure 1: Rate function F for K Poisson distributed with mean 1.4998. It vanishes at the origin and at (p, θ) = (.5827, .8740), it is unbounded in neighborhoods of (0, 0) in its domain. For convenience, large values of F are truncated, and the graph over the domain r ≤ .65t is not shown. The dark blue strip corresponds to .65t ≤ r ≤ .67t, and the yellow part of the graph to r ≥ .67t.

3 Proposition 5 . 2

 352 [ε] is non-negative in the neighborhood of 0. Finally,G 2 [ε] = γ s + εη s ln γ s + εη s + 1γ s + εη s ln 1 -(γ s + εη s ) t 0 is independent of ε as η t = η 0 = 0.We finally turn to Proof of Theorem 2.8.First, as an application of Theorem 2.7, we deduce the LDP for the sequence (N n (τ n /n)) n≥1 . Indeed, by Varadhan contraction principle, With the same notations as in the statement of Theorem 2.8, the sequence (N n (τ n )/n) n≥1 obeys a LDP with rate function:G(r) = (1r) ln(1r) + r inf s≥0 I λ(s) + (λ(s) -1) ln (1exp(-s))/r + λ(s) exp(-s) , if r ∈ [0,[START_REF] Alves | Random walks systems on complete graphs[END_REF], and G(r) = ∞ otherwise, and speed n.By Varadhan contraction principle (see[START_REF] Dembo | Large Deviations Techniques and Applications[END_REF] Theorem 4.2.1]), we know that G(r) = inf F(r, t), t ≥ 0 .

  with λ = t/r, tρ solving the equation (1-exp(-tρ))/(tρ) = λ -1 . If λ = 1, then (λ-1) ln(tρ/λr) and ρ in (73) are both considered as 0. Letting s = tρ, we note that s is the unique root of the equation:1exp(-s) s = λ -1 , with λ = 1 if s = 0. As λ ranges over [1, ∞], R ranges over [0, ∞).Expressing λ in terms of s, the proof is easily completed.We now finish the proof of Theorem 2.8. The LDP for N n (τ n )/n yields lim supn→+∞ n -1 ln P N n (τ n ) = n ≤ -G(1), with G(1) = inf s≥0 I λ(s) + (λ(s) -1) ln 1exp(-s) + λ(s) exp(-s) .

n→∞ n - 1

 1 ln P A ∩ A ′ ∩ A ′′ ∩ B ∩ B ′ ∩ B ′′ ≥ -F(r, t) + δ(η) + δ ′ (ε; η),where δ(η) → 0 as η tends to 0 and δ ′ (ε; η) → 0 as ε tends to 0 when η > 0 is given. (As r and t do, ε and η play the same role as in the first step of the proof of the lower bound in Theorem 2.7.) Define now the new events:A ′′′ = {N n (ℓ + 1) = N n (ℓ) + 1; ⌊n(tη)⌋ ≤ ℓ < T n,n }, B ′′′ = {K ℓ ≥ 1; ⌊n(r + ε)⌋ + 1 ≤ ℓ ≤ n}.We claim that, on A′ ∩ A ′′ ∩ A ′′′ ∩ B ′ ∩ B ′′ ∩ B ′′′ , it holds T n,n ≤ τ n . Indeed, by definition of A ′′ , ⌊n(tη)⌋ ≤ T ⌊nr+nε⌋,n , so that, for ℓ ∈ [⌊n(tη)⌋ + 1, T ⌊nr+nε⌋+1,n -1],we have (in the same way as in (45))R(N n (ℓ)) ≥ R(m) + N n (ℓ)m t/rnη ′ ≥ R(m) + N n (⌊nt -nη⌋)m t/rnη ′ + (ℓ -⌊nt -nη⌋)t/r > ⌊nt -nη⌋ + (ℓ -⌊nt -nη⌋)t/r > ℓ,and thus, for ℓ ∈ [T ⌊nr+nε⌋+1,n , T n,n ], we also haveR(N n (ℓ)) = R(⌊nr + nε⌋) + R(N n (ℓ)) -R(⌊nr + nε⌋) = R(N n (T ⌊nr+nε⌋,n )) + R(N n (ℓ)) -R(N n (T ⌊nr+nε⌋,n )) ≥ R(N n (T ⌊nr+nε⌋,n )) + N n (ℓ) -N n (T ⌊nr+nε⌋,n ) > T ⌊nr+nε⌋,n + ℓ -T ⌊nr+nε⌋,n = ℓ.

  ln P A ′′′ |A ′ ∩ A ′′ ≥ 1 r-η ln(1u)du = δ ′′ (r, η),(75)where here and below δ ′′ (r, η) stands for a generic term such that δ ′′ (r, η) → 0 as (r, η) → (1, 0). Similarly, by (60),P B ′′′ |B ′ ∩ B ′′ ∩ C ≥ P{K ≥ 1} n-⌊n(r+ε)⌋ , so that lim inf n→∞ n -1 ln P B ′′′ |C ′ ∩ B ′ ∩ B ′′ ≥ (1r) ln P(K ≥ 1) = δ ′′′ (r),(76)with δ ′′′ (r) → 0 as r → 1. Therefore, from (74,75,76),lim inf n→∞ n -1 ln P N n (τ n ) = n ≥ lim inf n→∞ n -1 ln P(A ′ ∩ A ′′ ) + ln P(C ∩ B ′ ∩ B ′′ )+ δ ′′ (r, η) + δ ′′′ (r).

If t ≥ 1

 1 and t ∈ Dom(I), the above inequality still holds, by continuity as well, provided Dom • (I) ∩ (1, ∞) = ∅. If t ∈ Dom(I), the result obviously holds, so that, in the case when Dom• (I) ∩ (1, ∞) = ∅, lim inf n→∞ n -1 ln P N n (τ n ) = n ≥inf t≥1 F(1, t) = -G(1).

1 0

 1 i/n) -nrI[START_REF] Alves | Random walks systems on complete graphs[END_REF] .Letting r tend to 1, we deduce thatP N n (τ n ) = n ≥ exp -n-1 i=1 ln(1i/n) -nI(1) , so that lim inf n→∞ n -1 ln P N n (τ n ) = n ≥ln(1u)du -I(1) = -(1 + I(1)).

  r + nη/4; m ≤ ℓ ≤ nr + nε , since the upper condition in B can be reformulated as

R(nr

+ nε) -R(m) ≤ (nr + nεm)t/r + n(η/2tε/r) + mt/r,

and η/2tε/r ≥ η/4. By Mogulskii's Theorem, we get:


Xavier Sauvage
email: xavier.sauvage@univ-rouen.fr

Artur Ganeev

Yulia Ivanisenko

Nariman Enikeev

Maxim Murashkin

Ruslan Valiev

Grain boundary segregation in UFG alloys processed by severe plastic deformation

Keywords: Severe plastic deformation, Grain boundary, segregation, aluminum alloys, carbon steel

Grain boundary segregations were investigated by Atom Probe Tomography in an Al-Mg alloy, a carbon steel and Armco® Fe processed by severe plastic deformation (SPD). In the non-deformed state, the GBs of the aluminium alloy are Mg depleted, but after SPD some local enrichment up to 20 at.% was detected. In the Fe-based alloys, large carbon concentrations were also exhibited along GBs after SPD. These experimental observations are attributed to the specific structure of GBs often described as "non-equilibrum" in ultra fine grained materials processed by SPD. The grain boundary segregation mechanisms are discussed and compared in the case of substitutional (Mg in fcc Al) and interstitial (C in bcc Fe) solute atoms.

Introduction

Using severe plastic deformation (SPD) techniques, it has been shown that ultrafine grained (UFG) structure could be achieved in various metals and metallic alloys [1]. The grain size refinement mechanism during SPD is controlled by the generation of dislocations and dynamic recovery processes, i.e. the way dislocations do dynamically reorganize to form first low angle boundaries (dislocation cell walls) and finally, for larger strains, high angle boundaries [1]. These features may explain why a small change in the Mg concentration in aluminum can dramatically change the grain size achievable by SPD. Indeed, if the typical grain size achieved by High Pressure Torsion (HPT) in pure Al is about 800 nm [2], it drops down to only 150 nm in Al-3%Mg [3][4][5]. This trend has been confirmed by a large number of experimental investigations [6][7][8][9]. Beyond the strong interactions of Mg with dislocations, it is also well known that this element is prone to grain boundary (GB) segregation. Both experimental evidence [10,11] and simulation work [12][13][14] have demonstrated this tendency.

GB segregation is an extremely sensitive phenomenon because it may affect significantly the material properties like the corrosion resistance, the mechanical behavior or the thermal stability [START_REF] Lejcek | Grain boundary segregations in metals[END_REF][START_REF] Kirchheim | [END_REF][17]. In UFG materials the proportion of grain boundaries is much larger than in conventional coarse-grained alloys. Beside, GB boundaries achieved by SPD usually exhibit special features, like long range elastic stresses and enhanced free volume [1,19]. Thus they are sometimes called "non-equilibrium" GB and they do appear as ideal candidate for segregations that may minimize their local energy state [17,18]. There is some indirect evidence of grain boundary segregation in UFG materials processed by SPD. For example it has been demonstrated that the thermal stability of Ni [20] or Ag [21] is linked to the amount of impurities (supposed to segregate at GBs). A similar way, the UFG structure of Cu processed by SPD is more stable upon annealing if the material is alloyed with a small amount of Sb [22]. However, one should note that the role of solute elements on the thermal stability of nanocrystalline materials could be rather complex and not necessarily linked to segregations [23]. But using Atom Probe Tomography (APT) some direct proofs of GB segregation were obtained in various UFG alloys processed by SPD, like steels [24,25], Ti alloys [26], Ni [27] and Al alloys [28][29][30][31][32]. It is worth noticing that GB segregations might be a key issue for the application of UFG alloys, since it could significantly affect the properties [START_REF] Lejcek | Grain boundary segregations in metals[END_REF] like the strength [32][33][34][35] or the thermal stability [20][21][22].

In this paper, SPD induced GB segregation in UFG materials is discussed on the basis of new experimental data collected on two different systems, namely Al-Mg and Fe-C, where solute atoms are respectively located on substitution and interstitial sites in the matrix. These data were collected by APT to reveal local information about chemical gradients. For the Al-Mg system, some attempts were made to compare the distribution of Mg atoms in the annealed material (coarse grained) including along GBs, and in the UFG state (after SPD) were GBs are different and described as "non-equilibrum" [1,19]. For the Fe-C system, two different steels were investigated to find out if the amount of available solute element could significantly affect the segregation level at GBs.

Experimental

The Al-Mg alloy investigated in the present study is a hot-pressed commercial alloy containing 5.7% Mg, 0.32%Sc and 0.4%Mn (wt.%). Before grain refinement by SPD, the material was homogenized at 380°C during 2h (above the solubility limit of Mg in fcc Al), the grain size being larger than 10m. Discs (25 mm in diameter and 2mm in thickness) were processed High Pressure Torsion (HPT) at room temperature under a pressure of 6 GPa up to 20 revolutions. Two different Fe-based materials were also investigated. A commercial Armco ® iron with a very low level of impurity and a commercial C45 steel with a nominal carbon concentration of 0.45wt.%. Before grain refinement by SPD, the C45 steel was patented as following: homogenization treatment at 900°C during 1 hour and then transformed at 500°C to obtain a pseudo-pearlitic structure with nanoscaled Fe 3 C particles. Both Fe-based materials were processed by HPT at 350°C under a pressure of 6GPa, up to 5 revolutions (discs 10 mm in diameter and 0.3 mm in thickness).

APT samples were prepared by standard electropolishing techniques at a distance of 6mm (respectively 3mm) from the disc center for the Al-Mg alloy (respectively Fe-based materials).

Analyses were performed in UHV conditions, using an energy compensated atom probe equipped with an ADLD detector [36]. Two different configurations were used: a standard reflectron (small field of view) or a curved reflectron (large field of view). Samples were field evaporated using electric pulses (30kHz pulse repetition rate and 20% pulse fraction) at a temperature of 80K. Such conditions are known to provide quantitative measurements in Fe-C alloys (the carbon quantification was made following the procedure described in [24]) but not in Al-Mg. Indeed, at a temperature higher than 40K a significant amount of Mg might be evaporated between pulses (preferential evaporation) leading to non-quantitative measurements. However, SPD samples being extremely sensitive and prone to early specimen failure during analysis, it was impossible to analyze them at a temperature below 80K. Thus, a systematic correction was applied on the Mg content from a calibration measurement performed on a unique sample of the non deformed material (7.0 ±0.2 at.%Mg measured at 40K vs 4.4 ±0.2 at.% at 80K).

Results

Al-Mg alloy

Mg distribution before deformation

Most of APT data set collected for the non-deformed material (homogenized at 380°C during 2h) do exhibit a very homogeneous distribution of Mg in solid solution as expected. The average concentration measured is about 7.0 ±0.2 at.%, very close to the nominal composition.

However, as shown in Fig. 1 (a), a planar defect, depleted in Mg was also intercepted. No crystallographic information is available in this data set, but this feature is most probably a GB. A composition profile was computed across (Fig. 1 (b)), and considering the thickness of the sampling volume (1nm), it turns out that this GB is characterized by a 2nm thick layer depleted in Mg (sharp gradients and local concentration almost down to zero). Since the alloy does contain some Sc, it was not surprising to find some spherical Al 3 Sc nanoscaled particles (Fig. 1 (c)). Their size is in a range of 5 to 10nm and the amount of Sc remaining in solid solution in the aluminum matrix is below the detection limit of the instrument (i.e. below 50 ppm). One should note that the small black dots corresponding to Sc atoms in the reconstructed volume of Fig. 1 (c) are related to the detection noise in the mass range of Sc ions in the mass spectrum. The alloy also contains some Mn but this element was only detected in large Al-Mn intermetallic particles (data not shown here). Such a Mg depletion along GBs is not consistent with recent simulation work showing that a Mg rich layer should cover GBs in fcc Al [12][13][14]. It is however important to note that only very specific grain boundaries were simulated in these calculations. Beside, only one GB in the coarse grained state was successfully analyzed in the present study. Paine and co-authors [11] have performed a systematic study of GB segregation by STEM-EDX in a similar alloy (6.5 wt.%Mg) homogenized at 350°C during 30min. They measured that 8 out of 11 GBs were significantly depleted in Mg, thus it is reasonable to think that this only APT measurement is rather representative of the average GB state before SPD.

Mg distribution in the UFG structure resulting from SPD

As detailed in our previous work [9], after HPT at room temperature, the average grain size is about 130nm. There are still Al 3 Sc particles and TEM observations (not shown here) have revealed that they are often located along GBs, pinning them and probably limiting their mobility. Such particles were also detected by APT (Fig. 3 (a)), but the most interesting is the distribution of Mg atoms that now appears locally absolutely non uniform, confirming our preliminary observations [32]. In the data set displayed in Fig. 3; a GB boundary, pinned by an Al 3 Sc particle, was identified (arrowed). A profile computed across this boundary shows that there is a significant drop of the apparent local density in the 3D reconstructed volume across this boundary. This is a typical feature resulting from the misorientation of the two grains located on each side of the boundary. Indeed, the evaporation field may slightly change as a function of the crystallographic orientation, leading to some small change in the local magnification and thus in the local density. The local Mg enrichment is relatively weak along the boundary but strong Mg segregations clearly appear in the vicinity of this boundary. The small volume selected in this specific region (Fig. 3 (c)) clearly shows a kind of cell structure.

Cells seem almost completely depleted in Mg while their boundaries appear fully covered. A 2D Mg chemical map was computed to image the concentration gradients in this area (Fig. 3 (d)). It clearly reveals that along the cell boundaries the average concentration is about 10at.%Mg, with maxima as high as 20at.%. Other volumes with a more uniform distribution of Mg were also analyzed (not shown here). The average composition is lower than in the non-deformed state (6.4±0.5 vs 7.0±0.2 at.%) and is consistent with Mg segregations along GBs or in their vicinity.

Such large local fluctuations of the Mg content could also be attributed to some Al-Mg intermetallic precipitates even if the local concentration never reaches the 40at.% Mg required for the nucleation along GB of the equilibrium Al 3 Mg 2 phase [37]. Indeed, in the Al-Mg system, the nucleation of GP zones or metastable phases with a L1 0 or L1 2 structure and a Mg concentration of 25at.% (i.e. close to the local concentrations measured in the present investigations) have been reported in the literature [38][39][40][41]. Beside, one should note that the dynamic precipitation of GP zones during plastic deformation of an Al-Cu alloys was recently observed [41], and the nucleation of metastable precipitates in an Al-Mg-Si-Cu alloy processed by ECAP at 200°C was also reported [29]. However, it was shown that metastable intermetallic phases and GP zones in the Al-Mg system are unstable at room temperature or higher if the Mg content of the alloy is below 9at.% [38][39][40][41], like in the present material.

Moreover, second phase particles and precipitates are known to dissolve during SPD at room temperature (sheared by dislocations) [42,43]. Thus, the high concentration of Mg locally measured by APT can reasonably be attributed without ambiguity to segregations along crystalline defects.

The SPD induced GB segregation of Mg in a similar alloy was already reported in a previous work [32], but here new data showing a more complex situation are provided. A GB pinned by an Al 3 Sc particle was intercepted but most of the segregated Mg is located in a complex network in the vicinity of the boundary (Fig. 2). Moreover, the analysis of a Mg depleted grain boundary in the annealed material (Fig. 1) unambiguously prove that such features are typical of UFG structures resulting from the SPD process. Thus, it seems that there is no systematic Mg enrichment of GBs during SPD, but a systematic flow of Mg toward the GBs induced by the plastic deformation. Beside, the more or less complex distribution of Mg in the GB area might be related to local distortions, i.e. to the non equilibrium state of the specific boundaries created during HPT [1,19].

Fe-based materials

Carbon distribution in the UFG C45 steel processed by HPT

Before HPT, as a result of the patenting treatment, carbon atoms are well partitioned in the C45 steel, most of them being in Fe 3 C carbides while a very small amount, typically less than 0.1%, is in solid solution in the bcc ferrite matrix. After HPT at 350°C, ultrafine grains are elongated with an aspect ratio of about 3 (mean length 250 nm and width 70 nm, estimated from TEM data that are not shown here). Beside, as shown in the 3D reconstructed volume displayed on the Fig. 3 (a), the carbon distribution has changed. Both nanoscaled and elongated carbides (about 20 nm in length) are clearly exhibited together with some diffuse segregations along some boundaries. A composition profile computed across the carbide/matrix interface (Fig. 3 (b)) clearly indicates that these carbides are partly dissolved as reported in some earlier work [24,25]. Indeed, the carbon concentration is well below 25 at.% as expected for stoichiometric cementite (Fe 3 C carbide), it is only in a range of 15 to 20 at.%. Following this partial decomposition, carbon atoms released in the matrix do segregate along defects like boundaries where the local concentration is up to 2 at.% (see the concentration profile Fig. 3 (c)). These observations are fully consistent with our previous studies about the contribution of such GB segregation on the grain size refinement mechanism in a high carbon steel processed by SPD [24]. Beside, we show as well that these segregations could be directly connected to some carbides. It seems indeed that some of them pin the new boundaries created during SPD and then directly "feed" them with solute elements. The interfacial excess of carbon at the boundary was estimated from the APT data and is in a range of 3 to 5 at/nm 2 . The segregation of carbon along defects like dislocations or GBs in steel is a well known feature. Takahashi and co-authors have very recently investigated such interfacial excess of carbon as a function of the GB misorientation angle [44], showing that larger misorientation leads to higher level of segregation. The value measured in the present study is consistent with data reported for a GB misorientation angle of about 30°.

Carbon distribution in the UFG Armco ® iron processed by HPT

The Armco® iron does contain a very low amount of impurity. APT analyses, performed on five samples, providing each of them several millions of atoms, have shown that the following elements could be detected in solid solution: Al (50 to 100 ppm), P (50 to 100 ppm), C (100 to 200 ppm) and N (500 to 800 ppm). After HPT at 350°C, the grain size is in a range of 200 to 250 nm (estimated from TEM data not shown here), and as shown on Fig. 4 (a), carbon atoms are not homogeneously distributed. Some segregations along planar defects are indeed clearly revealed in the 3D reconstructed volume. On this image, for a better visualization of the segregation along a boundary, carbon atoms were artificially represented with dots much bigger than Fe atoms. The composition profile computed across the boundary (direction indicated by the arrow), shows that the local carbon concentration is up to about 0.5 at.% in a thin layer spreading on each side of the boundary over a distance of about 2nm. Thus, some SPD induced segregations occurred during the HPT process even if the amount of C is close to the solubility limit in bcc iron at 350°C [45]. One should note that no significant concomitant segregation of N was detected, in agreement with other published data [44].

The interfacial excess of carbon at the boundary estimated from the APT is in a range of 0.3 to 0.5 at/nm 2 . This is much lower than in the C45 steel processed by HPT in similar conditions, and this is obviously attributed to the lower amount of carbon available. This interfacial excess is also four times lower than the data reported for a steel containing only 15 at. ppm of carbon (i.e. one order of magnitude lower than the present material) [44]. However, in the present case, the grain size is much smaller (0.2 m vs 20m) and it can easily be estimated that one third of carbon atoms are segregated along GBs while it was only one out of seven in the annealed and fully recrystallized steel investigated by Takahashi and coauthors. Thus, the carbon segregation along GBs is clearly promoted by the severe plastic deformation.

Discussion about the SPD induced GB segregation

The mechanisms of plastic deformation in UFG materials are not controlled by dislocation storage inside grains that are often almost completely free of internal substructures. Most of dislocations are indeed emitted from GBs, and then immediately propagate through the grain's interior up to opposite GBs where they are absorbed and dynamically recover. Thus, there is a constant flow of dislocations toward GBs. Beside, it was demonstrated also that a large density of point defects and especially vacancies are created [46][47][48][49][50][51][52]. Like in irradiated materials, GBs are sinks for these vacancies (some might also be annihilated along dislocations), which leads also to a constant vacancy flux toward them. Beside, it has been demonstrated that Mg atoms in solid solution in fcc Al are strongly coupled to vacancies, with a positive binding energy in a range of 0.2 to 0.4 eV [53][54][55]. Thus, the atomic scale mechanism of the SPD induced segregation observed in the present study, is probably very similar to that of non-equilibrium segregation resulting from irradiation [START_REF] Lejcek | Grain boundary segregations in metals[END_REF]56]. Mg being strongly coupled to vacancies, the flux of these point defects toward GBs drags Mg atoms during the plastic deformation, leading to strong local enrichments. At room temperature, dynamic recovery processes of dislocations are limited, leading to the formation of the socalled "non equilibrium grain boundaries" with large local distortions (due to extrinsic dislocations) [1,19]. Mg atoms being larger than Al, some elastic strain could be relaxed by Mg clusters giving rise to local compressive stresses. Thus it is reasonable to think that Mg segregation may stabilize GBs by reducing their energy [START_REF] Kirchheim | [END_REF]17]. In the present work, large local enrichment in Mg was also observed in a network in the vicinity of a boundary. One should note that in aged dilute Al-Mg alloys, it was demonstrated that Mg atoms easily segregate along dislocation loops [53]. Similar features have been reported in irradiated materials where the typical loop size resulting from the agglomeration of point defects is in a range of 10 to 20 nm [56]. It is interesting to note that this value is close to the length scale of the network imaged in Fig. 3. However, one cannot exclude that the Mg mobility could also be enhanced by dislocations. Pipe diffusion mechanism along dislocation cores [57] may operate but also solute drag [58]. Indeed, moving dislocations are absorbed at GB during SPD, which leads to a constant dislocation flow toward the boundary. Due to the enhanced atomic mobility of Mg promoted by SPD induced vacancies, these dislocations could drag a significant amount of Mg even at room temperature. Beside, unusually fast diffusion of Mg was observed in a UFG Al-Mg alloy [59] and more generally fast diffusion paths have recently been reported in SPD materials [60].

Carbon atoms in solid solution in the bcc Fe are located on interstitial sites, while Mg atoms in the fcc Al are on substitutional sites, leading to different diffusion mechanisms. However, carbon atoms are also known to strongly interact with dislocations leading to strong segregations [42,61,62], and also to be strongly bonded to vacancies forming the so called C-V complexes [63,64]. Thus, the segregation kinetic of this interstitial element (i.e. the flow of C atoms towards the grain boundaries during SPD), is also most probably related to the annihilation of vacancies and dislocations in the vicinity of GBs.

Conclusions

i) The results of this work demonstrate that SPD induced grain refinement in metallic alloys may also leads to the active formation of GB segregations of solute elements or impurities.

These segregations may exhibit specific morphologies and unusually high local concentrations that were not observed before in metallic materials subjected to lower levels of plastic deformation and/or conventional thermal treatments.

ii) The formation of such segregations in SPD materials is attributed to the generation of "non-equilibrium" grain boundaries, which contain excessive density of extrinsic dislocations and thus additional local lattice strains and enhanced free volumes.

iii) There are experimental evidences that such SPD induced GB segregations may improve the material's properties. Therefore, it is believed that there is an opportunity to control such GB local features and thus to tune some properties of UFG alloys via SPD processing parameters.

Figure captions

Figure 1

 1 Figure 1 APT data collected for the Al-Mg alloy before HPT processing. (a) 3D reconstructed volume showing a thin Mg depleted layer attributed to a GB (only Mg atoms are displayed for more clarity) ; (b) Concentration profile computed across the Mg depleted layer (sampling volume thickness 1nm) ; (c) 3D reconstructed volume showing the homogeneous distribution of Mg in the grain interior and a Sc rich nanoscaled particle.

Figure 2 Figure 3

 23 Figure 2 APT data collected for the Al-Mg alloy processed by HPT. (a) 3D reconstructed volume showing the heterogeneous distribution of Mg in the vicinity of a GB pinned by an Al 3 Sc particle; (b) Mg concentration profile and evolution of the apparent density across the GB (thickness of the sampling volume 1nm); (c) small selection showing in a more appropriate orientation the heterogeneous distribution of Mg in the vicinity of the GB; (d) 2D Mg concentration map corresponding to the small selection and showing that the local Mg concentration is up to 20at.%

Figure 4

 4 Figure 4 APT data collected on the Armco iron processed by HPT. (a) 3D reconstructed volume showing the heterogeneous distribution of carbon atoms (red dots), some segregations along boundaries are clearly exhibited. (b) Carbon concentration profile across a segregation along a boundary (see arrow on image (a)) showing that the local concentration is up to about 0.5at.% (sampling volume thickness 1nm)

Figure 4

 4 Figure 4

Acknowledgements

One of the authors, Yu Ivanisenko, is thankful to DFG for funding support of a part of this investigation. The authors (A.Ganeev, R.Valiev and M. Murashkin ) are thankful to RFBR -11-08-91330 for partial support of the investigation.