UPPER TAILS FOR INTERSECTION LOCAL TIMES OF RANDOM WALKS IN SUPERCRITICAL DIMENSIONS

Xia Chen and Peter Mörters

University of Tennessee and University of Bath

Abstract. We determine the precise asymptotics of the logarithmic upper tail probability of the total intersection local time of p independent random walks in ℤ^{d} under the assumption p(d − 2) > d. Our approach allows a direct treatment of the infinite time horizon.

Mathematics Subject Classification (2000): 60F10, 60G50, 60K35.

1. Introduction and main result

1.1 Motivation Quantities measuring the amount of self-intersection of a random walk, or of mutual intersection of several independent random walks have been studied intensively for more than twenty years, see e.g. [DV79, LG86, La91, MR97, HK01, Ch04]. This research is often motivated by the rôle these quantities play in quantum field theory, see e.g. [FFS92], in our understanding of self-avoiding walks and polymer models, see e.g. [MS93], or in the analysis of stochastic processes in random environments, see e.g. [HKM06, GKS07, AC07, FMW08]. In the latter models dependence between a moving particle and a random environment frequently comes from the particle’s ability to revisit sites with a (in some sense) attractive environment, and therefore measures of self-intersection quantify the degree of dependence between movement and environment. Typically, in high dimensions this dependence gets weaker, as the movements become more transient and self-intersections less likely.

In their influential paper [KM94], Khanin, Mazel, Shlosman and Sinai make the surprising observation that even in high dimensions the random variables counting the total number of intersections of two independent simple random walks have subexponential tails at infinity. They argue that this observation is intimately related to the fact that a random walk in random potential has subdiffusive behaviour in all dimensions. Similar observations were made at around the same time by Sznitman in a continuous setting, see [Sz93]. In their analysis of intersection measures of high-dimensional random walks, Khanin et al. obtain estimates for the tails at infinity, but there are still significant gaps between the given upper and lower bounds, which despite considerable effort have not been resolved in the past ten years. In this paper we make a contribution to the closure of these gaps.

To be precise, let (X^{(1)}(n) : n ∈ ℕ), …, (X^{(p)}(n) : n ∈ ℕ) be p independent identically distributed random walks taking values in ℤ^{d}. The number of intersections of the walks can be measured in two natural ways: The intersection local time,

I := ∑_{i_{1}=1}^{∞} ⋯ ∑_{i_{p}=1}^{∞} 1l{X^{(1)}(i_{1}) = ⋯ = X^{(p)}(i_{p})},

counts the times when the paths intersect, whereas the intersection of the ranges,

J := ∑_{x∈ℤ^{d}} 1l{X^{(1)}(i_{1}) = ⋯ = X^{(p)}(i_{p}) = x for some (i_{1}, …, i_{p})},

counts the sites where the paths intersect. Obviously, we always have J ≤ I.

Moreover, under suitable conditions on the random walk, it is well known that

