Francis Comets
email: comets@math.univ-paris-diderot.fr

Serguei Popov
email: popov@ime.unicamp.br

Marina Vachkovskaia
email: marinav@ime.unicamp.br

Two-dimensional random interlacements and late points for random walks

Keywords: random interlacements, hitting time, simple random walk, Doob's h-transform AMS 2010 subject classifications: Primary 60K35. Secondary 60G50, 82C41

We define the model of two-dimensional random interlacements using the simple random walk trajectories conditioned on never hitting the origin, and then obtain some properties of this model. Also, for the random walk on a large torus conditioned on not hitting the origin up to some time proportional to the mean cover time, we show that the law of the vacant set around the origin is close to that of random interlacements at the corresponding level. Thus, this new model provides a microscopic description of late points of the covering process.

Introduction

We start by an informal description of our purpose.

Random interlacements in two dimensions

Random interlacements were introduced by Sznitman in [START_REF] Sznitman | Vacant set of random interlacements and percolation[END_REF], motivated by the problem of disconnection of the discrete torus Z d n := Z d /nZ d by the trace of simple random walk, in dimension 3 or higher. Detailed accounts can be found in the survey [START_REF] Černý | From random walk trajectories to random interlacements[END_REF] and the recent books [START_REF] Drewitz | An introduction to random interlacements[END_REF][START_REF] Sznitman | Topics in occupation times and Gaussian free fields[END_REF]. Loosely speaking, the model of random interlacements in Z d , d ≥ 3, is a stationary Poissonian soup of (transient) simple random walk trajectories on the integer lattice. There is an additional parameter u > 0 entering the intensity measure of the Poisson process, the larger u is the more trajectories are thrown in. The sites of Z d that are not touched by the trajectories constitute the vacant set V u . The random interlacements are constructed simultaneously for all u > 0 in such a way that V u 1 ⊂ V u 2 if u 1 > u 2 . In fact, the law of the vacant set at level u can be uniquely characterized by the following identity:

P[A ⊂ V u ] = exp -u cap(A) , (1)
where cap(A) is the capacity of a finite set A ⊂ Z d . Informally, the capacity measures how "big" is the set from the point of view of the walk, see Section 6.5 of [START_REF] Lawler | Random walk: a modern introduction[END_REF] for formal definitions, as well as ( 12)-( 13) below. At first glance, the title of this section seems to be meaningless, just because even a single trajectory of two-dimensional simple random walk a.s. visits all sites of Z 2 , so the vacant set would be always empty. Nevertheless, there is also a natural notion of capacity in two dimensions (cf. Section 6.6 of [START_REF] Lawler | Random walk: a modern introduction[END_REF]), so one may wonder if there is a way to construct a decreasing family (V α , α > 0) of random subsets of Z 2 in such a way that a formula analogous to (1) holds for every finite A. This is, however, clearly not possible since the two-dimensional capacity of one-point sets equals 0. On the other hand, it turns out to be possible to construct such a family so that

P[A ⊂ V α ] = exp -πα cap(A) (2)
holds for all sets containing the origin (the factor π in the exponent is just for convenience, as explained below). We present this construction in Section 2.1.

To build the interlacements, we use the trajectories of simple random walks conditioned on never hitting the origin. Of course, the law of the vacant set is no longer translationally invariant, but we show that it has the property of conditional translation invariance, cf. Theorem 2.3 below. In addition, we will see that (similarly to the d ≥ 3 case) the random object we construct has strong connections to random walks on two-dimensional torus. All this makes us believe that "two-dimensional random interlacements" is the right term for the object we introduce in this paper.

1.2 Cover time and late points of simple random walk on a discrete torus

Consider the simple random walk on the two-dimensional discrete torus Z 2 n with the starting point chosen uniformly at random. Let T n be the first moment when this random walk visits all sites of Z 2 n ; we refer to T n as the cover time of the torus. It was shown in [START_REF] Dembo | Cover times for Brownian motion and random walks in two dimensions[END_REF] that Tn n 2 ln 2 n → 4 π in probability; later, this result was refined in [START_REF] Ding | On cover times for 2D lattices[END_REF], and then even finer results on the first correction to this limit were obtained in [START_REF] Belius | The subleading order of two dimensional cover times[END_REF] for the similar problem of covering the (continuous) torus with a Brownian sausage.

The structure of the set of late points (i.e., the set of points that are still unvisited up to a given time) of the random walk on the torus is rather well understood in dimensions d ≥ 3, see [START_REF] Belius | Gumbel fluctuations for cover times in the discrete torus[END_REF][START_REF] Miller | Uniformity of the late points of random walk on Z d n for d ≥ 3[END_REF], and also in the continuous case [START_REF] Goodman | Extremal geometry of a Brownian porous medium[END_REF]. On the other hand, much remains to be discovered in two dimensions. In [START_REF] Dembo | Late points for random walks in two dimensions[END_REF] it was shown that this set has interesting fractal-like properties when the elapsed time is a fraction of the expected cover time. This particular behavior is induced by long distance correlations between hitting times due to recurrence. In this paper, we prove that the law of the uncovered set around the origin at time 4α π n 2 ln 2 n conditioned on the event that the origin is uncovered, is close to the law of two-dimensional random interlacements at level α. We hope that this result would lead to other advances in understanding the structure of the uncovered set.

As a side note, observe that the two-dimensional random interlacements relate to the simple random walk on the torus at a time proportional to the cover time. In higher dimensions, one starts to observe the "interlacement regime" already at times below the cover time by a factor of ln n.

Organisation of the paper: In Section 2.1 we construct the model of random interlacements and present some of its properties. In Section 2.2 we formulate a result relating this model and the vacant set of the simple random walk on the discrete torus. We prove some results on the spotwhen short arguments are available -, postponing the proof of the other ones to Section 4. Section 3 contains a number of auxiliary facts needed for the proof of the main results.

Definitions and results

We start by defining the two-dimensional random interlacement process, which involves some potential theoretic considerations.

Random interlacements: definitions, properties

Let • be the Euclidean norm. Define the (discrete) ball B(x, r) = {y ∈ Z 2 : yx ≤ r} (note that x and r need not be necessarily integer), and abbreviate B(r) := B(0, r). We write x ∼ y if x and y are neighbours on Z 2 . The (internal) boundary of A ⊂ Z 2 is defined by

∂A = {x ∈ A : there exists y ∈ Z 2 \ A such that x ∼ y}.
Let (S n , n ≥ 0) be two-dimensional simple random walk. Write P x for the law of the walk started from x and E x for the corresponding expectation. Let

τ 0 (A) = inf{k ≥ 0 : S k ∈ A}, (3)
τ 1 (A) = inf{k ≥ 1 : S k ∈ A} (4)
be the entrance and the hitting time of the set A by simple random walk S.

Note that inf ∅ = +∞. For a singleton A = {x}, we will shortly denote τ i (A) = τ i (x), i = 0, 1. Define the potential kernel a by

a(x) = ∞ k=0 P 0 [S k = 0] -P x [S k = 0] . (5)
It can be shown that the above series indeed converges and we have a(0) = 0, a(x) > 0 for x = 0, and

a(x) = 2 π ln x + γ + O( x -2 ) (6)
as x → ∞, cf. Theorem 4.4.4 of [START_REF] Lawler | Random walk: a modern introduction[END_REF] (the value of γ is known1 , but we will not need it in this paper). Also, the function a is harmonic outside the origin, i.e., 1 4 y:y∼x a(y) = a(x) for all x = 0.

Observe that [START_REF] Ding | On cover times for 2D lattices[END_REF] immediately implies that a(S k∧τ 0 (0) ) is a martingale, we will repeatedly use this fact in the sequel. With some abuse of notation, we also consider the function a(r) = 2 π ln r + γ of a real argument r ≥ 1. The advantage of using this notation is e.g. that, due to (6), we may write, as r → ∞,

y∈∂B(x,r) ν(y)a(y) = a(r) + O( x /r) (8)
for any probability measure ν on ∂B(x, r). The harmonic measure of a finite A ⊂ Z 2 is the entrance law "starting at infinity",

hm A (x) = lim y →∞ P y [S τ 1 (A) = x]. (9)
By recurrence of the walk, hm A is a probability measure on ∂A. The existence of the above limit follows from Proposition 6.6.1 of [START_REF] Lawler | Random walk: a modern introduction[END_REF]; also, this proposition together with (6.44) implies that

hm A (x) = 2 π lim R→∞ P x τ 1 (A) > τ 1 ∂B(R) ln R. (10)
Intuitively, the harmonic measure at x ∈ ∂A is proportional to the probability of escaping from x to a large sphere. Now, for a finite set A containing the origin, we define its capacity by

