Phase transition on the fluctuation of the structure of random walk ranges Thanks: Research supported in part by JSPS KAKENHI Grant-in-Aid for Early-Career Scientists (No. JP24K16931) (I.O.). Thanks: Research partially supported by NSF grant DMS 2102842 Arka Adhikari, Izumi Okada Abstract . We investigate fluctuation phenomena for the graph distance and the number of cut points associated with random media arising from the range of a random walk. Our results demonstrate a sequence of dimension-dependent phase transitions in the scaling behavior of these fluctuations, leading to qualitatively different regimes across dimensions lower than six, equal to six, and higher than six. In particular, in six dimensions, we show that the convergence to the normal distribution occurs under a scaling different from that of the standard central limit theorem. We also give the related results for the effective resistance of the random walk range. 1. Random walk on random walk range Consider the simple random walk (S_{n})_{n=0}^{\infty} on {\mathbb{Z}}^{d} for d\geq 4 . We define the graph of the random walk range as follows: \displaystyle V({\mathcal{G}}):=\{S_{m}:m\geq 0\}, \displaystyle E({\mathcal{G}}):=\{\{S_{m},S_{m+1}\}:m\geq 0\}. Originally, Lawler and Burdzy [ 5 ] discussed the exponents for the fluctuation of the random walk range and proposed many open problems. Croydon and Shiraishi [ 11 , 20 , 21 ] estimated the graph distance, the effective resistance of (V({\mathcal{G}}),E({\mathcal{G}})) and the number of cut points of the random walk range between S_{0} and S_{n} in d=4 , and showed that their typical order is n/(\log n)^{1/2+o(1)} . In addition, Croydon [ 7 ] did similar work in d\geq 5 , and showed that their typical order is linear. In [ 22 ] , he discussed the loop erased random walk and other related concepts for the graph of the random walk range in d=2,3 . As our motivation, random walks in random media have attracted considerable interest as mathematical models for transport phenomena in disordered environments. Typical examples include random conductance models, random walks in random environments, and random walks on percolation clusters. One of the central themes in this area is to understand how the geometry and randomness of the underlying medium influence the long-time behavior of the walk (e.g., see [ 8 , 9 ] ). For example, for supercritical percolation clusters on {\mathbb{Z}}^{d} with d\geq 2 , the walk behaves diffusively, in close analogy with the simple random walk on {\mathbb{Z}}^{d} (e.g., see [ 3 ] ). The situation is markedly different at criticality. In highly irregular media, such as large critical percolation clusters, it is widely believed that the random walk exhibits subdiffusive behavior (e.g., [ 19 ] ). In addition, [ 8 , 10 ] deal with time changes of processes on resistance spaces, which cover the case when the resistance has a non-trivial scaling limit. We refer the reader to [ 14 ] for further references on these topics. An important tool for analyzing random walks in random media is the effective resistance or graph distance associated with the underlying random media. In particular, the behavior of the effective resistance is closely connected to the spectral dimension of the random subset, which characterizes the long-time decay of return probabilities and provides a key indicator of whether the associated random walk exhibits diffusive or anomalous scaling. Independent of the study of random walks on random media, understanding the graph distance in random media is of intrinsic interest. The graph distance captures the geometry induced by the random environment itself and provides a natural notion of distance that reflects how connectivity and paths are shaped by randomness. The behavior of graph distance plays a central role in a variety of problems, including volume growth, metric scaling, and universality phenomena in random geometry. In particular, in light of recent developments, it is conjectured that graph distances in several models of random media exhibit non-trivial scaling behavior, potentially related to general universality phenomena. These considerations provide strong motivation for a detailed analysis of graph distances in random media, which is a focus of the present work. Motivated by these considerations, we aim to understand the fluctuation behavior of the effective resistance and the graph distance in random media. In this paper, we take the range of a random walk as a concrete example of a random medium. According to the results of Croydon [ 7 ] , in d\geq 5 the leading-order behavior is linear regardless of the dimension and does not possess a phase transition, which naturally raises the question of how fluctuations behave around this leading term. Our analysis reveals that the fluctuation behavior depends sensitively on the dimension. In particular, we find distinct regimes in dimensions four, five, six, and seven and higher. A major phase transition occurs at dimension six: for d\geq 6 , the fluctuations, when normalized by the square root of the variance, converge in distribution to a Gaussian random variable, whereas in dimensions four and five, the same normalization leads to convergence to zero. We also note that the variance of the normal random variable in d=6 that appears in the central limit theorem is non-standard in the sense that it is actually not equal to the variance of the original random variable. Moreover, our proofs suggest that in dimensions four and five, if the fluctuations are rescaled by the appropriate order, they are expected to converge to non-Gaussian random variables. We will give the definitions necessary to state the main results. We consider the graph {\mathcal{G}}[a,b] as the set of edges constructed by the random walk trace: \displaystyle E({\mathcal{G}}[a,b]):=\{\{S_{m},S_{m+1}\}:a\leq m\leq b-1\}. The graph distance between two points, as is standard, counts the number of edges in the shortest path connecting them in the graph. In addition, we define the number of cut points on \mathcal{G}[1,n] by \displaystyle\sum_{i=2}^{n}1\{S[1,i-1]\cap S[i,n]=\emptyset\}. We define a quadratic form \mathcal{E} on functions f,g:V(G)\to\mathbb{R} by \mathcal{E}(f,g)=\frac{1}{2}\sum_{\begin{subarray}{c}x,y\in V\\ \{x,y\}\in E\end{subarray}}(f(x)-f(y))(g(x)-g(y)). This corresponds to the energy dissipation of the resistance electrical network on G . We also introduce the space H^{2}:=\{\,f\in\mathbb{R}^{V}:\mathcal{E}(f,f)<\infty\,\}, which serves as the natural domain of the energy form. The effective resistance between A and B is defined via the energy minimization R_{G}(A,B)^{-1}\;=\;\inf\Biggl\{\mathcal{E}(f,f)\;\Big|\;\quad f|_{A}=1,\ f|_{B}=0,f\in H^{2}\Biggr\}. This quantity represents the voltage difference required to send the current from A to B and therefore corresponds to the usual notion of effective resistance in an electrical network. For vertices x,y\in V , we write R_{G}(x,y) to denote R_{G}(\{x\},\{y\}) . We will now define the notation used to represent the graph distance, the effective resistance, and the number of cut points. Let X^{1}_{[a,b]}(x,y):=d_{\mathcal{G}_{[a,b]}}(x,y) , X^{2}_{[a,b]}(i,j) be the number of cut points on \mathcal{G}_{[a,b]} between the time i and j , and X^{3}_{[a,b]}(x,y):=R_{\mathcal{G}_{[a,b]}}(x,y) . A trivial relationship among these variables is X^{3}_{[a,b]}(x,y)\leq X^{1}_{[a,b]}(x,y) and X^{2}_{[a,b]}(i,j)\leq X^{3}_{[a,b]}(S_{i},S_{j}) . We sometimes write X^{i}[a,b] as X^{i}_{[a,b]}(S_{a},S_{b}) and X^{i}_{n}=X^{i}_{[0,n]}(S_{0},S_{n}) for i=1,3 and X^{2}[a,b] as X^{2}_{[a,b]}(a,b) and X^{2}_{n}=X^{2}_{[1,n]}(1,n) . Since the following proof is the same, we omit the symbol “ i ”, wherever it appears. To ease the presentation, we omit hereafter the integer-part symbol \lceil\cdot\rceil . If there exists c\in(0,\infty) such that ca_{n}\leq b_{n}\leq c^{-1}a_{n} , we write a_{n}\asymp b_{n} . In addition, if a_{n}/b_{n}\to 1 as n\to\infty , we write a_{n}\sim b_{n} . If \log a_{n}/\log b_{n}\to 1 as n\to\infty , we write a_{n}\approx b_{n} . a_{n}\gg b_{n} means a_{n}/b_{n}\to\infty as n\to\infty and a_{n}\ll b_{n} means b_{n}/a_{n}\to\infty as n\to\infty . We write f(n)\lesssim g(n) if there exists a (deterministic) constant c>0 such that f(n)\leq cg(n) for all n , and f(n)\gtrsim g(n) if g(n)\lesssim f(n) . First, we will give our main results for the graph distance and the number of cut points: Proposition 1.1 . It holds that, as n\to\infty , \mathrm{Var}(X_{n})\quad\begin{cases}\sim\alpha^{i}_{d}n&\text{for }d\geq 7,\\ \asymp n\log n&\text{for }d=6,\\ \asymp n^{3/2}&\text{for }d=5,\\ =\frac{n^{2}}{(\log n)^{2\pm o(1)}}&\text{for }d=4,\end{cases} for some constant \alpha^{i}_{d}>0 for i=1,2 . Theorem 1.2 . For d\geq 7 , as n\to\infty , \displaystyle\frac{X_{n}-\mathbb{E}X_{n}}{\sqrt{\mathrm{Var}(X_{n})}}\stackrel{{\scriptstyle d}}{{\rightarrow}}\mathcal{N}(0,1) and for d=6 , there is a deterministic function \phi(n)\asymp n\log n such that as n\to\infty , \displaystyle\frac{X_{n}-\mathbb{E}X_{n}}{\sqrt{\phi(n)}}\stackrel{{\scriptstyle d}}{{\rightarrow}}\mathcal{N}(0,1). For d=4,5 , as n\to\infty , \displaystyle\frac{X_{n}-\mathbb{E}X_{n}}{\sqrt{\mathrm{Var}(X_{n})}}\stackrel{{\scriptstyle d}}{{\rightarrow}}0. Next, we will give the result for the effective resistance. Proposition 1.3 . For d\geq 7 and \alpha^{3}_{d}>0 , as n\to\infty , \displaystyle\mathrm{Var}(X_{n})\sim\alpha^{3}_{d}n. For d=6 , \displaystyle\limsup_{n\to\infty}\frac{\mathrm{Var}(X_{n})}{n\log n}>0,\quad\limsup_{n\to\infty}\frac{\mathrm{Var}(X_{n})}{n(\log n)^{2}}<\infty. For d=5 , \displaystyle\mathrm{Var}(X_{n})\approx n^{3/2}. For d=4 and \epsilon>0 , \displaystyle\limsup_{n\to\infty}\frac{\mathrm{Var}(X_{n})}{n^{2}/(\log n)^{2+\epsilon}}>0,\quad\limsup_{n\to\infty}\frac{\mathrm{Var}(X_{n})}{n^{2}/(\log n)^{1-\epsilon}}<\infty. Theorem 1.4 . For d\geq 7 , as n\to\infty , \displaystyle\frac{X_{n}-\mathbb{E}X_{n}}{\sqrt{\mathrm{Var}(X_{n})}}\stackrel{{\scriptstyle d}}{{\rightarrow}}\mathcal{N}(0,1). for d=6 , there is a subsequence (n_{k}) and \phi(n)\geq cn(\log n) for some c>0 such that as n\to\infty , \displaystyle\frac{X_{n_{k}}-\mathbb{E}X_{n_{k}}}{\sqrt{\phi(n_{k})}}\stackrel{{\scriptstyle d}}{{\rightarrow}}\mathcal{N}(0,1). For d=5 , as n\to\infty , \displaystyle\frac{X_{n}-\mathbb{E}X_{n}}{\sqrt{\mathrm{Var}(X_{n})}}\stackrel{{\scriptstyle d}}{{\rightarrow}}0, and for d=4 , there is a subsequence (n_{k}) such that as n\to\infty , \displaystyle\frac{X_{n_{k}}-\mathbb{E}X_{n_{k}}}{\sqrt{\mathrm{Var}(X_{n_{k}})}}\stackrel{{\scriptstyle d}}{{\rightarrow}}0. Open problem 1.5 . Does a strong law of large numbers hold for X_{n} ? (In [ 11 ] , a weak law has been proved on (V({\mathcal{G}}),E({\mathcal{G}})) . In [ 21 , Remark 2.2.2] , the upper bound for a strong law for the effective resistance was essentially shown.) One of the difficulties in the proof is that X_{n} does not satisfy monotonicity with respect to n . Even if this obstacle could be overcome, especially in the case d=4 , the variance is not much smaller than that of \mathbb{E}[X_{n}]^{2} (they differ only by a factor of ``\log n" in d=4 ), so it seems unlikely that the result can be proved using standard concentration inequalities. Remark 1.6 . We believe that the stronger results of Propositions 1.1 and 1.2 are true for the effective resistance as well, but we avoid writing the extra technical details for simplicity. Instead, we present a weaker version that holds under weaker assumptions, such as without any correlation assumptions on the cross terms; we believe that the analysis performed in this section is of independent interest and can be readily applicable to any random variable on the random walk range that is governed by heavy tailed behavior. As a key ingredient of our approach to the analysis of fluctuations, we employ a decomposition of the random walk path. More precisely, we split the trajectory S[0,n] into two subpaths S[0,n/2] and S[n/2,n] , and compare the corresponding effective resistances or graph distances. The quantity X[0,n/2]+X[n/2,n]-X[0,n] naturally arises as error terms. By iterating this decomposition procedure, we obtain a representation consisting of a sum of finely decomposed random variables, which behave approximately as independent and identically distributed terms, together with accumulated error terms. A key observation is that a phase transition occurs depending on the dimension: while in dimensions d\geq 6 the sum of the i.i.d.-type terms dominates the fluctuations, in lower dimensions the error terms become dominant and significantly affect the scaling behavior. Consequently, it is expected that for d\geq 6 the fluctuations converge in distribution to a Gaussian random variable, whereas such Gaussian behavior does not persist in lower dimensions. We outline the main technical difficulties in the proof of our results. For the graph distance and the number of cut points, establishing the validity or failure of the central limit theorem, which constitutes our main theorem, requires a precise and delicate analysis of the variance. In particular, this analysis necessitates a careful control of the correlations among the error terms arising from the decomposition employed in the proof. As a first step, it is necessary to improve the result of [ 4 , Lemma 1.1] by identifying the optimal strategy for events in the large deviation regime that give rise to large error terms. We show that such events correspond to situations in which the random walk forms a large loop. The second step consists in estimating the correlations of these error terms. More precisely, one must show that these correlations are sufficiently small when the time intervals associated with the decomposition that generates the error terms are well separated. A technical difficulty to show the validity or failure of the central limit theorem is the fact that the large deviation probabilities governing these error terms exhibit heavy-tailed behavior. In fact, a related phenomenon for the decomposition was already observed in earlier work of the authors [ 1 , 2 , 12 ] concerning the capacity of the range of a random walk. In that setting, when analyzing fluctuations via a similar decomposition scheme, a phase transition occurred between dimensions four and five, depending on which term became dominant in the decomposition. While this qualitative behavior is closely related to the phenomena studied in the present paper, the analysis in our current setting requires substantially different techniques. More specifically, in the previous work the error terms arising from the decomposition became negligible in dimensions d\geq 5 , whereas in the present case the error terms remain of polynomial order even for d\geq 6 , necessitating a much more delicate analysis. Moreover, although in dimension four the error terms are leading in both settings, their control in the present work requires global information on the entire path, leading to more intricate estimates. We also obtained partial results for the effective resistance; however, the resulting bounds are weaker than those for the other quantities. This is due to technical difficulties arising in the estimation of the correlations of the error terms. Nevertheless, even without a detailed analysis of these correlations, once an estimate of the error terms corresponding to an improvement of [ 4 , Lemma 1.1] is available, we are able to obtain an analogy that yields a phase transition for the central limit theorem of the effective resistance under weaker assumptions on the error terms. We believe that this analogy is useful for a broad class of random variables for which a decomposition of the type considered in this work can be carried out. 2. Preparations in d\geq 5 In this section, we will establish various estimates that will allow us to understand the cross terms that appear in the course of our analysis. We will give the definitions here. Consider the error term E_{n}:=X^{i}[0,n]+X^{i}[n,2n]-X^{i}[0,2n]. In general, we may write \displaystyle E_{n}^{(k,l)}(i):= \displaystyle X^{i}\bigg[\frac{2l}{2^{k+1}}n,\frac{2l+1}{2^{k+1}}n\bigg]+X^{i}\bigg[\frac{2l+1}{2^{k+1}}n,\frac{2l+2}{2^{k+1}}n\bigg]-X^{i}\bigg[\frac{l}{2^{k}}n,\frac{l+1}{2^{k}}n\bigg]. Since the following proofs do not depend on the quantity of interest, we omit the symbol“ i ”, wherever it appears. In the next lemma, we improve the result of [ 4 , Lemma 1.1] . We will use the following asymptotics on the tail probabilities of E_{n} in the following sections. Lemma 2.1 . Let d\geq 5 . There exist some constants 0n)\leq a_{1}+a_{2}. By the same proof in [ 4 , Lemma 1.1] (which essentially computes the probability of having a large loop), we can obtain (2.4) \displaystyle a_{1}\leq C(J)n^{-\frac{d}{2}+2}. Note that if S(-\infty,k_{3j}-1]\cap S[k_{3j+1},\infty)=\emptyset , S(-\infty,k_{3j+2}-1]\cap S[k_{3j+3},\infty)=\emptyset and N([1,n])=0 , then N([k_{3j+1},k_{3j+2}-1],[k_{3j},k_{3j+3}-1])=0 . To see the reason for this, note that N([1,n])=0 means that no point in the interval [k_{3j+1},k_{3j+2}-1] can be a cut point; thus, for t\in[k_{3j+1},k_{3j+2}-1] , we must have that S(-\infty,t-1]\cap S[t,\infty)\neq\emptyset . However, since S(-\infty,k_{3j}-1]\cap S[k_{3j+1},\infty)=\emptyset and S(-\infty,k_{3j+2}-1]\cap S[k_{3j+3},\infty)=\emptyset , S[k_{3j},t-1]\cap S[t,k_{3j+3}-1]\neq\emptyset holds instead. Hence, \displaystyle a_{2}\leq\mathbb{P}\bigg(\bigcap_{j=1}^{J}\{N([k_{3j+1},k_{3j+2}-1],[k_{3j},k_{3j+3}-1])=0\}\bigg). For 0\leq j0 (it should not depend on J ), \displaystyle\hat{a}_{1}+\hat{a}_{2}\ll n^{-\delta} and hence \displaystyle a_{2}\leq C(J)(n^{-\delta})^{J}. Therefore, if we pick sufficiently large J , we obtain a_{2}\leq Cn^{-\frac{d}{2}+2} and in addition the desired result follows by combining ( 2.3 ) and ( 2.4 ). ∎ Proof of ( 2.2 ). We start by defining a collection of sets which, when they hold together, will imply E_{n}>cn for an appropriate constant c . Let \displaystyle D_{1}:=\{\ X[n,2n]\geq c_{d}n\}, \displaystyle D_{2}:=\{{\rm Cap}(S[2n-sn,2n])\geq c^{\prime}_{d}sn\}, \displaystyle D_{3}:=\{\max_{2n-sn\leq i\leq 2n}\|S_{i}-S_{n}\|\leq C_{1}n^{1/2}\}, \displaystyle D_{4}:=\{\|S_{sn}-S_{n}\|\leq C_{1}n^{1/2}\}. Here, c_{d} and c_{d}^{\prime} are some dimension-dependent constants, (by the law of large numbers for the capacity of the random walk range, we choose c_{d}^{\prime} to satisfy {\rm Cap}(S[0,n])\sim 2c^{\prime}_{d}n ). Recall the (slightly modified) definition of T^{1} as the first cut point after time n . By [ 7 , Lemma 2.2] , we know that there is c_{d}>0 such that \mathbb{P}(X^{2}_{(-\infty,\infty)}[T^{1},n+T^{1}]\geq c_{d}n)=1-o(1) . Noting that X^{2}_{(-\infty,\infty)}[a,b] will be a lower bound for X[a,b] for any times a and b and that X^{2}_{(-\infty,\infty)}[a,b] is monotonically increasing as we increase the interval [a,b] , we obtain \displaystyle\mathbb{P}(D_{1})\geq \displaystyle\mathbb{P}(T^{1}\leq n+f(n),X^{2}_{(-\infty,\infty)}[T^{1},2n]\geq c_{d}n/2)-\mathbb{P}(T^{1}\geq n+f(n)) \displaystyle\geq \displaystyle\mathbb{P}(X^{2}_{(-\infty,\infty)}(0,n-f(n))\geq c_{d}n/2|0\text{ is cut point})-\mathbb{P}(T^{1}\geq n+f(n))=1-o(1) if f(n)=o(n) and f(n)\to\infty as n\to\infty with the aid of the estimate in the proof of ( 2.1 ). Moreover, we have \mathbb{P}(D_{2})=1-o(1) (see [ 13 ] ) and for any \epsilon>0 , there is C_{1}<\infty such that \mathbb{P}(D_{i})\geq 1-\epsilon for i=3,4 by the local central limit theorem and the reflection principle for random walks (see [ 15 , Theorem 1.2.1] ). Hence, if we pick sufficiently large C_{1}<\infty , we have \mathbb{P}(\cap_{i=1}^{4}D_{i})\geq 1/2 . Let us define the set A:=S[2n-sn,2n] and z:=S_{sn} . On the event D_{1}\cap D_{2} , we see that we have \max_{x\in A}\|x-z\|\leq 2C_{1}n^{1/2} . We now reverse the random walk S_{0},\ldots,S_{sn} , to create a new random walk \tilde{S}_{0},\ldots,\tilde{S}_{sn} , defined as, \tilde{S}_{i}:=S_{sn-i}-S_{sn}. \tilde{S} is distributed as a random walk starting at the point z and, conditional on the value of z , it is independent of A . We now seek to compute the probability that the random walk \tilde{S} intersects the set A . To do this, we derive a last hitting time decomposition of the random walk \tilde{S} with the set A before time sn , by considering the last time of intersection between \tilde{S} and the set A . Then, \displaystyle\mathbb{P}^{z}(T_{A}sn-i) \displaystyle\geq\sum_{x\in A}\sum_{i=1}^{sn}\mathbb{P}^{z}(\tilde{S}_{i}=x)\mathbb{P}^{x}(T_{A}=\infty) \displaystyle\geq\min_{a\in A}\sum_{i=1}^{sn}\mathbb{P}^{z}(\tilde{S}_{i}=a)\sum_{x\in A}\mathbb{P}^{x}(T_{A}=\infty) \displaystyle=\min_{a\in A}\sum_{i=1}^{sn}\mathbb{P}^{z}(\tilde{S}_{i}=a){\rm Cap}(A)\geq c(s)n^{-d/2+1}{\rm Cap}(A). In the last line, we used the local central limit theorem. It is important that \|x-z\|0 . As a consequence, we obtain the following lemma. Lemma 2.4 ( d=6 ) . We have the following estimates for the error terms E_{n} . \mathbb{E}[E_{n}]\lesssim(\log n),\quad\mathbb{E}[E_{n}^{2}]\asymp n. As a consequence of the first and last inequality above, we have that \mathrm{Var}(E_{n})\gtrsim n . Let \Omega_{n} be the event that \mathbb{E}[E_{n}]-E_{n}\geq 0 , then, we have that (2.5) \mathbb{E}[(E_{n}-\mathbb{E}[E_{n}])^{2}\mathbbm{1}[\Omega_{n}]]\lesssim(\log n)^{2}\ll n. The previous equation implies that the largest contribution to the variance of E_{n} occurs when E_{n}-\mathbb{E}[E_{n}] is positive. Proof. Most of the previous estimates are a consequence of the layer cake representation of the expectation. For example, we have \mathbb{E}[E_{n}]=\sum_{l=1}^{n}\mathbb{P}(E_{n}\geq l)\lesssim\sum_{l=1}^{n}\frac{1}{l}\lesssim(\log n). In addition, we have \mathbb{E}[E_{n}^{2}]=\sum_{l=1}^{n}l\mathbb{P}(E_{n}\geq l)\lesssim\sum_{l=1}^{n}\frac{1}{l}l\lesssim\sum_{l=1}^{n}1=n. Finally, we have, \mathbb{E}[E_{n}^{2}]=\sum_{l=1}^{n}l\mathbb{P}(E_{n}\geq l)\gtrsim\sum_{l=an}^{bn}l\frac{1}{l}\gtrsim n. Since E_{n}\geq 0 , we have that \mathbb{E}[E_{n}]-E_{n}\lesssim\log n . This gives us the final estimate we desire. ∎ 3. Proof of CLT for d\geq 7 In this section, we will show the central limit theorem for d\geq 7 . 3.1. Proof of variance In this subsection, we will give the estimate of the variance. Lemma 3.1 . For d\geq 7 , \displaystyle\mathrm{Var}(X^{(i)}_{n})\sim\alpha_{d}^{i}n with \alpha_{d}^{i}>0 for i=1,2,3 . To show it, we first prove the following lemma. Lemma 3.2 . For d\geq 7 , the limit \lim_{n\to\infty}\frac{\operatorname{Var}(X_{n})}{n} exists. For simplicity, we write \overline{X}:=X-\mathbb{E}[X] . Proof. We refer to [ 18 , Lemma 6.2] . Define a_{k}=\sup\left\{\|\overline{X}_{n}\|_{2}:2^{k}\leq n<2^{k+1}\right\}, where \|X\|_{m}:=\mathbb{E}[|X|^{m}]^{1/m} for m\geq 1 . For k\geq 2 , let n be such that 2^{k}\leq n<2^{k+1} . Taking expectations and using the triangle inequality, we obtain \|\overline{X}_{2n}\|_{2}\leq\|\overline{X}_{n}+\overline{X}[n,2n]\|_{2}+2\max\left(\|E_{n}\|_{2},\mathbb{E}[E_{n}]\right). Since X_{n} and X[n+1,2n] are independent, we have \|\overline{X}_{n}+\overline{X}[n+1,2n]\|_{2}=\left(\|\overline{X}_{n}\|_{2}^{2}+\|\overline{X}[n,2n]\|_{2}^{2}\right)^{1/2}. Using ( 2.1 ) and that \max\left(\|E_{n}\|_{2},\mathbb{E}[E_{n}]\right)\leq C(\log n)^{M} for d\geq 8 and \max\left(\|E_{n}\|_{2},\mathbb{E}[E_{n}]\right)\leq n^{1/4} for d=7 , we find \|\overline{X}_{2n}\|_{2}\leq\left(\|\overline{X}_{n}\|_{2}^{2}+\|\overline{X}[n,2n]\|_{2}^{2}\right)^{1/2}+c_{1}n^{1/4}. From the definition of a_{k} , it follows that a_{k}\leq\sqrt{2}a_{k-1}+c_{2}2^{k/4}, for some constant c_{2} . Setting b_{k}=\frac{a_{k}}{2^{k/2}} , we get a recursive inequality b_{k}\leq b_{k-1}+c_{1}2^{-k/4} . This implies a_{k}\lesssim 2^{k/2} , and hence \operatorname{Var}(X_{n})\lesssim n. Letting \gamma_{n}=\mathbb{E}[(X_{n}-\mathbb{E}[X_{n}])^{2}] , we have \gamma_{n+m}\leq\gamma_{n}+\gamma_{m}+\delta_{n+m},\quad\gamma_{n+m}\geq\gamma_{n}+\gamma_{m}-\delta_{n+m}^{\prime}, where \delta_{n+m},\delta_{n+m}^{\prime}=\mathcal{O}((n+m)^{3/4}) . Indeed, if n\leq m and E_{n,m}:=X_{n}+X[n,n+m]-X_{n+m} , \displaystyle\gamma_{n+m}= \displaystyle\gamma_{n}+\gamma_{m}+2\mathbb{E}[(X_{n}-\mathbb{E}[X_{n}])(E_{n,m}-\mathbb{E}[E_{n,m}])] \displaystyle+ \displaystyle\mathbb{E}[(X[n,n+m]-\mathbb{E}[X[n,n+m]])(E_{n,m}-\mathbb{E}[E_{n,m}])]+\mathbb{E}[(E_{n,m}-\mathbb{E}[E_{n,m}])^{2}]. Then, the Cauchy-Schwarz inequality would give, \displaystyle\mathbb{E}[(X_{n}-\mathbb{E}[X_{n}])(E_{n,m}-\mathbb{E}[E_{n,m}])] \displaystyle\leq\mathbb{E}[(X_{n}-\mathbb{E}[X_{n}])^{2}]^{1/2}\mathbb{E}[(E_{n,m}-\mathbb{E}[E_{n,m}])^{2}]^{1/2}\lesssim n^{1/2}m^{1/4}, \displaystyle\mathbb{E}[(X[n,n+m]-\mathbb{E}[X[n,n+m]])(E_{n,m}-\mathbb{E}[E_{n,m}])]\lesssim m^{1/2}m^{1/4}, \displaystyle\mathbb{E}[(E_{n,m}-\mathbb{E}[E_{n,m}])^{2}]\lesssim m^{1/2} and hence \displaystyle\max(\delta_{n+m},\delta_{n+m}^{\prime})\lesssim(m^{1/2}m^{1/4}+m^{1/2}). Therefore, by Hammersley’s lemma, the existence of the limit \lim_{n\to\infty}\frac{\gamma_{n}}{n} follows. ∎ To show that the above limit is positive, we will give a toy model to understand the proof. Lemma 3.3 (Toy model) . We consider i.i.d. (Y_{i})_{i=1}^{\infty} such that \mathbb{P}(Y_{i}=1)=p for 0T_{i-1}:Y_{s}\neq 1\} and \hat{G}_{m}=\{l\leq m:T_{l+1}-T_{l}=2\text{ or }3\} , G_{n}=\{l:T_{l+1}\leq n,T_{l+1}-T_{l}=2\text{ or }3\} , \mathcal{\hat{F}}_{m}:=\sigma((Y_{T_{l}})_{l=1}^{m}\cup\cup_{l\notin\hat{G}_{m}}(Y_{i})_{i=T_{l}+1}^{T_{l+1}-1}) , \mathcal{F}_{n}:=\sigma((Y_{T_{l}\wedge n})_{l=1}^{\infty}\cup\cup_{l\notin G_{n}}(Y_{i})_{i=T_{l}+1}^{T_{l+1}-1}) . Set \hat{D}_{m}:=\{i\in[1,T_{m}]:Y_{i}=1\} , D_{n}:=\{i\in[1,n]:Y_{i}=1\} . Let \mathbb{P}_{m} and \mathbb{E}_{m} be the probability and expectation for (Y_{l})_{l=1}^{T_{m}} and \displaystyle\hat{N}_{1} \displaystyle:=|\{i\in[1,T_{m}]:i-1,i+1\not\in\hat{D}_{m},i\in\hat{D}_{m}\}|, \displaystyle\hat{N}_{2} \displaystyle:=|\{i\in[1,T_{m}]:i-1,i+2\not\in\hat{D}_{m},i,i+1\in\hat{D}_{m}\}|. Moreover, let \displaystyle N_{1} \displaystyle:=|\{i\in[1,n]:i-1,i+1\not\in D_{n},i\in D_{n}\}|, \displaystyle N_{2} \displaystyle:=|\{i\in[1,n]:i-1,i+2\not\in D_{n},i,i+1\in D_{n}\}|. Namely, N_{1} denotes the number of events in which Y_{i}=1 occurs exactly once and N_{2} the number of events in which Y_{i}=1 appears exactly twice in a row. \mathbb{P}^{n} denotes the probability for (Y_{T_{l}\wedge n})_{l=1}^{\infty} . For large M , there exists c>0 such that \displaystyle A_{n}:=\{|N_{1}-\mathbb{E}[N_{1}]|\leq M\sqrt{n},\quad|N_{2}-\mathbb{E}[N_{2}]|\leq M\sqrt{n}\}, (3.1) \displaystyle\mathbb{P}(A_{n})>c>0. In addition, for |a-\mathbb{E}_{m}[\hat{N}_{1}]|\leq\sqrt{m} , |b-\mathbb{E}_{m}[\hat{N}_{2}]|\leq\sqrt{m} and c\leq\sqrt{m} , (3.2) \displaystyle\mathbb{P}_{m}(\hat{N}_{1}=a,\hat{N}_{2}=b+c|\mathcal{\hat{F}}_{m})\leq C\mathbb{P}_{m}(\hat{N}_{1}=a+c,\hat{N}_{2}=b|\mathcal{\hat{F}}_{m}). Eventually, for |a-\mathbb{E}[N_{1}]|\leq M\sqrt{n} , |b-\mathbb{E}[N_{2}]|\leq M\sqrt{n} , (3.3) \displaystyle\mathbb{P}^{n}(N_{1}=a,N_{2}=b+\sqrt{n})\leq C\mathbb{P}^{n-\sqrt{n}}(N_{1}=a+\sqrt{n},N_{2}=b). Proof. It is easy to see that \mathbb{P}(||G_{n}|-\mathbb{E}[|G_{n}|]|\leq\sqrt{n})>c . Since (T_{l+1}-T_{l})_{l=1}^{m} is i.i.d. and \mathbb{E}_{m}[\hat{N}_{1}]=p(1-p)m , \mathbb{E}_{m}[\hat{N}_{2}]=p^{2}(1-p)m , by the central limit theorem for the sum of Bernoulli random variables, there exists c>0 such that \displaystyle\hat{A}_{m}:=\{|\hat{N}_{1}-\mathbb{E}_{m}[\hat{N}_{1}]|\leq\sqrt{m},\quad|\hat{N}_{2}-\mathbb{E}_{m}[\hat{N}_{2}]|\leq\sqrt{m}\}, \displaystyle\mathbb{P}(\hat{A}_{m})>c>0. We now define m to be the largest value of l such that T_{l}\leq n . We consider values of m that satisfy |m-\mathbb{E}[|G_{n}|]|\leq\sqrt{n} . Under these conditions, note that if |\hat{N}_{1}-\mathbb{E}_{m}[\hat{N}_{1}]|\leq\sqrt{m} , then |\mathbb{E}[N_{1}]-\mathbb{E}_{m}[\hat{N}_{1}]|+\sqrt{m}=O(\sqrt{n}) and hence |N_{1}-\mathbb{E}[N_{1}]|=|\hat{N}_{1}-\mathbb{E}[N_{1}]|\leq M\sqrt{n} for large M<\infty . In addition, if |\hat{N}_{2}-\mathbb{E}_{m}[\hat{N}_{2}]|\leq\sqrt{m} , then |N_{2}-\mathbb{E}[N_{2}]|\leq M\sqrt{n} for large M<\infty . Then, \displaystyle\mathbb{P}(A_{n})\geq \displaystyle\mathbb{P}(||G_{n}|-\mathbb{E}[|G_{n}|]|\leq\sqrt{n}) \displaystyle\times \displaystyle\mathbb{P}\left(|N_{1}-\mathbb{E}[N_{1}]|\leq M\sqrt{n},|N_{2}-\mathbb{E}[N_{2}]|\leq M\sqrt{n}\bigg|||G_{n}|-\mathbb{E}[|G_{n}|]|\leq\sqrt{n}\right) \displaystyle\geq \displaystyle c\min_{|m-\mathbb{E}[|G_{n}|]|\leq\sqrt{n}}\mathbb{P}\left(|N_{1}-\mathbb{E}[N_{1}]|\leq M\sqrt{n},|N_{2}-\mathbb{E}[N_{2}]|\leq M\sqrt{n}\bigg||G_{n}|=m\right) \displaystyle\geq \displaystyle c\min_{|m-\mathbb{E}[|G_{n}|]|\leq\sqrt{n}}\mathbb{P}_{m}(\hat{A}_{m})\geq c and hence we obtain ( 3.1 ). Noting that \mathbb{P}_{m}(\cdot|\mathcal{\hat{F}}_{m}) is the conditional probability that specifies the value of the variable Y_{i} except at those locations where Y_{i} occurs exactly once or twice in a row. Under this conditional probability, we are potentially allowed to change these locations where Y_{i} occurs exactly once to those where Y_{i} occurs twice in a row or vice versa. Then, comparing the combinations, we notice that \displaystyle\frac{\mathbb{P}_{m}(\hat{N}_{1}=a,\hat{N}_{2}=b+c|\mathcal{\hat{F}}_{m})}{\mathbb{P}_{m}(\hat{N}_{1}=a+c,\hat{N}_{2}=b|\mathcal{\hat{F}}_{m})}=\frac{(a+b+c)!}{a!(b+c)!}p^{a}p^{2(b+c)}\times\bigg(\frac{(a+b+c)!}{(a+c)!b!}p^{a+c}p^{2b}\bigg)^{-1}. Hence, Stirling’s formula yields ( 3.2 ). Similarly, \displaystyle\frac{\mathbb{P}^{n}(N_{1}=a,N_{2}=b+\sqrt{n})}{\mathbb{P}^{n-\sqrt{n}}(N_{1}=a+\sqrt{n},N_{2}=b)}=\frac{(a+b+\sqrt{n})!}{a!(b+\sqrt{n})!}p^{a}p^{2(b+\sqrt{n})}\times\bigg(\frac{(a+b+\sqrt{n})!}{(a+\sqrt{n})!b!}p^{a+\sqrt{n}}p^{2b}\bigg)^{-1} and Stirling’s formula yields ( 3.3 ). ∎ Lemma 3.4 . It holds that \alpha_{d}>0 . Proof. Set D:=\{i\in[0,n/2]:S_{2i}=S_{2i+2}=S_{2i+1}+e\} , where e is some unit vector, Y_{i}:=1\{i\in D\} and T_{i}=\{s>T_{i-1}:Y_{s}\neq 1\} . Let \displaystyle N_{1} \displaystyle:=|\{i\in[1,n/2]:i-1,i+1\not\in D,i\in D\}|, \displaystyle N_{2} \displaystyle:=|\{i\in[1,n/2]:i-1,i+2\not\in D,i,i+1\in D\}|, and \mathbb{P}^{n} denotes the probability for (Y_{T_{l}\wedge(n/2)})_{l=1}^{\infty} . By ( 3.1 ), there exists c_{1}>0 such that \displaystyle A_{n}:=\{|N_{1}-\mathbb{E}[N_{1}]|\leq M\sqrt{n},\quad|N_{2}-\mathbb{E}[N_{2}]|\leq M\sqrt{n}\}, \displaystyle\mathbb{P}(A_{n})>c_{1}>0. In addition, by ( 3.3 ), for any d>0 , \displaystyle\mathbb{P}^{n}(X_{n}=d,A_{n}) \displaystyle= \displaystyle\sum_{\begin{subarray}{c}|a-\mathbb{E}[N_{1}]|\leq M\sqrt{n},\\ |b-\mathbb{E}[N_{2}]|\leq M\sqrt{n}\end{subarray}}\mathbb{P}^{n}(X_{n}=d,N_{1}=a,N_{2}=b+\sqrt{n}) \displaystyle\leq \displaystyle c_{2}\sum_{\begin{subarray}{c}|a-\mathbb{E}[N_{1}]|\leq M\sqrt{n},\\ |b-\mathbb{E}[N_{2}]|\leq M\sqrt{n}\end{subarray}}\mathbb{P}^{n-\sqrt{n}}(X_{n-\sqrt{n}}=d,N_{1}=a+\sqrt{n},N_{2}=b) \displaystyle\leq \displaystyle c_{2}\mathbb{P}(X_{n-\sqrt{n}}=d). Now, assume for contradiction that for any \epsilon>0 , as n\to\infty , (3.4) \displaystyle\mathbb{P}(|\overline{X}_{n}|\leq\epsilon\sqrt{n})\to 1. Since \mathbb{E}X_{n}/n\to c_{0} by Remark 2.3 , we have \limsup_{n\to\infty}(\mathbb{E}X_{n}-\mathbb{E}X_{n-\sqrt{n}})/\sqrt{n}\geq c_{3} for some c_{3}>0 . Indeed, if \limsup_{n\to\infty}(\mathbb{E}X_{n}-\mathbb{E}X_{n-\sqrt{n}})/\sqrt{n}c and this contradicts ( 3.4 ). Therefore, we obtain \liminf_{n\to\infty}\mathbb{P}(|\overline{X}_{n}|\leq\epsilon\sqrt{n})<1 and hence \alpha_{d}>0 . ∎ 3.2. Proof of CLT Lemma 3.5 . For d\geq 7 and for all n\in\mathbb{N} , we have \mathbb{E}[(\overline{X}_{n})^{2+\epsilon}]\lesssim n^{1+\epsilon/2}. Proof. Define a_{k}=\sup\left\{\|\overline{X}_{n}\|_{2+\epsilon}:2^{k}\leq n<2^{k+1}\right\}. Fix k\geq 2 , and let n satisfy 2^{k}\leq n<2^{k+1} . Then, by the triangle inequality, \|\overline{X}_{2n}\|_{2+\epsilon}\leq\|\overline{X}_{n}+\overline{X}[n,2n]\|_{2+\epsilon}+\|E_{n}\|_{2+\epsilon}, Using the inequality \displaystyle\|\overline{X}_{n}+\overline{X}[n,2n]\|_{2+\epsilon} \displaystyle\leq \displaystyle\big(\mathbb{E}[|\overline{X}_{n}|^{2+\epsilon}]+\mathbb{E}[|\overline{X}[n,2n]|^{2+\epsilon}]+C\mathbb{E}[|\overline{X}_{n}|^{1+\epsilon}]\mathbb{E}[|\overline{X}[n,2n]|] \displaystyle\hskip 28.45274pt+C\mathbb{E}[|\overline{X}_{n}|]\mathbb{E}[|\overline{X}[n,2n]|^{1+\epsilon}]\big)^{1/(2+\epsilon)}, and ( 2.1 ) and Lemma 3.2 , which gives \mathbb{E}[|\overline{X}_{n}|^{1+\epsilon}]\mathbb{E}[|\overline{X}[n,2n]|]\lesssim n^{1+\epsilon/2} , we obtain \|\overline{X}_{2n}\|_{2+\epsilon}\leq\left(\mathbb{E}[\overline{X}_{n}^{2+\epsilon}]+\mathbb{E}[\overline{X}[n,2n]^{2+\epsilon}]\right)^{1/(2+\epsilon)}+Cn^{1/2}. From the definition of a_{k} , it follows that a_{k}\leq 2^{1/(2+\epsilon)}a_{k-1}+c_{2}\cdot(2^{k})^{1/2}, for some constant c_{2}>0 . Define b_{k}=2^{-k/(2+\epsilon)}a_{k} . Then we get b_{k}\leq b_{k-1}+c_{2}2^{-k/(2+\epsilon)}(2^{k})^{1/2}, which implies that (b_{k})\lesssim 2^{-k/(2+\epsilon)}(2^{k})^{1/2} . Thus, a_{k}\lesssim 2^{k/2} , and hence for all n , \left(\mathbb{E}[\overline{X}_{n}^{2+\epsilon}]\right)^{1/(2+\epsilon)}\lesssim\sqrt{n}. This completes the proof. ∎ Proof of Theorem 1.1. We decompose X_{n} as follows: X_{n}=\sum_{i=1}^{2^{L}}\tilde{X}_{(L,i)}+\mathcal{E}, where \tilde{X}_{(L,i)}:=X[(i-1)n2^{-L},in2^{-L}] and \mathcal{E}:=-\sum_{k=0}^{L}\sum_{l=1}^{2^{k}}E_{n}^{(k,l)} . Set L=\lfloor\frac{1}{4}\log_{2}n\rfloor so that 2^{L}=n^{1/4} . Then, (3.5) \displaystyle\frac{\mathbb{E}[|\mathcal{E}|]}{\sqrt{n}}\lesssim\frac{n^{1/4}\log n}{\sqrt{n}}\to 0\quad\text{as }n\to\infty. Hence, it suffices to prove that \frac{1}{\sqrt{n}}\sum_{i=1}^{2^{L}}\left(\tilde{X}_{(L,i)}-\mathbb{E}[\tilde{X}_{(L,i)}]\right)\xrightarrow{d}\mathcal{N}(0,\alpha_{d}). We now apply the Lindeberg–Feller central limit theorem. We write Z_{L,i}:=\tilde{X}_{(L,i)}-\mathbb{E}[\tilde{X}_{(L,i)}] . We verify the Lindeberg–Feller conditions: (i) Variance Condition. By Lemma 3.3, we have \sum_{i=1}^{2^{L}}\operatorname{Var}(\tilde{X}_{(L,i)})\sim 2^{L}\cdot\alpha_{d}\cdot\frac{n}{2^{L}}=\alpha_{d}n, hence \frac{1}{n}\sum_{i=1}^{2^{L}}\operatorname{Var}(\tilde{X}_{(L,i)})\to\alpha_{d}>0. (ii) Lindeberg Condition. For any \epsilon>0 , we must show that as n\to\infty , \sum_{i=1}^{2^{L}}\frac{1}{n}\mathbb{E}\left[|Z_{L,i}|^{2}\cdot\mathbf{1}_{\{|Z_{L,i}|>\epsilon\sqrt{n}\}}\right]\to 0. Using Hölder and Chebyshev’s inequality: \mathbb{E}\left[|Z_{L,i}|^{2}\cdot\mathbf{1}_{\{|Z_{L,i}|>\epsilon\sqrt{n}\}}\right]\leq\mathbb{E}[|Z_{L,i}|^{2+\delta}]^{2/(2+\delta)}\mathbb{P}(|Z_{L,i}|\geq\epsilon\sqrt{n})^{\delta/(2+\delta)}. By Lemma 3.5 , \mathbb{E}[|Z_{L,i}|^{2+\delta}]^{2/(2+\delta)}\lesssim\frac{n}{2^{L}}. Furthermore, Chebyshev’s inequality should give, \mathbb{P}(|Z_{L,i}|>\epsilon\sqrt{n})\leq\frac{\mathrm{Var}(\tilde{X}_{L,i})}{\epsilon^{2}n}\lesssim\frac{n}{\epsilon^{2}n(2^{L})}=\frac{1}{\epsilon^{2}(2^{L})}. Thus, we have, \mathbb{E}\left[|Z_{L,i}|^{2}\cdot\mathbf{1}_{\{|Z_{L,i}|>\epsilon\sqrt{n}\}}\right]\leq\frac{n}{(\epsilon^{2})^{\delta/(2+\delta)}(2^{L})^{1+\delta/(2+\delta)}}. Finally, we can sum up all of the appropriate terms and see that, \sum_{i=1}^{2^{L}}\frac{1}{n}\mathbb{E}\left[|Z_{L,i}|^{2}\cdot\mathbf{1}_{\{|Z_{L,i}|>\epsilon\sqrt{n}\}}\right]\lesssim 2^{L}\frac{1}{n}\frac{n}{(\epsilon^{2})^{\delta/(2+\delta)}(2^{L})^{1+\frac{\delta}{(2+\delta)}}}\to 0, as n\to\infty and 2^{L}\to\infty . Therefore, both Lindeberg–Feller conditions are satisfied, and we conclude \frac{\sum_{i=1}^{2^{L}}(\tilde{X}_{(L,i)}-\mathbb{E}[\tilde{X}_{(L,i)}])}{\sqrt{n}}\xrightarrow{d}\mathcal{N}(0,\alpha_{d}) as n\to\infty and 2^{L}\to\infty and hence combining this with ( 3.5 ), we see that \displaystyle\frac{X_{n}-\mathbb{E}X_{n}}{\sqrt{\mathrm{Var}(X_{n})}}\stackrel{{\scriptstyle d}}{{\rightarrow}}\mathcal{N}(0,1) as n\to\infty . ∎ 4. 6 Dimensions In this section, we estimate the variance and the Limit in distribution of \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}} in d=6 . 4.1. Lower and Upper Bounds on the Variance 4.1.1. Graph distance and cut points Now, we produce an upper bound to the variance of the graph distance. Lemma 4.1 . We have the following upper bound on the variance of X_{n} : \mathrm{Var}(X_{n})\lesssim n(\log n). Proof. We now perform the full binary decomposition as, X_{n}=\sum_{k=0}^{\log_{2}n}\sum_{l=1}^{2^{k}}-E_{n}^{(k,l)}+\sum_{k=0}^{n}X[k,k+1]. We define the error term \mathcal{E}_{k}:=\sum_{l=1}^{2^{k}}-E_{n}^{(k,l)}. By independence of the components E_{n}^{(k,l)} , we have that, \mathrm{Var}(\mathcal{E}_{k})=\sum_{l=1}^{2^{k}}\mathrm{Var}(E_{n}^{(k,l)})\lesssim\sum_{l=1}^{2^{k}}\frac{n}{2^{k}}=n. Thus we have, by expanding the variance and applying the Cauchy-Schwarz inequality, that (4.1) \mathrm{Var}\left(\sum_{k=0}^{\log_{2}n}\mathcal{E}_{k}\right)\leq\sum_{k=0}^{\log_{2}n}\mathrm{Var}(\mathcal{E}_{k})+2\sum_{k_{1}=0}^{\log_{2}n}\sum_{k_{2}=0}^{\log_{2}n}\mathrm{Var}(\mathcal{E}_{k_{1}})^{1/2}\mathrm{Var}(\mathcal{E}_{k_{2}})^{1/2}\lesssim n(\log n)^{2}+n. In addition, since each X[k,k+1] is deterministically 1, we have that \mathrm{Var}(X[k,k+1])=0 . Then, we have \mathrm{Var}(X_{n})\lesssim n(\log n)^{2}. By our binary decomposition, we find that, for a_{n}=n/(\log n)^{3} , X_{n}=\sum_{l=1}^{a_{n}}X[(l-1)\frac{n}{a_{n}},l\frac{n}{a_{n}}]+\sum_{k=0}^{\log_{2}(a_{n})}\sum_{l=1}^{2^{k}}(-E_{n}^{(k,l)}). Now, we claim that \displaystyle\mathbb{E}[E_{n}^{(k_{1},l_{1})}E_{n}^{(k_{2},l_{2})}]\lesssim(\log n)^{2}. Let \tilde{S} be the reversal of the first part, that is \tilde{S}_{i}^{(k,l)}=S_{l\frac{n}{2^{k}}-i}-S_{l\frac{n}{2^{k}}} . \hat{S} will be the second part, that is \hat{S}_{i}^{(k,l)}=S_{l\frac{n}{2^{k}}+i}-S_{l\frac{n}{2^{k}}} . Indeed, if E_{n}^{(k,l)}\geq a , \Omega(a,k,l) holds, where \displaystyle\Omega(a,k,l):= \displaystyle\{\hat{S}^{(k,l)}[a/2,\frac{n}{2^{k}}]\cap\tilde{S}^{(k,l)}[0,\frac{n}{2^{k}}]\neq\emptyset\}(=:A_{1}^{(a,k,l)}) \displaystyle\bigcup\{\tilde{S}^{(k,l)}[a/2,\frac{n}{2^{k}}]\cap\hat{S}^{(k,l)}[0,\frac{n}{2^{k}}]\neq\emptyset\}(=:A_{2}^{(a,k,l)}). Then, \mathbb{E}[E_{n}^{(k_{1},l_{1})}E_{n}^{(k_{2},l_{2})}]=\sum_{a,b}\mathbb{E}[\mathbbm{1}[E_{n}^{(k_{1},l_{1})}\geq a]\mathbbm{1}[E_{n}^{(k_{2},l_{2})}\geq b]]\leq\sum_{a,b}\sum_{i,j=1}^{2}\mathbb{P}(A_{i}^{(a,k_{1},l_{1})}\cap A_{j}^{(b,k_{2},l_{2})}). In addition, \displaystyle\mathbb{P}(A_{1}^{(a,k_{1},l_{1})}\cap A_{1}^{(b,k_{2},l_{2})}) \displaystyle\leq \displaystyle\mathbb{P}\bigg(\{\hat{S}^{(k_{1},l_{1})}[\frac{a}{2},\frac{n}{2^{k_{1}}}]\cap\tilde{S}^{(k_{1},l_{1})}[0,\frac{n}{2^{k_{1}}}]\neq\emptyset\}\cap\{\hat{S}^{(k_{2},l_{2})}[\frac{b}{2},\frac{n}{2^{k_{2}}}]\cap\tilde{S}^{(k_{2},l_{2})}[0,\frac{n}{2^{k_{2}}}]\neq\emptyset\}\bigg) \displaystyle\leq \displaystyle\sum_{u_{1}=\frac{a}{2}+l_{1}\frac{n}{2^{k_{1}}}}^{(l_{1}+1)\frac{n}{2^{k_{1}}}}\sum_{u_{2}=(l_{1}-1)\frac{n}{2^{k_{1}}}}^{l_{1}\frac{n}{2^{k_{1}}}}\sum_{u_{3}=\frac{b}{2}+l_{2}\frac{n}{2^{k_{2}}}}^{(l_{2}+1)\frac{n}{2^{k_{2}}}}\sum_{u_{4}=(l_{2}-1)\frac{n}{2^{k_{2}}}}^{l_{2}\frac{n}{2^{k_{2}}}}\sum_{x}\sum_{y} \displaystyle\mathbb{P}(S_{u_{1}}=S_{u_{2}}=x,S_{u_{3}}=S_{u_{4}}=y). By [ 15 , Theorem 1.2.1] , letting p(x,n):=\frac{1}{(2d\pi n)^{d/2}}\exp(-\frac{|x|^{2}}{2dn}) for d=6 , we have that if |\frac{2l_{1}-1}{2^{k_{1}+1}}n-\frac{2l_{2}-1}{2^{k_{2}+1}}n|>\frac{n}{2^{k_{2}+1}} for k_{1}0 very close to 1. We will see where this condition plays a role close to the end of the proof. By our binary decomposition, we find that, (4.2) X_{n}=\sum_{l=1}^{n^{\delta}}X[(l-1)n^{1-\delta},ln^{1-\delta}]+\sum_{k=0}^{\log_{2}(n^{\delta})}\sum_{l=1}^{2^{k}}(-E_{n}^{(k,l)}). We will write MT:=\sum_{l=1}^{n^{\delta}}X[(l-1)n^{1-\delta},ln^{1-\delta}],\quad\mathcal{E}:=\sum_{k=0}^{\log_{2}(n^{\delta})}\sum_{l=1}^{2^{k}}(-E_{n}^{(k,l)}). We have that \mathrm{Var}(X_{n})=\mathrm{Var}(MT)+\mathrm{Var}(\mathcal{E})+2\text{Cov}(MT,\mathcal{E}) and \mathrm{Var}(\mathcal{E})=\sum_{k=0}^{\log_{2}(n^{\delta})}\sum_{l=1}^{2^{k}}\mathrm{Var}(-E_{n}^{(k,l)})+\sum_{k_{1}=0}^{\log_{2}(n^{\delta})}\sum_{l_{1}=1}^{2^{k_{1}}}\sum_{k_{2}=0}^{\log_{2}(n^{\delta})}\sum_{l_{2}=1}^{2^{k_{2}}}\text{Cov}(-E_{n}^{(k_{1},l_{1})},-E_{n}^{(k_{2},l_{2})}). In addition, we obtain that, for sufficiently large n , \sum_{k=0}^{\log_{2}(n^{\delta})}\sum_{l=1}^{2^{k}}\mathrm{Var}(-E_{n}^{(k,l)})\geq\sum_{k=0}^{\log_{2}(n^{\delta})}\sum_{l=1}^{2^{k}}c\frac{n}{2^{k}}\geq c\delta n\log n. By Lemma 2.4 , we have \displaystyle\text{Cov}(-E_{n}^{(k_{1},l_{1})},-E_{n}^{(k_{2},l_{2})})= \displaystyle-\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}]+\mathbb{E}[E_{n}^{(k_{1},l_{1})}E_{n}^{(k_{2},l_{2})}] \displaystyle\geq \displaystyle-\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}]\geq-(\log n)^{2}. Furthermore, we remark that if the intervals [n/2^{k_{1}+1}(2l_{1}-2),n/2^{k_{1}+1}(2l_{1})] (this is the interval corresponding to the cross term E^{(k_{1},l_{1})} ) and [n/2^{k_{2}+1}(2l_{2}-2),n/2^{k_{2}+1}(2l_{2})] (this is the interval corresponding to E^{(k_{2},l_{2})} ) are completely disjoint from each other, then E^{(k_{1},l_{1})} and E^{(k_{2},l_{2})} are independent of each other and the covariance is 0 . Using these considerations, we see that a lower bound for the covariances is the following: \displaystyle\sum_{k_{1}=0}^{\log_{2}(n^{\delta})}\sum_{l_{1}=1}^{2^{k_{1}}}\sum_{k_{2}=k_{1}+1}^{\log_{2}(n^{\delta})}\sum_{l_{2}=0}^{2^{k_{2}-k_{1}}}-(\log n)^{2}\geq-\sum_{k_{1}=0}^{\log_{2}(n^{\delta})}2^{k_{1}}[n^{\delta}/2^{k_{1}}](\log n)^{2} \displaystyle=-n^{\delta}(\log n)^{3}\gg-n(\log n),\text{ if }\delta<1. Furthermore, notice that by Lemma 4.1 , we have the upper bound \mathrm{Var}(X_{n})\leq Cn\log n . Thus, we can show that \mathrm{Var}(MT)\leq Cn^{\delta}[n^{1-\delta}\log(n^{1-\delta})]\leq C(1-\delta)n\log n, by setting \delta sufficiently close to 1 , this can be made very small. Finally, we can apply the Cauchy-Schwarz inequality to say that, \mathrm{Var}(X_{n})\geq\mathrm{Var}(MT)+\mathrm{Var}(\mathcal{E})-2\mathrm{Var}(MT)^{1/2}\mathrm{Var}(\mathcal{E})^{1/2}. Then for \delta close to but not equal to 1 , we have \mathrm{Var}(\mathcal{E})\geq cn\log n and \mathrm{Var}(MT)\leq C(1-\delta)n\log n . Thus, \mathrm{Var}(X_{n})\gtrsim n\log n , as desired. ∎ 4.1.2. Effective resistance We start with the following lower bound. Lemma 4.3 . There exist a constant \epsilon>0 and a subsequence (n_{k}) such that \mathrm{Var}(X_{n_{k}})\geq\epsilon n_{k}\log n_{k} . In other words, \limsup_{n\to\infty}\frac{\mathrm{Var}(X_{n})}{n\log n}>0. Proof. Assume for contradiction that this is not true. Then, it must be the case that for every \kappa>0 , there exists N_{\kappa} such that for all n\geq N_{\kappa} , we have, \mathrm{Var}(X_{n})\leq\kappa n\log n. Fix \delta>0 . For \delta>0 , we will choose a sufficiently small \kappa>0 and derive a contradiction later. Recall our binary decomposition in ( 4.2 ). As long as n^{1-\delta}\geq N_{\kappa} , we have that (4.3) \mathrm{Var}(MT)\leq n^{\delta}[\kappa n^{1-\delta}\log n^{1-\delta}]=\kappa(1-\delta)n\log n and (4.4) \mathrm{Var}(\mathcal{E})=\sum_{k=0}^{\log_{2}(n^{\delta})}\sum_{l=1}^{2^{k}}\mathrm{Var}(-E_{n}^{(k,l)})+\sum_{k_{1}=0}^{\log_{2}(n^{\delta})}\sum_{l_{1}=1}^{2^{k_{1}}}\sum_{k_{2}=0}^{\log_{2}(n^{\delta})}\sum_{l_{2}=1}^{2^{k_{2}}}\text{Cov}(-E_{n}^{(k_{1},l_{1})},-E_{n}^{(k_{2},l_{2})}). We have that, for sufficiently large n , \sum_{k=0}^{\log_{2}(n^{\delta})}\sum_{l=1}^{2^{k}}\mathrm{Var}(-E_{n}^{(k,l)})\geq\sum_{k=0}^{\log_{2}(n^{\delta})}\sum_{l=1}^{2^{k}}c\frac{n}{2^{k}}\geq c\delta n\log n. Notice that \displaystyle\text{Cov}(-E_{n}^{(k_{1},l_{1})},-E_{n}^{(k_{2},l_{2})})=\mathbb{E}[E_{n}^{(k_{1},l_{1})}E_{n}^{(k_{2},l_{2})}]-\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}] \displaystyle\geq-\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}]\gtrsim-(\log n)^{2}. Here, we only used that E_{n}\geq 0 to get the second inequality. Putting these estimates back into equation ( 4.4 ), we observe that (4.5) \mathrm{Var}(\mathcal{E})\geq c\delta n\log n-O((\log n)^{2}(n^{\delta}\log(n^{\delta}))^{2}) This last term will be greater than \frac{c\delta}{2}n\log n for n sufficiently large. Finally, we can apply the Cauchy-Schwarz inequality to say that, (4.6) \mathrm{Var}(X_{n})\geq\mathrm{Var}(MT)+\mathrm{Var}(\mathcal{E})-2\mathrm{Var}(MT)^{1/2}\mathrm{Var}(\mathcal{E})^{1/2}. Notice that as a function of the value of \mathrm{Var}(\mathcal{E}) , the right-hand side is increasing when \mathrm{Var}(\mathcal{E})\geq\mathrm{Var}(MT). We have already obtained a lower bound on \mathrm{Var}(\mathcal{E}) from equation ( 4.5 ) that is larger than the upper bound we have on \mathrm{Var}(MT) from equation ( 4.3 ). Indeed, notice that if \mathrm{Var}(MT)<\frac{c\delta}{8}n\log n , then we would have that the right hand side of ( 4.6 ) will be greater than, (\mathrm{Var}(\mathcal{E})^{1/2}-\mathrm{Var}(MT)^{1/2})^{2}\geq\left(\frac{\sqrt{c\delta}}{\sqrt{2}}\sqrt{n\log n}-\frac{\sqrt{c\delta}}{2\sqrt{2}}\sqrt{n\log n}\right)^{2}\geq\frac{c\delta}{8}n\log n. Then, we have that by setting \kappa sufficiently small that and applying the previous inequality that \mathrm{Var}(X_{n})\geq\frac{c\delta}{8}n\log n . This is a contradiction to the assumption that we cannot produce a lower bound to the \limsup of \frac{\mathrm{Var}(X_{n})}{n\log n} . ∎ Now, we produce an upper bound to the variance of the effective resistance. Since the proof is the same as that of ( 4.1 ), we omit it. Lemma 4.4 . We have the following upper bound of the variance of X_{n} : \mathrm{Var}(X_{n})\lesssim n(\log n)^{2}. 4.2. The Limit in Distribution of \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}} 4.2.1. Graph distance and cut points Proof of Theorem 1.2 for d=6 . Part 1: A CLT contribution Define the value n_{\delta}:=\exp\left[\frac{1}{2}\log n+(\sqrt{\log n})^{1-\delta}\right] . Now, \mathcal{G}:=\sum_{i=1}^{n_{\delta}}X[(i-1)n/n_{\delta},in/n_{\delta}]-\mathbb{E}[X[(i-1)n/{n_{\delta}},in/n_{\delta}]] will be a normal random variable of variance of order n\log n . Define Z_{n_{\delta},i}:=\frac{X[(i-1)n/n_{\delta},in/n_{\delta}]-\mathbb{E}[X[(i-1)n/n_{\delta},in/n_{\delta}]]}{\sqrt{\mathrm{Var}(X_{n/n_{\delta}})}}. The variables Z_{n_{\delta},i} are all independent of each other and one \sum_{i=1}^{n_{\delta}}\mathbb{E}\left[Z_{n_{\delta},i}^{2}\right]=1. Furthermore, we have that, \sum_{i=1}^{n_{\delta}}\mathbb{E}[Z_{n_{\delta},i}^{2}\mathbbm{1}[|Z_{n_{\delta},i}|\geq\epsilon]]=0, since deterministically X[(i-1)n/n_{n_{\delta}},in/n_{\delta}]\leq n/n_{\delta}\ll\sqrt{n(\log n/n_{\delta})} holds. Part 2: Controlling the error term at mesoscopic scales Define n_{\delta,-}:=\exp\left[\frac{1}{2}\log n-(\sqrt{\log n})^{1-\delta}\right] . Let us control \mathcal{M}:=\sum_{k=\log_{2}n_{\delta,-}}^{\log_{2}n_{\delta}}\sum_{l=1}^{2^{k}}(-E_{n}^{(k,l)}+\mathbb{E}[E_{n}^{(k,l)}]). Since at a given level k , all of the -E_{n}^{(k,l)} are independent of each other, we can compute \mathbb{E}\left[\left(\sum_{l=1}^{2^{k}}(-E_{n}^{(k,l)}+\mathbb{E}[E_{n}^{(k,l)}])\right)^{2}\right]=\sum_{l=1}^{2^{k}}\mathbb{E}[(-E_{n}^{(k,l)}+\mathbb{E}[E_{n}^{(k,l)}])^{2}]\lesssim\frac{n}{2^{k}}2^{k}=n. Thus, we see that \mathbb{E}[\mathcal{M}^{2}]\leq 4n(\sqrt{\log n})^{2-2\delta} . Hence, by Markov’s inequality, we have that (4.7) \mathbb{P}(\mathcal{M}\geq\sqrt{n(\log n)^{1-\delta/2}})\to 0 as n\to\infty for any \epsilon>0 . Part 3: Controlling the error terms at the smallest scales We let \Omega_{k,l} be the event that, \Omega_{k,l}:=\left\{|E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}]|\ \leq\left(\frac{n}{2^{k}}\right)^{1-\frac{1}{(\sqrt{\log n})^{1+2\delta}}}\right\}. Notice that for fixed k , the events \Omega_{k,l} are all independent of each other. Define \Omega_{k}:=\bigcap_{l=1}^{2^{k}}\Omega_{k,l} Thus, we see that when 2^{k}\leq n_{\delta,-}\leq n^{1/2} , by ( 2.5 ), \displaystyle\mathbb{E}\left[\left(\sum_{l=1}^{2^{k}}E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}]\right)^{2}\mathbbm{1}[\Omega_{k}]\right]=\sum_{l=1}^{2^{k}}\mathbb{E}[(E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}])^{2}\mathbbm{1}[\Omega_{k,l}]] \displaystyle+\sum_{l_{1},l_{2}=1}^{2^{k}}\mathbb{E}[(E_{n}^{(k,l_{1})}-\mathbb{E}[E_{n}^{(k,l_{1})}])\mathbbm{1}[\Omega_{k,l_{1}}]]\mathbb{E}[(E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}])\mathbbm{1}[\Omega_{k,l_{2}}]] \displaystyle\leq 2^{k}\left(\frac{n}{2^{k}}\right)^{1-\frac{1}{(\sqrt{\log n})^{1+2\delta}}}+(2^{k})^{2}(\log n)^{2}=n^{1-\frac{1}{(\sqrt{\log n})^{1+2\delta}}}(2^{k})^{\frac{1}{(\sqrt{\log n})^{1+2\delta}}}+n_{\delta,-}^{2}(\log n)^{2} \displaystyle\leq n^{1-\frac{1}{2(\sqrt{\log n})^{1+2\delta}}}+\exp[\log n-\sqrt{\log n}^{1-\delta}+2\log\log n]. In addition, we also have that when 2^{k}\leq n_{\delta,-} , \displaystyle\mathbb{P}(\Omega_{k}^{c})\leq\sum_{l=1}^{2^{k}}\mathbb{P}(\Omega_{k,l}^{c})\leq\frac{2^{k}}{\left(\frac{n}{2^{k}}\right)^{1-\frac{1}{(\sqrt{\log n})^{1+2\delta}}}} \displaystyle= \displaystyle\frac{(2^{k})^{2-\frac{1}{(\sqrt{\log n})^{1+2\delta}}}}{n^{1-\frac{1}{(\sqrt{\log n})^{1+2\delta}}}}\leq\frac{\exp\left[\left(\frac{\log n}{2}-\sqrt{\log n}^{1-\delta}\right)\left(2-\frac{1}{(\sqrt{\log n})^{1+2\delta}}\right)\right]}{\exp[\log n-(\sqrt{\log n})^{1-2\delta}]}\leq\exp[-(\sqrt{\log n})^{1-\delta}], for n sufficiently large. If we now define \Omega=\bigcap_{k=1}^{\log_{2}n_{\delta,-}}\Omega_{k} , then we see that, \mathbb{P}(\Omega^{c})\leq\sum_{k=1}^{\log_{2}n_{\delta,-}}\mathbb{P}(\Omega_{k}^{c})\leq\log n\exp[-(\sqrt{\log n})^{1-\delta}]\ll 1. Furthermore, if we define \mathcal{L}:=\sum_{k=0}^{\log_{2}n_{\delta,-}}\sum_{l=1}^{2^{k}}(E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}]), we have \displaystyle\mathbb{E}\left[\mathcal{L}^{2}\mathbbm{1}[\Omega]\right] \displaystyle\leq\sum_{k_{1},k_{2}=0}^{\log_{2}n_{\delta,-}}\mathbb{E}\left[\left(\sum_{l=1}^{2^{k_{1}}}E_{n}^{(k_{1},l)}-\mathbb{E}[E_{n}^{(k_{1},l)}]\right)\left(\sum_{l=1}^{2^{k_{2}}}E_{n}^{(k_{2},l)}-\mathbb{E}[E_{n}^{(k_{2},l)}]\right)\mathbbm{1}[\Omega]\right] \displaystyle\leq\sum_{k_{1},k_{2}=0}^{\log_{2}n_{\delta,-}}\mathbb{E}\left[\left(\sum_{l=1}^{2^{k_{1}}}E_{n}^{(k_{1},l)}-\mathbb{E}[E_{n}^{(k_{1},l)}]\right)^{2}\mathbbm{1}[\Omega_{k_{1}}]\right]^{1/2}\mathbb{E}\left[\left(\sum_{l=1}^{2^{k_{2}}}E_{n}^{(k_{2},l)}-\mathbb{E}[E_{n}^{(k_{2},l)}]\right)^{2}\mathbbm{1}[\Omega_{k_{2}}]\right]^{1/2} \displaystyle\leq(\log n)^{2}n^{1-\frac{1}{2(\sqrt{\log n})^{1+2\delta}}}+(\log n)^{2}\exp[\log n-\sqrt{\log n}^{1-\delta}+4\log\log n]\ll n. By using Markov’s inequality, we see that, (4.8) \displaystyle\mathbb{P}\left(\sum_{k=0}^{\log_{2}n_{\delta,-}}\sum_{l=1}^{2^{k}}(E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}]>\sqrt{n}\right) \displaystyle\leq\mathbb{P}(\Omega^{c})+n^{-1}\mathbb{E}\left[\left(\sum_{k=0}^{\log_{2}n_{\delta,-}}\sum_{l=1}^{2^{k}}(E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}]\right)^{2}\mathbbm{1}[\Omega]\right]\to 0, as n\to\infty . Recall that \mathcal{G} from Part 1 was a Gaussian random variable and the order of the variance of \mathcal{G} was n\log n , which is much larger than the error terms of Parts 2 and 3. Then, combining Part 1, 2, 3, we can obtain the desired result using the Lindeberg–Feller central limit theorem. 4.2.2. Effective resistance Next, we will give the proof of Theorem 1.4 for d=6 . We present only the necessary adjustments from the proof of Theorem 1.2 . This involves changing Parts 1 and 4, while keeping Parts 2 and 3. We also remark that the results of this section only depend on the tail behavior of the cross terms E_{n} behaving like \mathbb{P}(E_{n}\geq l)\asymp\frac{1}{l} . In particular, the results are general enough to not require any estimate on the correlation between the cross terms. Thus, the methods of this section are of general interest and can potentially be applied to other heavy tailed statistics of the random walk range. We now define the function f(n) as, \mathrm{Var}(X_{n})=n(\log n)^{f(n)}. Part 1: A CLT contribution Define the value n_{\delta}:=\exp\left[\frac{1}{2}\log n+(\sqrt{\log n})^{1-\delta}\right] . Now, \mathcal{G}:=\sum_{i=1}^{n_{\delta}}X[(i-1)n/n_{\delta},in/n_{\delta}]-\mathbb{E}[X[(i-1)n/{n_{\delta}},in/n_{\delta}]] will be a normal random variable of variance n(\log(n/n_{\delta}))^{f(n/n_{\delta})} , provided f(n/n_{\delta})\geq 0. Define Z_{n_{\delta},i}:=\frac{X[(i-1)n/n_{\delta},in/n_{\delta}]-\mathbb{E}[X[(i-1)n/n_{\delta},in/n_{\delta}]]}{\sqrt{n(\log n/n_{\delta})^{f(n/n_{\delta})}}}. The variables Z_{n_{\delta},i} are all independent of each other and one \sum_{i=1}^{n_{\delta}}\mathbb{E}\left[Z_{n_{\delta},i}^{2}\right]=1. Furthermore, we have that, \sum_{i=1}^{n_{\delta}}\mathbb{E}[Z_{n_{\delta},i}^{2}\mathbbm{1}[|Z_{n_{\delta},i}|\geq\epsilon]]=0, since deterministically, we have that X[(i-1)n/n_{n_{\delta}},in/n_{\delta}]\leq n/n_{\delta}\ll\sqrt{n(\log n/n_{\delta})^{f(n/n_{\delta})}} , provided f(n^{1/2-\delta})\geq 0 . Part 4: Nontriviality of the Limit We will consider those values of n such that f(n/n_{\delta})\geq 1-\delta/4 (by Lemma 4.2 , this should happen infinitely often.) We will divide the analysis into two cases. Case 1: f(n/n_{\delta})\geq 1-\delta/4 and f(n)\leq f(n/n_{\delta})+\frac{1}{\log\log n} happen infinitely often together. Then, we have that \displaystyle\mathrm{Var}(X_{n})=n(\log n)^{f(n/n_{\delta})}(\log n)^{f(n)-f(n/n_{\delta})}\leq n(\log(n/n_{\delta})^{3})^{f(n/n_{\delta})}\log n^{\frac{1}{\log\log n}} \displaystyle\leq 27en(\log(n/n_{\delta}))^{f(n/n_{\delta})}. Since \mathcal{G} is Gaussian with variance n(\log(n/n_{\delta}))^{f(n/n_{\delta})} , with constant probability, it will be greater than \sqrt{n(\log(n/n_{\delta}))^{f(n/n_{\delta})}} . Equations ( 4.8 ) and ( 4.7 ) show that the remaining error terms will not be larger than \epsilon\sqrt{n(\log n)^{1-\delta/2}} with high probability. Thus, on a set of non-vanishing probability, we must have that as n\to\infty , \displaystyle\mathbb{P}\bigg(\frac{\mathcal{M}+\mathcal{L}}{\sqrt{n(\log(n/n_{\delta}))^{f(n/n_{\delta})}}}\geq\epsilon\bigg)\to 0 for any \epsilon>0 . Thus, \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}} converges to \mathcal{N}(0,a) . Case 2: f(n/n_{\delta})\geq 1-\delta/4 and f(n)\leq f(n/n_{\delta})+\frac{1}{\log\log n} do not happen infinitely often together. Then there exists a sequence m_{1},m_{2},\ldots,m_{k},\ldots such that \frac{m_{k+1}}{(m_{k+1})_{\delta}}=m_{k},\forall k and f(m_{k+1})-f(m_{k})\geq\frac{1}{\log\log m_{k+1}} . (Notice that by Lemma 4.2 , we will always be able to find elements such that f(n/n_{\delta})\geq 1-\delta/4 , so we do not need to worry about the possibility that f(n/n_{\delta})\leq 1-\delta/4 for all large n .) The relationship m_{k}=\frac{m_{k+1}}{(m_{k+1})_{\delta}} will imply that m_{k+1}\leq(m_{k})^{3} . Thus, m_{k+1}\leq(m_{1})^{3^{k}} . Therefore, we have that f(m_{k+1})-f(m_{k})\geq\frac{1}{\log\log m_{k+1}}\geq\frac{1}{(k+1)\log 4}, for all k large enough. This will imply that \lim_{k\to\infty}f(m_{k})=\infty . This contradicts the upper bound on f from Lemma 4.1 . Thus, we see that this proof establishes that there is a subsequence where \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}}, does not converge to 0 . Moreover, along this subsequence X_{n}-\mathbb{E}[X_{n}] will be distributed (after appropriate normalization) as a normal random variable whose variance is given by n(\log(n/n_{\delta}))^{f(n/n_{\delta})} . ∎ 5. The fluctuations converge to 0 in dimension d=5 In this section, we will give the proof of Propositions 1.1 and 1.3 and Theorems 1.2 and 1.4 in d=5 . Since we do not show the correlation estimates ( 5.1 ) for the effective resistance, we present the weaker estimates of its variance. Since the proof is similar, we will omit the proof of Proposition 1.3 in d=5 . Lemma 5.1 . We have \displaystyle\mathrm{Var}(X_{n})\asymp n^{3/2}. Proof. Fix some small \alpha>0 . We consider the variance of \mathcal{E}=-\sum_{k=0}^{(1-\alpha)\log_{2}n}\sum_{l=1}^{2^{k}}E_{n}^{(k,l)} . For 0\leq k_{1},k_{2}\leq(1-\alpha)\log_{2}n , 1\leq l_{1}\leq 2^{k_{1}} , 1\leq l_{2}\leq 2^{k_{2}} , let \displaystyle\Lambda_{1}:=\{((k_{1},l_{1}),(k_{2},l_{2})):[2^{-k_{1}}(l_{1}-1)n,2^{-k_{1}}l_{1}n]\cap[2^{-k_{2}}l_{2}n,2^{-k_{2}}(l_{2}+1)n]\neq\emptyset\}, \displaystyle\Lambda_{2}:=\{((k_{1},l_{1}),(k_{2},l_{2})):[2^{-k_{1})}(l_{1}-1)n,2^{k_{1}}l_{1}n]\cap[2^{-k_{2}}(l_{2}-1)n,2^{-k_{2}}l_{2}n]=\emptyset\}. Since \displaystyle\sum_{((k_{1},l_{1}),(k_{2},l_{2}))\in\Lambda_{2}}\mathbb{E}[E_{n}^{(k_{1},l_{1})}E_{n}^{(k_{2},l_{2})}]=\sum_{((k_{1},l_{1}),(k_{2},l_{2}))\in\Lambda_{2}}\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}], we have \displaystyle\mathrm{Var}(\mathcal{E})\geq\sum_{k=0}^{(1-\alpha)\log_{2}n}\sum_{l=1}^{2^{k}}\mathbb{E}[(E_{n}^{(k,l)})^{2}]-\sum_{((k_{1},l_{1}),(k_{2},l_{2}))\in\Lambda_{1}}\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}]. By ( 2.2 ), we have \sum_{k=0}^{(1-\alpha)\log_{2}n}\sum_{l=1}^{2^{k}}\mathbb{E}[(E_{n}^{(k,l)})^{2}]\geq cn^{3/2} . Now we claim that \displaystyle\sum_{((k_{1},l_{1}),(k_{2},l_{2}))\in\Lambda_{1}}\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}]\leq n^{3/2-\alpha/2+o(1)}. Indeed, \displaystyle\sum_{((k_{1},l_{1}),(k_{2},l_{2}))\in\Lambda_{1}}\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}] \displaystyle\lesssim \displaystyle(\log n)^{2}\sup_{\alpha\leq\beta_{1}\leq\beta_{2}\leq 1}\sum_{l_{1},l_{2}:((1-\beta_{1})\log_{2}n,l_{1})((1-\beta_{2})\log_{2}n,l_{2})\in\Lambda_{1}}\mathbb{E}[E_{n}^{((1-\beta_{1})\log_{2}n,l_{1})}]\mathbb{E}[E_{n}^{{(1-\beta_{2})}\log_{2}n,l_{2})}] \displaystyle\lesssim \displaystyle(\log n)^{2}\sup_{\alpha\leq\beta_{1}\leq\beta_{2}\leq 1}n^{\beta_{2}-\beta_{1}}n^{1-\beta_{2}}n^{\beta_{2}/2}n^{\beta_{1}/2}\leq n^{3/2-\alpha/2+o(1)}. Hence, we obtain \mathrm{Var}(\mathcal{E})\gtrsim n^{3/2} . In addition, ( 2.2 ) yields \sum_{k=1}^{(1-\alpha)\log_{2}n}\sum_{l=1}^{2^{k}}\mathbb{E}[(E_{n}^{(k,l)})^{2}]\leq cn^{3/2} . Now by the same argument as that of Lemma 4.1 , we have (5.1) \displaystyle\sum_{k_{1}=0}^{(1-\alpha)\log_{2}n}\sum_{l_{1}=1}^{2^{k_{1}}}\sum_{k_{2}=k_{1}+1}^{(1-\alpha)\log_{2}n}\sum_{l_{2}=0}^{2^{k_{2}-k_{1}}}\mathbb{E}[E_{n}^{(k_{1},l_{1})}E_{n}^{(k_{2},l_{2})}]\leq n^{3/2-\alpha/2+o(1)}. Hence, we obtain \mathrm{Var}(\mathcal{E})\lesssim n^{3/2} . If we let MT=\sum_{l=1}^{n^{1-\alpha}}X[(l-1)n^{\alpha},ln^{\alpha}] , \mathrm{Var}(MT)\leq\sum_{l=1}^{n^{1-\alpha}}\mathbb{E}[X[(l-1)n^{\alpha},ln^{\alpha}]^{2}]\lesssim n^{1+\alpha} for sufficiently small \alpha>0 . Then, \mathrm{Var}(X_{n})\geq(\mathrm{Var}(\mathcal{E})^{1/2}-\mathrm{Var}(MT)^{1/2})^{2}\geq cn^{3/2} and \mathrm{Var}(X_{n})\leq(\mathrm{Var}(\mathcal{E})^{1/2}+\mathrm{Var}(MT)^{1/2})^{2}\lesssim n^{3/2} . ∎ Proof of Theorems 1.2 and 1.4 in d=5 . For small \delta>0 , we use Markov’s inequality in the computation of the variance, to derive, \displaystyle\sup_{\alpha\leq\beta\leq 1-\delta}\mathbb{P}\bigg(\frac{\sum_{l=1}^{n^{1-\beta}}(E_{n}^{((1-\beta)\log n,l)}-\mathbb{E}[E_{n}^{((1-\beta)\log n,l)}])}{\sqrt{\mathrm{Var}(X_{n})}}\geq\frac{\epsilon}{\log n}\bigg) \displaystyle\leq \displaystyle\sup_{\alpha\leq\beta\leq 1-\delta}(\log n)^{2}\epsilon^{-2}\frac{\sum_{l=1}^{n^{1-\beta}}\mathrm{Var}(E_{n}^{((1-\beta)\log n,l)})}{\mathrm{Var}(X_{n})} \displaystyle\lesssim \displaystyle\sup_{\alpha\leq\beta\leq 1-\delta}(\log n)^{2}\frac{n^{1-\beta}n^{3\beta/2}}{n^{3/2}}\lesssim(\log n)^{2}n^{-\delta/2}. Now, we use Markov’s inequality in the computation of the absolute value combined with the triangle inequality, to get, \displaystyle\sup_{1-\delta\leq\beta\leq 1}\mathbb{P}\bigg(\frac{\sum_{l=1}^{n^{1-\beta}}(E_{n}^{((1-\beta)\log n,l)}-\mathbb{E}[E_{n}^{((1-\beta)\log n,l)}])}{\sqrt{\mathrm{Var}(X_{n})}}\geq\frac{\epsilon}{\log n}\bigg) \displaystyle\leq \displaystyle\sup_{1-\delta\leq\beta\leq 1}(\log n)\epsilon^{-1}\frac{\sum_{l=1}^{n^{1-\beta}}\mathbb{E}[E_{n}^{((1-\beta)\log n,l)}]}{\sqrt{\mathrm{Var}(X_{n})}} \displaystyle\lesssim \displaystyle\sup_{1-\delta\leq\beta\leq 1}(\log n)\frac{n^{1-\beta}n^{\beta/2}}{n^{3/4}}\lesssim(\log n)n^{-1/4+\delta/2}. Therefore, \displaystyle\mathbb{P}\bigg(\frac{|X_{n}-\mathbb{E}[X_{n}]|}{\sqrt{\mathrm{Var}(X_{n})}}\geq\epsilon\bigg) \displaystyle\leq \displaystyle\mathbb{P}\bigg(\frac{|MT-\mathbb{E}[MT]|}{\sqrt{\mathrm{Var}(X_{n})}}\geq\epsilon/2\bigg) \displaystyle+C(\log n)\sup_{\alpha\leq\beta\leq 1}\mathbb{P}\bigg(\frac{\sum_{l=1}^{n^{1-\beta}}(E_{n}^{(\beta\log n,l)}-\mathbb{E}[E_{n}^{(\beta\log n,l)}])}{\sqrt{\mathrm{Var}(X_{n})}}\geq\epsilon/(2\log n)\bigg)\lesssim n^{-\alpha/4} as desired. ∎ 6. The fluctuations converge to 0 in dimension d=4 In this section, we estimate the variance and the Limit in distribution of \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}} in d=4 . In what follows, we will simplify notation by reducing to a discussion of only the cross term E_{n} since we will only apply a dyadic decomposition and the only other cross term that could appear, X_{2n+1}-X_{n}-X[n,2n+1] , will have a similar analysis. In subsection 6.1 , we will give the lower bounds for the cross term, which holds for the graph distance, cut points and the effective resistance. In subsections 6.2 - 6.4 , we will show the upper bounds for the cross term and main results in d=4 . In these subsections, we are considering only the graph distance, cut points since Lemma 6.8 does not work for the effective resistance. We will give our main result in d=4 for the effective resistance in subsection 6.5 . 6.1. Lower bounds for the Cross Term We will first start by obtaining a lower bound of \mathbb{E}[E_{n}]. Our heuristic argument is the following: if there is an intersection between S[3n/2,2n] and S[0,n] , then this will form a shortcut in the graph distance between the points S_{2n} and S_{0} . The amount that the graph distance would reduce via this shortcut will be related to the graph distance between S_{n} and S_{2n} , which by a law of large numbers should be O\left(\frac{n}{(\log n)^{1/2}}\right) . Furthermore, the probability of the intersection of S[3n/2,2n] and S[0,n] is approximately O((\log n)^{-1}) . Thus, one would heuristically argue that \mathbb{E}[E_{n}]=\frac{n}{(\log n)^{3/2\pm o(1)}} . However, the exact value of the reduction of the graph distance is a complicated function of the loop intersection structure of the two walks. Thus, knowing that there is a long-range intersection may not be enough the deduce the reduction of the graph distance. Furthermore, to get the exact order \frac{n}{(\log n)^{3/2}} , that we desire, then we would need to argue that there is exact independence between the event that there is an intersection between S[3n/2,2n] and S[0,n] and the event that the graph distance between S_{n} and S_{2n} is O\left(\frac{n}{(\log n)^{1/2}}\right) . The following lemma will address these issues by finding appropriate events that will allow us to constrain the geometry of the random walk range. Lemma 6.1 . Let E_{n} denote the cross term that appears when considering the number of cut points, the effective resistance or the graph distance. We have \mathbb{E}[E_{n}]\geq\frac{n}{(\log n)^{3/2+o(1)}} . Remark 6.2 . In [ 21 , Section 4] , he has already shown \mathbb{E}[E_{n}]\geq\frac{n}{(\log n)^{3/2+o(1)}} for the effective resistance. We obtain the same result by a slightly simpler proof which derives intersection estimates by using the capacity of the random walk. Proof. We split the walk S[0,2n] into two parts. \tilde{S} will be the reversal of the first part, that is, \tilde{S}_{i}=S_{n-i}-S_{n} . \hat{S} will be the second part, that is \hat{S}_{i}=S_{n+i}-S_{n} . We now define the following events that impose good properties on the first walk \tilde{S}_{n} . Pick small \epsilon>0 . We let \tilde{T}_{i} be the sequence of cut points along the walk \tilde{S}_{n} , and \displaystyle A_{1}:=\{\max_{\tilde{T}_{i}\leq n}(\tilde{T}_{i+1}-\tilde{T}_{i})\leq\frac{n}{(\log n)^{7/12}}\},\quad A_{2}:=\{\tilde{X}_{n/2}\geq\frac{1}{1+\epsilon}\mathbb{E}[X_{n/2}]\}, \displaystyle A_{3}:=\{\tilde{X}[n-n/(\log n)^{\epsilon},n]\leq n/(\log n)^{1/2+\epsilon/2}\}, \displaystyle A_{4}:=\{{\rm Cap}(\tilde{S}(n-n/(\log n)^{\epsilon},n))\geq\frac{1}{2}\frac{\pi^{2}}{8}\frac{n}{(\log n)^{1+\epsilon}}\}, \displaystyle A_{5}:=\{\tilde{S}_{i}\leq C_{1}\sqrt{n},\quad\forall i\in[n-n/(\log n)^{\epsilon},n]\} noting \mathbb{E}[{\rm Cap}(\tilde{S}[0,n])]\sim\frac{\pi^{2}}{8}\frac{n}{\log n} (e.g., see [ 6 ] ). In the above equation, we use the notation \tilde{X}[a,b] to denote the graph distance between the points \tilde{S}_{a} and \tilde{S}_{b} along the graph \tilde{S}[a,b] . By [ 11 , Lemma 2.3] , \mathbb{P}(A_{1})=1-o(1) . Similarly, the law of large numbers ensures that \mathbb{P}(A_{2}) , \mathbb{P}(A_{3})=1-o(1) noting [ 11 , Theorem 1.2] and \mathbb{P}(A_{4})=1-o(1) (see [ 6 , Theorem 1.1] ). By the local central limit theorem, we have that \mathbb{P}(A_{5})=1-\epsilon(C_{1}) , where \epsilon(C_{1})\to 0 as C_{1}\to\infty . Let \mathcal{Q}:=A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\cap A_{5} . From our previous estimates, we can take a union bound to deduce that \mathbb{P}(\mathcal{Q})\geq 1-2\epsilon(C_{1}) , for n sufficiently large. Now, we need to define an event on the intersection of \hat{S} with \tilde{S} . Let \tau be defined to be the first time of intersection between \hat{S} and \tilde{S}[n-n/(\log n)^{\epsilon},n] after time n-n/(\log n)^{\epsilon} . That is, \tau:=\inf\{i>n-n/(\log n)^{\epsilon}:\hat{S}_{i}\in\tilde{S}[n-n/(\log n)^{\epsilon},n]\} . We define, \displaystyle B_{1}:=\{\hat{X}[\tau,n]\leq n/(\log n)^{1/2+\epsilon/2}\},\quad B_{2}:=\{\hat{S}_{n-n/(\log n)^{\epsilon}}\leq C_{1}\sqrt{n}\}, \displaystyle B_{3}:=\{\hat{S}[n-n/(\log n)^{\epsilon},n]\cap\tilde{S}[n-n/(\log n)^{\epsilon},n]\neq\emptyset\}. As before, we let \hat{X}[a,b] to denote the graph distance between the points \hat{S}_{a} and \hat{S}_{b} on the graph connecting \hat{S}[a,b] . Note that event B_{1} is independent of B_{2}\cap B_{3} by the Strong Markov Property, even if you have conditioned on the walk \tilde{S}[0,n] . By the law of large numbers, we have that \mathbb{P}(B_{1})=1-o(1) and (6.1) \displaystyle\mathbb{P}(B_{1}\cap B_{2}\cap B_{3}\cap\mathcal{Q}) \displaystyle=\mathbb{P}(B_{1}|B_{2}\cap B_{3}\cap\mathcal{Q})\mathbb{P}(B_{2}\cap B_{3}\cap\mathcal{Q}) \displaystyle=\mathbb{P}(B_{1})\mathbb{P}(B_{3}|B_{2}\cap\mathcal{Q})\mathbb{P}(B_{2}\cap\mathcal{Q}). We first claim that we have \mathbb{P}(B_{3}|B_{2}\cap\mathcal{Q})\geq\frac{c}{(\log n)^{1+2\epsilon}} for some constant c>0 . We use \mathcal{S} as a shorthand for the set \tilde{S}[n-n/(\log n)^{\epsilon},n] . Let \hat{S}_{n-n/(\log n)^{\epsilon}}\leq C_{1}n^{1/2} , as is necessary to satisfy the event B_{2} . By the last hitting time decomposition, we have that on \mathcal{Q} \displaystyle\mathbb{P}^{\hat{S}_{n-n/(\log n)^{\epsilon}}}(\taun/(\log n)^{\epsilon}-i) \displaystyle\geq \displaystyle\sum_{i=1}^{n/(\log n)^{\epsilon}}\sum_{a\in\mathcal{S}}\mathbb{P}^{\hat{S}_{n-n/(\log n)^{\epsilon}}}(\hat{S}_{i+n-n/(\log n)^{\epsilon}}=a)\mathbb{P}^{a}(\tau=\infty) \displaystyle\geq \displaystyle\left(\min_{\hat{a}\in\mathcal{S}}\sum_{i=1}^{n/(\log n)^{\epsilon}}\mathbb{P}^{\hat{S}_{n-n/(\log n)^{\epsilon}}}(\hat{S}_{i+n-n/(\log n)^{\epsilon}}=\hat{a})\right)\sum_{a\in\mathcal{S}}\mathbb{P}^{a}(\tau=\infty) \displaystyle= \displaystyle\left(\min_{\hat{a}\in\mathcal{S}}\sum_{i=1}^{n/(\log n)^{\epsilon}}\mathbb{P}^{\hat{S}_{n-n/(\log n)^{\epsilon}}}(\hat{S}_{i+n-n/(\log n)^{\epsilon}}=\hat{a})\right){\rm Cap}(\mathcal{S}). On the union A_{5}\cap B_{2} , we can apply the local central limit theorem to deduce that \left(\min_{\hat{a}\in\mathcal{S}}\sum_{i=1}^{n/(\log n)^{\epsilon}}\mathbb{P}^{\hat{S}_{n-n/(\log n)^{\epsilon}}}(\hat{S}_{i+n-n/(\log n)^{\epsilon}}=\hat{a})\right)\geq cn^{-1}(\log n)^{-\epsilon} , for some constant c>0 on \mathcal{Q} . Furthermore, the event A_{5} ensures that {\rm Cap}(\mathcal{S})\geq\frac{1}{2}\frac{\pi^{2}}{8}\frac{n}{(\log n)^{1+\epsilon}} on \mathcal{Q} . Multiplying these together, we see that there is some c>0 such that \mathbb{P}^{\hat{S}_{n-n/(\log n)^{\epsilon}}}(\tauc/(\log n)^{1+2\epsilon} on \mathcal{Q} . This means that \mathbb{P}(B_{3}|B_{2}\cap\mathcal{Q})\geq c/(\log n)^{1+2\epsilon} for some c>0 . Returning to equation ( 6.1 ), we see that we see that we must have \mathbb{P}(B_{1}\cap B_{2}\cap B_{3}\cap\mathcal{Q})\geq c/(\log n)^{1+2\epsilon} for some c>0 . Now, on the event B_{1}\cap B_{2}\cap B_{3}\cap\mathcal{Q} , we claim we have E_{n}>n/(\log n)^{1/2+\epsilon/2} . Due to the presence of the cut points from the event A_{1} and the lower bound on the graph distance \tilde{X}_{n/2} from A_{2} , we have that \tilde{X}_{n}\geq\frac{1}{1+\epsilon}\mathbb{E}[X_{n/2}]-\frac{n}{(\log n)^{7/12}} . By events A_{3} , A_{1} , and B_{1} , the graph distance between the points \hat{S}_{n} and \tilde{S}_{n} , is at most 2n/(\log n)^{1/2+\epsilon/2}+2\frac{n}{(\log n)^{7/12}} . Computing the difference, we now see that E_{n}>n/(\log n)^{1/2+\epsilon/2} on B_{1}\cap B_{2}\cap B_{3}\cap\mathcal{Q} as desired and this event happens with probability c/(\log n)^{1+2\epsilon} . By multiplying these two terms together, we see that \mathbb{E}[E_{n}]>n/(\log n)^{3/2+\epsilon/2+2\epsilon} . This proof also works even for the effective resistance or the number of cut points. ∎ Lemma 6.3 . There exists a set \Omega with probability \text{O}\left(\frac{\log\log n}{\log n}\right) such that we have E_{n}\mathbbm{1}[\Omega^{c}]\ll\mathbb{E}[E_{n}]. Proof. Recall the notation \hat{S} and \tilde{S} from the proof of Lemma 6.1 . Consider the event \displaystyle\Omega:= \displaystyle\{\hat{S}[n/(\log n)^{4},n]\cap\tilde{S}[0,n]\neq\emptyset\}\bigcup\{\tilde{S}[n/(\log n)^{4},n]\cap\hat{S}[0,n]\neq\emptyset\} \displaystyle\bigcup\left\{\sum_{i\in\left[\frac{n}{(\log n)^{4}},\frac{n}{(\log n)^{2}}\right]}1\{\tilde{S}[0,i-1]\cap\tilde{S}[i,n]=\emptyset\}=0\right\} \displaystyle\bigcup\left\{\sum_{i\in\left[\frac{n}{(\log n)^{4}},\frac{n}{(\log n)^{2}}\right]}1\{\hat{S}[0,i-1]\cap\hat{S}[i,n]=\emptyset\}=0\right\}. The first two events that compose \Omega ensure that there exists some long-range intersection between \tilde{S} and \hat{S} . The third and fourth events force there to be no cut points in \tilde{S} between n/(\log n)^{4} and n/(\log n)^{2} . We claim both that \Omega holds with probability O\left(\frac{\log\log n}{\log n}\right) and that on the event \Omega^{c} , we must have that the cross term E_{n} for number of cut points, the effective resistance, and the graph distance must by less than \frac{n}{(\log n)^{2}}\ll\mathbb{E}[E_{n}] by Lemma 6.1 . By [ 15 , Theorem 4.3.6 part(ii)] , we must have that \mathbb{P}(\hat{S}[n/(\log n)^{4},n]\cap\tilde{S}[0,n]\neq\emptyset)=\text{O}\left(\frac{\log\log n}{\log n}\right) . Similarly, by [ 11 , equation (7)] , \mathbb{P}\left(\sum_{i\in\left[\frac{n}{(\log n)^{4}},\frac{n}{(\log n)^{2}}\right]}1\{\tilde{S}[0,i-1]\cap\tilde{S}[i,n]=\emptyset\}\right)=\text{O}\left(\frac{\log\log n}{\log n}\right). Combining these bounds gives us that \mathbb{P}(\Omega)\leq\text{O}\left(\frac{\log\log n}{\log n}\right) , as desired. Now, we will check that on \Omega^{c} , our cross term can be no more than \frac{n}{(\log n)^{2}} . Notice that on \Omega^{c} , there must be some cut point in the interval \left[\frac{n}{(\log n)^{4}},\frac{n}{(\log n)^{2}}\right] for both \tilde{S} and \hat{S} . Let \mathcal{C}_{\tilde{S}} denote the time instance of the cut point of \tilde{S} (cut time) in this interval and let \mathcal{C}_{\hat{S}} denote the time instance of the cut point of \hat{S} in this interval. Furthermore, since there is no intersection between \hat{S}[n/(\log n)^{4},n] and \tilde{S} , \mathcal{C}_{\hat{S}} must still be a cut point in the full graph \hat{S}\cup\tilde{S}. Notice that we have \hat{X}_{n}=\hat{X}[0,\mathcal{C}_{\hat{S}}]+\hat{X}[\mathcal{C}_{\hat{S}},n]\leq\hat{X}[\mathcal{C}_{\hat{S}},n]+n/(\log n)^{2}. Similarly, we have \tilde{X}_{n}\leq\tilde{X}[\mathcal{C}_{\tilde{S}},n]+n/(\log n)^{2}. Lastly, we see that X_{2n}\geq\hat{X}[\mathcal{C}_{\hat{S}},n]+\tilde{X}[\mathcal{C}_{\tilde{S}},n] . Altogether, we see that on \Omega^{c} , we have E_{n}=\tilde{X}_{n}+\hat{X}_{n}-X_{2n}\leq\frac{2n}{(\log n)^{2}}\ll\mathbb{E}[E_{n}] . ∎ Remark 6.4 . If one is interested in the graph distance or the number of cut points, then we can proceed to more simply define \Omega by considering only its first line from its definition in Lemma 6.3 . We will use this fact later in the proof of Lemma 6.8 . By applying the Cauchy-Schwarz inequality, we obtain the following lower bound on \mathbb{E}[E_{n}^{2}] as a corollary. Corollary 6.5 . Let E_{n} denote the cross term that appears when computing the number of cut points, the effective resistance, or the graph distance. Then, we have, \mathbb{E}[E_{n}^{2}]\geq\frac{n^{2}}{(\log n)^{2+o(1)}}. Proof. Let \Omega be the set from Lemma 6.3 . Note that by the Cauchy-Schwarz inequality, we have that, \mathbb{E}[E_{n}^{2}]\mathbb{P}(\Omega)\geq\mathbb{E}[E_{n}\mathbbm{1}[\Omega]]^{2}\geq(1-o(1))\mathbb{E}[E_{n}]^{2}. Since \mathbb{P}(\Omega)=O\left(\frac{\log\log n}{\log n}\right) , we can take ratios and deduce that \mathbb{E}[E_{n}^{2}]\geq\frac{n^{2}}{(\log n)^{2+o(1)}} , as desired. ∎ 6.2. Upper bounds for the Cross terms Our proof of the upper bound for \mathbb{E}[E_{n}^{2}] requires more steps. Indeed, unlike our proof of the lower bound, we cannot establish our upper bound directly. However, we will first show that if we have the inequality \mathbb{E}[E_{n}^{2}]\leq\frac{Cn^{2}\log\log n}{(\log n)^{2}}+(\log n)^{-\epsilon}\mathrm{Var}(X_{n}) , this will be enough to show that \mathrm{Var}(X_{n})\leq\frac{n^{2}}{(\log n)^{2-o(1)}} and ultimately that \mathbb{E}[E_{n}^{2}]\leq\frac{n^{2}}{(\log n)^{2-o(1)}} . 6.2.1. Our first reduction The goal of this section is to establish our reduction that showing \mathbb{E}[E_{n}^{2}]\leq\frac{Cn^{2}\log\log n}{(\log n)^{2}}+(\log n)^{-\epsilon}\mathrm{Var}(X_{n}) is enough to establish \mathbb{E}[E_{n}^{2}],\mathrm{Var}(X_{n})\leq\frac{n^{2}}{(\log n)^{2+o(1)}} . Lemma 6.6 . Let X_{n} denote the number of cut points or the graph distance. Assume that there is some \epsilon>0 such that for all n , we have (6.2) \mathbb{E}[E_{n}^{2}]\leq\frac{Cn^{2}\log\log n}{(\log n)^{2}}+(\log n)^{-\epsilon}\mathrm{Var}(X_{n}). Then, we must have that, \mathrm{Var}(X_{n})\leq\frac{n^{2}}{(\log n)^{2-o(1)}},\quad\mathbb{E}[E_{n}^{2}]\leq\frac{n^{2}}{(\log n)^{2-o(1)}}. Proof. Fix any \kappa>0 , we will first show that for n large enough, we must have that, \mathrm{Var}(X_{n})\leq\frac{n^{2}}{(\log n)^{2-\kappa}}. Let us write \mathrm{Var}(X_{n})=\frac{n^{2}}{(\log n)^{f(n)}}. We will use the dyadic decomposition to find an equation for f(n) . We see that, \mathrm{Var}(X_{2n})=\mathrm{Var}(X_{n})+\mathrm{Var}(X_{[n,2n]})+\mathrm{Var}(\mathcal{E}_{n})+\text{Cov}(\mathcal{E}_{n},X_{n}+X_{[n,2n]}). We then have that using the previous expansion on the variance and equation ( 6.2 ) that, \displaystyle\frac{(2n)^{2}}{(\log(2n))^{f(2n)}} \displaystyle\leq\frac{2n^{2}}{(\log n)^{f(n)}}+\frac{Cn^{2}\log\log n}{(\log n)^{2}}+(\log n)^{-\epsilon}\frac{n^{2}}{(\log n)^{f(n)}} \displaystyle+\sqrt{\frac{(\log n)^{-\epsilon}n^{2}}{(\log n)^{f(n)}}+\frac{Cn^{2}\log\log n}{(\log n)^{2}}}\sqrt{\frac{2n^{2}}{(\log n)^{f(n)}}}. We can bound the right-hand side as, \displaystyle\frac{2n^{2}}{(\log n)^{f(n)}}+\frac{Cn^{2}\log\log n}{(\log n)^{2}}+\frac{n^{2}}{(\log n)^{f(n)+\epsilon}}+C\frac{n^{2}}{(\log n)^{f(n)+\epsilon/2}}+C\frac{n^{2}\sqrt{\log\log n}}{(\log n)^{f(n)/2+1}} \displaystyle\leq\frac{(2+\delta)n^{2}}{(\log n)^{f(n)}}+C\frac{n^{2}\log\log n}{(\log n)^{2}}, where \delta>0 can be set to be any small constant and C is some universal constant (that could depend on \delta ) and could change from line to line. We consider two cases: Case 1: f(n)\geq 2-\kappa In this case, note that for n large enough, we must have that \frac{n^{2}\log\log n}{(\log n)^{2}}\leq\delta\frac{n^{2}}{(\log n)^{2-\kappa}} . Thus, we obtain the inequality, (6.3) \displaystyle\frac{4n^{2}}{(\log 2n)^{f(2n)}}\leq\frac{(2+2\delta)n^{2}}{(\log n)^{2-\kappa}}, \displaystyle\log\frac{4}{2+2\delta}+(2-\kappa)\log\log n\leq f(2n)\log\log 2n, \displaystyle f(2n)\geq(2-\kappa)\frac{\log\log n}{\log\log n+\log\left[1+\frac{\log 2}{\log n}\right]}+\frac{1}{\log\log 2n}\log\frac{4}{2+2\delta} \displaystyle\geq(2-\kappa)-\frac{2-\kappa}{2\log n\log\log n}+\frac{1}{\log\log 2n}\log\frac{4}{2+2\delta}\geq(2-\kappa), when n is large enough. Case 2: f(n)\leq 2-\kappa In this case, when n is large enough, we can still obtain the inequality for any small \delta>0 , \frac{n^{2}\log\log n}{(\log n)^{2}}\leq\delta\frac{n^{2}}{(\log n)^{f(n)}} . Thus, we obtain the inequality, (6.4) \displaystyle\frac{4n^{2}}{(\log 2n)^{f(2n)}}\leq\frac{(2+2\delta)n^{2}}{(\log n)^{f(n)}}, \displaystyle(\log 2n)^{f(2n)}\geq\frac{4}{2+2\delta}(\log n)^{f(n)}, \displaystyle f(2n)\log\log 2n\geq\log\frac{4}{2+2\delta}+f(n)\log\log n, \displaystyle f(2n)\geq f(n)\frac{\log\log n}{\log\log 2n}+\frac{1}{\log\log 2n}\log\frac{4}{2+2\delta} \displaystyle\geq f(n)-\frac{f(n)}{2\log n\log\log n}+\frac{1}{\log\log(2n)}\log\frac{4}{2+2\delta}\geq f(n)+\frac{c}{\log\log n}, where c>0 will be some universal constant, and the least line will hold provided n is sufficiently large. Now, let n_{0} be large enough integer such that both equations ( 6.3 ) and ( 6.4 ) hold. Furthermore, consider k large enough so that \sum_{j=0}^{k-1}\frac{c}{\log\log(2^{j+1}n_{0})}\geq 2-\kappa. We claim that for any n\geq 2^{k}n_{0} , we must have that f(n)\geq 2-\kappa . First, consider the sequence f(n),f(n/2),f(n/4),\ldots,f(n/2^{L}) , where L is the largest integer such that n/2^{L}\geq n_{0} . If there existed some 0\leq i\leq L such that f(n/2^{i})\geq 2-\kappa , then by repeatedly applying equation ( 6.3 ), we must have that f(n)\geq 2-\kappa . Otherwise, ( 6.4 ) must hold for all 0\leq i\leq L , and we see that f(n)\geq f(n/2^{L})+\sum_{j=0}^{L}\frac{c}{\log\log(n/2^{j})}\geq\sum_{j=0}^{k-1}\frac{c}{\log\log 2^{j+1}n_{0}}\geq 2-\kappa . Here, we remark that we used the fact that f(n)\geq 0 is a trivial lower bound for all n . By substituting our bound on \mathrm{Var}(X_{n}) into equation ( 6.2 ), we derive an upper bound on \mathbb{E}[E_{n}^{2}] . ∎ Assuming the consequence of the above result, we also have the following corollary. Corollary 6.7 . Assume that we know \mathbb{E}[E_{n}^{2}]\leq\frac{n^{2}}{(\log n)^{2+o(1)}} , then we have \mathbb{E}[E_{n}]\leq\frac{n}{(\log n)^{3/2+o(1)}} . Proof. Recall the set \Omega from Lemma 6.3 . By the Cauchy-Schwarz inequality and the definition of \Omega , we have \mathbb{E}[E_{n}^{2}]\mathbb{P}(\Omega)\geq\mathbb{E}[E_{n}\mathbbm{1}[\Omega]]^{2}\geq(1-o(1))\mathbb{E}[E_{n}]^{2}. Using the fact that \mathbb{P}(\Omega)=O(\log\log n/\log n) gives the result. ∎ 6.2.2. Establishing equation ( 6.2 ) The goal of this section is to establish equation ( 6.2 ). We will first show that this equation holds provided that one derives an appropriate conditional statement for the probability that two random walks intersect. Before we start, let us recall the notation that we used in the proof of Lemma 6.1 . Let us call the reversal of the walk S[0,n] from time 0 to n \hat{S} . That is \hat{S}_{i}=S_{n}-S_{n-i} . Let us call S[n,2n] as \tilde{S} . That is \tilde{S}_{i}=S_{n+i}-S_{n} . In this subsection, we will give the estimate only for cut points and the graph distance. Lemma 6.8 . Let X_{n} denote the number of cut points, or the graph distance. Assume that there exists some \epsilon>0 such that with probability significantly less than (\log n)^{-2} , we have that, (6.5) \mathbb{P}(\tilde{S}[n/(\log n)^{4},n]\cap\hat{S}\neq\emptyset|\hat{S})\geq(\log n)^{-\epsilon}. Then, equation ( 6.2 ) holds. Proof. (1) Notice that we have E_{n}>l implies that \tilde{X}_{n}\geq\frac{l}{2} or \hat{X}_{n}\geq\frac{l}{2} . Furthermore, \Omega also holds by Lemma 6.3 . Then, \{E_{n}>l\}\subset(\{\tilde{X}_{n}\geq l/2\}\cap\Omega)\cup(\{\hat{X}_{n}\geq l/2\}\cap\Omega). (2) Furthermore, (again still considering that E_{n}>l ) in the case \tilde{X}_{n}\geq\frac{l}{2} , it must be the case that there is an intersection between \tilde{S}{[n/(\log n)^{4},n]} and \hat{S} by the proof of Lemma 6.3 . (Recall, we needed the event \Omega to hold in order to ensure that there is a large reduction in the graph distance.) (3) Vice versa, in the case \hat{X}_{n}\geq\frac{l}{2} , it must be the case that there is an intersection between \hat{S}[n/(\log n)^{4},n] and \tilde{S} . Thus, we have that, \mathbb{P}(E_{n}>l)\leq 2\mathbb{P}(\tilde{X}_{n}\geq l/2,\tilde{S}{[n/(\log n)^{4},n]}\cap\hat{S}\neq\emptyset). Furthermore, observe that, (6.6) \displaystyle\mathbb{E}[E_{n}^{2}]\leq 2\sum_{l=1}^{n}l\mathbb{P}(\tilde{X}_{n}\geq l/2,\tilde{S}[n/(\log n)^{4},n]\cap\hat{S}\neq\emptyset)\leq 2\sum_{l=1}^{4\mathbb{E}[\tilde{X}_{n}]}4\mathbb{E}[\tilde{X}_{n}]\mathbb{P}(\tilde{S}[n/(\log n)^{4},n]\cap\hat{S}\neq\emptyset) \displaystyle+2\sum_{l>4\mathbb{E}[\tilde{X}_{n}]}l\mathbb{P}(\tilde{X}_{n}\geq l/2,\tilde{S}[n/(\log n)^{4},n]\cap\hat{S}\neq\emptyset) \displaystyle\leq\frac{Cn^{2}\log\log n}{(\log n)^{2}}+2\sum_{l>4\mathbb{E}[\tilde{X}_{n}]}l\mathbb{P}(\tilde{X}_{n}\geq l/2,\tilde{S}[n/(\log n)^{4},n]\cap\hat{S}\neq\emptyset). We used \mathbb{E}[\tilde{X}_{n}]\leq\frac{n}{(\log n)^{1/2+o(1)}} to show the final inequality. (Note that in [ 11 , Lemma 2.2] , they stated that it should be obtained for the graph distance if one follows the proof of [ 21 ] .) Now, assume that equation ( 6.5 ) holds with probability significantly less than (\log n)^{-2} . Let \Omega_{B} be the set of walks \tilde{S} such that equation ( 6.5 ) holds. We have that, \displaystyle\sum_{l>4\mathbb{E}[\tilde{X}_{n}]}l\mathbb{P}(\tilde{X}_{n}\geq l/2,\tilde{S}[n/(\log n)^{4},n]\cap\hat{S}\neq\emptyset,\tilde{S}\not\in\Omega_{B}) \displaystyle+\sum_{l>4\mathbb{E}[\tilde{X}_{n}]}l\mathbb{P}(\tilde{X}_{n}\geq l/2,\tilde{S}[n/(\log n)^{4},n]\cap\hat{S}\neq\emptyset,\tilde{S}\in\Omega_{B}) \displaystyle\leq n\sum_{l>4\mathbb{E}[\tilde{X}_{n}]}\mathbb{P}(\tilde{S}\not\in\Omega_{B}) \displaystyle+\sum_{l>4\mathbb{E}[\tilde{X}_{n}]}l\mathbb{P}(\hat{S}\cap\tilde{S}[n/(\log n)^{4},n]\neq\emptyset|\tilde{S}\in\Omega_{B},\tilde{X}_{n}>l/2)\mathbb{P}(\tilde{S}\in\Omega_{B},\tilde{X}_{n}\geq l/2) \displaystyle\leq o(n^{2}(\log n)^{-2})+\sum_{l>4\mathbb{E}[\tilde{X}_{n}]}l(\log n)^{-\epsilon}\mathbb{P}(\tilde{X}_{n}\geq l/2)\leq o(n^{2}(\log n)^{-2})+2\mathrm{Var}(X_{n})(\log n)^{-\epsilon}. Combining the previous equation with equation ( 6.6 ) gives the desired result. ∎ 6.3. Establishing equation ( 6.5 ) Lemma 6.9 . With probability greater than 1-\frac{1}{(\log n)^{2}} on walks \tilde{S} , there exists some c>0 such that we have, \mathbb{P}(\hat{S}\cap\tilde{S}[\frac{n}{(\log n)^{4}},n]\neq\emptyset|\tilde{S})\leq(\log n)^{-c}. We start with the following observation. We define a sequence of scales 0=K_{0}0 . By using Markov’s inequality and equation ( 6.9 ), we see that we have \mathbb{P}(\mathcal{O}_{i}^{c})\leq\frac{(\log n)^{4}}{K_{i}^{1-\delta}}. Thus, we see that, \mathbb{P}((\bigcap_{k=11}^{f}\mathcal{O}_{k})^{c})\leq\sum_{k=11}^{f}\frac{(\log n)^{4}}{K_{k}^{1-\delta}}\leq C\frac{(\log n)^{4}}{K_{11}^{1-\delta}}\ll\frac{1}{(\log n)^{2}}. In what follows, we will restrict our study to the event (6.11) \tilde{\Omega}:=\bigcap_{k=11}^{f}\mathcal{O}_{k}. On this event, we will analyze ( 6.8 ). Notice that we must have |\tilde{S}[\frac{n}{(\log n)^{4}},n]\cap\mathcal{A}_{i,n})|\leq|L(\mathcal{B}_{\sqrt{n/K_{i}}})|\leq\frac{n}{(K_{i})^{1+\delta}}\ll 1 . By using subadditivity of the capacity and the fact that the capacity must be less than the volume, we must have that \displaystyle\text{Cap}(\tilde{S}[\frac{n}{(\log n)^{4}},n]\cap\mathcal{A}_{i,n})\leq|\tilde{S}[\frac{n}{(\log n)^{4}},n]\cap\mathcal{A}_{i,n}| \displaystyle\leq|L(\mathcal{B}_{\sqrt{n/K_{i}}})|\leq\frac{n}{(K_{i})^{1+\delta}}. Now, since \max_{z\in\mathcal{A}_{i,n}}G(z)\leq C\frac{K_{i+1}}{n} , then we have, \displaystyle\sum_{i=11}^{f-1}\text{Cap}(\tilde{S}[\frac{n}{(\log n)^{4}},n]\cap\mathcal{A}_{i,n})\max_{z\in\mathcal{A}_{i,n}}G(z)\leq\sum_{i=11}^{f-1}\frac{n}{(K_{i})^{1+\delta}}\frac{K_{i+1}}{n}\leq CK_{11}^{-\delta}. ∎ 6.3.2. The smallest scales We now continue our analysis of equation ( 6.8 ) by considering the contributions from the large scales of K_{i} with i\leq 11 . We start by giving some lemmas that will be useful for our analysis. In the following, it is assumed that we consider an index with i\leq 11 . Notice that by the moment estimate for the capacity of the random walk in four dimensions, we have the following lemma. Lemma 6.11 . Let S[0,n] be a random walk starting at the origin. For any integer k>0 and \chi>0 , we have that, (6.12) \mathbb{P}\left({\rm Cap}(S[0,n])\geq\frac{n}{(\log n)^{1-\chi}}\right)\leq\frac{1}{(\log n)^{k}}, for any k\geq 0 . Proof. In [ 12 , Lemma 4.6] , we have that these are c>0 and C<\infty such that \displaystyle\mathbb{E}\left[\exp\left(c\frac{(\log n)^{2}}{n}({\rm Cap}(S[0,n])-\mathbb{E}[{\rm Cap}(S[0,n])])\right)\right]\leq C and \mathbb{E}[{\rm Cap}(S[0,n])]\sim\frac{\pi^{2}}{8}\frac{n}{(\log n)} (e.g., see [ 6 , Theorem 1.1] ). Hence, we can derive ( 6.12 ) by applying Markov’s inequality. ∎ In order to discuss the properties of the parts of the random walk inside each annulus, we need to consider the following stopping times. Define \displaystyle T^{i}_{k}:=\inf\{t\geq\tau^{i}_{k-1}:S_{t}\leq\sqrt{n/K_{i}}\}, \displaystyle\tau^{i}_{k}:=\inf\{t\geq T^{i}_{k}:S_{t}\geq 2\sqrt{n/K_{i}}\}. These are a sequence of times indicating when the random walk hits that ball of radius \sqrt{n/K_{i}} and later details when it escapes said ball. The following lemma will ensure that with high probability that there are not too many times in which the random walk will make an excursion into the ball of radius \sqrt{n/K_{i}} . Furthermore, each excursion into this ball will lie very close to its expected time. Lemma 6.12 . Let M^{i}=\sup\{k:\tau^{i}_{k}\leq n\} . Let \mathcal{H}^{i} be the event that \mathcal{H}^{i}:=\{M^{i}\leq(\log n)^{C}\}\bigcap_{k=1}^{(\log n)^{C}}\{|\tau^{i}_{k}-T^{i}_{k}|\leq\frac{n}{K_{i}^{1-\kappa}}\}\bigcap_{k=1}^{(\log n)^{C}}\{|\tau^{i}_{k}-T^{i}_{k}|\geq\frac{n}{K_{i}^{1+\kappa}}\}. We claim that there is some C such that \mathbb{P}((\mathcal{H}^{i})^{c})\ll\frac{1}{(\log n)^{2}} . Proof. Notice that M^{i} can be bounded from above by the number of spheres of radius \sqrt{n/K_{i}} that are necessary in order to cover the full random walk S[1,n] . Considering a sufficiently large C<\infty , bounding M^{i} with high probability is the estimate of [ 12 , Lemma 3.4] . Note that the probability that |\tau^{i}_{k}-T^{i}_{k}|\geq\frac{n}{K_{i}^{1-\kappa}} is bounded by the probability that a Brownian motion stays within a ball of radius 2\sqrt{n/K_{i}} for time \frac{n}{K_{i}^{1-\kappa}} . But, this happens with probability less than \exp[-cK_{i}^{\kappa}] . By taking a union bound, this is less than (\log n)^{C}\exp[-cK_{i}^{\kappa}]\ll(\log n)^{-2} . Furthermore, the probability that |\tau^{i}_{k}-T^{i}_{k}|\leq\frac{n}{K_{i}^{1+\kappa}} can be bounded by \exp[-cK_{i}^{\kappa}] by the reflection principle. Again, by taking a union bound, this is less than (\log n)^{C}\exp[-cK_{i}^{\kappa}]\ll(\log n)^{-2} . ∎ Proof of Lemma 6.9 : Estimate for ( 6.7 ). We can also define the event, \mathcal{G}^{i}:=\bigcap_{i=1}^{(\log n)^{C}}\left\{{\rm Cap}\left(S\left[T^{i}_{k},T^{i}_{k}+\frac{n}{K_{i}^{1-\kappa}}\right]\right)\leq\frac{n}{(\log n)^{1-\chi}K_{i}^{1-\kappa}}\right\}. By equation ( 6.12 ), we see that \mathbb{P}((\mathcal{G}^{i})^{c})\ll(\log n)^{-2} . Finally, we will need the following event, \mathcal{S}^{i}:=\left\{L(\mathcal{B}_{2\sqrt{n/K_{i}}})\leq\frac{n}{(K_{i})^{1-\delta}}\right\}, where we recall the notation L(\mathcal{B}_{r}) from Lemma 6.10 . By using equation ( 6.10 ) and Markov’s inequality with k large enough, we would have that \mathbb{P}((\mathcal{S}^{i})^{c})\ll(\log n)^{-2}. Now we consider the intersection of events, \Omega^{i}=\mathcal{S}^{i}\cap\mathcal{G}^{i}\cap\mathcal{H}^{i}. By combining the probability bounds from earlier, we have \mathbb{P}((\Omega^{i})^{c})\ll(\log n)^{-2}. Notice that, on the event \Omega^{i} , we can show that, (6.13) \displaystyle\rm{\displaystyle Cap}\left(\tilde{S}\left[\frac{n}{(\log n)^{4}},n\right]\cap\mathcal{A}_{i,n}\right)\leq\sum_{k=1}^{M^{i}}{\rm Cap}(\tilde{S}[T^{i}_{k},\tau^{i}_{k}])\leq\sum_{k=1}^{M^{i}}{\rm Cap}(\tilde{S}[T^{i}_{k},T^{i}_{k}+\frac{n}{K_{i}^{1-\kappa}}]) \displaystyle\leq\sum_{k=1}^{M^{i}}\frac{n}{(\log n)^{1-\chi}K_{i}^{1-\kappa}}\leq K_{i}^{2\kappa}\sum_{k=1}^{M^{i}}\frac{n}{(\log n)^{1-\chi}K_{i}^{1+\kappa}}\leq\frac{K_{i}^{2\kappa}}{(\log n)^{1-\chi}}\sum_{k=1}^{M^{i}}|\tau^{i}_{k}-T^{i}_{k}| \displaystyle\leq\frac{K_{i}^{2\kappa}}{(\log n)^{1-\chi}}L(\mathcal{B}_{2\sqrt{n/K_{i}}})\leq\frac{K_{i}^{2\kappa}}{(\log n)^{1-\chi}}\frac{n}{(K_{i})^{1-\delta}}. The second inequality used the fact that |\tau^{i}_{k}-T^{i}_{k}|\leq\frac{n}{K_{i}^{1-\kappa}} from the event \mathcal{H}^{i} . The third inequality used the bound on the capacity from the event \mathcal{G}^{i} . The fifth inequality used that |\tau^{i}_{k}-T^{i}_{k}|\geq\frac{1}{K_{i}^{1-\kappa}} from the event \mathcal{H}^{i} . Note that the sum of these differences is a lower bound on the amount of times in the intersection between \tilde{S}[\frac{n}{(\log n)^{4}},n] and \mathcal{B}_{2\sqrt{n/K_{i}}} . The final inequality used the event \mathcal{S}^{i} . Now, we see that \displaystyle\rm{\displaystyle Cap}\left(\tilde{S}\left[\frac{n}{(\log n)^{4}},n\right]\cap\mathcal{A}_{i,n}\right)\max_{z\in\mathcal{A}_{i,n}}G(z) \displaystyle\leq\frac{K_{i}^{2\kappa}n}{(\log n)^{1-\chi}(K_{i})^{1-\delta}}\frac{K_{i+1}}{n}\leq(\log n)^{3(2\kappa+\delta)+\chi}(\log n)^{-\epsilon}. By setting 3(2\kappa)+\delta+\chi\leq\epsilon/2 , we see that the line above will be less than (\log n)^{-\epsilon/2} . We now consider \hat{\Omega}:=\bigcap_{i=1}^{11}\Omega^{i} , we must have \mathbb{P}(\hat{\Omega}^{c})\ll(\log n)^{-2} . Furthermore, we must also have \sum_{i=1}^{11}{\rm Cap}\left(\tilde{S}\left[\frac{n}{(\log n)^{4}},n\right]\cap\mathcal{A}_{i,n}\right)\max_{z\in\mathcal{A}_{i,n}}G(z)\leq(\log n)^{-\epsilon/2}. Now, consider the intersection \tilde{\Omega}\cap\hat{\Omega} , where we recall \tilde{\Omega} from equation ( 6.11 ). We must have that \mathbb{P}((\tilde{\Omega}\cap\hat{\Omega})^{c})\ll(\log n)^{-2} and, in addition, the right-hand side of equation ( 6.8 ) can be bounded by (\log n)^{-c} for some c>0 . This completes the proof of Lemma 6.9 . ∎ 6.4. An analysis of X_{n}-\mathbb{E}[X_{n}] In this section, we will prove that \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}}\to 0 in distribution. We will first start by proving upper and lower bounds on \mathrm{Var}(X_{n}) . Note that an upper bound on \mathrm{Var}(X_{n}) was already derived in Lemma 6.6 . We now derive the corresponding lower bound for \mathrm{Var}(X_{n}) . Is this subsection, we will give the estimate only for cut points and graph distance. Lemma 6.13 . Let X_{n} denote the number of cut points, or the graph distance. We have that \mathrm{Var}(X_{n})\geq\frac{n^{2}}{(\log n)^{2+o(1)}}. Proof. We perform a dyadic decomposition of X_{n} up to (\log n)^{\epsilon} levels for some \epsilon>0 . We thus write X_{n}=\sum_{k=0}^{\epsilon\log_{2}(\log n)}\sum_{l=1}^{2^{k}}-E_{n}^{(k,l)}+\sum_{j=0}^{(\log n)^{\epsilon}-1}X[jn/(\log n)^{\epsilon},(j+1)n/(\log n)^{\epsilon}]. Notice, now that since \sum_{j=0}^{(\log n)^{\epsilon}-1}X[jn/(\log n)^{\epsilon},(j+1)n/(\log n)^{\epsilon}] is a sum of i.i.d. terms where each individual term has variance at most \frac{n^{2}}{(\log n)^{2-o(1)}} , we can compute its variance as (\log n)^{\epsilon}\frac{n^{2}}{(\log n)^{2\epsilon}(\log n)^{2-o(1)}}\leq\frac{n^{2}}{(\log n)^{2+\epsilon-o(1)}}. This will not be the major contributor to the variance. We will now consider the contribution to the variance from \sum_{k=0}^{\epsilon\log_{2}(\log n)}\sum_{l=1}^{2^{k}}-E_{n}^{(k,l)} . Notice, we have, \displaystyle\mathrm{Var}\left(\sum_{k=0}^{\epsilon\log_{2}(\log n)}\sum_{l=1}^{2^{k}}-E_{n}^{(k,l)}\right) \displaystyle=\sum_{k=0}^{\epsilon\log_{2}(\log n)}\sum_{l=1}^{2^{k}}\mathrm{Var}(-E_{n}^{(k,l)})+\sum_{k_{1},k_{2},l_{1},l_{2}:(k_{1},l_{1})\neq(k_{2},l_{2})}\mathbb{E}\left[E_{n}^{(k_{1},l_{1})}E_{n}^{(k_{2},l_{2})}-\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}]\right] \displaystyle\geq\mathrm{Var}(E_{n}^{(0,1)})-\sum_{k_{1},k_{2},l_{1},l_{2}:(k_{1},l_{1})\neq(k_{2},l_{2})}\mathbb{E}[E_{n}^{(k_{1},l_{1})}]\mathbb{E}[E_{n}^{(k_{2},l_{2})}] \displaystyle\geq\frac{n}{(\log n)^{2+o(1)}}-(\log n)^{2\epsilon}\frac{n^{2}}{(\log n)^{3+o(1)}}\gg\frac{n}{(\log n)^{2+o(1)}}. We used the fact that E_{n}^{(k_{1},l_{1})} are all positive terms, so the only possible negative contribution to the covariance comes from the product of expectations. However, we know from Corollary 6.7 that the product of expectations of these expectations is bounded from above by \frac{n^{2}}{(\log n)^{3+o(1)}} . This completes the proof of our assertion. ∎ With a small modification to the proof above, we can derive the following main result. Theorem 6.14 . Let X_{n} denote the number of cut points, or the graph distance. We have that as n\to\infty , \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}}\to 0, in distribution. Proof. We proceed with the same dyadic decomposition as we have done in the previous proof. X_{n}=\sum_{k=0}^{\epsilon\log_{2}(\log n)}\sum_{l=1}^{2^{k}}-E_{n}^{(k,l)}+\sum_{j=0}^{(\log n)^{\epsilon}-1}X[jn/(\log n)^{\epsilon},(j+1)n/(\log n)^{\epsilon}]. Let \Omega^{(k,l)} be the set from Lemma 6.3 (constructed for the appropriate cross term E_{n}^{(k,l)} ) and consider \Omega_{A}:=\bigcap_{(k,l)}\Omega^{(k,l)} . By Lemma 6.3 , we can ensure that (\Omega^{(k,l)})^{c} holds with probability no larger than \text{O}\left(\frac{\log\log n}{\log n}\right) . By taking a union bound, we see that \mathbb{P}(\Omega_{A}^{c})=\text{O}\left(\frac{\log\log n}{(\log n)^{1-\epsilon}}\right)\ll 1. On the event, \Omega^{(k,l)} , we see that |-E_{n}^{(k,l)}+\mathbb{E}[E_{n}^{(k,l)}]|\leq\frac{n}{(\log n)^{3/2+o(1)}}. Thus, on \Omega_{A} , we must have \left|\sum_{k=0}^{\epsilon\log_{2}(\log n)}\sum_{l=1}^{2^{k}}-E_{n}^{(k,l)}+\mathbb{E}[E_{n}^{(k,l)}]\right|\leq(\log n)^{\epsilon}\frac{n}{(\log n)^{3/2-o(1)}}. Furthermore, notice that by Lemma 6.6 , \displaystyle\mathrm{Var}\left(\sum_{j=0}^{(\log n)^{\epsilon}-1}X[jn/(\log n)^{\epsilon},(j+1)n/(\log n)^{\epsilon}]\right)\leq\frac{n^{2}}{(\log n)^{2+\epsilon+o(1)}}. Let \Omega_{B} be the event that \sum_{j=0}^{(\log n)^{\epsilon}-1}X[jn/(\log n)^{\epsilon},(j+1)n/(\log n)^{\epsilon}]-\mathbb{E}[X[jn/(\log n)^{\epsilon},(j+1)n/(\log n)^{\epsilon}]] is smaller than \frac{n}{(\log n)^{1+\epsilon/4}} . By Markov’s inequality \mathbb{P}(\Omega_{B}^{c})\leq(\log n)^{-\epsilon/2} . Now, on \Omega_{A}\cap\Omega_{B} , we have X_{n}-\mathbb{E}[X_{n}]\leq\frac{n}{(\log n)^{1+\epsilon/4}}+(\log n)^{\epsilon}\frac{n}{(\log n)^{3/2-o(1)}}\ll\frac{n}{(\log n)^{1+o(1)}}=\sqrt{\mathrm{Var}(X_{n})}. Furthermore, \mathbb{P}(\Omega_{A}\cap\Omega_{B})=1-o(1) by a union bound. This completes the proof. ∎ 6.5. An analysis of the effective resistance In this subsection, we present, for independent interest, a similar analysis done in the previous sections when we impose weaker conditions on the bounds we obtain for the variance and the expectation for the cross terms under consideration in d=4 . Namely, we will assume that the cross-terms are very heavy tailed and that we have some almost optimal upper and lower bounds for the variance up to powers of \log n . In particular, we will give the proof of the desired result for the effective resistance in d=4 in Subsection 6.5.2 . The following assumption will detail what we assume about the cross terms under consideration. Before this, in Subsection 6.5.1 , we will give an estimate for the effective resistance, which assures that Assumption 6.17 parts (2) (3) will hold. 6.5.1. Upper bound for the cross term of the effective resistance We will give the upper bound for the second moment of the cross term of the effective resistance E[E_{n}^{2}] . Lemma 6.15 . Consider d=4 . There exists an event \Omega of probability O(\frac{\log\log n}{\log n}) such that (6.14) \displaystyle E_{n}\mathbbm{1}[\Omega^{c}]\leq\mathbb{E}[E_{n}]. We have that (6.15) \mathbb{E}[E_{n}^{2}]\leq\frac{n^{2}}{(\log n)^{1-o(1)}}. Remark 6.16 . The constant that appears on the right-hand side of equation ( 6.15 ) is not the best possible (rather it should be improved to 1-o(1) ). However, obtaining the optimal constant is not necessary for the estimates that follow. Proof. Recall \Omega in Lemma 6.3 . On \Omega^{c} , we have that, E_{n}\leq 2\frac{n}{(\log n)^{b/2}}. Hence, we obtain ( 6.14 ). Notice, also that since E_{n} is deterministically less than n , we must have that, \mathbb{E}[E_{n}^{2}]=\mathbb{E}[E_{n}^{2}\mathbbm{1}[\Omega]]+\mathbb{E}[E_{n}^{2}\mathbbm{1}[\Omega^{c}]]\leq n^{2}\mathbb{P}(\Omega)+4\frac{n^{2}}{(\log n)^{b}}\leq\frac{n^{2}}{(\log n)^{1-o(1)}}. Hence, we obtain ( 6.15 ). ∎ Proof of Proposition 1.3 . By Lemmas 6.1 and 6.15 , we obtain the result, which corresponds to (2) (3) for Assumption 6.17 for b_{1}=2+o(1) and b_{2}=1-o(1) . ∎ 6.5.2. General arguments Assumption 6.17 . We let X[a,b] for a,b\in\mathbb{Z}^{+},b>a be a collection of random variables satisfying the following properties. First, define E_{n}:=X_{n}+X[n,2n]-X_{2n} (1) The law of X[a,b] depends only on the value of |b-a| . (2) If [a,b]\cap[c,d]=\emptyset independent, then X[a,b] is independent of X[c,d] . (3) There exist constants b_{1},b_{2} such that \frac{n^{2}}{(\log n)^{b_{1}}}\leq\mathbb{E}[E_{n}^{2}]\leq\frac{n^{2}}{(\log n)^{b_{2}}}. (4) There is a set \Omega with probability O(\frac{\log\log n}{\log n}) such that E_{n}\mathbbm{1}[\Omega^{c}]\leq\mathbb{E}[E_{n}]. We first define the function f(n) as, \mathrm{Var}(X_{n})=\frac{n^{2}}{(\log n)^{f(n)}}. In order to characterize this, we need to first define the associated function g(n) as as follows: \mathbb{E}[E_{n}^{2}]:=\frac{n^{2}}{(\log n)^{g(n)}}. We remark that the third part of our Assumption 6.17 shows that we have b_{1}+o(1)\leq g(n)\leq b_{2}+o(1) , but we do not get a uniform control of g(n) . In addition, as a consequence of the fourth part of Assumption 6.17 , we must also have: (6.16) \mathbb{E}[E_{n}^{2}]O\left(\frac{\log\log n}{\log n}\right)\geq\mathbb{E}[E_{n}]^{2}. To try to get a uniform control of g(n) on a fixed number of scales, we fix a constant K and additionally define the function g(n,K) as: g(n,K):=\min_{1\leq j\leq K}g(n2^{-j}). This function will be used to characterize the size of the expectation of the square of the graph distance, as detailed in the following lemma. Lemma 6.18 . Fix some K>0 . Assume that there exists n such that f(n2^{-K})\geq g(n,K)+\frac{1}{4} . Then, we will have that f(n)\leq g(n,K)+o(1) , where o(1) is a term that will decay to 0 as n is taken to \infty . Proof. We start with a dyadic decomposition of the random variables. As a consequence, we observe that, \displaystyle X_{n}-\mathbb{E}[X_{n}]=\sum_{j=1}^{2^{K}}(\tilde{X}_{K,j}-\mathbb{E}[\tilde{X}_{K,j}])+\sum_{k=1}^{K}\sum_{l=1}^{2^{k}}(E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}]). We first consider the variance of the term, \overline{\mathcal{E}}:=-\sum_{k=1}^{K}\sum_{l=1}^{2^{k}}(E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}]). We remark that when computing the second moment \mathcal{E}^{2} , the only negative contribution can come from terms of the form, (6.17) \displaystyle N_{(k_{1},l_{1}),(k_{2},l_{2})}:=-\mathbb{E}[(E_{n}^{(k_{1},l_{1})}-\mathbb{E}[E_{n}^{(k_{1},l_{1})}])\mathbbm{1}[E_{n}^{(k_{1},l_{1})}-\mathbb{E}[E_{n}^{(k_{1},l_{1})}]>0] \displaystyle\times(E_{n}^{(k_{2},l_{2})}-\mathbb{E}[E_{n}^{(k_{2},l_{2})}])\mathbbm{1}[E_{n}^{(k_{2},l_{2})}-\mathbb{E}[E_{n}^{(k_{2},l_{2})}]<0]] \displaystyle\leq\mathbb{E}[(E_{n}^{(k_{1},l_{1})}-\mathbb{E}[E_{n}^{(k_{1},l_{1})}])^{2}\mathbbm{1}[E_{n}^{(k_{1},l_{1})}-\mathbb{E}[E_{n}^{(k_{1},l_{1})}]>0]^{1/2} \displaystyle\times\mathbb{E}[(E_{n}^{(k_{2},l_{2})}-\mathbb{E}[E_{n}^{(k_{2},l_{2})}])^{2}\mathbbm{1}[E_{n}^{(k_{2},l_{2})}-\mathbb{E}[E_{n}^{(k_{2},l_{2})}]<0]]^{1/2} \displaystyle\leq\mathbb{E}[(E_{n}^{(k_{1},l_{1})})^{2}]^{1/2}\mathbb{E}[E_{n}^{(k_{2},l_{2})}]\leq\frac{n2^{-k_{1}}}{(\log(n2^{-k_{1}}))^{g(n2^{-k_{1}})/2}}\frac{n2^{-k_{2}}}{(\log n2^{-k_{2}})^{g(n2^{-{k_{2}}})/2+1/2-o(1)}} \displaystyle\leq\frac{n^{2}}{(\log n)^{g(n,K)+1/2+o(1)}}. To get the third inequality, we used the fact that E_{n}^{(k_{2},l_{2})} must be positive. Thus, under the condition that E_{n}^{(k_{2},l_{2})}-\mathbb{E}[E_{n}^{(k_{2},l_{2})}] is negative, the expectation of \mathbb{E}[(E_{n}^{(k_{2},l_{2})}-\mathbb{E}[E_{n}^{(k_{2},l_{2})}])^{2}\mathbbm{1}[E_{n}^{(k_{2},l_{2})}-\mathbb{E}[E_{n}^{(k_{2},l_{2})}]<0]]^{1/2}\leq\mathbb{E}[E_{n}^{(k_{2},l_{2})}] . The second to last inequality used the definition of g along with equation ( 6.16 ) for n large enough. Finally, the last inequality used the fact that \frac{n}{(\log n)^{k}} is increasing for n large enough as well as the definition of g(n,K) . This should contrast with the positive contribution coming from, \mathbb{E}[(E_{n}^{(k_{1},l_{1})}-\mathbb{E}[E_{n}^{(k_{1},l_{1})}])^{2}]=\frac{(n2^{-k_{1}})^{2}}{(\log n2^{-k_{1}})^{g(n2^{-k_{1}})}}. There will be at least one term (k_{1},l_{1}) where g(n2^{-k_{1}}) attains its maximum value, and for this specific value k^{\max} , we have that, \frac{(n2^{-k^{\max}})^{2}}{(\log n2^{-k^{\max}})^{g(n2^{-k^{\max}})}}=\frac{n^{2}}{(\log n)^{g(n,K)+o(1)}}. The factor of o(1) is to compensate for possible changes of the constant factor in front. We remark that due to these computations, there is a gap of of a factor of (\log n)^{1/2} between the positive term above and the negative contribution from equation ( 6.17 ). This will ensure a sufficiently good lower bound for the expectation of \overline{\mathcal{E}} . Indeed, we have that, (6.18) \displaystyle\mathbb{E}[\mathcal{E}^{2}]\geq\sum_{k=1}^{K}\sum_{l=1}^{2^{k}}\mathbb{E}[(E_{n}^{(k_{1},l_{1})}-\mathbb{E}[E_{n}^{(k_{1},l_{1})}])^{2}]+\sum_{k_{1}=1}^{K}\sum_{l_{1}=1}^{2^{k_{1}}}\sum_{k_{2}=1}^{K}\sum_{l_{1}=1}^{2^{k_{2}}}N_{(k_{1},l_{1}),(k_{2},l_{2})} \displaystyle\geq\frac{n^{2}}{(\log n)^{g(n,K)+o(1)}}-K^{2}4^{K}\frac{n^{2}}{(\log n)^{g(n,K)+\frac{1}{2}+o(1)}}\geq\frac{n^{2}}{(\log n)^{g(n,K)+o(1)}}. Furthermore, if we define \mathcal{I}:=\sum_{j=1}^{2^{K}}(\tilde{X}_{(K,j)}-\mathbb{E}[\tilde{X}_{(K,j)}]), we notice that we have, (6.19) \mathbb{E}[\mathcal{I}^{2}]\leq 2^{K}\frac{(n2^{-K})^{2}}{(\log n2^{-K})^{f(n2^{-K})}}\leq 2^{K}\frac{(n2^{-K})^{2}}{(\log n2^{-K})^{g(n,K)+\frac{1}{4}}}\leq\frac{n^{2}}{(\log n)^{g(n,K)+\frac{1}{4}}}. In the first inequality, we used the fact that \mathcal{I} is a sum of independent random variables. Since g(n,K) lies between b_{2}+o(1) and b_{1}+o(1) , the final inequality must be true for large enough n . Notice now, that we have, by the Cauchy-Schwarz inequality, (6.20) \mathbb{E}[(\overline{\mathcal{E}}+\mathcal{I})^{2}]\geq(\mathbb{E}[\overline{\mathcal{E}}^{2}]^{1/2}-\mathbb{E}[\mathcal{I}^{2}]^{1/2})^{2}\geq\frac{n^{2}}{(\log n)^{g(n,K)+o(1)}}. ∎ Remark 6.19 . By ( 6.18 ), ( 6.19 ) and ( 6.20 ), we have \epsilon>0 , \displaystyle\limsup_{n\to\infty}\frac{\mathrm{Var}(X_{n})}{n^{2}/(\log n)^{b_{2}+\epsilon}}>0,\quad\limsup_{n\to\infty}\frac{\mathrm{Var}(X_{n})}{n^{2}/(\log n)^{b_{1}-\epsilon}}<\infty noting (\mathbb{E}[\overline{\mathcal{E}}^{2}]^{1/2}-\mathbb{E}[\mathcal{I}^{2}]^{1/2})^{2}\leq\mathbb{E}[(\overline{\mathcal{E}}+\mathcal{I})^{2}]\leq(\mathbb{E}[\overline{\mathcal{E}}^{2}]^{1/2}+\mathbb{E}[\mathcal{I}^{2}]^{1/2})^{2} . We now present the heuristic argument we will use to analyze the behavior of \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}} . • We start by taking the high probability event \Omega to be the event that all E_{n}^{(k,l)}-\mathbb{E}[E_{n}^{(k,l)}]\leq\mathbb{E}[E_{n}^{(k,l)}] . • If there exists an infinite sequence of m such that we have f(n2^{-K}) is greater than g(n,K)+\frac{1}{4} , then we have f(n)\leq g(n,K)-o(1) . For such n , we will be able to show that \frac{X_{n}-\mathbb{E}[X_{n}]}{\sqrt{\mathrm{Var}(X_{n})}} will go to 0 . • In the case that the above does not happen, it must be the case that eventually all f(n2^{-K})\leq g(n,K)+\frac{1}{4}