Olivier Garet

A CENTRAL LIMIT THEOREM FOR THE NUMBER OF DESCENTS AND SOME URN MODELS

Keywords: 2000 Mathematics Subject Classification. 60F05, 60C05 Central Limit Theorem, urn models. 1

A central limit theorem for the number of descents and some urn models

The purpose of this work is to establish a Central Limit Theorem that can be applied to a particular form of Markov chains, a form that is encountered in various problems of a combinatorial nature. This class is large enough to cover a number of classical results, such as the Central Limit Theorem for the number of descents in a random permutation of S n , two-type generalized Pólya urns, as well as some other urn models.

We can immediately state the theorem:

Theorem 0.1. Let (a n ) n≥1 be a sequence of integrable random variables. We note, for n ≥ 1, S n = a 1 + • • • + a n . We suppose that there exists some constant M and, for k ∈ {1, 2, 3}, non-random sequences (α n k ) n≥1 , (D n k ) n≥1 and real numbers α 1 , α 2 , α 3 , D 1 , D 2 , D 3 such that

• ∀n ≥ 1 |a n | ≤ M . • ∀n ≥ 1 ∀k ∈ {1, 2, 3} E[a k n+1 |a 1 , . . . , a n ] = D n k - α n k n S n , with lim n→+∞ α n k = α k and lim n→+∞ D n k = D k . • α n 1 = α 1 + o 1 √ n and D n 1 = D 1 + o 1 √ n .
We also compute = D 1 α 1 +1 and D = D 2 -( + α 2 ). If it is then verified that α 1 > - 1 2 and D > 0, then Sn-n √ n converges in distribution to N (0, S) with S = D 2α 1 +1 .

The article is organized as follows: in a first part, as an appetizer, we recall the definitions, the Central Limit Theorem on the number of descents and we see how to deduce it from our general theorem. The second part is devoted to the proof of the theorem, while the last two parts give applications to urn models, including the Pólya urn model, but not limited to it.

The number of descents

When σ is a permutation of the set {1, . . . , n}, the descents of σ are the points Desc(σ) = {i ∈ {1, . . . , n -1}; σ(i) > σ(i + 1)}.

Similarly, the ascents are defined by

Asc(σ) = {i ∈ {1, . . . , n -1}; σ(i) < σ(i + 1)}.
It is well known that the number of descents (or the number of ascents) of a uniformly chosen random permutation has an asymptotic normal behaviour: if σ n is chosen uniformly among the permutations on {1, . . . , n}, we have

|Desc(σ n )| -n/2 √ n =⇒ N 0, 1 12 .
In a recent article [START_REF] Chatterjee | A central limit theorem for a new statistic on permutations[END_REF], Chatterjee and Diaconis counted no less than 6 proofs. Thus, we venture here to present a seventh -and perhaps even an eighth, if we count as such the transcription of the question into an urn problem, which can be studied using this article or the literature. Note also the recent proof by Özdemir using martingales [START_REF] Alperen | Martingales and descent statistics[END_REF]. Our proof of Theorem 0.1 is based on conditional expectation together with the method of moments. Among the six proofs for the CLT on the number of descents evoked by Chatterjee and Diaconis, the proof by David and Barton [START_REF] David | Combinatorial chance[END_REF] (Chapter 10) also relies on the method of moments, however they use the generating functions whereas our approach is more related to conditioning. An easy way to perform the uniform distribution on the permutations in {1, . . . , n} is to apply the insertion algorithm: take σ 1 as the identity on {1}, then σ n+1 = σ n • (n + 1 U n+1 ), where (U n ) is a sequence of independent random variables such that for each n, U n follows the uniform distribution on {1, . . . , n}. Then, for each n, σ n follows the uniform distribution on S n .

Let D n = |Desc(σ n )|. We have, for n ≥ 1:

D n+1 = D n + 1 E n+1 , with E n+1 = {U n+1 -1 ∈ Asc(σ n ) ∪ {0}}.
Let also

F n = σ(U 1 , . . . , U n ), then P(E n+1 |F n ) = |Asc(σ n )| + 1 n + 1 = (n -1 -D n ) + 1 n + 1 = n -D n n + 1 (1) Let S n = D n -n-1
2 . Let us define S 1 = 0, a 1 = S 1 , and for n ≥ 1:

a n+1 = S n+1 -S n = (D n+1 -D n ) - 1 2 = 1 E n+1 - 1 2 , then S n = a 1 + • • • + a n . The random variable a n is {-1/2, 1/2} valued.
Finally,

E(a n+1 |F n ) = P(E n+1 |F n ) - 1 2 = n-1 2 -D n n + 1 = - S n n + 1 . ( 2
)
Theorem 0.1 applies particularly easily: we have F n = σ(a 1 , . . . , a n ), (a n ) is uniformly bounded by 1/2, Equation (2) gives the second assumption for k = 1, k = 2 and k = 3 easily follow because the sequence (a 2 n ) is constant equal to 1/4: we can apply the theorem with M = 1/2, D 1 = 0, D 2 = 1/4, D 3 = 0 and α 1 = 1, α 2 = 0, α 3 = 1/4, which gives the announced result.

Proof of the Theorem

We already note F n = σ(a 1 , . . . , a n ). Let's start with the study of the first moment.

E(S n+1 ) = E(S n ) + E(a n+1 ) = E(S n ) + D n 1 - α n 1 n E(S n ) = (1 - α n 1 n )E(S n ) + D n 1 = (1 - α 1 n )E(S n ) + D 1 + o 1 √ n since |E(S n )| ≤ nM
To solve the recurrence, we rely on two analytic lemmas:

Lemma 2.1. Let C, k, α, β ∈ R with α -1 < β ≤ α, β + k > -1 and (u n ) n≥n 0 , sequences such that u n+1 = (1 - k n + c )u n + Cn α + o(n β ),
Proof. Note that

1 - k n + c = n + c -k n + c = Γ(n + c -k + 1) Γ(n + c -k) Γ(n + c) Γ(n + c + 1) = P k,c (n) P k,c (n + 1)
,

with P k,c (x) = Γ(x+c) Γ(x+c-k)
. By the Stirling formula, P k,c (x) = x k (1 + O(1/x)) at infinity, the recurrence equation is then rewritten

P k,c (n + 1)u n+1 = P k,c (n)u n + CP k,c (n + 1)n α + o(n β+k ) = P k,c (n)u n + Cn α+k + o(n β+k ),
and then, with the telescopic sum,

u n P k,c (n) = C n α+k+1 α+k+1 + o(n β+k+1
), and finally

u n = C α + k + 1 n α+1 + o(n β+1 ). Lemma 2.2. Let C, k, α ∈ R with C > 0, α + k > -1 and (u n ) n≥n 0 , (k n ) n≥n 0 sequences such that u n+1 = (1 - k n n + c )u n + Cn α + o(n β ), with lim k n = k.
We suppose moreover that ∀n ≥ n 0 u n ≥ 0. Then,

u n = C α + k + 1 n α+1 + o(n α+1 ).
Proof. One can find n 0 such that n + c > 0, v n > 0, and 1 -kn n+c > 0 for n ≥ n 0 , then for ε > 0 small enough, take

n 1 ≥ n 0 such that 1 -k-ε n+c > 1 -kn n+c > 1 -k+ε n+c > 0 for n ≥ n 1 . Let w n 1 = x n 1 = u n 1 , then for n ≥ n 1 , w n+1 = w n 1 - k + ε n + c + v n and x n+1 = x n 1 - k -ε n + c + v n .
By natural induction,

x n ≥ u n ≥ w n ≥ 0 for each n ≥ n 1 , then lim n→+∞ u n n -(α+1) ≥ lim n→+∞ w n n -(α+1) = C α + k + ε + 1 ,
where the last equality follows from Lemma 2.1. Letting ε tend to 0, we get

lim n→+∞ u n n -(α+1) ≥ C α+k+1 . Similarly lim n→+∞ u n n -(α+1) ≤ lim n→+∞ x n n -(α+1) = C α + k -ε + 1 ,
and, letting ε tend to 0, lim

n→+∞ u n n -(α+1) ≤ C α+k+1 , which completes the proof. Applying Lemma 2.1 to the sequence (E(S n )) n≥1 , we get E(S n ) = n + o( √ n), with = D 1 α 1 +1
. By the Slutsky Lemma, it is now sufficient to prove that Sn-E(Sn) √ n =⇒ N (0, D/(2α 1 + 1)).

We will first reduce to the case where

D n 1 = 0 for all n. Let n = E(a n ) and a n = a n -n . Since E[a n+1 |a 1 , . . . , a n ] = D n 1 - α n 1 n S n , we have n = D n 1 - α n 1 n E(S n ), so n → D 1 -α 1 = (α 1 + 1) -α 1 = .
It is clear that (a n ) checks the same sort of assumptions as (a n ), only the limit values are changed. If we put

f k,n (x) = D n k - α n k n x, we have E(a n+1 |F n ) = f 1,n (S n ), then n+1 = f 1,n (E(S n )), and
E(a n+1 |F n ) = f 1,n (S n ) -f 1,n (E(S n )) = - α n 1 n (S n -E(S n ))
which gives the constants associated to a n : α 1 = α 1 and D n 1 = 0 for all n. We also have

E(a 2 n+1 |F n ) = E(a 2 n+1 + 2 n -2 n a n+1 |F n ) = f 2,n (S n ) + 2 n -2 n f 1,n (S n ) = f 2,n (S n ) -α n 2 1 + • • • + n n + 2 n -2 n f 1,n (S n ) + 2α n 1 n 1 + • • • + n n = f 2,n (S n ), with f 2,n (x) = f 2,n (x) -α n 2 1 +•••+ n n + 2 n -2 n f 1,n (x) + 2α n 1 n 1 +•••+ n n
, which leads to

D 2 = lim f 2,n (0) = D 2 -α 2 + 2 -2 D 1 + 2α 1 2 = D 2 -(α 2 -+ 2D 1 -2α 1 ) = D 2 -(α 2 + -2(D 1 -(1 + α 1 ))) = D 2 -( + α 2 )
The same kind of calculation applies for k = 3, it is not detailed because the explicit values of the corresponding constants are not necessary.

Then, we can assume without loss of generality that D n 1 = 0 and E(S n ) = 0 for all n. We will now estimate by recurrence the sequences of the different moments, for the orders greater than one.

For each non-negative integer k, there exist polynomials R k and

T k such that R k (x, y) = k(k-1)(k-2) 6 x k-3 y 3 + T k (x, y) (x + y) k = x k + kx k-1 y + k(k -1) 2 x k-2 y 2 + R k (x, y), with ∀x ∈ R ∀y ∈ [-M, M ] |R k (x, y)| ≤ (M + 1) k (1 ∨ |x| k-3 ) ∀x ∈ R ∀y ∈ [-M, M ] |T k (x, y)| ≤ (M + 1) k (1 ∨ |x| k-4 ) Particularly, we get S k n+1 = S k n + kS k-1 n a n+1 + k(k -1) 2 S k-2 n a 2 n+1 + R k (S n , a n+1 ).
Conditioning by F n , then reintegrating, we have

E(S k n+1 ) =(1 - kα n 1 n )E(S k n ) + D n 2 k(k -1) 2 E(S k-2 n ) + (kD n 1 - k(k -1) 2 α n 2 n )E(S k-1 n ) + E(R k (S n , a n+1 )) so, since D n 1 = 0, we have E(S k n+1 ) = (1 - kα n 1 n )E(S k n ) + D n 2 k(k -1) 2 E(S k-2 n ) + E(R k (S n , a n+1 )) + O( 1 n E(S k-1 n )). (3)
For k = 2, we have R 2 = 0 and E(S n ) = 0, which simply gives

E(S 2 n+1 ) = (1 - 2α n 1 n )E(S 2 n ) + D n 2 .
With Lemma 2.2, we get

E(S 2 n ) = D n + o(n), where D = D 2α 1 + 1 .
Let's move on to the general case. With the help of the recursion (3), we will prove that for each k ∈ N, we have

E(S k n ) = C k n k/2 + o(n k/2 ), (4)
where (C k ) k≥0 is the sequence defined by C 0 = 1, C 1 = 0 and C k = D C k-2 (k -1): since D > 0, this is the sequence for the moments of N (0, D ). We note that terms with even index are positive. This will be useful to apply Lemma 2.2.

The proof is by induction on k. The asymptotic expansion is proved for k = 0, 1, 2. Assuming (4) holds for {0, 1 . . . , k -1} and let us prove for k. We invoke the inductive assumption for k -2 and k -1; it comes