cap(A) = x∈A a(x) hm A (x); (11)
in particular, cap {0} = 0 since a(0) = 0. For a set not containing the origin, its capacity is defined as the capacity of a translate of this set that does contain the origin. Indeed, it can be shown that the capacity does not depend on the choice of the translation. A number of alternative definitions is available, cf. Section 6.6 of [START_REF] Lawler | Random walk: a modern introduction[END_REF]. Also, observe that, by symmetry, the harmonic measure of any two-point set is uniform, so cap {x, y} = 1 2 a(y-x) for any x, y ∈ Z 2 .

Let us define another random walk ( S n , n ≥ 0) on Z 2 (in fact, on Z 2 \{0}) in the following way: the transition probability from x to y equals a(y) 4a(x) for all x ∼ y (this definition does not make sense for x = 0, but this is not a problem since the walk S can never enter the origin anyway). The reader will promptly recognise S as the Doob's h-transform of the simple random walk, under condition of not hitting the origin. Note that [START_REF] Ding | On cover times for 2D lattices[END_REF] implies that the random walk S is indeed well defined, and, clearly, it is an irreducible Markov chain on Z 2 \ {0}. We denote by P x , E x the probability and expectation for the random walk S started from x = 0. Then, it is straightforward to observe that

• the walk S is reversible, with the reversible measure µ x := a 2 (x);

• in fact, it can be represented as a random walk on the two-dimensional lattice with conductances (or weights) a(x)a(y), x, y ∈ Z 2 , x ∼ y ;

• a(x), x ∈ Z 2 \ {0} is an excessive measure for S (i.e., for all y = 0,

x a(x) P x ( S 1 = y) ≤ a(y)), with equality failing at the four neighbours of the origin. Therefore, by e.g. Theorem 1.9 of Chapter 3 of [START_REF] Revuz | Markov chains[END_REF], the random walk S is transient;

• an alternative argument for proving transience is the following: let N be the set of the four neighbours of the origin. Then, a direct calculation shows that 1/a( S k∧ τ 0 (N ) ) is a martingale. The transience then follows from Theorem 2.2.2 of [START_REF] Fayolle | Topics in the Constructive Theory of Countable Markov Chains[END_REF].

Let τ 0 , τ 1 be defined as in (3)-( 4), but with S on the place of S. Our next definitions are appropriate for the transient case. For a finite A ⊂ Z 2 , we define the equilibrium measure

e A (x) = 1{x ∈ A} P x [ τ 1 (A) = ∞]µ x , (12)
and the capacity (with respect to S)

cap(A) = x∈A e A (x). ( 13
)
Observe that, since µ 0 = 0, it holds that cap(A) = cap(A ∪ {0}) for any set A ⊂ Z 2 . Now, we use the general construction of random interlacements on a transient weighted graph introduced in [START_REF] Teixeira | Interlacement percolation on transient weighted graphs[END_REF]. In the following few lines we briefly summarize this construction. Let W be the space of all doubly infinite nearest-neighbour transient trajectories in Z 2 , W = = ( k ) k∈Z : the set {m : m = y} is finite for all y ∈ Z 2 .

We say that and are equivalent if they coincide after a time shift, i.e., ∼ when there exists k such that m+k = m for all m. Then, let W * = W/ ∼ be the space of trajectories modulo time shift, and define χ * to be the canonical projection from W to W * . For a finite A ⊂ Z 2 , let W A be the set of trajectories in W that intersect A, and we write W * A for the image of W A under χ * . One then constructs the random interlacements as Poisson point process on W * × R + with the intensity measure ν ⊗ du, where ν is described in the following way. It is the unique sigma-finite measure on W * such that for every finite A

1 W * A • ν = χ * • Q A ,
where the finite measure Q A on W A is determined by the following equality:

Q A ( k ) k≥1 ∈ F, 0 = x, ( -k ) k≥1 ∈ G = e A (x) • P x [F ] • P x [G | τ 1 (A) = ∞].
The existence and uniqueness of ν was shown in Theorem 2.1 of [START_REF] Teixeira | Interlacement percolation on transient weighted graphs[END_REF]. Definition 2.1. For a configuration λ δ (w * λ ,u λ ) of the above Poisson process, the process of random interlacements at level α (which will be referred to as RI(α)) is defined as the set of trajectories with label less than or equal to πα, i.e.,

λ:u λ ≤πα δ w * λ .
Observe that this definition is a bit unconventional (we used πα instead of just α, as one would normally do), but we will see below that it is quite reasonable in two dimensions, since the formulas become generally cleaner.

It is important to have in mind the following "constructive" description of random interlacements at level α "observed" on a finite set A ⊂ Z 2 . Namely,

• take Poisson(πα cap(A)) number of particles;

• place these particles on the boundary of A independently, with distribution e A = ( cap A) -1 e A (x), x ∈ A ;

• let the particles perform independent S-random walks (since S is transient, each walk only leaves a finite trace on A).

It is also worth mentioning that the FKG inequality holds for random interlacements, cf. Theorem 3.1 of [START_REF] Teixeira | Interlacement percolation on transient weighted graphs[END_REF].

The vacant set at level α,

V α = Z 2 \ λ:u λ ≤πα ω * λ (Z),
is the set of lattice points uncovered by the random interlacement. It contains the origin by definition. In Figure 1 we present a simulation of the vacant set for different values of the parameter. As a last step, we need to show that we have indeed constructed the object for which (2) is verified. For this, we need to prove the following fact: Proposition 2.2. For any finite set A ⊂ Z 2 such that 0 ∈ A it holds that cap(A) = cap(A).

Proof. Indeed, consider an arbitrary x ∈ ∂A, x = 0, and (large) r such that A ⊂ B(r -2). Write using (6)

P x τ 1 (A) > τ 1 ∂B(r) = a( end ) a(x) 1 4 | | = 1 + o(1) 2 π ln r a(x) 1 4 |
| = 1 + o(1) 2 π ln r a(x) P x τ 1 (A) > τ 1 ∂B(r) ,
where the sums are taken over all trajectories that start at x, end at ∂B(r), and avoid A ∪ ∂B(r) in between; end ∈ ∂B(r) stands for the ending point of the trajectory, and | | is the trajectory's length. Now, we send r to infinity and use [START_REF] Goodman | Extremal geometry of a Brownian porous medium[END_REF]

to obtain that, if 0 ∈ A, a(x) P x [ τ 1 (A) = ∞] = hm A (x). ( 14
)
Multiplying by a(x) and taking summation in x ∈ A (recall that µ x = a 2 (x)) we obtain the expressions in ( 11) and ( 13) and thus conclude the proof. For α = 1.5 the only vacant site is the origin. Also, note that the sets are the same for α = 1 and α = 1.25; this is not surprising since just a few new walks enter the picture when increasing the rate by a small amount.

Together with formula (1.1) of [START_REF] Teixeira | Interlacement percolation on transient weighted graphs[END_REF], Proposition 2.2 shows the fundamental relation [START_REF] Belius | The subleading order of two dimensional cover times[END_REF] announced in introduction: for all finite subsets A of Z 2 ,

P[A ⊂ V α ] = exp -πα cap(A ∪ {0}) .
As mentioned before, the law of two-dimensional random interlacements is not translationally invariant, although it is of course invariant with respect to reflections/rotations of Z 2 that preserve the origin. Let us describe some other basic properties of two-dimensional random interlacements:

Theorem 2.3. (i) For any α > 0, x ∈ Z 2 , A ⊂ Z 2 , it holds that P[A ⊂ V α | x ∈ V α ] = P[-A + x ⊂ V α | x ∈ V α ]. ( 15
)
More generally, for all α > 0, x ∈ Z 2 \{0}, A ⊂ Z 2 , and any orthogonal transformation M preserving the lattice and exchanging 0 and x, we have

P[A ⊂ V α | x ∈ V α ] = P[M A ⊂ V α | x ∈ V α ]. (16)
(ii) With γ from ( 6) we have

P[x ∈ V α ] = exp -πα a(x) 2 = e -γ πα/2 x -α 1 + O( x -2 ) . ( 17
)
(iii) For A such that 0 ∈ A ⊂ B(r) we have

P[A ⊂ V α | x ∈ V α ] = exp - πα 4 cap(A) 1 + O r ln r ln x x 1 -cap(A) 2a(x) + O r ln r x . (18)
(iv) For x, y = 0, x = y, we have P {x, y} ⊂ V α = exp -πα cap({0, x, y}) , where the expression for cap({0, x, y}) is given in Lemma 3.9 below. Moreover, as s := x → ∞, ln y ∼ ln s and ln xy ∼ β ln s with some β ∈ [0, 1], we have

P {x, y} ⊂ V α = s -4α 4-β +o(1) . (19)
(v) Assume that ln x ∼ ln s, ln r ∼ β ln s with β < 1. Then, as s → ∞,

P B(x, r) ⊂ V α = s -2α 2-β +o(1) . ( 20
) A 1 A 2 x 0 s 2 s α 1 ≈ 1 4 α α 2 ≈ 2 7 α
Figure 2: How the "local rate" looks like if we condition in the event that a "distant" site is vacant.