ℙ\{I < ∞\} = ℙ\{J < ∞\} = \{ \begin{matrix}1 & if p(d − 2) > d, \\ 0 & otherwise. \end{matrix}

The lower bounds here are easy and hold for all symmetric, aperiodic random walks with finite variance, while the upper bounds hold for simple, symmetric walks by a celebrated result of Dvoretzky and Erdős [DE51]. We assume throughout this paper that p(d − 2) > d, i.e. we are assuming that we are in supercritical dimensions. Then, in the case of simple, symmetric random walks, Khanin et al. show in [KM94] that there exist constants c_{1}, c_{2} > 0 such that, for all a large enough,

exp \{ − c_{1}a^{\frac{1}{p}} \} ≤ ℙ\{I > a\} ≤ exp \{ − c_{2}a^{\frac{1}{p}} \}.

Interestingly, the upper tails of J are substantially lighter. Khanin et al. show that, for all ε > 0 and all sufficiently large a,

exp \{ − a^{\frac{d−2}{d} +ε}\} ≤ ℙ\{J > a\} ≤ exp \{ − a^{\frac{d−2}{d} −ε}\}.

The challenging question lies in understanding the difference of these behaviours, providing sharp estimates for the tails, and understanding the underlying ‘optimal strategies’.

The most important recent progress on this problem was made by van den Berg, Bolthausen and den Hollander [BBH04] for the spatially and temporally continuous analogue of J: Let W_{1}^{ε}(t) and W_{2}^{ε}(t) be the ε-neighbourhoods of two independent Brownian paths starting at the origin and running for t time units, and use | · | to denote Lebesgue measure. They show that, for d ≥ 3,

lim_{t↑∞} \frac{1}{t^{(d−2)/d}} log ℙ\{|W_{1}^{ε}(θt) ∩ W_{2}^{ε}(θt)| ≥ t\} = −I_{d}^{ε}(θ),

and, if d ≥ 5, there exists a critical θ^{∗} such that I_{d}^{ε}(θ) = I_{d}^{ε}(θ^{∗}) for all θ ≥ θ^{∗}. This strongly suggests that, in the supercritical case d ≥ 5,

lim_{t↑∞} \frac{1}{t^{(d−2)/d}} log ℙ\{|W_{1}^{ε}(∞) ∩ W_{2}^{ε}(∞)| ≥ t\} = −I_{d}^{ε}(θ^{∗}),

but the techniques of [BBH04] are strongly reliant on Donsker-Varadhan large deviation theory and, mostly for this reason, do not allow the treatment of infinite times. Therefore this problem, like its discrete counterpart, remains open for the time being.

In the present paper we focus on the intersection local time I, working directly in the discrete setting. We provide sharp estimates for the tail behaviour of I, in other words we identify the limit

lim_{a↑∞} \frac{1}{a^{1/p}} log ℙ\{I > a\} ,

which is given in terms of a natural associated variational problem. The important progress here lies in the fact that our method avoids the use of Donsker-Varadhan large deviation theory and instead allows a direct treatment of infinite times. The proofs provide new insight into the optimal strategies leading to the event {I > a}. An interpretation of the results is that the bulk of the intersections contributing to large values of I are attained in a bounded subset of ℤ^{d}. Naturally, this strategy does not lead to large values of J, which therefore have to be obtained by a different, more expensive, strategy.

1.2 Statement of the main results

1.2.1 Intersection local times for discrete time random walks. Let (X^{(1)}(n) : n ∈ ℕ), …, (X^{(p)}(n) : n ∈ ℕ) be p independent identically distributed random walks started at time n = 0 in the origin and taking values on the lattice ℤ^{d}. Suppose that the walks are aperiodic, have symmetric increments and finite variance, and that d is sufficiently large to satisfy p(d − 2) > d, i.e. we are in supercritical dimensions. Let 𝔾 be Green’s function associated to the random walk, defined by

𝔾(x) := ∑_{n=1}^{∞} ℙ{X^{(1)}(n) = x}.

Note that we are following the (slightly unusual) convention of not summing over the time n = 0, which only influences the value 𝔾(0). We first state integrability and boundedness of some operators associated with Green’s function.

Lemma 1. Let q > 1 be the conjugate of p defined by p^{−1}+q^{−1} = 1. For every nonnegative h ∈ L^{q}(ℤ^{d}) a bounded, symmetric operator 𝔄_{h}: L^{2}(ℤ^{d}) → L^{2}(ℤ^{d}) is defined by

𝔄_{h}g(x) = \sqrt{e^{h(x)} − 1} ∑_{y∈ℤ^{d}} 𝔾(x − y)g(y) \sqrt{e^{h(y)} − 1} .

Moreover, we have 𝔾 ∈ L^{p}(ℤ^{d}) and for the spectral radius, or operator norm,

∥𝔄_{h}∥ := sup {|⟨g, 𝔄_{h}g⟩| : ∥g∥_{2} = 1} = sup {⟨g, 𝔄_{h}g⟩ : g ≥ 0, ∥g∥_{2} = 1}  (1)

of the operator 𝔄_{h} we have the inequality

∥𝔄_{h}∥ ≤ ∥𝔾∥_{p} (e^{∥h∥_{q}} − 1) .  (2)

Note that the alternative description of the spectral radii of 𝔄_{h}, for nonnegative h ∈ L^{q}(ℤ^{d}), on the right hand side of (1) holds trivially because Green’s function is nonnegative. The next theorem, which is our main result, shows that this family of spectral radii can be used to describe the upper tail constant of the intersection local time. Its proof will be given in Section 2.

Theorem 2. The upper tail behaviour of the intersection local time I is given as

lim_{a↑∞} \frac{1}{a^{1/p}} log ℙ\{I > a\} = −p inf \{∥h∥_{q} : h ≥ 0 with ∥𝔄_{h}∥ ≥ 1\} ,  (3)

and the right hand side is negative and finite.

Remark 1.

(a) Heuristically, the optimal strategy for the random walks to realise the event {I > a} is to spend each about a^{1/p} time units in all points of a finite domain A ⊂ ℤ^{d}, which is not growing with a. This leads to a typical intersection local time I ≈ a on this domain alone. As a ↑ ∞ the intersection sites do not spread out in space when the random walks are conditioned on {I > a}, hence this strategy makes I large without making J large. This explains the fundamental difference between these two quantities in supercritical dimensions.

(b) Our proof provides the following evidence for this behaviour: Suppose A ⊂ ℤ^{d} is a finite set and

I(A) := ∑_{i_{1}=1}^{∞} ⋯ ∑_{i_{p}=1}^{∞} 1l{X^{(1)}(i_{1}) = ⋯ = X^{(p)}(i_{p}) ∈ A},

the number of intersections in the set A. Then we show, as a by-product of the proof of Theorem 2, that

lim_{a↑∞} \frac{1}{a^{1/p}} log ℙ\{I(A) > a\} = −p inf \{∥h∥_{q} : h ≥ 0, supp h ⊂ A with ∥𝔄_{h}∥ ≥ 1\} .  (4)

It is easy to see that, as A ↑ ℤ^{d}, the right hand side in (4) converges to the right hand side in (3), and thus for large A the tails of I(A) come arbitrarily close to those of I.

(c) A further interesting feature of our result is that the rate of decay of ℙ{I(A) > a} is invariant under spatial shifts of A, in other words, at the given scale the random walks show no preference for locating their intersections near their starting point. This fact causes considerable difficulty in the proof of the upper bound, as the rate of ℙ{I(A^{c}) > a} does not increase when A is getting large so that, loosely speaking, the problem is not exponentially tight. The technique to get around this problem is one of the main technical innovations in this paper.

Remark 2. From (2) we easily obtain an upper bound for the constant in (3), namely

−p inf {∥h∥_{q} : h ≥ 0 with ∥𝔄_{h}∥ ≥ 1} ≤ −p log (1 + ∥𝔾∥_{p}^{−1}) .

For a lower bound, we define the potential operator

𝔊f(x) := ∑_{y∈ℤ^{d}} 𝔾(x − y)f(y),

and note that, as 𝔾 ∈ L^{p}(ℤ^{d}), this defines a bounded, symmetric operator

𝔊: L^{\frac{2p}{2p−1}} (ℤ^{d}) ⟶ L^{2p}(ℤ^{d}) .

We thus get, using e^{h} − 1 ≥ h for h ≥ 0, that

−p inf {∥h∥_{q} : h ≥ 0, sup_{∥g∥_{2}=1}⟨g, 𝔄_{h}g⟩ ≥ 1}

≥ −p inf \{b : sup_{{∥g∥_{2}=1 \atop ∥h∥q=1}} ⟨\sqrt{h}g, 𝔊\sqrt{h}g⟩ ≥ 1/b\}

= −p/ sup {⟨f^{2p−1}, 𝔊f^{2p−1}⟩ : ∥f∥_{2p} = 1} .

Neither of these bounds are sharp.

1.2.2 Intersection local times for continuous time random walks. It would be desirable to bring the variational formula on the right hand side of (3) into a form naturally interpretable as a competition between a probabilistic cost and benefit factor, and interpret the optimiser in terms of the optimal strategy of the walks. However, the present formula cannot be easily transformed to such a form, an artefact which we believe is due to the discrete time structure of the random walk.

We therefore provide a more transparent result for continuous time random walk for comparison. Let

(X^{(1)}(t) : t ≥ 0), …, (X^{(p)}(t) : t ≥ 0)

be independent, identically distributed continuous time random walks and let A be their generator, defined by

Af(x) = lim_{t↓0} \frac{𝔼_{x}f(Xt^{(1)}) − f(x)}{t} .

We assume that the random walks are aperiodic, and symmetric with finite variance. Then A is a nonpositive definite, symmetric operator. Based on Green’s function

G(x) := ∫_{0}^{∞} ℙ{X(t) = x} dt ,

we define the potential operator 𝔊 as in the discrete time case, see Remark 2. Under our standing assumption of supercriticality, d(p − 2) > d, it is easy to see that G ∈ L^{p}(ℤ^{d}), and again that the potential operator is a bounded operator

𝔊: L^{\frac{2p}{2p−1}} (ℤ^{d}) ⟶ L^{2p}(ℤ^{d}) .

We define the intersection local time as

Ĩ:= ∫_{0}^{∞}dt_{1} ⋯ ∫_{0}^{∞}dt_{p} 1l{X^{(1)}(t_{1}) = ⋯ = X^{(p)}(t_{p})},

which is finite in the supercritical regime. As before, we ask for its upper tail behaviour.

Theorem 3. The upper tail behaviour of the intersection local time Ĩ is given as

lim_{a↑∞} \frac{1}{a^{1/p}} log ℙ\{Ĩ > a\} = −p/ sup \{⟨f^{2p−1}, 𝔊f^{2p−1}⟩ : ∥f∥_{2p} = 1\} ,  (5)

where the right hand side is negative and finite.

Remark 3. Under some additional conditions, the formula on the right can be reformulated in an appealing way. Denote the supremum on the right hand side of (5) by ϱ. Given ϵ > 0 choose f ≥ 0 such that ∥f∥_{2p} = 1 and ⟨f^{2p−1}, 𝔊f^{2p−1}⟩ ≥ ϱ − ϵ. Then one can use that −A ∘ 𝔊 =id and the fact that, by Hölder’s inequality,

∥𝔊f^{2p−1}∥_{2p} ≥ ∥f∥_{2p}^{− \frac{2p}{2p−1}} ⟨f^{2p−1}, 𝔊f^{2p−1}⟩ ≥ ϱ − ϵ,

to obtain that

\begin{aligned}ϱ & ≥ ⟨𝔊f^{2p−1}, f^{2p−1}⟩ = ⟨𝔊f^{2p−1}, −A𝔊f^{2p−1}⟩ = (ϱ − ϵ)^{2} ⟨\frac{𝔊f^{2p−1}}{ϱ − ϵ} , −A\frac{𝔊f^{2p−1}}{ϱ − ϵ} ⟩ \\ & ≥ (ϱ − ϵ)^{2} inf \{⟨g, −Ag⟩ : ∥g∥_{2p} = 1\}, \end{aligned}

whence, for ϵ ↓ 0, we get

\frac{1}{ϱ} ≥ inf \{⟨g, −Ag⟩ : ∥g∥_{2p} = 1\}.

For the converse inequality, we assume that the generator A is such that there exists a positive minimiser g for the variational problem on the right hand side^{1}. A simple perturbation calculation then yields the Euler-Lagrange equation −ρ Ag = g^{2p−1}, where 1/ρ denotes the minimum. Together with −A ∘ 𝔊 =id, this implies that, for some u with Au = 0, we have ρ g = 𝔊g^{2p−1} + u. Note that u is vanishing at infinity and hence, assuming that A allows a maximum principle, we infer that u = 0. Therefore,

\frac{1}{ρ} = ⟨g, −Ag⟩ = \frac{1}{ρ^{2}} ⟨𝔊g^{2p−1}, g^{2p−1}⟩ ≤ \frac{ϱ}{ρ^{2}} .

Hence we obtain that the right hand side in (5) equals

−p inf \{∥\sqrt{−A}g∥_{2}^{2} : ∥g∥_{2p} = 1\} .

In this form, the constant has a natural interpretation: At least heuristically, the optimal strategy for each random walk is to build up a local time field

ℓ^{(j)}(x) := ∫_{0}^{∞} 1l{X^{(j)}(t) = x} dt ≈ a^{1/p}g^{2}(x) for all j ∈ {1, …, p},

which implies

Ĩ = ∑_{x∈ℤ^{d}} ∏_{j=1}^{p} ℓ^{(j)}(x) ≈ ∑_{x∈ℤ^{d}} ∏_{j=1}^{p} a^{1/p} g^{2}(x) = a .

1This assumption is generally nontrivial to verify, even for explicitly given A.

The probability of a random walk achieving such a local time is

≈ exp \{ − a^{1/p} ∥\sqrt{−A}g∥_{2}^{2}\},

which is reminiscent of the rate functions in Donsker-Varadhan theory.

Remark 4. The proof of Theorem 3 follows a similar strategy as in the discrete time case but, thanks to the absence of some combinatorial difficulties arising from the discrete time structure, it is considerably easier. Following the arguments analogous to Theorem 2 gives

lim_{a↑∞} \frac{1}{a^{1/p}} log ℙ\{Ĩ > a\} = −p inf \{∥h∥_{q} : h ≥ 0 with ∥𝔅_{h}∥ ≥ 1\},

where the operator 𝔅_{h}: L^{2}(ℤ^{d}) → L^{2}(ℤ^{d}) is defined by

𝔅_{h}g(x) = \sqrt{h(x)} ∑_{y∈ℤ^{d}} G(x − y)g(y) \sqrt{h(y)} .

Then one can observe that

inf \{∥h∥_{q} : h ≥ 0, sup_{∥g∥_{2}=1}⟨g, 𝔅_{h}g⟩ ≥ 1\} = inf \{b : sup_{{∥g∥_{2}=1 \atop ∥h∥q=1}} ⟨\sqrt{h}g, 𝔊\sqrt{h}g⟩ ≥ 1/b\}
= 1/ sup {⟨f^{2p−1}, 𝔊f^{2p−1}⟩ : ∥f∥_{2p} = 1} .

2. Random walks in discrete time: Proof of Theorem 2.

In Section 2.1 we provide the proof of Lemma 1. The proof of Theorem 2 is divided into six steps, presented in Sections 2.2 to 2.7 below. We now give a brief overview over these steps and the main techniques of the proof.

By Lemma 2.3 in [KM02] we have, for any nonnegative random variable X,

lim_{k↑∞} \frac{1}{k} log 𝔼[\frac{X^{k}}{(k!)^{p}} ] = −κ ⟺ lim_{a↑∞} \frac{1}{a^{1/p}} log ℙ\{X > a\} = −pe^{κ/p} .  (6)

Moreover, it is elementary to show that

∑_{k=1}^{∞} \frac{θ^{k}}{k!} 𝔼[X^{k}]^{\frac{1}{p}} = ∞ for θ > e^{κ/p} ⟺ lim sup_{k↑∞} \frac{1}{k} log 𝔼[\frac{X^{k}}{(k!)^{p}} ] ≥ −κ .

Hence the lower bound in Theorem 2 is proved once we show that

(i) the limit κ := − lim_{k↑∞} \frac{1}{k} log 𝔼[\frac{I^{k}}{(k!)^{p}} ] exists,

(ii) if there exists h ≥ 0 with ∥h∥_{q} = θ such that ∥𝔄_{h}∥ > 1 then ∑_{k=1}^{∞} \frac{θ^{k}}{k!} 𝔼[I^{k}]^{\frac{1}{p}} = ∞.

The proof of (i) is accomplished in Section 2.2 using a subadditivity argument. As a by-product of this proof we see that for the upper tail behaviour of I it is irrelevant whether we start summation in the definition of I at time zero or one. The proof of (ii) is based on the precise formula (11) for the integer moments, which we derive in Section 2.3. Here the peculiarities of the discrete time structure can be quickly explained: It is easy to see that

𝔼[I^{k}] = ∑_{x_{1},...,x_{k}∈ℤ^{d}} ( ∑_{i_{1},...,i_{k}} 𝔼 ∏_{ℓ=1}^{k} 1l{X(i_{ℓ}) = x_{ℓ}})^{p},

where X is a random walk with the same law as X^{(1)}, …, X^{(p)}. To evaluate the expectation we need to keep track of indices with i_{k} = i_{ℓ} with k < ℓ as

1l\{X(i_{k}) = x_{k}, X(i_{ℓ}) = x_{ℓ}\} = \{ \begin{matrix}1l\{X(i_{k}) = x_{k}\} & if x_{k} = x_{ℓ}, \\ 0 & if x_{k} ≠ x_{ℓ}. \end{matrix}

This ‘diagonal effect’ cannot be neglected and we need to keep track of the number of equal indices in (i_{1}, …, i_{k}). This leads to a significantly more complicated combinatorial structure of the moment formula and, ultimately, to the difference between the tail behaviour in the discrete and continuous time case. Having formulated a moment formula which keeps track of this effect, in Section 2.4, we insert it in the exponential series in (ii) and verify divergence of the series using first Hölder’s inequality and then a spectral argument. This completes the proof of the lower bound in Theorem 2.

The proof of the upper bound is more delicate. We again use (i) and the formula (11) to reduce the problem to studying the large moment asymptotics of an explicit analytical quantity. However the use of spectral arguments, which was so successful for the lower bound, now seems to be confined to studying intersection local times in finite sets. Using similar ideas we show in Section 2.5 that, for any finite set A ⊂ ℤ^{d},

lim sup_{k↑∞} \frac{1}{k} log \frac{1}{k!} 𝔼[I(A)^{k}] ≤ −p log inf \{∥h∥_{q} : h ≥ 0, supp h ⊂ A with ∥𝔄_{h}∥ ≥ 1\}.

As indicated in Remark 1(c), the extension of the result from finite sets A to the entire lattice is highly nontrivial, because the problem is not exponentially tight. To overcome this difficulty, we need to project the full problem onto a finite domain by wrapping it around a torus. More precisely, in Section 2.6 we let A = [−N, N)^{d} for a large integer N and show that

lim sup_{k↑∞} \frac{1}{k} log \frac{1}{k!} 𝔼[I^{k}] ≤ −p log inf \{∥h∥_{q} : h ≥ 0, supp h ⊂ A with ∥𝔄̃_{h,N}∥ ≥ 1\},

where in the definition of the operator 𝔄̃_{h,N} the kernel 𝔾 has been replaced by 𝔾̃_{N} defined by

𝔾̃_{N}(y) = \{ ∑_{z∈ℤ^{d}} 𝔾^{p}(2Nz + y)\}^{\frac{1}{p}} for any y ∈ ℤ^{d} .

In Section 2.7 we let the period of the torus go to infinity and prove that

lim sup_{N→∞} inf {∥h∥_{q} : h ≥ 0, supp h ⊂ A with ∥𝔄̃_{h,N}∥ ≥ 1} ≥ inf {∥h∥_{q} : h ≥ 0 with ∥𝔄_{h}∥ ≥ 1},

which leads to the required upper bound.

2.1 Proof of Lemma 1.

We start by showing that 𝔾 ∈ L^{p}(ℤ^{d}). Indeed, by [Uc98, (1.4)], we have (using only finite variance of the increments and the fact that the walk is aperiodic),

𝔾(z) ≤ ∑_{x∈ℤ^{d}} \frac{π(x)}{1 + |x − z|^{d−2}} for all z ∈ ℤ^{d},

where (π(x): x ∈ ℤ^{d}) is a summable family of nonnegative weights. Hence, as p(d − 2) > d,

( ∑_{z∈ℤ^{d}} 𝔾^{p}(z))^{\frac{1}{p}} ≤ ∑_{x∈ℤ^{d}} ( ∑_{z∈ℤ^{d}} \frac{π^{p}(x)}{(1 + |x − z|^{d−2})^{p}} )^{\frac{1}{p}} = ( ∑_{x∈ℤ^{d}} π(x)) ( ∑_{z∈ℤ^{d}} \frac{1}{(1 + |z|^{d−2})^{p}} )^{\frac{1}{p}} < ∞ .

To prove that the operator 𝔄_{h} is bounded note that, whenever ∥g_{1}∥_{2} = ∥g_{2}∥_{2} = 1 and g_{1}, g_{2} ≥ 0, by Hölder’s inequality,

\begin{aligned}⟨g_{1}, 𝔄_{h}g_{2}⟩ & = ∑_{x,y∈ℤ^{d}} g_{1}(x) \sqrt{e^{h(x)} − 1} 𝔾(x − y) \sqrt{e^{h(y)} − 1} g_{2}(y) \\ & ≤ ( ∑_{x,y∈ℤ^{d}} 𝔾^{p}(x − y)\{g_{1}(x) \sqrt{e^{h(x)} − 1} g_{2}(y) \sqrt{e^{h(y)} − 1} \}^{\frac{p}{2p−1}} )^{\frac{1}{p}} \\ & × ( ∑_{x,y∈ℤ^{d}} \{g_{1}(x) \sqrt{e^{h(x)} − 1} g_{2}(y) \sqrt{e^{h(y)} − 1}\}^{\frac{2p}{2p−1}} )^{\frac{1}{q}} . \end{aligned}  (7)

Using again Hölder’s inequality, the second factor on the right hand side of (7) is bounded by

\begin{matrix}( ∑_{x∈ℤ^{d}} \{g_{1}(x) \sqrt{e^{h(x)} − 1} & \}^{\frac{2p}{2p−1}} )^{\frac{1}{q}} ( ∑_{x∈ℤ^{d}} \{g_{2}(x) \sqrt{e^{h(x)} − 1}\}^{\frac{2p}{2p−1}} )^{\frac{1}{q}} \\ ≤ ( ∑_{x∈ℤ^{d}} g_{1}^{2}(x))^{\frac{1}{q+1}} ( ∑_{x∈ℤ^{d}} g_{2}^{2}(x))^{\frac{1}{q+1}} (\{ ∑_{x∈ℤ^{d}} (e^{h(x)} − 1)^{q}\}^{\frac{1}{q}} )^{\frac{2}{q+1}} , \end{matrix}

whence we use that ∥g_{1}∥_{2} = ∥g_{2}∥_{2} = 1 and

\{ ∑_{x∈ℤ^{d}} (e^{h(x)} − 1)^{q}\}^{\frac{1}{q}} ≤ ∑_{k=1}^{∞} \frac{∥h∥_{q}^{k}}{k!} \{ ∑_{x∈ℤ^{d}} (\frac{h(x)}{∥h∥_{q}} )^{kq}\}^{\frac{1}{q}} ≤ e^{∥h∥_{q}} − 1 .

By a shift of coordinates the first factor on the right hand side of (7) equals

( ∑_{x∈ℤ^{d}} 𝔾^{p}(x) ∑_{y∈ℤ^{d}} \{g_{1}(x + y) \sqrt{e^{h(x+y)} − 1} g_{2}(y) \sqrt{e^{h(y)} − 1}\}^{\frac{p}{2p−1}} )^{\frac{1}{p}} ,

and, using the Cauchy-Schwarz inequality, a further shift and Hölder’s inequality,

∑_{y∈ℤ^{d}}\{g_{1}(x + y) \sqrt{e^{h(x+y)} − 1} g_{2}(y) \sqrt{e^{h(y)} − 1}\}^{\frac{p}{2p−1}}

≤ ( ∑_{y∈ℤ^{d}} \{g_{1}(x + y) \sqrt{e^{h(x+y)} − 1}\}^{\frac{2p}{2p−1}} )^{\frac{1}{2}} ( ∑_{y∈ℤ^{d}} \{g_{2}(y) \sqrt{e^{h(y)} − 1}\}^{\frac{2p}{2p−1}} )^{\frac{1}{2}}

≤ ( ∑_{y∈ℤ^{d}} g_{1}^{2}(y))^{\frac{p}{4p−2}} ( ∑_{y∈ℤ^{d}} g_{2}^{2}(y))^{\frac{p}{4p−2}} ( ∑_{y∈ℤ^{d}} \{e^{h(y)} − 1\}^{q})^{\frac{p−1}{2p−1}} ≤ (e^{∥h∥_{q}} − 1)^{\frac{q}{q+1}} .

Combining all these estimates we obtain that

⟨g_{1}, 𝔄_{h}g_{2}⟩ ≤ ( ∑_{y∈ℤ^{d}} 𝔾(y)^{p})^{\frac{1}{p}} (e^{∥h∥_{q}} − 1),

which implies that 𝔄_{h} is bounded and its spectral radius satisfies (2). 2.2 Existence of the high moment limit of intersection local time We define the ‘augmented’ intersection local time I_{0} by

I_{0} := ∑_{i_{1},...,i_{p}=0}^{∞} 1l{X^{(1)}(i_{1}) = ⋯ = X^{(p)}(i_{p})} .

Lemma 4. The limit κ_{0} := − lim_{k→∞} \frac{1}{k} log \frac{𝔼[I_{0}^{k}]}{(k!)^{p}} exists.

Proof. By the subadditivity lemma it suffices to show that, for any k, l ≥ 1,

𝔼[I_{0}^{k+l}]^{1/p} ≤ \binom{k + l}{k} 𝔼[I_{0}^{k}]^{1/p} 𝔼[I_{0}^{l}]^{1/p} .  (8)

By X we denote a random walk with the same law as X^{(1)}, …, X^{(p)} and define its local time in x by ℓ(x) := ∑_{j=0}^{∞} 1l{X(j) = x}. Then

𝔼[I_{0}^{k+l}] = ∑_{x_{1},...,x_{k+l}∈ℤ^{d}} {𝔼 ∏_{j=1}^{k+l} ℓ(x_{j})}^{p}

= ∑_{x_{1},...,x_{k+l}∈ℤ^{d}} { ∑_{i_{1},...,i_{k+l}=0}^{∞} 𝔼 ∏_{j=1}^{k+l} 1l{X(i_{j}) = x_{j}}}{𝔼 ∏_{j=1}^{k+l} ℓ(x_{j})}^{p−1}

= ∑_{i_{1},...,i_{k+l}=0}^{∞} ∑_{x_{1},...,x_{k+l}∈ℤ^{d}} {𝔼 ∏_{j=1}^{k+l} 1l{X(i_{j}) = x_{j}}}{𝔼 ∏_{j=1}^{k+l} ℓ(x_{j})}^{p−1}.

For any two vectors (j_{1}, …, j_{k}) and (j_{k+1}, …, j_{k+l}) we write

(j_{1}, …, j_{k}) ≺ (j_{k+1}, …, j_{k+l}) ⟺ max{j_{1}, …, j_{k}} ≤ min{j_{k+1}, …, j_{k+l}} .

Instead of choosing the vector (i_{1}, …, i_{k+l}) directly, we may first pick k out of k + l coordinates, then pick two vectors (j_{1}, …, j_{k}) ≺ (j_{k+1}, …, j_{k+l}) and fill the chosen k coordinates successively with the entries of (j_{1}, …, j_{k}) and the remaining coordinates with the entries of (j_{k+1}, …, j_{k+l}). Using this procedure and the permutation invariance we get

𝔼[I_{0}^{k+l}] ≤ \binom{k + l}{k} ∑_{{(i_{1},...,i_{k}) \atop ≺(i_{k+1},...,i_{k+l})}} ∑_{x_{1},...,x_{k+l}} \{𝔼 ∏_{j=1}^{k+l} 1l\{X(i_{j}) = x_{j}\}\}\{𝔼 ∏_{j=1}^{k+l} ℓ(x_{j})\}^{p−1}.

Thus, using Hölder’s inequality in the second step,

\begin{matrix}𝔼 & [I_{0}^{k+l}] ≤ \binom{k + l}{k} ∑_{x_{1},...,x_{k+l}} \{ ∑_{{(i_{1},...,i_{k}) \atop ≺(i_{k+1},...,i_{k+l})}} 𝔼 ∏_{j=1}^{k+l} 1l\{X(i_{j}) = x_{j}\}\}\{𝔼 ∏_{j=1}^{k+l} ℓ(x_{j})\}^{p−1} \\ ≤ \binom{k + l}{k} \{ ∑_{x_{1},...,x_{k+l}} ( ∑_{{(i_{1},...,i_{k}) \atop ≺(i_{k+1},...,i_{k+l})}} 𝔼 ∏_{j=1}^{k+l} 1l\{X(i_{j}) = x_{j}\})^{p}\}^{\frac{1}{p}} \{ ∑_{x_{1},...,x_{k+l}} (𝔼 ∏_{j=1}^{k+l} ℓ(x_{j}))^{p}\}^{\frac{p−1}{p}} . \end{matrix}

As the last factor equals (𝔼[I_{0}^{k+l}])^{\frac{p−1}{p}} we get

(𝔼[I_{0}^{k+l}])^{\frac{1}{p}} ≤ \binom{k + l}{k} \{ ∑_{x_{1},...,x_{k+l}∈ℤ^{d}} ( ∑_{{(i_{1},...,i_{k}) \atop ≺(i_{k+1},...,i_{k+l})}} 𝔼 ∏_{j=1}^{k+l} 1l\{X(i_{j}) = x_{j}\})^{p}\}^{\frac{1}{p}} .  (9)

Writing i_{∗} = max{i_{1}, …, i_{k}} we have

𝔼 ∏_{j=1}^{k+l} 1l{X(i_{j}) = x_{j}} = {𝔼 ∏_{j=1}^{k} 1l{X(i_{j}) = x_{j}}}{𝔼 ∏_{j=k+1}^{k+l} 1l{X(i_{j} − i_{∗}) = x_{j} − x_{i_{∗}}}},

10 XIA CHEN AND PETER MÖRTERS

and therefore

∑_{{(i_{1},...,i_{k}) \atop ≺(i_{k+1},...,i_{k+l})}}𝔼 ∏_{j=1}^{k+l} 1l\{X(i_{j}) = x_{j}\}

= ∑_{i_{1},...,i_{k}=0}^{∞} {𝔼 ∏_{j=1}^{k} 1l{X(i_{j}) = x_{j}}}{ ∑_{i_{k+1},...,i_{k+l}=0}^{∞} 𝔼 ∏_{j=k+1}^{k+l} 1l{X(i_{j}) = x_{j} − x_{i_{∗}}}}

= ∑_{i_{1},...,i_{k}=0}^{∞} {𝔼 ∏_{j=1}^{k} 1l{X(i_{j}) = x_{j}}}{𝔼 ∏_{j=k+1}^{k+l} ℓ(x_{j} − x_{i_{∗}})}.

Thus

∑_{x_{1},...,x_{k+l}∈ℤ^{d}} \{ ∑_{{(i_{1},...,i_{k}) \atop ≺(i_{k+1},...,i_{k+l})}} 𝔼 ∏_{j=1}^{k+l} 1l\{X(i_{j}) = x_{j}\}\}^{p}

= ∑_{x_{1},...,x_{k+l}∈ℤ^{d}} ∏_{h=1}^{p} ( ∑_{i_{1}^{h},...,i_{k}^{h}=0}^{∞} {𝔼 ∏_{j=1}^{k} 1l{X(i_{j}^{h}) = x_{j}}}{𝔼 ∏_{j=k+1}^{k+l} ℓ(x_{j} − x_{i_{∗}^{h}})})

= ∑_{x_{1},...,x_{k}∈ℤ^{d}} ( ∏_{h=1}^{p} ∑_{i_{1}^{h},...,i_{k}^{h}=0}^{∞} {𝔼 ∏_{j=1}^{k} 1l{X(i_{j}^{h}) = x_{j}}}) ∑_{x_{k+1},...,x_{k+l}∈ℤ^{d}} ∏_{h=1}^{p} {𝔼 ∏_{j=k+1}^{k+l} ℓ(x_{j} − x_{i_{∗}^{h}})} .

By Hölder’s inequality

\begin{aligned}∑_{x_{k+1},...,x_{k+l}∈ℤ^{d}} & ∏_{h=1}^{p} \{𝔼 ∏_{j=k+1}^{k+l} ℓ(x_{j} − x_{i_{∗}^{h}})\} \\ & ≤ ∏_{h=1}^{p} \{ ∑_{x_{k+1},...,x_{k+l}∈ℤ^{d}} \{𝔼 ∏_{j=k+1}^{k+l} ℓ(x_{j} − x_{i_{∗}^{h}})\}^{p}\}^{1/p} = 𝔼[I_{0}^{l}], \end{aligned}

and thus

\begin{aligned}∑_{x_{1},...,x_{k+l}∈ℤ^{d}} & \{ ∑_{{(i_{1},...,i_{k}) \atop ≺(i_{k+1},...,i_{k+l})}} 𝔼 ∏_{j=1}^{k+l} 1l\{X(i_{j}) = x_{j}\}\}^{p} \\ & ≤ 𝔼[I_{0}^{l}] ∑_{x_{1},...,x_{k}∈ℤ^{d}} ∏_{h=1}^{p} ∑_{i_{1}^{h},...,i_{k}^{h}=0}^{∞} \{𝔼 ∏_{j=1}^{k} 1l\{X(i_{j}^{h}) = x_{j}\}\} = 𝔼[I_{0}^{l}]𝔼[I_{0}^{k}], \end{aligned}

which together with (9) proves (8) and thus completes the proof. □

Lemma 5. The limit κ := − lim_{k→∞} \frac{1}{k} log \frac{𝔼[I^{k}]}{(k!)^{p}} exists and is equal to κ_{0}. Proof. To make the passage from I_{0} to I first note that I ≤ I_{0}, and hence we have

lim sup_{k→∞} \frac{1}{k} log \frac{1}{(k!)^{p}} 𝔼[I^{k}] ≤ −κ_{0} .

Hence only the converse inequality needs to be proved. Define the local times

ℓ_{j}(x) := ∑_{k=0}^{∞} 1l{X^{(j)}(k) = x} for x ∈ ℤ^{d} .

Then we obtain

I_{0} ≤ I + ∑_{j=1}^{p} ∏_{{i=1 \atop i≠j}}^{p} ℓ_{i}(0) ,

and thus, by the triangle inequality,

𝔼[I_{0}^{k}]^{1/k} ≤ 𝔼[I^{k}]^{1/k} + 𝔼[( ∑_{j=1}^{p} ∏_{{i=1 \atop i≠j}}^{p} ℓ_{i}(0))^{k}]^{1/k}.  (10)

For the second term we get, using the multinomial theorem,

𝔼[( ∑_{j=1}^{p} ∏_{{i=1 \atop i≠j}}^{p} ℓ_{i}(0))^{k}] = ∑_{{k_{1}+···+kp=k \atop k_{1},...,kp≥0}} \frac{k!}{k_{1}! ⋯ k_{p}!} ∏_{i=1}^{p} 𝔼[ℓ_{i}(0)^{∑_{j≠i} k_{j}}] .

As X = ℓ_{i}(0) is a geometric random variable and hence 𝔼[e^{λX}] < ∞ for some λ > 0, we get

𝔼[ℓ_{i}(0)^{n}] ≤ n! 𝔼[e^{λX}] λ^{−n}.

Hence, for a suitable constant C > 0,

𝔼[( ∑_{j=1}^{p} ∏_{{i=1 \atop i≠j}}^{p} ℓ_{i}(0))^{k}] ≤ 𝔼[e^{λX}]^{p} λ^{−k(p−1)} ∑_{{k_{1}+···+kp=k \atop k_{1},...,kp≥0}} \frac{k!}{k_{1}! ⋯ k_{p}!} ∏_{i=1}^{p} ( ∑_{{j=1 \atop j≠i}}^{p} k_{j})! ≤ C^{k} (k!)^{p−1} ,

which implies

lim inf_{k→∞} \frac{1}{k} log \frac{1}{(k!)^{p}} 𝔼[( ∑_{j=1}^{p} ∏_{{i=1 \atop i≠j}}^{p} ℓ_{i}(0))^{k}] = −∞ .

The result thus follows from (10). □

2.3 The integer moments of intersection local time

We define, for any 1 ≤ m ≤ k, the family of all m-partitions of the set {1, …, k} as

E_{m} := {π = (π_{1}, …, π_{m}) : π_{j} ≠ ∅ with π_{i} ∩ π_{j} = ∅ for all i ≠ j and ⋃_{j=1}^{m} π_{j} = {1, …, k}},

where we assume that the elements π_{1}, …, π_{m} of an m-partition are ordered by increasing order of their minimal elements. To any (i_{1}, …, i_{k}) ∈ ℕ^{k} we associate

• a tuple (i_{1}^{∗}, …, i_{m}^{∗}) of distinct natural numbers such that {i_{1}, …, i_{k}} = {i_{1}^{∗}, …, i_{m}^{∗}} and elements in the tuple (i_{1}^{∗}, …, i_{m}^{∗}) appear in the order in which they appear first in (i_{1}, …, i_{k});

• an m-partition (π_{1}, …, π_{m}) ∈ E_{m} with i_{j} = i_{ℓ}^{∗} whenever j ∈ π_{ℓ}.

Conversely, given a tuple (j_{1}, …, j_{m}) of distinct natural numbers and an m-partition π we can find (i_{1}, …, i_{k}) ∈ ℕ^{k} such that the induced m-tuple is (j_{1}, …, j_{m}) and the induced m-partition is π.

Define the family of k-tuples of points in ℤ^{d} associated to some π ∈ E_{m} by

A(π) := {(x_{1}, …, x_{k}) ∈ (ℤ^{d})^{k} : x_{i} = x_{j} for all i, j ∈ π_{ℓ} and ℓ ∈ {1, …, m} }.

For any (x_{1}, …, x_{k}) ∈ A(π) and for any 1 ≤ ℓ ≤ m, we use x_{π_{ℓ}} for the common value of {x_{j} : j ∈ π_{ℓ}}. Observing that

X(i_{ℓ}) = x_{ℓ} for all ℓ ∈ {1, …, k}
⇔ (x_{1}, …, x_{k}) ∈ A(π) and X(i_{ℓ}^{∗}) = x_{π_{ℓ}} for all ℓ ∈ {1, …, m} ,

we get that

𝔼[I^{k}] = ∑_{x_{1},...,x_{k}∈ℤ^{d}} ( ∑_{i_{1},...,i_{k}} 𝔼 ∏_{ℓ=1}^{k} 1l{X(i_{ℓ}) = x_{ℓ}})^{p}

= ∑_{x_{1},...,x_{k}∈ℤ^{d}} ( ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(x_{1}, …, x_{k}) ∈ A(π)} ∑_{distinct^{j_{1},...,jm}} 𝔼 ∏_{ℓ=1}^{m} 1l{X(j_{ℓ}) = x_{π_{ℓ}}})^{p},

and therefore, using 𝔖_{m} to denote the symmetric group on m elements,

𝔼[I^{k}] = ∑_{x_{1},...,x_{k}∈ℤ^{d}} ( ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(x_{1}, …, x_{k}) ∈ A(π)} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} 𝔾(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}}))^{p} ,  (11)