E(S k n+1 ) = (1 - kα n 1 n )E(S k n ) + C k-2 D 2 k(k -1) 2 n k/2-1 (5) + E(R k (S n , a n+1 )) + o(n k/2-1 ). If k is odd, then |E(R k (S n , a n+1 ))| ≤ (M + 1) k (1 + E(S k-3 n )) = O(n k-3 2 ). If k is even, then |E(T k (S n , a n+1 ))| ≤ (M + 1) k (1 + E(S k-4 n )) = O(n k-4 2 ), (6)
whereas

E(S k-3 n a 3 n+1 ) = E(S k-3 n (D n 3 - α n 3 S n n )) = O(n k- 3
2 ),

which gives E(R k (S n , a n+1 )) = O(n k- 3
2 ). In any case, we have thus

E(S k n+1 ) = (1 - kα n 1 n )E(S k n ) + C k-2 D 2 k(k -1) 2 n k/2-1 + o(n k/2-1 ). (7) If k is odd, we have |E(S k n )| ≤ E(S k-1 n |S n |) ≤ M nE(S k-1 n ) = O(n 1+(k-1)/2 ), so E(S k n+1 ) = (1 - kα 1 n )E(S k n ) + C k-2 D 2 k(k -1) 2 n k/2-1 + o(n k/2-1 ), (8)
and we apply Lemma 2.1. Otherwise, the sequence E(S k n ) is non-negative and we apply Lemma 2.2.

In both cases, it comes that

E(S k n ) = 2 (1 + 2α 1 )k D 2 C k-2 k(k -1) 2 n k/2 + o(n k/2 ) = C k n k/2-1 + o(n k/2-1 ),
which completes the inductive step. We have proved that for each k ≥ 0, we have

lim n→+∞ E(( S n √ n ) k ) = E(X k ),
where X ∼ N (0, D ). By the method of moments, we conclude that S n √ n =⇒ N (0, D ).

Pólya's urn with random coefficients

There is a wealth of literature on Pólya's urns and their various extensions. For the properties we will find here, the most natural references are Freedman [START_REF] Freedman | Bernard Friedman's urn[END_REF], Bagchi and Pal [START_REF] Bagchi | Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures[END_REF], Smythe [START_REF] Smythe | Central limit theorems for urn models[END_REF], and Janson [START_REF] Janson | Functional limit theorems for multitype branching processes and generalized Pólya urns[END_REF]. We work here with ballot boxes with two types of balls. The model considered is a balanced model, i.e. at each step, the number of balls in the urn increases by N , where N is a natural non-zero fixed integer.

Let's describe the dynamics: the urn initially contains a 0 white balls and b 0 black balls. The composition of the urn varies over time as follows: at time n, a ball is shot into the urn, if it is white, it is put back into the urn as well as B 1 n white and N -B 1 n black, where, conditionally to the above, B 1 n follows the law µ 1 . If it is black, it is put back in the box along with B 2 n white and N -B 2 n black, where, conditionally to the above, B 2 n follows the law µ 2 . We only impose -1 ≤ B 1 n ≤ N and -1 ≤ N -B 2 n ≤ N : it is therefore possible to remove a ball, but only if it has been fired.

At time n, the urn therefore contains a 0 + b 0 + nN balls. The number of white balls in the urn at the time n is a 0 +

• • • + a n , with L(a n+1 |a 0 , . . . , a n ) = a 0 + S n a 0 + b 0 + nN µ 1 + b 0 + (nN -S n ) a 0 + b 0 + nN µ 2 .
Noting m i,k = R x k dµ i , we have then

E(a k n+1 |a 0 , . . . , a n ) = a 0 + S n a 0 + b 0 + nN m 1,k + b 0 + (nN -S n ) a 0 + b 0 + nN m 2,k .
Assumptions about the form of conditional expectations are easily verified, with

D k = m 2,k and α k = m 2,k -m 1,k N
. The first condition of validity of the Central Limit Theorem is given by

α 1 > -1 2 , or ρ = m 1,1 -m 2,1 N < 1 2 .
In the classic formalism of Pólya's ballot boxes, the mean replacement matrix is

m 1,1 N -m 1,1 m 2,1 N -m 2,1 ,
whose eigenvalues are N and m 1,1 -m 2,1 . The condition ρ < 1 2 thus found is indeed the classic condition on the eigenvalue quotient, which is classically denoted as the "small urns" case. The second condition D > 0 requires a little more calculations. Letting

r i = m i,1 N and v i = Var B i 1 N = m 2 i,2 N 2 -r 2 i , we find D 2α 1 +1 = N 2 (R+S) (2α 1 +1)(α 1 +1) 2 with R = r 2 α 2 1 (1 -r 1 ) and S = (α 1 + 1)(v 2 (1 -r 1 ) + v 1 r 2 )
. Since r 2 ≥ 0 and r 1 ≤ 1, R and S are non-negative. It is then easy to see that only a few degenerate cases lead to D = 0: the cases µ 1 = δ N and µ 2 = δ 0 , as well as the case where there is k such as µ 1 = µ 2 = δ k . Thus, in the two-ball model, we recovers Smythe's CLT [START_REF] Smythe | Central limit theorems for urn models[END_REF] on "small urns". It is interesting to note that we have an explicit form for the covariance of the normal limit distribution.

3.1.

Example: a removed ball and added balls. In this example, at each step, one ball is removed from the urn, then black and white balls are added, b in total (with b ≥ 2), the number of white balls following a distribution µ on {0, . . . , b}, with µ ∈ {δ 0 , δ b }. With the above notations, we have N = b -1, µ 1 = µ * δ -1 and µ 2 = µ. If we denote by m the expectation of µ and by σ 2 its variance, we have then

m 1,1 = m -1, m 1,2 = σ 2 + (m -1) 2 , m 2,1 = m, m 2,2 = σ 2 + m 2 . α 1 = m 1,1 -m 2,1 N = 1 b-1 and α 2 = m 2,2 -m 1,2 N = 2m-1 b-1 The quotient ρ = m 1,1 -m 2,1 N = -1 b-1 checks ρ < 1 2 . We have D 1 = m 2,1 = m, hence = D 1 1 + α 1 = D 1 1 -ρ = m 1 + 1 b-1 = m(b -1) b , D 2 = m 2,2 = σ 2 + m 2 .
We finally have

D = D 2 -( + α 2 ) = σ 2 + m b (1 - m b ).
So if B n denotes the number of white balls at time n

B n -m(b-1) b n √ n =⇒ N 0, b -1 b + 1 (σ 2 + m b (1 - m b
)) .

3.2.

Example: Bernard Friedman urn. In this example, we add α balls of the drawn color and β balls of the other color. We have thus N = α + β, µ 1 = δ α and µ 2 = δ β , which gives us

D 1 = m 2,1 = β, D 2 = m 2,2 = β 2 , α 1 = m 2,1 -m 1,1 N = β-α β+α and α 2 = m 2,2 -m 2,1 N = β 2 -α 2 β+α = β -α. So = D 1 α 1 +1 = β 2β α+β = α+β 2 , D = D 2 -( + α 2 ) = β 2 -α+β 2 3β-α 2 = (α-β) 2 4 . So if 3β > α
and S n is the number of white balls in the urn after n steps, we have

S n -α+β 2 n √ n =⇒ N 0, (α -β) 2 (α + β) 4(3β -α) .
In particular, if we add only one ball of the other color, we have α = 0 and β = 1 and

S n -n 2 √ n =⇒ N 0, 1 12 .

3.3.

Returning to the dynamics of descents. The coincidence of this last equation with the CLT for downhill runs may lead to a new look to Equation (1), which can be rewritten as

L(1 E n+1 |F n ) = 1 + D n 1 + n δ 0 + n -D n 1 + n δ 1 .
We can then see that the dynamics of variation of the descents is exactly the dynamics of the variation of the number of white balls in a Bernard Friedman urn starting from a white ball, and where we add to each step a ball of a different color from the one drawn. One can e.g. imagine that there is time n D n + 1 white balls and n -D n black balls in the urn. It is then obvious that the Central Limit Theorems obtained correspond. This is the eighth proof that was announced. Although it is easy, this identification of the process of the number of descents with a Bernard Friedman urn seems new to us. We can extend the analogy even further. After one step, our Bernard Friedman urn necessarily contains a white ball and a black ball: this is the initial state of the urn considered by Diaconis and Fulton [START_REF] Diaconis | A growth model, a game, an algebra, Lagrange inversion, and characteristic classes[END_REF] to study the number N n of strictly negative points visited by the Internal Diffusion-Limited Aggregation model on Z after he has received n points. Remember that the Internal Diffusion-Limited Aggregation model is defined as follows: start at time 1 with with one point at the origin and say it forms the first block. Then, at each turn of the clock, start a walker from the origin and stop it as soon as it leaves the block, then enlarge the block by adding the stopped walker to it. At times n, the block is {-N n , . . . , -N n + (n -1)}, where N n denotes the number of points in the negative part. The gambler's ruin theory says that one will exit from the left with probability -Nn+(n-1)+1 (-Nn+(n-1)+1)+(Nn+1) = n-Nn n+1 . So, we get

L(N n+1 -N n |N 1 , . . . , N n ) = 1 + D n 1 + n δ 0 + n -D n 1 + n δ 1
and the processes (N n ) n≥1 and (D n ) n≥1 have the same distribution.

Balls on a circle

We conclude with an example that does not allow itself to be reduced to a Pólya urn. In this model, b 0 black balls and w 0 white balls are initially placed in a circle, with 1 ≤ w 0 < b 0 . The balls are arranged along the circle to respect a placement rule which is described as follows:

First, white and black balls are placed alternately. At a given moment, when there are only black balls to be placed, they placed next to each other (see Figure 1).

Then, 3 neighbouring balls are randomly drawn and removed; then a white balls and b black balls are inserted, in order to respect the placement rule.

To ensure that the rule can always be met, assumptions must be made about a and b. The assumptions a ≥ 1 and a+b ≥ 4 are natural so that there is always at least one white ball in the circle and the number of balls grows. We also need to add assumptions so that the blacks always stay ahead. We can consider alternatively However, the existence of this group of three balls means that Black's lead is at least 2; but the dynamics equations mean that the number of balls is always an odd number, so Black's lead is at least 3; losing two units means Black's lead is at least one. Conditional expectations are indeed of the required form.

In particular D 1 = a, D 2 = a 2 , α 1 = 3 a+b-3 , α 2 = 6a-5 a+b-3 . It is obvious that α 1 > - 1 2 , but the fact that D > 0 needs more care.

( 1 )

 1 b -a ≥ 3. (2) b -a = 1 and w 0 + b 0 is odd. At the n th step, the urn contains (a + b -3)n + w 0 + b 0 balls, including S n white. Let's clarify the equations of the dynamics. The three balls that are removed can be spotted by the central ball. There are 4 possible configurations for this group of balls: • a white ball surrounded by two black balls. This happens S n times, the gain for the whites is a -1; The advance of the blacks increases by (b -a) -1 ≥ 0. • a black ball surrounded by two white. This happens S n -1 times, the gain for the whites is a -2; the advance of the blacks increases by (b -a) + 1 ≥ 2. • two adjacent black balls and one white ball. It happens 2 times if the black balls represent strictly more than half of the balls, which, as we will see, is ensured by the assumption that we have taken, the gain for the whites is a -1; the advance of the blacks increases by (b -a) -1 ≥ 0. • three black balls otherwise,the gain for the whites is a. The advance of the blacks increases by (b-a)-3. Under Hypothesis (1), (b-a) ≥ 3, so the blacks are still ahead. Under Hypothesis (2), b -a = 1, so the advance is reduced by two units.

- 1 + 1 -

 11 If we write a n+1 = S n+1 -S n , we haveL(a n+1 |a 1 , . . . , a n ) = S n -1 (a + b -3)n + w 0 + b 0 δ a-2 + S n + 2 (a + b -3)n + w 0 + b 0 δ a2S n + 1 (a + b -3)n + w 0 + b 0 δ a (9)Thus for any positive integer k, we haveE(a k n+1 |a 1 , . . . , a n ) = (a -2) k (S n -1) (a + b -3)n + w 0 + b 0 + (a -1) k (S n + 2) (a + b -3)n + w 0 + b 0 + a k -(2S n + 1)a k (a + b -3)n + w 0 + b 0 = (a -2) k + (a -1) k -2a k (a + b -3)n + w 0 + b 0 S n + a k + -(a -2) k + 2(a -1) k -1 (a + b -3)n + w 0 + b 0 .

Figure 1 . 1 =D = D 2 -

 112 Figure 1. The dynamics, in a configuration with 2 white and 7 black balls. The transition rule is given by a = 2 and b = 5.

For example, with w 0 = a = 2, b 0 = b = 3, we have