These results invite a few comments.

Remark 2.4.

1. The statement in (i) describes an invariance property given that a point is vacant. We refer to it as the conditional stationarity of two-dimensional random interlacements.

2. We can interpret (iii) as follows: the conditional law of RI(α) given that a distant site x is vacant, is similar -near the origin -to the unconditional law of RI(α/4). Combined with (i), the similarity holds near x as well. Moreover, one can also estimate the "local rate" away from the origin, see Figure 2. More specifically, observe from Lemma 3.10 (ii)

that cap(A 2 ) ln s with s = dist(0, A 2 ) large implies cap {0} ∪ A 2 = a(s) 2 (1 + o(1)
). If x is at a much larger distance, say ln x ∼ ln(s 2 ), then (18) reveals a "local rate" equal to 2 7 α, that is,

P[A 2 ⊂ V α | x ∈ V α ] = exp -2 7 πα cap {0} ∪ A 2 (1 + o(1)
) . 3. By symmetry, the conclusion of (iv) remains the same in the situation when ln x , ln xy ∼ ln s and ln y ∼ ln(s β ).

Proof of (i) and (ii). To prove (i), observe that

cap {0, x} ∪ A = cap {0, x} ∪ (-A + x)
by symmetry. For the second statement in (i), note that, for A = {0, x}∪A, it holds that cap A = cap M A = cap {0, x} ∪ M A . Item (ii) follows from the above mentioned fact that cap {0, x} = 1 2 a(x) together with [START_REF] Dembo | Late points for random walks in two dimensions[END_REF].

We postpone the proof of other parts of Theorem 2.3, since it requires some estimates for capacities of different kind of sets. We now turn estimates on the cardinality of the vacant set.

Theorem 2.5. (i) We have

E |V α ∩ B(r)| ∼      2π 2-α e -γ πα/2 × r 2-α , for α < 2, 2πe -γ πα/2 × ln r, for α = 2, const, for α > 2.
(ii) For α > 1 it holds that V α is finite a.s. Moreover,

P V α = {0} > 0 and P V α = {0} → 1 as α → ∞. (iii) For α ∈ (0, 1), we have |V α | = ∞ a.s. Moreover, P V α ∩ B(r) \ B(r/2) = ∅ ≤ r -2(1-√ α) 2 +o(1) . (21)
Proof of (i) and (ii). Part (i) immediately follows from Theorem 2.3 (ii).

The proof of the part (ii) is easy in the case α > 2. Indeed, observe first that E|V α | < ∞ implies that V α itself is a.s. finite. Also, Theorem 2.3 (ii) actually implies that E|V α \ {0}| → 0 as α → ∞, so P V α = {0} → 1 by Chebyshev inequality. Now, let us prove that, in general, P |V α | < ∞ = 1 implies that P V α = {0} > 0. Indeed, if V α is a.s. finite, then one can find a sufficiently large R such that

P |V α ∩ (Z 2 \ B(R))| = 0 > 0. Since P[x / ∈ V α ] > 0 for any x = 0, the claim that P V α = {0} > 0 follows from the FKG inequality applied to events {x / ∈ V α }, x ∈ B(R) together with |V α ∩ (Z 2 \ B(R))| = 0 .
As before, we postpone the proof of part (iii) and the rest of part (ii) of Theorem 2.5. Let us remark that we believe that the right-hand side of (21) gives the correct order of decay of the above probability; we, however, do not have a rigorous argument at the moment. Also, note that the question whether V 1 is a.s. finite or not, is open. For now, the authors do not have even heuristic arguments in favor of either alternative.

We do have, however, a heuristic explanation about the unusual behaviour of the model for α ∈ (1, 2): in this non-trivial interval, the vacant set is a.s. finite but its expected size is infinite. The reason for that is the following: the number of S-walks that hit B(r) has Poisson law with rate of order ln r. Thus, decreasing this number by a constant factor (with respect to the expectation) has only a polynomial cost. On the other hand, by doing so, we increase the probability that a site x ∈ B(r) is vacant for all x ∈ B(r) at once, which increases the expected size of V α ∩ B(r) by a polynomial factor. It turns out that this effect causes the actual number of uncovered sites in B(r) to be typically of much smaller order then the expected number of uncovered sites there.

Simple random walk on a discrete torus and its relationship with random interlacements

Now, we state our results for the random walk on torus. Let (X k , k ≥ 0) be the simple random walk on Z 2 n with X 0 chosen uniformly at random. Define the entrance time to the site x ∈ Z 2 n by

T n (x) = inf{t ≥ 0 : X t = x}, (22)
and the cover time of the torus by

T n = max x∈Z 2 n T n (x). (23)
Let us also define the uncovered set at time t,

U (n) t = {x ∈ Z 2 n : T n (x) > t}. (24)
Denote by Υ n : Z 2 → Z 2 n , Υ n (x, y) = (x mod n, y mod n), the natural projection modulo n. Then we can write X k = Υ(S k ). Consistently, we will use the same notation for (discrete Euclidean) balls on Z 2 n : B(y, r) ⊂ Z 2 n is defined by B(y, r) = Υ n B(z, r), where z ∈ Z 2 is such that Υ n z = y. Let also

t α := 4α π n 2 ln 2 n.
In the following theorem, we prove that, given that 0 is uncovered, the law of the uncovered set around 0 at time t α is close to that of RI(α):

Theorem 2.6. Let α > 0 and A is a finite subset of Z 2 . We have The proof of this theorem will be presented in Section 4. However, at this point we give a heuristic argument for (25). Let us consider the excursions of the random walk X between ∂B n 3 ln n and ∂B(n/3) up to time t α . We hope that Figure 3 is self-explanatory; formal definitions are presented in Section 3.4. Let N α be the number of these excursions. It is possible to prove that this (random) number is concentrated around 2α ln 2 n ln ln n , with deviation probabilities of subpolynomial order, see Lemma 3.12 below. The result we just mentioned is for unconditional probabilities, but, since the probability of the event {0 ∈ U (n) tα } is only polynomially small (actually, it is n -2α+o (1) ), the same holds for the deviation probabilities conditioned on this event. So, let us just assume for now that the number of the excursions is exactly 2α ln 2 n ln ln n , and see where will it lead us.

lim n→∞ P[Υ n A ⊂ U (n) tα | 0 ∈ U (n) tα ] = exp -πα cap(A ∪ {0}) . ( 25
) A X 0 X tα Z 2 n 0 ∂B n 3 ∂B n 3 ln n
Assume without restriction of generality that 0 ∈ A. Then, Lemmas 3.1 and 3.3 imply that

• the probability that an excursion hits the origin is roughly ln ln n ln(n/3) ; • provided that cap(A) ln n, the probability that an excursion hits the set A is roughly ln ln n ln(n/3) 1 + π cap(A) 2 ln(n/3) . So, the conditional probability p * that an excursion does not hit A given that it does not hit the origin is

p * ≈ 1 -ln ln n ln(n/3) 1 + π cap(A)
2 ln(n/3)

1 -ln ln n ln(n/3) ≈ 1 - π ln ln n 2 ln 2 n cap(A),
and then we obtain

P[Υ n A ⊂ U (n) tα | 0 ∈ U (n) tα ] ≈ p Nα * ≈ 1 - π ln ln n 2 ln 2 n cap(A) 2α ln 2 n ln ln n ≈ exp -πα cap(A) ,
which agrees with the statement of Theorem 2.6. However, turning the above heuristics to a rigorous proof is not an easy task. The reason for this is that, although N α is indeed concentrated around 2α ln 2 n ln ln n , it is not concentrated enough: the probability that 0 is not hit during k excursions, where k varies over the "typical" values of N α , changes too much. Therefore, in the proof of Theorem 2.6 we take a different route by considering the suitable h-transform of the walk, as explained in Section 4.

Some auxiliary facts and estimates

In this section we collect lemmas of all sorts that will be needed in the sequel.

Simple random walk in Z 2

First, we recall a couple of basic facts for the exit probabilities of simple random walk. Lemma 3.1. For all x, y ∈ Z 2 and R > 0 with x ∈ B(y, R), y ≤ R -2, we have

P x τ 1 (0) > τ 1 ∂B(y, R) = a(x) a(R) + O(R -1 y ) , (26)
and for all y ∈ B(r), x ∈ B(y, R) \ B(r) with r + y ≤ R -2, we have

P x τ 1 (∂B(r)) > τ 1 ∂B(y, R) = a(x) -a(r) + O(r -1 ) a(R) -a(r) + O(R -1 y + r -1 ) , (27)
as r, R → ∞.

Remark 3.2. Observe that (26) reduces to (27) with r = 0 provided that the terms a(r) and O(r -1 ) are taken equal to 0.