where we use the convention that x_{π_{σ(0)}} := 0.

2.4 The lower bound in Theorem 2

Based on (11) we now complete the proof of the lower bound in Theorem 2. We will repeatedly make use of the following two simple facts:

• For any π ∈ E_{m}, the map

Φ: A(π) → (ℤ^{d})^{m}, (x_{1}, …, x_{k}) ↦ (x_{π_{1}}, …, x_{π_{m}})

is one-to-one and onto, i.e. a bijection.

• For any j_{1}, …, j_{m} ≥ 1 with j_{1} + ⋯ + j_{m} = k, we have

#\{π = (π_{1}, ⋯, π_{m}) ∈ E_{m} : #(π_{ℓ}) = j_{ℓ} for all ℓ ∈ \{1, …, m\}\} = \frac{1}{m!} \frac{k!}{j_{1}! ⋯ j_{m}!}.

Recall from our outline that, given Lemma 5, in order to verify the lower bound in Theorem 2 it suffices to establish the following lemma.

Lemma 6. If there exists h ≥ 0 with ∥h∥_{q} ≤ θ such that ∥𝔄_{h}∥ > 1, then

∑_{k=1}^{∞} \frac{θ^{k}}{k!} 𝔼[I^{k}]^{\frac{1}{p}} = ∞.