When a + b ≥ 4, with b = a + 2 or (b = a + 1 and w 0 + b 0 is even), the white never dominates, but equality of the two colors is possible (which is why (9) fails). Simulations seem to show that eventually, blacks definitely prevail with Sn n(a+b-3) → a a+b < 1 2 and that the stated Central Limit Theorem is always valid.

When the Central Limit Theorem is established, the convergence in probability of Sn n(a+b-3) to a a+b follows. The question of almost sure convergence is natural, and, presumably, more delicate.


Leonardo Sandrolini
email: leonardo.sandrolini@unibo.it

Andrea Mariscotti
email: andrea.mariscotti@unige.it

Impact of Short-Time Fourier Transform Parameters on the Accuracy of EMI Spectra Estimates in the 2-150 kHz Supraharmonic Interval

Keywords: AC-DC power converters, Discrete Fourier Transform, Electromagnetic compatibility, Electromagnetic interference, Conducted

Methods based on time-domain sampling and successive tapering and Fourier analysis, used in the "harmonics" frequency interval up to 2.4 kHz, cannot be automatically extended to the 2-150 kHz interval, in particular considering the emissions of Switched-Mode Power Supplies (SMPSs) in a modern smart grid or low-voltage distribution scenario. Emissions are substantially impulsive and oscillatory superposed to the mains signal, possibly featuring multiple switching fundamentals and their harmonics with unstable or purposely changing fundamental frequency. Fourier analysis (namely Discrete Fourier Transform) is commonly used to characterize the spectrum of emissions from time-domain data, but the influence of its settings should be verified for accuracy and systematic errors, so to establish the uncertainty of spectral estimates. After an initial theoretical and practical discussion of characteristics, objectives and weak points, a verification is carried out with the help of several measurements performed in different operating conditions on a set of six different SMPSs, evaluating systematic error and uncertainty, and defining a set of recommendations.

emissions; Power Quality; Smart grids; Supraharmonics.

Introduction

The widespread use of Switched-Mode Power Supplies (SMPSs) can be justified with flexibility, portability and better efficiency, including superior voltage regulation at the load compared to more traditional conversion schemes. SMPSs feature various types of power electronic converters, whose conducted emissions must be assessed accurately, with harmonic and interharmonic distortion occurring over a wide range of frequencies [START_REF] Thomas | Conducted emissions in distribution systems (1 kHz-1 MHz)[END_REF]. Conducted emissions caused by the switching process, in fact, originate from switching fundamentals of some tens of kHz and spread in the hundreds kHz and MHz ranges, well above the "classical" interval of harmonic penetration studies, limited in general to 2.0-2.4 kHz for 50-60 Hz systems [2, 3]. In the last ten years attention has been extended to frequency intervals up to 150 kHz [4][5][START_REF] Bartak | EMI of emissions in the frequency range 2 kHz -150 kHz[END_REF][START_REF] Klatt | Comparison of measurement methods for the frequency range of 2 kHz to 150 kHz[END_REF][8][START_REF] Mariscotti | Techniques for the analysis of time-domain conducted emissions of SMPS in smart grids[END_REF][START_REF] Ensini | Conducted emissions on DC power grids[END_REF][START_REF] Hedayati | Filter configuration and PWM method for singlephase inverters with reduced conducted EMI noise[END_REF][12], focusing on the so called "supraharmonics". Some standards [13][14][15][START_REF]Electromagnetic compatibility (EMC) -part 4-19: Testing and measurement techniques -test for immunity to conducted, differential mode disturbances and signalling in the frequency range 2 kHz to 150 kHz[END_REF] deal with the 2-150 kHz interval, but do not cover explicitly a critical source of emissions, SMPSs, and similarly other switching power converters, such as Photovoltaic Infeed Converters (PVIC). Modern SMPS as a source of EMI in smart grids and LV industrial networks have received much attention [4][5][START_REF] Bartak | EMI of emissions in the frequency range 2 kHz -150 kHz[END_REF][START_REF] Klatt | Comparison of measurement methods for the frequency range of 2 kHz to 150 kHz[END_REF][8][START_REF] Mariscotti | Techniques for the analysis of time-domain conducted emissions of SMPS in smart grids[END_REF][START_REF] Ensini | Conducted emissions on DC power grids[END_REF][START_REF] Hedayati | Filter configuration and PWM method for singlephase inverters with reduced conducted EMI noise[END_REF][12], especially considering the extension of the frequency range beyond the harmonic interval and the significant propagation and penetration in low-voltage networks (e.g. caused by interaction of device frontend filters, resonances, etc.) [START_REF] Bollen | Spread of high frequency current emission[END_REF][18][START_REF] Torquato | Propagation characteristics of high-frequency harmonics in distribution systems[END_REF]. A broader resolution bandwidth has been recently proposed [START_REF] Klatt | Comparison of measurement methods for the frequency range of 2 kHz to 150 kHz[END_REF][START_REF]Electromagnetic compatibility (EMC) -part 4-30: Testing and measurement techniques -power quality measurement methods[END_REF] passing from the aggregation bandwidth of 200 Hz of the IEC 61000-4-7 [START_REF]Electromagnetic compatibility (EMC) -part 4-7: Testing and measurement techniques -general guide on harmonics and interharmonics measurements and instrumentation, for power supply systems and equipment[END_REF], to the 2 kHz frequency resolution of the IEC 61000-4-30 [START_REF]Electromagnetic compatibility (EMC) -part 4-30: Testing and measurement techniques -power quality measurement methods[END_REF], closer to the resolution bandwidth (RBW) required for the radiofrequency conducted emissions above 150 kHz. All these measurements are performed using timesampled data followed by spectrum calculation with Fourier transform (a Discrete Fourier Transform, DFT, implemented as Short-Time Fourier Transform, STFT, to include the overlap of adjacent windows when tracking Fourier spectrum versus time). When dealing with potentially nonstationary impulsive emissions, the effect of the STFT parameters on the accuracy of the spectrum estimate in amplitude and frequency needs to be quantified. Nevertheless, frequency domain scan of emissions with classic EMI receivers requires measuring the signal within the resolution bandwidth in a given measurement time, which increases the scan time even for narrow frequency ranges such as 2-150 kHz, as the receiver must be tuned in steps smaller than the resolution bandwidth (less than 200 Hz, the 6 dB EMI bandwidth according to [START_REF]Specification for radio disturbance and immunity measuring apparatus and methods -part 1-1: Radio disturbance and immunity measuring apparatus -measuring apparatus[END_REF]) to obtain an accurate result [START_REF] Medler | Timing considerations using FFT-based measuring receivers for EMI compliance measurements[END_REF][START_REF] Keller | Comparison of time domain scans and stepped frequency scans in EMI test receivers[END_REF]. Although the cited standards require the evaluation of amplitude-only spectra against limits, the phase of the spectrum components may be also relevant to evaluate the combined effects of multiple SMPSs, resonance phenomena, etc. [START_REF] Alfieri | New power quality indices for the assessment of waveform distortions from 0 to 150 kHz in power systems with renewable generation and modern non-linear loads[END_REF], giving advantage to methods based on time-domain data.

In general, SMPS conducted emissions observed in time domain contain the switching fundamental (or more than one, depending on the architecture), its harmonics, and other narrowband components at higher frequency, superposed to the mains fundamental and repeating following the modulation process (e.g. 100 Hz for power factor correction at the output of the single-phase rectifier with 50 Hz mains), as shown in Fig. 2 of [START_REF] Bollen | Standards for supraharmonics (2 to 150 khz)[END_REF] and later in sec. 3 below.

Considering the switching and modulation process, modern modulators for converters in the range of some tens of W up to some kW have switching frequencies in the tenths of kHz and adopt smart modulation techniques to reduce voltage stress on components, improve efficiency and reduce EMI. Modulators are also able to switch between different modulation patterns, each optimized for a range of operations: for example pulse skipping at very low loads improves efficiency, whereas Pulse Frequency Modulation (PFM) not only does not sacrifice efficiency, but has a very fast dynamic response, particularly useful for load steps. The well known Pulse Width Modulation (PWM) is usually adopted at large loading near the nominal or above, to ensure stability, when attaining high values of efficiency is much less critical. These modulation techniques have different spectral signatures, and considering the fast control loop dynamics, they may be applied one after the other during the same transient or load step, with two of them even captured in a single Fourier time window, that needs thus to be as short as possible.

In addition, small-scale variability of spectral lines and phase noise can also be caused by drift due to temperature changes, switching timebase instability, etc., besides small modulation adjustments.

As opposed to the standard swept frequency-domain method using a spectrum analyzer or EMI receiver with Peak, Quasi-Peak or Average detectors as per many standards, real-time spectrum analyzers have been proposed and demonstrated [START_REF] Braun | A real-time time-domain EMI measurement system for full-compliance measurements according to CISPR 16-1-1[END_REF][START_REF] Costa | Time-domain electromagnetic interference measurement system for intermittent disturbances[END_REF][START_REF] Azpurua | A measurement system for radiated transient electromagnetic interference based on general purpose instruments[END_REF], as well as pure time-domain baseband sampling, e.g. by means of a Digital Sampling Oscilloscope (DSO) or data acquisition system (DAS) followed by Fourier analysis, is used extensively [START_REF] Parvis | A precompliance EMC test-set based on a sampling oscilloscope[END_REF][START_REF] Noshahr | Evaluating emission and immunity of harmonics in the frequency range of 2-150 kHz caused by switching of static convertor in solar power plants[END_REF]. The advantages are: economic, if using a DSO or DAS already available; the possibility of selecting various analysis modes and parameters, and repeating the analysis at will starting from the original time-sampled data; tracking frequency domain characteristics of emissions for the entire spectrum, with the zero span mode limited to a single frequency only. Conversely, the drawbacks and limitations are: a more limited dynamic range and higher noise floor, as a direct consequence of the limited number of bits; the risk of overloading, that may occur whenever large low-frequency components or major transients overlap to the frequency interval subject to measurement. Overloading from low-frequency components can be prevented by using a high-pass filter (similar to the EMI receiver input selector filter), but cannot improve the full scale setting, which is determined by the height of the main peak, as it will be shown in Section 3. This work considers time-domain sampling, but follows a frequency-domain approach based on Fourier analysis, as the basic analysis tool so widespread in the literature, for which some care must be exercised. In fact, Fourier analysis is implemented in the methods described in the two major referenced standards for supraharmonics, IEC 61000-4-7 [START_REF]Electromagnetic compatibility (EMC) -part 4-7: Testing and measurement techniques -general guide on harmonics and interharmonics measurements and instrumentation, for power supply systems and equipment[END_REF] and IEC 61000-4-30 [START_REF]Electromagnetic compatibility (EMC) -part 4-30: Testing and measurement techniques -power quality measurement methods[END_REF]. Recently in [32,[START_REF] Khokhlov | Comparison of measurement methods for the frequency range 2-150 kHz (supraharmonics) based on the present standards framework[END_REF] these two approaches have been compared and, although both methods present critical elements in detecting components with variable frequency and/or magnitude, IEC 61000-4-30 shows better performance than IEC 61000-4 4-7, except for the analysis of disturbance components with small amplitude.

A method that removes spacing between adjacent Fourier windows allows highfrequency components to be detected in a periodic voltage disturbance appearing as a notch, which instead cannot be detected by equally-spaced measurement methods, such as the one in [START_REF]Electromagnetic compatibility (EMC) -part 4-30: Testing and measurement techniques -power quality measurement methods[END_REF]. This method in reality corresponds to the application of STFT for the analysis of long sequences of time-sampled data; the correct and aware use of the STFT to this wide class of signals needs thus an in-depth investigation, as it will be shown in the rest of the work.

It is briefly noted that although the Fourier analysis is the preferred and widely used approach, analysis of electrical quantities with poor stationarity or featuring significant transients can be carried out using time-domain Power

Quality indexes and Multiresolution Signal Decomposition has been proposed

with examples for AC and DC supply schemes [34][35][START_REF] Sandrolini | Signal transformations for analysis of supraharmonic EMI caused by switched-mode power supplies[END_REF].

The objective of the paper is twofold: i) defining suitable choices of STFT parameters as for frequency resolution, sampling rate, overlap and time window to track satisfactorily signal dynamics, including agreement with existing standards; ii) characterizing the impact of the various parameters on the accuracy of the estimate of spectral components (amplitude and frequency). Considering the lack of synchronous sampling and local non-stationarity of the SMPS modulation, spectral leakage is an issue: a relevant point is thus to include the effect of smoothing windows in the assessment.