Proof. Both (26) and ( 27) are easily deduced from the following argument: recall that the sequence a(S k∧τ 0 (0) ), k ≥ 0, is a martingale, and apply the Optional Stopping Theorem together with ( 6) and [START_REF] Drewitz | An introduction to random interlacements[END_REF]. For the second statement, with τ = τ 1 (∂B(r)) ∧ τ 1 ∂B(y, R) and q = P x τ 1 (∂B(r)) > τ 1 ∂B(y, R) , we write

a(x) = E x a(S τ ); τ = τ 1 (∂B(y, R)) + E x a(S τ ); τ = τ 1 (∂B(r)) = (1 -q) a(r) + O(r -1 ) + q a(R) + O(R -1 y ) , yielding (27)
. The first statement has a similar proof.

We have an estimate for more general sets.

Lemma 3.3. Let A be a finite subset of Z 2 such that A ⊂ B(r). We have for r

+ 1 ≤ x ≤ R -2, x + y ≤ R -1 P x τ 1 (A) > τ 1 ∂B(y, R) = a(x) -cap(A) + O r ln r ln x x a(R) -cap(A) + O R -1 y + r ln r ln x x . (28)
Proof. First, observe that, for u ∈ A,

P x S τ 1 (A) = u = hm A (u) 1 + O r ln x x
, see e.g. Theorem 2.1.3. in [START_REF] Lawler | Intersections of random walks[END_REF]. Then, we can write

P x S τ 1 (A) = u, τ 1 (A) < τ 1 ∂B(y, R) = P x S τ 1 (A) = u -P x S τ 1 (A) = u, τ 1 (A) > τ 1 ∂B(y, R) = hm A (u) 1 + O r ln x x -P x τ 1 (A) > τ 1 ∂B(y, R) × z∈∂B(y,R) P z S τ 1 (A) = u P x S τ 1 (∂B(y,R)) = z | τ 1 (A) > τ 1 ∂B(y, R) = hm A (u) 1 + O r ln x x -P x τ 1 (A) > τ 1 ∂B(y, R) hm A (u) 1 + O r ln R R = hm A (u)P x τ 1 (A) < τ 1 ∂B(y, R) 1 + O r ln x
x , using twice the above observation and also that B( x ) ⊂ B(y, R), yielding

P x S τ 1 (A) = u | τ 1 (A) < τ 1 ∂B(y, R) = hm A (u) 1 + O r ln x x . (29)
Abbreviating q := P x τ 1 (A) > τ 1 ∂B(y, R) , we have by the Optional Stopping Theorem and ( 29)

a(x) = qa(R) + O(R -1 y ) + (1 -q) u∈A\{0} a(u) hm A (u) 1 + O r ln x x = qa(R) + O(R -1 y ) + (1 -q) 1 + O r ln x x cap(A),
and (28) follows (observe also that cap(A) ≤ cap B(r) = 2 π ln r +O(1)).

Simple random walk conditioned on not hitting the origin

Next, we relate the probabilities of certain events for the walks S and S.

For M ⊂ Z 2 , let Γ (x)
M be the set of all nearest-neighbour finite trajectories that start at x ∈ M \ {0} and end when entering ∂M for the first time; denote also Γ

(x) y,R = Γ (x) B(y,R) . For A ⊂ Γ (x)
M write S ∈ A if there exists k such that (S 0 , . . . , S k ) ∈ A (and the same for the conditional walk S). In the next result we show that

P x [ • | τ 1 (0) > τ 1 ∂B(R) ] and P x [ • ] are almost indistinguishable on Γ (x)
0,R (that is, the conditional law of S almost coincides with the unconditional law of S). A similar result holds for excursions on a "distant" (from the origin) set.

Lemma 3.4. (i) Assume A ⊂ Γ (x) 0,R . We have P x S ∈ A | τ 1 (0) > τ 1 ∂B(R) = P x S ∈ A 1 + O((R ln R) -1 ) . ( 30
) (ii) Assume that A ⊂ Γ (x)
M and suppose that 0 / ∈ M , and denote s = dist(0, M ), r = diam(M ). Then, for x ∈ M ,

P x [S ∈ A] = P x [ S ∈ A] 1 + O r s ln s . ( 31
)
Proof. Let us prove part (i). Assume without restricting generality that no trajectory from A passes through the origin. Then, it holds that

P x [ S ∈ A] = ∈A a( end ) a(x) 1 4 | | ,
with |ρ| the length of ρ. On the other hand, by (26)

P x [S ∈ A | τ 1 (0) > τ 1 ∂B(R) ] = a(R) + O(R -1 ) a(x) ∈A 1 4 | |
.

Since end ∈ ∂B(R), we have a( end ) = a(R) + O(R -1 ), and so (30) follows.

The proof of part (ii) is analogous (observe that a(y 1 )/a(y 2 ) = 1+O r s ln s for any y 1 , y 2 ∈ M ).

As observed in Section 1.1, the random walk S is transient. Next, we estimate the probability that the S-walk avoids a ball centered at the origin: Lemma 3.5. Assume r ≥ 1 and x ≥ r + 1. We have

P x τ 1 B(r) = ∞ = 1 - a(r) a( x ) 1 + O(r -1 ) .
Proof. By (26) and Lemma 3.4 (i) we have

P x τ 1 B(r) = ∞ = lim R→∞ P x τ 1 (∂B(r)) > τ 1 ∂B(R) | τ 1 (0) > τ 1 ∂B(R) .
The claim then follows from ( 26)-( 27).

Remark 3.6. Alternatively, one can deduce the proof of Lemma 3.5 from the fact that 1/a( S k∧ τ 0 (N ) ) is a martingale, together with the Optional Stopping Theorem.

We will need also an expression for the probability of avoiding any finite set containing the origin: Lemma 3.7. Assume that 0 ∈ A ⊂ B(r), and x ≥ r + 1. Then

P x [ τ 1 (A) = ∞] = 1 - cap(A) a(x) + O r ln r ln x x . (32)
Proof. Indeed, using Lemmas 3.3 and 3.4 (i) together with (26), we write

P x [ τ 1 (A) = ∞] = lim R→∞ P x τ 1 (A) > τ 1 ∂B(R) | τ 1 (0) > τ 1 ∂B(R) = lim R→∞ a(R) + O(R -1 ) a(x) × a(x) -cap(A) + O r ln r ln x x a(R) -cap(A) + O R -1 + r ln r ln x x ,
thus obtaining (32).

It is also possible to obtain the exact expressions for one-site escape probabilities, and probabilities of (not) hitting a given site:

P x [ τ 1 (y) < ∞] = a(x) + a(y) -a(x -y) 2a(x) , (33)
for x = y, x, y = 0 and

P x [ τ 1 (x) < ∞] = 1 - 1 2a(x) (34)
for x = 0. In particular, we recover from (34) the transience of S. Also, observe that (33) implies the following surprising fact: for any x = 0,

lim y→∞ P x [ τ 1 (y) < ∞] = 1 2 .
The above relation leads to the following heuristic explanation for Theorem 2.3 (iii). Since the probability of hitting a distant site is about 1/2, by conditioning that this distant site is vacant, we kind of throw away three quarters of the trajectories that pass through a neighbourhood of the origin: indeed the double-infinite trajectory has to avoid this distant site two times, before and after reaching that neighborhood. We temporarily postpone the proof of ( 33)-( 34). Let us first state a couple of other general estimates, for the probability of (not) hitting a given set (which is, typically, far away from the origin), or, more specifically, a disk: Lemma 3.8. Assume that x / ∈ B(y, r) and y > 2r ≥ 1. Abbreviate also Ψ 1 = y -1 r, Ψ 2 = r ln r ln y y , Ψ 3 = r ln r ln x-y x-y + ln y y .

(i) We have

P x τ 1 (B(y, r)) < ∞ = a(y) + O(Ψ 1 ) a(y) + a(x) -a(x -y) + O(r -1 ) a(x) 2a(y) -a(r) + O(r -1 + Ψ 1 ) . (35)
(ii) Consider now any nonempty set A ⊂ B(y, r). Then, it holds that

P x τ 1 (A) < ∞ = a(y) + O(Ψ 1 ) a(y) + a(x) -a(x -y) + O(r -1 + Ψ 3 ) a(x) 2a(y) -cap(A) + O(Ψ 2 ) . (36)
Observe that (35) is not a particular case of (36); this is because (27) typically provides a more precise estimate than (28). Proof. Fix a (large) R > 0, such that R > max{ x , s + r} + 1. Denote

h 1 = P x τ 1 (0) < τ 1 ∂B(R) , h 2 = P x τ 1 B(y, r) < τ 1 ∂B(R) , p 1 = P x τ 1 (0) < τ 1 ∂B(R) ∧ τ 1 (B(y, r)) , p 2 = P x τ 1 B(y, r) < τ 1 ∂B(R) ∧ τ 1 (0) , q 12 = P 0 τ 1 B(y, r) < τ 1 ∂B(R) , q 21 = P ν τ 1 (0) < τ 1 ∂B(R) ,
where ν is the entrance measure to B(y, r) starting from x conditioned on the event τ 1 B(y, r) < τ 1 ∂B(R) ∧ τ 1 (0) , see Figure 4. Using Lemma 3.1, we obtain