Proof. Let h ≥ 0 with ∥h∥_{q} ≤ θ. Then, using Hölder’s inequality in the first step,

θ^{k} 𝔼[I^{k}]^{\frac{1}{p}} ≥ ∑_{x_{1},...,x_{k}∈ℤ^{d}} ( ∏_{j=1}^{k} h(x_{j})) ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l\{(x_{1}, …, x_{k}) ∈ A(π)\} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} 𝔾(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}})

= ∑_{m=1}^{k} ∑_{σ∈𝔖_{m}} ∑_{π∈E_{m}} ∑_{x_{1},...,x_{k}∈ℤ^{d}} ( ∏_{ℓ=1}^{m} h(x_{π_{ℓ}})^{#(π_{ℓ})})( ∏_{ℓ=1}^{m} 𝔾(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}}))

= ∑_{m=1}^{k} ∑_{σ∈𝔖_{m}} ∑_{π∈E_{m}} ∑_{x_{1},...,x_{m}∈ℤ^{d}} ( ∏_{ℓ=1}^{m} h(x_{ℓ})^{#(π_{ℓ})})( ∏_{ℓ=1}^{m} 𝔾(x_{σ(ℓ)} − x_{σ(ℓ−1)})),

where we use the convention x_{σ(0)} := 0, and the last step follows from the one-to-one correspondence between A(π) and ℤ^{m}. Therefore,

\begin{aligned}θ^{k} 𝔼[I^{k}]^{\frac{1}{p}} & ≥ ∑_{m=1}^{k} m! ∑_{x_{1},...,x_{m}∈ℤ^{d}} ∑_{π∈E_{m}} ( ∏_{ℓ=1}^{m} h(x_{ℓ})^{#(π_{ℓ})})( ∏_{ℓ=1}^{m} 𝔾(x_{ℓ} − x_{ℓ−1})) \\ & = ∑_{m=1}^{k} ∑_{x_{1},...,x_{m}∈ℤ^{d}} ∑_{{j_{1}+···+jm=k \atop j_{1},...,jm≥1}} \frac{k!}{j_{1}! ⋯ j_{m}!}( ∏_{ℓ=1}^{m} h(x_{ℓ})^{j_{ℓ}})( ∏_{ℓ=1}^{m} 𝔾(x_{ℓ} − x_{ℓ−1})), \end{aligned}

where we use the convention x_{0} := 0. Thus

\begin{aligned}∑_{k=1}^{∞} \frac{θ^{k}}{k!} 𝔼[I^{k}]^{\frac{1}{p}} & ≥ ∑_{m=1}^{∞} ∑_{k=m}^{∞} ∑_{x_{1},...,x_{m}} \{ ∑_{{j_{1}+···+jm=k \atop j_{1},...,jm≥1}} \frac{1}{j_{1}! ⋯ j_{m}!}( ∏_{ℓ=1}^{m} h(x_{ℓ})^{j_{ℓ}})\}( ∏_{ℓ=1}^{m} 𝔾(x_{ℓ} − x_{ℓ−1})) \\ & = ∑_{m=1}^{∞} ∑_{x_{1},...,x_{m}} \{ ∏_{ℓ=1}^{m} ∑_{j=1}^{∞} \frac{h(x_{ℓ})^{j}}{j!} \}( ∏_{ℓ=1}^{m} 𝔾(x_{ℓ} − x_{ℓ−1})) \\ & = ∑_{m=1}^{∞} ∑_{x_{1},...,x_{m}} ∏_{ℓ=1}^{m} (e^{h(x_{ℓ})} − 1) 𝔾(x_{ℓ} − x_{ℓ−1}) . \end{aligned} (12)

Now assume that h additionally satisfies ∥𝔄_{h}∥ > 1. Fix ε > 0 such that ∥𝔄_{h}∥ > e^{ε} and g ≥ 0 with ∥g∥_{2} = 1 such that ⟨g, 𝔄_{h}g⟩ > e^{ε}. By monotone convergence we may find a finite set A ⊂ ℤ^{d} such that

⟨g1l_{A}, 𝔄_{h}(g1l_{A})⟩ > e^{ε} and ∥g1l_{A}∥_{2} > e^{−ε},

and additionally, but without loss of generality, g, h > 0 on A. We infer that there exists δ > 0 with

( inf_{y∈A} 𝔾(y)) (e^{h(x)} − 1) ≥ δ g^{2}(x) 1l_{A}(x) for all x ∈ ℤ^{d}.

Hence

∑_{x_{1},...,x_{m}∈ℤ^{d}} ∏_{ℓ=1}^{m} (e^{h(x_{ℓ})} − 1) 𝔾(x_{ℓ} − x_{ℓ−1})

= ∑_{x_{1},...,x_{m}∈ℤ^{d}} 𝔾(x_{1}) \sqrt{e^{h(x_{1})} − 1} [ ∏_{ℓ=2}^{m} \sqrt{e^{h(x_{ℓ−1})} − 1} 𝔾(x_{ℓ} − x_{ℓ−1}) \sqrt{e^{h(x_{ℓ})} − 1}] \sqrt{e^{h(x_{m})} − 1}

≥ δ ∑_{x_{1},...,x_{m}∈ℤ^{d}} g(x_{1})1l_{A}(x_{1}) [ ∏_{ℓ=2}^{m} \sqrt{e^{h(x_{ℓ−1})} − 1} 𝔾(x_{ℓ} − x_{ℓ−1})\sqrt{e^{h(x_{ℓ})} − 1}] g(x_{m})1l_{A}(x_{m})

= δ⟨g1l_{A}, 𝔄_{h}^{m−1}(g1l_{A})⟩ .

By the spectral theorem, see for example [He82, 79.1], for any g̃ ∈ L^{2}(ℤ^{d}) with ∥g̃∥_{2} = 1 there exists a probability measure μg̃ such that, for every k ≥ 0,

⟨g̃, 𝔄_{h}^{k}g̃⟩ = ∫_{−∞}^{∞} θ^{k} μg̃(dθ) ,

and consequently, at least for even k,

⟨g̃, 𝔄_{h}^{k}g̃⟩ = ∫_{−∞}^{∞} θ^{k} μg̃(dθ) ≥ ( ∫_{−∞}^{∞} θ μg̃(dθ))^{k} = ⟨g̃, 𝔄_{h}g̃⟩^{k}.

We infer that

lim inf_{{m↑∞ \atop m odd}} \frac{1}{m} log ∑_{x_{1},...,x_{m}∈ℤ^{d}} ∏_{ℓ=1}^{m} (e^{h(x_{ℓ})} − 1)𝔾(x_{ℓ} − x_{ℓ−1})
≥ log ⟨g1l_{A}, 𝔄_{h}(g1l_{A})⟩ + log ∥g1l_{A}∥_{2} > 0 .

Combining this with (12) we see that the series ∑ \frac{θ^{k}}{k!} 𝔼[I^{k}]^{\frac{1}{p}} diverges, as claimed. □

2.5 The upper bound for intersections in a finite set

We now assume that A ⊂ ℤ^{d} is a finite set and consider the intersection local time restricted to the set A, which is defined as I(A) in Remark 1(b). The arguments of Section 2.3 show that

𝔼[I(A)^{k}] = ∑_{x_{1},...,x_{k}∈A} [ ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(x_{1}, …, x_{k}) ∈ A(π)} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} 𝔾(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}})]^{p}.

We now provide an upper bound for the asymptotics of this expression as k ↑ ∞, replacing (for later reference) Green’s function wherever it occurs by an arbitrary symmetric kernel.

Lemma 7. Suppose G: ℤ^{d} → (0, ∞) is symmetric. Then

lim sup_{k↑∞} \frac{1}{k} log \frac{1}{k!} ∑_{x_{1},...,x_{k}∈A}[ ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l\{(x_{1}, …, x_{k}) ∈ A(π)\} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}})]^{p}
≤ −p log inf {∥h∥_{q} : h ≥ 0, supp h ⊂ A with ∥𝔄_{h}∥ ≥ 1},