The characteristics of the STFT algorithm considered to process time-domain data and the experimental setup are illustrated in Sec. 2. The results are presented in Sec. 3. From the analysis presented in Sec. 4, it is shown that the choice of the smoothing window has influence on the accuracy of the amplitude estimate and represents a source of systematic error. Although broader smoothing windows tend to worsen the accuracy of the frequency estimate of components, this is not a critical aspect, as interpolation can recover easily the location of signal components lying between frequency bins with a more than satisfactory accuracy. Finally, the estimates are statistically analysed by means of boxplots, where the impact of different windows, overlap and resolu-tion frequency on the estimated amplitude of spectral peaks is considered. A set of recommendations is defined as regards max-hold setting, type of window, overlap and frequency resolution.

The analysis is verified against experimental data from six different SMPS in various operating conditions, so with a wide range of spectral signatures. Swept frequency spectra of an EMI receiver are also included as reference.

Problem Definition and Experimental Setup

The considered characteristics of the STFT algorithm are reviewed in the following, setting the framework of the analysis appearing in Sections III and IV. The experimental setup for the measurement of SMPS conducted emissions is also described.

STFT General Characteristics

The STFT is based on the Discrete Fourier Transform (DFT) and adopts a sliding approach to track spectral properties of the signal over time. The critical parameters are: the time window T , which defines the frequency resolution, df = 1/T , and sets a relationship with the signal nonstationary components; the number of points N stems directly from the chosen sampling frequency f s = N df . It is worth noting that DFT can be interpreted as a bank of filters each with df bandwidth, useful when reasoning on the amount of noise and averaging of nonstationary components implemented by a more or less large df value.

Due to nonstationarity and lack of synchronous sampling, spectral leakage [START_REF] Harris | On the use of windows for harmonic analysis with the discrete fourier transform[END_REF][START_REF] Lyons | Understanding Digital Signal Processing[END_REF] is a key performance issue in both its manifestations:

• Long-range leakage: the interference, or mutual effect, between spectral components, caused by the lack of synchronism between the time window T and the period of the sinusoidal components within the signal. When synchronous sampling is not possible, a suitable control measure is using smoothing (or tapering) windows to reduce the order of the discontinuity at the ends of the periodic extension where the signal is cut.

• Short-range leakage, that corresponds to the simpler fact that, when the spectrum is represented as samples on a discrete frequency vector, the real underlying signal frequency may lie between two discrete points, thus worsening or biasing the frequency estimate; it is also named "scalloping loss" or "picket fence effect". The problem is remedied by interpolation.

Smoothing windows have impact on many attributes of spectral analysis, including detection of details, resolution, and dynamic range. The estimated harmonic amplitude at a given frequency is biased by the accumulated broad-band noise that falls inside the bandwidth of the window, behaving as a filter. Starting from the implicit rectangular window, a convenient figure of merit is the Equivalent Noise Bandwidth (ENBW) [START_REF] Harris | On the use of windows for harmonic analysis with the discrete fourier transform[END_REF] (see Table I). To ensure spectrum readability, the dynamic range between the relevant components peaks and two types of extraneous elements (noise and residual leakage due to window sidelobes) should be considered. For noise, without synchronous sampling, the improvement of such dynamic range by averaging of N s successive spectra is only through the reduction of the noise variance (as square root of N s ), that is the so-called "incoherent averaging" using only amplitude information [START_REF] Lyons | Understanding Digital Signal Processing[END_REF]. For sidelobes a window with low "highest sidelobe level" should be used [START_REF] Harris | On the use of windows for harmonic analysis with the discrete fourier transform[END_REF].

Interpolation is a further option to improve the accuracy of amplitude and frequency estimates: several techniques have been proposed [START_REF] Quinn | Estimation of frequency, amplitude, and phase from the DFT of a time series[END_REF][START_REF] Jacobsen | On local interpolation of dft outputs[END_REF][START_REF] Gasior | Improving FFT frequency measurement resolution by parabolic and gaussian interpolation[END_REF][START_REF] Agrez | Weighted multipoint interpolated DFT to improve amplitude estimation of multifrequency signal[END_REF], such as parabolic, Gaussian (for samples with logarithmic amplitude, such as spectra expressed in dB), and M -point interpolation (M odd), with discussion still open on accuracy and applicability with/without smoothing windows.

STFT introduces another parameter, the percentage of overlap p between adjacent time windows for better time tracking, with a minor, but not negligible, impact on the correlation between spectral components.

STFT Settings

The values of the parameters for the analysis have been scheduled with different exigencies:

• for the frequency resolution df and time window length T :

compliance with the IEC 61000-4-7 [START_REF]Electromagnetic compatibility (EMC) -part 4-7: Testing and measurement techniques -general guide on harmonics and interharmonics measurements and instrumentation, for power supply systems and equipment[END_REF] requirement for PQ analysis, applicable to the low frequency range up to 2 kHzfor 50 Hz systems, setting T = 200 ms; this sets the minimum overall time record length to 200 ms;

compliance with the standards for EMI in the 2-150 kHz range [13][14][15][START_REF]Electromagnetic compatibility (EMC) -part 4-19: Testing and measurement techniques -test for immunity to conducted, differential mode disturbances and signalling in the frequency range 2 kHz to 150 kHz[END_REF], that indicate a swept frequency-domain technique using preferably 200 Hz resolution bandwidth (RBW) (corresponding to T = 5 ms); to the aim of extending the 200 Hz analysis and covering MIL-STD settings, a 1 kHz RBW is included and an additional smaller RBW=100 Hz (corresponding to T = 1 and 10 ms, respectively);

• for the overlap percentage p:

values used in practice are 0 and 50% minimizing the correlation between samples of adjacent windows; the 0% value will be discouraged in section IV;

• selected smoothing windows are a tradeoff between completeness and compactness: the seven most popular windows (von Hann, Hamming, Blackman-Harris, Bohman, Flat Top, Gaussian, and the Rectangular one) are selected out of a set of about 25 available [START_REF] Harris | On the use of windows for harmonic analysis with the discrete fourier transform[END_REF] (see Table 1).

Experimental Setup

Six SMPSs for Information Technology Equipment (ITE) are considered (see Table 2), featuring low nominal power (between 10 and 30 W), to ease load power sizing (metal-heatsink housed resistors were used) and allow the use of a small 16 A LISN (Line Impedance Stabilization Network).

The AC mains disturbance, as an external factor and a source of measurement error, is decoupled by the LISN [START_REF] Collin | The role of supply conditions on the measurement of high-frequency emissions[END_REF]. The variations of the fundamental to attenuate the fundamental and the low-order harmonics possibly leaking through the LISN: the resistor R 1 = 1.5 kΩ is large enough to be neglected in parallel to the impedance matching 50 Ω resistor R m , giving a neat 100 nF for C 1 to get the 1 kHz cutoff. This setting is also in line with the EN 61000-4-30.

For frequency domain measurements an EMI receiver with Peak detector and variable RBW was used, scanning between 10 kHz and 1 MHz. The experimental setup is shown in Fig. 1.

The IEC 61000-4-7 [START_REF]Electromagnetic compatibility (EMC) -part 4-7: Testing and measurement techniques -general guide on harmonics and interharmonics measurements and instrumentation, for power supply systems and equipment[END_REF] indicates a requirement of synchronization with the mains fundamental waveform and period; the reason is to control spectral leakage at the source, rather than relying entirely on tapering in post-processing during Fourier analysis. As a matter of fact this is relevant for harmonics, i.e.

namely spectral components harmonically related to the mains frequency. In the present case observed phenomena are switching phenomena and consequential ringing, that are not harmonics of the fundamental, although they occur as a pulse train synchronized with the double of the fundamental frequency (100 Hz).

This fact is considered then later in sec. 3.1 for the selection of the window duration for the Fourier analysis. The pulsed pattern is thus synchronized with the mains frequency, and as a consequence DSO recording triggered to the main pulse, although the continuous Fourier spectrum of a single pulse is not related

Results Overview and General Considerations

This section reports a synthesis of the results and an overview of the achieved accuracy, as a guide for the interpretation of the detailed results shown in the next section.

Time domain waveforms

All SMPS have the signal y 1 from the LISN to the DSO characterized by impulses repeating every 10 ms (corresponding to the ripple of the rectified mains voltage internally in the SMPS), with alternate waveshape, depending on the internal alternating polarity of the rectification stage (see Fig. 2). Each impulse contains some bursts of oscillations with variable damping.

For the window duration T three conditions may be identified: T < 10 ms, T = 10 ms and T > 10 ms. A long window with T 10 ms will bracket many impulses of either polarity. Choosing exactly 10 ms with bad synchronization, the risk of observing always a head and a tail with opposite polarity (and thus smaller mean value) is quite high. Overlapping these 10 ms windows will ensure that there will be one window capturing an almost aligned portion of the impulse, much closer to the desired amplitude estimate. A value of T only slightly larger than 10 ms will be able to capture the impulse whatever the initial time position avoiding the negative effects of "weird" synchronization for T = 10 ms.

Using a window conveniently shorter than 10 ms ensures that bracketing of the central impulses will occur without reduction due to averaging with smaller portions in the head and tail of the signal; in this case the estimate of the overall spectrum will result from the collection and suitable processing of a sufficiently long series of windows. So, this last setting should be the preferred one.

Since the portion of the impulse yielding the peak amplitude is quite narrow (occurring at 10 and 20 ms in Fig. 2(a), and accompanied by additional impulses in Fig. 2(b)), taking the maximum absolute value of the STFT spectra (but losing phase information) will give a correct and consistent result, provided that T is not too small, e.g. not less than 0.5-1 ms in the present case. It is observed that 0.5 ms agrees with the 2 kHz bandwidth requirement in [START_REF]Electromagnetic compatibility (EMC) -part 4-30: Testing and measurement techniques -power quality measurement methods[END_REF].

Spectrum characteristics

The spectrum of the conducted emissions with a waveform as in Fig. 2 is a line spectrum as could be measured with a narrow enough RBW, in the range of 30 Hz or less, to separate the lines spaced by 100 Hz (twice the mains frequency). A swept frequency-domain measurement as in Fig. 3 can measure the rms at each step with a dwell time long enough to assure having captured the maximum rms reading of the signal at that frequency bin (the scan time of the example was about 11 hours).

The first peaks of the switching fundamental appear between 20 and 50 kHz depending on the type of SMPS; their harmonics have decreasing amplitude,

Accuracy, Systematic errors, and Uncertainty

Calculated spectra are affected by systematic errors caused by window length T, due to averaging of signal components and too a narrow frequency resolution, and by weird synchronization with the repetition rate of 100 Hz (with the term "weird" we indicate that the sequence of windows fixed by the choice of the initial time interval may miscut the signal, so that no window contains all the relevant portions of the signal). Once systematic errors are removed or under control by selection of T and p (the latter is less critical, provided it is not 0, see end of Sec. 4.3), applying max hold, the remaining variability may be ascribed to the uncertainty of the method. This is statistically analyzed and displayed with boxplots in sec. 4, where the mentioned max hold value should be retained as the correct estimate of the amplitude. Smoothing windows, excluding Flat-Top,

show altogether a spread of maxima of less than 0.5 dB, the Flat-Top always estimating larger amplitudes, anticipating the result of a shorter time window.

The spread of maxima due to the overlap, excluding p = 0% that in some cases gives a significantly lower value, is limited to less than 0.1 dB.

Detailed Results and Quantitative Analysis

The line spectrum measured with the EMI receiver with low RBW (10 Hz) (see Fig. 2 as example) is considered the reference for the spectrum details and amplitude estimate.

Amplitude accuracy

The choice of the smoothing window has influence on the accuracy of the amplitude estimate (Fig. 5) and represents a source of systematic error. Starting

Frequency resolution

The effect of the frequency resolution df is considered with respect to the amount of noise floor, separation of components and resulting amplitude. Small enough df values (less than the 100 Hz spacing) give a detailed representation of the underlying line spectrum, as shown in Fig. 8; the line spectrum becomes an envelope spectrum, as soon as df approaches 100 Hz. The effect of ENBW can be recognized: for the Flat-Top with 3.77 bin a 50 ms time window is barely sufficient to recognize the line spectrum; the Gaussian window with only 1.45 bin follows well peaks and valleys. The effect of the captured noise floor can be seen in the difference of the estimated peak amplitude for the same df condition, as reported in the caption of Fig. 8: it is easy to see that the peak amplitude estimates for the largest RBW are very similar and for the analyzed data the error is only 0.3 dB. The 5 Hz frequency resolution very accurately shows the 100 Hz spaced spectrum lines at the expense of a heavy unacceptable amplitude underestimate. Considering that the frequency components highlighted by the smallest df values are coherent, they must be summed arithmetically when they combine under a larger df value: thus estimated amplitude grows up almost linearly with RBW, although there is a significant decay of the lateral lines, so that the contribution of those farther from the center line is much less relevant (from which the Flat-Top reaching faster the "saturated" amplitude value for that bin); the linear increase with RBW can thus be held correct for the narrower RBWs for which the bell shaped spectrum lines have a similar height and not a pronounced slope [START_REF] Linkwitz | Techniques for measuring narrowband and broadband emi signals using spectrum analyzers[END_REF].