h 1 = 1 - a(x) a(R) + O(R -1 ) , (37)
h 2 = 1 - a(x -y) -a(r) + O(r -1 ) a(R) -a(r) + O(R -1 y -x + r -1 ) , (38)
and

q 12 = 1 - a(y) -a(r) + O(r -1 ) a(R) -a(r) + O(R -1 y + r -1 ) , ( 39
)
q 21 = 1 - a(y) + O( y -1 r) a(R) + O(R -1 y ) . ( 40
)
Then, as a general fact, it holds that

h 1 = p 1 + p 2 q 21 , h 2 = p 2 + p 1 q 12 .
Solving this system with respect to p 1 , p 2 , we obtain

p 1 = h 1 -h 2 q 21 1 -q 12 q 21 , (41)
p 2 = h 2 -h 1 q 12 1 -q 12 q 21 , (42)
and so, using (37)-( 40), we write

P x τ 1 (B(y, r)) < τ 1 ∂B(R) | τ 1 (0) > τ 1 ∂B(R) = p 2 (1 -q 21 ) 1 -h 1 = (h 2 -h 1 q 12 )(1 -q 21 ) (1 -h 1 )(1 -q 12 q 21 ) = a(x) a(R) + O(R -1 ) + a(y) -a(r) + O(r -1 ) a(R) -a(r) + O(R -1 y + r -1 ) - a(x -y) -a(r) + O(r -1 ) a(R) -a(r) + O(R -1 x -y + r -1 ) + O ln x ln y ln 2 R × a(y) + O( y -1 r) a(R) + O(R -1 y ) × a(x) a(R) + O(R -1 ) -1 × a(y) -a(r) + O(r -1 ) a(R) -a(r) + O(R -1 y + r -1 ) + a(y) + O( y -1 r) a(R) + O(R -1 y ) + O ln 2 y ln 2 R -1
.

Sending R to infinity, we obtain the proof of (35).

To prove (36), we use the same procedure, with h 1 = h 1 , q 21 expressed in the same way as q 21 (although they are not necessarily equal, the difference takes place in the error terms O(•)) and, by Lemma 3.3,

h 2 = 1 - a(x -y) -cap(A) + O r ln r ln x-y x-y a(R) -cap(A) + O R -1 x -y + r ln r ln x-y x-y , q 12 = 1 - a(y) -cap(A) + O r ln r ln y y a(R) -cap(A) + O R -1 y + r ln r ln y y .
After the analogous calculations, we obtain (36).

Proof of relations (33)-(34). Formula (34) rephrases ( 14) with A = {0, x}. Identity (33) follows from the same proof as in Lemma 3.8 (i), taking r = 0 and using Remark 3.2.

Harmonic measure and capacities

Next, we need a formula for calculating the capacity of three-point sets:

Lemma 3.9. Let x 1 , x 2 , x 3 ∈ Z 2 , and abbreviate

v 1 = x 2 -x 1 , v 2 = x 3 -x 2 , v 3 = x 1 -x 3 .
Then, the capacity of the set A = {x 1 , x 2 , x 3 } is given by the formula

a(v 1 )a(v 2 )a(v 3 ) a(v 1 )a(v 2 ) + a(v 1 )a(v 3 ) + a(v 2 )a(v 3 ) -1 2 a 2 (v 1 ) + a 2 (v 2 ) + a 2 (v 3 ) . ( 43
)
Proof. By Proposition 6.6.3 and Lemma 6.6.4 of [START_REF] Lawler | Random walk: a modern introduction[END_REF], the inverse capacity of A is equal to the sum of entries of the matrix

a -1 A =   0 a(v 1 ) a(v 3 ) a(v 1 ) 0 a(v 2 ) a(v 3 ) a(v 2 ) 0   -1 = 1 2    -a(v 2 ) a(v 1 )a(v 3 ) 1 a(v 1 ) 1 a(v 3 ) 1 a(v 1 ) -a(v 3 ) a(v 1 )a(v 2 ) 1 a(v 2 ) 1 a(v 3 ) 1 a(v 2 ) -a(v 1 ) a(v 2 )a(v 3 )    ,
and this implies (43).

Before proceeding, let us notice the following immediate consequence of Lemma 3.7: for any finite A ⊂ Z 2 such that 0 ∈ A, we have

cap(A) = lim x →∞ a(x) P x [τ 1 (A) < ∞]. (44)
Next, we need estimates for the S-capacity of a "distant" set, and, in particular of a ball which does not contain the origin. Recall the notations Ψ 1,2,3 from Lemma 3.8. Lemma 3.10. Assume that y > 2r ≥ 1.

(i) We have cap {0} ∪ B(y, r) = a(y) + O(Ψ 1 ) a(y) + O(r -1 ) 2a(y) -a(r) + O(r -1 + Ψ 1 ) . ( 45
)
(ii) Suppose that A ⊂ B(y, r). Then

cap {0} ∪ A = a(y) + O(Ψ 1 ) a(y) + O(r -1 + Ψ 2 ) 2a(y) -cap(A) + O(Ψ 2 ) . ( 46
)
Proof. This immediately follows from (44) and Lemma 3.8 (observe that a(x)a(xy) → 0 as x → ∞ and Ψ 3 becomes Ψ 2 ).

We also need to compare the harmonic measure on a set (distant from the origin) to the entrance measure of the S-walk started far away from that set.

Lemma 3.11. Assume that A is a finite subset of Z 2 , 0 / ∈ A, x = 0, and also that 2 diam(A) < dist(x, A) < 1 4 dist(0, A). Abbreviate u = diam(A), s = dist(x, A). Then, for y ∈ A, it holds that

P x S τ 1 (A) = y | τ 1 (A) < ∞ = hm A (y) 1 + O u ln s s . ( 47
)
Proof. Let z 0 ∈ A be such that z 0x = s. Define the discrete circle L = ∂B(z 0 , s); observe that x ∈ L and dist(z , A) ≥ s/2 for all z ∈ L. Let

σ = sup 0 ≤ k ≤ τ 1 (A) : S k ∈ L
be the last moment before τ 1 (A) when the trajectory passes through L. Note also that for all z ∈ L

P z S τ 1 (A) = y | τ 1 (A) < τ 1 (L) = hm A (y) 1 + O u ln s s ; ( 48
)
the proof of this is actually the same as the proof of (29).

Using the Markov property of S, we write

P x τ 1 (A) < ∞, S τ 1 (A) = y = k≥0,z∈L P x τ 1 (A) < ∞, σ = k, S σ = z, S τ 1 (A) = y = k≥0,z∈L P x S k = z, S / ∈ A for all ≤ k × P z τ 1 (A) < ∞, S τ 1 (A) = y, S / ∈ L for all ≤ τ 1 (A) . ( 49
)
Now, observe that the last term in (49) only involves trajectories that lie in B(z 0 , s), and we have dist 0, B(z 0 , s) ≥ r/2. So, we can use Lemma 3.4 (ii) together with (48) to write, with r = dist(0, A),

P z τ 1 (A) < ∞, S τ 1 (A) = y, S / ∈ L for all ≤ τ 1 (A) = P z S τ 1 (A) = y, S / ∈ L for all ≤ τ 1 (A) 1 + O u r ln r = P z S τ 1 (A) = y | τ 1 (A) < τ 1 (L) P z [τ 1 (A) < τ 1 (L)] 1 + O u r ln r = hm A (y) P z τ 1 (A) < τ 1 (L) 1 + O u r ln r + u ln s s .
Inserting this back to (49), we obtain

P x τ 1 (A) < ∞, S τ 1 (A) = y = hm A (y) 1 + O u r ln r + u ln u s × k≥0,z∈L P x S k = z, S / ∈ A for all ≤ k P z τ 1 (A) < τ 1 (L) = hm A (y) P z τ 1 (A) < ∞ 1 + O u r ln r + u ln s s ,
and this concludes the proof of Lemma 3.11 (observe that the first term in O(•) is of smaller order than the second one).

Random walk on the torus and its excursions

First, we define the entrance time to a set A ⊂ Z 2 n by

T n (A) = min x∈A T n (x).
Now, consider two sets A ⊂ A ⊂ Z 2 n , and suppose that we are only interested in the trace left by the random walk on the set A. Then, (apart from the initial piece of the trajectory until hitting ∂A for the first time) it is enough to know what are the excursions of the random walk between the boundaries of A and A . By definition, an excursion is a simple random walk path that starts at ∂A and ends on its first visit to ∂A , i.e., = ( 0 , 1 , . . . , m ), where 0 ∈ ∂A, m ∈ ∂A , k / ∈ ∂A and k ∼ k+1 for k < m. With some abuse of notation, we denote by st := ρ 0 and end := m the starting and the ending points of the excursion. To define these excursions, consider the following sequence of stopping times:

D 0 = T n (∂A ), J 1 = inf{t > D 0 : X t ∈ ∂A}, D 1 = inf{t > J 1 : X t ∈ ∂A },
and

J k = inf{t > D k-1 : X t ∈ ∂A}, D k = inf{t > J k : X t ∈ ∂A },
for k ≥ 2. Then, denote by Z (i) = (X J i , . . . , X D i ) the ith excursion of X between ∂A and ∂A , for i ≥ 1. Also, let Z 0 = (X 0 , . . . , X D 0 ) be the "initial" excursion (it is possible, in fact, that it does not intersect the set A at all). Recall that t α := 4α π n 2 ln 2 n and define

N α = max{k : J k ≤ t α }, (50)
N α = max{k : D k ≤ t α } (51)
to be the number of incomplete (respectively, complete) excursions up to time t α .

Next, we need also to define the excursions of random interlacements in an analogous way. Assume that the trajectories of the S-walks that intersect A are enumerated according to their u-labels (recall the construction in Section 2.2). For each trajectory from that list (say, the jth one, denoted S (j) and time-shifted in such a way that S

Proofs of the main results

First of all, we apply some results of Section 3 to finish the proof of Theorem 2.3.

Proof of Theorem 2.3, parts (iii)-(v). Recall the fundamental formula (2) for the random interlacement and the relation [START_REF] Dembo | Late points for random walks in two dimensions[END_REF]. Then, the statement (iv) follows from Lemma 3.9, while (v) is a consequence of Lemma 3.10 (i).

Finally, observe that, by symmetry and Lemma 3.10 (ii) we have

P[A ⊂ V α | x ∈ V α ] = exp -πα cap(A ∪ {x}) -cap({0, x}) = exp -πα a(x) + O r ln r ln x x 2 2a(x) -cap(A) + O r ln r ln x x - a(x) 2 = exp - πα 4 cap(A) 1 + O r ln r ln x x 1 -cap(A) 2a(x) + O r ln r x ,
thus proving the part (iii).

Proof of Theorem 2.5 (iii). We start by stating an elementary fact: let N be a Poisson random variable with parameter λ, and Y 1 , Y 2 , Y 3 , . . . be independent (also of N ) random variables with exponential distribution E(p) with parameter p. Let Θ = N j=1 Y j be the corresponding compound Poisson random variable. Its Cramér transform b → λ( √ b -1) 2 is easily computed, and the Chernov's bound writes, for all b > 1,

P[Θ ≥ bλp -1 ] ≤ exp -λ( √ b -1) 2 . (54)
Now, assume that α < 1. Fix β ∈ (0, 1), which will be later taken close to 1, and fix some set of non-intersecting disks -β) . Denote also B j := B x j , r β ln 3 r β , j = 1, . . . , k r . Before going to the heart of the matter we briefly sketch the strategy of proof. We start to show that at least a half of these balls B j will receive at most 2α ln 2 r β 3β 2 ln ln r β excursions from ∂B j to ∂B j up to time t α . Moreover, using soft local times, we couple such excursions from RI(α) with a slightly larger number of independent excursions from the Ŝ-walk: with overwhelming probability, the trace on ∪ j B j of the latter excursion process contains the trace of the former, so the vacant set V α restricted to balls B j is smaller than the set of unvisited points by the independent process. Now, by independence, it will be possible to estimate the probability for leaving that many balls partially uncovered, and this will conclude the proof.

