==== Front J Stat PhysJ Stat PhysJournal of Statistical Physics0022-47151572-9613Springer US New York 197810.1007/s10955-018-1978-0ArticleCluster Tails for Critical Power-Law Inhomogeneous Random Graphs van der Hofstad Remco fsmith@example.com 1Kliem Sandra fsmith@example.com 2van Leeuwaarden Johan S. H. fsmith@example.com 11 0000 0004 0398 8763grid.6852.9Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands 2 0000 0001 2187 5445grid.5718.bFakultät für Mathematik, Universität Duisburg-Essen, Thea-Leymann-Str. 9, 45127 Essen, Germany 3 3 2018 3 3 2018 2018 171 1 38 95 23 11 2016 30 1 2018 © The Author(s) 2018Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.Recently, the scaling limit of cluster sizes for critical inhomogeneous random graphs of rank-1 type having finite variance but infinite third moment degrees was obtained in Bhamidi et al. (Ann Probab 40:2299–2361, 2012). It was proved that when the degrees obey a power law with exponent τ∈(3,4), the sequence of clusters ordered in decreasing size and multiplied through by n-(τ-2)/(τ-1) converges as n→∞ to a sequence of decreasing non-degenerate random variables. Here, we study the tails of the limit of the rescaled largest cluster, i.e., the probability that the scaling limit of the largest cluster takes a large value u, as a function of u. This extends a related result of Pittel (J Combin Theory Ser B 82(2):237–269, 2001) for the Erdős–Rényi random graph to the setting of rank-1 inhomogeneous random graphs with infinite third moment degrees. We make use of delicate large deviations and weak convergence arguments. Keywords Critical random graphsPower-law degreesInhomogeneous networksThinned Lévy processesExponential tiltingLarge deviationsMathematics Subject Classification 60C0505C8090B15Eindhoven University of Technologyissue-copyright-statement© Springer Science+Business Media, LLC, part of Springer Nature 2018 ==== Body Introduction The Erdős–Rényi random graph G(n, p) on the vertex set [n]:={1,…,n} is constructed by including each of the n2 possible edges with probability p, independently of all other edges. Erdős and Rényi discovered the double-jump phenomenon: The size of the largest component was shown to be, in probability, of order logn, n2/3, or n, depending on whether the average vertex degree was less than, close to, or more than one. In 1984 Bollobás [10] and subsequently Łuczak [28] showed for the scaling window p=(1+λn-1/3)/n, that the largest component is of the order n2/3. Since then, the critical, or near-critical behavior of random graphs has received tremendous attention (see [2, 4, 9, 18, 27]). Let (C(i))i≥1 denote the connected components of G(n, p), ordered in size, i.e., |Cmax|=|C(1)|≥|C(2)|≥⋯ Aldous [2] proved the following result: Theorem 1.1 (Aldous [2]). For p=(1+λn-1/3)/n, λ∈R fixed, and n→∞, 1.1 |C(1)|n-2/3,|C(2)|n-2/3,…⟶dγ1(λ),γ2(λ),…, where γ1(λ)>γ2(λ)>⋯ are the ordered excursions of the reflected version of the process (Wtλ)t≥0≡(Wt+λt-t2/2)t≥0 with (Wt)t≥0 a standard Wiener process. Theorem 1.1 says that the ordered connected components in the critical Erdős–Rényi random graph are described by the ordered excursions of the reflected version of (Wtλ)t≥0. The strict inequalities between the scaling limits of the ordered cluster follows from the local limit theorem proved in [23], see also [25, 29]. Pittel [31, Eq. (1.12)] derived an exact formula for the distribution function of the limiting variable γ1(λ) (of the largest component) and various asymptotic results were obtained, including 1.2 P(γ1(λ)>u)=19π/8u3/2e-18u(u-2λ)2(1+o(1)),u→∞. As pointed out in [32, 33], the constant 9π/8 was mistakenly reported in [31, Eq. (1.12)] as 2π due to a small oversight in the derivation. The result in (1.2) gives sharp asymptotics for the largest component in the critical Erdős–Rényi graph. It was rederived and extended in [33] using the original approach in [31]. Another generalization of (1.2) was obtained in [24] by studying the excursions of the scaling limit of the exploration process that is used to describe the limits in Theorem 1.1. In this paper, we follow a similar path, but then for a class of inhomogeneous random graphs and its scaling limit, and extend (1.2) to this setting. Several recent works have studied inhomogeneity in random graphs and how it changes the critical nature. In our model, the vertices have a weight associated to them, and the weight of a vertex moderates its degree. Therefore, by choosing these weights appropriately, we can generate random graphs with highly variable degrees. For our class of random graphs, it is shown in [22, Theorem 1.1] that when the weights do not vary too much, the critical behavior is similar to the one in the Erdős–Rényi random graph. See in particular the recent works [6, 34], where it was shown that if the degrees have finite third moment, then the scaling limit for the largest critical components in the critical window are essentially the same (up to a trivial rescaling that we explain in more detail below) as for the Erdős–Rényi random graph in Theorem 1.1. When the degrees have infinite third moment, instead, it was shown in [22, Theorem 1.2] that the sizes of the largest critical clusters are quite different. In [7] scaling limits were obtained for the sizes of the largest components at criticality for rank-1 inhomogeneous random graphs with power-law degrees with power-law exponent τ∈(3,4). For τ∈(3,4), the degrees have finite variance but infinite third moment. It was shown that the sizes of the largest components, rescaled by n-(τ-2)/(τ-1), converge to hitting times of a thinned Lévy process. The latter is a special case of the general multiplicative coalescents studied by Aldous and Limic in [2] and [3]. We next discuss these results in more detail. Inhomogeneous Random Graphs In our random graph model, vertices have weights, and the edges are independent, with edge probabilities being approximately equal to the rescaled product of the weights of the two end vertices of the edge. While there are many different versions of such random graphs (see below), it will be convenient for us to work with the so-called Poissonian random graph or Norros–Reittu model [30]. To define the model, we consider the vertex set [n]:={1,2,…,n} and suppose each vertex is assigned a weight, vertex i having weight wi. Now, attach an edge between vertices i and j with probability 1.3 pij=1-exp(-wiwjℓn),whereℓn=∑i∈[n]wi. Different edges are independent. In this model, the average degree of vertex i is close to wi, thus incorporating inhomogeneity in the model. There are many adaptations of this model, for which equivalent results hold. Indeed, the model considered here is a special case of the so-called rank-1 inhomogeneous random graph introduced in great generality by Bollobás et al. [11]. It is asymptotically equivalent with many related models, such as the random graph with prescribed expected degrees or Chung-Lu model, where instead 1.4 pij=max(wiwj/ℓn,1), and which has been studied intensively by Chung and Lu (see [13–17]). A further adaptation is the generalized random graph introduced by Britton et al. [12], for which 1.5 pij=wiwjℓn+wiwj. See Janson [26] for conditions under which these random graphs are asymptotically equivalent, meaning that all events have asymptotically equal probabilities. As discussed in more detail in [22, Sect. 1.3], these conditions apply in the setting to be studied in this paper. Therefore, all results proved here also hold for these related rank-1 models. We refer the interested reader to [22, Sect. 1.3] for more details. Having specified the edge probabilities as functions of the vertex weights w=(wi)i∈[n] in (1.3), we now explain how we choose the vertex weights. Let the weight sequence w=(wi)i∈[n] be defined by 1.6 wi=[1-F]-1(i/n), where F is a distribution function on [0,∞) for which we assume that there exists a τ∈(3,4) and 0<cF<∞ such that 1.7 limx→∞xτ-1[1-F(x)]=cF, and where [1-F]-1 is the generalized inverse function of 1-F defined, for u∈(0,1), by 1.8 [1-F]-1(u)=inf{s:[1-F](s)≤u}. By convention, we set [1-F]-1(1)=0. Note that our inhomogeneity is chosen in such a way that the vertex weights i↦wi are decreasing, with w1 being the largest vertex weight. For the setting in (1.3) and (1.6), by [11, Theorem 3.13], the number of vertices with degree k, which we denote by Nk, satisfies 1.9 Nk/n⟶PE[e-WWkk!],k≥0, where ⟶P denotes convergence in probability, and where W has distribution function F appearing in (1.6). We recognize the limiting distribution as a so-called mixed Poisson distribution with mixing distribution F, i.e., conditionally on W=w, the distribution is Poisson with mean w. As discussed in more detail in [22], since a Poisson random variable with large parameter w is closely concentrated around its mean w, the tail behavior of the degrees in our random graph is close to that of the distribution F. As a result, when (1.7) holds, and with Dn the degree of a uniformly chosen vertex in [n], lim supn→∞E[Dna]<∞ when a<τ-1 and lim supn→∞E[Dna]=∞ when a≥τ-1. In particular, the degree of a uniformly chosen vertex in [n] has finite second, but infinite third moment when (1.7) holds with τ∈(3,4). Under the key assumption in (1.7), 1.10 [1-F]-1(u)=(cF/u)1/(τ-1)(1+o(1)),u↓0, and the third moment of the degrees tends to infinity, i.e., with W∼F, we have E[W3]=∞. Define 1.11 ν=E[W2]/E[W], so that, again by (1.7), ν<∞. Then, by [11, Theorem 3.1] (see also [11, Sect. 16.4] for a detailed discussion on rank-1 inhomogeneous random graphs, of which our random graph is an example), when ν>1, there is one giant component of size proportional to n, while all other components are of smaller size o(n), and when ν≤1, the largest connected component contains a proportion of vertices that converges to zero in probability. Thus, the critical value of the model is ν=1. The main goal of this paper is to investigate what happens close to the critical point, i.e., when ν=1. With the definition of the weights in (1.6) and for F such that ν=1, we write Gn0(w) for the graph constructed with the probabilities in (1.3), while, for any fixed λ∈R, we write Gnλ(w) when we use the weight sequence 1.12 w(λ)=(1+λn-(τ-3)/(τ-1))w. We shall assume that n is so large that 1+λn-(τ-3)/(τ-1)≥0, so that wi(λ)≥0 for all i∈[n]. When τ>4, so that E[W3]<∞, it was shown in [6, 22, 34] that the scaling limit of the random graphs studied here are (apart from a trivial rescaling of time and λ) equal to the scaling limit of the ordered connected components in the Erdős–Rényi random graph in Theorem 1.1. The rescaling of time and λ is due to the variance of the step distribution of the cluster exploration process being unequal to 1 (see Sect. 1.2 below for more details on what we mean with 'cluster exploration'). For the Erdős–Rényi random graph the step distribution has a Poisson distribution with parameter 1 minus one. When τ∈(3,4) the situation is entirely different, as discussed next. Throughout this paper, we make use of the following standard notation. We let ⟶d denote convergence in distribution, and ⟶P convergence in probability. For a sequence of random variables (Xn)n≥1, we write Xn=oP(bn) when |Xn|/bn⟶P0 as n→∞. For a non-negative function n↦g(n), we write f(n)=O(g(n)) when |f(n)| / g(n) is uniformly bounded, and f(n)=o(g(n)) when limn→∞f(n)/g(n)=0. Furthermore, we write f(n)=Θ(g(n)) if f(n)=O(g(n)) and g(n)=O(f(n)). Finally, we abbreviate 1.13 α=1/(τ-1),ρ=(τ-2)/(τ-1),η=(τ-3)/(τ-1). The Scaling Limit for τ∈(3,4) We next recall two key results that we recently established in [7]: Theorem 1.2 (Weak convergence of the ordered critical clusters for τ∈(3,4) [7]) Fix the Norros–Reittu random graph with weights w(λ) defined in (1.6) and (1.12). Assume that ν=1 and that (1.7) holds. Then, for all λ∈R, 1.14 (|C(1)|n-ρ,|C(2)|n-ρ,…)⟶d(γ1(λ),γ2(λ),…), in the product topology, for some non-degenerate limit (γi(λ))i≥1. In order to further specify the scaling limit (γi(λ))i≥1, we need to introduce a continuous-time process (St)t≥0, referred to as a thinned Lévy process, and defined as 1.15 St=b-abt+ct+∑i=2∞biα[Ii(t)-atiα], where a, b, c have been identified in [7, Theorem 2.4] as a=cFα/E[W], b=cFα and c=θ=λ+ζ with 1.16 ζ=cF2αE[W]∑i≥1∫i-1iu-2αdu-i-2α∈(-∞,0) the constant given in [7, (2.18)]1. The process (St)t≥0 starts out positive. It can be positive or negative, and we will be interested in the first hitting time of (St)t≥0 of zero. Further, here we use the notation 1.17 Ii(t)=1{Ti≤t}, where (Ti)i≥2 are independent exponential random variables with mean 1.18 E[Ti]=iα/a. The term thinned Lévy process refers to the fact that Ii(t) can be interpreted as 1{Ni(t)≥1}, where (Ni(t))i≥1 are independent Poisson processes with rate a/iα. If we replace 1{Ni(t)≥1} by Ni(t) in this representation, then the corresponding process is a Lévy process. In (St)t≥0, only the first point in these Poisson processes is counted, thus we can think about the Poisson processes as being thinned. See below for more details on the interpretation of (St)t≥0. Let H1(0) denote the first hitting time of 0 of the process (St)t≥0, i.e., 1.19 H1(0)=inf{t≥0:St=0}, and C(1) the connected component to which vertex 1 (with the largest weight) belongs. We recall from [7, Theorem 2.1 and Proposition 3.7] that also |C(1)|n-ρ converges in distribution: Theorem 1.3 (Weak convergence of the cluster of vertex 1 for τ∈(3,4)). Fix the Norros–Reittu random graph with weights w(λ) defined in (1.6) and (1.12). Assume that ν=1 and that (1.7) holds. Then, for all λ∈R, 1.20 n-ρ|C(1)|⟶dH1a(0), with H1a(0) the hitting time of 0 of (St)t≥0 with a=cFα/E[W], b=cFα, c=θ. Let us informally describe how the process (St)t≥0 arises through a cluster exploration, and how it is linked to H1a(0) in (1.20) as well as (γi(λ))i≥1 in (1.14). In Theorem 1.3, we explore the connected component of vertex 1 one vertex at a time in a breadth-first way, and keep track of the number of active vertices, which are vertices that are found to be in C(1), but whose neighbors have not yet been inspected whether they are in C(1). Let Sk(n) be the number of active vertices after k steps, so that S0(n)=1. Obviously, |C(1)|=inf{k:Sk(n)=0}, since we are done with the exploration of a cluster when there are no unexplored vertices left, and we explore one vertex at a time. By construction, S1(n) is the number of neighbors of vertex 1, which can be seen to be close to w1≈bnα. Thus, the exploration process can be expected to be of order nα, and we will rescale S1(n) by a factor n-α. As explained in more detail in [7] and for the edge-probabilities in (1.3), the exploration can be performed rather effectively in terms of a marked branching process with mixed Poisson offspring distribution. Here, an unexplored vertex in the branching process, v, first draws a mark Mv for which P(Mv=i)=wi/ℓn, and after this, it draws a Poisson number of children with mean wMv. The connection to the cluster exploration in the graph is obtained by thinning all vertices whose mark has appeared earlier. Here, we can think of the mark Mv=i as indicating that the vertex v in the branching process is being mapped to vertex i in the graph. The largest weights correspond to the small values of i∈[n]. The amount of time it takes us to draw a mark corresponding to vertex i is of the order ℓn/wi, which is of order nρa/iα, which suggests that (n-αStnρ(n))t≥0 converges in distribution to some process (St)t≥0. Further, the first time that i≥2 is chosen, Ti(n), satisfies n-ρTi(n)⟶dTi, where Ti is exponential with rate a/iα. Further, vertex i has roughly wi≈nαb/iα neighbors, so that Sk(n) makes a jump of order nαb/iα when i is found to be in C(1). This informally explains the process (1.15)–(1.18), while (1.19) explains that when the exploration process hits zero, then the cluster is fully explored. Turning this into a formal proof was one of the main steps in [7]. The above description does not yet describe the scaling limit (γi(λ))i≥1 in (1.14). For this, we note that after the exploration of C(1), we need to explore the clusters of the (high-weight) vertices that are not part of C(1). We do this by taking the vertex with largest weight that is not in C(1), which in the scaling limit corresponds to the smallest i for which Ii(H1(0))=0, and start exploring the cluster of that vertex. This is again done by using processes similar to (St)t≥0, but changes arise due to the depletion-of-points effect. Indeed, since C(1) is fully explored, in later explorations those vertices cannot arise again. We refrain from describing this in more detail, as it is not needed in this paper. We repeat this procedure, and explore the connected components of unexplored vertices of the highest weights one by one. After performing these explorations infinitely often, we obtain (γi(λ))i≥1 as the ordered vector of hitting times of zero of these cluster exploration processes. Some more details are given in Sect. 2.4. By scaling, H1a(0)/a for some a, b, c has the same distribution as the hitting time H1(0) obtained by taking b′=a′=1, and c′=c/(ab)=(λ+ζ)/(ab). We shall reparametrize a′=b′=1 and let 1.21 St=1+β~t+∑i=2∞ci[Ii(t)-cit], where we set 1.22 β~=β-1withβ=c′=θ/(ab)=(λ+ζ)/(ab), have used the notation 1.23 ci=i-α, and where Ii(t) is defined in (1.17)–(1.18) with a replaced by a′=1. This scaling is convenient, as it reduces the clutter in our notation. Main Results In this section we state our main results. Recall γ1(λ) from (1.14). Our Main Theorem establishes a generalization of Pittel's result in (1.2) to our rank-1 inhomogeneous random graph with power-law exponents τ∈(3,4): Main Theorem (Tail behavior scaling limit for τ∈(3,4)). When u→∞, there exists I>0 independent of λ and A=A(λ),κi,j=κi,j(λ) such that 1.24 P(γ1(λ)>au)=Au(τ-1)/2e-Iuτ-1+uτ-1∑i+j≥1κiju-i(τ-2)-j(τ-3)(1+o(1)). The constants I, A and κij are specified in Sect. 2. By scaling, these constants only depend on a, b through c′=c/(ab)=(λ+ζ)/(ab), any other dependence disappears since the law of H1(0) only depends on c′. Since τ∈(3,4), the sum over i, j such that i+j≥1 is in fact finite, as we can ignore all terms for which τ-1-i(τ-2)-j(τ-3)<0. We also see that the Main Theorem connects up nicely with Pittel's result in (1.2) that arises for τ=4, as for example seen in the fact that the exponent of u in the exponential is equal to 3 for τ=4 and the exponent in the power of u in the prefactor is equal to 3 / 2, as in (1.2). That these powers depend sensitively on τ is a manifestation of the importance of the inhomogeneity, which we will see throughout this paper. Aside from the Main Theorem, we prove two further theorems about the structure of the largest connected component when it is large. The first theorem concerns the probability that H1a(0)>u for some u>0 large, where H1a(0) is the weak limit of n-ρ|C(1)| identified in Theorem 1.3. This is achieved by investigating the hitting time H1(0) of 0 of the process (St)t≥0 in (1.21). Theorem 1.4 (Tail behavior scaling limit cluster vertex 1 for τ∈(3,4)). When u→∞, there exists I>0 independent of β~ and A=A(β~) and κij(β~)∈R such that 1.25 P(H1(0)>u)=P(H1a(0)>au)=Au(τ-1)/2e-Iuτ-1+uτ-1∑i+j≥1κiju-i(τ-2)-j(τ-3)(1+o(1)). The constants I, A and κij are equal to those in the Main Theorem. Comparing the Main Theorem and Theorem 1.4, we see that P(H1(0)>u)=P(γ1(λ)>au)·(1+o(1)). This has the interpretation that vertex 1, which is the vertex with the largest weight in our rank-1 inhomogeneous random graph, is with overwhelming probability in the largest connected component when this largest connected component is quite large. We can even go one step further and study the optimal trajectory the process t↦St takes in order to achieve the unlikely event that H1(0)>u when u is large. In order to describe this trajectory, we need to introduce some further notation. In the proof, it will be crucial to tilt the distribution, i.e., to investigate the measure P~ with Radon–Nikodym derivative eθuSu/E[eθuSu], for some appropriately chosen θ. The selection of an appropriate θ for the thinned Lévy process(St)t≥0 is quite subtle, and has been the main topic of our paper [1]. The main results from paper [1] are reported in Sect. 2, and will play an important role in the present analysis. We refer to below (2.13) for the definition of θ∗ that appears in the description of the optimal trajectory that is identified in the following theorem (Fig. 1): Theorem 1.5 (Optimal trajectory). For p∈[0,1], define 1.26 IE(p)=(τ-1)∫0∞(eθ∗v(1-e-pv)eθ∗v(1-e-v)+e-v-pv)dvvτ-1, with θ∗ as defined below (2.13). Then, for u→∞ and for any ε>0, 1.27 P(supp∈[0,1]|Spu-uτ-2IE(p)|≤uτ-2ε∣H1(0)>u)=1-o(1). Our Main Theorem follows by combining Theorems 1.4 and 1.5, and showing that, for u large, the probability that 1∈C(1) is overwhelmingly large. This argument is performed in detail in Sect. 2.4:Fig. 1 Numerical plots of p↦IE(p) for τ=3.1,3.5 and 3.9. In a first step, θ∗ was determined as the unique θ such that IE(1)=IE(1,θ)=0 Brownian motion on a parabola Note that substituting τ=4 into (1.24) yields Au3/2e-Iu3+κ01u2+(κ10+κ02)u(1+o(1)), which agrees with the result of Pittel in (1.2). This suggests a smooth transition from the case τ∈(3,4) to the case τ>4. We next further explore this relation. Consider the process (Wtλ)t≥0=(Wt+λt-t2/2)t≥0 with (Wt)t≥0 a standard Wiener process as mentioned in Theorem 1.1. We now apply the technique of exponential change of measure to this process. First note that the moment generating function of Wuλ can be computed as 1.28 logϕ(u;ϑ)≡logEeϑuWuλ=ϑuλu-12u2+12ϑu2 and let θu∗ be the solution of θu∗=argminϑlogϕ(u;ϑ), which is given by 1.29 θu∗=12-λu. The main term is 1.30 ϕ(u)=ϕ(u;θu∗)=Eeθu∗uWuλ=e-18u3+12λu2-12λ2u=e-18u(u-2λ)2. Noting that 1.31 P(γ1(λ)>u)≤PWuλ>0≤Peθu∗uWuλ>1≤Eeθu∗uWuλ, we see that this upper bound agrees to leading order with the result of Pittel in (1.2). In order to derive the full asymtptotics in (1.2), one can define the measure 1.32 P~(E)=ϕ(u)-1Eeθu∗uWuλ1E, rewrite 1.33 P(γ1(λ)>u)=ϕ(u)E~eθu∗uWuλ1{γ1(λ)>u}, and then deduce the asymptotics of the latter expectation in full detail. Our analysis will be based on this intuition, now applied to a more involved, so-called thinned Lévy, stochastic process. Overview of the Proofs In this section, we give the overview of the proofs of Theorems 1.4–1.3. The point of departure for our proofs is the conjecture that P(H1(0)>u)≈P(Su>0) for large u. The event {H1(0)>u} obviously implies {Su>0}, but because of the strong downward drift of the process (St)t≥0, it seems plausible that both events are roughly equivalent. In [1] a detailed study was presented on the large deviations behavior of the process (St)t≥0. Using exponential tilting of measure the following two theorems were proved. Theorem 2.1 (Exact asymptotics tail Su [1, Theorem 1.1]). There exists I,D>0 and κij∈R such that, as u→∞, 2.1 P(Su>0)=Du(τ-1)/2e-Iuτ-1+uτ-1∑i+j≥1κiju-i(τ-2)-j(τ-3)(1+o(1)). Theorem 2.2 (Sample path large deviations [1, Theorem 1.2]). There exists a function p↦IE(p) on [0, 1] such that, for any ε>0 and p∈[0,1), 2.2 limu→∞P(|Spu-uτ-2IE(p)|≤εuτ-2∣Su>0)=1. In [1] it is explained that specific challenges arise in the identification of a tilted measure due to the power-law nature of (St)t≥0. General principles prescribe that the tilt should follow from a variational problem, but in the case of (St)t≥0 this involves a Riemann sum that is hard to control. In [1] this Riemann sum is approximated by its limiting integral, and it is proved that the tilt that follows from the corresponding approximate variational problem is sufficient to establish the large deviations results in Theorems 2.1 and 2.2. Details about this tilted measure are presented in Sect. 2.1. It is clear that Theorems 2.1 and 2.2 for the event {Su>0} are the counterparts of Theorems 1.4 and 1.5 for {H1(0)>u}. Let us now sketch how we make the conjecture that P(H1(0)>u)≈P(Su>0) for large u formal. We show that P(H1(0)>u) has the same asymptotic behavior as P(Su>0) in (2.1), with the same constants except for the constant D. Despite the similarity of this result, the proof method we shall use is entirely different from the exponential tilting in [1]. In order to establish the asymptotics for P(H1(0)>u), we establish sample path large deviations, not conditioned on the event {Su>0}, but on the event {H1(0)>u}. This is much harder, since we have to investigate the probability that St>0 for all t∈[0,u]. However, this is also more important, as only the hitting times H1(0) give us asymptotics of the limiting cluster sizes. In order to prove these strong sample-path properties, we first prove that, under the tilted measure, St is close to its expected value for a finite, but large, number of t's, followed by a proof that the path cannot deviate much in the small time intervals between these times. Now here is our strategy for the proofs. We extend the conjecture P(H1(0)>u)≈P(Su>0) by a conjectured sample path behavior that says that, under the tilted measure, the typical sample path of (St)t≥0 that leads to the event {Su>0} remains positive and hence implies {H1(0)>u}. To be more specific, we divide up this likely sample path into three parts: the early part, the middle part, and the end part. Our proof consists of treating each of these parts separately. We shall prove consecutively that with high probability the process:(i) Does not cross zero in the initial part of the trajectory ('no early hits'); (ii) Is high up in the state space in the middle part of the trajectory, while experiencing small fluctuations, and therefore does not hit zero ('no middle ground'); (iii) Is forced to remain positive until the very end. In the last step, we have to be very careful, and it is in this step that it will turn out that the constant D arising in the asymptotics of P(Su>0) in (2.1) is different from the constant A arising in the asymptotics of P(H1(0)>u) in (1.25). This is due to the fact that even when Su>0, the path could dip below zero right before time u and does so with non-vanishing probability. The proof reveals that then it will do so in the time interval [u-Tu-(τ-2),u] for some large T. We next summarize the technique of exponential tilting developed in [1] for the thinned Lévy process (St)t≥0 with τ∈(3,4), which allows us to give more details about how we shall establish the conjectured sample path behavior for each of the three parts described above. Tilting and Properties of the Tilted Process All results presented in this subsection are proved in [1]. Exponential tilting Parts of this section are taken almost verbatim from [1]. We use the notion of exponential tilting of measure in order to rewrite 2.3 P(Su>0)=ϕ(u;ϑ)E~ϑe-ϑuSu1{Su>0}, where ϑ is chosen later on. For every event E, define the measure P~ϑ with corresponding expectation E~ϑ by means of the equality 2.4 P~ϑ(E)=1ϕ(u;ϑ)EϑeϑuSu1E, with normalizing constant ϕ(u;ϑ) given by 2.5 ϕ(u;ϑ)=EeϑuSu. In terms of this notation, we are interested in 2.6 P(H1(0)>u)=ϕ(u;ϑ)E~ϑe-ϑuSu1{S[0,u]>0}, where we write {S[0,u]>0}={St>0∀t∈[0,u]}. We now explain in more detail how to choose a good ϑ. The independence of the indicators (Ii(u))i≥2 yields 2.7 ϕ(u;ϑ)=E[eϑuSu]=eϑu(1+β~u)∏i=2∞e-ϑu2ci2(e-ciu+eϑciu(1-e-ciu))=eϑu(1+β~u)e∑i=2∞f(i/uτ-1;ϑ) with 2.8 f(x;ϑ)=log(1+e-x-α(e-ϑx-α-1))+ϑx-α-ϑx-2α. The function x↦f(x;ϑ) is integrable at x=0 and at x=∞, so the above sum can be approximated by the integral 2.9 ∑i=2∞f(i/uτ-1;ϑ)=uτ-1∫0∞f(x;ϑ)dx+eϑ(u)≡uτ-1Λ(ϑ)+eϑ(u), for some error term u↦eϑ(u) given by 2.10 eϑ(u)=ϑu[ζ(α)-1]-u2[ζ(2α)-1]+oϑ(1), where α=1/(τ-1) and the Riemann zeta functions ζ(·) defined as 2.11 ζ(s)=limN→∞∑n=1Nn-s-N1-s1-s-12N-s,Re(s)>-1,s≠1, where Re(s) denotes the real part of s∈C. Equation (2.11) follows from Euler–Maclaurin summation [21, p. 333]. The error term in (2.10) converges to 0 uniformly for ϑ in compact sets bounded away from zero. As a result, 2.12 ϕ(u;ϑ)=euτ-1Λ(ϑ)+ϑu(ζ(α)+(β~-ζ(2α)+1)u)+oϑ(1). Let θu∗ be the solution of 2.13 θu∗=argminϑ[Λ(ϑ)+ϑu2-τ(ζ(α)+(β~-ζ(2α)+1)u)]. Moreover, let θ∗ be the value of ϑ where ϑ↦Λ(ϑ) is minimal. It follows easily that I≡-Λ(θ∗)>0 and that θ∗ is unique. In [1, Lemma 3.6], we have seen that θu∗=θ∗+o(1). Further, θ∗>0 by [1, Lemma 3.5]. Set ϕ(u)=ϕ(u;θu∗). The asymptotics of ϕ(u) are as follows. Proposition 2.3 (Asymptotics of main term [1, Proposition 2.1]). As u→∞, and with I=-minϑ≥0Λ(ϑ)>0, there exist κij∈R such that 2.14 ϕ(u)=Eeθu∗uSu=e-Iuτ-1+uτ-1∑i+j≥1κiju-i(τ-2)-j(τ-3)(1+o(1)). Properties of the process under the tilted measure In what follows, take ϑ=θu∗, and let P~=P~θu∗ with corresponding expectation E~=E~θu∗. Abbreviate θ=θu∗. Under this new measure, the rare event of Su being positive becomes quite likely. To describe these results, let us introduce some notation. Recall from (1.26) that, for p∈[0,1], 2.15 IE(p)=(τ-1)∫0∞(eθ∗v(1-e-pv)eθ∗v(1-e-v)+e-v-pv)dvvτ-1, where we take ϑ=θ∗, which turns out to be the limit of θu∗ as u→∞ (see, e.g., [1, Lemma 3.6]). The asymptotic mean of the process p↦Spu conditionally on Su>0 can be described with the help of the function p↦IE(p), cf. Theorem 2.2. One easily checks that 2.16 IE(0)=0,andIE(1)=0, the latter by definition of θ∗, as 0=Λ′(θ∗)=IE(1). Finally, 2.17 IE(p)>0foreveryp∈(0,1), and 2.18 IE′(0)>0andIE′(1)<0. Lemma 2.4 (Expectation of St [1, Lemma 2.2]). As u→∞,E~[St]=uτ-2IE(t/u)+O(1+t+t|θ∗-θu∗|uτ-3) uniformly in t∈[0,u]. E~[St-Su]=uτ-2IE(t/u)+O(u-t+u-1+|θ∗-θu∗|uτ-2) uniformly in t∈[u/2,u]. E~[St-Su]=uτ-3IE′(1)(t-u)(1+o(1))+O(u-1) when u-t=o(u). uE~[Su]=o(1) when u→∞. We will also need some consequences of the asymptotic properties of E~[St]. This is stated in the following corollary: Corollary 2.5 As u→∞,E~[St]≥c_tuτ-3 and E~[St]≤c¯tuτ-3 uniformly for t∈[ε,u/2], where 0<c_<c¯<∞; E~[Su-t-Su]≥c_tuτ-3 and E~[Su-t-Su]≤c¯tuτ-3 uniformly for t∈[Tu-(τ-2),u/2], where 0<c_<c¯<∞; E~[St]=E~[St1](1+o(1)) for t∈[t1,t2] and t1∈[ε,u/2] and t2-t1=O(u-(τ-2)); E~[St]=E~[St1](1+oT(1)) for t∈[t1,t2] and t1∈[u/2,u-Tu-(τ-2)], where oT(1) denotes a quantity c(T, u) such that limT→∞lim supu→∞c(T,u)=0 and t2-t1=O(u-(τ-2)). Proof Part (a) for t∈[ε,εu] for ε>0 sufficiently small follows from Lemma 2.4(a) together with the facts that IE(0)=0, IE′(0)>0, and that 1+t+t|θ∗-θu∗|uτ-3=o(tuτ-3). The fact that IE′(0)>0 also implies that c_ can be taken to be strictly positive. For t∈[εu,u/2], Part (a) follows from the fact that IE(p)>0 for all p∈[ε,1/2] and that 1+t+t|θ∗-θu∗|uτ-3=o(uτ-2). Part (b) follows as Part (a), now using Lemma 2.4(b) together with the fact that IE(1)=0, IE′(1)<0. Part (c) follows from Lemma 2.4(a), by subtracting the two terms. Note that the error term O(1+t1+t1|θ∗-θu∗|uτ-3) is o(t1uτ-3) since t1≥ε, while E~[St1]=Θ(t1uτ-3) by Part (a) of this corollary. Further, note that 2.19 uτ-2[IE(t/u)-IE(t1/u)]=Ouτ-2maxp∈[0,1]|IE′(p)|(t2-t1)=O(1), which is o(1)E~[St1]. Part (d) follows again from Lemma 2.4(a) by subtracting the two terms. Note again that the error term O(1+t1+t1|θ∗-θu∗|uτ-3) is o(t1uτ-3), while E~[St1]=Θ(t1uτ-3) by part (b) of this corollary and Lemma 2.4(a). Further, note that 2.20 uτ-2[IE(t/u)-IE(t1/u)]=Ouτ-2maxp∈[0,1]|IE′(p)|(t2-t1)=OT(1), which is oT(1)E~[St1]. □ The next lemma gives asymptotic properties of the variance of St. Define, for p∈[0,1], 2.21 IV(p)=(τ-1)∫0∞eθ∗v(1-e-pv)eθ∗v(1-e-v)+e-v(1-eθ∗v(1-e-pv)eθ∗v(1-e-v)+e-v)dvvτ-2 and 2.22 JV(p)=(τ-1)∫0∞eθ∗v(e-pv-e-v)eθ∗v(1-e-v)+e-v(1-eθ∗v(e-pv-e-v)eθ∗v(1-e-v)+e-v)dvvτ-2, 2.23 GV(p)=(τ-1)∫0∞e2θ∗v(1-e-pv)(e-pv-e-v)eθ∗v(1-e-v)+e-v2dvvτ-2. Again, it is not hard to check that 2.24 0<IV(p)<∞foreveryp∈(0,1],whileIV(0)=0, and 2.25 0<JV(p)<∞foreveryp∈[0,1),whileJV(1)=0. Lemma 2.6 (Covariance structure of St [1, Lemma 2.3]). As u→∞,Var~[St]=uτ-3IV(t/u)+O(1+t|θ∗-θu∗|uτ-4) uniformly in t∈[0,u]. Var~[St-Su]=uτ-3JV(t/u)+O((u-t)u-1+(u-t)|θ∗-θu∗|uτ-4) uniformly in t∈[0,u]. Cov~[St,Su-St]=-uτ-3GV(t/u)+O((u-t)u-1+(u-t)|θ∗-θu∗|uτ-4) uniformly in t∈[0,u]. The next result bounds the Laplace transform of the couple (St,Su): Proposition 2.7 (Joint moment generating function of (St,Su) [1, Proposition 2.4]). (a) As u→∞, 2.26 E~[eλSt-E~[St]IV(t/u)uτ-3]=e12λ2+Θ, where |Θ|≤ou(1) as u→∞ uniformly in t∈[u/2,u] and λ in a compact set. (b) Fix ε>0 small. As u→∞, for any λ1,λ2∈R, 2.27 E~[eλ1St-E~[St]IV(t/u)uτ-3+λ2Su-St-E~[Su-St]JV(t/u)uτ-3]=e12λ12+12λ22-λ1λ2GV(t/u)IV(t/u)JV(t/u)+Θ, where |Θ|≤ou(1)+O(t3(3-τ)/2) uniformly in t∈[ε,u-u-(τ-5/2)] and λ1,λ2 in a compact set. Combine Proposition 2.7 and uE~[Su]=o(1) (see [1, Lemma 4.1]) to show that u-(τ-3)/2Su converges to a normal distribution with mean 0 and variance IV(1). Moreover, as we see below, the density of Su close to zero behaves like 2πIV(1)-1/2u-(τ-3)/2: Proposition 2.8 (Density of Su near zero [1, Proposition 2.5]) Uniformly in s=o(u(τ-3)/2), the density f~Su of Su satisfies 2.28 f~Su(s)=Bu-(τ-3)/2(1+o(1)), with B=2πIV(1)-1/2 and IV(p) defined in (2.21). Moreover, f~St(s) is uniformly bounded by a constant times u-(τ-3)/2 for all s, u and t∈[u/2,u]. There are three more results from [1] that will be used in this paper. The first is a description of the distribution of the indicator processes (Ii(t))t≥0 under the measure P~. Since our indicator processes (Ii(t))t≥0 are independent, this property also holds under the measure P~: Lemma 2.9 (Indicator processes under the tilted measure [1, Lemma 4.2]) Under the measure P~, the distribution of the indicator processes (Ii(t))t≥0 is that of independent indicator processes. More precisely, 2.29 Ii(t)=1{Ti≤t}, where (Ti)i≥2 are independent random variables with distribution 2.30 P~(Ti≤t)=eθciu1-e-citeθciu1-e-ciu+e-ciufort≤u;eθciu1-e-ciu+e-ciu-e-citeθciu1-e-ciu+e-ciufort>u. The second lemma describes what happens to the variances for small p or for p close to 1: Lemma 2.10 (Asymptotic variance near extremities [1, Lemma 4.3(b)]). As p→1, JV(p)=-(1-p)JV′(1)(1+o(1)) with JV′(1)<0, while, as p→0, 2.31 IV(p)=pτ-3IV(1+o(1)),withIV=(τ-1)∫0∞(1-e-y)e-ydyyτ-2. Consequently, there exist 0<c_<c¯<∞ such that, for every p∈[0,ε] with ε>0 sufficiently small, 2.32 c_pτ-3≤IV(p)≤c¯pτ-3. We finally rely on the following corollary that allows us to compute sums that we will encounter frequently: Corollary 2.11 (Replacing sums by integrals in general [1, Corollary 3.3]). For every a∈R,a>τ-1 and b>0, there exists a constant c(a, b) such that 2.33 ∑i=2∞ciae-bciu=c(a,b)uτ-a-1(1+o(1)). No Early Hits and Middle Ground In this section, we prove that the tilted process is unlikely to hit 0 until a time that is very close to u. We start by investigating the early hits. No early hits In this step, we prove that it is unlikely that the process hits zero early on, i.e., in the first time interval [0,ε] for some ε>0 sufficiently small. In its statement, we write 0∈S[0,t] for the event that {Ss=0} for some s∈[0,t], so that P(H1(0)>u)=P(0∉S[0,u]). Lemma 2.12 (No early hits). For every u∈[0,∞), as ε↓0, 2.34 P(0∈S[0,ε],Su>0)=oε(1)P(Su>0), where oε(1) denotes a function that converges to zero as ε↓0, uniformly in u. The proof of Lemma 2.12 follows from a straightforward application of the FKG-inequality for independent random variables (see [19], or [20, Theorem 2.4, p. 34]). The standard versions of the FKG-inequality hold for independent indicator random variables, and in our case we need it for independent exponentials. It is not hard to prove that the FKG-inequality we need holds by an approximation argument. Proof We note that the process (St)t≥0 is a deterministic function of the exponential random variables (Ti)i≥2 (recall (1.15), (1.17) and (1.18)). Now, the event {0∈S[0,ε]} is increasing in terms of the random variables (Ti)i≥2 (use that St only has positive jumps). Here we say that an event A is increasing when, if A occurs for a realization (ti)i≥2 of (Ti)i≥2, and if (ti′)i≥2 is coordinatewise larger than (ti)i≥2, then A also occurs for (ti′)i≥2. Clearly, the event {Su>0} is decreasing (for a definition, change the role of ti and ti′ in the definition of an increasing event), so that the FKG-inequality implies that these events are negatively correlated: 2.35 P(0∈S[0,ε],Su>0)≤P(0∈S[0,ε])P(Su>0). We conclude the proof by noting that P(0∈S[0,ε])=oε(1) independently of u. □ The key to our proof of Theorem 1.4 will be to show that P(H1(0)>u)=Θ(P(Su>0)), so that Lemma 2.12 and the known asymptotics of P(Su>0) imply that it is unlikely to have an early hit of zero. No middle ground By (2.4) (recall that ϕ(u)=ϕ(u;θ) with θ=θu∗), Lemma 2.12 and Theorem 2.1, 2.36 P(H1(0)>u)=ϕ(u)E~e-θuSu1{S[0,u]>0}=ϕ(u)E~e-θuSu1{S[ε,u]>0}+ϕ(u)u-(τ-1)/2oε(1). For M>0 arbitrarily fixed, we split 2.37 P(H1(0)>u)=ϕ(u)E~e-θuSu1{S[ε,u]>0,Su∈[0,M/u]}+ϕ(u)E~e-θuSu1{S[ε,u]>0,Su>M/u}+ϕ(u)u-(τ-1)/2oε(1). By Proposition 2.8, we can bound 2.38 E~e-θuSu1{S[ε,u]>0,Su>M/u}≤E~e-θuSu1{Su>M/u}≤∫M/u∞e-θuvf~Su(v)dv≤O(u-(τ-3)/2)∫M/u∞e-θuvdv=O(u-(τ-1)/2)e-θM. As a result, we fsmith@example.com P(H1(0)>u)=ϕ(u)E~e-θuSu1{S[ε,u]>0,Su∈[0,M/u]}+ϕ(u)u-(τ-1)/2oM(1)+ϕ(u)u-(τ-1)/2oε(1), where oM(1) denotes a quantity c(M, u) such that lim supM→∞lim supu→∞c(M,u)=0. We continue to prove that the dominant contribution to the expectation of the right-hand side of (2.39) originates from paths that remain positive until time u-t for t=Tu-(τ-2), with T>0 arbitrarily fixed. Proposition 2.13 (No middle ground). Fix ε>0. For every u∈[0,∞) and ε,M>0 fixed, 2.40 P~(0∈S[ε,u-Tu-(τ-2)],Su∈[0,M/u])≤oT(1)u-(τ-1)/2, where we recall that oT(1) denotes a quantity c(T, u) such that limT→∞lim supu→∞c(T,u)=0. We prove Proposition 2.13 in Sect. 3. By (2.39) and Proposition 2.13, 2.41 P(H1(0)>u)=ϕ(u)E~e-θuSu1{S[u-Tu-(τ-2),u]>0}+ϕ(u)u-(τ-1)/2[oε(1)+oM(1)+oT(1)]. Since ε, M and T are arbitrary, it now suffices to identify the asymptotics of the expectation appearing on the right-hand side of (2.41). Remaining Positive Near the End To prove Theorem 1.4, by Proposition 2.3 and Eq. (2.41), it suffices to prove that, with γ=(τ-1)/2, 2.42 E~e-θuSu1{S[u-Tu-(τ-2),u]>0,Su∈[0,M/u]}=(A+oM(1)+oT(1))u-γ(1+o(1)), where T>0 fixed. In the above expectation, we see two terms. The term e-θuSu forces Su to be small, more precisely, Su=Θ(1/u) for u large, while the term 1{S[u-Tu-(τ-2),u]>0} forces the path to remain positive until time u. We now study these two effects. We start by highlighting the ideas behind the analysis of the process (St)t∈[u-Tu-(τ-2),u]. Comparing Theorem 1.4 to Theorem 2.1, we see that they are identical, except for the precise constant, which is A in Theorem 1.4 and D>A in Theorem 2.1. This difference is due to the fact that, conditionally on Su>0, the process has a probability of not hitting zero in the interval [u-Tu-(τ-2),u] that is strictly positive and bounded away from zero. In order to analyse this probability, we identify the scaling limit of the process (uSu-tu-(τ-2)-uSu)t≥0 as u→∞ conditionally on uSu=v, and relate it to a certain Lévy process. The parameter A / D is closely related to the probability that this limiting process is bounded below by -v, integrated over v. Let us now give the details. In order to investigate the probability that S[u-Tu-(τ-2),u]>0, we proceed as follows. Let 2.43 J(u)={j:Ij(u)=1} denote the set of indices for which Tj≤u. We condition on the set J(u). Note that Su is measurable with respect to J(u). We now rewrite Su-t in a convenient form. For this, recall (1.21) and write 2.44 Su-t=tu+u-tuSu+∑i=2∞ciIi(u-t)-u-tuIi(u)=tu+u-tuSu-∑i=2∞ci1{Ti∈(u-t,u]}-tuIi(u). Thus, with 2.45 Qu(t)≡uSu-t-t-(u-t)Su=-∑i=2∞ci[u1{Ti∈(u-t,u]}-tIi(u)], we have that Su-t>0 precisely when Qu(t)>-t-(u-t)Su. We rewrite 2.46 Qu(t)=-∑i∈J(u)ci[u1{Ti∈(u-t,u]}-t]. Note that, for any t=o(u), 2.47 E~[e-θuSu1{S[u-t,u]>0}]=1u∫0∞e-θvP~(S[u-t,u]>0∣uSu=v)f~Su(v/u)dv=1u∫0∞e-θvP~(Qu(s)>-v-s+sv/u∀s∈[0,t]∣uSu=v)f~Su(v/u)dv. We aim to use dominated convergence on the above integral, and we start by proving pointwise convergence. By Proposition 2.8, f~Su(v/u)=Bu-(τ-3)/2(1+o(1)) pointwise in v (in fact, even when v=o(u(τ-1)/2)). This leads us to study, for all v>0, 2.48 gu,t(v)≡P~(Qu(s)>-v-s+sv/u∀s∈[0,t]∣uSu=v). We split 2.49 Qu(t)=Au(t)-Bu(t), where 2.50 Bu(t)≡u∑i∈J(u)ci1{Ti∈(u-t,u]}-P~(Ti>u-t∣Ti≤u),Au(t)≡-∑i∈J(u)ciuP~(Ti>u-t∣Ti≤u)-t. Thus, (Au(t))t∈[0,u] is deterministic given J(u), while (Bu(t))t∈[0,u] is random given J(u). The main result for the near-end regime is the following proposition, which proves that gu(v) converges pointwise. Proposition 2.14 (Weak conditional convergence of time-reversed process). (a) As u→∞, conditionally on uSu=v, 2.51 (Au(tu-(τ-2)))t≥0⟶d(κt)t≥0, where κ∈(0,∞) is given by 2.52 κ=∫0∞x-αeθx-αe-x-αeθx-α(1-e-x-α)+e-x-α[ex-α-1-x-α]dx. (b) As u→∞, conditionally on uSu=v, 2.53 (Bu(tu-(τ-2)))t≥0⟶d(Lt)t≥0, where (-Lt)t≥0 is a Lévy process with no positive jumps and with Laplace transform 2.54 Eea(-Ls)=es∫-∞0eaz-1-azΠ(dz),a≥0, and characteristic measure 2.55 Π(dz)=(τ-1)(-z)-(τ-1)e-θze-θz(1-ez)+ezezdz. Proposition 2.14 is proved in Sect. 5, and determines the precise constant A from (1.25), as we now explain in more detail. We proceed by investigating some properties of the supremum of the Lévy process from (2.53) that we need later on. Note in particular that the distribution of Ls in (2.54) does not depend on v. With a slight abuse of notation, also the probability law describing the limiting process (Ls)s≥0 shall be denoted by P. Lemma 2.15 (Supremum of the Lévy process). Let I∞≡inft≥0(-Lt+κt). Then 2.56 P(I∞≥-v)=W(v)/W(∞), where W:[0,∞)→[0,∞) is the unique continuous increasing function that has Laplace transform 2.57 ∫0∞e-axW(x)dx=1ψ(a),a>Ψ(0), where the Laplace exponent ψ is given by E[ea(κt-Lt)]=etψ(a) and is computed in (2.58) below, while Ψ(0) is the largest solution of the equation ψ(a)=0, and W(∞)=1/ψ′(0)=1/κ is a constant. Proof We rewrite (2.54) to see that Xs≡-Ls+κs is a Lévy process with no positive jumps and Laplace exponent 2.58 ψ(a)=κa+∫(-∞,0)eaz-1-azΠ(dz)=β′a+∫(-∞,0)eaz-1-az1{z>-1}Π(dz) with 2.59 β′=κ+∫(-∞,0)(-z)1{z≤-1}Π(dz)>0 as defined in [5, Sect. VII.1]. Indeed, recall from [5, Sect. VII.1] that E[eaXs]=esψ(a) and note that our β′ corresponds to a in [5]. Also note from (2.52) that κ>0. Thus ψ′(0+)=κ>0 and [5, Corollary 2(ii) in Sect. VII.1] yields that Xs drifts to ∞ (for a definition, see [5, Theorem 12(ii) in Sect. VI.3]). This in turn implies (see [5, Proof of Theorem 8, in Sect. VII.2]) 2.60 P(I∞≥-v)=W(v)/W(∞), where W is given in the statement of [5, Theorem 8, in Sect. VII.2]. For the definition of Ψ see before [5, Theorem 1 of Sect. VII.1]. Also note from the second equation of the proof of [5, Proof of Theorem 8, in Sect. VII.2] that W(∞)>0. To see that W(∞)=1/ψ(0), note that if a↓0, 2.61 ∫0∞e-axW(x)dx=W(∞)a(1+o(1)). Now, ψ(0)=0, so that 1/ψ(a)=1/(aψ′(0))(1+o(1)) as a↓0, which identifies W(∞)=1/ψ′(0)=1/κ. □ By Proposition 2.14 and the continuity of W in Lemma 2.15, with MT=sup0≤s≤T(Ls-κs) for each v≥0 and for t=Tu-(τ-2), for u→∞, 2.62 gu,t(v)→gT(v)≡P(MT≤v). Further, as T→∞, 2.63 gT(v)↓g(v)≡Psup0≤s<∞(Ls-κs)≤v=W(v)W(∞). Now we are ready to complete the proofs of our main results. Completion of the Proofs Completion of the Proof of Theorem1.4 We start by completing the proof of Theorem 1.4. Recall that it remains to prove (2.42) with γ=(τ-1)/2. By (2.47) and (2.48), we need to compute 2.64 E~[e-θuSu1{S[u-t,u]>0,Su∈[0,M/u]}]=1u(τ-1)/2∫0Me-θvgu,t(v)[u(τ-3)/2f~Su(v/u)]dv, where t=Tu-(τ-2). A similar problem was encountered in [1, Proof of Theorem 1.1], which is restated here as Theorem 2.1, apart from the fact that there the function gu,t(v) was absent. We wish to use bounded convergence. For this, we note that u(τ-3)/2f~Su(v/u)→B by Proposition 2.8 for each v (in fact, for all v=o(u)), while, by (2.62)–(2.63), gu,t(v)→gT(v), which, in turn, converges to g(v) as T→∞. Further, since gu,t(v)≤1 and u(τ-3)/2f~Su(v/u) is uniformly bounded (see Proposition 2.8), the integrand e-θvgu,t(v)[u(τ-3)/2f~Su(v/u)] is uniformly bounded by a constant. Thus, by the Bounded Convergence Theorem, 2.65 E~e-θuSu1{S[u-t,u]>0,Su∈[0,M/u]}=Bu(τ-1)/2∫0Me-θvgT(v)dv(1+o(1))=Bu(τ-1)/2∫0Me-θvg(v)dv(1+o(1)+oT(1)). This identifies (recall (2.42), (2.56), (2.57) and (2.62)) 2.66 A=B∫0∞e-θvg(v)dv=B∫0∞e-θvP(M≤v)dv=BθE[e-θM]=Bψ′(0)ψ(θ). Recall that D is the constant appearing in Theorem 2.1. Since D=B/θ by [1, (7.4)] and P(M≤v)<1 for every v, we also immediately obtain that A∈(0,D). and completes the proof of Theorem 1.4. □ Path properties: Proof of Theorem1.5 We bound, using that {H1(0)>u}⊆{Su>0}, 2.67 P(supp∈[0,1]|Spu-uτ-2IE(p)|>εuτ-2∣H1(0)>u)≤P(supp∈[0,1]|Spu-uτ-2IE(p)|>εuτ-2∣Su>0)P(Su>0)P(H1(0)>u). By Theorems 2.1 and 1.4, the ratio of probabilities converges to D/A∈(0,∞), while, by Theorem 2.2, the conditional probability converges to 0. This completes the proof of Theorem 1.5. □ Completion of the Proof of the Main Theorem We finally complete the proof of the scaling of the critical clusters in the Main Theorem using Theorem 1.4 and recalling (1.22). For this, we go back to the random graph setting. Let us start by giving some introduction. The process (St)t≥0 in (1.21) arises when exploring a cluster in the Norros–Reittu random graph with weights w(λ) defined in (1.6) and (1.12), as described informally in Sect. 1.2. Recall Theorem 1.3. Here St denotes the scaling limit of n-1/(τ-1)=n-α times the number of vertices found at time tn(τ-2)/(τ-1)=tnρ. The key idea is that each time that a vertex, say j∈[n], is being explored, we have a chance (1+λn-(τ-3)/(τ-1))wiwj/ℓn that the edge to the vertex i with the ith largest weight is present. As it turns out (see e.g., [6, Lemma 1.3]), the vertices are found in a size-biased reordered way, meaning that the kth vertex found is v(k), where (here the factor (1+λn-(τ-3)/(τ-1)) cancels) 2.68 P(v(k)=j∣v(1),…,v(k-1))=wj∑l∉{v(1),…,v(k-1)}wl. Thus, the average weight of the kth vertex found is 2.69 E[wv(k)(1+λn-(τ-3)/(τ-1))∣v(1),…,v(k-1)]≈∑j∈[n]wj2ℓn≈E[W2]E[W]=ν=1, which informally corresponds to the graph being close to critical (as made more precise in [7]). By (2.68), the probability that at the kth exploration we find the vertex i with the ith largest weight is close to wi/ℓn. By (1.10) and (1.6), 2.70 wi≈(cFn/i)1/(τ-1), so the probability of finding i is close to (cF/i)1/(τ-1)n(2-τ)/(τ-1)/E[D]≈ai-1/(τ-1)n-ρ by the definitions below (1.15) and (1.13). If this occurs, then the number of vertices added to the exploration process is close to wi(1+λn-(τ-3)/(τ-1))≈(cF/i)1/(τ-1)n1/(τ-1)=bi-1/(τ-1)nα. Further, the probability that vertex i is not found in the time interval [0,t]nρ is close to e-tai-1/(τ-1)=P(Ii(t)=0). It is not hard to see that these events are weakly dependent, so that the scaling limits of the times that the high-weight vertices are found are close to independent exponential random variables with rate ai-1/(τ-1). This explains the random variables arising in (1.21). The restriction to i≥2 in (1.21) arises since we explore the cluster of vertex 1. The cluster is fully explored when there are no more active vertices waiting to be explored. This corresponds to St=0 for the first time, which is H1a(0) and explains the result in Theorem 1.3. Recall the informal description in Sect. 1.2 here as well. Next, we claim that when a particularly large cluster is found, then, since the weight w1 is the largest of all weights, the maximal cluster is whp the cluster of vertex 1. This explains why the asymptotics in the Main Theorem for the maximal cluster is identical to the asymptotics in Theorem 1.4 for the cluster of vertex 1. To make this heuristic precise, we show, in this section, that indeed it is unlikely for an unusually large cluster to be found that does not contain 1. We next make the ideas in this heuristic precise, by introducing the exploration process of the cluster of vertex i for a general i≥1. Denote 2.71 St(i)=ci+β~it+∑j=1:j≠i∞cj[Ij(t)-cjt], where β~i=(λ+ζ)/(ab)-ci2 (see [7, Remark 3.9] and recall a′,b′,c′ from above (1.21)). The intuition for the above formula is that 2.72 St(i)=λ+ζabt+∑j≥1∞cj[Ij(t)-cjt], where we slightly abuse notation to now set Ii(0)=1 for the process (St(i))t≥0 since vertex i is almost surely in the cluster of vertex i. Since (St(i))t≥0 describes the scaling limit of the exploration process of the cluster of vertex i≥1, while Ij(t) has the interpretation as the indicator that vertex j is found in the exploration before time t, it is reasonable to set Ii(0)=1 for (St(i))t≥0.2 Again recall the informal description of the exploration process in Sect. 1.2. We continue to show that it is highly unlikely that the cluster of vertex i is large, while vertex 1 is not in it. For this, we define 2.73 H(i)(0)=inft≥0:St(i)=0. Then, H1(0)=H(1)(0) and H(i)(0) denotes (an appropriate multiple of) the scaling limit of the cluster of vertex i, i.e., n-ρ|C(i)|⟶daH(i)(0), where C(i) denotes the connected component to which vertex i belongs to. Further, let C≤(i) be the set C(i) if none of the vertices j∈[i-1]={1,…,i-1} belongs to C(i), and the empty set ∅ otherwise. We know from [7, (3.78)] and the scaling explained around (1.21) that n-ρ|C(i)|⟶da·H(i)(0) for each i≥1 with ρ=(τ-2)/(τ-1) (cf. (1.13)). Finally, denote 2.74 Hi(0)=0if∃j<isuch thatIj(H(i)(0))=1;H(i)(0)otherwise. Then, by [7, (3.79)], n-ρ|C≤(i)|⟶da·Hi(0). This provides us with the appropriate background to complete the proof of the Main Theorem. We start with the lower bound. By construction, γ1(λ)≥a·H1(0) (see [7, Theorems 1.1 and 2.1] and recall that C(i) denotes the ith-largest connected component). Therefore, 2.75 P(γ1(λ)>au)≥P(H1(0)>u), and thus the lower bound follows from Theorem 1.4. For the upper bound, we use that (cf. [7, Theorems 1.1]) 2.76 P(γ1(λ)>au)=limn→∞P∃i:n-ρ|C≤(i)|≥au=limK→∞limn→∞P∃i∈[K]:n-ρ|C≤(i)|≥au≤limK→∞limn→∞∑i∈[K]Pn-ρ|C≤(i)|≥au, Here we have used the fact that there are with high probability only finitely many clusters that are larger than εnρ (as proved in [7, Theorem 1.6]). By the weak convergence of n-ρ|C≤(i)|, it holds that limn→∞P(n-ρ|C≤(i)|≥au)=P(Hi(0)>u) for all i≥1, so that we fsmith@example.com P(γ1(λ)>au)≤P(H1(0)>u)+∑i≥2P(Hi(0)>u). The first term is the main term, and we prove that ∑i≥2P(Hi(0)>u)=o(P(H1(0)>u)) now. For this, we note that 2.78 P(Hi(0)>u)=PIj(u)=0∀j∈[i-1],S[0,u](i)>0=P(Ij(u)=0∀j∈[i-1])PS[0,u](i)>0∣Ij(u)=0∀j∈[i-1]. We can rewrite, on the event {Ij(u)=0∀j∈[i-1]}, and using that c1≥ci for every i≥1, 2.79 St(i)=λ+ζabt+∑j≥i+1cj(Ij(t)-cjt)+ci-∑j=1icj2t≤λ+ζabt+∑j≥i+1cj(Ij(t)-cjt)+c1-∑j=1icj2t. Therefore, 2.80 PS[0,u](i)>0∣Ij(u)=0∀j∈[i-1]≤Pλ+ζabt+∑j≥i+1cj(Ij(t)-cjt)+c1-∑j=1icj2t>0∀t∈[0,u]=P(S[0,u](1)>0∣Ij(u)=0∀j∈[i]\{1}), where in the last equality, we use that, conditionally on Ij(u)=0 forall j∈[i]\{1}, the equality St(1)=λ+ζabt+∑j≥i+1cj(Ij(t)-cjt)+c1-∑j=1icj2t holds. The event {Ij(u)=0∀j∈[i]\{1}} is decreasing (recall the notions used in the proof of Lemma 2.12) in the random variables (Ti)i≥2, while the event {S[0,u](1)>0} is increasing. Thus, by the FKG-inequality, 2.81 P(S[0,u](1)>0∣Ij(u)=0∀j∈[i]\{1})≤P(S[0,u](1)>0)=P(H1(0)>u). We can identify 2.82 P(Ij(u)=0∀j∈[i-1])=e-∑j=1i-1cju. Combining (2.77), (2.81)–(2.82) we fsmith@example.com P(γ1(λ)>au)≤P(H1(0)>u)[1+∑i≥2e-∑j=1i-1cju]. Since cj=j-α with α∈(1/3,1/2), ∑j=1i-1cj≥(i-1)ci-1=(i-1)1-α. Therefore, 2.84 ∑i≥2e-∑j=1i-1cju=o(1). This completes the proof of the Main Theorem. □ No Middle Ground: Proof of Proposition 2.13 In this section, we show that the probability to hit zero in the time interval [ε,u-Tu-(τ-2)], where T is a constant, becomes negligible as T→∞. The strategy of proof is as follows. We start in Proposition 3.2 by investigating the value of St at some discrete times (tk)k≥1 in [0, u] and show that with high probability St does not deviate far from its mean. Next, in Proposition 3.3, we show that it is unlikely for the process (St)t≥0 to make a substantial deviation in the interval [tk,tk+1] from its value in tk. We start with a preparatory lemma that will allow us to give bounds on the asymptotic parameters appearing in the upcoming proofs: Lemma 3.1 (Asymptotics of parameters). There exists K≥1 such that 3.1 P~∑i=2∞ci2Ii(u)≥Kuτ-3≤Cu-(τ-1), and, for all |λ|≤δu with δ>0 sufficiently small, there exists K>0 such that 3.2 P~∑i=2∞ci[1-Ii(u/2)](eλci-1-λci)≥Kλ2uτ-4≤Cu-(τ-1). Proof We use the second moment method. With Lemma 2.9 we compute that 3.3 E~∑i=2∞ci2Ii(u)≤∑i=2∞ci2C(θ)(1-e-ciu). Split the sum into i with ciu≤1 and ciu>1. For the first, we bound 1-e-ciu≤O(1)ciu, for the latter, we bound 1-e-ciu≤1, to obtain 3.4 E~∑i=2∞ci2Ii(u)≤O(1)∑i:ciu≤1ci3u+O(1)∑i:ciu>1ci2=O(1)uτ-3(1+o(1)), the latter by an explicit computation using that ci=i-1/(τ-1). Further, with Corollary 2.11 3.5 Var~∑i=2∞ci2Ii(u)≤∑i=2∞ci4(1-P~(Ti≤u))≤C(θ)∑i=2∞ci4e-ciu=O(1)uτ-5(1+o(1)). The Chebychev inequality now proves (3.1). For (3.2), we again compute 3.6 E~∑i=2∞ci[1-Ii(u/2)](eλci-1-λci)≤C(θ)∑i=2∞cie-ciu/2eλci-1-λci=C(θ)∑i=2∞cie-ciu/2e|λ|ci(λci)2/2. Thus, for |λ|≤δu and again using Corollary 2.11, we obtain 3.7 E~∑i=2∞ci[1-Ii(u/2)](eλci-1-λci)=O(λ2uτ-4). Further, 3.8 Var~(∑i=2∞ci[1-Ii(u/2)](eλci-1-λci))≤C(θ)∑i=2∞ci2e-ciu/2(eλci-1-λci)2≤C(θ)|λ|4∑i=2∞ci6e-ciu/2e2|λ|ci=O(|λ|4uτ-7). Again the claim follows from the Chebychev inequality. □ We continue to show that the probability for St to deviate far from its mean at some discrete times in the time interval [ε,u-Tu-(τ-2)] is small when T is large enough: Proposition 3.2 (Probability to deviate far from mean at discrete times). Let η>0 and δu=u-(τ-2). For any ε>0 and M>0, 3.9 where we recall the definition of oT(1) from Proposition 2.13. Proof The proof is split between the cases t∈[ε,u/2], t∈[u/2,u-ε] and t∈[u-ε,u-u-(τ-2)], where t=kδu and ε>0 is some arbitrary constant. Proof for t∈[ε,u/2]. We start by proving the proposition for t∈[ε,u/2], for which we use Proposition 2.7 with λ1=±1 and λ2=0 to see that, for any x>0, 3.10 P~(|St-E~[St]IV(t/u)uτ-3|>x)≤ce-x, where we note that the eΘ error term can be put inside the constant c since |Θ|≤ou(1)+O(t3(τ-3)) and t≥ε is strictly positive. By (2.32) in Lemma 2.10, IV(p)≤cpτ-3 for all p∈[0,1/2]. Applying this to p=t/u yields 3.11 P~|St-E~[St]|>cxt(τ-3)/2≤ce-x. By Corollary 2.5(a), we have E~[St]/(tuτ-3)∈[c_,c¯] for t∈[ε,u/2] and some constants c_,c¯>0. Therefore, taking x=aηt12(5-τ)uτ-3 for some a>0 chosen appropriately, 3.12 P~|St-E~[St]|>ηE~[St]≤ce-aηt12(5-τ)uτ-3. We take t=kδu for kδu∈[ε,u/2], so that there are at most u/δu=uτ-1possible values of k. Thus, 3.13 P~∃tk∈[ε,u/2]:|Stk-E~[Stk]|>ηE~[Stk]≤c(ϵ)uτ-1e-aηu(τ-1)/2. This proves the proposition for kδu∈[ε,u/2]. Proof for t∈[u/2,u-ε]. We continue by proving the proposition for t∈[u/2,u-ε], for which we again use Proposition 2.7 with λ1=±1 and λ2=0 to see that, for any x>0, 3.14 P~(|St-E~[St]IV(t/u)uτ-3|>x)≤ce-x. By Lemma 2.10 and the fact that IV(p)>0 for every p∈(0,1), we obtain that there exists a constant c>0 such that IV(p)≥c for all p∈[1/2,1-ε]. Applying this to p=t/u yields 3.15 P~|St-E~[St]|>cxu(τ-3)/2≤ce-x. By Lemma 2.4(d) and Corollary 2.5(b), we have E~[St]u-(τ-2)∈[c_,c¯] for all t∈[u/2,u-ε] and some constants c_=c_(ε),c¯=c¯(ε)>0. Therefore, taking x=aηu(τ-1)/2 for some a>0 chosen appropriately, 3.16 P~|St-E~[St]|>ηE~[St]≤ce-aηu(τ-1)/2. We take t=tk=kδu for kδu∈[u/2,u-ε], so that there are at most u/δu=uτ-1 possible values of k. Thus, 3.17 P~∃tk∈[u/2,u-ε]:|Stk-E~[Stk]|>ηE~[Stk]≤c(ϵ)uτ-1e-aηu(τ-1)/2. This proves the proposition for kδu∈[u/2,u-ε]. Proof for t∈[u-ε,u-Tu-(τ-2)]:
{'source': 'PubMedDataset'}