Uncertainty of the amplitude estimate

Statistical properties of the estimates are first demonstrated by comparison of the curves of the median and the two profiles of the inter-quartile levels (25% and 75%), compared to the top curve obtained with the max hold (see Figure 9). Then a more refined graphical representation is implemented by means of boxplots, where the impact of different windows, overlap p and resolution frequency df on the estimated amplitude of spectral peaks is considered.

The curves in Figure 9 show that the dispersion described by the interquartile profiles is smaller at high frequency (less than ±5 dB) and larger for the low frequency components. The max hold profile is much larger, indicating that the distribution at almost all frequency bins is long tailed, except for those frequency intervals around 30 -38 kHz and 57 kHz, where there are no relevant components of emission.

Calculated spectra are thus subject to a significant dispersion and characterized by systematic errors for some specific parameters combinations. Boxplots allow a better and more complete graphical representation of the statistical characteristics. They show the median (red horizontal bar), the inter-quartile levels (25% and 75%, also known as Q1 and Q3, respectively, represented by the upper and lower blue edges of the box) and the upper and lower adjacent values (represented by the black horizontal dashes of the whiskers), which correspond to the largest or smallest data point which is not an outlier (red asterisks). The The overlap condition p = 0% (no overlap) leads in some cases to underestimation of the maximum or larger spread, as shown in Fig. 10 and 11 (the evidence was obtained by plotting the same boxplot, but removing the cases for p = 0% observing that the outliers at the bottom disappeared); moreover, the notches of the boxplot relevant to p = 0% in some cases do not overlap with the other boxplot notches, thus suggesting a different median of the relevant distribution; using some percentage of overlap is then recommended (50% is generally easier to implement).

It is also observed that the largest estimate is obtained with RBW = 2 kHz, in line with the recommendation of the IEC 61000-4-30, but also the amplitude estimates resulting from RBW = 1 kHz are very close: we may say that much of the difference for the first peak of both LB P25 (Fig. 10(a)) and KT P25 (Fig. 11(a)) is due to the larger collection of the background noise for the 2 kHz setting. For the analyzed SMPSs, since the switching burst may last up to about 1 ms, in a few cases the readout with RBW = 2 kHz was slightly lower than for 1 kHz: this occurred for less than 1% of all cases and the maximum difference was about 0.2 dB.

As already pointed out, the Flat Top has a larger ENBW and anticipates the estimate compared to the other windows. Considering that the proposed method uses the max hold function applied to the calculated DFT spectra, the comparison of the maxima obtained with the different windows shows that is a difference of the maxima of 0.9 -1.2 dB for the LB and 0.5 -0.6 dB for the KT (using spread-spectrum modulation), as appears in Table 3, by comparing the mean values in the two rightmost columns.

In order to complete the analysis, the results for another configuration, P90, As soon as all the RBW values and windows are used and the maximum is extracted, the resulting amplitude estimates are all aligned whatever the overlap percentage, although we have already noticed that 0% is exposed to larger dispersion, outliers and in principle the risk of underestimating some signal components based on the following mechanism, already discussed in sec. 3.1: the combination of a time window length T equal to the repetition period of the pulses, combined with a no overlap setting (p = 0%), with a synchronized acqui- it all along the recording, in particular if smoothing windows are used, that attenuate the signal at the two ends. This may also occur for sub-multiples of 10 ms, such as 5 ms.

In general spread-spectrum modulation might show some inconsistencies in the results, such as: lack of a clear monotonic increase of amplitude with increasing RBW, especially for high-frequency components, as observed above for the comparison of 1 kHz and 2 kHz RBW values; uncommon statistical distribution of amplitude values, resulting in a larger number of outliers, as detected by the boxplot routine.

Conclusion

The time-domain measurement of conducted emissions of Switched-Mode Power Supplies (SMPSs) has been considered compared to the frequency domain method, analyzing the effects of the parameters of the Short-Time Fourier In general, broad tapering windows are preferable (such as the Flat-Top, although the other examined windows give also repeatable results) and/or the use of a short enough window (e.g. T = 0.5 -1.5 ms) to slice the signal accurately, followed by max hold applied to the absolute value of the spectral components.

Of course, the max-hold setting necessary for an accurate estimate of the spectral amplitude reduces the accuracy of tracking vs. time and does not allow to preserve phase information.

The accuracy of the frequency estimate of components is not a critical aspect, although broader smoothing windows tend to worsen it; interpolation can recover easily the location of signal components lying between frequency bins with a more than satisfactory accuracy. For amplitude interpolation has not been considered in this work, since the focus was on the variability of spectrum data to which various interpolation methods can be applied at a later stage.

Once max hold and a conveniently large resolution frequency (1 -2 kHz) are chosen, the remaining uncertainty of the amplitude estimate is quite small, showing a spread of 0 -0.3 dB with respect to the overlap values and 0.9 -1.2 dB with respect to the smoothing windows excluding the Flat Top; using the Flat Top, as advised, removes the uncertainty related to the used window, maximizing the amplitude estimate.

Figure 1 :

 1 Figure 1: Scheme of the experimental setup: SMPS under test and its dc variable load, LISN (Line Impedance Stabilization Network), 50 Ω impedance matching, high-pass filter (1 kHz cutoff) and low-pass filter (2 MHz cutoff), Digital Storage Oscilloscope (DSO) and EMI Receiver.

Figure 2 :

 2 Figure 2: Time domain waveform of the high-pass filtered LISN output y 1 for KT P25 (a) and P90 (b) power levels.

Figure 3 :

 3 Figure 3: Line spectrum of LB P25 measured with EMI receiver and RBW = 10 Hz.

Figure 4 :

 4 Figure 4: STFT spectra for (a) KT P25 (waveform in Fig. 2), (b) LB P25, Hann window, 50% overlap, decreasing time window length T = 10, 5, 1, 0.5, 0.25 ms (from light grey to black curve).

  from a situation where all spectra are corrected for the different coherent gain values of the selected smoothing window, it is possible to observe the peak at the fundamental in Fig.5(b) that increases going from the Rectangular (in light grey) to the Hann and Gaussian, Hamming and Blackman-Harris, and then Flat-Top. The spread of amplitude values is not only caused by the amount of noise floor captured by larger ENBW values, but also by the different slope and sideband attenuation intercepting the adjacent line spectrum components (visible in Figs.7 and 8). A broader window yields larger estimates, closer to the true value (represented by the top curves in Fig.7). The Flat-Top, for instance, anticipates the growth of the peaks for increasing RBW, at the expense of a longer window duration by about a factor 2 (the ratio of the ENBW values) to keep the same effective frequency resolution.The amplitude accuracy attained with the Flat Top window and the other tapering windows (represented by a Hann window) is again emphasized in Figure6for a different SMPS (SH P90) operating with a random modulation: even for 200 Hz RBW the Flat Top correctly estimates the amplitude of the switching components with the green curve almost touching the other two curves at 1 kHz and 2 kHz RBWs; conversely, the amplitude of the nonstationary components caused by the overall switching pulse shape increases with RBW and using the Flat Top, as already pointed out.

Figure 5 :

 5 Figure 5: STFT spectra for LB P25, 200 Hz, 50% overlap and different smoothing windows.

Figure 6 :

 6 Figure 6: STFT spectra for SH P90, 50% overlap, RBW = 2 kHz, 1 kHz and 200 Hz for blue, orange ad green curves: (a) Hann and (b) Flat-Top windows.

Figure 7 :

 7 Figure 7: STFT spectra for KT P25, 50% overlap, RBW = 1 kHz, 200 Hz, 100 Hz, 20 Hz, 5 Hz for top (light gray) to bottom (black) curves: (a) Hanning and (b) Flat-Top windows.

Figure 8 :

 8 Figure 8: STFT spectra for LB P90, 50% overlap, RBW = 1 kHz, 200 Hz, 100 Hz, 20 Hz, 5 Hz for top (light gray) to bottom (black) curves: (a) Gaussian and (b) Flat-Top windows. Peak amplitude at RBW = 1 kHz, 200 Hz and 100 Hz is (a) 77.9, 75.4, 71.5 and (b) 78.2, 78.1, 77.2 dBµV, respectively. 24

Figure 9 :

 9 Figure 9: Spectrum of SH P25 measured with 1 kHz frequency resolution: median (purple solid), inter-quartile levels (purple dashed) and max hold (light brown).

  of the LB and KT SMPSs and for P25 and P90 for the BA SMPS are shown in Fig. 12. The boxplots present the amplitude of the first peak as a function of frequency resolution. Comparing Fig. 12 with Figs. 10 (a), (b) and Fig. 11 (a), (b) it can again be noticed that the notches of the boxplots do not overlap, yielding strong evidence that the medians of the distributions differ and confirming the importance of frequency resolution in the analysis. Moreover, as previously noticed the 200 Hz frequency resolution is either responsible of largest dispersion (for LB P90 and KT P90) or highest number of outliers (for BA SMPS). Eventually, observing Fig. 12 (c), (d), besides non overlapping medians one can notice that the maxima of the distributions decrease with decreasing frequency resolutions; in the case of BA SMPS, thus, it seems that 2 kHz is the minimum frequency not to underestimate the first peak.

Figure 10 :Figure 11 :Figure 12 :

 101112 Figure 10: Boxplot of the amplitude of the first (a, c, e) and second peak (b, d, f) for LB P25, as a function of (a, b) frequency resolution (corresponding to the T values in S T ), (c, d) smoothing window, (e, f) overlap percentage p for values in S p . 29

Table 1 :

 1 Properties of the Selected Smoothing Windows

				Equiv.
		Highest		Noise		Worst-case
			Coherent		Scallop
	Window	Side-lobe		Band-		processing
			Gain		Loss (dB)
		level (dB)		Width		loss (dB)
				(bins)
	Rectangular
		-13	1.000	1.00	3.92	3.92
	(R)
	von Hann
		-32	0.500	1.50	1.42	3.18
	(HN)
	Hamming
		-27	0.540	1.36	1.75	3.10
	(HM)
	Blackman-
	Harris	-92	0.359	2.00	0.83	3.85
	(BH)
	Bohman (B)	-46	0.405	1.79	1.02	3.54
	Flat Top (FT)	-88	0.216	3.77	0.01	5.77
	Gaussian (G)	-44	0.495	1.45	1.58	3.18

amplitude instead are not filtered by the LISN and should be considered as a potentially influencing factor. Recently, they have been considered for their impact on the assessment of conducted emissions of LED lamps

[START_REF] Collin | The role of supply conditions on the measurement of high-frequency emissions[END_REF]

, finding that the LISN (or equivalent network) is necessary to filter pollution of supraharmonic terms from the mains, but waveform quality for the low frequency portion can be ensured only with a separated power supply. Results obtained in

[START_REF] Collin | The role of supply conditions on the measurement of high-frequency emissions[END_REF]

, Fig.

12

, show two different behaviors for Type A and Type D LED lamps, with the former quite insensitive to a spread of the fundamental amplitude of ±10%; the latter instead exhibit a 100% variation of current intensity at the switching frequency over the said spread. In the present case, the analysis is carried out for each SMPS and each test condition with one recorded trace of 200 ms, where significant variations of mains amplitude can be excluded a pri-2 is the internal input capacitance of the DSO, equal to 15 pF with good accuracy (and not critical for the used sampling rate compared to the selected 2 kHz -1 MHz interval). A high-pass filter with a cutoff frequency of 1 kHz (one octave below the minimum frequency of interest) is also included

Table 3 :

 3 Mean and dispersion for max hold estimates of LB and KT SMPSs

	first and second peak of emission vs. overlap and window
			window	window	window
	SMPS peak	overlap
			(excl. R)	(excl. R & FT)	(only FT)
	LB P25 pk1	70.767 / 0	69.756 / 0.503	69.554 / 0.097	70.767
	LB P25 pk2	60.425 / 0.286	59.829 / 0.382	59.678 / 0.104	60.586
	KT P25 pk1	68.720 / 0.101	68.362 / 0.299	68.260 / 0.185	68.870
	KT P25 pk2	65.983 / 0.0008	65.538 / 0.235	65.449 / 0.096	65.984
	sition e.g. caused by the DSO trigger that position the peak at the beginning of
	the recording, will always underestimate the amplitude and never recover from


Olivier Garet

R Égine Marchand

PERCOLATION AND FIRST-PASSAGE PERCOLATION ON ORIENTED GRAPHS

Keywords: Mathematics Subject Classification. 60K35, 82B43 Percolation, first-passage percolation, sharp transition. 1