B 1 = B(x 1 , r β ), . . . , B kr = B(x kr , r β ) ⊂ B(r) \ B(r/2), with cardinality k r = 1 4 r 2(1
We start with an observation: the number of S-walks in RI(α) intersecting a given disk B i 0 has Poisson law with parameter λ = (1 + o(1)) 2α 2-β ln r. Indeed, the law is Poisson by construction, the parameter πα cap(B i 0 ∪ {0}) is found in (2) and then estimated using Lemma 3.10 (i).

Next, by Lemma 3.8 (i), the probability that the walk S started from any y ∈ ∂B i 0 does not hit B i 0 is (1 + o(1)) 3 ln ln r β (2-β) ln r . This depends on the starting point, however each S-walk generates a number of excursions between ∂B i 0 and ∂B i 0 which is dominated by a geometric law G(p ) with success parameter p = (1 + o(1)) 3 ln ln r β (2-β) ln r . Recall also that the integer part of E(u) is geometric G(1e -u ). So, with p =ln(1p ), the total number N (i 0 ) α of excursions between ∂B i 0 and ∂B i 0 in RI(α) can be dominated by a compound Poisson law with E(p) terms in the sum with expectation

λp -1 = (1 + o(1))
2α ln 2 r β 3β 2 ln ln r β .

Then, using (54), we obtain for b > 1

P N (i 0 ) α ≥ b 2α ln 2 r β 3β 2 ln ln r β ≤ exp -(1 + o(1)) √ b -1 2 2α β(2 -β) ln r β = r -(1+o(1))( √ b-1) 2 2α 2-β . (55)
Now, let W b be the set

W b = j ≤ k r : N (j) α < b 2α ln 2 r β 3β 2 ln ln r β .
Combining (55) with Markov inequality, we get

k r 2 P |W b | > k r /2 ≤ E W b ≤ k r r -(1+o(1))( √ b-1) 2 2α 2-β , so P |W b | ≥ k r /2 ≥ 1 -2r -(1+o(1))( √ b-1) 2 2α 2-β . ( 56
)
Lemma 2.1 of [START_REF] Comets | On large deviations for the cover time of two-dimensional torus[END_REF] implies that (observe that, by Lemma 3.11, the parameter v in Lemma 2.1 of [START_REF] Comets | On large deviations for the cover time of two-dimensional torus[END_REF] can be anything exceeding O(1/ ln 2 r), so we choose e.g. v = (ln ln r) -1 ) P D j ≤ exp -C ln 2 r (ln ln r) 2 , so we obtain by the union bound the subpolynomial estimate

P D ≤ 1 4 r 2(1-β) exp -C ln 2 r (ln ln r) 2 . ( 59
)
Observe that, by construction, on the event D we have V α ∩ B j = ∅ for all j ∈ W ∩ W b . So, using (56), (58), and (59), we obtain

P V α ∩ B(r) \ B(r/2) = ∅ ≤ P |W b | < k r 2 + P D + P | W | < 3k r 5 ≤ 2r -(1+o(1))( √ b-1) 2 2α 2-β + 1 4 r 2(1-β) exp -C ln 2 r (ln ln r) 2 + exp -Cr 2(1-β) .
Since b ∈ (1, α -1 ) can be arbitrarily close to α -1 and β ∈ (0, 1) can be arbitrarily close to 1, this concludes the proof of (21).

Proof of Theorem 2.5 (ii). To complete the proofs in Section 2.1, it remains to prove that |V α | < ∞ a.s. for α > 1. First,we establish the following elementary fact. For x ∈ ∂B(2r) and y ∈ B(r) \ B(r/2), it holds

P x [ τ 1 (y) < τ 1 (r ln r)] = ln ln r ln r 1 + o(1) . (60)
Indeed, define the events

G 0 = {τ 1 (0) < τ 1 (r ln r)}, G 1 = {τ 1 (y) < τ 1 (r ln r)};
then, Lemma 3.1 implies that

P x [G 0 ] = ln ln r ln r 1 + o(1) = P x [G 1 ] 1 + o(1) .
Observe that

P x [G 0 ∩ G 1 ] = P x [G 0 ∪ G 1 ]P x [G 0 ∩ G 1 | G 0 ∪ G 1 ] ≤ P x [G 0 ] + P x [G 1 ] P 0 [G 1 ] + P y [G 0 ] ≤ ln ln r ln r 2 1 + o(1) .
So,

P x [G 1 | G 0 ] = P x [G 1 ] -P x [G 0 ∩ G 1 ] 1 -P x [G 0 ] = ln ln r ln r 1 + o(1) ,
and we use Lemma 3.4 to conclude the proof of (60). Now, the goal is to prove that, for α > 1

P[there exists y ∈ B(r) \ B(r/2) such that y ∈ V α ] ≤ r -α 2 (1-α -1 ) 2 (1+o (1)
) .

(61) This would clearly imply that the set V α is a.s. finite, since

{V α is infinite} = V α ∩ B(2 n )\B(2 n-1 ) = ∅ for infinitely many n , (62)
and the Borel-Cantelli lemma together with (61) imply that the probability of the latter event equals 0.

Let N α,r be the number of S-excursions of RI(α) between ∂B(r) and ∂B(r ln r). Analogously to (55), it is straightforward to show that, for b < 1,

P N α,r ≤ b 2α ln 2 r ln ln r ≤ r -2α(1- √ b) 2 (1+o(1)) . (63)
Now, (60) implies that for y ∈ B(r) \ B(r/2)

P y is uncovered by first b 2α ln 2 r ln ln r excursions ≤ 1 - ln ln r ln r (1 + o(1)) 2α ln 2 r ln ln r = r -2bα(1+o(1)) , (64)
so, using the union bound, = n -2α+o (1) , see e.g. (1.6)-(1.7) in [START_REF] Comets | On large deviations for the cover time of two-dimensional torus[END_REF]. Then, observe that Lemma 3.12 implies that

P ∃y ∈ B(r) \ B(r/2) : y ∈ V α , N α,r > b 2α ln 2 r ln ln r ≤ r -2(bα-1)(1+o(
P N α / ∈ I δ 0 ∈ U (n) tα ≤ P[N α / ∈ I δ ] P[0 ∈ U (n) tα ] ≤ n 2α+o(1) × n -C α 2 ,
so, if C is large enough, for some c > 0 it holds that

P N α ∈ I δn,α 0 ∈ U (n) tα ≥ 1 -n -c α . ( 66
) Define h(t, x) = P x [T n (0) > t].
To simplify the notations, let us also assume that t α is integer. As mentioned in the end of Section 2.2, we will represent the conditioned random walk as a time-dependent Markov chain, using the Doob's h-transform. Indeed, it is well known and easily checked that the simple random walk on Z 2 n conditioned on the event {0 ∈ U (n) tα } is a time-dependent Markov chain X with transition probabilities given by

P[ Xs+1 = y | Xs = x] = h(t α -s -1, y) h(t α -s, x) × 1 4 , (67)
if yx 1 = 1, and equal to 0 otherwise. For simpler notations, we do not indicate the dependence on t α in the notation X. In order to proceed, we need the following fact, which proof can be skipped in a first reading.

Lemma 4.1. For all λ ∈ (0, 1/5), there exist c 1 > 0, n 1 ≥ 2 (depending on λ) such that for all n ≥ n 1 , β ≥ 1, x , y ≥ λn, |r| ≤ βn 2 and all s ≥ 0,

h(s, x) h(s + r, y) -1 ≤ c 1 β ln n . ( 68
) Proof. Denote h(t, µ) := P µ [T n (0) > t],
where P µ [•] is the probability for the simple random walk on Z 2 n starting from the initial distribution µ.

Let us define the set M of probability measures on Z 2 n in the following way: M = ν : ν B(j) ≤ 7j 2 n -2 for all j ≤ λn ;

observe that any probability measure concentrated on a one-point set {x} with x ≥ λn belongs to M. Assume from now on that n is odd, so that the simple random walk on Z 2 n is aperiodic (the case of even n can be treated essentially in the same way, with some obvious modifications). Recall that the uniform measure µ 0 on Z 2 n , i.e., µ 0 (x) = n -2 for all x ∈ Z 2 n , is the invariant law of simple random walk X on Z 2 n . Since the mixing time of X is of order n 2 (e.g., Theorem 5.5 in [START_REF] Levin | Markov chains and mixing times[END_REF]), it is clear that for any δ ∈ (0, 1) one can find large enough c (in fact, c = O(ln δ -1 )) such that for any probability measure ν it holds that

νP (s) = (1 -δ)µ 0 + δν , with ν ∈ M (69)
for all s ≥ c n 2 . In fact, the argument only shows that ν , defined in the above equality, is a probability measure. However, using that the s-step transition probability for X from x to y in Z 2 n is equal to P x (S s ∈ {y} + nZ 2 ), the local limit theorem implies that ν belongs to the set M for large enough c .

Then, we are going to obtain that there exist some c 2 > 0, b 0 > 0, such that for all b ∈ {b 0 , 2b 0 , 3b 0 , . . .} and all ν ∈ M,

h(bn 2 , ν) = P ν [T n (0) > bn 2 ] ≥ 1 - bc 2 ln n . (70)
To prove (70), let us first show that there exists c 3 = c 3 (λ) > 0 such that

P ν T n (0) < T n ∂B(λn) ≤ c 3 ln n (71) for all ν ∈ M. Abbreviate W j = B λn 2 j-1 \ B λn 2 j
and write, using (26) 1) .

x∈W j ν(x)P x T n (0) < T n ∂B(λn) ≤ x∈W j ν(x) 1 - a(x) a(λn) + O(n -1 ) ≤ 7n -2 × λ 2 n 2 2 2(j-1) × 1 - ln λn -j ln 2 ln λn + O(n -1 ) ≤ 1 ln λn × 7jλ 2 ln 2 2 2(j-
Let j 0 be such that λn

2 j 0 ≤ n √ ln n . Write P ν T n (0) < T n ∂B(λn) ≤ ν B n √ ln n + j 0 j=1 x∈W j ν(x)P x T n (0) < T n ∂B(λn) ≤ 7 ln n + 1 ln λn j 0 j=1 7jλ 2 ln 2 2 2(j-1)
for ν ∈ M, which proves (71). To obtain (70), let us first fix b 0 > 0 such that νP (b 0 n 2 ) ∈ M for any ν ∈ M. Observe that the number of excursions by time b 0 n 2 between ∂B(λn) and ∂B(n/3) is stochastically bounded by a Geometric random variable with expectation of constant order. Since (again by (26)) for any x ∈ ∂B(λn) P x T n (0) < T n ∂B(n/3) ≤ c 4 ln n , and, considering a random sum of a geometric number of independent Bernoulli with parameter c 4 / ln n, it is is not difficult to obtain that

P ν [T n (0) ≤ b 0 n 2 ] ≤ c 5 ln n . (72)
The inequality (70) then follows from (72) and the union bound, (note that the above inequalities hold with factor 2 in the right-hand side, but we intentionally put a larger factor there for reasons that will become clear later). We now extend by induction that (73)-(74) from times s ≤ s 0 = c n 2 to all times. Let s k = (k + 1)c n 2 , and consider the recursion hypothesis (H k ) :

(73) and (74) hold for s ≤ s k , that we just have proved for k = 0. Assume now (H k ) for some k. Define the event G r,s = {X j = 0 for all r + 1 ≤ j ≤ s}, and write h(s + t, µ) = P µ [G where the sum is over all paths that begin in x and end on the first visit to ∂B(n/3). So, using (77), we obtain for all s ≤ t αn 2 √ ln n and all x ∈ ∂B n The other terms in the right-hand sides of (87)-(88) are o(1) due to (66), (85), and (86). Since, as observed just before Lemma 4.1

P[Υ n A ⊂ U (n) tα | 0 ∈ U (n) tα ] = P T n (A) > t α ,
the proof of Theorem 2.6 is concluded.

Figure 1 :

 1 Figure 1: A realization of the vacant set (dark blue) of RI(α) for different values of α.For α = 1.5 the only vacant site is the origin. Also, note that the sets are the same for α = 1 and α = 1.25; this is not surprising since just a few new walks enter the picture when increasing the rate by a small amount.

Figure 3 :

 3 Figure 3: Excursions (depicted as the solid pieces of the trajectory) of the SRW on the torus Z 2 n

Figure 4 :

 4 Figure 4: On the proof of Lemma 3.8

P 1 j=0P- 1 ≤ 2 .

 112 ν [T n (0) ≤ kb 0 n 2 ] ≤ k-νP (jb 0 n 2 ) [T n (0) ≤ b 0 n 2 ] ≤ kc 5 ln n .Now, let c ∈ b 0 N * be such that δ < 1/3 in (69). Assume also that n is sufficiently large so that 1 -c c 2 ln n Then, (70) implies that for all s ≤ c n 2 and ν ∈ M h(s, µ) h(s, ν)

(c n 2 )

 2 )P µ [T n (0) > c n 2 | G c n 2 ,t+s ] h(s, νP (c n 2 ) )P ν [T n (0) > c n 2 | G c n 2 ,t+s ] = P x τ 1 (A) > τ 1 (∂B(n/3)) 1 + O 1 ln n ,

For k ≥ 1 n ln 2 n 2α ln 2 n

 12 3 ln n , P T (s) n (A) > T (s) n (∂B(n/3)) | X s = x = 1o(1)). (82)Before we are able to conclude the proof of Theorem 2.6, we need another step to take care of times close to t α . Consider any x ∈ ∂B n 3 ln n and any s ≥ 0 such that t αs ≤ n 2 √ ln n. Then, (78) together with the fact that h(•, •) is nondecreasing with respect to the first (temporal) argument imply thatP x ( X 0 , . . . , X | | ) = = h(t αs -| |, end ) h(t αs, x) P x (X 0 , . . . , X | | ) = ≤ c 7 P x (X 0 , . . . , X | | ) =(83)for any path with 0 = x. Then, similarly to Section 3.4, define Jk Dk to be the starting and ending times of kth excursion of X between ∂B n 3 ln n and ∂B(n/3), k ≥ 1. Letζ = min{k : Jk ≥ t αn 2 √ ln n}be the index of the first X-excursion that starts before time t α -n 2 √ ln n. Let ξ 1 , ξ 2 , ξ 3 , . . . be a sequence of i.i.d. Bernoulli random variables independent of everything, withP[ξ k = 1] = 1 -P[ξ k = 0] = 1define two sequences of random variables ξ k = 1{ X j / ∈ A for all j ∈ [ Jk , Dk ]}, for j < ζ, ξ k , for j ≥ ζ,andη k = 1{ X j / ∈ A for all j ∈ [ Jζ+k-1 , Dζ+k-1 ]}. ≥ P ξ k = 1 for all k ≤ (1 + δ n,α ) 2α ln 2 n ln ln n -P N α > (1 + δ n,α )2α ln 2 n ln ln n -P η k = 1 for all k ≤ ), we obtain that the first terms in the right-hand sides of (87)ln ln n = (1 + o(1)) expπα cap(A ∪ {0}) .

  Let N α be the number of excursions between ∂B n 3 ln n and ∂B(n/3) up to time t α . It holds that P 0 ∈ U

	Proof of Theorem 2.6. Abbreviate δ n,α = Cα ln ln n ln n and
	I δn,α = (1 -δ n,α )	2α ln 2 n ln ln n	, (1 + δ n,α )	2α ln 2 n ln ln n	.
	(n)
	tα
						1)) . (65)
	Using (63) and (65) with b = 1 4 1 + 1 α	2 we conclude the proof of (61) and
	of Theorem 2.5 (ii).

  Abbreviate t = c n 2 for the rest of the proof of the Lemma. Let us estimate the second term in the right-hand side of (75). Let Γ [0,t] be the set of all nearest-neighbour trajectories on Z 2 n of length t. For ∈ Γ [0,t] we haveP µ [ ] = µ( 0 ) 1using the relation (73) for s ≤ s k . Summing over such that T n (0) ≤ t and using (70), we obtain, for µ ∈ M,P µ [T n (0) > t | G t,s+t ] ≥ 1 -

	4	| | and
	P µ [ | G t,s+t ] = µ( 0 )	1 4	| |	×	h(s, end ) h(s, µP (t) )	≤ µ( 0 )	1 4	| |	1 +	3c c 2 ln n
								c c 2 ln n	1 +	3c c 2 ln n	.	(76)
	Now, we use (69) and (75) to obtain that, with µ , ν defined in (69),
	h(t + s, µ) h(t + s, ν)	=	h(s, µP

t,s+t ]P µ [T n (0) > t | G t,s+t ] = h(s, µP (t) )P µ [T n (0) > t | G t,s+t ].