where the operator 𝔄_{h} is associated with the kernel G.

Remark 5. With this lemma we have completed the proof of Remark 1(b). Indeed, the lower bound for the asymptotics of the intersection local times I(A) in a finite set A follows from the arguments in Sections 2.1 and 2.3 simply replacing ℤ^{d} by A. For the upper bound use Lemma 7 with G = 𝔾. □

Proof. Fix a vector x = (x_{1}, …, x_{k}) of length k with entries from the set A and associate its empirical measure L_{k}^{x} by letting

L_{k}^{x} := \frac{1}{k} ∑_{j=1}^{k} δ_{x_{j}} .

For each τ ∈ 𝔖_{k} and π ∈ E_{m} we denote by τ(π) ∈ E_{m} the partition consisting of the sets τ(π)_{ℓ} := τ(π_{ℓ}) for ℓ ∈ {1 …, m}. Then, for any τ ∈ 𝔖_{k} and x = (x_{1}, …, x_{k}), we get

∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(x_{1}, …, x_{k}) ∈ A(π)} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}})

= ∑_{y_{1},...,y_{k}∈A} 1l{x = y ∘ τ} ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(y_{1}, …, y_{k}) ∈ A(τ(π))} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(y_{τ(π_{σ(ℓ)})} − y_{τ(π_{σ(ℓ−1)})})

= ∑_{y_{1},...,y_{k}∈A} 1l{x = y ∘ τ} ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(y_{1}, …, y_{k}) ∈ A(π)} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}) ,

where we use the conventions y_{τ(π_{σ(0)})} := 0, y_{π_{σ(0)}} := 0.

UPPER TAILS FOR INTERSECTIONS OF RANDOM WALK 15

Observe that, abbreviating μ = L_{k}^{x} and assuming L_{k}^{y} = L_{k}^{x}, we have

∑_{τ∈𝔖_{k}} 1l{x = y ∘ τ} = ∏_{x∈A} (kμ(x))! ,

and hence summing the previous expression over all permutations τ ∈ 𝔖_{k} gives

\begin{aligned}k! & ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l\{(x_{1}, …, x_{k}) ∈ A(π)\} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}}) \\ & = ∏_{x∈A} (kμ(x))! ∑_{y_{1},...,y_{k}} 1l\{L_{k}^{y} = μ\} ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l\{(y_{1}, …, y_{k}) ∈ A(π)\} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}) . \end{aligned}

Write ϕ_{μ}(x) = μ(x)^{1/q} for all x ∈ A and note that

∑_{y_{1},...,y_{k}}1l{L_{k}^{y} = μ} ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(y_{1}, …, y_{k}) ∈ A(π)} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}})

≤ ( ∏_{x∈A} ϕ_{μ}(x)^{−kμ(x)}) ∑_{y_{1},...,y_{k}} ϕ_{μ}(y_{1}) ⋯ ϕ_{μ}(y_{k}) ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(y_{1}, …, y_{k}) ∈ A(π)}

× ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}) .

Simplifying and finally using the expression for #E_{m}, we obtain

\begin{aligned}∑_{y_{1},...,y_{k}} & ϕ_{μ}(y_{1}) ⋯ ϕ_{μ}(y_{k}) ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l\{(y_{1}, …, y_{k}) ∈ A(π)\} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}) \\ & = ∑_{m=1}^{k} ∑_{π∈E_{m}} ∑_{y_{1},...,y_{k}} 1l\{(y_{1}, …, y_{k}) ∈ A(π)\}\{ ∏_{ℓ=1}^{m} ϕ_{μ}(y_{π_{ℓ}})^{#(π_{ℓ})}\} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}) \end{aligned}

= ∑_{m=1}^{k} ∑_{π∈E_{m}} ∑_{y_{1},...,y_{m}} { ∏_{ℓ=1}^{m} ϕ_{μ}(y_{ℓ})^{#(π_{ℓ})}} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(y_{σ(ℓ)} − y_{σ(ℓ−1)})

= ∑_{m=1}^{k} m! ∑_{y_{1},...,y_{m}} { ∑_{π∈E_{m}} ∏_{ℓ=1}^{m} ϕ_{μ}(y_{ℓ})^{#(π_{ℓ})}} ∏_{ℓ=1}^{m} G(y_{ℓ} − y_{ℓ−1})

= ∑_{m=1}^{k} ∑_{y_{1},...,y_{m}} \{ ∑_{{j_{1}+···+jm=k \atop j_{1},...,jm≥1}} \frac{k!}{j_{1}! ⋯ j_{m}!} ∏_{ℓ=1}^{m} ϕ_{μ}(y_{ℓ})^{j_{ℓ}}\} ∏_{ℓ=1}^{m} G(y_{ℓ} − y_{ℓ−1}).

Further, using Stirling’s formula, we obtain a fixed polynomial P (·), depending only on the cardinality of A, such that

\{ ∏_{x∈A} (kμ(x))!\} \{ ∏_{x∈A} ϕ_{μ}(x)^{−kμ(x)}\} ≤ P (k) k! \{ ∏_{j=1}^{k} μ(x_{j})^{\frac{1}{p}} \} .

Summarizing all what we have got so far

\begin{aligned}∑_{m=1}^{k} & ∑_{π∈E_{m}} 1l\{(x_{1}, …, x_{k}) ∈ A(π)\} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}}) \\ & ≤ P (k) k! \{ ∏_{j=1}^{k} μ(x_{j})^{\frac{1}{p}} \} ∑_{m=1}^{k} ∑_{y_{1},...,y_{m}∈A} \{ ∑_{{j_{1}+···+jm=k \atop j_{1},...,jm≥1}} \frac{1}{j_{1}! ⋯ j_{m}!} ∏_{ℓ=1}^{m} ϕ_{μ}^{j_{ℓ}}(y_{ℓ})\} ∏_{ℓ=1}^{m} G(y_{ℓ} − y_{ℓ−1}) . \end{aligned}

Summing over all possible vectors x = (x_{1}, …, x_{k}) gives

\begin{aligned}I_{k} & := ∑_{x_{1},...,x_{k}∈A} [ ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l\{(x_{1}, …, x_{k}) ∈ A(π)\} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} G(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}})]^{p} \\ & ≤ P (k)^{p} (k!)^{p} sup_{μ∈P_{k}(A)} [ ∑_{m=1}^{k} ∑_{y_{1},...,y_{m}∈A} ( ∑_{{j_{1}+···+jm=k \atop j_{1},...,jm≥1}} \frac{1}{j_{1}! ⋯ j_{m}!} ∏_{ℓ=1}^{m} ϕ_{μ}^{j_{ℓ}}(y_{ℓ})) ∏_{ℓ=1}^{m} G(y_{ℓ} − y_{ℓ−1})]^{p}, \end{aligned}