We give the first properties of independent Bernoulli percolation, for oriented graphs on the set of vertices Z d that are translation-invariant and may contain loops. We exhibit some examples showing that the critical probability for the existence of an infinite cluster may be direction-dependent. Then, we prove that the phase transition in a given direction is sharp, and study the links between percolation and first-passage percolation on these oriented graphs.

In percolation and directed percolation on the cubic lattice Z d , infinite clusters do not have the same geometry. In the unoriented setting, as soon as the opening parameter p exceeds the critical value p c (d) for the existence of an infinite cluster, one can build an infinite path in any given direction. On the contrary, in the oriented setting, clusters starting from the origin only live in the first quadrant; more precisely, when the opening parameter p exceeds the critical value -→ p c (d), a deterministic cone gives the directions in which infinite paths are found.

Between these two models, it seems natural to ask what may happen for percolation for oriented graphs, on the set of vertices Z d , whose connections do not forbid any direction, or in other words, for oriented graphs that contain loops.

In the present paper, we first exhibit one example of such an oriented graph, where every direction is permitted, but such that we observe two phase transitions: if p is small, there there exists no infinite path, then when p increases there is a phase where infinite paths exist but not in any direction (as in classical supercritical oriented percolation), and finally, when p is large enough, infinite paths can grow in any direction (as in classical supercritical unoriented percolation).

Then, coming back to the general framework, we give some properties of percolation on oriented graphs on Z d that give an echo to some standard results for unoriented percolation, with a particular attention to the links between oriented percolation and first-passage oriented percolation.

The framework and one example

We deal here with an oriented graph whose vertices are the elements of Z d , and whose edges are the couples (x, y) such that y -x belongs to a given finite set denoted by Dir. Hence, if E denotes the set of edges, one has

For a given parameter p ∈ (0, 1), we endow the set Ω = {0, 1} E with the Bernoulli product P p = Ber(p) ⊗E : under this probability measure, the edges are independently open (state 1) with probability p or closed (state 0) with probability 1 -p, and we are interested in the connectivity properties of the random graph G(ω) whose edges are the ones that are open in ω.

For x ∈ Z d , we denote by C + (x) the set of points that can be reached from x by a path in the random graph G, i.e. the points y such that there exists a sequence (x 0 , . . . , x n ) with x 0 = x, x n = y and (x i , x i+1 ) ∈ E for each i ∈ {0, . . . , n -1}.

For u ∈ R d \{0}, we define

D u (x) = sup y∈C+(x)
y -x, u .

The field (D u (x)) x∈Z d is stationary and ergodic. We set θ u (p) = P p (D u (0) = +∞) and p c (u) = inf{p > 0 : θ u (p) > 0}.

The quantity D u (x) measures the extension of the oriented open cluster issued from x in direction u and p c (u) is the critical parameter for the existence of an oriented open cluster that is unbounded in direction u. Note however that D u (x) = +∞ does not imply the existence of infinitely many points of C + (x) close to the half-line R + u.

An example. We take here d = 2, we fix some positive integer M and we choose Dir = {(0, -1); (-M, 1), (-M + 1, 1), . . . , (-1, 1), (0, 1), (1, 1), . . . , (M, 1)}.

In other words, the only allowed communications are the following: for all x, x ′ , y ∈ Z,

• (x, y) → (x ′ , y + 1) if |x -x ′ | ≤ M • (x, y) → (x, y -1) Let us denote by (e 1 , e 2 ) the canonical basis for R 2 : with this set of edges, we give an advantage to direction e 2 when compared to direction -e 2 .

We first observe that for M large enough, there exist values for the opening parameter p such that there is percolation in direction e 2 but not in direction -e 2 : Theorem 1.1. Denote by -→ p c (2) the critical value for classical oriented percolation on Z 2 + .

• For M ≥ 1, inf

u∈R d \{0} p c (u) ≥ 1 2M + 2
and sup [START_REF] Cox | Some limit theorems for percolation processes with necessary and sufficient conditions[END_REF].

u∈R d \{0} p c (u) ≤ -→ p c
• For M ≥ 2, p c (-e 2 ) ≥ 1 2 √ 2M + 1 . • For M ≥ 5, p c (e 2 ) ≤ 1 -(1 --→ p c (2)) 2/M < -2 log(1 --→ p c (2)) M ≤ 2 log 3 M .
Particularly, for M ≥ 37, p c (e 2 ) < p c (-e 2 ).

Proof. • The mean number of self-avoiding open paths starting from (0, 0) with length n is at most ((2M + 2)p) n . Thus if p < 1 2M+2 , the number of self-avoiding open paths is integrable and thus almost surely finite, and there is no percolation at all. When p > -→ p c (2), restricting Dir to {(0, -1), (1, 1)}, then to {(0, -1), (-1, 1)}, then to {(1, 1), (-1, 1)}, we obtain three copies of the standard oriented percolation in Z 2 + , and thus three percolation cones: it is then easy to see that for any u ∈ R d \{0}, P(D u (0) = +∞) > 0.

• For a fixed integer ℓ, the graph (Z 2 , E) contains exactly 2ℓ+n ℓ (2M + 1) ℓ paths from (0, 0) to Z × {-n} that contains ℓ steps upwards and ℓ + n steps downwards. Then, the mean number of open self-avoiding paths from (0, 0) to the line y = -n is no more that

+∞ ℓ=0 2ℓ + n ℓ (2M + 1) ℓ p 2ℓ+n ≤ +∞ ℓ=0 (2M + 1) ℓ (2p) 2ℓ+n = (2p) n 1 -4p 2 (2M + 1)
, as soon as 4p 2 (2M + 1) < 1. It follows that for p <

1 2 √
2M+1 , the number of selfavoiding paths from (0, 0) to {(x, y) ∈ Z 2 ; y ≤ 0} is integrable, therefore it is almost surely finite. This gives the first inequality.

• For the last inequality, we build a dynamic independent directed percolation from bloc events with length M/2 that partition the horizontal lines. Remember that M ≥ 5. The probability that a given point (x, y) in the segment

( M 2 x + [-M/4, M/4)) × {y} can be linked to some point in ( M 2 (x + 1) + [-M/4, M/4)) × y + 1} is larger than 1 -(1 -p) M/2
. So is the probability that one can link this point to some point in ( M 2 (x -1) + [-M/4, M/4)) × {y + 1}. Hence, we built a dynamic percolation of blocks in the spirit of Grimmett and Marstrand [START_REF] Grimmett | The supercritical phase of percolation is well behaved[END_REF] (see also Grimmett [START_REF] Grimmett | Percolation, volume 321 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF]), that stochastically dominates an independent directed bond percolation on Z 2 , with parameter 1 -(1 -p) M/2 . Then, percolation in direction e 2 is possible as soon as 1

-(1 -p) M/2 > -→ p c (2), whence p c (e 2 ) ≤ 1 -exp 2 M log(1 --→ p c (2)) < - 2 M log(1 --→ p c (2)) ≤ 2 log 3 M ,
where the last inequality comes from Liggett's bound [START_REF] Thomas | Survival of discrete time growth models, with applications to oriented percolation[END_REF]: -→ p c (2) ≤ 2/3. The desired result follows.

A sharp percolation transition

We now come back to our general framework. Let Ψ : Z d → R be a subadditive function, i.e. such that for any x, y ∈ Z d , Ψ(x + y) ≤ Ψ(x) + Ψ(y). We define

∀x ∈ Z d r Ψ (x) = sup y∈C+(x) Ψ(y -x).
The graph (Z d , E) being translation-invariant, the distribution of r Ψ (x) does not depend on x.

If A, B and S are subsets of Z d , the event A S → B means that there exists a path (x 0 , . . . , x n ) with x 0 ∈ A, x n ∈ B, x i ∈ S for i ∈ {1, . . . , n -1} and the bonds (x i , x i+1 ) are all open.

For p ∈ [0, 1] and 0 ∈ S ⊂ Z d , we define