(75)

γ = π -1 (2γ + ln 8), where γ = 0.5772156 . . . is the Euler-Mascheroni constant

Acknowledgments

The authors are grateful to Caio Alves and Darcy Cunha for pointing out to us that 1 a is a martingale for the conditioned walk, and to David Belius and Augusto Teixeira for useful discussions. Darcy Cunha also did the simulations of the model presented on Figure 1.

Also, the authors thank the financial support from Franco-Brazilian Scientific Cooperation program. S.P. and M.V. were partially supported by CNPq (grants 300886/2008-0 and 301455/2009-0). The last two authors thank FAPESP (2009/52379-8, 2014/06815-9, 2014/06998-6) for financial support. F.C. is partially supported by CNRS, UMR 7599 LPMA.

), where i = m + j-1 k=1 k , and m = 1, 2, . . . j . We let R α to be the number of trajectories intersecting A and with labels less than απ, and denote Nα = Rα k=1 k to be the total number of excursions of RI(α) between ∂A and ∂A . Observe also that the above construction makes sense with α = ∞ as well; we then obtain an infinite sequence of excursions of RI (=RI(∞)) between ∂A and ∂A .

Finally, let us recall a result of [START_REF] Dembo | Late points for random walks in two dimensions[END_REF] on the number of excursions for the simple random walk on Z 2 n .

Lemma 3.12. Consider the random variables J k , D k defined in this section with A = B n 3 ln n , A = B n 3 . Then, there exist positive constants δ 0 , c 0 such that, for any δ with c 0 ln n ≤ δ ≤ δ 0 , we have

and the same result holds with D k on the place of J k .

Proof. This is, in fact, a particular case of Lemma 3.2 of [START_REF] Dembo | Late points for random walks in two dimensions[END_REF].

A useful consequence of Lemma 3.12 is

and the same result holds with N α on the place of N α , where N α , N α are defined as in (50)-(51

Assume that 1 < b < α -1 and β ∈ (0, 1) is close enough to 1, so that bα β 2 < 1. As in Section 3.4, we denote by Ẑ(1),j , . . . , Ẑ( N (j) α ),j the excursions of RI(α) between ∂B j and ∂B j . Also, let Z(1),j , Z(2),j , Z(3),j , . . . be a sequence of i.i.d. S-excursions between ∂B j and ∂B j , started at hm B j . In the following, we assume that both Ẑand Z-excursions are constructed on the same probability space using the soft local times, as described in Section 2 of [START_REF] Comets | On large deviations for the cover time of two-dimensional torus[END_REF].

Let δ > 0 be such that (1 + δ) bα β 2 < 1 and abbreviate m = b 2α ln 2 r β 3β 2 ln ln r β . Define the events

Then, for all j ≤ k r it holds that

for all large enough r. Indeed, if the Z's were SRW-excursions, the above inequality (with any fixed constant in the right-hand side) could be obtained in a completely analogous way as the proof of Lemma 3.2 of [START_REF] Comets | On large deviations for the cover time of two-dimensional torus[END_REF]. On the other hand, Lemma 3.4 (ii) implies that the first (1 + δ)m S-excursions can be coupled with SRW-excursions with high probability, so (57) holds for Sexcursions as well. Define the set W = j ≤ k r : G j occurs . Since the events ( Gj , j ≤ k r ) are independent, by (57) we have (recall that

for all r large enough. Next, we consider the events

(recall that the excursions are coupled using soft local times), and

, for s ≤ s k . We now use (H k ) for the two ratios of h's in the above expression, we also use (76) for the conditional probability in the denominator -simply bounding it by 1 in the numerator -to obtain

for ν ∈ M. Since δ < 1/3, for large enough n we obtain that (73) also holds for all s ≤ s k+1 . In the same way, we prove the validity of (74) for s ≤ s k+1 . This proves the recursion, which in turn, implies (68) for the case r = 0. To conclude the proof of Lemma 4.1, we observe that the general case follows from (70).

We continue the proof of Theorem 2.6. We assume that the set A is fixed, so that cap(A) = O(1) and diam(A) = O(1). In addition, assume without resricting generality that 0 ∈ A. Recall that with (66) we control the number of excursions between ∂B n 3 ln n and ∂B(n/3) up to time t α . Now, we estimate the (conditional) probability that an excursion hits the set A. For this, observe that Lemmas 3.1, 3.3 and 3.4 imply that, for any x ∈ ∂B n 3 ln n

Now, we need the following fact: there exists c 5 > 0 such that

for all s ≥ n 2 ln n and all x ∈ Z 2 n such that x ≥ n 3 ln n (in fact, it is straightforward to obtain that (78) holds if x ≥ n ε 0 , where ε 0 ∈ (0, 1) is some fixed number). To prove (78) it is enough to observe that

• the number of (possibly incomplete) excursions between ∂B n 3 ln n and ∂B(n/3) until time s does not exceed 3s n 2 ln ln n with probability at least 1exp c 6 s n 2 ln ln n , by (53); • regardless of the past, each excursion hits 0 with probability ln ln n ln n (1 + o(1)), by (26).

To extract from (77) the corresponding formula for the X-excursion, we first observe that, for x ∈ ∂B n 3 ln n and s

where y,k = P x X Tn(∂B(n/3)) = y, T n (∂B(n/3)) = k | T n (0) > T n (∂B(n/3)) and 0 ≤ ψ s,n ≤ e -Cs/n 2 . Recall the notation Γ (x) 0,R from the beginning of Section 3.2. Then, for a fixed x ∈ ∂B n 3 ln n let us define the set of paths

for some c > 0. Now, going back to (79) and setting a

a relation which can be compared to Lemma 4.1.

For A ⊂ Z 2 , let us define also the hitting times of the corresponding set on the torus for the X-walk after a given moment s:

we abbreviate also T n (A) = T (0) n (A). Then, in the same way we obtain

Now, observe that (82) and the strong Markov property imply that

Also, the relation (83) together with Lemma 3.3 imply that

Then, (83) and Lemma 3.12 imply that (note that π/2 < 3)

Recall the notation δ n,α from the beginning of the proof of this theorem. We can write P ξ k = 1 for all k ≤ (1δ n,α ) 2α ln