where P_{k}(A) stands for the set of probability densities ν on A such that ν(x) is of the form i/k. Recall that ϕ_{μ} ≥ 0 satisfies ∥ϕ_{μ}∥_{q} = 1 and hence we may replace the supremum by one over all L^{q}-normalised nonnegative functions on A. Thus, for every θ > 0,

\frac{θ^{k}}{k!} (I_{k})^{\frac{1}{p}} ≤ P (k) sup_{∥f∥_{q}=1} ∑_{n=1}^{∞} θ^{n} ∑_{m=1}^{n} ∑_{y_{1},...,y_{m}∈A} ( ∑_{{j_{1}+···+jm=n \atop j_{1},...,jm≥1}} \frac{1}{j_{1}! ⋯ j_{m}!} ∏_{ℓ=1}^{m} f^{j_{ℓ}}(y_{ℓ})) ∏_{ℓ=1}^{m} G(y_{ℓ} − y_{ℓ−1})

= P (k) sup_{∥h∥_{q}=θ} ∑_{m=1}^{∞} ∑_{y_{1},...,y_{m}∈A} \{ ∏_{ℓ=1}^{m} ∑_{j=1}^{∞} \frac{h(y_{ℓ})^{j}}{j!} \} ∏_{ℓ=1}^{m} G(y_{ℓ} − y_{ℓ−1})

= P (k) sup_{∥h∥_{q}=θ} ∑_{m=1}^{∞} ∑_{y_{1},...,y_{m}∈A} { ∏_{ℓ=1}^{m} (e^{h(y_{ℓ})} − 1)} ∏_{ℓ=1}^{m} G(y_{ℓ} − y_{ℓ−1}).

Let g(x) = [#A]^{−1/2} for all x ∈ A and note that ∥g∥_{2} = 1. Using that 0 ≤ h(x) ≤ θ we obtain

∑_{y_{1},...,y_{m}∈A}{ ∏_{ℓ=1}^{m} (e^{h(y_{ℓ})} − 1)} ∏_{ℓ=1}^{m} G(y_{ℓ} − y_{ℓ−1})

≤ ( sup_{y∈A} G(y)) (e^{θ} − 1) ∑_{y_{1},...,y_{m}∈A} ∏_{ℓ=2}^{m} \{\sqrt{e^{h(y_{ℓ−1})} − 1} G(y_{ℓ} − y_{ℓ−1}) \sqrt{e^{h(y_{ℓ})} − 1}\}

= ( sup_{y∈A} G(y)) (e^{θ} − 1) [#A] ⟨g, 𝔄_{h}^{m−1}g⟩

≤ ( sup_{y∈A} G(y)) (e^{θ} − 1) [#A] ∥𝔄_{h}∥^{m−1} .

Suppose that θ < inf{∥h∥_{q} : supp h ⊂ A, ∥𝔄_{h}∥ ≥ 1}, then there exists ϵ > 0 such that every h with ∥h∥_{q} = θ satisfies ∥𝔄_{h}∥ < 1 − ϵ. We infer that

\frac{θ^{k}}{k!} (I_{k})^{\frac{1}{p}} ≤ P (k) ( sup_{y∈A} G(y)) (e^{θ} − 1) [#A] sup_{∥h∥_{q}=θ} ∑_{m=1}^{∞} ∥𝔄_{h}∥^{m−1}.

As the suprema on the right hand side are both finite, we obtain

lim sup_{k→∞} \frac{1}{k} log \frac{I_{k}}{(k!)^{p}} ≤ −p log θ ,

as required to complete the proof. □

2.6 Wrapping the random walks around the torus We now look back to the full lattice ℤ^{d} and discuss how to project the problem onto a finite set. We fix a large integer N an let A_{N} := [−N, N)^{d}. Then every x ∈ ℤ^{d} can uniquely be written as x = 2Nz + y for z ∈ ℤ^{d} and y ∈ A_{N}. Hence, using Hölder’s inequality in the second step,

𝔼[I^{k}] = ∑_{y_{1},...,y_{k}∈A_{N}} ∑_{z_{1},...,z_{k}∈ℤ^{d}} [ ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(2Nz_{1} + y_{1}, …, 2Nz_{k} + y_{k}) ∈ A(π)}

× ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} 𝔾(2N(z_{π_{σ(ℓ)}} − z_{π_{σ(ℓ−1)}}) + (y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}))]^{p}

≤ ∑_{y_{1},...,y_{k}∈A_{N}} [ ∑_{m=1}^{k} ∑_{π∈E_{m}} ∑_{σ∈𝔖_{m}} { ∑_{z_{1},...,z_{k}∈ℤ^{d}} 1l{(2Nz_{1} + y_{1}, …, 2Nz_{k} + y_{k}) ∈ A(π)}

× ∏_{ℓ=1}^{m} 𝔾^{p}(2N(z_{π_{σ(ℓ)}} − z_{π_{σ(ℓ−1)}}) + (y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}))}^{1/p}]^{p} .

From the uniqueness of the decomposition x = 2Nz + y we infer that

1l{(2Nz_{1} + y_{1}, …, 2Nz_{k} + y_{k}) ∈ A(π)} = 1l{(y_{1}, …, y_{k}) ∈ A(π)} 1l{(z_{1}, …, z_{k}) ∈ A(π)}.

Therefore,

∑_{z_{1},...,z_{k}∈ℤ^{d}}1l{(2Nz_{1} + y_{1}, …, 2Nz_{k} + y_{k}) ∈ A(π)} ∏_{ℓ=1}^{m} 𝔾^{p}(2N(z_{π_{σ(ℓ)}} − z_{π_{σ(ℓ−1)}}) + (y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}))

= 1l{(y_{1}, …, y_{k}) ∈ A(π)} ∑_{z_{1},...,z_{k}∈ℤ^{d}} 1l{(z_{1}, …, z_{k}) ∈ A(π)}

× ∏_{ℓ=1}^{m} 𝔾^{p}(2N(z_{π_{σ(ℓ)}} − z_{π_{σ(ℓ−1)}}) + (y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}))

\begin{matrix}= 1l\{(y_{1}, …, y_{k}) ∈ A(π)\} ∑_{z_{1},...,z_{m}∈ℤ^{d}} ∏_{ℓ=1}^{m} 𝔾^{p}(2N(z_{σ(ℓ)} − z_{σ(ℓ−1)}) + (y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}})) \\ = 1l\{(y_{1}, …, y_{k}) ∈ A(π)\} ∏_{ℓ=1}^{m} 𝔾̃_{N}^{p}(y_{π_{σ(ℓ)}} − y_{π_{σ(ℓ−1)}}) , \end{matrix}

where we define

𝔾̃_{N}(y) = \{ ∑_{z∈ℤ^{d}} 𝔾^{p}(2Nz + y)\}^{\frac{1}{p}} for any y ∈ ℤ^{d} .

Summarizing, we have shown that

𝔼[I^{k}] ≤ ∑_{x_{1},...,x_{k}∈A_{N}} [ ∑_{m=1}^{k} ∑_{π∈E_{m}} 1l{(x_{1}, …, x_{k}) ∈ A(π)} ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{m} 𝔾̃_{N}(x_{π_{σ(ℓ)}} − x_{π_{σ(ℓ−1)}})]^{p} .

We can now apply Lemma 7 and obtain

lim sup_{k↑∞} \frac{1}{k} log \frac{1}{k!} 𝔼[I^{k}] ≤ −p log inf \{∥h∥_{q} : h ≥ 0, supp h ⊂ A_{N} with ∥𝔄̃_{h,N}∥ ≥ 1\},

where the self-adjoint operator 𝔄̃_{h,N}: L^{2}(ℤ^{d}) → L^{2}(ℤ^{d}) is defined by

𝔄̃_{h,N}g(x) = \sqrt{e^{h(x)} − 1} ∑_{y∈A_{N}} 𝔾̃_{N}(x − y) \sqrt{e^{h(y)} − 1} g(y) .

2.7 The upper bound in Theorem 2

The proof of Theorem 2 is complete once we have proved the following lemma.

Lemma 8.

lim sup_{N→∞} inf {∥h∥_{q} : h ≥ 0 with ∥𝔄̃_{h,N}∥ ≥ 1} ≥ inf {∥h∥_{q} : h ≥ 0 with ∥𝔄_{h}∥ ≥ 1}.

Proof. Fix positive integers M < N and define the annulus

E_{N} := {x ∈ A_{N}: |x| ≥ N − M} .

We decompose 𝔾 = 𝔾_{+} + 𝔾_{−} with 𝔾_{+}(x) = 𝔾(x)1l{|x| > M} and 𝔾_{−}(x) = 𝔾(x)1l{|x| ≤ M}. In analogy to 𝔾̃_{N} we define symmetric, periodic functions 𝔾̃_{+} and 𝔾̃_{−} by

𝔾̃_{±}(y) = \{ ∑_{z∈ℤ^{d}} 𝔾_{±}^{p}(2Nz + y)\}^{\frac{1}{p}} for any y ∈ ℤ^{d} .

By the triangle inequality we have 𝔾̃_{N} ≤ 𝔾̃_{+} + 𝔾̃_{−}. The induced operators 𝔄̃_{h,±}: L^{2}(A_{N}) → L^{2}(A_{N}) are defined by

𝔄̃_{h,±}g(x) = \sqrt{e^{h(x)} − 1} ∑_{y∈A_{N}} 𝔾̃_{±}(x − y) \sqrt{e^{h(y)} − 1} g(y) .

For the spectral radius of these operators we thus obtain

∥𝔄̃_{h,N}∥ ≤ ∥𝔄̃_{h,+}∥ + ∥𝔄̃_{h,−}∥ .

Suppose now that h: A_{N} → [0, ∞) is given and let h_{0} : ℤ^{d} → [0, ∞) its extension to the whole of ℤ^{d} defined by letting h_{0}(x) = 0 for x ∈ ℤ^{d} \ A_{N}. We next show that