ϕ p (S) := p (x,y)∈∂ + S P p (0 S → x), where ∂ + S = E ∩ (S × (Z d \S)) (1
p c (Ψ) := sup{p ∈ [0, 1] : P p (r Ψ (0) = ∞) = 0}.
Note that in the above definition, the set S may be infinite. Then, we have the following result: (1) For p < pc (Ψ), there exists c = c(Ψ, p) > 0 such that for each n ≥ 1,

P p (r Ψ (0) ≥ n) ≤ e -cn .
(2) For p > pc (Ψ), P p (r

Ψ (0) = +∞) ≥ p -pc (Ψ) p(1 -pc (Ψ))
.

In particular, (1) and (2) imply that pc (Ψ) = p c (Ψ).

Note that Ψ u (x) = u, x is linear and thus subadditive, and, for this map, p c (Ψ u ) = p c (u).

Proof. • At first, let us prove that (1) and (2) imply pc (Ψ) = p c (Ψ). If p < pc (Ψ), then for each n ≥ 1, we have P p (r Ψ (0) = +∞) ≤ P p (r Ψ (0) ≥ n) ≤ e -cn ; letting n go to infinity, we get P(r Ψ (0) = +∞) = 0. So pc (Ψ) ≤ p c (Ψ). But (2) implies that P p (r Ψ (0) = +∞) > 0 for p > pc (Ψ), thus pc (Ψ) ≥ p c (Ψ).

• Proof of (1): it is very similar to Duminil-Copin-Tassion [START_REF] Duminil-Copin | A new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model[END_REF][START_REF] Duminil-Copin | A new proof of the sharpness of the phase transition for Bernoulli percolation on Z d[END_REF][START_REF] Duminil-Copin | Correction to: a new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model[END_REF]. Since it is short, we give it to stay self-contained.

Let p < pc (Ψ). By the very definition of pc (Ψ), we can find S ⊂ Z d that contains the origin and such that ϕ p (S) < 1 and sup S Ψ < +∞. Fix a positive integer L ≥ sup S∪Dir Ψ. We set

Λ n = {x ∈ Z d : Ψ(x) ≤ n}. Thus, {r Ψ (0) > n} = {0 → Λ c n }. For k ≥ 1,
an open path starting from 0 and escaping from Λ kL eventually leaves S. Then,

{0 → Λ c 2kL } = ∪ (x,y)∈∂ + S {0 S → x, ω (x,y) = 1, y S c → Λ c 2kL }
By independence, we get

P p (r Ψ (0) > 2kL) ≤ (x,y)∈∂ + S P p (0 S → x) p P p (y S c → Λ c 2kL ).
Note that

• If (x, y) ∈ ∂ + S, then Ψ(y) ≤ Ψ(x) + max Dir Ψ ≤ 2L;
• {y

S c → Λ c 2kL } ⊂ {∃z ∈ C + (y) : Ψ(z) > 2kL}; • thus if (x, y) ∈ ∂ + S and z ∈ C + (y) is such that Ψ(z) > 2kL, then Ψ(z -y) ≥ Ψ(z) -Ψ(y) > 2kL -2L = 2(k -1)L.
We thus obtain

P p (r Ψ (0) > 2kL) ≤ (x,y)∈∂ + S P p (0 S → x) p P p (r Ψ (y) > 2(k -1)L) ≤ ϕ p (S)P p (r Ψ (0) > 2(k -1)L) It follows that P p (r Ψ (0) > 2kL) ≤ ϕ p (S) k ,
which gives the desired result.

• Proof of (2). In Duminil-Copin-Tassion, the idea is to use the Russo inequality. It is a bit more tricky here, because the events {0 ↔ ∂Λ n }, which correspond to the exit of finite boxes in Duminil-Copin-Tassion, now depend on infinitely many bonds. The proof is cut into three lemmas.

We begin with a lemma on a general graph.

Lemma 2.2. Let G = (V, E) be an oriented graph with V finite or denumerable. Let P denote a Bernoulli product on {0, 1} E . Let X and Y be disjoint subsets of V , with P(X → Y ) > 0. For each S ⊂ V , and each (x, y) ∈ E, we set

r (x,y) X (S) = 1 1 X⊂S 1 1 (x,y)∈∂ + S P(X S → x).
We denote by T Y the σ-field generated by the events {x → Y }, for x ∈ V . We denote by B Y the random subset of V composed by the points that are not linked to Y .

Remember that e ∈ E is said to be pivotal for an event

A ∈ B({0, 1} E ) in the configuration ω ∈ {0, 1} E if 1 1 A (0 e ω E\{e} ) = 1 1 A (1 e ω E\{e} ).
Then, for any e ∈ E,

P(e pivotal for X → Y, X → Y | T Y ) = r e X (B Y ).
Proof of Lemma 2.2. Let us denote by Γ the set of oriented paths in Y c from a point in Y c to a point in Y . Then the subsets ∩ γ∈A ∩ e∈γ {ω e = 1}, for A ⊂ Γ, form a π-system that generates T Y , so it is enough to prove that for each A ⊂ Γ, one has

P e pivotal for X → Y, X → Y, ∀γ ∈ A, ∀f ∈ γ, ω f = 1 = E   r e X (B Y ) γ∈A f ∈γ ω f   . (3)
The quantities that appear on each side of (3) are the limit of analogous quantities for a sequence of finite subgraphs of G. So, by dominated convergence, it is sufficient to prove (3) for a finite graph. From now on, we assume that G is finite.

Decomposing on the (finite number of) possible values of B Y , we thus only have to prove that for any subset S of vertices such that X ⊂ S ⊂ Y c ,

P e pivotal for X → Y, B Y = S ∀γ ∈ A, ∀f ∈ γ, ω f = 1 = E   r e X (S)1 1 {BY =S} γ∈A f ∈γ ω f   .
Fix a set S such that X ⊂ S ⊂ Y c . Let us denote by

E 1 = {(x, y) ∈ E : x, y ∈ S}, E 2 = ∂ + S = {(x, y) ∈ E : x ∈ S, y ∈ S c }, E 3 = {(x, y) ∈ E\(E 1 ∪ E 2 ) : ∃(u, v) ∈ ∂ + S, P 1 (v S c → x, y S c → Y ) = 1}.
Note that on the event B Y = S, as X ⊂ S, pivotal edges for X → Y are necessarily in E 2 and that when e / ∈ E 2 , both members vanish. The event B Y = S is measurable with respect to the states of the edges in E 2 ∪ E 3 , and implies that all edges in E 2 are closed. Thus both members vanish if A ⊂ E 3 . Denote by A 3 the set of possible configurations of edges in E 3 that correspond to B Y = S. Finally, we thus have to prove that for any S such that X ⊂ S ⊂ Y c , for any e = (x, y) ∈ E 2 , for any ξ ∈ A 3 ,

P e pivotal for X → Y, ∀f ∈ E 3 , ω f = ξ f , B Y = S = E   r e X (S)1 1 {BY =S} f ∈E3 1 1 {ω f =ξ f }   .
But now, by independence,

P e pivotal for X → Y, ∀f ∈ E 3 , ω f = ξ f , B Y = S = P X S → x, ∀f ∈ E 2 , ω f = 0 ∀f ∈ E 3 , ω f = ξ f =P(X S → x)P(∀f ∈ E 2 , ω f = 0, ∀f ∈ E 3 , ω f = ξ f ) =P(X S → x)P(B Y = S, ∀f ∈ E 3 , ω f = ξ f ),
which is indeed the mean value of r e X (S)1 1

{BY =S} f ∈E3 1 1 {ω f =ξ f } .
We come back to the case of a graph on

Z d . Lemma 2.3. Let p ∈ [0, 1]. For every natural number n, we set f n (p) = P p (0 → Λ c n ) and c n = inf S⊂Λn,0∈S ϕ p (S). Then, for each p ∈ [0, 1[. lim h→0 + f n (p + h) -f n (p) h ≥ 1 p(1 -p) c n (1 -f n (p)).
Proof of Lemma 2.3. The event {0 → Λ c n } depends on infinitely many bonds, so one can not directly apply the Russo formula. However, since {0 → Λ c n } is an increasing event, the following inequality is preserved (see for example Grimmett [START_REF] Grimmett | Percolation, volume 321 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF], page 43):

lim h→0 + f n (p + h) -f n (p) h ≥ e∈E P(e is pivotal for 0 → Λ c n ) = e∈E 1 1 -p P(e is pivotal for 0 → Λ c n , 0 → Λ c n )
Now consider the random set S n of points from which Λ c n can not be reached. Note that {0 → Λ c n } = {0 ∈ S n }. For each S ⊂ Z d and (x, y) ∈ E, we define the random variable

r (x,y) p (S) = 1 1 (x,y)∈∂ + S P p (0 S → x).
Integrating the result of Lemma 2.2, we have for each e ∈ E:

P(e is pivotal for 0 → Λ c n , 0 → Λ c n ) = E p 1 1 0∈Sn r e p (S n ) . Then, we get e∈E E p 1 1 0∈Sn r e p (S n ) = E p 1 1 {0 →Λ c n } e∈E r e p (S n ) = E p 1 1 {0 →Λ c n } ϕ p (S n ) p ≥ E p 1 1 {0 →Λ c n } c n p = c n 1 -f n (p) p ,
which gives the desired inequality.

∀x ∈ I, f (x) ≥ lim t→x -f (t); • h is continuous on I • For each x ∈ I lim t→0 + f (x + t) -f (x) t ≥ h(x).
F ε (x) = f (x) - x a h(t) dt + εx.
It is sufficient to prove that F ε is non-decreasing for each ε > 0. Indeed, it will imply that

f (b) - b a h(t) dt + εb = F ε (b) ≥ F ε (a) = f (a) + εa,
which gives the lemma when ε tends to 0.

Let

x ∈ [a, b]. By definition of F ε , lim t→0 + F ε (x + t) -F ε (x) t = lim t→0 + f (x + t) -f (x) t -h(x) + ε ≥ ε.
So there exists η x > 0 such that for any t ∈ (0,

η x ), Fε(x+t)-Fε(x) t ≥ ε/2 ≥ 0. Let B = {x ∈ [a, b] : F ε (x) < F ε (a)}.
Assume by contradiction that B = ∅ and define c = inf B. Let (x n ) be a sequence in B that tends to c. By the previous observation, the inequality

F ε (x n ) ≥ F ε (c) holds for n large enough. Since x n ∈ B, by definition of B, F ε (a) > F ε (x n ). Thus F ε (a) > F ε (c).
As F ε is the sum of a function which is upper semi-continuous from the left and of a continuous function, it is still upper semi-continuous from the left. So

F ε (c) ≥ lim t→c -F ε (t),
and by definition of c, F ε (t) ≥ F (a) for each t ∈]a, c[, so F ε (c) ≥ F ε (a). This brings a contradiction.

End of the proof of Theorem 2.1: proof of (2). Fix p ′ ∈]p c (Ψ), 1[ and define on [0, 1) the function g(x) = -log(1 -x): it is non-decreasing and convex.

Let p ∈ [p ′ , 1) and h ∈ (0, 1 -p):

g(f n (p + h)) -g(f n (p)) f n (p + h) -f n (p) f n (p + h) -f n (p) h ≥ g ′ (f n (p)) f n (p + h) -f n (p) h .
With Lemma 2.3 (note that as p > pc (Ψ), c n ≥ 1), we obtain that

lim h→0 + g(f n (p + h)) -g(f n (p)) h ≥ c n p(1 -p) ≥ 1 p(1 -p) .
We can now apply Lemma 2.4 on [p ′ , 1[: as f n is non-increasing, g • f n is nondecreasing, so it is clearly upper semi-continuous from the left: for any

p > p ′ g(f n (p)) ≥ g(f n (p)) -g(f n (p ′ )) ≥ p p ′ dx x(1 -x) = log p(1 -p ′ ) p ′ (1 -p) = g p -p ′ p(1 -p ′ )
.

It follows that f n (p) ≥ p-p ′ p(1-p ′ )
, then, letting p ′ tend to pc (Ψ), we get

f n (p) ≥ p -pc (Ψ) p(1 -pc (Ψ))
.

Finally, we obtain (2) by letting n go to infinity.

3. Links with first-passage percolation that can been seen as a random pseudo-distance on Z d . Using Kingman's subadditive ergodic theorem allows to define

∀x ∈ Z d µ ν (x) = lim n→+∞ t(0, nx) n , ( 5
)
where the limits hold almost surely and in L 1 . The functional µ ν is homogeneous and subadditive, and can be extended to a symmetric semi-norm on R d . With some extra integrability assumption, we obtain the analytic form of the asymptotic shape theorem:

lim x →+∞ t(0, x) -µ ν (x) x = 0 P a.s. ( 6
)
The subadditivity and the symmetries of the lattice imply quite simply that µ ν is a norm if and only if it µ ν ((1, 0, . . . , 0)) > 0 is strictly positive. Moreover, it has long been known (see for example Cox-Durrett [START_REF] Cox | Some limit theorems for percolation processes with necessary and sufficient conditions[END_REF] or Kesten [START_REF] Kesten | Aspects of first passage percolation[END_REF]) that µ ν is a norm if and only ν({0}) < p c (Z d ), where p c (Z d ) is the critical percolation parameter for independent percolation on the edges of Z d .

Our idea here is to find, in oriented percolation on (Z d , E), an analogous characterization of directions of percolation in terms of the semi-norm for an associated oriented first-passage percolation on (Z d , E). Things are necessarily more intricate, since we saw that for oriented percolation the critical probability may depend on the direction. (Z d ,E). We suppose that to each oriented bond e ∈ E is associated a random variable t e , the (t e )'s being i.i.d. integrable non-negative random variables, with ν as common distribution; we denote by p the probability p = P(t e = 0) = ν({0}).

Oriented percolation and first-passage percolation on

In this section, we assume that the semi-group of Z d generated by Dir is the whole set Z d . Then, the graph (Z d , E) is transitive.

As in the classical setting, we can define the passage time of an oriented path as in ( 4), use Kingman's subadditive ergodic theorem to define the associated functional µ ν as in [START_REF] Duminil-Copin | Correction to: a new proof of the sharpness of the phase transition for Bernoulli percolation and the Ising model[END_REF], which is now positively homogeneous and subadditive but not necessarily symmetric. By sudadditivity,

∀x, y ∈ Z d |µ ν (x + y) -µ ν (x)| ≤ y 1 max{µ(εe i ) : 1 ≤ i ≤ d, ε ∈ {0, 1}}.
Thus µ ν can be extended in the usual way to a non-symmetric semi-norm on R d . Finally, we get, under some extra integrability assumption, the analytic form of the asymptotic shape theorem as in [START_REF] Grimmett | The supercritical phase of percolation is well behaved[END_REF].

Our hope is to characterize the directions of percolations in (Z d , E) when edges are open with probability p, i.e. the u ∈ R d such that

D u (0) = sup y∈C+(0) y, u = +∞
with the help of the semi-norm µ ν for some law ν for the passage times of the edges. Since the only relevant parameter here is ν({0}) = p, we take from now on

ν p = pδ 0 + (1 -p)δ 1 ;
we denote by µ p the associated semi-norm on R d and we set

A p = {x ∈ R d : µ p (x) ≤ 1},
which is a closed and convex set, but not necessarily bounded. We thus need some basics in the theory of convex sets.

Convex sets.

As A p is closed and convex, we can associate to A p two nonempty closed convex cones:

• The recession cone

1 of A p is 0 + (A p ) = {u ∈ R d : A p + R + u ⊂ A p } = {x ∈ R d : µ p (x) = 0}. • The barrier cone of A p is Bar(A p ) = {u ∈ R d : sup x∈Ap x, u < +∞} = {x ∈ R d : b p (x) > 0}, where b p (u) = inf{µ p (x) : x ∈ R d such that u, x = 1}.
The polar cone of a closed non-empty convex cone C is defined by

C • = {u ∈ R d : ∀x ∈ C x, u ≤ 0}.
The map C → C • is an involutive map in the set of closed non-empty convex cones. Note also that C ∩ C • = {0}. Here, 0 + (A p ) is the polar cone associated to Bar(A p ) (see Rockafellar [START_REF] Rockafellar | Convex analysis[END_REF] Corollary 14.2.1 p 123). In other words, characterizing the directions x ∈ R d such that µ p (x) = 0 is equivalent to characterizing the directions y ∈ R d such that b p (y) > 0.

3.4. Results. Let us define, for p ∈ [0, 1],

BG(p) = u ∈ R d : P p sup y∈C+(0)
y, u = +∞ = 0 .

Note that BG(p) is non-increasing in p. The set BG(p) collects the directions in which the growth of the cluster issued from 0 is bounded. It is thus natural to make the following conjecture:

Conjecture 3.1. ∀p ∈ [0, 1] Bar(A p ) = BG(p).
For the moment, we only manage to prove the following result:

Theorem 3.2. For every p ∈ [0, 1], int(Bar(A p )) ⊂ BG(p) and ∪ q>p int(BG(q)) ⊂ Bar(A p ).
This result will be a direct consequence of corollaries 3.4 and 3.7.

As in the classical setting, we can describe the asymptotic behavior of the pointto-hyperplane passage times with µ p . For u ∈ R d \{0} and n ≥ 0, set Proof. As in the unoriented case, it will follow from the analytic form of the shape theorem. However, the existence of directions for which µ p vanishes requires some attention.

H n (u) = {x ∈ R d : x, u ≥ n} and t(0, H n (u)) = inf x∈Hn(u) t(0, x).
• Let L > b p (u). There exists x ∈ R d with u, x = 1 and µ p (x) ≤ L. For n ≥ 1, denote by x n one vertex in H n (u) which is the closest to nx.

Then µ p (x n ) ≤ nµ p (x) + O(1). Since t(0, H n (u)) ≤ t(0, x n ), we have lim t(0, H n (u)) n ≤ lim µ p (x n ) n ≤ µ p (x) ≤ L.
Letting L go to b p (u), we obtain that lim t(0, H n (u)) n ≤ b p (u).

• If u ∈ Bar(A p ), then b p (u) = 0 and the desired convergence is clear.

• If u ∈ int(Bar(A p )), there exists ε > 0 such that the open ball centered in u with radius ε is included in Bar(A p ); moreover, b p (u) > 0. By contradiction, assume that there exists ℓ ∈ (0, b p (u)) such that

lim n→+∞ t(0, H n (u)) n ≤ ℓ < b p (u).
Then, one can build an infinite increasing sequence integers (n k ) and sites (x k ) such that t(0, x k ) ≤ ℓn k and u, x k = n k + O [START_REF] Auffinger | 50 years of first-passage percolation[END_REF]. By a compactness argument, we can assume that

x k x k → x. Then, n k x k = x k x k , u + O(1/ x k ) → x, u
. By the asymptotic shape theorem, t(0,x k )

x k tends to µ p (x), and we get the inequality

µ p (x) ≤ ℓ u, x .
Assume that u, x = 0, then µ p (x) = 0, so x ∈ 0 + (A p ). But Bar(A p ) is the polar cone of 0 + (A p ): by definition of ε, u + εx/2 ∈ Bar(A p ), so 0 ≥ u + εx/2, x = ε/2, which is a contradiction. So assume that u, x = 0: we can define x = x u,x and then u, x = 1 and µ p (x) ≤ ℓ, which contradicts the definition of b p (u). x, u = +∞, for each n ≥ 1, one can find x n ∈ C + (0), with x n , u ≥ n. Then, x n ∈ H n (u) and t(0, H n (u)) = 0. We then apply Theorem 3.3.

Theorem 3.5. Fix u ∈ R d \{0} such that lim x→u p c (x) > 0 and fix p such that 0 < p < lim x→u p c (x). There exist constants A, B, κ > 0 such that ∀n ≥ 0 P(t(0, H n (u)) ≤ κn) ≤ Ae -Bn .
Proof. The idea is close to the one used by Grimmett and Kesten [START_REF] Grimmett | First-passage percolation, network flows and electrical resistances[END_REF] to obtain large deviations inequalities for first-passage percolation: along an optimal path from 0 to H n (u), we expect to find a number proportional to n/N of disjoint streches whose increase in the u-direction is at least N . However, as p < p c (u), the first point of Theorem 2.1 ensures that P p sup y∈C+(0) y, u ≥ N decreases exponentially fast with N , so with high probability, streches whose increase in the u-direction is at least N have to use edges with passage time 1, and should globally contribute to an amount of time κn for some small κ > 0. A renormalisation argument allows to make all this accurate. However, we did not manage to implement the renormalisation argument under the assumption p < p c (u), and we rather work under the stronger assumption p < lim x→u p c (x).

1. We can assume without loss that u 1 < 1. Then, we can find δ ∈ R 2 \{0} with u, δ = 0 such that v = u + δ and w = u -δ satisfy p < min(p c (v), p c (w)), v 1 < 1 and w 1 < 1. By construction, u = v+w 2 . We define the following set

T = x ∈ R 2 : x, v ≤ 1, x, w ≤ 1, x, u ≥ -10 .
We can easily check that T is bounded and thus is a triangle: for any x ∈ T , (7) -10 ≤ x, u ≤ 1, -11 ≤ x, δ ≤ 11, and

x 2 ≤ C = 100 u 2 2 + 121 δ 2 2 .
As sup{ x, v : x ∈ [-1, 1] 2 } = v 1 , we also check that [-1, 1] 2 ⊂ T , and we set θ = max( v 1 , w 1 ) < 1.

2. For an integer N ≥ 4, we partition Z 2 into boxes (B N (k)) k∈Z 2 = (2N k + {-N, . . . , N -1} 2 ) k∈Z 2 . We set B N = B N (0), and T N is the image of T by the dilatation with ratio N . Note that B N is included inside T N . We then define naturally the translated triangles T N (k) = 2N k + T N .

Consider now a path γ from 0 to H n (u). As in Grimmett-Kesten [START_REF] Grimmett | First-passage percolation, network flows and electrical resistances[END_REF], we now associate to this path a squeleton Γ = (i 0 , i 1 , . . . , i ℓ ) of distinct N -boxes and a sequence (b 0 , b 1 , . . . , b ℓ ) of sites such that, except for the last point, b k ∈ B N (i k ) ⊂ T N (i k ), in the following manner. Set i 0 = 0 and b 0 = 0. Suppose i 0 , . . . , i n , b 0 , . . . , b n have been defined.

• If the last point γ last of γ belongs to T N (i n ), then we end the process and set ℓ = n. • Otherwise, let b n+1 be the first point of the path that is outside T N (i n ) and define i n+1 as the only index such that b n+1 ∈ B N (i n+1 ). We also a crossing type for b n+1 :

if b n+1 -2N i n , v > N or b n+1 -2N i n , w > N , we say that the crossing type of i n is up; -otherwise b n+1 -2N i n , u < -10N and we say that the crossing type of i n is down.

We then remove the loops from this sequence, and we obtain, by relabeling the coordinates of the remaining N -boxes if necessary, the squeleton Γ = (i k ) 0≤l≤ℓ of the path γ, see Grimmett-Kesten [START_REF] Grimmett | First-passage percolation, network flows and electrical resistances[END_REF] for details. We denote by I up (γ) and I down (γ) the number of crossings of the squeleton that are of the respective types up and down. Note that I up + I down (γ) = ℓ. Let us now establish rough bounds for I up and I down by using the following decomposition

γ last = (γ last -b ℓ ) + ℓ-1 k=0 (b k+1 -2N i k ) + ℓ-1 k=0 (2N i k -b k ).
We have the following estimates:

• γ last and b ℓ are both in T N (i ℓ ), so with [START_REF] Grimmett | Percolation, volume 321 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF], γ last -b ℓ , u ≤ 11N .

• For any k ∈ {1, . . . , ℓ}, let a k be the last point of the path γ before b k to be in T N (i k-1 ). As a k ∈ T N (i k-1 ), with [START_REF] Grimmett | Percolation, volume 321 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF] From this, we first deduce that for every n large enough,

Theorem 2 . 1 .

 21 Fix d ≥ 2. Let Ψ : Z d → R be a subadditive function.

Figure 1 .

 1 Figure 1. Oriented percolation with M = 1, p = 0.51 on the left and p = 0.55 on the right. The pictures are centered at the origin. The points are colored accordingly to their distance to the origin. The coloring is performed by the Dijkstra algorithm until one hits the border.

Lemma 2 . 4 .

 24 Let I ⊂ R be an open interval of R and let f and h be real valued functions defined on I and such that• f is left upper semi-continuous on I from the left:

  Then, for any a and b in I with a ≤ b, we have f (b) -f (a) ≥ b a h(x) dx. Proof of Lemma 2.4. Let a, b ∈ I with a < b. We fix ε > 0 and define on [a, b]:

3. 1 .

 1 Percolation and first-passage percolation on the (unoriented) edges of Z d . Consider first Z d endowed with the set E d of edges between nearest neighbors. In the first-passage percolation model, iid non negative and integrable random variables (t e ) e∈E d are associated to edges. Let us denote by ν their common law. We refer the reader to the recent review paper on first passage percolation by Damron et al [1]. For each path γ in the graph (Z d , E d ), we define t(γ) = e∈γ t e , and ∀x, y ∈ Z d , t(x, y) = inf

Theorem 3 . 3 .

 33 For each u ∈ R d which is not at the boundary of A p , we have the almost sure convergence:lim n→+∞ t(0, H n (u)) n = b p (u).

Corollary 3 . 4 .

 34 int(Bar(A p )) ⊂ BG(p).Proof. Assume that u ∈ BG(p). Then, θ u (p) > 0. On the event sup x∈C+(0)

•

  we have a k -2N i k-1 , u ≤ N . As (a k , b k ) is an edge, b k -2N i k-1 , u ≤ N + K, where K = max e∈Dir e, u > 0. If i k is of type down, b k -2N i k-1 , u ≤ -10N . • For any k ∈ {0, . . . , ℓ -1}, b k ∈ B N (i k ), thus 2N i k -b k , u ≤ N u 1 ≤ N .As γ is a path from 0 to H n (u), this leads, for any fixed N ≥ K, to n ≤ γ last , u≤ 11N + (N + K)I up (γ) -10N I down (γ) + N (I up (γ) + I down (γ))≤ 11N + 3N (I up (γ) -3I down (γ)).

( 8 )

 8 ℓ ≥ I up (γ) ≥ n 3N -

sometimes called characteristic cone or asymptotic cone

And we also see that 3N (I up (γ) -3I down (γ)) ≥ n -11N ≥ 0 for every n large enough, so 3I down (γ) ≤ I up (γ) and [START_REF] Kesten | Aspects of first passage percolation[END_REF] I up (γ) ≥ 3 4 (I up (γ) + I down (γ)) = 3 4 ℓ.

3. For k ∈ Z 2 , we say that the box B N (k) is good if for each x ∈ B N (k), max sup

and that B N (k) is bad otherwise. As p < min(p c (v), p c (w)), by the first point of Theorem 2.1, there exists α > 0 such that for every n ≥ 1,

y, v ≥ n ≤ e -αn and P p sup

Thus, for every N ≥ 1, P p (B N is bad) ≤ 2(2N + 1) 2 e -α(1-θ)N and lim

Let us also denote by I G up (γ) the number of boxes that belong to the squeleton, whose associated crossing is of type up, and that are also good. Assume that i k is the index of a crossing of type up, and for instance that b

If moreover the box B N (i k ) is good, then sup y∈C+(b k ) y, v < N (1 -θ), and this implies that the portion of the path γ between b k and b k+1 uses at least one edge with passage time 1; and the same is true if the crossing is up because b k+1 -2N i k , w > N . So [START_REF] Thomas | Survival of discrete time growth models, with applications to oriented percolation[END_REF] t(γ) ≥ I G up (γ). From now on, we will denote it as I G up (Γ, ε) the number of good boxes associated to the couple formed by a squeleton and a sequence of up/down status for its crossings.

4. Remember that C is defined in [START_REF] Grimmett | Percolation, volume 321 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF]. We now fix the last parameters: choose α > 0 and ρ ∈ (0, 1) such that

As the states of the boxes are identically distributed and only locally dependant and lim N →+∞ P p (B N is good) = 1, we can use the Liggett-Schonnmann-Stacey coupling result [START_REF] Liggett | Domination by product measures[END_REF]: there exists N large enough such that the field of the states of the boxes (B N (k)) k∈Z 2 stochastically dominates a product of Bernoulli laws with parameter ρ. We then fix κ > 0 small enough to have

Thanks to (8), ( 9) and ( 10), we have

Because of ( 7), for a fixed ℓ ≥ n/4, there are at most (8(C + 1) 2 ) ℓ couples (Γ, ε) with length ℓ. If such a couple satisfies I up (Γ, ε) ≥ 3 4 ℓ, then I G up (Γ, ε) stochastically dominates a variable S with binomial law with parameters (⌈ 3 4 ℓ⌉, ρ), so P p (I G up (Γ, ε) ≤ κn) ≤ P(S ≤ κn) = P(e -αS ≥ e -ακn ) ≤ e ακn E (e -αS ) ≤ e ακn (ρe -α + 1 -ρ) 3 4 ℓ . So we obtain:

) n , which ends the proof.

Corollary 3.6.

Proof. Suppose p < lim x→u p c (x). By Theorem 3.5, there exist c, α > 0 such that for each n ≥ 1, P p (t(0, H n (u)) ≤ cn) ≤ e -αn . Then, with the Borel-Cantelli lemma and Theorem 3.3, we get b p (u) ≥ c.

Corollary 3.7. ∪ q>p int(BG(q)) ⊂ Bar(A p ).

Proof. Consider u ∈ ∪ q>p int(BG(q)): there exists q > p such that u ∈ int(BG(q)), which means that there exists δ > 0, with B(u, δ) ⊂ BG(q). For each x ∈ B(u, δ), we have θ x (q) = 0 and p c (x) ≥ q. This implies that lim x→u p c (x) ≥ q > p. We conclude with Corollary 3.6.