∥𝔄̃_{h,N}∥ ≤ ∥𝔄_{h_{0}}∥ + (e^{∥h∥_{q}} − 1)\{\{ ∑_{|x|>M} 𝔾^{p}(x)\}^{\frac{1}{p}} + 2\{ ∑_{x∈ℤ^{d}} 𝔾^{p}(x)\}^{\frac{1}{p}} [\frac{#E_{N}}{(2N)^{d}} ]^{\frac{p−1}{p}} \}.  (13)

Using (13) we complete the proof by the following argument: For any t > 0 let

φ(t) := inf {∥h∥_{q} : h ≥ 0 with ∥𝔄_{h}∥ ≥ t}.

Note that, using that 𝔾 ∈ L^{p}(ℤ^{d}), by choosing first a large M and then an even larger N, we can make the expression in the curly bracket on the right hand side of (13) as small as we wish. Hence

lim sup_{N→∞} inf {∥h∥_{q} : h ≥ 0 with ∥𝔄̃_{h,N}∥ ≥ 1} ≥ φ(1 − ε),

for any ε > 0. As \frac{1}{1−ε}(e^{θ} − 1) ≤ exp\{\frac{θ}{1−ε}\} − 1 we obtain, from the definition of 𝔄_{h} that

∥𝔄_{\frac{h}{1−ε}} ∥ ≥ \frac{1}{1−ε} ∥𝔄_{h}∥ ,

whence φ(1 − ε) ≥ (1 − ε) φ(1), so that the statement of Lemma 8 follows by letting ε ↓ 0.

To prove (13) first fix g: A_{N} → [0, ∞) with ∥g∥_{2} = 1. For notational convenience we extend both g and h periodically to the whole lattice ℤ^{d}. We claim that there exists x_{0} ∈ A_{N} such that

∑_{x∈E_{N}} \{g(x + x_{0})\sqrt{e^{h(x+x_{0})} − 1}\}^{\frac{2p}{2p−1}} ≤ (e^{∥h∥_{q}} − 1)^{\frac{p}{2p−1}} \frac{#E_{N}}{(2N)^{d}} .  (14)

Indeed, this follows readily from

\begin{aligned}∑_{{x∈E_{N} \atop y∈A_{N}}} & \{g(x + y)\sqrt{e^{h(x+y)} − 1}\}^{\frac{2p}{2p−1}} ≤ \{ ∑_{{x∈E_{N} \atop y∈A_{N}}} g^{2}(x + y)\}^{\frac{p}{2p−1}} \{ ∑_{{x∈E_{N} \atop y∈A_{N}}} (e^{h(x+y)} − 1)^{\frac{p}{p−1}} \}^{\frac{p−1}{2p−1}} \\ & ≤ [#E_{N}] \{ ∑_{y∈A_{N}} (e^{h(y)} − 1)^{\frac{p}{p−1}} \}^{\frac{p−1}{2p−1}} ≤ [#E_{N}] (e^{∥h∥_{q}} − 1)^{\frac{p}{2p−1}} . \end{aligned}

We write h̄(x) = h(x + x_{0}) and ḡ(x) = g(x + x_{0}). Then

∑_{x,y∈A_{N}}g(x)\sqrt{e^{h(x)} − 1} 𝔾̃_{−}(x − y)\sqrt{e^{h(y)} − 1}g(y) = ∑_{x,y∈A_{N}} ḡ(x) \sqrt{e^{h̄(x)} − 1} 𝔾̃_{−}(x − y)\sqrt{e^{h̄(y)} − 1} ḡ(y)

≤ ∑_{x,y∈A_{N} \E_{N}} ḡ(x) \sqrt{e^{h̄(x)} − 1} 𝔾̃_{−}(x − y)\sqrt{e^{h̄(y)} − 1} ḡ(y)

+ 2 ∑_{{x∈E_{N} \atop y∈A_{N}}} ḡ(x) \sqrt{e^{h̄(x)} − 1} 𝔾̃_{−}(x − y)\sqrt{e^{h̄(y)} − 1} ḡ(y) .

From the fact that 𝔾̃_{−}(x − y) = 𝔾_{−}(x − y) when x, y ∈ A_{N} \ E_{N}, we infer that

∑_{x,y∈A_{N} \E_{N}} ḡ(x) \sqrt{e^{h̄(x)} − 1} 𝔾̃_{−}(x − y)\sqrt{e^{h̄(y)} − 1} ḡ(y) ≤ ∥𝔄_{h_{0}}∥ .

Moreover, from Hölder’s inequality,

∑_{{x∈E_{N} \atop y∈A_{N}}} ḡ(x) \sqrt{e^{h̄(x)} − 1} 𝔾̃_{−}(x − y)\sqrt{e^{h̄(y)} − 1} ḡ(y)

≤ \{ ∑_{x,y∈A_{N}} 𝔾̃_{−}^{p}(x − y)(\sqrt{(e^{h̄(x)} − 1)(e^{h̄(y)} − 1)}ḡ(x)ḡ(y))^{\frac{p}{2p−1}} \}^{\frac{1}{p}}

× \{ ∑_{{x∈E_{N} \atop y∈A_{N}}} (\sqrt{(e^{h̄(x)} − 1)(e^{h̄(y)} − 1)}ḡ(x)ḡ(y))^{\frac{2p}{2p−1}} \}^{\frac{p−1}{p}} .

To treat the first factor, note that, by periodicity,

\begin{aligned}∑_{x,y∈A_{N}} & 𝔾̃_{−}^{p}(x − y)(\sqrt{(e^{h̄(x)} − 1)(e^{h̄(y)} − 1)}ḡ(x)ḡ(y))^{\frac{p}{2p−1}} \\ & = ∑_{x∈A_{N}} 𝔾̃_{−}^{p}(x) ∑_{y∈A_{N}} (\sqrt{(e^{h̄(x+y)} − 1)(e^{h̄(y)} − 1)}ḡ(x + y)ḡ(y))^{\frac{p}{2p−1}} . \end{aligned}

Moreover, arguing as before using Hölder’s inequality,

∑_{y∈A_{N}}(\sqrt{(e^{h̄(x+y)} − 1)(e^{h̄(y)} − 1)}ḡ(x + y)ḡ(y))^{\frac{p}{2p−1}}

≤ \{ ∑_{y∈A_{N}} (ḡ(x + y)\sqrt{e^{h̄(x+y)} − 1})^{\frac{2p}{2p−1}} \}^{\frac{1}{2}} \{ ∑_{y∈A_{N}} (ḡ(y)\sqrt{e^{h̄(y)} − 1})^{\frac{2p}{2p−1}} \}^{\frac{1}{2}}

≤ \{ ∑_{y∈A_{N}} g^{2}(y)\}^{\frac{p}{2p−1}} \{ ∑_{y∈A_{N}} (e^{h(y)} − 1)^{\frac{p}{p−1}} \}^{\frac{p−1}{2p−1}} ≤ (e^{∥h∥_{q}} − 1)^{\frac{p}{2p−1}} .

For the second factor we obtain, using (14),

\begin{aligned}∑_{{x∈E_{N} \atop y∈A_{N}}} & (\sqrt{(e^{h̄(x)} − 1)(e^{h̄(y)} − 1)}ḡ(x)ḡ(y))^{\frac{2p}{2p−1}} \\ & = \{ ∑_{x∈E_{N}} (ḡ(x)\sqrt{e^{h̄(x)} − 1})^{\frac{2p}{2p−1}} \}\{ ∑_{y∈A_{N}} (ḡ(y)\sqrt{e^{h̄(y)} − 1})^{\frac{2p}{2p−1}} \} ≤ (e^{∥h∥_{q}} − 1)^{\frac{2p}{2p−1}} \frac{#E_{N}}{(2N)^{d}} . \end{aligned}

Summarizing, we have that

\begin{aligned}∥𝔄̃_{h,−}∥ & = sup_{∥g∥_{2}=1} ∑_{x,y∈A_{N}} g(x) \sqrt{e^{h(x)} − 1} 𝔾̃_{−}(x − y) \sqrt{e^{h(y)} − 1} g(y) \\ & ≤ ∥𝔄_{h_{0}}∥ + 2(e^{∥h∥_{q}} − 1) \{ ∑_{x∈ℤ^{d}} 𝔾^{p}(x)\}^{\frac{1}{p}} [\frac{#E_{N}}{(2N)^{d}} ]^{\frac{p−1}{p}} . \end{aligned}

In a similar fashion as above, or indeed as in Lemma 1, we also obtain that

∥𝔄̃_{h,+}∥ ≤ \{ ∑_{y∈A_{N}} 𝔾̃_{+}^{p}(y)\}^{\frac{1}{p}} (e^{∥h∥_{q}} − 1) = \{ ∑_{|x|>M} 𝔾^{p}(x)\}^{\frac{1}{p}} (e^{∥h∥_{q}} − 1) .

This proves (13) and hence completes the proof of the lemma. □

3. Random walks in continuous time: Proof of Theorem 3

3.1 Tail behaviour of the intersection local time In this section we prove that

lim_{a↑∞} \frac{1}{a^{1/p}} log ℙ\{Ĩ > a\} = −\frac{p}{ϱ} ,  (15)

where ϱ is as in Remark 3. As this is essentially a simpler version of the proof of Theorem 2, we only give a sketch, further details can be filled in easily by copying the methods of our main result. The proof is carried out in four steps.

In the first step we reduce the problem to an analytic problem. By (6) it suffices to prove

lim_{k↑∞} \frac{1}{k} log 𝔼[\frac{Ĩ^{k}}{(k!)^{p}} ] = p log ϱ .

Using the convention that x_{σ(0)} := 0, we get

𝔼Ĩ^{k} = 𝔼[ ∑_{x∈ℤ^{d}} ∏_{j=1}^{p} ∫_{0}^{∞} 1l{X^{(j)}(t) = x} dt]^{k} = ∑_{x_{1},...,x_{k}∈ℤ^{d}} [𝔼 ∫_{0}^{∞} dt_{1} ⋯ ∫_{0}^{∞} dt_{k} ∏_{ℓ=1}^{k} 1l{X(t_{ℓ}) = x_{ℓ}}]^{p}

= ∑_{x_{1},...,x_{k}∈ℤ^{d}} [ ∑_{σ∈𝔖_{k}} ∫_{0}^{∞} dt_{1} ∫_{t_{1}}^{∞} dt_{2} ⋯ ∫_{t_{k−1}}^{∞} dt_{k} 𝔼 ∏_{ℓ=1}^{k} 1l{X(t_{ℓ}) = x_{σ(ℓ)}}]^{p}

= ∑_{x_{1},...,x_{k}∈ℤ^{d}} [ ∑_{σ∈𝔖_{k}} ∏_{ℓ=1}^{k} G(x_{σ(ℓ−1)} − x_{σ(ℓ)})]^{p} ,

and hence it suffices to prove that

lim_{k→∞} \frac{1}{k} log \frac{1}{(k!)^{p}} ∑_{x_{1},...,x_{k}∈ℤ^{d}} [ ∑_{σ∈𝔖_{k}} ∏_{ℓ=1}^{k} G(x_{σ(ℓ−1)} − x_{σ(ℓ)})]^{p} = p log ρ .  (16)

In the second step we provide the lower bound for (16). Let q be the conjugate of p, and use Hölder’s inequality to obtain, for any nonnegative h ∈ L^{q}(ℤ^{d}) with ∥h∥_{q} = 1,

\frac{1}{k!} ( ∑_{x_{1},...,x_{k}∈ℤ^{d}} [ ∑_{σ∈𝔖_{k}} ∏_{ℓ=1}^{k} G(x_{σ(ℓ−1)} − x_{σ(ℓ)})]^{p})^{1/p} ≥ ∑_{x_{1},...,x_{k}∈ℤ^{d}} ∏_{ℓ=1}^{k} h(x_{ℓ}) G(x_{ℓ} − x_{ℓ−1}).

For any nonnegative f ∈ L^{2p}(ℤ^{d}) with ∥f∥_{2p} = 1 we define h := f^{2p/q} and g := f^{p} and note that ∥g∥_{2} = ∥h∥_{q} = 1 and f^{2p−1} = \sqrt{h}g. If we also fix a finite set A ⊂ ℤ^{d}, we can find a constant δ > 0 (depending on f and A) such that h(x) ≥ δg^{2}(x) for all x ∈ ℤ^{d}, and G(x) ≥ δ for all x ∈ A. Then

∑_{x_{1},...,x_{k}} ∏_{ℓ=1}^{k} h(x_{ℓ}) G(x_{ℓ} − x_{ℓ−1})

≥ δ^{2} ∑_{x_{1},...,x_{k}} g(x_{1})1l_{A}(x_{1}) [ ∏_{ℓ=2}^{k} \sqrt{h(x_{ℓ−1})} G(x_{ℓ} − x_{ℓ−1})\sqrt{h(x_{ℓ})}] g(x_{k})1l_{A}(x_{k})

= δ^{2} ⟨g1l_{A}, 𝔅_{h}^{k−1}g1l_{A}⟩ .

From the spectral theorem we infer that

lim inf_{k↑∞} \frac{1}{k} log ⟨g, 𝔅_{h}^{k−1}g⟩ ≥ log⟨g1l_{A}, 𝔅_{h}g1l_{A}⟩ + log ∥g1l_{A}∥_{2}

⟶^{A↑ℤ^{d}} log⟨f^{2p−1}, 𝔊f^{2p−1}⟩ ,

and the lower bound in (16) follows as f was arbitrary from the positive unit ball of L^{2p}(ℤ^{d}).

In the third step we show that, for any finite set A ⊂ ℤ^{d},

lim sup_{k→∞} \frac{1}{k} log \frac{1}{(k!)^{p}} ∑_{x_{1},...,x_{k}∈A} [ ∑_{σ∈𝔖_{k}} ∏_{ℓ=1}^{k} G(x_{σ(ℓ)} − x_{σ(ℓ−1)})]^{p}

≤ p log sup {⟨f^{2p−1}, 𝔊f^{2p−1}⟩: for f: ℤ^{d} → [0, ∞) with supp h ⊂ A and ∥f∥_{2p} = 1} ,

(17)

where (for later reference) we replace Green’s function wherever it occurs by an arbitrary symmetric kernel G: ℤ^{d} → [0, ∞). The same tilting technique as in Lemma 7 gives, for a suitable polynomial P, μ = L_{k}^{x} and ϕ(x) = μ(x)^{1/q},

∑_{σ∈𝔖_{k}} ∏_{ℓ=1}^{k} G(x_{σ(ℓ)} − x_{σ(ℓ−1)}) ≤ P (k) k! \{ ∏_{j=1}^{k} μ(x_{j})^{\frac{1}{p}} \} ∑_{y_{1},...,y_{k}∈A} ϕ(y_{1}) ⋯ ϕ(y_{k}) ∏_{ℓ=1}^{k} G(y_{ℓ} − y_{ℓ−1}) .

Therefore we obtain

\frac{1}{(k!)^{p}} ∑_{x_{1},...,x_{k}∈A} [ ∑_{σ∈𝔖_{k}} ∏_{ℓ=1}^{k} G(x_{σ(ℓ)} − x_{σ(ℓ−1)})]^{p}

= ∑_{x_{1},...,x_{k}∈A} exp {k ∑_{z∈A} μ(z) log μ(z) + o(k)} [ sup_{∥ϕ∥_{q}=1} ∑_{y_{1},...,y_{k}∈A} ϕ(y_{1}) ⋯ ϕ(y_{k}) ∏_{ℓ=1}^{k} G(y_{ℓ} − y_{ℓ−1})]^{p}

= e^{o(k)} [ sup_{∥ϕ∥_{q}=1} ∑_{y_{1},...,y_{k}∈A} ϕ(y_{1}) ⋯ ϕ(y_{k}) ∏_{ℓ=1}^{k} G(y_{ℓ} − y_{ℓ−1})]^{p} .

Let g(x) := [#A]^{−1/2}1l_{A}(x) so that ∥g∥_{2} = 1. Using that ϕ(x) ≤ 1 for all x ∈ A, we obtain

∑_{y_{1},...,y_{k}∈A} ϕ(y_{1}) ⋯ ϕ(y_{k}) ∏_{ℓ=1}^{k} G(y_{ℓ} − y_{ℓ−1}) ≤ [#A] ⟨g, 𝔅_{ϕ}^{k−1}g⟩ ≤ [#A] ∥𝔅_{ϕ}∥^{k−1},

from which the result readily follows.

In the fourth step we extend the result from finite sets to the full lattice ℤ^{d}. Projection on a torus as in Section 2.6 gives

∑_{x_{1},...,x_{k}∈ℤ^{d}} [ ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{k} G(x_{σ(ℓ)} − x_{σ(ℓ−1)})]^{p} ≤ ∑_{y_{1},...,y_{k}∈A_{N}} [ ∑_{σ∈𝔖_{k}} ∏_{ℓ=1}^{k} G̃_{N}(y_{σ(ℓ)} − y_{σ(ℓ−1)})]^{p},

where

G̃_{N}(x) := [ ∑_{z∈ℤ^{d}} G^{p}(2Nz + x)]^{1/p}.

Using (17) for this kernel gives

lim sup_{k→∞} \frac{1}{k} log \frac{1}{(k!)^{p}} ∑_{x_{1},...,x_{k}∈ℤ^{d}} [ ∑_{σ∈𝔖_{m}} ∏_{ℓ=1}^{k} G(x_{σ(ℓ)} − x_{σ(ℓ−1)})]^{p}

≤ p log sup {⟨f^{2p−1}, 𝔊_{N}f^{2p−1}⟩ : for f: ℤ^{d} → [0, ∞) with supp f ⊂ A_{N} and ∥f∥_{2p} = 1} ,

(18)

where the operator 𝔊_{N} stands for convolution with the kernel G̃_{N}. Exactly as in the proof of (13) one shows that, for 0 < M < N,

sup {⟨f^{2p−1}, 𝔊_{N}f^{2p−1}⟩ : for f: ℤ^{d} → [0, ∞) with supp f ⊂ A_{N} and ∥f∥_{2p} = 1}
≤ sup {⟨f^{2p−1}, 𝔊f^{2p−1}⟩ : for f: ℤ^{d} → [0, ∞) with ∥f∥_{2p} = 1}

+ [ ∑_{|x|>M} G^{p}(x)]^{1/p} + 2[\frac{#E_{N}}{(2N)^{d}} ]^{\frac{p−1}{p}} [ ∑_{x∈ℤ^{d}} G^{p}(x)]^{1/p} ,

where E_{N} := {x ∈ A_{N}: |x| > N −M}. The first term on the last line can be made arbitrarily small by choice of M. For any M the second term converges to zero as N ↑ ∞. This shows that, as N ↑ ∞, the variational problem on the right hand side of (18) converges to ϱ, thus completing the proof of (15).

4. Conclusion

We believe that the method of this paper opens up new avenues for the treatment of a wide range of intersection problems in supercritical dimensions, which are by no means limited to random walk. The major advantage of our approach over the established Donsker-Varadhan theory is its direct applicability to problems with an infinite time horizon. However, studying the upper tail behaviour of the intersection of the ranges requires additional ideas and is subject of ongoing research.

Acknowledgements: We thank the Mathematisches Forschungsinstitut Oberwolfach for enabling us to complete this work during a ‘Research in Pairs’ visit, and an anonymous referee for carefully reading our manuscript. Further thanks are due to Nadia Sidorova and Alexander Frolkin for providing numerical evidence allowing us to reject a conjecture that came up in the course of the work. The first author was supported in part by NSF grant DMS-0704024 and the second author by grant EP/C500299/1 and an Advanced Research Fellowship of EPSRC.

References

[AC07] A. Asselah and F. Castell. Self-intersection times for random walk and random walk in random scenery in dimensions d ≥ 5. Probab. Theory Related Fields 138: 1–32, 2007.

[BBH04] M. van den Berg, E. Bolthausen, and F. den Hollander. On the volume of the intersection of two Wiener sausages. Ann. Math. 159: 741–782, 2004.

[Ch04] X. Chen. Exponential asymptotics and law of the iterated logarithm for intersection local times of random walks. Ann. Probab., 32: 3248–3300, 2004.

[DV79] M.D. Donsker and S.R.S. Varadhan. On the number of distinct sites visited by a random walk. Comm. Pure Appl. Math., 32: 721–747, 1979.

[DE51] A. Dvoretzky and P. Erdős. Some problems on random walk in space. In: Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950. University of California Press, Berkeley and Los Angeles, pp. 353–367, 1951.

[FFS92] R. Fernández, J. Fröhlich and A. D. Sokal. Random walks, critical phenomena, and triviality in quantum field theory. Springer, New York (1992).

[FMW08] K. Fleischmann, P. Mörters and V. Wachtel. Moderate deviations for a random walk in random scenery. Stoch. Proc. Appl., 118: 1768–1802, 2008.

[GKS07] N. Gantert, W. König and Z. Shi. Annealed deviations of random walk in random scenery. Ann. Inst. H. Poincaré: Probab. Stat. 43: 47–76, 2007.

[HK01] Y. Hamana and H. Kesten. A large-deviation result for the range of random walk and for the Wiener sausage. Probab. Theory Related Fields 120: 183–208, 2001.

[He82] H. Heuser. Functional Analysis. Wiley, Chichester (1982).

[HKM06] R. van der Hofstad, W. König and P. Mörters. The universality classes in the parabolic Anderson model. Comm. Math. Phys. 267: 307-353, 2006.

[KM94] K.M. Khanin, A.E. Mazel, S.B. Shlosman and Ya.G. Sinai. Loop condensation effects in the behavior of random walks. In: Markov processes and applications, Birkhäuser, pp 167–184, 1994.

[KM02] W. König and P. Mörters. Brownian intersection local times: Upper tail asymptotics and thick points. Ann. Probab., 30: 1605–1656, 2002.

[La91] G.F. Lawler. Intersections of random walks. Birkhäuser, Boston (1991).

[LG86] J. F. Le Gall. Propriétés d’intersection des marches aléatoires. I. Convergence vers le temps local d’intersection. Comm. Math. Phys. 104: 471–507, 1986.

[MS93] N. Madras and G. Slade. The self-avoiding walk. Birkhäuser, Boston (1993).

[MR97] M. Marcus and J. Rosen. Laws of the iterated logarithm for intersections of random walks on ℤ^{4}. Ann. Inst. H. Poincaré Probab. Statist. 33: 37–66, 1997.

[Sz93] A.S. Sznitman. Brownian asymptotics in a Poissonian environment. Probab. Theory Related Fields 95: 155– 174, 1993.

[Uc98] K. Uchiyama. Wiener’s test for random walks with mean zero and finite variance. Ann. Probab. 26: 368– 376, 1998.

Xia Chen  Peter Mörters
Department of Mathematics  Department of Mathematical Sciences
University of Tennessee  University of Bath
Knoxville, TN 37996-1300  Bath BA2 7AY
USA  United Kingdom

        xchen@math.utk.edu                  maspm@bath.ac.uk