Introduction
Let G ⃗ = ( V , E ⃗ ) \vec{G}=(V,\vec{E}) G = ( V , E ) be a graph where each edge comes with a specific direction and there are no self-loops. More precisely, E ⃗ \vec{E} E is a subset of the following set of ordered pairs
{ ( u , v ) : u , v ∈ V , u ≠ v } \{(u,v):u,v\in V,\ u\ne v\} {( u , v ) : u , v ∈ V , u = v }
If e ⃗ ∈ E ⃗ \vec{e}\in\vec{E} e ∈ E , such that e ⃗ = ( u , v ) \vec{e}=(u,v) e = ( u , v ) , we say that u u u is the tail of e ⃗ \vec{e} e and v v v is the head of e ⃗ \vec{e} e and denote them by e ⃗ − \vec{e}^{-} e − and e ⃗ + \vec{e}^{+} e + , respectively. We say e ⃗ \vec{e} e is an outgoing edge from u u u and an incoming edge to v v v . A directed path is a sequence of distinct edges e ⃗ 1 , e ⃗ 2 , ⋯ , e ⃗ n \vec{e}_1,\vec{e}_2,\cdots,\vec{e}_n e 1 , e 2 , ⋯ , e n such that e ⃗ i + = e ⃗ ( i + 1 ) − \vec{e}_i^{+}=\vec{e}_{(i+1)}^{-} e i + = e ( i + 1 ) − , for all 1 ≤ i < n 1\le i<n 1 ≤ i < n . If there is a directed path e ⃗ 1 , e ⃗ 2 , ⋯ , e ⃗ n \vec{e}_1,\vec{e}_2,\cdots,\vec{e}_n e 1 , e 2 , ⋯ , e n such that e ⃗ n + = e ⃗ 1 − \vec{e}_n^{+}=\vec{e}_1^{-} e n + = e 1 − , we say that this path creates a directed cycle . Sometimes we denote a directed cycle by the set of heads and tails of the edges in it. If there is a directed path from a vertex u u u to a vertex v v v , we say that u u u is in the past of v v v , and denote it as u ∈ Past v u\in\operatorname{Past}_v u ∈ Past v . Note that our definition admits paths. with no edges, so v ∈ Past v v \in\operatorname{Past}_v v ∈ Past v , for all v ∈ V v \in V v ∈ V .
The setting of this article is on the complete directed graph K ⃗ n = ( V n , E ⃗ n ) \vec{K}_n = (V_n,\vec{E}_n) K n = ( V n , E n ) , where V n V_n V n is a set of n n n vertices, and E ⃗ n \vec{E}_n E n is the set of all possible directed edges. More precisely, the edge set of the complete directed graph is given by
E ⃗ n = { e ⃗ = ( u , v ) : u , v ∈ V n , u ≠ v } . \vec{E}_n = \{\vec{e} = (u,v) : u,v \in V_n,\ u \ne v\}. E n = { e = ( u , v ) : u , v ∈ V n , u = v } .
See Figure 1 for an example.
Figure 1. The complete directed graph on 5 vertices with distinguished vertex ∂ \partial ∂ .
Definition 1.1. An arborescence , denoted ( T ⃗ , ∂ ) (\vec{T},\partial) ( T , ∂ ) is a finite directed graph T ⃗ = ( V ( T ⃗ ) , E ( T ⃗ ) ) \vec{T} = (V(\vec{T}),E(\vec{T})) T = ( V ( T ) , E ( T )) with boundary ∂ ∈ V ( T ⃗ ) \partial\in V(\vec{T}) ∂ ∈ V ( T ) , which has the following properties:
∂ \partial ∂ has no outgoing edge,
all vertices v ∈ V ( T ⃗ ) ∖ { ∂ } v \in V(\vec{T}) \setminus\{\partial\} v ∈ V ( T ) ∖ { ∂ } have exactly one outgoing edge,
there are no directed cycles and
the graph is connected in the undirected sense.
Definition 1.2. A spanning arborescence ( T ⃗ , ∂ ) (\vec{T},\partial) ( T , ∂ ) of a finite directed graph ( G ⃗ , ∂ ) (\vec{G},\partial) ( G , ∂ ) , where ∂ \partial ∂ is a distinguished vertex, is an arborescence with boundary ∂ \partial ∂ such that V ( T ⃗ ) = V ( G ⃗ ) V(\vec{T}) = V(\vec{G}) V ( T ) = V ( G ) and E ( T ⃗ ) ⊂ E ( G ⃗ ) E(\vec{T}) \subset E(\vec{G}) E ( T ) ⊂ E ( G ) .
See Figure 2 for an example.
Figure 2. The red edges form a spanning arborescence of ( K ⃗ 5 , ∂ ) (\vec{K}_5,\partial) ( K 5 , ∂ ) .
Remark 1.3. For a spanning arborescence, given conditions 1 and 2 in Definition 1.1 , points 3 and 4 are equivalent to saying that the underlying undirected graph is a spanning tree, and then all edges are directed towards ∂ \partial ∂ .
Remark 1.4. In an arborescence, from each vertex there is a unique directed path to ∂ \partial ∂ .
The article concerns the behaviour of the spanning arborescence of ( K ⃗ n , ∂ ) (\vec{K}_n,\partial) ( K n , ∂ ) that has minimum weight when the edges are assigned random weights. This means that each of the directed edges of K ⃗ n \vec{K}_n K n is assigned an independent non-negative random variable with density p ( x ) p(x) p ( x ) , which satisfies the following properties:
p ( 0 ) > 0 p(0)>0 p ( 0 ) > 0 ,
p p p is continuous at 0 0 0 ,
∫ 0 ∞ x p ( x ) d x < ∞ \int_0^\infty xp(x)\,\mathrm{d}x<\infty ∫ 0 ∞ x p ( x ) d x < ∞ .
We denote this family of random variables by { Y e ⃗ } e ⃗ ∈ E ⃗ n \{Y_{\vec e}\}_{\vec e\in\vec E_n} { Y e } e ∈ E n and define the weight of a spanning arborescence ( T ⃗ , ∂ ) (\vec T,\partial) ( T , ∂ ) of ( K ⃗ n , ∂ ) (\vec K_n,\partial) ( K n , ∂ ) to be
W ( T ⃗ ) = ∑ e ⃗ ∈ E ⃗ ( T ⃗ ) Y e ⃗ . W(\vec T)=\sum_{\vec e\in\vec E(\vec T)}Y_{\vec e}. W ( T ) = e ∈ E ( T ) ∑ Y e .
The minimum spanning arborescence (MSA) on ( K ⃗ n , ∂ ) (\vec K_n,\partial) ( K n , ∂ ) is then defined to be
( T ⃗ n ∗ , ∂ ) : = arg min { W ( T ⃗ ) : ( T ⃗ , ∂ ) is a spanning arborescence on ( K ⃗ n , ∂ ) } . (\vec T_n^*,\partial):=\operatorname*{arg\,min}\{W(\vec T):(\vec T,\partial)\text{ is a spanning arborescence on }(\vec K_n,\partial)\}. ( T n ∗ , ∂ ) := arg min { W ( T ) : ( T , ∂ ) is a spanning arborescence on ( K n , ∂ )} .
We will denote by W n ∗ W_n^* W n ∗ the weight of the minimum spanning arborescence. Note that the minimum spanning arborescence is almost surely unique as the weights on the edges are continuous random variables. The main result of this article is the following:
Theorem 1.5. Let i.i.d. weights { Y e ⃗ } e ⃗ ∈ E ⃗ n \{Y_{\vec e}\}_{\vec e\in\vec E_n} { Y e } e ∈ E n be assigned to the edges of ( K ⃗ n , ∂ ) (\vec K_n,\partial) ( K n , ∂ ) whose common density p p p satisfies the previous hypotheses. Let X v ( n ) : = min e ⃗ − = v Y e ⃗ X_v^{(n)}:=\min_{\vec e_-=v}Y_{\vec e} X v ( n ) := min e − = v Y e . Then as n → ∞ n\to\infty n → ∞ ,
n ( W n ∗ − n E ( X v ( n ) ) ) → d N ( 0 , 1 p ( 0 ) 2 ) . \sqrt{n}\left(W_n^*-n\mathbb{E}\left(X_v^{(n)}\right)\right)\xrightarrow{d}\mathcal{N}\left(0,\frac{1}{p(0)^2}\right). n ( W n ∗ − n E ( X v ( n ) ) ) d N ( 0 , p ( 0 ) 2 1 ) . Since { Y e ⃗ } e ⃗ ∈ E ⃗ n \{Y_{\vec e}\}_{\vec e\in\vec E_n} { Y e } e ∈ E n are i.i.d., { X v ( n ) } v ∈ V n ∖ { ∂ } \{X_v^{(n)}\}_{v\in V_n\setminus\{\partial\}} { X v ( n ) } v ∈ V n ∖ { ∂ } are also i.i.d. For brevity we remove the suffix and denote them as X ( n ) X^{(n)} X ( n ) , for all v ∈ V n ∖ { ∂ } v\in V_n\setminus\{\partial\} v ∈ V n ∖ { ∂ } . The limiting variance is 1 p ( 0 ) 2 \frac{1}{p(0)^2} p ( 0 ) 2 1 since lim n → ∞ n 2 Var ( X ( n ) ) = 1 p ( 0 ) 2 \lim_{n\to\infty}n^2\operatorname{Var}\left(X^{(n)}\right)=\frac{1}{p(0)^2} lim n → ∞ n 2 Var ( X ( n ) ) = p ( 0 ) 2 1 , we can derive it as an immediate corollary of Lemma 6.1 .
Remark 1.6. Let Z n = n ( W n ∗ − n E ( X ( n ) ) ) Z_n=\sqrt{n}\left(W_n^*-n\mathbb{E}\left(X^{(n)}\right)\right) Z n = n ( W n ∗ − n E ( X ( n ) ) ) and a n = n E ( X ( n ) ) a_n=n\mathbb{E}\left(X^{(n)}\right) a n = n E ( X ( n ) ) . By Theorem 1.5 , we know that Z n Z_n Z n is tight. Since n − 1 / 2 → 0 n^{-1/2}\to0 n − 1/2 → 0 , W n ∗ − a n = Z n / n → 0 W_n^*-a_n=Z_n/\sqrt{n}\to0 W n ∗ − a n = Z n / n → 0 in probability. If the edge weights are i.i.d. Exponential(1) or Uniform[ 0 , 1 ] [0,1] [ 0 , 1 ] , then a n = 1 a_n=1 a n = 1 . Thus W n ∗ → 1 W_n^*\to1 W n ∗ → 1 in probability.
Our article follows a great deal of recent interest in understanding the behaviour of the MSA in various settings, including the complete directed graph. The issue of almost sure convergence to an infinite volume limit was explored in [RS24] by Ray and Sen. Inspired by an algorithmic construction of the MSA, they describe a new stochastic process termed the “loop-contracting random walk” for the purposes of constructing the arborescence. This is in analogy with the loop-erased random walk and its relationship with weighted spanning trees, formalized by Wilson’s algorithm. One of the major results of [RS24] is that the infinite volume limit exists almost surely if the loop-contracting random walk is almost surely transient. Verifying the transience is tricky since the process is not Markovian and it is unclear if it admits a zero-one law.
The MSA on the complete directed graph has been studied in [8 ] , [9 ] and [BR26]. In the undirected case, a law of large numbers for the weight of the minimum spanning tree was proved by Frieze [8 ] , remarkably showing that for a wide class of weights the limit is ζ ( 3 ) \zeta(3) ζ ( 3 ) . The method of [8 ] hinges on assuming that the density of the weights satisfies p ( 0 ) > 0 p(0)>0 p ( 0 ) > 0 . For the MSA, the analogous law of large numbers for uniform [ 0 , 1 ] [0,1] [ 0 , 1 ] weights was accomplished by Frieze and Tkocz in [9 ] . The limit, in contrast to the undirected version’s ζ ( 3 ) \zeta(3) ζ ( 3 ) , is 1 1 1 . The central limit theorem for the weight of the MST on the complete graph was proved by Janson [11 ] with i.i.d. Uniform[ 0 , 1 ] [0,1] [ 0 , 1 ] edge weights. The variance of the limiting Gaussian was first identified as a highly complicated sum, later simplified by Wästlund to 6 ζ ( 4 ) − 4 ζ ( 3 ) 6\zeta(4)-4\zeta(3) 6 ζ ( 4 ) − 4 ζ ( 3 ) [13 ] .
Hansen established a CLT, as well as a law of large numbers (in the L 1 L^1 L 1 sense), for the weight of the MSA without a fixed boundary [10 ] . Fixing a boundary vertex imposes additional connectivity constraints, making the repair steps (specifically Step 2 and Step 3 detailed in § 4 ) different. Furthermore, the CLT of [10 ] can be recovered from our result for the class of weights considered in this article. We discuss this in § 9 . The case with a designated boundary point is important, since there are known algorithms for constructing the rooted MSA, such as the Chu-Liu-Edmonds-Bock (CLEB) algorithm (see [2 ] , [6 ] ). Constructing the MSA without a designated boundary point is significantly more tedious, whether the rooted case can be bypassed altogether remains unclear. The CLEB algorithm is instrumental in the study of the infinite volume structure MSAs in [RS24] and [BR26].
Bagchi and Ray explored the limiting structure of the MSA as a graph and characterized the local weak limit as a Poisson(1) Galton-Watson tree conditioned to survive directed towards an infinite path. To identify the local weak limit of MSA on the complete directed graph, the memoryless property of the exponential distribution plays very important role. This stands in sharp contrast to the local weak limit of the minimum spanning tree on the undirected complete graph. In both [RS24] and [BR26], it is observed that the geometry of the MSA depends on the distribution of the weights, significantly complicating its study.
More generally, our article fits neatly into the theme of exploring central limit theorems for randomized combinatorial optimization problems. We direct the reader to [4 ] and [5 ] for CLTs for certain other combinatorial optimization problems in the mean field setting. Note, [5 ] is in the positive temperature setting and can thus be thought of as CLTs for approximate versions of the relevant optimization problems.
AI Declaration
All ideas for the proof were conceived by us. Google Gemini Pro and ChatGPT were used for verification of details, finding gaps and proof reading. Gemini also suggested the integral representation used in the saddle point argument in the proof of Lemma 5.6. We subsequently verified all details by hand, and the actual writing has been done by us.
Acknowledgement
The authors would like to thank Gourab Ray for suggesting the problem and for several subsequent useful discussions, concerning both the mathematics and presentation.
Proof Method
In § 5 , 4 and 5, we present detailed proofs for the case when weights have exponential distribution with mean 1, mainly because the memoryless property of the exponential distribution allows several calculations in the proof to be carried out explicitly. We explain how the methods carry over to a more general family of distributions in § 8 .
Throughout the article, for positive f f f and g g g , we are going to use the following standard asymptotic notation:
f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f ( n ) = O ( g ( n )) if there exist constants C > 0 C>0 C > 0 and n 0 ∈ N n_0\in\mathbb{N} n 0 ∈ N such that f ( n ) ≤ C g ( n ) f(n)\leq Cg(n) f ( n ) ≤ C g ( n ) for all n ≥ n 0 n\geq n_0 n ≥ n 0 .
f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) f ( n ) = Θ ( g ( n )) if there exist constants c , C > 0 c,C>0 c , C > 0 and n 0 ∈ N n_0\in\mathbb{N} n 0 ∈ N such that c g ( n ) ≤ f ( n ) ≤ C g ( n ) cg(n)\leq f(n)\leq Cg(n) c g ( n ) ≤ f ( n ) ≤ C g ( n ) , for all n ≥ n 0 n\geq n_0 n ≥ n 0 . If f ( n ) / g ( n ) → 1 f(n)/g(n)\to1 f ( n ) / g ( n ) → 1 , then we say that f ∼ g f\sim g f ∼ g .
f ( n ) = o ( g ( n ) ) f(n)=o(g(n)) f ( n ) = o ( g ( n )) if lim n → ∞ f ( n ) g ( n ) = 0 \lim_{n\to\infty}\frac{f(n)}{g(n)}=0 lim n → ∞ g ( n ) f ( n ) = 0 .
Recall that we have the complete directed graph K ⃗ n \vec{K}_n K n with a fixed vertex ∂ \partial ∂ and every directed edge e ⃗ ∈ E ⃗ n \vec{e}\in\vec{E}_n e ∈ E n independently has an Exponential(1) weight Y e ⃗ Y_{\vec{e}} Y e . The first step is to expose the minimum-weight outgoing edge from every vertex except ∂ \partial ∂ . We denote the configuration so obtained by K ⃗ n 1 \vec{K}_n^1 K n 1 , and its weight by W n W_n W n , that is W n = ∑ e ⃗ ∈ E ⃗ ( K ⃗ n 1 ) Y e ⃗ W_n=\sum_{\vec{e}\in\vec{E}(\vec{K}_n^1)}Y_{\vec{e}} W n = ∑ e ∈ E ( K n 1 ) Y e . See Figure 3 for a possible configuration.
Figure 3. K ⃗ n 1 \vec{K}_n^1 K n 1 obtained by exposing the minimum-weight outgoing edges from all the vertices, except ∂ \partial ∂ , in K ⃗ n \vec{K}_n K n . Every component has one cycle, except C ∂ C^\partial C ∂ that is an arborescence with boundary ∂ \partial ∂ .
Any two vertices that are connected by a sequence of edges, irrespective of direction, are said to be part of the same connected component. Note the following points about the connected components of K ⃗ n 1 \vec{K}_n^1 K n 1 , which are straightforward to prove:
We will comment more on the structural properties of this directed graph K ⃗ n 1 \vec{K}_n^1 K n 1 in the next section. It suffices for now to note that the choice of exposed edges from each vertex, as well as their weights, are independent.
Lemma 2.1. W n → 1 W_n \to1 W n → 1 almost surely as n → ∞ n \to\infty n → ∞ .
Proof. Let X v ( n ) X_v^{(n)} X v ( n ) be the weight of the edge exposed from vertex v v v when exposing the minimum weight edge. This means,
X v ( n ) : = min e ⃗ − = v Y e ⃗ . X_v^{(n)} := \min_{\vec{e}_-=v}Y_{\vec{e}}. X v ( n ) := e − = v min Y e .
The minimum of m m m independent exponential random variables is an exponential random variable whose mean is m − 1 m^{-1} m − 1 . We can then rescale these variables to get
X v ( n ) = Y v ( n ) n − 1 , X_v^{(n)} = \frac{Y_v^{(n)}}{n-1}, X v ( n ) = n − 1 Y v ( n ) ,
where { Y v ( n ) } v ∈ V n \{Y_v^{(n)}\}_{v\in V_n} { Y v ( n ) } v ∈ V n are independent exponential random variables with mean 1. Since
W n = ∑ v ∈ V n ∖ { ∂ } X v ( n ) = 1 n − 1 ∑ v ∈ V n ∖ { ∂ } Y v ( n ) , W_n = \sum_{v\in V_n\setminus\{\partial\}} X_v^{(n)}
= \frac{1}{n-1}\sum_{v\in V_n\setminus\{\partial\}}Y_v^{(n)}, W n = v ∈ V n ∖ { ∂ } ∑ X v ( n ) = n − 1 1 v ∈ V n ∖ { ∂ } ∑ Y v ( n ) ,
the almost sure limit W n → E ( Y v ) = 1 W_n \to\mathbb{E}(Y_v)=1 W n → E ( Y v ) = 1 follows from the strong law of large numbers.
For the next layer of asymptotics, note that it is straightforward to extract a CLT for W n W_n W n , which we now state without proof:
Lemma 2.2.
n − 1 ( W n − 1 ) → d N ( 0 , 1 ) . \sqrt{n-1}(W_n-1) \xrightarrow{d} \mathcal{N}(0,1). n − 1 ( W n − 1 ) d N ( 0 , 1 ) .
Recall that W n ∗ W_n^* W n ∗ is the weight of the MSA in ( K ⃗ n , ∂ ) (\vec{K}_n,\partial) ( K n , ∂ ) . It turns out the law of large numbers for W n W_n W n is an important first step towards verifying a law of large numbers for W n ∗ W_n^* W n ∗ . Thanks to that, the authors in [9 ] reduce their problem to proving that W n ∗ − W n W_n^*-W_n W n ∗ − W n converges to 0 almost surely. To start with, note that W n ≤ W n ∗ W_n\leq W_n^* W n ≤ W n ∗ , since every vertex (except ∂ \partial ∂ ) has an outgoing edge and the weight of it is greater than or equal to the weight of the minimal edge. The technique is to alter K ⃗ n 1 \vec{K}_n^1 K n 1 such that the resulting graph is a spanning arborescence of ( K ⃗ n , ∂ ) (\vec{K}_n,\partial) ( K n , ∂ ) , which is guaranteed to have weight greater than or equal to W n ∗ W_n^* W n ∗ . We refer to this procedure as “repairing”, and denote its weight by R n R_n R n . Thus, R n R_n R n is the sum of the weights of the edges added in by the modifications minus the weights of the edges removed.
In [9 ] the law of large numbers for W n ∗ W_n^* W n ∗ then follows from finding a repair procedure such that R n → 0 R_n\to0 R n → 0 almost surely. However, to show that the CLT for W n W_n W n extends to W n ∗ W_n^* W n ∗ we further need to show that n − 1 ( W n ∗ − W n ) → 0 \sqrt{n-1}(W_n^*-W_n)\to0 n − 1 ( W n ∗ − W n ) → 0 in probability, and then the extension follows from Slutsky’s theorem. The problem is thus to find a repair procedure such that
n R n → 0 \sqrt{n}R_n\to0 n R n → 0
in probability.
The following terminology will be used for the remainder of the article.
We denote by C o m p \mathrm{Comp} Comp the collection of connected components of K ⃗ n 1 \vec{K}_n^1 K n 1 .
We denote by C max \mathcal{C}^{\max} C m a x the largest connected component of K ⃗ n 1 \vec{K}_n^1 K n 1 .
We denote by C ∂ \mathcal{C}^{\partial} C ∂ the connected component containing ∂ \partial ∂ .
We denote by C y c l e max \mathrm{Cycle}_{\max} Cycle m a x the directed cycle contained in C max \mathcal{C}^{\max} C m a x .
We identify certain structural properties for the configuration K n 1 K_n^1 K n 1 , which if satisfied, admit a repair procedure yielding an arborescence of small enough weight. These properties are explicitly laid out in (2) . To summarize:
The number of connected components of K ⃗ n 1 \vec{K}_n^1 K n 1 , ∣ C o m p ∣ |\mathrm{Comp}| ∣ Comp ∣ is bounded above by C log n C\log n C log n for some constant C < ∞ C<\infty C < ∞ .
∣ C y c l e max ∣ |\mathrm{Cycle}_{\max}| ∣ Cycle m a x ∣ is bounded below and above by ∣ C max ∣ 1 2 − δ |\mathcal{C}^{\max}|^{\frac{1}{2}-\delta} ∣ C m a x ∣ 2 1 − δ and ∣ C max ∣ 1 2 + δ |\mathcal{C}^{\max}|^{\frac{1}{2}+\delta} ∣ C m a x ∣ 2 1 + δ respectively for some δ > 0 \delta>0 δ > 0 .
We have a large number of vertices u ∈ C max u\in\mathcal{C}^{\max} u ∈ C m a x such that P a s t u \mathrm{Past}_u Past u is appropriately large.
The event where these occur holds with high probability. This is precisely stated in Lemma 3.4 and a proof is presented in Section 5. An important consequence for our repair procedure is that for n n n sufficiently large (in a deterministic sense), on the good event, C ∂ ≠ C max \mathcal{C}^{\partial}\ne\mathcal{C}^{\max} C ∂ = C m a x . This is because the cycle size is large.
Once we are on the good event, the repair procedure is as follows. For illustrations on the repair steps see Figure 4 and Figure 5 .
Figure 4. Step 1 of the repair. From the vertices of the cycles of the components other than C ∂ C^{\partial} C ∂ (coloured pink), we pick the minimal outgoing edges (coloured red) to C max C^{\max} C m a x (coloured blue), add these edges and delete the edges (dotted red) which are in the cycles.
Figure 5. Top left. Step 2 of the repair. u ∗ u_{*} u ∗ is the vertex in A ⊂ C max \mathcal{A} \subset\mathcal{C}^{\max} A ⊂ C m a x from which the minimal outgoing edge (coloured red) is hitting C ∂ \mathcal{C}^{\partial} C ∂ . We add this edge and delete the red dotted edge from u ∗ u_{*} u ∗ towards the cycle. This step joins Past u ∗ \operatorname{Past}_{u_{*}} Past u ∗ (coloured purple) to C ∂ \mathcal{C}^{\partial} C ∂ (coloured pink). Top right. Step 3 of the repair. We pick the minimal outgoing edge (coloured red) from Cycle max \operatorname{Cycle}_{\max} Cycle m a x (coloured teal) to Past u ∗ ∪ C ∂ \operatorname{Past}_{u_{*}} \cup\mathcal{C}^{\partial} Past u ∗ ∪ C ∂ . Add that edge and deleted the red dotted edge in Cycle max \operatorname{Cycle}_{\max} Cycle m a x . Bottom. The spanning arborescence of ( K ⃗ n , ∂ ) (\vec{K}_{n},\partial) ( K n , ∂ ) we obtain after finishing Step 3 of the repair.
Step 1: Merge all components, except C ∂ \mathcal{C}^{\partial} C ∂ , with C max \mathcal{C}^{\max} C m a x . This is done by adding an outgoing edge from the cycle in a given component C \mathcal{C} C to any vertex in C max \mathcal{C}^{\max} C m a x , and from the vertex that now has two outgoing edges, delete the edge that leads back into the cycle. We choose the edge to be the one that minimizes the increase in weight of this repair, that is, the weight of the added edge minus the weight of the deleted edge. For brevity, we keep the name of C max \mathcal{C}^{\max} C m a x unchanged after this step.
The error accumulated in this step is bounded in Lemma 3.6 . For the new edge from C \mathcal{C} C to C max \mathcal{C}^{\max} C m a x , there are at least ∣ C max ∣ |\mathcal{C}^{\max}| ∣ C m a x ∣ many edges to choose from, the minimal edge over these having expected weight O ( ∣ C max ∣ − 1 ) O(|\mathcal{C}^{\max}|^{-1}) O ( ∣ C m a x ∣ − 1 ) . The lower bound on ∣ C max ∣ |\mathcal{C}^{\max}| ∣ C m a x ∣ follows from the upper bound on ∣ C o m p ∣ |\mathrm{Comp}| ∣ Comp ∣ via the pigeonhole principle. We then have to add the errors arising from all components apart from C ∂ \mathcal{C}^{\partial} C ∂ , yielding an overall expected error bound of O ( ∣ C max ∣ − 1 ∣ C o m p ∣ ) O(|\mathcal{C}^{\max}|^{-1}|\mathrm{Comp}|) O ( ∣ C m a x ∣ − 1 ∣ Comp ∣ ) .
At this step of the process, we have two disjoint arborescences. The obstacle now is merging C max \mathcal{C}^{\max} C m a x with C ∂ \mathcal{C}^{\partial} C ∂ by connecting a vertex in C y c l e max \mathrm{Cycle}_{\max} Cycle m a x to C ∂ \mathcal{C}^{\partial} C ∂ . The naive approach fails here. The best bounds we have are ∣ C ∂ ∣ ≥ 1 |\mathcal{C}^{\partial}|\geq1 ∣ C ∂ ∣ ≥ 1 as C ∂ \mathcal{C}^{\partial} C ∂ is going to be distributed as a Poisson(1) Galton-Watson tree as n → ∞ n\to\infty n → ∞ , and ∣ C y c l e max ∣ ≥ n 1 2 − δ |\mathrm{Cycle}_{\max}|\geq n^{\frac{1}{2}-\delta} ∣ Cycle m a x ∣ ≥ n 2 1 − δ , for some small positive δ \delta δ , implying that all we can say about the minimal repairing edge is that it has weight O ( n − 1 2 + δ ) O(n^{-\frac{1}{2}+\delta}) O ( n − 2 1 + δ ) . This does not tend to 0 when multiplied by n \sqrt{n} n . The issue is not just the quality of the bound, since in reality we can prove that ∣ C ∂ ∣ |C^{\partial}| ∣ C ∂ ∣ and ∣ C y c l e max ∣ |\mathrm{Cycle}_{\max}| ∣ Cycle m a x ∣ are of order 1 1 1 and n \sqrt{n} n respectively, so there is no hope that this repair works even with an improved lower bound. The next step therefore relies intuitively on increasing the size of the boundary component, and thus reducing the weight of the minimal edge required for connection. It is for this purpose that the notion of the pasts of the vertices in C max C^{\max} C m a x is required, as well as the fact that on the good event there are many of them with sufficiently large pasts.
Step 2: Denote by A \mathcal{A} A the set of all u u u with sufficiently large pasts in C max C^{\max} C m a x . The precise notion can be found in Definition 3.3 , with relevant quantifiers set up in (1) . For each u ∈ A u \in\mathcal{A} u ∈ A , let E ∂ ( u ) E_{\partial}(u) E ∂ ( u ) be the set of all outgoing edges from u u u to C ∂ C^{\partial} C ∂ in K ⃗ n \vec{K}_n K n . We first select, for each u ∈ A u \in\mathcal{A} u ∈ A , the edge in E ∂ ( u ) E_{\partial}(u) E ∂ ( u ) that minimizes the increase in weight obtained by replacing the current outgoing edge from u u u . We then choose the vertex u ∗ ∈ A u_* \in\mathcal{A} u ∗ ∈ A for which this minimum increase is smallest, and perform the corresponding replacement. The past of the chosen vertex, P a s t u ∗ \mathrm{Past}_{u_*} Past u ∗ , is an arborescence with boundary u ∗ u_* u ∗ . By deleting the original outgoing edge from u ∗ u_* u ∗ and adding the selected edge in E ∂ ( u ∗ ) E_{\partial}(u_*) E ∂ ( u ∗ ) , we attach P a s t u ∗ \mathrm{Past}_{u_*} Past u ∗ to C ∂ C^{\partial} C ∂ , thereby increasing the size of C ∂ C^{\partial} C ∂ . The increase in weight of this step has mean O ( ∣ A ∣ − 1 ) O(|\mathcal{A}|^{-1}) O ( ∣ A ∣ − 1 ) and is handled precisely in Lemma 3.7 .
Step 3: We pick the outgoing edge from the vertices of C y c l e max \mathrm{Cycle}_{\max} Cycle m a x to the vertices of P a s t u ∗ ∪ C ∂ \mathrm{Past}_{u_*} \cup C^{\partial} Past u ∗ ∪ C ∂ that minimizes the increase in weight of the repair. Suppose the tail of that edge is u ′ u' u ′ . We add that edge and delete the original outgoing edge emanating from u ′ u' u ′ in C y c l e max \mathrm{Cycle}_{\max} Cycle m a x in K ⃗ n 1 \vec{K}_n^1 K n 1 . This attaches C max C^{\max} C m a x to C ∂ C^{\partial} C ∂ , yielding a spanning arborescence of K ⃗ n \vec{K}_n K n with boundary ∂ \partial ∂ . The increase in weight from this step has mean O ( ∣ C y c l e max ∣ − 1 ⋅ ∣ P a s t u ∗ ∣ − 1 ) O(|\mathrm{Cycle}_{\max}|^{-1} \cdot|\mathrm{Past}_{u_*}|^{-1}) O ( ∣ Cycle m a x ∣ − 1 ⋅ ∣ Past u ∗ ∣ − 1 ) , and is precisely bounded in Lemma 3.8 . The key point is that the good event is specified such that we can ensure ∣ C y c l e max ∣ ∣ P a s t u ∗ ∣ ≫ n |\mathrm{Cycle}_{\max}||\mathrm{Past}_{u_*}| \gg\sqrt{n} ∣ Cycle m a x ∣∣ Past u ∗ ∣ ≫ n , specifically n 1 2 + ϵ n^{\frac{1}{2}+\epsilon} n 2 1 + ϵ , for any ϵ > 0 \epsilon> 0 ϵ > 0 as per (1) .
Section 3 concludes with the proof of Theorem 1.5 , modulo the proof of Lemma 3.4 . Additional structural ingredients required to prove Lemma 3.4 appear in Sections 4 and 5 respectively.
Bound on the Weight of the Repair
After exposing the minimal outgoing edge from each vertex except ∂ \partial ∂ , we are left with a directed graph that has a very precise structure. Recall, we are denoting this graph by K ⃗ n 1 \vec{K}_n^1 K n 1 .
Definition 3.1. A cycle-bounded arborescence is a pair ( M ⃗ , C ⃗ ) (\vec{M},\vec{C}) ( M , C ) , where M ⃗ \vec{M} M is a directed graph in which every vertex has exactly one outgoing edge, and C ⃗ \vec{C} C is a directed cycle in M ⃗ \vec{M} M such that the directed graph obtained by contracting all vertices of C ⃗ \vec{C} C to a single vertex ∂ C ⃗ \partial_{\vec{C}} ∂ C and deleting the resulting self-loops is an arborescence with boundary ∂ C ⃗ \partial_{\vec{C}} ∂ C .
Figure 6. Left. A cycle-bounded arborescence. Right. The arborescence with boundary ∂ C ⃗ \partial_{\vec{C}} ∂ C obtained by contracting the vertices in its cycle C ⃗ \vec{C} C .
The connected components of K ⃗ n 1 \vec{K}_n^1 K n 1 can now be completely characterized. See Figure 3 . Both of the following facts can be proved using a straightforward induction argument:
Every component C C C in K ⃗ n 1 \vec{K}_n^1 K n 1 which is not C ∂ C^{\partial} C ∂ is a cycle-bounded arborescence.
The component C ∂ C^{\partial} C ∂ is an arborescence with boundary ∂ \partial ∂ .
For individual components, the following holds.
Lemma 3.2. Consider the event that a collection of vertices U = { v 1 , v 2 , … , v m } ⊆ V n U = \{v_1, v_2, \ldots, v_m\} \subseteq V_n U = { v 1 , v 2 , … , v m } ⊆ V n not containing ∂ \partial ∂ are the vertex set of a component C C C of K ⃗ n 1 \vec{K}_n^1 K n 1 . Conditioned on this event, C C C is equal in distribution to a uniform cycle-bounded arborescence on U U U .
Sketch of proof. Let K ⃗ n ′ ′ \vec{K}_n'' K n ′′ denote the graph obtained by independently choosing an outgoing edge uniformly from every vertex except ∂ \partial ∂ . Then K ⃗ n 1 \vec{K}_n^1 K n 1 and K ⃗ n ′ ′ \vec{K}_n'' K n ′′ are equal in distribution (note we are looking only at the edges themselves, not the weights). This is because the weights under consideration are i.i.d. Exponential(1), and thus continuous, so any integer linear combination of them will not be zero almost surely (in particular, no two edges will have the same weight).
More useful structural properties of K ⃗ n 1 \vec{K}_n^1 K n 1 are proved in Sections 4 and 5. In particular, K ⃗ n 1 \vec{K}_n^1 K n 1 shares a close relationship with the so-called random mapping model, which we detail in Section 5.
Recall that we denote past of a vertex u u u in C max C^{\max} C m a x by Past u \operatorname{Past}_u Past u . We will also work with fixed ϵ , δ , η > 0 \epsilon,\delta,\eta> 0 ϵ , δ , η > 0 satisfying the following properties:
0 < δ < ϵ , max { 2 ( ϵ + δ ) , 6 δ } < 1 and 1 2 < η < 1 − ϵ + δ 2 . (1) 0 < \delta< \epsilon,\ \max\{2(\epsilon+\delta),6\delta\} < 1\ \text{and}\ \frac{1}{2} < \eta< 1-\frac{\epsilon+\delta}{2}. \tag*{(1)} 0 < δ < ϵ , max { 2 ( ϵ + δ ) , 6 δ } < 1 and 2 1 < η < 1 − 2 ϵ + δ . (1)
Definition 3.3. For the largest component C max C^{\max} C m a x , and for ϵ \epsilon ϵ fixed in agreement with (3.1), define the following random set of vertices
A ϵ : = { u ∈ C max ∖ Cycle max : ∣ C max ∣ 1 2 + ϵ ∣ Cycle max ∣ ≤ ∣ Past u ∣ ≤ 2 ∣ C max ∣ 1 2 + ϵ ∣ Cycle max ∣ } . A_\epsilon:= \left\{u \in C^{\max} \setminus\operatorname{Cycle}_{\max} : \frac{|C^{\max}|^{\frac{1}{2}+\epsilon}}{|\operatorname{Cycle}_{\max}|} \leq|\operatorname{Past}_u| \leq2\frac{|C^{\max}|^{\frac{1}{2}+\epsilon}}{|\operatorname{Cycle}_{\max}|}\right\}. A ϵ := { u ∈ C m a x ∖ Cycle m a x : ∣ Cycle m a x ∣ ∣ C m a x ∣ 2 1 + ϵ ≤ ∣ Past u ∣ ≤ 2 ∣ Cycle m a x ∣ ∣ C m a x ∣ 2 1 + ϵ } .
Recall that ∣ Comp ∣ |\operatorname{Comp}| ∣ Comp ∣ is the number of components in K ⃗ n 1 \vec{K}^{1}_{n} K n 1 . For ϵ \epsilon ϵ , δ \delta δ and η \eta η as per (1) , we will refer to the following event as good :
E ϵ , δ , η : = { ∣ Comp ∣ ≤ 11 log 2 log n , ∣ C max ∣ 1 2 − δ < ∣ Cycle max ∣ < ∣ C max ∣ 1 2 + δ , ∣ A ϵ ∣ > ( log 2 11 n log n ) η } . (2) \mathcal{E}_{\epsilon,\delta,\eta}:=\left\{|\operatorname{Comp}|\leq\frac{11}{\log2}\log n,\quad|\mathcal{C}^{\max}|^{\frac{1}{2}-\delta}<|\operatorname{Cycle}_{\max}|<|\mathcal{C}^{\max}|^{\frac{1}{2}+\delta},\quad|\mathcal{A}_{\epsilon}|>\left(\frac{\log2}{11}\frac{n}{\log n}\right)^{\eta}\right\}. \tag*{(2)} E ϵ , δ , η := { ∣ Comp ∣ ≤ log 2 11 log n , ∣ C m a x ∣ 2 1 − δ < ∣ Cycle m a x ∣ < ∣ C m a x ∣ 2 1 + δ , ∣ A ϵ ∣ > ( 11 log 2 log n n ) η } . (2)
There are two important properties that are guaranteed to hold on the good event that will be used repeatedly:
∣ C max ∣ > n log 2 11 log n |\mathcal{C}^{\max}|>\frac{n\log2}{11\log n} ∣ C m a x ∣ > 11 l o g n n l o g 2 , follows immediately using the pigeonhole principle.
C max ≠ C ∂ \mathcal{C}^{\max}\neq\mathcal{C}^{\partial} C m a x = C ∂ for n n n large enough, since we know that on E ϵ , δ , η \mathcal{E}_{\epsilon,\delta,\eta} E ϵ , δ , η , ∣ Cycle max ∣ > ( n log 2 11 log n ) 1 2 − δ > 1 |\operatorname{Cycle}_{\max}|>\left(\frac{n\log2}{11\log n}\right)^{\frac{1}{2}-\delta}>1 ∣ Cycle m a x ∣ > ( 11 l o g n n l o g 2 ) 2 1 − δ > 1 , final inequality holds so long as n log 2 > 11 log n n\log2>11\log n n log 2 > 11 log n . This allows us to ignore the case C max = C ∂ \mathcal{C}^{\max}=\mathcal{C}^{\partial} C m a x = C ∂ .
As suggested by the nomenclature, the good event E ϵ , δ , η \mathcal{E}_{\epsilon,\delta,\eta} E ϵ , δ , η is typical.
Lemma 3.4. As n → ∞ n\to\infty n → ∞ ,
P ( E ϵ , δ , η c ) = O ( ( n log n ) max { − δ , − 1 + max { ϵ + δ , 6 δ } } ) . \mathbb{P}\left(\mathcal{E}_{\epsilon,\delta,\eta}^{c}\right)=O\left(\left(\frac{n}{\log n}\right)^{\max\left\{-\delta,-1+\max\{\epsilon+\delta,6\delta\}\right\}}\right). P ( E ϵ , δ , η c ) = O ( ( log n n ) m a x { − δ , − 1 + m a x { ϵ + δ , 6 δ } } ) .
The proof will be presented in Section 5. Before we go further, let us state one useful fact about exponential distribution.
Lemma 3.5. Let X 1 , ⋯ , X n X_1,\cdots,X_n X 1 , ⋯ , X n be i.i.d. Exponential(1) random variables and X J = min 1 ≤ i ≤ n X i X_J=\min_{1\leq i\leq n}X_i X J = min 1 ≤ i ≤ n X i be the minimum among them. Then conditioned on J J J , the variables ( X i − X J ) i ≠ J (X_i-X_J)_{i\neq J} ( X i − X J ) i = J are i.i.d. Exponential(1).
Proof. Fix j ∈ { 1 , … , n } j\in\{1,\ldots,n\} j ∈ { 1 , … , n } . By the memoryless property of the exponential distribution, conditional on J = j J=j J = j and X J = x X_J=x X J = x , the random variables ( X i − X J ) i ≠ j (X_i-X_J)_{i\neq j} ( X i − X J ) i = j are independent and each has distribution Exponential(1). Their joint distribution does not depend on x x x . Integrating over X J X_J X J , conditional on J = j J=j J = j , shows that the same conditional joint distribution holds given J = j J=j J = j alone. This proves the result.
We now accumulate the errors from each of the repair steps. Note, the exposure of the minimal outgoing edge from each vertex results in a random graph K ⃗ n 1 \vec{K}^{1}_{n} K n 1 (we are ignoring the weights themselves, we are only identifying which of the edges are minimal). Knowledge of K ⃗ n 1 \vec{K}^{1}_{n} K n 1 immediately tells us whether the good event E ϵ , δ , η \mathcal{E}_{\epsilon,\delta,\eta} E ϵ , δ , η occurs or not. For notational convenience will denote by E n , E ϵ , δ , η \mathbb{E}^{n,\mathcal{E}_{\epsilon,\delta,\eta}} E n , E ϵ , δ , η the conditional expectation given K ⃗ n 1 \vec{K}^{1}_{n} K n 1 , restricted to E ϵ , δ , η \mathcal{E}_{\epsilon,\delta,\eta} E ϵ , δ , η :
E n , E ϵ , δ , η ( X ) : = E ( X 1 E ϵ , δ , η ∣ K ⃗ n 1 ) = 1 E ϵ , δ , η E ( X ∣ K ⃗ n 1 ) . \mathbb{E}^{n,\mathcal{E}_{\epsilon,\delta,\eta}}(X):=\mathbb{E}(X\mathbf{1}_{\mathcal{E}_{\epsilon,\delta,\eta}}\mid\vec{K}^{1}_{n})=\mathbf{1}_{\mathcal{E}_{\epsilon,\delta,\eta}}\mathbb{E}(X\mid\vec{K}^{1}_{n}). E n , E ϵ , δ , η ( X ) := E ( X 1 E ϵ , δ , η ∣ K n 1 ) = 1 E ϵ , δ , η E ( X ∣ K n 1 ) .
Lemma 3.6. Let K ⃗ n 2 \vec{K}^{2}_{n} K n 2 denote the graph obtained after the completion of Step 1. Note, there are only two components: C ∂ \mathcal{C}^{\partial} C ∂ and C max \mathcal{C}^{\max} C m a x . Let W n 1 W^{1}_{n} W n 1 denote the weight of the edges so obtained. Then
0 ≤ ( W n 1 − W n ) 1 E ϵ , δ , η ≤ R n 1 , where E ( R n 1 ) = O ( ( log n ) 2 n ) . 0\leq(W^{1}_{n}-W_{n})\mathbf{1}_{\mathcal{E}_{\epsilon,\delta,\eta}}\leq R^{1}_{n},\quad\text{where }\mathbb{E}(R^{1}_{n})=O\left(\frac{(\log n)^{2}}{n}\right). 0 ≤ ( W n 1 − W n ) 1 E ϵ , δ , η ≤ R n 1 , where E ( R n 1 ) = O ( n ( log n ) 2 ) .
Proof. We condition on K ⃗ n 1 \vec{K}^{1}_{n} K n 1 and assume that E ϵ , δ , η \mathcal{E}_{\epsilon,\delta,\eta} E ϵ , δ , η occurs. Let C i \mathcal{C}_{i} C i be a component of K ⃗ n 1 \vec{K}^{1}_{n} K n 1 which is neither C ∂ \mathcal{C}^{\partial} C ∂ nor C max \mathcal{C}^{\max} C m a x . Let Cycle i \operatorname{Cycle}_{i} Cycle i be the unique cycle in C i \mathcal{C}_{i} C i , which is of size at least 2 since our vertices do not have self-loops. Let E max ( u ) E_{\max}(u) E m a x ( u ) denote the collection of edges with tail u ∈ Cycle i u\in\operatorname{Cycle}_{i} u ∈ Cycle i and head in C max \mathcal{C}^{\max} C m a x , and let e ⃗ ∗ ( u ) \vec{e}_{*}(u) e ∗ ( u ) denote the existing outgoing edge from u u u in K ⃗ n 1 \vec{K}^{1}_{n} K n 1 , in particular the minimal edge at u u u . Define
e ⃗ i + ( u ) : = argmin e ∈ E max ( u ) { Y e ⃗ e − Y e ⃗ ∗ ( u ) } \vec{e}^{+}_{i}(u):=\underset{e\in E_{\max}(u)}{\operatorname{argmin}}\{Y^{e}_{\vec{e}}-Y_{\vec{e}_{*}(u)}\} e i + ( u ) := e ∈ E m a x ( u ) argmin { Y e e − Y e ∗ ( u ) }
and
e ⃗ i − : = e ↑ ( u i ∗ ) where u i ∗ : = argmin u ∈ Cycle i { Y e ⃗ i + ( u ) − Y e ⃗ ∗ ( u ) } . \vec{e}^{-}_{i}:=e^{\uparrow}(u_{i*})\text{ where }u_{i*}:=\underset{u\in\operatorname{Cycle}_{i}}{\operatorname{argmin}}\{Y_{\vec{e}^{+}_{i}(u)}-Y_{\vec{e}_{*}(u)}\}. e i − := e ↑ ( u i ∗ ) where u i ∗ := u ∈ Cycle i argmin { Y e i + ( u ) − Y e ∗ ( u ) } .
Define δ i : = Y e ⃗ i + ( u i ∗ ) − Y e ⃗ ∗ ( u i ∗ ) \delta_i:=Y_{\vec{e}^{+}_{i}(u_{i*})}-Y_{\vec{e}_{*}(u_{i*})} δ i := Y e i + ( u i ∗ ) − Y e ∗ ( u i ∗ ) . Note, applying Lemma 3.5 , and using the fact that the minimum of m m m exponential variables is equal in distribution to an exponential random variable with mean m − 1 m^{-1} m − 1 , we obtain that δ i \delta_i δ i is an exponential random variable with mean given by ∣ C max ∣ − 1 ⋅ ∣ Cycle i ∣ − 1 |C^{\max}|^{-1}\cdot|\operatorname{Cycle}_i|^{-1} ∣ C m a x ∣ − 1 ⋅ ∣ Cycle i ∣ − 1 . Since we are on E ε , δ , η E_{\varepsilon,\delta,\eta} E ε , δ , η , the pigeonhole principle gives us ∣ C max ∣ > n log 2 11 log n |C^{\max}|>\frac{n\log2}{11\log n} ∣ C m a x ∣ > 11 l o g n n l o g 2 . We obtain
∣ Cycle i ∣ ⋅ ∣ C max ∣ ≥ 2 ⋅ log 2 11 ⋅ n log n . (3) |\operatorname{Cycle}_i|\cdot|C^{\max}|\ge2\cdot\frac{\log2}{11}\cdot\frac{n}{\log n}. \tag*{(3)} ∣ Cycle i ∣ ⋅ ∣ C m a x ∣ ≥ 2 ⋅ 11 log 2 ⋅ log n n . (3)
Thus, E n , E , δ , η ( δ i ) ≤ 11 log n 2 n log 2 \mathbb{E}^{n,\mathcal{E},\delta,\eta}(\delta_i)\le\frac{11\log n}{2n\log2} E n , E , δ , η ( δ i ) ≤ 2 n l o g 2 11 l o g n . Since there are at most 11 log 2 log n \frac{11}{\log2}\log n l o g 2 11 log n many components, this procedure has to be repeated at most 11 log 2 log n \frac{11}{\log2}\log n l o g 2 11 log n times, and the error accumulated is the sum of δ i \delta_i δ i over all components. Thus,
0 ≤ ( W n 1 − W n ) 1 E ε , δ , η ≤ R n 1 : = ( ∑ i δ i ) 1 E ε , δ , η . 0\le(W_n^1-W_n)\mathbf{1}_{E_{\varepsilon,\delta,\eta}}\le R_n^1:=\left(\sum_i\delta_i\right)\mathbf{1}_{E_{\varepsilon,\delta,\eta}}. 0 ≤ ( W n 1 − W n ) 1 E ε , δ , η ≤ R n 1 := ( i ∑ δ i ) 1 E ε , δ , η .
Clearly,
E n , E , δ , η ( R n 1 ) = ∑ i E n , E , δ , η ( δ i ) ≤ 11 log n 2 n log 2 11 log 2 log n = O ( ( log n ) 2 n ) . \mathbb{E}^{n,\mathcal{E},\delta,\eta}(R_n^1)=\sum_i\mathbb{E}^{n,\mathcal{E},\delta,\eta}(\delta_i)\le\frac{11\log n}{2n\log2}\frac{11}{\log2}\log n=O\left(\frac{(\log n)^2}{n}\right). E n , E , δ , η ( R n 1 ) = i ∑ E n , E , δ , η ( δ i ) ≤ 2 n log 2 11 log n log 2 11 log n = O ( n ( log n ) 2 ) .
Taking expectation again, we conclude.
Next, we bound the weight of Step 2, in which we grow the component of ∂ \partial ∂ by attaching a large arborescence to it.
Lemma 3.7. Let K ⃗ n 3 \vec{K}_n^3 K n 3 denote the graph obtained after the completion of Step 2. Let W n 2 W_n^2 W n 2 denote the sum of weights of edges in K ⃗ n 3 \vec{K}_n^3 K n 3 . Then
0 ≤ ( W n 2 − W n 1 ) 1 E ε , δ , η ≤ R n 2 , where E ( R n 2 ) = O ( ( n log n ) − η ) . 0\le(W_n^2-W_n^1)\mathbf{1}_{E_{\varepsilon,\delta,\eta}}\le R_n^2,\qquad\text{where }\mathbb{E}(R_n^2)=O\left(\left(\frac{n}{\log n}\right)^{-\eta}\right). 0 ≤ ( W n 2 − W n 1 ) 1 E ε , δ , η ≤ R n 2 , where E ( R n 2 ) = O ( ( log n n ) − η ) . Proof. We condition on K ⃗ n 1 \vec{K}_n^1 K n 1 and assume that E ε , δ , η E_{\varepsilon,\delta,\eta} E ε , δ , η occurs. For a given vertex u u u , let the existing edge in K ⃗ n 1 \vec{K}_n^1 K n 1 with tail u u u be denoted by e ⃗ ∗ ( u ) \vec e_*(u) e ∗ ( u ) . Consider the collection of all vertices u ∈ A u\in\mathcal{A} u ∈ A , and the collection of all edges from u u u to C ∂ C^\partial C ∂ in K ⃗ n \vec{K}_n K n . Denote this collection E ∂ ( u ) E_\partial(u) E ∂ ( u ) and define
e ⃗ † ( u ) = argmin { Y e ⃗ − Y e ⃗ ∗ : e ⃗ ∈ E ∂ ( u ) } . \vec e^\dagger(u)=\operatorname*{argmin}\{Y_{\vec e}-Y_{\vec e_*}:\vec e\in E_\partial(u)\}. e † ( u ) = argmin { Y e − Y e ∗ : e ∈ E ∂ ( u )} . Note, ∣ E ∂ ( u ) ∣ = ∣ C ∂ ∣ |E_\partial(u)|=|C^\partial| ∣ E ∂ ( u ) ∣ = ∣ C ∂ ∣ , so by Lemma 3.5 { Y e ⃗ † ( u ) − Y e ⃗ ∗ ( u ) } u ∈ A ε \{Y_{\vec e^\dagger(u)}-Y_{\vec e_*(u)}\}_{u\in A_\varepsilon} { Y e † ( u ) − Y e ∗ ( u ) } u ∈ A ε are a family of i.i.d. exponential random variables with mean ∣ C ∂ ∣ − 1 |C^\partial|^{-1} ∣ C ∂ ∣ − 1 . Next, consider
u ∗ : = argmin { Y e ⃗ † ( u ) − Y e ⃗ ∗ ( u ) : u ∈ A } . u_*:=\operatorname*{argmin}\{Y_{\vec e^\dagger(u)}-Y_{\vec e_*(u)}:u\in A\}. u ∗ := argmin { Y e † ( u ) − Y e ∗ ( u ) : u ∈ A } . Note, as the minimum of ∣ A ∣ |A| ∣ A ∣ many independent exponential random variables with mean ∣ C ∂ ∣ − 1 |C^\partial|^{-1} ∣ C ∂ ∣ − 1 , again by Lemma 3.5 , Y e ⃗ † ( u ∗ ) − Y e ⃗ ∗ ( u ∗ ) Y_{\vec e^\dagger(u_*)}-Y_{\vec e_*(u_*)} Y e † ( u ∗ ) − Y e ∗ ( u ∗ ) is exponential with mean ∣ A ∣ − 1 ∣ C ∂ ∣ − 1 ≤ ( n log 2 / 11 log n ) − η |A|^{-1}|C^\partial|^{-1}\le(n\log2/11\log n)^{-\eta} ∣ A ∣ − 1 ∣ C ∂ ∣ − 1 ≤ ( n log 2/11 log n ) − η . Finally,
0 ≤ ( W n 2 − W n 1 ) 1 E ε , δ , η ≤ ( Y e ⃗ † ( u ∗ ) − Y e ⃗ ∗ ( u ∗ ) ) 1 E ε , δ , η = : R n 2 . 0\le(W_n^2-W_n^1)\mathbf{1}_{E_{\varepsilon,\delta,\eta}}\le(Y_{\vec e^\dagger(u_*)}-Y_{\vec e_*(u_*)})\mathbf{1}_{E_{\varepsilon,\delta,\eta}}=:R_n^2. 0 ≤ ( W n 2 − W n 1 ) 1 E ε , δ , η ≤ ( Y e † ( u ∗ ) − Y e ∗ ( u ∗ ) ) 1 E ε , δ , η =: R n 2 . The final step is identical to the previous lemma.
In the following lemma we bound the weight of the last repair step, in which we connect Cycle max \operatorname{Cycle}_{\max} Cycle m a x to the component of ∂ \partial ∂ , which is now large enough.
Lemma 3.8. Let K ⃗ n 4 \vec{K}_n^4 K n 4 denote the arborescence obtained after the completion of Step 3. Then
0 < ( W n 3 − W n 2 ) 1 E ε , δ , η ≤ R n 3 , where E ( R n 3 ) = O ( ( n log n ) − 1 2 − ε ) . 0<(W_n^3-W_n^2)\mathbf{1}_{E_{\varepsilon,\delta,\eta}}\le R_n^3,\qquad\text{where }\mathbb{E}(R_n^3)=O\left(\left(\frac{n}{\log n}\right)^{-\frac{1}{2}-\varepsilon}\right). 0 < ( W n 3 − W n 2 ) 1 E ε , δ , η ≤ R n 3 , where E ( R n 3 ) = O ( ( log n n ) − 2 1 − ε ) . Proof. We condition on K ⃗ n 1 \vec{K}_n^1 K n 1 and assume that E ε , δ , η E_{\varepsilon,\delta,\eta} E ε , δ , η occurs. We take the edge from the vertices of Cycle max \operatorname{Cycle}_{\max} Cycle m a x to Past u ∗ ∪ C ∂ \operatorname{Past}_{u_*}\cup C^\partial Past u ∗ ∪ C ∂ that minimizes the repair cost. By an argument identical to that of Lemma 3.7 , we find the repair cost is given by an exponential random variable with mean
∣ Past u ∗ ∪ C ∂ ∣ − 1 ∣ Cycle max ∣ − 1 ≤ ∣ C max ∣ − 1 2 − ε ≤ ( log 2 11 ⋅ n log n ) − 1 2 − ε , |\operatorname{Past}_{u_*}\cup C^\partial|^{-1}|\operatorname{Cycle}_{\max}|^{-1}\le|C^{\max}|^{-\frac{1}{2}-\varepsilon}\le\left(\frac{\log2}{11}\cdot\frac{n}{\log n}\right)^{-\frac{1}{2}-\varepsilon}, ∣ Past u ∗ ∪ C ∂ ∣ − 1 ∣ Cycle m a x ∣ − 1 ≤ ∣ C m a x ∣ − 2 1 − ε ≤ ( 11 log 2 ⋅ log n n ) − 2 1 − ε , which follows from Lemma 3.5 . The remainder of the argument is identical to the previous two lemmas.
To extend to the general class of weights as per the criteria defined in Theorem 1.5 , all we need to do is establish an analogue for Lemma 3.5 . The steps are then identical. This analogue is presented in § 8 , in particular Lemma 6.1 . We are now in a position to prove the CLT, modulo Lemma 3.4 .
Proof of Theorem 1.5 in the exponential case. As demonstrated in § 4 , proving the CLT boils down to a verification that n ( W n ∗ − W n ) \sqrt{n}(W_n^* - W_n) n ( W n ∗ − W n ) converges to 0 in probability. For a fixed ε ′ > 0 \varepsilon' > 0 ε ′ > 0 let B n : = { n ( W n ∗ − W n ) > ε ′ } B_n := \{\sqrt{n}(W_n^* - W_n) > \varepsilon'\} B n := { n ( W n ∗ − W n ) > ε ′ } be the event whose probability we want to prove goes to 0. Note,
B n = ( B n ∩ E ε , δ , η ) ∪ ( B n ∩ E ε , δ , η c ) , B_n = (B_n \cap E_{\varepsilon,\delta,\eta}) \cup(B_n \cap E_{\varepsilon,\delta,\eta}^{c}), B n = ( B n ∩ E ε , δ , η ) ∪ ( B n ∩ E ε , δ , η c ) ,
which implies, by Lemma 3.4 ,
P ( B n ) = P ( B n ∩ E ε , δ , η ) + P ( B n ∩ E ε , δ , η c ) ≤ P ( B n ∩ E ε , δ , η ) + P ( E ε , δ , η c ) ≤ P ( B n ∩ E ε , δ , η ) + O ( ( n log n ) max { − δ , − 1 + max { ε + δ , 6 δ } } ) . \begin{aligned}
\mathbb{P}(B_n) = \mathbb{P}(B_n \cap E_{\varepsilon,\delta,\eta}) + \mathbb{P}(B_n \cap E_{\varepsilon,\delta,\eta}^{c}) \\
&\leq\mathbb{P}(B_n \cap E_{\varepsilon,\delta,\eta}) + \mathbb{P}(E_{\varepsilon,\delta,\eta}^{c}) \\
&\leq\mathbb{P}(B_n \cap E_{\varepsilon,\delta,\eta}) + O\left(\left(\frac{n}{\log n}\right)^{\max\{-\delta,-1+\max\{\varepsilon+\delta,6\delta\}\}}\right).
\end{aligned} P ( B n ) = P ( B n ∩ E ε , δ , η ) + P ( B n ∩ E ε , δ , η c ) ≤ P ( B n ∩ E ε , δ , η ) + P ( E ε , δ , η c ) ≤ P ( B n ∩ E ε , δ , η ) + O ( ( log n n ) m a x { − δ , − 1 + m a x { ε + δ , 6 δ }} ) .
To show that P ( B n ∩ E ε , δ , η ) \mathbb{P}(B_n \cap E_{\varepsilon,\delta,\eta}) P ( B n ∩ E ε , δ , η ) goes to 0, we showed that ( W n ∗ − W n ) 1 E ε , δ , η (W_n^* - W_n)1_{E_{\varepsilon,\delta,\eta}} ( W n ∗ − W n ) 1 E ε , δ , η is upper bounded by a random variable R n R_n R n , where n R n → 0 \sqrt{n}R_n \to0 n R n → 0 in probability. Note that, at the end of Step 3, we have an arborescence (see Figure 5 ) whose total weight W n 3 W_n^3 W n 3 upper bounds W n ∗ W_n^* W n ∗ . Thus,
0 < ( W n ∗ − W n ) 1 E ε , δ , η ≤ ( W n 3 − W n ) 1 E ε , δ , η ≤ R n 1 + R n 2 + R n 3 , 0 < (W_n^* - W_n)1_{E_{\varepsilon,\delta,\eta}} \leq(W_n^3 - W_n)1_{E_{\varepsilon,\delta,\eta}} \leq R_n^1 + R_n^2 + R_n^3, 0 < ( W n ∗ − W n ) 1 E ε , δ , η ≤ ( W n 3 − W n ) 1 E ε , δ , η ≤ R n 1 + R n 2 + R n 3 ,
where R n 1 R_n^1 R n 1 , R n 2 R_n^2 R n 2 and R n 3 R_n^3 R n 3 are as per Lemmas 3.6 , 3.7 and 3.8 respectively. Define R n R_n R n to be the sum of the three error terms. By the prior three lemmas,
E ( n R n ) = O ( ( log n ) 1 2 + max { ε , η − 1 2 } n min { ε , η − 1 2 } ) = o ( 1 ) . \mathbb{E}(\sqrt{n}R_n) = O\left(\frac{(\log n)^{\frac{1}{2}+\max\{\varepsilon,\eta-\frac{1}{2}\}}}{n^{\min\{\varepsilon,\eta-\frac{1}{2}\}}}\right) = o(1). E ( n R n ) = O ( n m i n { ε , η − 2 1 } ( log n ) 2 1 + m a x { ε , η − 2 1 } ) = o ( 1 ) .
Notice that the leading order error term comes from the last two steps (Lemmas 3.7 and 3.8 ). Thus, n ( W n ∗ − W n ) → 0 \sqrt{n}(W_n^* - W_n) \to0 n ( W n ∗ − W n ) → 0 in probability. Since n ( W n − 1 ) → N ( 0 , 1 ) \sqrt{n}(W_n - 1) \to\mathcal{N}(0,1) n ( W n − 1 ) → N ( 0 , 1 ) in distribution, by Slutsky’s theorem n ( W n ∗ − 1 ) \sqrt{n}(W_n^* - 1) n ( W n ∗ − 1 ) converges to the same limit in distribution.
Structure of the largest component of Directed Complete Graph
We need to understand some structural properties of C max C^{\max} C m a x . If we condition on the event that a specific subcollection of vertices U ⊆ V n U \subseteq V_n U ⊆ V n constitutes C max C^{\max} C m a x , then C max C^{\max} C m a x is equal in distribution to a uniformly sampled cycle-bounded arborescence on those vertices. The previous claim follows from Lemma 3.2 . Going one step further, conditioned on the event that the vertices constituting Cycle max \operatorname{Cycle}_{\max} Cycle m a x are U ~ ⊆ U \widetilde{U} \subseteq U U ⊆ U , then the distribution of the remainder C max ∖ Cycle max C^{\max} \setminus\operatorname{Cycle}_{\max} C m a x ∖ Cycle m a x is uniformly chosen amongst all forests on U U U , rooted at the vertices of U ~ \widetilde{U} U . The edges are then oriented towards the roots.
For a given vertex u u u , we now calculate the distribution of the size of its past ∣ Past u ∣ |\operatorname{Past}_u| ∣ Past u ∣ . We will denote by P U , U ~ \mathbb{P}^{U,\widetilde{U}} P U , U and E U , U ~ \mathbb{E}^{U,\widetilde{U}} E U , U the conditional probability and conditional expectation with respect to the event that the vertex sets of C max C^{\max} C m a x and Cycle max \operatorname{Cycle}_{\max} Cycle m a x are U U U and U ~ \widetilde{U} U respectively. Moreover, let ∣ U ∣ = m |U| = m ∣ U ∣ = m and ∣ U ~ ∣ = k |\widetilde{U}| = k ∣ U ∣ = k .
Lemma 4.1. For any u ∈ U ∖ U ~ u \in U \setminus\widetilde{U} u ∈ U ∖ U ,
P U , U ~ ( ∣ Past u ∣ = l ) = ( m − k − 1 l − 1 ) l l − 2 ( m − l ) m − l − k m m − k − 1 , \mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u| = l) = \binom{m-k-1}{l-1}\frac{l^{l-2}(m-l)^{m-l-k}}{m^{m-k-1}}, P U , U ( ∣ Past u ∣ = l ) = ( l − 1 m − k − 1 ) m m − k − 1 l l − 2 ( m − l ) m − l − k ,
1 ≤ l ≤ m − k 1 \leq l \leq m-k 1 ≤ l ≤ m − k .
Proof. The number of rooted forests on m m m vertices with k k k designated roots is given by k m m − k − 1 k m^{m-k-1} k m m − k − 1 , by Cayley’s formula. Next, choose the descendants: Past u \operatorname{Past}_u Past u cannot contain any of the designated roots. Since u u u is already in Past u \operatorname{Past}_u Past u , we must choose l − 1 l-1 l − 1 additional vertices from the remaining m − k − 1 m-k-1 m − k − 1 available non-roots. There are ( m − k − 1 l − 1 ) \binom{m-k-1}{l-1} ( l − 1 m − k − 1 ) ways to do this. By Cayley’s formula, there are l l − 2 l^{l-2} l l − 2 distinct trees on these l l l vertices. When we set u u u as the root of this subtree, all edges are uniquely directed toward u u u . Next, we need to work with the ancestors of u u u . We must have exactly one edge pointing to a vertex outside of Past u \operatorname{Past}_u Past u (there are m − l m-l m − l such vertices). Thus, there are m − l m-l m − l choices for the parent of u u u . Finally, the remaining m − l m-l m − l vertices must form a valid directed forest pointing toward the k k k roots. No vertex outside Past u \operatorname{Past}_u Past u can be connected to Past u \operatorname{Past}_u Past u (otherwise it would be part of Past u \operatorname{Past}_u Past u ). Using our forest-counting formula, the number of ways to arrange the remaining vertices is k ( m − l ) m − l − k − 1 k(m-l)^{m-l-k-1} k ( m − l ) m − l − k − 1 .
A more advanced version of the same lemma will be required for two-point estimates. In particular, the joint distribution of the descendant trees for two distinct vertices in a forest can be explicitly calculated. There are however three sub cases to be considered.
Lemma 4.2. Let u u u and v v v be non-root vertices in U U U (that is, u , v ∈ U ∖ U ~ u,v \in U \setminus\widetilde{U} u , v ∈ U ∖ U ). Then
P U , U ~ ( ∣ Past u ∣ = l 1 , ∣ Past v ∣ = l 2 , B ) = { ( m − k − 2 ) ! l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 ( l 1 − 1 ) ! ( l 2 − 1 ) ! ( m − k − l 1 − l 2 ) ! m m − k − 1 , B = { Past u ∩ Past v = ∅ } , ( m − k − 2 ) ! l 2 l 2 − 2 ( l 1 − l 2 ) l 1 − l 2 − 1 ( m − l 1 ) m − l 1 − k ( l 2 − 1 ) ! ( l 1 − l 2 − 1 ) ! ( m − k − l 1 ) ! m m − k − 1 , B = { v ∈ Past u } , ( m − k − 2 ) ! l 1 l 1 − 2 ( l 2 − l 1 ) l 2 − l 1 − 1 ( m − l 2 ) m − l 2 − k ( l 1 − 1 ) ! ( l 2 − l 1 − 1 ) ! ( m − k − l 2 ) ! m m − k − 1 , B = { u ∈ Past v } . \mathbb{P}^{U,\widetilde{U}}\left(\left|\operatorname{Past}_u\right|=l_1,\left|\operatorname{Past}_v\right|=l_2,\mathcal{B}\right)=\begin{cases}
\dfrac{(m-k-2)!l_1^{l_1-2}l_2^{l_2-2}(m-l_1-l_2)^{m-l_1-l_2-k+1}}{(l_1-1)!(l_2-1)!(m-k-l_1-l_2)!m^{m-k-1}}, & \mathcal{B}=\{\operatorname{Past}_u\cap\operatorname{Past}_v=\varnothing\},\\[6pt]
\dfrac{(m-k-2)!l_2^{l_2-2}(l_1-l_2)^{l_1-l_2-1}(m-l_1)^{m-l_1-k}}{(l_2-1)!(l_1-l_2-1)!(m-k-l_1)!m^{m-k-1}}, & \mathcal{B}=\{v\in\operatorname{Past}_u\},\\[6pt]
\dfrac{(m-k-2)!l_1^{l_1-2}(l_2-l_1)^{l_2-l_1-1}(m-l_2)^{m-l_2-k}}{(l_1-1)!(l_2-l_1-1)!(m-k-l_2)!m^{m-k-1}}, & \mathcal{B}=\{u\in\operatorname{Past}_v\}.
\end{cases} P U , U ( ∣ Past u ∣ = l 1 , ∣ Past v ∣ = l 2 , B ) = ⎩ ⎨ ⎧ ( l 1 − 1 )! ( l 2 − 1 )! ( m − k − l 1 − l 2 )! m m − k − 1 ( m − k − 2 )! l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 , ( l 2 − 1 )! ( l 1 − l 2 − 1 )! ( m − k − l 1 )! m m − k − 1 ( m − k − 2 )! l 2 l 2 − 2 ( l 1 − l 2 ) l 1 − l 2 − 1 ( m − l 1 ) m − l 1 − k , ( l 1 − 1 )! ( l 2 − l 1 − 1 )! ( m − k − l 2 )! m m − k − 1 ( m − k − 2 )! l 1 l 1 − 2 ( l 2 − l 1 ) l 2 − l 1 − 1 ( m − l 2 ) m − l 2 − k , B = { Past u ∩ Past v = ∅ } , B = { v ∈ Past u } , B = { u ∈ Past v } .
Proof. Note the following trichotomy, we either have Past v ∩ Past u = ∅ \operatorname{Past}_v\cap\operatorname{Past}_u=\varnothing Past v ∩ Past u = ∅ , Past u ⊂ Past v \operatorname{Past}_u\subset\operatorname{Past}_v Past u ⊂ Past v if u ∈ Past v u\in\operatorname{Past}_v u ∈ Past v , or Past v ⊂ Past u \operatorname{Past}_v\subset\operatorname{Past}_u Past v ⊂ Past u if v ∈ Past u v\in\operatorname{Past}_u v ∈ Past u . There are no other possibilities. We also note that we must have l 1 + l 2 ≤ m − k l_1+l_2\le m-k l 1 + l 2 ≤ m − k for the disjoint case, 1 ≤ l 2 < l 1 ≤ m − k 1\le l_2<l_1\le m-k 1 ≤ l 2 < l 1 ≤ m − k for the case Past v ⊂ Past u \operatorname{Past}_v\subset\operatorname{Past}_u Past v ⊂ Past u , and the corresponding reversed expression for the final case in our trichotomy.
Case 1. We partition the m − k − 2 m-k-2 m − k − 2 available non-root vertices into Past u \operatorname{Past}_u Past u and Past v \operatorname{Past}_v Past v , leaving m − k − l 1 − l 2 m-k-l_1-l_2 m − k − l 1 − l 2 non-roots outside both. For the vertices constituting each descendant tree, there are ( m − k − 2 l 1 − 1 ) \binom{m-k-2}{l_1-1} ( l 1 − 1 m − k − 2 ) and ( m − k − l 1 − 1 l 2 − 1 ) \binom{m-k-l_1-1}{l_2-1} ( l 2 − 1 m − k − l 1 − 1 ) choices respectively (for vertices other than u u u and v v v ). Multiplying and simplifying yields the prefactor
( m − k − 2 ) ! ( l 1 − 1 ) ! ( l 2 − 1 ) ! ( m − k − l 1 − l 2 ) ! \frac{(m-k-2)!}{(l_1-1)!(l_2-1)!(m-k-l_1-l_2)!} ( l 1 − 1 )! ( l 2 − 1 )! ( m − k − l 1 − l 2 )! ( m − k − 2 )!
For each of these pasts, there are l 1 l 1 − 2 l_1^{l_1-2} l 1 l 1 − 2 and l 2 l 2 − 2 l_2^{l_2-2} l 2 l 2 − 2 possibilities respectively. Next, u u u and v v v attach themselves to the forest spanned by the remaining m − l 1 − l 2 m-l_1-l_2 m − l 1 − l 2 vertices, meaning they independently select parents among these, yielding ( m − l 1 − l 2 ) 2 (m-l_1-l_2)^2 ( m − l 1 − l 2 ) 2 ways of doing so. Then, apply Cayley’s formula to calculate the number of forests spanned by the remainder, which is k ( m − l 1 − l 2 ) m − l 1 − l 2 − k − 1 k(m-l_1-l_2)^{m-l_1-l_2-k-1} k ( m − l 1 − l 2 ) m − l 1 − l 2 − k − 1 . Finally divide by k m m − k − 1 km^{m-k-1} k m m − k − 1 , which is the total number of labeled rooted forests on m m m vertices and k k k designated roots.
Case 2. We select the l 2 − 1 l_2-1 l 2 − 1 vertices for Past v \operatorname{Past}_v Past v and the l 1 − l 2 − 1 l_1-l_2-1 l 1 − l 2 − 1 vertices that belong to Past u \operatorname{Past}_u Past u but not Past v \operatorname{Past}_v Past v . There are ( m − k − 2 l 2 − 1 ) \binom{m-k-2}{l_2-1} ( l 2 − 1 m − k − 2 ) and ( m − k − l 2 − 1 l 1 − l 2 − 1 ) \binom{m-k-l_2-1}{l_1-l_2-1} ( l 1 − l 2 − 1 m − k − l 2 − 1 ) ways of doing so respectively. The inner subtree Past v \operatorname{Past}_v Past v has l 2 l 2 − 2 l_2^{l_2-2} l 2 l 2 − 2 configurations. The vertex v v v must then connect to one of the l 1 − l 2 l_1-l_2 l 1 − l 2 vertices in the rest of Past u \operatorname{Past}_u Past u , with ( l 1 − l 2 ) (l_1-l_2) ( l 1 − l 2 ) ways of doing so. Finally, u u u must connect to the outside forest, with ( m − l 1 ) (m-l_1) ( m − l 1 ) ways of doing so. Cayley’s formula then tells us that the outside forest has k ( m − l 1 ) m − l 1 − k − 1 k(m-l_1)^{m-l_1-k-1} k ( m − l 1 ) m − l 1 − k − 1 many configurations to choose from.
We have all the tools required to examine the occurrence of vertices in C max \mathcal{C}^{\max} C m a x with large pasts. Note, conditioned on the event that the vertices of C max \mathcal{C}^{\max} C m a x are a given U ⊂ V n U\subset V_n U ⊂ V n , with ∣ U ∣ = m |U|=m ∣ U ∣ = m , and the vertices constituting Cycle max \operatorname{Cycle}_{\max} Cycle m a x are a given U ~ \widetilde{U} U with ∣ U ~ ∣ = k |\widetilde{U}|=k ∣ U ∣ = k , we can write
∣ A ∣ = ∑ u ∈ U ∖ U ~ 1 ( m 1 3 + ϵ k ≤ ∣ Past u ∣ ≤ 2 m 1 2 + ϵ k ) . (4) |\mathcal{A}|=\sum_{u\in U\setminus\widetilde{U}}\mathbf{1}\left(\frac{m^{\frac{1}{3}+\epsilon}}{k}\leq\left|\operatorname{Past}_u\right|\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}\right). \tag*{(4)} ∣ A ∣ = u ∈ U ∖ U ∑ 1 ( k m 3 1 + ϵ ≤ ∣ Past u ∣ ≤ k 2 m 2 1 + ϵ ) . (4)
Lemma 4.3. For m m m large, and m 1 2 − δ ≤ k ≤ m 1 2 + δ m^{\frac{1}{2}-\delta} \le k \le m^{\frac{1}{2}+\delta} m 2 1 − δ ≤ k ≤ m 2 1 + δ , ϵ \epsilon ϵ and δ \delta δ as per (1) ,
E U , U ~ ( ∣ A ∣ ) = Θ ( k m 3 4 − ϵ 2 ) . \mathbb{E}^{U,\widetilde{U}}(|A|)=\Theta\left(\sqrt{k}m^{\frac{3}{4}-\frac{\epsilon}{2}}\right). E U , U ( ∣ A ∣ ) = Θ ( k m 4 3 − 2 ϵ ) .
Proof. Note that from (4) we have
E U , U ~ ( ∣ A ∣ ) = ∑ u ∈ U ∖ U ~ P U , U ~ ( m 1 2 + ϵ k ≤ ∣ Past u ∣ ≤ 2 m 1 2 + ϵ k ) = ( m − k ) P U , U ~ ( m 1 2 + ϵ k ≤ ∣ Past u ∣ ≤ 2 m 1 2 + ϵ k ) . \mathbb{E}^{U,\widetilde{U}}(|A|)=\sum_{u\in U\setminus\widetilde{U}}\mathbb{P}^{U,\widetilde{U}}\left(\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq|\operatorname{Past}_u|\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}\right)=(m-k)\mathbb{P}^{U,\widetilde{U}}\left(\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq|\operatorname{Past}_u|\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}\right). E U , U ( ∣ A ∣ ) = u ∈ U ∖ U ∑ P U , U ( k m 2 1 + ϵ ≤ ∣ Past u ∣ ≤ k 2 m 2 1 + ϵ ) = ( m − k ) P U , U ( k m 2 1 + ϵ ≤ ∣ Past u ∣ ≤ k 2 m 2 1 + ϵ ) .
Thus, we need lower and upper bounds of the probability above. Note that
P U , U ~ ( m 1 2 + ϵ k ≤ ∣ Past u ∣ ≤ 2 m 1 2 + ϵ k ) = ∑ m 1 2 + ϵ k ≤ l ≤ 2 m 1 2 + ϵ k P U , U ~ ( ∣ Past u ∣ = l ) . \mathbb{P}^{U,\widetilde{U}}\left(\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq|\operatorname{Past}_u|\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}\right)=\sum_{\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq l\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}}\mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u|=l). P U , U ( k m 2 1 + ϵ ≤ ∣ Past u ∣ ≤ k 2 m 2 1 + ϵ ) = k m 2 1 + ϵ ≤ l ≤ k 2 m 2 1 + ϵ ∑ P U , U ( ∣ Past u ∣ = l ) .
If we expand the factorial terms in the formula from Lemma 4.1, we can express the probability of the number of vertices in Past u \operatorname{Past}_u Past u being l l l as
P U , U ~ ( ∣ Past u ∣ = l ) = l l − 2 ( l − 1 ) ! ∏ j = 1 l − 1 ( 1 − k + j m ) ( 1 − l m ) m − l − k . \mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u|=l)=\frac{l^{l-2}}{(l-1)!}\prod_{j=1}^{l-1}\left(1-\frac{k+j}{m}\right)\left(1-\frac{l}{m}\right)^{m-l-k}. P U , U ( ∣ Past u ∣ = l ) = ( l − 1 )! l l − 2 j = 1 ∏ l − 1 ( 1 − m k + j ) ( 1 − m l ) m − l − k .
On taking the logarithm, we obtain
log ( l l − 2 ( l − 1 ) ! ) + ∑ j = 1 l − 1 log ( 1 − k + j m ) + ( m − l − k ) log ( 1 − l m ) . \log\left(\frac{l^{l-2}}{(l-1)!}\right)+\sum_{j=1}^{l-1}\log\left(1-\frac{k+j}{m}\right)+(m-l-k)\log\left(1-\frac{l}{m}\right). log ( ( l − 1 )! l l − 2 ) + j = 1 ∑ l − 1 log ( 1 − m k + j ) + ( m − l − k ) log ( 1 − m l ) .
In the regime under consideration, both k k k and l l l are o ( m ) o(m) o ( m ) . We can use Taylor’s theorem for the second summand to get
∑ j = 1 l − 1 log ( 1 − k + j m ) = − ∑ j = 1 l − 1 k + j m + O ( ( k + l ) 2 m 2 ) = − k ( l − 1 ) m − l ( l − 1 ) 2 m + O ( l ( k + l ) 2 m 2 ) . \begin{aligned}
\sum_{j=1}^{l-1}\log\left(1-\frac{k+j}{m}\right)=-\sum_{j=1}^{l-1}\frac{k+j}{m}+O\left(\frac{(k+l)^2}{m^2}\right) \\
&=-\frac{k(l-1)}{m}-\frac{l(l-1)}{2m}+O\left(\frac{l(k+l)^2}{m^2}\right).
\end{aligned} j = 1 ∑ l − 1 log ( 1 − m k + j ) = − j = 1 ∑ l − 1 m k + j + O ( m 2 ( k + l ) 2 ) = − m k ( l − 1 ) − 2 m l ( l − 1 ) + O ( m 2 l ( k + l ) 2 ) .
We can also use Taylor’s theorem for the last summand and get
( m − l − k ) log ( 1 − l m ) = − ( l − l 2 + k l m ) + O ( l 2 m − 1 ) . (m-l-k)\log\left(1-\frac{l}{m}\right)=-\left(l-\frac{l^2+kl}{m}\right)+O\left(l^2m^{-1}\right). ( m − l − k ) log ( 1 − m l ) = − ( l − m l 2 + k l ) + O ( l 2 m − 1 ) .
Adding these two terms, we find that k l m \frac{kl}{m} m k l gets canceled and some terms can absorbed into the O O O errors, and we are left with
− l + k m + O ( m − 2 l ( k + l ) 2 ) + O ( l 2 m − 1 ) . -l+\frac{k}{m}+O\left(m^{-2}l(k+l)^2\right)+O\left(l^2m^{-1}\right). − l + m k + O ( m − 2 l ( k + l ) 2 ) + O ( l 2 m − 1 ) .
Notice that since m 1 2 − δ ≤ k ≤ m 1 2 + δ m^{\frac{1}{2}-\delta}\leq k\leq m^{\frac{1}{2}+\delta} m 2 1 − δ ≤ k ≤ m 2 1 + δ , then in this regime for m m m and l l l , the last three of these terms are uniformly o ( 1 ) o(1) o ( 1 ) under the hypotheses (1) . Applying Stirling’s approximation allows us to conclude
P U , U ~ ( ∣ Past u ∣ = l ) = l l − 2 e − l ( l − 1 ) ! ( 1 + o ( 1 ) ) = Θ ( 1 l 3 / 2 ) . (5) \mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u|=l)=\frac{l^{l-2}e^{-l}}{(l-1)!}(1+o(1))=\Theta\left(\frac{1}{l^{3/2}}\right). \tag*{(5)} P U , U ( ∣ Past u ∣ = l ) = ( l − 1 )! l l − 2 e − l ( 1 + o ( 1 )) = Θ ( l 3/2 1 ) . (5)
for some implicit constants C , c > 0 C,c>0 C , c > 0 . Remember we are considering
m 1 2 + ϵ k ≤ l ≤ 2 m 1 2 + ϵ k . \frac{m^{\frac{1}{2}+\epsilon}}{k}\leq l\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}. k m 2 1 + ϵ ≤ l ≤ k 2 m 2 1 + ϵ .
so for all such l l l ,
c k 3 / 2 2 3 / 2 m 3 / 2 ( 1 2 + ϵ ) ≤ P U , U ~ ( ∣ Past u ∣ = l ) ≤ C k 3 / 2 m 3 / 2 ( 1 2 + ϵ ) \frac{c k^{3/2}}{2^{3/2}m^{3/2}\left(\frac{1}{2}+\epsilon\right)} \leq\mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u|=l) \leq\frac{C k^{3/2}}{m^{3/2}\left(\frac{1}{2}+\epsilon\right)} 2 3/2 m 3/2 ( 2 1 + ϵ ) c k 3/2 ≤ P U , U ( ∣ Past u ∣ = l ) ≤ m 3/2 ( 2 1 + ϵ ) C k 3/2
and thus
( m 1 2 + ϵ k + 1 ) c ′ k 3 / 2 m 3 / 2 ( 1 2 + ϵ ) ≤ ∑ m 1 2 + ϵ k ≤ l ≤ 2 m 1 2 + ϵ k P U , U ~ ( ∣ Past u ∣ = l ) ≤ ( m 1 2 + ϵ k + 1 ) C k 3 / 2 m 3 / 2 ( 1 2 + ϵ ) . \left(\frac{m^{\frac{1}{2}+\epsilon}}{k}+1\right)\frac{c'k^{3/2}}{m^{3/2}\left(\frac{1}{2}+\epsilon\right)}
\leq
\sum_{\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq l\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}}
\mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u|=l)
\leq
\left(\frac{m^{\frac{1}{2}+\epsilon}}{k}+1\right)\frac{Ck^{3/2}}{m^{3/2}\left(\frac{1}{2}+\epsilon\right)}. ( k m 2 1 + ϵ + 1 ) m 3/2 ( 2 1 + ϵ ) c ′ k 3/2 ≤ k m 2 1 + ϵ ≤ l ≤ k 2 m 2 1 + ϵ ∑ P U , U ( ∣ Past u ∣ = l ) ≤ ( k m 2 1 + ϵ + 1 ) m 3/2 ( 2 1 + ϵ ) C k 3/2 .
Multiplying by ( m − k ) (m-k) ( m − k ) , and remembering that k ∈ ( m 1 2 − δ , m 1 2 + δ ) k\in\left(m^{\frac{1}{2}-\delta},m^{\frac{1}{2}+\delta}\right) k ∈ ( m 2 1 − δ , m 2 1 + δ ) , we obtain that
E U , U ~ ( ∣ A ∣ ) = Θ ( k m 3 4 − ϵ 2 ) . \mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)=\Theta\left(\sqrt{k}m^{\frac{3}{4}-\frac{\epsilon}{2}}\right). E U , U ( ∣ A ∣ ) = Θ ( k m 4 3 − 2 ϵ ) .
In order to get a concentration estimate for ∣ A ∣ |\mathcal{A}| ∣ A ∣ , we also need a variance upper bound. Getting this upper bound requires a decomposition over various cases. To start with, let P = A × A \mathcal{P}=\mathcal{A}\times\mathcal{A} P = A × A . Note that a particular realization of a random forest induces a (random) partition of the ordered pairs of vertices as
P = P n e s t ∪ P d i s c ∪ P s e l f , \mathcal{P}=\mathcal{P}_{nest}\cup\mathcal{P}_{disc}\cup\mathcal{P}_{self}, P = P n es t ∪ P d i sc ∪ P se l f ,
where
P n e s t : = { ( u , v ) : u , v ∈ A , u ∈ Past v or v ∈ Past u , u ≠ v } , \mathcal{P}_{nest}:=\{(u,v):u,v\in\mathcal{A},u\in\operatorname{Past}_v\text{ or }v\in\operatorname{Past}_u,u\neq v\}, P n es t := {( u , v ) : u , v ∈ A , u ∈ Past v or v ∈ Past u , u = v } ,
P d i s c : = { ( u , v ) : u , v ∈ A , Past u ∩ Past v = ∅ } , \mathcal{P}_{disc}:=\{(u,v):u,v\in\mathcal{A},\operatorname{Past}_u\cap\operatorname{Past}_v=\varnothing\}, P d i sc := {( u , v ) : u , v ∈ A , Past u ∩ Past v = ∅ } ,
and
P s e l f : = { ( u , u ) : u ∈ A } . \mathcal{P}_{self}:=\{(u,u):u\in\mathcal{A}\}. P se l f := {( u , u ) : u ∈ A } .
Thus,
∣ A ∣ 2 = ∣ P n e s t ∣ + ∣ P d i s c ∣ + ∣ A ∣ , |\mathcal{A}|^2=|\mathcal{P}_{nest}|+|\mathcal{P}_{disc}|+|\mathcal{A}|, ∣ A ∣ 2 = ∣ P n es t ∣ + ∣ P d i sc ∣ + ∣ A ∣ ,
and
E U , U ~ ( ∣ A ∣ 2 ) = E U , U ~ ( ∣ P n e s t ∣ ) + E U , U ~ ( ∣ P d i s c ∣ ) + E U , U ~ ( ∣ A ∣ ) . (6) \mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|^2)=\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{nest}|)+\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{disc}|)+\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|). \tag*{(6)} E U , U ( ∣ A ∣ 2 ) = E U , U ( ∣ P n es t ∣ ) + E U , U ( ∣ P d i sc ∣ ) + E U , U ( ∣ A ∣ ) . (6)
Lemma 4.4. For m m m large, m 1 2 − δ ≤ k ≤ m 1 2 + δ m^{\frac{1}{2}-\delta}\leq k\leq m^{\frac{1}{2}+\delta} m 2 1 − δ ≤ k ≤ m 2 1 + δ , and δ \delta δ as per (1) , we have
E U , U ~ ( ∣ P n e s t ∣ ) ≤ C ′ ′ ′ m , \mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{nest}|)\leq C'''m, E U , U ( ∣ P n es t ∣ ) ≤ C ′′′ m , for some C ′ ′ ′ > 0 C'''>0 C ′′′ > 0 .
Proof. We may restrict to the case of Past v ⊂ Past u \operatorname{Past}_v\subset\operatorname{Past}_u Past v ⊂ Past u , that is v ∈ Past u v\in\operatorname{Past}_u v ∈ Past u , since twice the expected number of these pairs yields E U , U ~ ( ∣ P n e s t ∣ ) \mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{nest}|) E U , U ( ∣ P n es t ∣ ) . Thus,
1 2 E U , U ~ ( ∣ P n e s t ∣ ) = ∑ u ≠ v ∑ 2 m 1 2 + ϵ k ≥ l 1 > l 2 ≥ m 1 2 + ϵ k P U , U ~ ( v ∈ Past u , ∣ Past u ∣ = l 1 , ∣ Past v ∣ = l 2 ) . \frac{1}{2}\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{nest}|)
=
\sum_{u\neq v}
\sum_{\frac{2m^{\frac{1}{2}+\epsilon}}{k}\geq l_1>l_2\geq\frac{m^{\frac{1}{2}+\epsilon}}{k}}
\mathbb{P}^{U,\widetilde{U}}(v\in\operatorname{Past}_u,|\operatorname{Past}_u|=l_1,|\operatorname{Past}_v|=l_2). 2 1 E U , U ( ∣ P n es t ∣ ) = u = v ∑ k 2 m 2 1 + ϵ ≥ l 1 > l 2 ≥ k m 2 1 + ϵ ∑ P U , U ( v ∈ Past u , ∣ Past u ∣ = l 1 , ∣ Past v ∣ = l 2 ) .
Note that the probability in the sum cannot depend on the specific labels due to symmetry. There are in particular 2 ( m − k 2 ) 2\binom{m-k}{2} 2 ( 2 m − k ) many such pairs. Thus, applying Lemma 4.2
1 2 E U , U ~ ( ∣ P n e s t ∣ ) = 2 ( m − k 2 ) ∑ 2 m 1 2 + ϵ k ≥ l 1 > l 2 ≥ m 1 2 + ϵ k ( m − k − 2 ) ! l 1 l 2 − 2 ( l 1 − l 2 ) l 1 − l 2 − 1 ( m − l 1 ) m − l 1 − k ( l 2 − 1 ) ! ( l 1 − l 2 − 1 ) ! ( m − k − l 1 ) ! m m − k − 1 . \frac{1}{2}\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{nest}|)
=
2\binom{m-k}{2}
\sum_{\frac{2m^{\frac{1}{2}+\epsilon}}{k}\geq l_1>l_2\geq\frac{m^{\frac{1}{2}+\epsilon}}{k}}
\frac{(m-k-2)!\,l_1^{l_2-2}(l_1-l_2)^{l_1-l_2-1}(m-l_1)^{m-l_1-k}}
{(l_2-1)!(l_1-l_2-1)!(m-k-l_1)!\,m^{m-k-1}}. 2 1 E U , U ( ∣ P n es t ∣ ) = 2 ( 2 m − k ) k 2 m 2 1 + ϵ ≥ l 1 > l 2 ≥ k m 2 1 + ϵ ∑ ( l 2 − 1 )! ( l 1 − l 2 − 1 )! ( m − k − l 1 )! m m − k − 1 ( m − k − 2 )! l 1 l 2 − 2 ( l 1 − l 2 ) l 1 − l 2 − 1 ( m − l 1 ) m − l 1 − k .
A simpler expression for the sum can be obtained by conditioning further. Note,
P U , U ~ ( v ∈ Past u , ∣ Past u ∣ = l 1 , ∣ Past v ∣ = l 2 ) = P U , U ~ ( ∣ Past v ∣ = l 2 , v ∈ Past u ∣ ∣ Past u ∣ = l 1 ) × P U , U ~ ( ∣ Past u ∣ = l 1 ) . \mathbb{P}^{U,\widetilde{U}}(v\in\operatorname{Past}_u,|\operatorname{Past}_u|=l_1,|\operatorname{Past}_v|=l_2)
=
\mathbb{P}^{U,\widetilde{U}}\left(|\operatorname{Past}_v|=l_2,v\in\operatorname{Past}_u\mid|\operatorname{Past}_u|=l_1\right)
\times\mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u|=l_1). P U , U ( v ∈ Past u , ∣ Past u ∣ = l 1 , ∣ Past v ∣ = l 2 ) = P U , U ( ∣ Past v ∣ = l 2 , v ∈ Past u ∣ ∣ Past u ∣ = l 1 ) × P U , U ( ∣ Past u ∣ = l 1 ) .
By Lemma 4.1,
P ( ∣ Past u ∣ = l 1 ) = ( m − k − 1 l 1 − 1 ) l 1 l 1 − 2 ( m − l 1 ) m − l 1 − k m m − k − 1 . \mathbb{P}(|\operatorname{Past}_{u}|=l_{1})=\binom{m-k-1}{l_{1}-1}\frac{l_{1}^{l_{1}-2}(m-l_{1})^{m-l_{1}-k}}{m^{m-k-1}}. P ( ∣ Past u ∣ = l 1 ) = ( l 1 − 1 m − k − 1 ) m m − k − 1 l 1 l 1 − 2 ( m − l 1 ) m − l 1 − k .
It simplifies things considerably if we rewrite the summand in terms of the conditional probability. In particular, we obtain
P U , U ~ ( ∣ Past v ∣ = l 2 , v ∈ Past u ∣ ∣ Past u ∣ = l 1 ) = l 1 − 1 m − k − 1 ( l 1 − 2 l 2 − 1 ) l 2 l 2 − 2 ( l 1 − l 2 ) l 1 − l 2 − 1 l 1 l 1 − 2 . \mathbb{P}^{U,\widetilde{U}}\left(|\operatorname{Past}_{v}|=l_{2},v\in\operatorname{Past}_{u}\mathrel{\big|}|\operatorname{Past}_{u}|=l_{1}\right)=\frac{l_{1}-1}{m-k-1}\binom{l_{1}-2}{l_{2}-1}\frac{l_{2}^{l_{2}-2}(l_{1}-l_{2})^{l_{1}-l_{2}-1}}{l_{1}^{l_{1}-2}}. P U , U ( ∣ Past v ∣ = l 2 , v ∈ Past u ∣ Past u ∣ = l 1 ) = m − k − 1 l 1 − 1 ( l 2 − 1 l 1 − 2 ) l 1 l 1 − 2 l 2 l 2 − 2 ( l 1 − l 2 ) l 1 − l 2 − 1 .
Indeed, after fixing u u u , we can find other ( l 1 − 1 ) (l_{1}-1) ( l 1 − 1 ) vertices in Past u \operatorname{Past}_{u} Past u from ∣ U ∖ U ~ ∣ − 1 = ( m − k − 1 ) |U\setminus\widetilde{U}|-1=(m-k-1) ∣ U ∖ U ∣ − 1 = ( m − k − 1 ) vertices. Now, an argument similar to that of Lemma 4.1 gives the factor ( l 1 − 2 l 2 − 1 ) l 2 l 2 − 2 ( l 1 − l 2 ) l 1 − l 2 − 1 l 1 l 1 − 2 \binom{l_{1}-2}{l_{2}-1}\frac{l_{2}^{l_{2}-2}(l_{1}-l_{2})^{l_{1}-l_{2}-1}}{l_{1}^{l_{1}-2}} ( l 2 − 1 l 1 − 2 ) l 1 l 1 − 2 l 2 l 2 − 2 ( l 1 − l 2 ) l 1 − l 2 − 1 . By Stirling’s approximation,
( l 1 − 2 l 2 − 1 ) = ( l 1 − 2 ) ! ( l 2 − 1 ) ! ( l 1 − l 2 − 1 ) ! ≤ C 2 π ( l 1 − 2 ) l 1 − 3 2 ( l 2 − 1 ) l 2 − 1 2 ( l 1 − l 2 − 1 ) l 1 − l 2 − 1 2 , \binom{l_{1}-2}{l_{2}-1}=\frac{(l_{1}-2)!}{(l_{2}-1)!(l_{1}-l_{2}-1)!}\leq\frac{C}{\sqrt{2\pi}}\frac{(l_{1}-2)^{l_{1}-\frac{3}{2}}}{(l_{2}-1)^{l_{2}-\frac{1}{2}}(l_{1}-l_{2}-1)^{l_{1}-l_{2}-\frac{1}{2}}}, ( l 2 − 1 l 1 − 2 ) = ( l 2 − 1 )! ( l 1 − l 2 − 1 )! ( l 1 − 2 )! ≤ 2 π C ( l 2 − 1 ) l 2 − 2 1 ( l 1 − l 2 − 1 ) l 1 − l 2 − 2 1 ( l 1 − 2 ) l 1 − 2 3 ,
where C > 0 C>0 C > 0 . Combining with the terms that come from Cayley’s formula, we obtain
P U , U ~ ( ∣ Past v ∣ = l 2 , v ∈ Past u ∣ ∣ Past u ∣ = l 1 ) ≤ C 2 π l 2 − 3 / 2 ( l 1 l 1 − l 2 ) 1 / 2 = C 2 π l 2 − 3 / 2 ( 1 − l 2 l 1 ) − 1 / 2 . \mathbb{P}^{U,\widetilde{U}}\left(|\operatorname{Past}_{v}|=l_{2},v\in\operatorname{Past}_{u}\mathrel{\big|}|\operatorname{Past}_{u}|=l_{1}\right)\leq\frac{C}{\sqrt{2\pi}}l_{2}^{-3/2}\left(\frac{l_{1}}{l_{1}-l_{2}}\right)^{1/2}=\frac{C}{\sqrt{2\pi}}l_{2}^{-3/2}\left(1-\frac{l_{2}}{l_{1}}\right)^{-1/2}. P U , U ( ∣ Past v ∣ = l 2 , v ∈ Past u ∣ Past u ∣ = l 1 ) ≤ 2 π C l 2 − 3/2 ( l 1 − l 2 l 1 ) 1/2 = 2 π C l 2 − 3/2 ( 1 − l 1 l 2 ) − 1/2 .
Recall from (5) ,
P U , U ~ ( ∣ Past u ∣ = l 1 ) = l 1 l 1 − 2 e − l 1 ( l 1 − 1 ) ! ( 1 + o ( 1 ) ) ≤ C ′ 2 π l 1 3 / 2 , \mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_{u}|=l_{1})=\frac{l_{1}^{l_{1}-2}e^{-l_{1}}}{(l_{1}-1)!}(1+o(1))\leq\frac{C'}{\sqrt{2\pi}l_{1}^{3/2}}, P U , U ( ∣ Past u ∣ = l 1 ) = ( l 1 − 1 )! l 1 l 1 − 2 e − l 1 ( 1 + o ( 1 )) ≤ 2 π l 1 3/2 C ′ ,
for some C ′ > 0 C'>0 C ′ > 0 . Combining, we obtain that for some C ′ ′ > 0 C''>0 C ′′ > 0 ,
1 2 E U , U ~ ( ∣ P n e s t ∣ ) ≤ ( m − k ) ∑ m 1 2 + ϵ k ≤ l 1 ≤ 2 m 1 2 + ϵ k ∑ m 1 2 + ϵ k ≤ l 2 < l 1 C ′ ′ 2 π ( l 1 − 1 ) ( l 2 l 1 ) − 3 / 2 ( 1 − l 2 l 1 ) − 1 / 2 = ( m − k ) ∑ m 1 2 + ϵ k ≤ l 1 ≤ 2 m 1 2 + ϵ k C ′ ′ 2 π ( l 1 − 1 ) l 1 − 3 / 2 l 1 ⋅ 1 l 1 ∑ m 1 2 + ϵ k ≤ l 2 ≤ l 1 − 1 ( l 2 l 1 ) − 3 / 2 ( 1 − l 2 l 1 ) − 1 / 2 . \begin{aligned}
\frac{1}{2}\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{\mathrm{nest}}|)\leq(m-k)\sum_{\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq l_{1}\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}}\sum_{\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq l_{2}<l_{1}}\frac{C''}{2\pi}(l_{1}-1)(l_{2}l_{1})^{-3/2}\left(1-\frac{l_{2}}{l_{1}}\right)^{-1/2} \\
&=(m-k)\sum_{\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq l_{1}\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}}\frac{C''}{2\pi}(l_{1}-1)l_{1}^{-3/2}l_{1}\cdot\frac{1}{l_{1}}\sum_{\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq l_{2}\leq l_{1}-1}\left(\frac{l_{2}}{l_{1}}\right)^{-3/2}\left(1-\frac{l_{2}}{l_{1}}\right)^{-1/2}.
\end{aligned} 2 1 E U , U ( ∣ P nest ∣ ) ≤ ( m − k ) k m 2 1 + ϵ ≤ l 1 ≤ k 2 m 2 1 + ϵ ∑ k m 2 1 + ϵ ≤ l 2 < l 1 ∑ 2 π C ′′ ( l 1 − 1 ) ( l 2 l 1 ) − 3/2 ( 1 − l 1 l 2 ) − 1/2 = ( m − k ) k m 2 1 + ϵ ≤ l 1 ≤ k 2 m 2 1 + ϵ ∑ 2 π C ′′ ( l 1 − 1 ) l 1 − 3/2 l 1 ⋅ l 1 1 k m 2 1 + ϵ ≤ l 2 ≤ l 1 − 1 ∑ ( l 1 l 2 ) − 3/2 ( 1 − l 1 l 2 ) − 1/2 .
For the interior sum, denoting l 2 / l 1 l_{2}/l_{1} l 2 / l 1 by ξ \xi ξ , observe that the sum can be represented as
1 l 1 ∑ ξ ∈ T ξ − 3 / 2 ( 1 − ξ ) − 1 / 2 , where T = { n l 1 : n ∈ N , m 1 2 + ϵ k ≤ n ≤ l 1 − 1 } . \frac{1}{l_{1}}\sum_{\xi\in T}\xi^{-3/2}(1-\xi)^{-1/2},\qquad\text{where }T=\left\{\frac{n}{l_{1}}:n\in\mathbb{N},\ \frac{m^{\frac{1}{2}+\epsilon}}{k}\leq n\leq l_{1}-1\right\}. l 1 1 ξ ∈ T ∑ ξ − 3/2 ( 1 − ξ ) − 1/2 , where T = { l 1 n : n ∈ N , k m 2 1 + ϵ ≤ n ≤ l 1 − 1 } .
The interior sum is thus a Riemann sum, since l 1 ≤ 2 m 1 2 + ϵ k l_{1}\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k} l 1 ≤ k 2 m 2 1 + ϵ , approximating the integral
∫ m 1 2 + ϵ k ⋅ l 1 1 ξ − 3 / 2 ( 1 − ξ ) − 1 / 2 d ξ ≤ ∫ 1 2 1 ξ − 3 / 2 ( 1 − ξ ) − 1 / 2 d ξ < ∞ . \int_{\frac{m^{\frac{1}{2}+\epsilon}}{k\cdot l_{1}}}^{1}\xi^{-3/2}(1-\xi)^{-1/2}\,d\xi\leq\int_{\frac{1}{2}}^{1}\xi^{-3/2}(1-\xi)^{-1/2}\,d\xi<\infty. ∫ k ⋅ l 1 m 2 1 + ϵ 1 ξ − 3/2 ( 1 − ξ ) − 1/2 d ξ ≤ ∫ 2 1 1 ξ − 3/2 ( 1 − ξ ) − 1/2 d ξ < ∞.
Thus, the inner sum can be uniformly bounded above by a constant. Overall, we obtain
1 2 E U , U ~ ( ∣ P n e s t ∣ ) ≤ C ′ ′ ′ ( m − k ) ∑ m 1 2 + ϵ k ≤ l 1 ≤ 2 m 1 2 + ϵ k 1 l 1 ≤ C ′ ′ ′ ′ ( m − k ) , \frac{1}{2}\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{\mathrm{nest}}|)\leq C'''(m-k)\sum_{\frac{m^{\frac{1}{2}+\epsilon}}{k}\leq l_{1}\leq\frac{2m^{\frac{1}{2}+\epsilon}}{k}}\frac{1}{l_{1}}\leq C''''(m-k), 2 1 E U , U ( ∣ P nest ∣ ) ≤ C ′′′ ( m − k ) k m 2 1 + ϵ ≤ l 1 ≤ k 2 m 2 1 + ϵ ∑ l 1 1 ≤ C ′′′′ ( m − k ) ,
where the last inequality follows from well-known bounds on harmonic sums.
Next, we address the issue of the disjoint pasts of the vertices in A \mathcal{A} A .
Lemma 4.5. For m m m large, m 1 2 − δ ≤ k ≤ m 1 2 + δ m^{\frac{1}{2}-\delta} \le k \le m^{\frac{1}{2}+\delta} m 2 1 − δ ≤ k ≤ m 2 1 + δ , and ϵ \epsilon ϵ and δ \delta δ as per (1) ,
E U , U ~ ( ∣ P d i s c ∣ ) = ( E U , U ~ ( ∣ A ∣ ) ) 2 + O ( m max { 1 , 1 + 5 δ − ϵ } ) . \mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{disc}|)=\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2+O\left(m^{\max\{1,1+5\delta-\epsilon\}}\right). E U , U ( ∣ P d i sc ∣ ) = ( E U , U ( ∣ A ∣ ) ) 2 + O ( m m a x { 1 , 1 + 5 δ − ϵ } ) .
Proof. By Lemma 4.2 for L = m 1 2 + ϵ k L=\frac{m^{\frac{1}{2}+\epsilon}}{k} L = k m 2 1 + ϵ ,
E U , U ~ ( ∣ P d i s c ∣ ) = ∑ L ≤ l 1 , l 2 ≤ 2 L u ≠ v P U , U ~ ( ∣ Past u ∣ = l 1 , ∣ Past v ∣ = l 2 , Past u ∩ Past v = ∅ ) = ( m − k ) ( m − k − 1 ) ∑ L ≤ l 1 , l 2 ≤ 2 L ( m − k − 2 ) ! l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 ( l 1 − 1 ) ! ( l 2 − 1 ) ! ( m − k − l 1 − l 2 ) ! m m − k − 1 . \begin{aligned}
\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{disc}|)=\sum_{\substack{L\le l_1,l_2\le2L\\u\ne v}}\mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u|=l_1,|\operatorname{Past}_v|=l_2,\operatorname{Past}_u\cap\operatorname{Past}_v=\varnothing) \\
&=(m-k)(m-k-1)\sum_{L\le l_1,l_2\le2L}\frac{(m-k-2)!l_1^{l_1-2}l_2^{l_2-2}(m-l_1-l_2)^{m-l_1-l_2-k+1}}{(l_1-1)!(l_2-1)!(m-k-l_1-l_2)!m^{m-k-1}}.
\end{aligned} E U , U ( ∣ P d i sc ∣ ) = L ≤ l 1 , l 2 ≤ 2 L u = v ∑ P U , U ( ∣ Past u ∣ = l 1 , ∣ Past v ∣ = l 2 , Past u ∩ Past v = ∅ ) = ( m − k ) ( m − k − 1 ) L ≤ l 1 , l 2 ≤ 2 L ∑ ( l 1 − 1 )! ( l 2 − 1 )! ( m − k − l 1 − l 2 )! m m − k − 1 ( m − k − 2 )! l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 .
Next, observe that
( E U , U ~ ( ∣ A ∣ ) ) 2 = ∑ L ≤ l 1 , l 2 ≤ 2 L u , v P U , U ~ ( ∣ Past u ∣ = l 1 ) P U , U ~ ( ∣ Past v ∣ = l 2 ) = ( m − k ) 2 ∑ L ≤ l 1 , l 2 ≤ 2 L ( m − k − 1 l 1 − 1 ) ( m − k − 1 l 2 − 1 ) l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k m 2 m − 2 k − 2 . \begin{aligned}
\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2=\sum_{\substack{L\le l_1,l_2\le2L\\u,v}}\mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_u|=l_1)\mathbb{P}^{U,\widetilde{U}}(|\operatorname{Past}_v|=l_2) \\
&=(m-k)^2\sum_{L\le l_1,l_2\le2L}\binom{m-k-1}{l_1-1}\binom{m-k-1}{l_2-1}\frac{l_1^{l_1-2}l_2^{l_2-2}(m-l_1)^{m-l_1-k}(m-l_2)^{m-l_2-k}}{m^{2m-2k-2}}.
\end{aligned} ( E U , U ( ∣ A ∣ ) ) 2 = L ≤ l 1 , l 2 ≤ 2 L u , v ∑ P U , U ( ∣ Past u ∣ = l 1 ) P U , U ( ∣ Past v ∣ = l 2 ) = ( m − k ) 2 L ≤ l 1 , l 2 ≤ 2 L ∑ ( l 1 − 1 m − k − 1 ) ( l 2 − 1 m − k − 1 ) m 2 m − 2 k − 2 l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k .
Define
R ( l 1 , l 2 ) = ( m − k ) ( m − k − 1 ) ( m − k − 2 ) ! l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 ( l 1 − 1 ) ! ( l 2 − 1 ) ! ( m − k − l 1 − l 2 ) ! m m − k − 1 ( m − k ) 2 ( m − k − 1 l 1 − 1 ) ( m − k − 1 l 2 − 1 ) l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k m 2 m − 2 k − 2 , R(l_1,l_2)=\frac{(m-k)(m-k-1)\dfrac{(m-k-2)!l_1^{l_1-2}l_2^{l_2-2}(m-l_1-l_2)^{m-l_1-l_2-k+1}}{(l_1-1)!(l_2-1)!(m-k-l_1-l_2)!m^{m-k-1}}}{(m-k)^2\binom{m-k-1}{l_1-1}\binom{m-k-1}{l_2-1}\dfrac{l_1^{l_1-2}l_2^{l_2-2}(m-l_1)^{m-l_1-k}(m-l_2)^{m-l_2-k}}{m^{2m-2k-2}}}, R ( l 1 , l 2 ) = ( m − k ) 2 ( l 1 − 1 m − k − 1 ) ( l 2 − 1 m − k − 1 ) m 2 m − 2 k − 2 l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k ( m − k ) ( m − k − 1 ) ( l 1 − 1 )! ( l 2 − 1 )! ( m − k − l 1 − l 2 )! m m − k − 1 ( m − k − 2 )! l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 ,
the ratio of the respective summands. Denote by
Ξ ( l 1 , l 2 ) : = ( m − k − 1 l 1 − 1 ) ( m − k − 1 l 2 − 1 ) l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k m 2 m − 2 k − 2 , \Xi(l_1,l_2):=\binom{m-k-1}{l_1-1}\binom{m-k-1}{l_2-1}\frac{l_1^{l_1-2}l_2^{l_2-2}(m-l_1)^{m-l_1-k}(m-l_2)^{m-l_2-k}}{m^{2m-2k-2}}, Ξ ( l 1 , l 2 ) := ( l 1 − 1 m − k − 1 ) ( l 2 − 1 m − k − 1 ) m 2 m − 2 k − 2 l 1 l 1 − 2 l 2 l 2 − 2 ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k ,
so that
( E U , U ~ ( ∣ A ∣ ) ) 2 = ( m − k ) 2 ∑ L ≤ l 1 , l 2 ≤ 2 L Ξ ( l 1 , l 2 ) . \left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2=(m-k)^2\sum_{L\le l_1,l_2\le2L}\Xi(l_1,l_2). ( E U , U ( ∣ A ∣ ) ) 2 = ( m − k ) 2 L ≤ l 1 , l 2 ≤ 2 L ∑ Ξ ( l 1 , l 2 ) .
The comparison between ( E U , U ~ ( ∣ A ∣ ) ) 2 \left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2 ( E U , U ( ∣ A ∣ ) ) 2 and E U , U ~ ( ∣ P d i s c ∣ ) \mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{disc}|) E U , U ( ∣ P d i sc ∣ ) can now be set up. Note,
E U , U ~ ( ∣ P d i s c ∣ ) = ( m − k ) 2 ∑ L ≤ l 1 , l 2 ≤ 2 L Ξ ( l 1 , l 2 ) ⋅ R ( l 1 , l 2 ) . (7) \mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{disc}|)=(m-k)^2\sum_{L\le l_1,l_2\le2L}\Xi(l_1,l_2)\cdot R(l_1,l_2). \tag*{(7)} E U , U ( ∣ P d i sc ∣ ) = ( m − k ) 2 L ≤ l 1 , l 2 ≤ 2 L ∑ Ξ ( l 1 , l 2 ) ⋅ R ( l 1 , l 2 ) . (7)
We aim to show that R R R is close to 1. Simplifying the expression for R R R by cancelling terms that appear in common, we find that
R ( l 1 , l 2 ) = m m − k − 1 ( m − k ) ! ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 ( m − k − l 1 ) ! ( m − k − l 2 ) ! ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k ( m − k − l 1 − l 2 ) ! . R(l_1,l_2)=\frac{m^{m-k-1}}{(m-k)!}\frac{(m-l_1-l_2)^{m-l_1-l_2-k+1}(m-k-l_1)!(m-k-l_2)!}{(m-l_1)^{m-l_1-k}(m-l_2)^{m-l_2-k}(m-k-l_1-l_2)!}. R ( l 1 , l 2 ) = ( m − k )! m m − k − 1 ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k ( m − k − l 1 − l 2 )! ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 ( m − k − l 1 )! ( m − k − l 2 )! .
The ratio term can further be split into a product of two terms, composed of the factorial parts and the power parts respectively. That is, define
F ( l 1 , l 2 ) : = ( m − k − l 1 ) ! ( m − k − l 2 ) ! ( m − k ) ! ( m − k − l 1 − l 2 ) ! F(l_1,l_2):=\frac{(m-k-l_1)!(m-k-l_2)!}{(m-k)!(m-k-l_1-l_2)!} F ( l 1 , l 2 ) := ( m − k )! ( m − k − l 1 − l 2 )! ( m − k − l 1 )! ( m − k − l 2 )!
and
P ( l 1 , l 2 ) = m m − k − 1 ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k . P(l_1,l_2)=\frac{m^{m-k-1}(m-l_1-l_2)^{m-l_1-l_2-k+1}}{(m-l_1)^{m-l_1-k}(m-l_2)^{m-l_2-k}}. P ( l 1 , l 2 ) = ( m − l 1 ) m − l 1 − k ( m − l 2 ) m − l 2 − k m m − k − 1 ( m − l 1 − l 2 ) m − l 1 − l 2 − k + 1 .
For ease of notation, denote m − k m-k m − k by q q q . By Stirling’s approximation,
F ( l 1 , l 2 ) = ( q − l 1 ) q − l 1 ( q − l 2 ) q − l 2 e − 2 q + l 1 + l 2 2 π ( q − l 1 ) ( q − l 2 ) q q ( q − l 1 − l 2 ) q − l 1 − l 2 e − 2 q + l 1 + l 2 2 π q ( q − l 1 − l 2 ) ( 1 + O ( m − 1 ) ) = ( q − l 1 ) q − l 1 ( q − l 2 ) q − l 2 q q ( q − l 1 − l 2 ) q − l 1 − l 2 ( 1 + O ( L ⋅ m − 1 ) ) \begin{aligned}
F(l_1,l_2)=\frac{(q-l_1)^{q-l_1}(q-l_2)^{q-l_2}e^{-2q+l_1+l_2}\sqrt{2\pi(q-l_1)(q-l_2)}}{q^q(q-l_1-l_2)^{q-l_1-l_2}e^{-2q+l_1+l_2}\sqrt{2\pi q(q-l_1-l_2)}}\left(1+O(m^{-1})\right) \\
&=\frac{(q-l_1)^{q-l_1}(q-l_2)^{q-l_2}}{q^q(q-l_1-l_2)^{q-l_1-l_2}}\left(1+O(L\cdot m^{-1})\right)
\end{aligned} F ( l 1 , l 2 ) = q q ( q − l 1 − l 2 ) q − l 1 − l 2 e − 2 q + l 1 + l 2 2 π q ( q − l 1 − l 2 ) ( q − l 1 ) q − l 1 ( q − l 2 ) q − l 2 e − 2 q + l 1 + l 2 2 π ( q − l 1 ) ( q − l 2 ) ( 1 + O ( m − 1 ) ) = q q ( q − l 1 − l 2 ) q − l 1 − l 2 ( q − l 1 ) q − l 1 ( q − l 2 ) q − l 2 ( 1 + O ( L ⋅ m − 1 ) )
For P P P , we have
P ( l 1 , l 2 ) = ( q + k ) q − 1 ( q + k − l 1 − l 2 ) q − l 1 − l 2 + 1 ( q + k − l 1 ) q − l 1 ( q + k − l 2 ) q − l 2 = q + k − l 1 − l 2 q + k ⋅ ( q + k ) q ( q + k − l 1 − l 2 ) q − l 1 − l 2 ( q + k − l 1 ) q − l 1 ( q + k − l 2 ) q − l 2 = ( 1 + O ( L ⋅ m − 1 ) ) ⋅ ( q + k ) q ( q + k − l 1 − l 2 ) q − l 1 − l 2 ( q + k − l 1 ) q − l 1 ( q + k − l 2 ) q − l 2 . \begin{aligned}
P(l_1,l_2)=\frac{(q+k)^{q-1}(q+k-l_1-l_2)^{q-l_1-l_2+1}}{(q+k-l_1)^{q-l_1}(q+k-l_2)^{q-l_2}} \\
&=\frac{q+k-l_1-l_2}{q+k}\cdot\frac{(q+k)^q(q+k-l_1-l_2)^{q-l_1-l_2}}{(q+k-l_1)^{q-l_1}(q+k-l_2)^{q-l_2}} \\
&=\left(1+O(L\cdot m^{-1})\right)\cdot\frac{(q+k)^q(q+k-l_1-l_2)^{q-l_1-l_2}}{(q+k-l_1)^{q-l_1}(q+k-l_2)^{q-l_2}}.
\end{aligned} P ( l 1 , l 2 ) = ( q + k − l 1 ) q − l 1 ( q + k − l 2 ) q − l 2 ( q + k ) q − 1 ( q + k − l 1 − l 2 ) q − l 1 − l 2 + 1 = q + k q + k − l 1 − l 2 ⋅ ( q + k − l 1 ) q − l 1 ( q + k − l 2 ) q − l 2 ( q + k ) q ( q + k − l 1 − l 2 ) q − l 1 − l 2 = ( 1 + O ( L ⋅ m − 1 ) ) ⋅ ( q + k − l 1 ) q − l 1 ( q + k − l 2 ) q − l 2 ( q + k ) q ( q + k − l 1 − l 2 ) q − l 1 − l 2 .
Combining terms, we obtain
R ( l 1 , l 2 ) = ( q − l 1 q + k − l 1 ) q − l 1 ( q − l 2 q + k − l 2 ) q − l 2 ( q + k q ) q ( q + k − l 1 − l 2 q − l 1 − l 2 ) q − l 1 − l 2 ( 1 + O ( L ⋅ m − 1 ) ) . R(l_1,l_2)=\left(\frac{q-l_1}{q+k-l_1}\right)^{q-l_1}\left(\frac{q-l_2}{q+k-l_2}\right)^{q-l_2}\left(\frac{q+k}{q}\right)^q\left(\frac{q+k-l_1-l_2}{q-l_1-l_2}\right)^{q-l_1-l_2}\left(1+O(L\cdot m^{-1})\right). R ( l 1 , l 2 ) = ( q + k − l 1 q − l 1 ) q − l 1 ( q + k − l 2 q − l 2 ) q − l 2 ( q q + k ) q ( q − l 1 − l 2 q + k − l 1 − l 2 ) q − l 1 − l 2 ( 1 + O ( L ⋅ m − 1 ) ) .
Observe that
( q − l 1 q + k − l 1 ) q − l 1 = exp ( − ( q − l 1 ) log ( 1 + k q − l 1 ) ) = exp ( − k + k 2 2 ( q − l 1 ) − k 3 3 ( q − l 1 ) 2 + O ( k 4 q 3 ) ) . \begin{aligned}
\left(\frac{q-l_1}{q+k-l_1}\right)^{q-l_1}=\exp\left(-(q-l_1)\log\left(1+\frac{k}{q-l_1}\right)\right) \\
&=\exp\left(-k+\frac{k^2}{2(q-l_1)}-\frac{k^3}{3(q-l_1)^2}+O\left(\frac{k^4}{q^3}\right)\right).
\end{aligned} ( q + k − l 1 q − l 1 ) q − l 1 = exp ( − ( q − l 1 ) log ( 1 + q − l 1 k ) ) = exp ( − k + 2 ( q − l 1 ) k 2 − 3 ( q − l 1 ) 2 k 3 + O ( q 3 k 4 ) ) .
Applying the same principle for all four terms, we gather our errors. Note, the k k k terms cancel. Next, the k 2 k^2 k 2 terms in the exponential can be combined as
k 2 2 ( 1 q − l 1 + 1 q − l 2 − 1 q − 1 q − l 1 − l 2 ) = − k 2 l 1 l 2 ( 2 q − l 1 − l 2 ) 2 q ( q − l 1 ) ( q − l 2 ) ( q − l 1 − l 2 ) . \frac{k^2}{2}\left(\frac{1}{q-l_1}+\frac{1}{q-l_2}-\frac{1}{q}-\frac{1}{q-l_1-l_2}\right)=\frac{-k^2l_1l_2(2q-l_1-l_2)}{2q(q-l_1)(q-l_2)(q-l_1-l_2)}. 2 k 2 ( q − l 1 1 + q − l 2 1 − q 1 − q − l 1 − l 2 1 ) = 2 q ( q − l 1 ) ( q − l 2 ) ( q − l 1 − l 2 ) − k 2 l 1 l 2 ( 2 q − l 1 − l 2 ) .
Finally we deal with the k 3 k^3 k 3 terms for which the relevant error contribution is
k 3 3 ( − 1 ( q − l 1 ) 2 − 1 ( q − l 2 ) 2 + 1 q 2 + 1 ( q − l 1 − l 2 ) 2 ) . \frac{k^3}{3}\left(-\frac{1}{(q-l_1)^2}-\frac{1}{(q-l_2)^2}+\frac{1}{q^2}+\frac{1}{(q-l_1-l_2)^2}\right). 3 k 3 ( − ( q − l 1 ) 2 1 − ( q − l 2 ) 2 1 + q 2 1 + ( q − l 1 − l 2 ) 2 1 ) .
The expanded term is more complicated, and is given by
k 3 l 1 l 2 ( 6 q 4 − 12 ( l 1 + l 2 ) q 3 + ( 8 l 1 2 + 18 l 1 l 2 + 8 l 2 2 ) q 2 − 2 ( l 1 + l 2 ) ( l 1 2 + 3 l 1 l 2 + l 2 2 ) q + l 1 l 2 ( l 1 + l 2 ) 2 ) 3 q 2 ( q − l 1 ) 2 ( q − l 2 ) 2 ( q − l 1 − l 2 ) 2 . \frac{k^3l_1l_2\left(6q^4-12(l_1+l_2)q^3+(8l_1^2+18l_1l_2+8l_2^2)q^2-2(l_1+l_2)(l_1^2+3l_1l_2+l_2^2)q+l_1l_2(l_1+l_2)^2\right)}{3q^2(q-l_1)^2(q-l_2)^2(q-l_1-l_2)^2}. 3 q 2 ( q − l 1 ) 2 ( q − l 2 ) 2 ( q − l 1 − l 2 ) 2 k 3 l 1 l 2 ( 6 q 4 − 12 ( l 1 + l 2 ) q 3 + ( 8 l 1 2 + 18 l 1 l 2 + 8 l 2 2 ) q 2 − 2 ( l 1 + l 2 ) ( l 1 2 + 3 l 1 l 2 + l 2 2 ) q + l 1 l 2 ( l 1 + l 2 ) 2 ) .
Plugging in the fact that l 1 l_1 l 1 and l 2 l_2 l 2 are Θ ( m 1 2 + ϵ / k ) \Theta(m^{\frac{1}{2}+\epsilon}/k) Θ ( m 2 1 + ϵ / k ) , and recalling that the regime of k k k in question is m 1 / 2 − δ ≤ k ≤ m 1 / 2 + δ m^{1/2-\delta}\leq k\leq m^{1/2+\delta} m 1/2 − δ ≤ k ≤ m 1/2 + δ and keeping the dominant errors, we obtain
R ( l 1 , l 2 ) = exp ( O ( 1 m 2 − 2 ϵ ) + O ( k m 3 − 2 ϵ ) + O ( k 4 m 3 ) ) ( 1 + O ( 1 k m 1 2 − ϵ ) ) . R(l_1,l_2)=\exp\left(O\left(\frac{1}{m^{2-2\epsilon}}\right)+O\left(\frac{k}{m^{3-2\epsilon}}\right)+O\left(\frac{k^4}{m^3}\right)\right)\left(1+O\left(\frac{1}{km^{\frac{1}{2}-\epsilon}}\right)\right). R ( l 1 , l 2 ) = exp ( O ( m 2 − 2 ϵ 1 ) + O ( m 3 − 2 ϵ k ) + O ( m 3 k 4 ) ) ( 1 + O ( k m 2 1 − ϵ 1 ) ) .
Note that the above expression is uniform in ( l 1 , l 2 ) (l_1,l_2) ( l 1 , l 2 ) . For the range of k k k in question, the k 4 / m 3 k^4/m^3 k 4 / m 3 term dominates. We may now recast (7) as
E U , U ~ ( ∣ P d i s c ∣ ) = ( m − k ) 2 ∑ L ≤ l 1 , l 2 ≤ 2 L Ξ ( l 1 , l 2 ) ⋅ R ( l 1 , l 2 ) \mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{disc}|)=(m-k)^2\sum_{L\le l_1,l_2\le2L}\Xi(l_1,l_2)\cdot R(l_1,l_2) E U , U ( ∣ P d i sc ∣ ) = ( m − k ) 2 L ≤ l 1 , l 2 ≤ 2 L ∑ Ξ ( l 1 , l 2 ) ⋅ R ( l 1 , l 2 )
( 1 + O ( k 4 m 3 ) + O ( 1 k m 1 2 − ϵ ) ) ⋅ ( m − k ) 2 ∑ L ≤ l 1 , l 2 ≤ 2 L Ξ ( l 1 , l 2 ) = ( 1 + O ( k 4 m 3 ) + O ( 1 k m 1 2 − ϵ ) ) ( E U , U ~ ( ∣ A ∣ ) ) 2 = ( 1 + O ( k 4 m 3 ) + O ( 1 k m 1 2 − ϵ ) ) ( E U , U ~ ( ∣ A ∣ ) ) 2 . \begin{aligned}
\left(1+O\left(\frac{k^4}{m^3}\right)+O\left(\frac{1}{km^{\frac{1}{2}-\epsilon}}\right)\right)\cdot(m-k)^2\sum_{L\le l_1,l_2\le2L}\Xi(l_1,l_2) \\
&=\left(1+O\left(\frac{k^4}{m^3}\right)+O\left(\frac{1}{km^{\frac{1}{2}-\epsilon}}\right)\right)\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2 \\
&=\left(1+O\left(\frac{k^4}{m^3}\right)+O\left(\frac{1}{km^{\frac{1}{2}-\epsilon}}\right)\right)\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2.
\end{aligned} ( 1 + O ( m 3 k 4 ) + O ( k m 2 1 − ϵ 1 ) ) ⋅ ( m − k ) 2 L ≤ l 1 , l 2 ≤ 2 L ∑ Ξ ( l 1 , l 2 ) = ( 1 + O ( m 3 k 4 ) + O ( k m 2 1 − ϵ 1 ) ) ( E U , U ( ∣ A ∣ ) ) 2 = ( 1 + O ( m 3 k 4 ) + O ( k m 2 1 − ϵ 1 ) ) ( E U , U ( ∣ A ∣ ) ) 2 .
Since ( E U , U ~ ( ∣ A ∣ ) ) 2 = O ( m 3 2 − ϵ k ) \left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2=O\left(m^{\frac{3}{2}-\epsilon}k\right) ( E U , U ( ∣ A ∣ ) ) 2 = O ( m 2 3 − ϵ k ) by Lemma 4.3 , we obtain
E U , U ~ ( ∣ P d i s c ∣ ) = ( E U , U ~ ( ∣ A ∣ ) ) 2 + O ( k 5 m 3 2 + ϵ ) + O ( m ) = ( E U , U ~ ( ∣ A ∣ ) ) 2 + O ( m max { 1 , 1 + 5 δ − ϵ } ) . \mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{disc}|)=\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2+O\left(\frac{k^5}{m^{\frac{3}{2}+\epsilon}}\right)+O(m)=\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2+O\left(m^{\max\{1,1+5\delta-\epsilon\}}\right). E U , U ( ∣ P d i sc ∣ ) = ( E U , U ( ∣ A ∣ ) ) 2 + O ( m 2 3 + ϵ k 5 ) + O ( m ) = ( E U , U ( ∣ A ∣ ) ) 2 + O ( m m a x { 1 , 1 + 5 δ − ϵ } ) .
Corollary 4.6. For m m m large, m 1 2 − δ ≤ k ≤ m 1 2 + δ m^{\frac{1}{2}-\delta}\le k\le m^{\frac{1}{2}+\delta} m 2 1 − δ ≤ k ≤ m 2 1 + δ , and ϵ \epsilon ϵ and δ \delta δ as per (1) ,
Var U , U ~ ( ∣ A ∣ ) ≤ C m max { 1 , 1 + 5 δ − ϵ } , \operatorname{Var}^{U,\widetilde{U}}(|\mathcal{A}|)\le Cm^{\max\{1,1+5\delta-\epsilon\}}, Var U , U ( ∣ A ∣ ) ≤ C m m a x { 1 , 1 + 5 δ − ϵ } , for some C > 0 C>0 C > 0 .
Proof. Note,
( E U , U ~ ( ∣ A ∣ 2 ) ) = E U , U ~ ( ∣ P n e s t ∣ ) + E U , U ~ ( ∣ P d i s c ∣ ) + E U , U ~ ( ∣ A ∣ ) . \left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|^2)\right)=\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{nest}|)+\mathbb{E}^{U,\widetilde{U}}(|\mathcal{P}_{disc}|)+\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|). ( E U , U ( ∣ A ∣ 2 ) ) = E U , U ( ∣ P n es t ∣ ) + E U , U ( ∣ P d i sc ∣ ) + E U , U ( ∣ A ∣ ) .
by (6) . Applying Lemmas 4.4, 4.5 and 4.3 , we obtain
E U , U ~ ( ∣ A ∣ 2 ) ≤ A m + ( E U , U ~ ( ∣ A ∣ ) ) 2 + A ′ m max { 1 , 1 + 5 δ − ϵ } + A ′ ′ m 3 / 4 − ϵ 2 k . \mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|^2)\le Am+\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2+A'm^{\max\{1,1+5\delta-\epsilon\}}+A''m^{3/4-\frac{\epsilon}{2}}\sqrt{k}. E U , U ( ∣ A ∣ 2 ) ≤ A m + ( E U , U ( ∣ A ∣ ) ) 2 + A ′ m m a x { 1 , 1 + 5 δ − ϵ } + A ′′ m 3/4 − 2 ϵ k .
Subtracting ( E U , U ~ ( ∣ A ∣ ) ) 2 \left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2 ( E U , U ( ∣ A ∣ ) ) 2 from both sides completes the proof.
Corollary 4.7. As m m m becomes large, there exists C ′ < ∞ C'<\infty C ′ < ∞ such that
P U , U ~ ( ∣ A ∣ ≤ m η ) ≤ C ′ m max { − 1 + ϵ + δ , − 1 + 6 δ } . \mathbb{P}^{U,\widetilde{U}}(|\mathcal{A}|\le m^\eta)\le C'm^{\max\{-1+\epsilon+\delta,-1+6\delta\}}. P U , U ( ∣ A ∣ ≤ m η ) ≤ C ′ m m a x { − 1 + ϵ + δ , − 1 + 6 δ } .
Proof. By Chebyshev’s inequality,
P U , U ~ ( ∣ A ∣ ≤ m η ) ≤ P U , U ~ ( ∣ A ∣ − E U , U ~ ( ∣ A ∣ ) ≥ E U , U ~ ( ∣ A ∣ ) − m η ) ≤ c Var U , U ~ ( ∣ A ∣ ) ( E U , U ~ ( ∣ A ∣ ) ) 2 , \mathbb{P}^{U,\widetilde{U}}(|\mathcal{A}|\le m^\eta)\le\mathbb{P}^{U,\widetilde{U}}\left(|\mathcal{A}|-\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\ge\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)-m^\eta\right)\le c\frac{\operatorname{Var}^{U,\widetilde{U}}(|\mathcal{A}|)}{\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2}, P U , U ( ∣ A ∣ ≤ m η ) ≤ P U , U ( ∣ A ∣ − E U , U ( ∣ A ∣ ) ≥ E U , U ( ∣ A ∣ ) − m η ) ≤ c ( E U , U ( ∣ A ∣ ) ) 2 Var U , U ( ∣ A ∣ ) ,
for some c > 0 c>0 c > 0 . This is because by our choice of parameters (1) , η < 1 − ϵ + δ 2 \eta<1-\frac{\epsilon+\delta}{2} η < 1 − 2 ϵ + δ , and thus E U , U ~ ( ∣ A ∣ ) \mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|) E U , U ( ∣ A ∣ ) dominates m η m^\eta m η in the limit. Plugging in our bounds, we obtain
Var U , U ~ ( ∣ A ∣ ) ( E U , U ~ ( ∣ A ∣ ) ) 2 ≤ C ′ m max { 1 , 1 + 5 δ − ϵ } m 3 / 2 − ϵ k = C ′ m max { − 1 2 + ϵ , − 1 2 + 5 δ } k − 1 ≤ C ′ m max { − 1 + ϵ + δ , − 1 + 6 δ } . \frac{\operatorname{Var}^{U,\widetilde{U}}(|\mathcal{A}|)}{\left(\mathbb{E}^{U,\widetilde{U}}(|\mathcal{A}|)\right)^2}\le C'\frac{m^{\max\{1,1+5\delta-\epsilon\}}}{m^{3/2-\epsilon}k}=C'm^{\max\{-\frac{1}{2}+\epsilon,-\frac{1}{2}+5\delta\}}k^{-1}\le C'm^{\max\{-1+\epsilon+\delta,-1+6\delta\}}. ( E U , U ( ∣ A ∣ ) ) 2 Var U , U ( ∣ A ∣ ) ≤ C ′ m 3/2 − ϵ k m m a x { 1 , 1 + 5 δ − ϵ } = C ′ m m a x { − 2 1 + ϵ , − 2 1 + 5 δ } k − 1 ≤ C ′ m m a x { − 1 + ϵ + δ , − 1 + 6 δ } .
The Random Mapping Model and Typicality of Good Event
Let ( K n , ∂ ) (K_n,\partial) ( K n , ∂ ) denote the undirected complete graph on n n n vertices with a distinguished vertex (root) ∂ \partial ∂ . We define the random mapping to be a random directed graph obtained as follows: define M \mathcal{M} M to be the collection of all functions f : V n → V n f: V_n \to V_n f : V n → V n such that f ( ∂ ) = ∂ f(\partial)=\partial f ( ∂ ) = ∂ . Note, there are n n − 1 n^{n-1} n n − 1 many such distinct functions. For f ∈ M f \in\mathcal{M} f ∈ M , we associate a directed graph, by placing the directed edge ( u , v ) (u,v) ( u , v ) vertices u u u and v v v if and only if f ( u ) = v f(u)=v f ( u ) = v . We ignore the self-loop at ∂ \partial ∂ . Since we are working with functions, note that every non-root vertex has an out-degree of exactly 1. We will denote this directed graph by K ⃗ n m a p \vec{K}_n^{map} K n ma p .
The following are known results on random mappings.
Lemma 5.1. We say that a vertex v v v is cyclic for F F F if F ( k ) ( v ) = v F^{(k)}(v)=v F ( k ) ( v ) = v for some k ∈ N k \in\mathbb{N} k ∈ N . Let L n L_n L n denote the number of cyclic vertices associated to a uniformly sampled F F F . We have that
P ( L n = k ) = k n n − k − 1 ( n − 1 k − 1 ) ( k − 1 ) ! n n − 1 = k n ∏ j = 1 k − 1 ( 1 − j n ) . \mathbb{P}(L_n=k)=\frac{kn^{n-k-1}\binom{n-1}{k-1}(k-1)!}{n^{n-1}}=\frac{k}{n}\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right). P ( L n = k ) = n n − 1 k n n − k − 1 ( k − 1 n − 1 ) ( k − 1 )! = n k j = 1 ∏ k − 1 ( 1 − n j ) .
Proof. There are ( n − 1 k − 1 ) \binom{n-1}{k-1} ( k − 1 n − 1 ) different choices for the k − 1 k-1 k − 1 cyclic vertices, since ∂ \partial ∂ is already counted. Cyclic vertices must get mapped to each other, and moreover the mappings must be one to one. Thus F F F acts as a permutation on the cyclic vertices other than ∂ \partial ∂ , and there are ( k − 1 ) ! (k-1)! ( k − 1 )! choices for the permutation. We now need to consider the possibilities for the other vertices. This corresponds to a labeled spanning forest, where the cyclic vertices are roots. There are k n n − k − 1 kn^{n-k-1} k n n − k − 1 such forests.
This gives us a robust bound on the typical number of cyclic vertices.
Lemma 5.2. For a ≤ 1 2 − δ a \le\frac{1}{2}-\delta a ≤ 2 1 − δ ,
P ( L n < n a ) ≤ n − 2 δ . \mathbb{P}(L_n<n^a)\le n^{-2\delta}. P ( L n < n a ) ≤ n − 2 δ .
Proof. We know that
P ( L n < n a ) = ∑ 1 ≤ k < n a k n ∏ j = 1 k − 1 ( 1 − j n ) ≤ ∑ 1 ≤ k < n a k n ≤ 1 n ( n a − 1 ) ( n a − 2 ) ≤ n 2 a − 1 ≤ n − 2 δ . \begin{aligned}
\mathbb{P}(L_n<n^a)=\sum_{1\le k<n^a}\frac{k}{n}\prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right) \\
&\le\sum_{1\le k<n^a}\frac{k}{n} \\
&\le\frac{1}{n}(n^a-1)(n^a-2)\le n^{2a-1}\le n^{-2\delta}.
\end{aligned} P ( L n < n a ) = 1 ≤ k < n a ∑ n k j = 1 ∏ k − 1 ( 1 − n j ) ≤ 1 ≤ k < n a ∑ n k ≤ n 1 ( n a − 1 ) ( n a − 2 ) ≤ n 2 a − 1 ≤ n − 2 δ .
Bounding the number of cyclic vertices allows us to control the number of connected components of the random mapping model, and thus our model as well.
Lemma 5.3. Let Comp \operatorname{Comp} Comp denote the collection of connected components of K ⃗ n m a p \vec{K}_n^{map} K n ma p . Then as n → ∞ n\to\infty n → ∞ ,
P ( ∣ Comp ∣ log n > 11 log 2 ) ≤ n − 2 δ . \mathbb{P}\left(\frac{|\operatorname{Comp}|}{\log n}>\frac{11}{\log2}\right)\le n^{-2\delta}. P ( log n ∣ Comp ∣ > log 2 11 ) ≤ n − 2 δ .
This result is rather well known, so we omit a detailed proof and provide a sketch. Later, we will argue that the same bound applies to Comp \operatorname{Comp} Comp as defined for K ⃗ n 1 \vec{K}_n^1 K n 1 . Thanks to a coupling commonly associated to Feller, appearing in [7 ] , it is known that the number of cycles of a uniform permutation on m m m letters can be represented as a sum of independent Bernoulli random variables. In particular, if Z m Z_m Z m denotes the number of cycles, then
Z m = ∑ k = 1 m I k , I k ∼ Ber ( k − 1 ) . (8) Z_m=\sum_{k=1}^{m}I_k,\quad I_k\sim\operatorname{Ber}(k^{-1}). \tag*{(8)} Z m = k = 1 ∑ m I k , I k ∼ Ber ( k − 1 ) . (8)
In particular, this allows us to conclude two things, the first being that
E ( Z m ) = log m + O ( 1 ) , \mathbb{E}(Z_m) = \log m + O(1), E ( Z m ) = log m + O ( 1 ) ,
by the well known asymptotics of the harmonic sum. Moreover, observe that as a consequence of the independence,
E ( 2 Z m ) = ∏ k = 1 m ( k − 1 k + 2 k ) = ∏ k = 1 m ( k + 1 k ) = m + 1. \mathbb{E}(2^{Z_m}) = \prod_{k=1}^{m} \left(\frac{k-1}{k}+\frac{2}{k}\right) = \prod_{k=1}^{m} \left(\frac{k+1}{k}\right) = m+1. E ( 2 Z m ) = k = 1 ∏ m ( k k − 1 + k 2 ) = k = 1 ∏ m ( k k + 1 ) = m + 1.
By Markov’s inequality,
P ( Z m ≥ t log m ) ≤ m + 1 2 t log m . \mathbb{P}(Z_m \ge t\log m) \le\frac{m+1}{2^{t\log m}}. P ( Z m ≥ t log m ) ≤ 2 t l o g m m + 1 .
Thus, taking t = 11 / log 2 t=11/\log2 t = 11/ log 2 , we find that
P ( Z log m ≥ 11 log 2 ) ≤ m − 10 . \mathbb{P}\left(\frac{Z}{\log m}\ge\frac{11}{\log2}\right)\le m^{-10}. P ( log m Z ≥ log 2 11 ) ≤ m − 10 .
Recall, the restriction of a random mapping to the cyclic vertices is a uniform permutation on those vertices. Since the cyclic vertices act as roots for the other vertices, the disjoint cycles of the permutation also index the connected components of the graph corresponding to the random map. Thus, given that the number of cyclic vertices is L n = m L_n=m L n = m , we immediately have that
P ( ∣ Comp ∣ > 11 log 2 log m | L n = m ) ≤ m − 10 . \mathbb{P}\left(|\operatorname{Comp}|>\frac{11}{\log2}\log m\middle|L_n=m\right)\le m^{-10}. P ( ∣ Comp ∣ > log 2 11 log m L n = m ) ≤ m − 10 .
Finally, observe that
P ( ∣ Comp ∣ ≤ 11 log 2 log n ) ≥ ∑ m ≥ n 1 2 − δ P ( ∣ Comp ∣ ≤ 11 log 2 log m | L n = m ) P ( L n = m ) ≥ ∑ m ≥ n 1 2 − δ ( 1 − n − 5 + 10 δ ) P ( L n = m ) ≥ ( 1 − n − 5 + 10 δ ) ( 1 − n − 2 δ ) . \begin{aligned}
\mathbb{P}\left(|\operatorname{Comp}|\le\frac{11}{\log2}\log n\right)
\ge\sum_{m\ge n^{\frac{1}{2}-\delta}}\mathbb{P}\left(|\operatorname{Comp}|\le\frac{11}{\log2}\log m\middle|L_n=m\right)\mathbb{P}(L_n=m) \\
&\ge\sum_{m\ge n^{\frac{1}{2}-\delta}}(1-n^{-5+10\delta})\mathbb{P}(L_n=m) \\
&\ge(1-n^{-5+10\delta})(1-n^{-2\delta}).
\end{aligned} P ( ∣ Comp ∣ ≤ log 2 11 log n ) ≥ m ≥ n 2 1 − δ ∑ P ( ∣ Comp ∣ ≤ log 2 11 log m L n = m ) P ( L n = m ) ≥ m ≥ n 2 1 − δ ∑ ( 1 − n − 5 + 10 δ ) P ( L n = m ) ≥ ( 1 − n − 5 + 10 δ ) ( 1 − n − 2 δ ) .
The final step follows from Lemma 5.2 . An important corollary is the following.
Corollary 5.4. As n → ∞ n\to\infty n → ∞ ,
P ( ∣ C max ∣ > n log 2 11 log n ) ≥ 1 − O ( n − 2 δ ) . \mathbb{P}\left(|C^{\max}|>\frac{n\log2}{11\log n}\right)\ge1-O(n^{-2\delta}). P ( ∣ C m a x ∣ > 11 log n n log 2 ) ≥ 1 − O ( n − 2 δ ) .
Proof. This follows from a direct application of Lemma 5.3 and the pigeonhole principle.
Given a component of size m m m , we now need to understand the size of the embedded cycle in that component. The procedure is almost identical to understanding the number of cyclic vertices. We now condition on the event that a collection of vertices U U U form the vertex set of a non boundary component. On this event, the structure of K ⃗ n 1 \vec{K}^{1}_{n} K n 1 restricted to these vertices is uniform amongst all cycle-bounded arborescences on those vertices, where the cycle length k k k must be greater than or equal to 2. This is the only difference as compared to the K ⃗ n 1 \vec{K}^{1}_{n} K n 1 case, the cycle can be a self loop corresponding to k = 1 k=1 k = 1 . We denote this conditional measure as P U \mathbb{P}^{U} P U , just as in Section 4.
Lemma 5.5. Let C m C_m C m denote the size of the cycle in a uniformly sampled cycle-bounded arborescence U U U where ∣ U ∣ = m |U|=m ∣ U ∣ = m , and self loops are not allowed. Then
P U ( C m = k ) = ( m k ) k ! ⋅ m m − k − 1 ∑ i = 2 m ( m i ) i ! ⋅ m m − i − 1 . \mathbb{P}^{U}(C_m=k)=\frac{\binom{m}{k}k!\cdot m^{m-k-1}}{\sum_{i=2}^{m}\binom{m}{i}i!\cdot m^{m-i-1}}. P U ( C m = k ) = ∑ i = 2 m ( i m ) i ! ⋅ m m − i − 1 ( k m ) k ! ⋅ m m − k − 1 .
Proof. First, we count the possibilities corresponding to C m = k C_m=k C m = k . Note that there are ( m k ) \binom{m}{k} ( k m ) choices for the k k k cyclic vertices. Next, there are ( k − 1 ) ! (k-1)! ( k − 1 )! many ways of ordering the cycle, up to shifts. Finally, by Cayley’s formula, there are k m m − k − 1 km^{m-k-1} k m m − k − 1 ways of constructing labeled forest with our cyclic vertices as roots. This yields
( m k ) ( k − 1 ) ! ⋅ k ⋅ m m − k − 1 . \binom{m}{k}(k-1)!\cdot k\cdot m^{m-k-1}. ( k m ) ( k − 1 )! ⋅ k ⋅ m m − k − 1 .
Next, the total number of cycle-bounded arborescences can now be obtained by summing the above expression over all k k k .
With this in mind, we can now compute a bound on the probability of a cycle being small.
Lemma 5.6. As m m m becomes large,
P U ( C m ∉ ( m 1 2 − δ , m 1 2 + δ ) ) ≤ m − δ . \mathbb{P}^{U}\left(C_m\notin\left(m^{\frac{1}{2}-\delta},m^{\frac{1}{2}+\delta}\right)\right)\le m^{-\delta}. P U ( C m ∈ / ( m 2 1 − δ , m 2 1 + δ ) ) ≤ m − δ .
Proof. Note that
P U ( C m ≤ m 1 2 − δ ) = ∑ 2 ≤ k ≤ m 1 2 − δ ( m k ) k ! ⋅ m m − k − 1 ∑ i = 2 m ( m i ) i ! ⋅ m m − i − 1 = ∑ 2 ≤ k ≤ m 1 2 − δ ∏ j = 2 k − 1 ( 1 − j m ) ∑ i = 2 m ( m i ) i ! ⋅ m − i . \mathbb{P}^{U}\left(C_m\le m^{\frac{1}{2}-\delta}\right)
=
\sum_{2\le k\le m^{\frac{1}{2}-\delta}}
\frac{\binom{m}{k}k!\cdot m^{m-k-1}}{\sum_{i=2}^{m}\binom{m}{i}i!\cdot m^{m-i-1}}
=
\sum_{2\le k\le m^{\frac{1}{2}-\delta}}
\frac{\prod_{j=2}^{k-1}\left(1-\frac{j}{m}\right)}{\sum_{i=2}^{m}\binom{m}{i}i!\cdot m^{-i}}. P U ( C m ≤ m 2 1 − δ ) = 2 ≤ k ≤ m 2 1 − δ ∑ ∑ i = 2 m ( i m ) i ! ⋅ m m − i − 1 ( k m ) k ! ⋅ m m − k − 1 = 2 ≤ k ≤ m 2 1 − δ ∑ ∑ i = 2 m ( i m ) i ! ⋅ m − i ∏ j = 2 k − 1 ( 1 − m j ) .
The trivial upper bound for the numerator suffices,
∑ 2 ≤ k ≤ m 1 2 − δ ∏ j = 2 k − 1 ( 1 − j m ) ≤ m 1 2 − δ . (9) \sum_{2\le k\le m^{\frac{1}{2}-\delta}}\prod_{j=2}^{k-1}\left(1-\frac{j}{m}\right)\le m^{\frac{1}{2}-\delta}. \tag*{(9)} 2 ≤ k ≤ m 2 1 − δ ∑ j = 2 ∏ k − 1 ( 1 − m j ) ≤ m 2 1 − δ . (9)
For C m ≥ m 1 2 + δ C_m\ge m^{\frac{1}{2}+\delta} C m ≥ m 2 1 + δ , we need the asymptotics of the numerator where the sum ranges over k ∈ ( m 1 2 + δ , m ] k\in(m^{\frac{1}{2}+\delta},m] k ∈ ( m 2 1 + δ , m ] . In this case, note that
∑ m 1 2 + δ ≤ k ≤ m ∏ j = 2 k − 1 ( 1 − j m ) ≤ ∑ m 1 2 + δ ≤ k ≤ m ∏ 2 ≤ j ≤ min { k − 1 , m 3 / 5 } ( 1 − j m ) . \sum_{m^{\frac{1}{2}+\delta}\le k\le m}\prod_{j=2}^{k-1}\left(1-\frac{j}{m}\right)
\le
\sum_{m^{\frac{1}{2}+\delta}\le k\le m}\prod_{2\le j\le\min\{k-1,m^{3/5}\}}\left(1-\frac{j}{m}\right). m 2 1 + δ ≤ k ≤ m ∑ j = 2 ∏ k − 1 ( 1 − m j ) ≤ m 2 1 + δ ≤ k ≤ m ∑ 2 ≤ j ≤ m i n { k − 1 , m 3/5 } ∏ ( 1 − m j ) .
The choice of 3 / 5 3/5 3/5 as the exponent of truncation is made for a purely aesthetic reason, it is the nicest fraction between 1 / 2 1/2 1/2 and 2 / 3 2/3 2/3 . Next, observe that we have
∑ m 1 2 + δ ≤ k ≤ m ∏ 2 ≤ j ≤ min { k − 1 , m 3 / 5 } ( 1 − j m ) ≤ ∑ m 1 2 + δ ≤ k ≤ m exp ( − ∑ 2 ≤ j ≤ min { k − 1 , m 3 / 5 } j m + O ( ( min { k − 1 , m 3 / 5 } ) 3 m 2 ) ) . \sum_{m^{\frac{1}{2}+\delta}\le k\le m}\prod_{2\le j\le\min\{k-1,m^{3/5}\}}\left(1-\frac{j}{m}\right)
\le
\sum_{m^{\frac{1}{2}+\delta}\le k\le m}\exp\left(-\sum_{2\le j\le\min\{k-1,m^{3/5}\}}\frac{j}{m}+O\left(\frac{\left(\min\{k-1,m^{3/5}\}\right)^3}{m^2}\right)\right). m 2 1 + δ ≤ k ≤ m ∑ 2 ≤ j ≤ m i n { k − 1 , m 3/5 } ∏ ( 1 − m j ) ≤ m 2 1 + δ ≤ k ≤ m ∑ exp − 2 ≤ j ≤ m i n { k − 1 , m 3/5 } ∑ m j + O ( m 2 ( min { k − 1 , m 3/5 } ) 3 ) .
The smallest value of k k k in the outer sum is m 1 2 + δ m^{\frac{1}{2}+\delta} m 2 1 + δ , and this yields an upper bound (since the sign in the exponential ahead of the dominant term is negative, the error vanishes since m 9 / 5 < m 2 m^{9/5}<m^2 m 9/5 < m 2 ). In particular, we obtain
∑ m 1 2 + δ ≤ k ≤ m ∏ j = 2 k − 1 ( 1 − j m ) ≤ m ⋅ exp ( − 1 2 m min { 2 δ , 1 5 } ) . (10) \sum_{m^{\frac{1}{2}+\delta}\le k\le m}\prod_{j=2}^{k-1}\left(1-\frac{j}{m}\right)
\le m\cdot\exp\left(-\frac{1}{2}m^{\min\{2\delta,\frac{1}{5}\}}\right). \tag*{(10)} m 2 1 + δ ≤ k ≤ m ∑ j = 2 ∏ k − 1 ( 1 − m j ) ≤ m ⋅ exp ( − 2 1 m m i n { 2 δ , 5 1 } ) . (10)
The last inequality holds for m m m sufficiently large. We then need a lower bound on the denominator, which is given by
∑ i = 2 m m ! ( m − i ) ! m − i = ∑ i = 1 m m ! ( m − i ) ! m − i − 1 = : I ( m ) − 1. \sum_{i=2}^{m}\frac{m!}{(m-i)!}m^{-i}
=
\sum_{i=1}^{m}\frac{m!}{(m-i)!}m^{-i}-1
=:I(m)-1. i = 2 ∑ m ( m − i )! m ! m − i = i = 1 ∑ m ( m − i )! m ! m − i − 1 =: I ( m ) − 1.
The sum can be represented by an integral, which will enable the use of Laplace asymptotics. Observe that
∫ 0 ∞ e − x ( 1 + x m ) m d x = ∫ 0 ∞ e − x ∑ i = 0 m ( m i ) ( x m ) i d x = I ( m ) + 1. \int_{0}^{\infty} e^{-x}\left(1+\frac{x}{m}\right)^m dx=\int_{0}^{\infty}e^{-x}\sum_{i=0}^{m}\binom{m}{i}\left(\frac{x}{m}\right)^i dx=I(m)+1. ∫ 0 ∞ e − x ( 1 + m x ) m d x = ∫ 0 ∞ e − x i = 0 ∑ m ( i m ) ( m x ) i d x = I ( m ) + 1.
Now, note that
∫ 0 ∞ e − x ( 1 + x m ) m d x = m ∫ 0 ∞ e − m u ( 1 + u ) m d u = m ∫ 0 ∞ e − m g ( u ) d u , \int_{0}^{\infty}e^{-x}\left(1+\frac{x}{m}\right)^m dx=m\int_{0}^{\infty}e^{-mu}(1+u)^mdu=m\int_{0}^{\infty}e^{-mg(u)}du, ∫ 0 ∞ e − x ( 1 + m x ) m d x = m ∫ 0 ∞ e − m u ( 1 + u ) m d u = m ∫ 0 ∞ e − m g ( u ) d u ,
where g ( u ) = u − log ( 1 + u ) g(u)=u-\log(1+u) g ( u ) = u − log ( 1 + u ) . Note that g g g is increasing, g ( 0 ) = 0 g(0)=0 g ( 0 ) = 0 , g ′ ( 0 ) = 0 g'(0)=0 g ′ ( 0 ) = 0 and is convex. Moreover, g ′ ′ ( 0 ) = 1 > 0 g''(0)=1>0 g ′′ ( 0 ) = 1 > 0 . Thus,
∫ 0 ∞ e − m g ( u ) d u ≥ C m \int_{0}^{\infty}e^{-mg(u)}du\ge\frac{C}{\sqrt{m}} ∫ 0 ∞ e − m g ( u ) d u ≥ m C
where the constant C C C depends on g ′ ′ ( 0 ) > 0 g''(0)>0 g ′′ ( 0 ) > 0 . Thus,
I ( m ) ≥ C m − 1. (11) I(m)\ge C\sqrt{m}-1. \tag*{(11)} I ( m ) ≥ C m − 1. (11)
For the lower tail we obtain by combining (9) and (11)
P U ( C m ≤ m 1 2 − δ ) ≤ m 1 2 − δ C m − 2 ≤ m − δ C ′ . \mathbb{P}^{U}\left(C_m\le m^{\frac{1}{2}-\delta}\right)\le\frac{m^{\frac{1}{2}-\delta}}{C\sqrt{m}-2}\le\frac{m^{-\delta}}{C'}. P U ( C m ≤ m 2 1 − δ ) ≤ C m − 2 m 2 1 − δ ≤ C ′ m − δ .
For the upper tail, we obtain
P U ( C m ≥ m 1 2 + δ ) ≤ m ⋅ exp ( − 1 2 m min { 2 δ , 1 } ) ≤ m − δ , \mathbb{P}^{U}\left(C_m\ge m^{\frac{1}{2}+\delta}\right)\le m\cdot\exp\left(-\frac{1}{2}m^{\min\{2\delta,1\}}\right)\le m^{-\delta}, P U ( C m ≥ m 2 1 + δ ) ≤ m ⋅ exp ( − 2 1 m m i n { 2 δ , 1 } ) ≤ m − δ ,
the final inequality holding for m m m sufficiently large.
We now have all the ingredients required to show that our good event E ε , δ , η \mathcal{E}_{\varepsilon,\delta,\eta} E ε , δ , η is typical for K ⃗ n 1 \vec{K}^{1}_{n} K n 1 . The main difference between K ⃗ n m a p \vec{K}^{map}_{n} K n ma p and K ⃗ n 1 \vec{K}^{1}_{n} K n 1 is that self-loops are permitted for the random mapping, corresponding to the fixed points of the associated functions. To set up a correspondence, let
M 0 = { f : V n → V n : f ( ∂ ) = ∂ , f ( u ) ≠ u ∀ u ∈ V n ∖ { ∂ } } . \mathcal{M}_{0}=\{f:V_n\to V_n:f(\partial)=\partial,\ f(u)\ne u\ \forall u\in V_n\setminus\{\partial\}\}. M 0 = { f : V n → V n : f ( ∂ ) = ∂ , f ( u ) = u ∀ u ∈ V n ∖ { ∂ }} .
Note that for every realization of K ⃗ n 1 \vec{K}^{1}_{n} K n 1 , we can associate a unique random mapping in M 0 \mathcal{M}_0 M 0 . Thus, the graph associated to the uniform measure on M 0 \mathcal{M}_0 M 0 is equal in distribution to K ⃗ n 1 \vec{K}^{1}_{n} K n 1 , with the self-loop at ∂ \partial ∂ ignored. It is also relatively straightforward to see that
∣ M 0 ∣ = ( n − 1 ) n − 1 . |\mathcal{M}_0|=(n-1)^{n-1}. ∣ M 0 ∣ = ( n − 1 ) n − 1 .
The following lemma is immediate:
Lemma 5.7. Let M \mathcal{M} M denote the set of all functions f : V n → V n f:V_n\to V_n f : V n → V n such that f ( ∂ ) = ∂ f(\partial)=\partial f ( ∂ ) = ∂ . Let F F F be uniformly sampled from M \mathcal{M} M . Then
P ( F ∈ M 0 ) = ( n − 1 ) n − 1 n n − 1 ↘ e − 1 , \mathbb{P}(F\in\mathcal{M}_0)=\frac{(n-1)^{n-1}}{n^{n-1}}\searrow e^{-1}, P ( F ∈ M 0 ) = n n − 1 ( n − 1 ) n − 1 ↘ e − 1 , as n → ∞ n\to\infty n → ∞ .
This lemma enables us to translate results from the random mapping model to our setting, especially probability bounds for rare events. The following is immediately clear for a random mapping F F F and a collection A \mathcal{A} A ,
P ( F ∈ A ∣ F ∈ M 0 ) ≤ e ⋅ P ( F ∈ A ) . (12) \mathbb{P}(F\in\mathcal{A}\mid F\in\mathcal{M}_0)\le e\cdot\mathbb{P}(F\in\mathcal{A}). \tag*{(12)} P ( F ∈ A ∣ F ∈ M 0 ) ≤ e ⋅ P ( F ∈ A ) . (12)
In particular, Lemma 5.3 and any corollaries all immediately admit corresponding versions for K ⃗ n 1 \vec{K}^{1}_{n} K n 1 . When we refer to these lemmas in the following proof, we are referring to the versions for K ⃗ n 1 \vec{K}^{1}_{n} K n 1 , in combination with (5.4).
Proof of Lemma 3.4 . Denote by
E 1 = { ∣ Comp ∣ ≤ 11 log 2 log n } , E 2 = { ∣ C max ∣ 1 2 − δ < ∣ Cycle max ∣ < ∣ C max ∣ 1 2 + δ } \mathcal{E}_1=\left\{|\operatorname{Comp}|\leq\frac{11}{\log2}\log n\right\},\quad\mathcal{E}_2=\left\{|C^{\max}|^{\frac{1}{2}-\delta}<|\operatorname{Cycle}_{\max}|<|C^{\max}|^{\frac{1}{2}+\delta}\right\} E 1 = { ∣ Comp ∣ ≤ log 2 11 log n } , E 2 = { ∣ C m a x ∣ 2 1 − δ < ∣ Cycle m a x ∣ < ∣ C m a x ∣ 2 1 + δ }
and
E 3 = { ∣ A ϵ ∣ > ( log 2 11 n log n ) η } . \mathcal{E}_3=\left\{|\mathcal{A}_{\epsilon}|>\left(\frac{\log2}{11}\frac{n}{\log n}\right)^{\eta}\right\}. E 3 = { ∣ A ϵ ∣ > ( 11 log 2 log n n ) η } .
Clearly,
E ϵ , δ , η = E 1 ∩ E 2 ∩ E 3 , \mathcal{E}_{\epsilon,\delta,\eta}=\mathcal{E}_1\cap\mathcal{E}_2\cap\mathcal{E}_3, E ϵ , δ , η = E 1 ∩ E 2 ∩ E 3 ,
and thus
E ϵ , δ , η c = E 1 c ∪ ( E 2 c ∩ E 1 ) ∪ ( E 3 c ∩ E 2 ∩ E 1 ) . \mathcal{E}_{\epsilon,\delta,\eta}^{c}=\mathcal{E}_1^{c}\cup(\mathcal{E}_2^{c}\cap\mathcal{E}_1)\cup(\mathcal{E}_3^{c}\cap\mathcal{E}_2\cap\mathcal{E}_1). E ϵ , δ , η c = E 1 c ∪ ( E 2 c ∩ E 1 ) ∪ ( E 3 c ∩ E 2 ∩ E 1 ) .
Applying Lemma 5.3 , we know that
P ( E 1 c ) = O ( n − 2 δ ) . \mathbb{P}(\mathcal{E}_1^{c})=O(n^{-2\delta}). P ( E 1 c ) = O ( n − 2 δ ) .
Next, for P ( E 2 c ∩ E 1 ) \mathbb{P}(\mathcal{E}_2^{c}\cap\mathcal{E}_1) P ( E 2 c ∩ E 1 ) , we split the probability of the intersection in terms of conditioning,
P ( E 2 c ∩ E 1 ) ≤ ∑ m ≥ n t log n ∑ ∣ U ∣ = m P ( E 2 c ∣ C max = U ) P ( C max = U ) , \mathbb{P}(\mathcal{E}_2^{c}\cap\mathcal{E}_1)\leq\sum_{m\geq\frac{n}{t\log n}}\sum_{|U|=m}\mathbb{P}(\mathcal{E}_2^{c}\mid C^{\max}=U)\mathbb{P}(C^{\max}=U), P ( E 2 c ∩ E 1 ) ≤ m ≥ t l o g n n ∑ ∣ U ∣ = m ∑ P ( E 2 c ∣ C m a x = U ) P ( C m a x = U ) ,
where t = 11 / log 2 t=11/\log2 t = 11/ log 2 . We begin the sum at n t log n \frac{n}{t\log n} t l o g n n because of the pigeonhole argument of Corollary 5.4 . By Lemma 5.6 , on the event ∣ U ∣ = m |U|=m ∣ U ∣ = m ,
P ( Cycle max ∉ ( m 1 2 − δ , m 1 2 + δ ) | C max = U ) ≤ C m − δ . \mathbb{P}\left(\operatorname{Cycle}_{\max}\notin\left(m^{\frac{1}{2}-\delta},m^{\frac{1}{2}+\delta}\right)\middle|C^{\max}=U\right)\leq Cm^{-\delta}. P ( Cycle m a x ∈ / ( m 2 1 − δ , m 2 1 + δ ) C m a x = U ) ≤ C m − δ .
Thus,
P ( E 2 c ∩ E 1 ) ≤ C t − δ ( n log n ) − δ ∑ m ≥ n t log n ∑ ∣ U ∣ = m P ( C max = U ) = O ( ( n log n ) − δ ) . \begin{aligned}
\mathbb{P}(\mathcal{E}_2^{c}\cap\mathcal{E}_1)\leq Ct^{-\delta}\left(\frac{n}{\log n}\right)^{-\delta}\sum_{m\geq\frac{n}{t\log n}}\sum_{|U|=m}\mathbb{P}(C^{\max}=U) \\
&=O\left(\left(\frac{n}{\log n}\right)^{-\delta}\right).
\end{aligned} P ( E 2 c ∩ E 1 ) ≤ C t − δ ( log n n ) − δ m ≥ t l o g n n ∑ ∣ U ∣ = m ∑ P ( C m a x = U ) = O ( ( log n n ) − δ ) .
Finally, we need to deal with P ( E 3 c ∩ E 2 ∩ E 1 ) \mathbb{P}(\mathcal{E}_3^{c}\cap\mathcal{E}_2\cap\mathcal{E}_1) P ( E 3 c ∩ E 2 ∩ E 1 ) . For ease of notation, we define
E m , k : = { ∣ C max ∣ = m , ∣ Cycle max ∣ = k } . \mathcal{E}_{m,k}:=\{|C^{\max}|=m,\ |\operatorname{Cycle}_{\max}|=k\}. E m , k := { ∣ C m a x ∣ = m , ∣ Cycle m a x ∣ = k } .
Note that we may further disjointly partition E m , k \mathcal{E}_{m,k} E m , k as
E m , k = ⋃ ∣ U ∣ = m U ~ ⊂ U , ∣ U ~ ∣ = k { C max = U , Cycle max = U ~ } . \mathcal{E}_{m,k}=\bigcup_{\substack{|U|=m\\ \widetilde{U}\subset U,\ |\widetilde{U}|=k}}\{C^{\max}=U,\ \operatorname{Cycle}_{\max}=\widetilde{U}\}. E m , k = ∣ U ∣ = m U ⊂ U , ∣ U ∣ = k ⋃ { C m a x = U , Cycle m a x = U } .
Note that
P ( E 3 c ∩ E 1 ∩ E 2 ) ≤ ∑ m ≥ n t log n ∑ m 1 2 − δ ≤ k ≤ m 1 2 + δ ∑ ∣ U ∣ = m U ~ ⊂ U , ∣ U ~ ∣ = k P ( { C max = U } ∩ { Cycle max = U ~ } ∩ { ∣ A ϵ ∣ ≤ m η } ) = ∑ m ≥ n t log n ∑ m 1 2 − δ ≤ k ≤ m 1 2 + δ ∑ ∣ U ∣ = m U ~ ⊂ U , ∣ U ~ ∣ = k P U , U ~ ( ∣ A ϵ ∣ ≤ m η ) P ( C max = U , Cycle max = U ~ ) . \begin{aligned}
\mathbb{P}(\mathcal{E}_3^{c}\cap\mathcal{E}_1\cap\mathcal{E}_2)\leq
\sum_{m\geq\frac{n}{t\log n}}\sum_{m^{\frac{1}{2}-\delta}\leq k\leq m^{\frac{1}{2}+\delta}}\sum_{\substack{|U|=m\\ \widetilde{U}\subset U,\ |\widetilde{U}|=k}}
\mathbb{P}\left(\{C^{\max}=U\}\cap\{\operatorname{Cycle}_{\max}=\widetilde{U}\}\cap\{|\mathcal{A}_{\epsilon}|\leq m^{\eta}\}\right) \\
&=\sum_{m\geq\frac{n}{t\log n}}\sum_{m^{\frac{1}{2}-\delta}\leq k\leq m^{\frac{1}{2}+\delta}}\sum_{\substack{|U|=m\\ \widetilde{U}\subset U,\ |\widetilde{U}|=k}}
\mathbb{P}^{U,\widetilde{U}}(|\mathcal{A}_{\epsilon}|\leq m^{\eta})\mathbb{P}(C^{\max}=U,\operatorname{Cycle}_{\max}=\widetilde{U}).
\end{aligned} P ( E 3 c ∩ E 1 ∩ E 2 ) ≤ m ≥ t l o g n n ∑ m 2 1 − δ ≤ k ≤ m 2 1 + δ ∑ ∣ U ∣ = m U ⊂ U , ∣ U ∣ = k ∑ P ( { C m a x = U } ∩ { Cycle m a x = U } ∩ { ∣ A ϵ ∣ ≤ m η } ) = m ≥ t l o g n n ∑ m 2 1 − δ ≤ k ≤ m 2 1 + δ ∑ ∣ U ∣ = m U ⊂ U , ∣ U ∣ = k ∑ P U , U ( ∣ A ϵ ∣ ≤ m η ) P ( C m a x = U , Cycle m a x = U ) .
Next, we apply Corollary 4.7. Plugging in, we obtain
P ( { ∣ A ϵ ∣ ≤ ( n t log n ) η } ∩ E 1 ∩ E 2 ) ≤ ∑ m ≥ n t log n ∑ k = ⌈ m 1 2 − δ ⌉ ⌊ m 1 2 + δ ⌋ C m − 1 + max { ϵ + δ , 6 δ } ∑ ∣ U ∣ = m U ~ ⊂ U , ∣ U ~ ∣ = k P ( C max = U , C y c l e max = U ~ ) ≤ ∑ m ≥ n t log n C m − 1 + max { ϵ + δ , 6 δ } ∑ m 1 2 − δ ≤ k ≤ m 1 2 + δ P ( E m , k ) ≤ C ′ ′ ( n log n ) − 1 + max { ϵ + δ , 6 δ } ∑ m , k P ( E m , k ) ≤ C ′ ′ ( n log n ) − 1 + max { ϵ + δ , 6 δ } . \begin{aligned}
\mathbb{P}\left(\left\{|\mathcal{A}_{\epsilon}| \le\left(\frac{n}{t\log n}\right)^{\eta}\right\}\cap\mathcal{E}_{1}\cap\mathcal{E}_{2}\right)
\le\sum_{m\ge\frac{n}{t\log n}}\sum_{k=\lceil m^{\frac{1}{2}-\delta}\rceil}^{\lfloor m^{\frac{1}{2}+\delta}\rfloor} C m^{-1+\max\{\epsilon+\delta,6\delta\}} \sum_{\substack{|U|=m\\ \widetilde{U}\subset U,|\widetilde{U}|=k}} \mathbb{P}\left(\mathcal{C}^{\max}=U,\mathop{\rm Cycle}\nolimits_{\max}=\widetilde{U}\right) \\
&\le\sum_{m\ge\frac{n}{t\log n}} C m^{-1+\max\{\epsilon+\delta,6\delta\}} \sum_{m^{\frac{1}{2}-\delta}\le k\le m^{\frac{1}{2}+\delta}} \mathbb{P}(\mathcal{E}_{m,k}) \\
&\le C''\left(\frac{n}{\log n}\right)^{-1+\max\{\epsilon+\delta,6\delta\}}\sum_{m,k}\mathbb{P}(\mathcal{E}_{m,k})
\le C''\left(\frac{n}{\log n}\right)^{-1+\max\{\epsilon+\delta,6\delta\}}.
\end{aligned} P ( { ∣ A ϵ ∣ ≤ ( t log n n ) η } ∩ E 1 ∩ E 2 ) ≤ m ≥ t l o g n n ∑ k = ⌈ m 2 1 − δ ⌉ ∑ ⌊ m 2 1 + δ ⌋ C m − 1 + m a x { ϵ + δ , 6 δ } ∣ U ∣ = m U ⊂ U , ∣ U ∣ = k ∑ P ( C m a x = U , Cycle m a x = U ) ≤ m ≥ t l o g n n ∑ C m − 1 + m a x { ϵ + δ , 6 δ } m 2 1 − δ ≤ k ≤ m 2 1 + δ ∑ P ( E m , k ) ≤ C ′′ ( log n n ) − 1 + m a x { ϵ + δ , 6 δ } m , k ∑ P ( E m , k ) ≤ C ′′ ( log n n ) − 1 + m a x { ϵ + δ , 6 δ } .
For the last bound, we have used the fact that max { ϵ + δ , 6 δ } < 1 \max\{\epsilon+\delta,6\delta\}<1 max { ϵ + δ , 6 δ } < 1 , as per (1) .
Extension to General Weights
In our bounds for the error accumulated at each step of repair, we conditioned on a specific outcome of K ⃗ n 1 \vec{K}_{n}^{1} K n 1 . In particular, for a given vertex, we conditioned on the knowledge of which one of its outgoing edges has minimal weight. When the edge weights are i.i.d. exponential, the memoryless property makes this conditioning particularly tractable. That being said, all our error bounds can be adapted to the setting of general weights subject to the hypothesis in Theorem 1.5 . To reiterate, the key features of the exponential family that we use are the following. Let { Y i } i = 1 n \{Y_i\}_{i=1}^{n} { Y i } i = 1 n be a family of i.i.d. Exponential(1) random variables. Then
If J = argmin 1 ≤ i ≤ n { Y i } J=\operatorname*{argmin}_{1\le i\le n}\{Y_i\} J = argmin 1 ≤ i ≤ n { Y i } then Y J Y_J Y J is exponentially distributed with mean 1 / n 1/n 1/ n .
Conditioned on J J J , the random variables Y k − Y J Y_k-Y_J Y k − Y J for k ≠ J k\ne J k = J are i.i.d. Exponential(1).
We will build analogues of the above properties in the following lemmas, that extend the exponential case to the general family of random variables. Note that this family includes uniform random variables, as well as the absolute value of α \alpha α -stable random variables for α ∈ ( 1 , 2 ] \alpha\in(1,2] α ∈ ( 1 , 2 ] .
In the following lemma we study the asymptotic properties of the minimum of m m m random variables.
Lemma 6.1. Let X 1 , X 2 , … , X m X_1,X_2,\ldots,X_m X 1 , X 2 , … , X m be non-negative i.i.d. continuous random variables with density function p p p , which has the following properties:
p p p is continuous at 0 0 0 ,
p ( 0 ) > 0 p(0)>0 p ( 0 ) > 0 ,
∫ 0 ∞ x p ( x ) d x < ∞ \int_{0}^{\infty}xp(x)\,dx<\infty ∫ 0 ∞ x p ( x ) d x < ∞ .
Then the following hold.
For all integers k ≥ 1 k\ge1 k ≥ 1 , the k k k -th moment of the minimum satisfies
lim m → ∞ m k E ( min { X 1 , X 2 , … , X m } k ) = k ! p ( 0 ) k . \lim_{m\to\infty}m^k\mathbb{E}\left(\min\{X_1,X_2,\ldots,X_m\}^k\right)=\frac{k!}{p(0)^k}. m → ∞ lim m k E ( min { X 1 , X 2 , … , X m } k ) = p ( 0 ) k k ! . Let q ( m ) q^{(m)} q ( m ) denote the density of m ⋅ min { X 1 , X 2 , … , X m } m\cdot\min\{X_1,X_2,\ldots,X_m\} m ⋅ min { X 1 , X 2 , … , X m } . Then q ( m ) ( 0 ) = p ( 0 ) q^{(m)}(0)=p(0) q ( m ) ( 0 ) = p ( 0 ) , and there exist ϵ , c > 0 \epsilon,c>0 ϵ , c > 0 such that q ( m ) ( x ) ≥ c q^{(m)}(x)\ge c q ( m ) ( x ) ≥ c for all x ∈ [ 0 , ϵ ] x\in[0,\epsilon] x ∈ [ 0 , ϵ ] .
Proof. Let F ( x ) F(x) F ( x ) be the distribution function of X 1 X_1 X 1 and Y m = min { X 1 , X 2 , … , X m } Y_m=\min\{X_1,X_2,\ldots,X_m\} Y m = min { X 1 , X 2 , … , X m } . We can express the moments of Y m Y_m Y m in terms of its tails to get
E ( Y m k ) = ∫ 0 ∞ k x k − 1 P ( Y m > x ) d x = ∫ 0 ∞ k x k − 1 ( 1 − F ( x ) ) m d x . (13) \mathbb{E}(Y_m^k)=\int_{0}^{\infty}kx^{k-1}\mathbb{P}(Y_m>x)\,dx=\int_{0}^{\infty}kx^{k-1}(1-F(x))^m\,dx. \tag*{(13)} E ( Y m k ) = ∫ 0 ∞ k x k − 1 P ( Y m > x ) d x = ∫ 0 ∞ k x k − 1 ( 1 − F ( x ) ) m d x . (13)
Assuming t = m x t=mx t = m x , we get
m k E ( Y m k ) = k ∫ 0 ∞ t k − 1 ( 1 − F ( t m ) ) m d t . (14) m^k\mathbb{E}(Y_m^k)=k\int_0^\infty t^{k-1}\left(1-F\left(\frac{t}{m}\right)\right)^m\,dt. \tag*{(14)} m k E ( Y m k ) = k ∫ 0 ∞ t k − 1 ( 1 − F ( m t ) ) m d t . (14)
Now using a Taylor expansion of F F F up to the linear term, and since F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 we have
F ( x ) = p ( 0 ) x + o ( x ) F(x)=p(0)x+o(x) F ( x ) = p ( 0 ) x + o ( x )
as x ↓ 0 x\downarrow0 x ↓ 0 . For any t ≥ 0 t\geq0 t ≥ 0 ,
m F ( t m ) → p ( 0 ) t , mF\left(\frac{t}{m}\right)\to p(0)t, m F ( m t ) → p ( 0 ) t ,
as m → ∞ m\to\infty m → ∞ . Consequently, as m → ∞ m\to\infty m → ∞ ,
( 1 − F ( t m ) ) m → e − p ( 0 ) t . \left(1-F\left(\frac{t}{m}\right)\right)^m\to e^{-p(0)t}. ( 1 − F ( m t ) ) m → e − p ( 0 ) t .
Thus the integrand in 6.1 converges pointwise to t k − 1 e − p ( 0 ) t t^{k-1}e^{-p(0)t} t k − 1 e − p ( 0 ) t . From the continuity of p p p at 0 0 0 we can consider a δ > 0 \delta>0 δ > 0 , such that for all 0 ≤ x ≤ δ 0\leq x\leq\delta 0 ≤ x ≤ δ ,
F ( x ) ≥ p ( 0 ) 2 x . F(x)\geq\frac{p(0)}{2}x. F ( x ) ≥ 2 p ( 0 ) x .
Now
m k E ( Y m k ) = ∫ 0 δ m k k x k − 1 ( 1 − F ( x ) ) m d x + ∫ δ ∞ m k k x k − 1 ( 1 − F ( x ) ) m d x . (15) m^k\mathbb{E}(Y_m^k)=\int_0^\delta m^k kx^{k-1}(1-F(x))^m\,dx+\int_\delta^\infty m^k kx^{k-1}(1-F(x))^m\,dx. \tag*{(15)} m k E ( Y m k ) = ∫ 0 δ m k k x k − 1 ( 1 − F ( x ) ) m d x + ∫ δ ∞ m k k x k − 1 ( 1 − F ( x ) ) m d x . (15)
For the second term of 6.2 we have, if m > k m>k m > k ,
∫ δ ∞ m k k x k − 1 ( 1 − F ( x ) ) m d x ≤ m k ( 1 − F ( δ ) ) m − k ∫ δ ∞ k x k − 1 ( 1 − F ( x ) ) k d x ≤ m k ( 1 − F ( δ ) ) m − k E ( Y k k ) \begin{aligned}
\int_\delta^\infty m^k kx^{k-1}(1-F(x))^m\,dx\leq m^k(1-F(\delta))^{m-k}\int_\delta^\infty kx^{k-1}(1-F(x))^k\,dx \\
&\leq m^k(1-F(\delta))^{m-k}\mathbb{E}(Y_k^k)
\end{aligned} ∫ δ ∞ m k k x k − 1 ( 1 − F ( x ) ) m d x ≤ m k ( 1 − F ( δ ) ) m − k ∫ δ ∞ k x k − 1 ( 1 − F ( x ) ) k d x ≤ m k ( 1 − F ( δ ) ) m − k E ( Y k k )
where Y k Y_k Y k is the minimum of k k k independent variables with density p p p . Notice this term decays exponentially in m m m because F ( δ ) > 0 F(\delta)>0 F ( δ ) > 0 and E ( Y k k ) ≤ ∏ i = 1 k E ( X i ) = E ( X 1 ) k \mathbb{E}(Y_k^k)\leq\prod_{i=1}^k\mathbb{E}(X_i)=\mathbb{E}(X_1)^k E ( Y k k ) ≤ ∏ i = 1 k E ( X i ) = E ( X 1 ) k which is finite by hypothesis. When 0 ≤ t ≤ m δ 0\leq t\leq m\delta 0 ≤ t ≤ m δ , ( 1 − F ( t / m ) ) m ≤ e − p ( 0 ) t / 2 (1-F(t/m))^m\leq e^{-p(0)t/2} ( 1 − F ( t / m ) ) m ≤ e − p ( 0 ) t /2 and t k − 1 e − p ( 0 ) t / 2 t^{k-1}e^{-p(0)t/2} t k − 1 e − p ( 0 ) t /2 is integrable on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) . By dominated convergence theorem and the fact that ( 1 − F ( t / m ) ) m → e − p ( 0 ) t (1-F(t/m))^m\to e^{-p(0)t} ( 1 − F ( t / m ) ) m → e − p ( 0 ) t , we obtain
lim m → ∞ m k E ( Y m k ) = lim m → ∞ k ∫ 0 m δ t k − 1 ( 1 − F ( t m ) ) m d t = k ∫ 0 ∞ t k − 1 e − p ( 0 ) t d t = k Γ ( k ) p ( 0 ) k = k ! p ( 0 ) k . \lim_{m\to\infty}m^k\mathbb{E}(Y_m^k)=\lim_{m\to\infty}k\int_0^{m\delta}t^{k-1}\left(1-F\left(\frac{t}{m}\right)\right)^m\,dt=k\int_0^\infty t^{k-1}e^{-p(0)t}\,dt=\frac{k\Gamma(k)}{p(0)^k}=\frac{k!}{p(0)^k}. m → ∞ lim m k E ( Y m k ) = m → ∞ lim k ∫ 0 m δ t k − 1 ( 1 − F ( m t ) ) m d t = k ∫ 0 ∞ t k − 1 e − p ( 0 ) t d t = p ( 0 ) k k Γ ( k ) = p ( 0 ) k k ! .
As for the density, let r r r denote the density of min { X 1 , X 2 , ⋯ , X m } \min\{X_1,X_2,\cdots,X_m\} min { X 1 , X 2 , ⋯ , X m } . Then
r ( t ) = − d d t P ( min { X 1 , X 2 , ⋯ , X m } > t ) = − d d t ( P ( X 1 > t ) ) m = − m ( P ( X 1 > t ) ) m − 1 d d t P ( X 1 > t ) = m ( P ( X 1 > t ) ) m − 1 p ( t ) \begin{aligned}
r(t)=-\frac{d}{dt}\mathbb{P}(\min\{X_1,X_2,\cdots,X_m\}>t) \\
&=-\frac{d}{dt}\left(\mathbb{P}(X_1>t)\right)^m=-m\left(\mathbb{P}(X_1>t)\right)^{m-1}\frac{d}{dt}\mathbb{P}(X_1>t)=m\left(\mathbb{P}(X_1>t)\right)^{m-1}p(t)
\end{aligned} r ( t ) = − d t d P ( min { X 1 , X 2 , ⋯ , X m } > t ) = − d t d ( P ( X 1 > t ) ) m = − m ( P ( X 1 > t ) ) m − 1 d t d P ( X 1 > t ) = m ( P ( X 1 > t ) ) m − 1 p ( t )
Next, note that
q ( m ) ( t ) = 1 m r ( t m ) = ( P ( X 1 > t m ) ) m − 1 p ( t ) . q^{(m)}(t)=\frac{1}{m}r\left(\frac{t}{m}\right)=\left(\mathbb{P}\left(X_1>\frac{t}{m}\right)\right)^{m-1}p(t). q ( m ) ( t ) = m 1 r ( m t ) = ( P ( X 1 > m t ) ) m − 1 p ( t ) .
Since p p p is continuous at 0 0 0 , there exists ε > 0 \varepsilon>0 ε > 0 such that p ( t ) > p ( 0 ) 2 p(t)>\frac{p(0)}{2} p ( t ) > 2 p ( 0 ) for all t ∈ [ 0 , ε ] t\in[0,\varepsilon] t ∈ [ 0 , ε ] . Thus, for such t t t ,
q ( m ) ( t ) ≥ ( 1 − ∫ 0 ε / m p ( t ) d t ) m − 1 p ( t ) ≥ ( 1 − p ( 0 ) ε 2 m ) m − 1 p ( 0 ) 2 ≥ p ( 0 ) 4 e − p ( 0 ) ε 2 . q^{(m)}(t)\geq\left(1-\int_0^{\varepsilon/m}p(t)\,dt\right)^{m-1}p(t)\geq\left(1-\frac{p(0)\varepsilon}{2m}\right)^{m-1}\frac{p(0)}{2}\geq\frac{p(0)}{4}e^{-\frac{p(0)\varepsilon}{2}}. q ( m ) ( t ) ≥ ( 1 − ∫ 0 ε / m p ( t ) d t ) m − 1 p ( t ) ≥ ( 1 − 2 m p ( 0 ) ε ) m − 1 2 p ( 0 ) ≥ 4 p ( 0 ) e − 2 p ( 0 ) ε .
We can also get the centred moments.
Lemma 6.3. Let X 1 , X 2 , … , X m X_1,X_2,\ldots,X_m X 1 , X 2 , … , X m be non-negative independent random variables with densities p 1 , … , p m p_1,\ldots,p_m p 1 , … , p m respectively and finite expectation. Moreover, assume that p i p_i p i are continuous at 0 0 0 , and that exist ε > 0 \varepsilon>0 ε > 0 and c > 0 c>0 c > 0 , such that
p i ( x ) > c for all x ∈ [ 0 , ε ] and E ( X i ) uniformly bounded p_i(x)>c\text{ for all }x\in[0,\varepsilon]\text{ and }\mathbb{E}(X_i)\text{ uniformly bounded} p i ( x ) > c for all x ∈ [ 0 , ε ] and E ( X i ) uniformly bounded for all $1\leq i\leq m, then
E ( min { X 1 , … , X m } ) = O ( 1 m ) . \mathbb{E}(\min\{X_1,\ldots,X_m\})=O\left(\frac{1}{m}\right). E ( min { X 1 , … , X m }) = O ( m 1 ) .
Proof. Let
M m : = min { X 1 , … , X m } , M_m:=\min\{X_1,\ldots,X_m\}, M m := min { X 1 , … , X m } ,
and F i F_i F i be the distribution function of X i X_i X i . Now
E ( M m ) = ∫ 0 ∞ P ( M m > x ) d x = ∫ 0 ∞ ∏ i = 1 m ( 1 − F i ( x ) ) d x , \mathbb{E}(M_m)=\int_{0}^{\infty}\mathbb{P}(M_m>x)dx=\int_{0}^{\infty}\prod_{i=1}^{m}(1-F_i(x))dx, E ( M m ) = ∫ 0 ∞ P ( M m > x ) d x = ∫ 0 ∞ i = 1 ∏ m ( 1 − F i ( x )) d x ,
by independence. Since there are finitely many random variables, the continuity of each p i p_i p i at 0 0 0 implies that there is some ε > 0 \varepsilon>0 ε > 0 , such that
p i ( x ) > c , p_i(x)>c, p i ( x ) > c ,
for all x ∈ [ 0 , ε ] x\in[0,\varepsilon] x ∈ [ 0 , ε ] and 1 ≤ i ≤ m 1\leq i\leq m 1 ≤ i ≤ m . So for 0 ≤ x ≤ ε 0\leq x\leq\varepsilon 0 ≤ x ≤ ε , we have F i ( x ) ≥ c x F_i(x)\geq cx F i ( x ) ≥ c x , for each i i i and
∏ i = 1 m ( 1 − F i ( x ) ) ≤ ( 1 − c x ) m ≤ e − m c x . \prod_{i=1}^{m}(1-F_i(x))\leq(1-cx)^m\leq e^{-mcx}. i = 1 ∏ m ( 1 − F i ( x )) ≤ ( 1 − c x ) m ≤ e − m c x .
For x > ε x>\varepsilon x > ε , the monotonicity of F i F_i F i and the fact that F i ( ε ) ≥ c ε F_i(\varepsilon)\geq c\varepsilon F i ( ε ) ≥ c ε give us
∏ i = 1 m ( 1 − F i ( x ) ) ≤ ( 1 − F 1 ( x ) ) ∏ i = 2 m ( 1 − F i ( ε ) ) ≤ ( 1 − c ε ) m − 1 ( 1 − F 1 ( x ) ) . \prod_{i=1}^{m}(1-F_i(x))\leq(1-F_1(x))\prod_{i=2}^{m}(1-F_i(\varepsilon))\leq(1-c\varepsilon)^{m-1}(1-F_1(x)). i = 1 ∏ m ( 1 − F i ( x )) ≤ ( 1 − F 1 ( x )) i = 2 ∏ m ( 1 − F i ( ε )) ≤ ( 1 − c ε ) m − 1 ( 1 − F 1 ( x )) .
Now
∫ 0 ε ∏ i = 1 m ( 1 − F i ( x ) ) d x ≤ ∫ 0 ε e − m c x d x ≤ 1 m c , \int_{0}^{\varepsilon}\prod_{i=1}^{m}(1-F_i(x))dx\leq\int_{0}^{\varepsilon}e^{-mcx}dx\leq\frac{1}{mc}, ∫ 0 ε i = 1 ∏ m ( 1 − F i ( x )) d x ≤ ∫ 0 ε e − m c x d x ≤ m c 1 ,
and
∫ ε ∞ ∏ i = 1 m ( 1 − F i ( x ) ) d x ≤ ( 1 − c ε ) m − 1 ∫ ε ∞ ( 1 − F 1 ( x ) ) d x ≤ ( 1 − c ε ) m − 1 E ( X 1 ) . \int_{\varepsilon}^{\infty}\prod_{i=1}^{m}(1-F_i(x))dx\leq(1-c\varepsilon)^{m-1}\int_{\varepsilon}^{\infty}(1-F_1(x))dx\leq(1-c\varepsilon)^{m-1}\mathbb{E}(X_1). ∫ ε ∞ i = 1 ∏ m ( 1 − F i ( x )) d x ≤ ( 1 − c ε ) m − 1 ∫ ε ∞ ( 1 − F 1 ( x )) d x ≤ ( 1 − c ε ) m − 1 E ( X 1 ) .
Combining these two and the fact that 0 < 1 − c ε < 1 0<1-c\varepsilon<1 0 < 1 − c ε < 1 , we can conclude that
E ( M m ) = O ( 1 m ) . \mathbb{E}(M_m)=O\left(\frac{1}{m}\right). E ( M m ) = O ( m 1 ) .
For the following lemma we also consider the same hypotheses as in Lemma 6.1 .
Lemma 6.4. Let J = argmin 1 ≤ i ≤ m { X i } J = \operatorname{argmin}_{1 \leq i \leq m}\{X_i\} J = argmin 1 ≤ i ≤ m { X i } . Conditioned on J J J and X J = x X_J = x X J = x , for almost all x x x such that p ( x ) > 0 p(x) > 0 p ( x ) > 0 and F ( x ) < 1 F(x) < 1 F ( x ) < 1 , the random variables { X i − X J } i ≠ J \{X_i - X_J\}_{i \ne J} { X i − X J } i = J are independent and have common density
p x ( t ) = p ( x + t ) 1 − F ( x ) , t ≥ 0 , p_x(t) = \frac{p(x+t)}{1-F(x)}, \qquad t \geq0, p x ( t ) = 1 − F ( x ) p ( x + t ) , t ≥ 0 , where p p p is the density of X i X_i X i and F F F is distribution function of X i X_i X i .
Proof. We will show that, conditional on J = j J = j J = j and on X J = x X_J = x X J = x , the joint density of { X i − x } i ≠ j \{X_i-x\}_{i \ne j} { X i − x } i = j is the product of the one-dimensional densities.
First notice that, from the independence, the joint density of all the variables is
f X 1 , … , X m ( x 1 , … , x m ) = ∏ i = 1 m p ( x i ) . f_{X_1,\ldots,X_m}(x_1,\ldots,x_m) = \prod_{i=1}^{m} p(x_i). f X 1 , … , X m ( x 1 , … , x m ) = i = 1 ∏ m p ( x i ) . Conditioned on the index where the minimum is attained J = j J = j J = j , and the minimum X J = x X_J = x X J = x we can make the change of variables
R i = X i − x for i ≠ j R_i = X_i - x \qquad\text{for } i \ne j R i = X i − x for i = j which has Jacobian equal to 1.
The joint distribution of ( J , X J ) (J, X_J) ( J , X J ) and { X i } i ≠ J \{X_i\}_{i \ne J} { X i } i = J can be computed using this change of variables to get
f J , X J , { X i } i ≠ J ( j , x , ( x i ) i ≠ J ) = p ( x ) ∏ i ≠ j p ( x + r i ) . f_{J,X_J,\{X_i\}_{i \ne J}}(j,x,(x_i)_{i \ne J}) = p(x) \prod_{i \ne j} p(x+r_i). f J , X J , { X i } i = J ( j , x , ( x i ) i = J ) = p ( x ) i = j ∏ p ( x + r i ) . The marginal distribution of ( J , X J ) (J, X_J) ( J , X J ) is straightforward to compute: we integrate the variables that are not the minimum and consider our change of variables. With this we have
f J , X J ( j , x ) = p ( x ) ∏ i ≠ j ∫ 0 ∞ p ( x + r i ) d r i = p ( x ) ( ∫ x ∞ p ( r ) d r ) m − 1 = p ( x ) ( 1 − F ( x ) ) m − 1 . \begin{aligned}
f_{J,X_J}(j,x) &= p(x) \prod_{i \ne j} \int_0^\infty p(x+r_i)\,dr_i \\
&= p(x) \left(\int_x^\infty p(r)\,dr\right)^{m-1} \\
&= p(x)(1-F(x))^{m-1}.
\end{aligned} f J , X J ( j , x ) = p ( x ) i = j ∏ ∫ 0 ∞ p ( x + r i ) d r i = p ( x ) ( ∫ x ∞ p ( r ) d r ) m − 1 = p ( x ) ( 1 − F ( x ) ) m − 1 . Finally, we consider the quotient to get the conditional density of the variables R i = X i − x R_i = X_i-x R i = X i − x :
f ( R i ) i ≠ j ∣ X J = x , J = j ( ( r i ) i ≠ j ) = p ( x ) ∏ i ≠ j p ( x + r i ) p ( x ) ( 1 − F ( x ) ) m − 1 = ∏ i ≠ j p ( x + r i ) 1 − F ( x ) . f_{(R_i)_{i \ne j}\mid X_J=x,J=j}((r_i)_{i \ne j}) = \frac{p(x)\prod_{i \ne j}p(x+r_i)}{p(x)(1-F(x))^{m-1}} = \prod_{i \ne j}\frac{p(x+r_i)}{1-F(x)}. f ( R i ) i = j ∣ X J = x , J = j (( r i ) i = j ) = p ( x ) ( 1 − F ( x ) ) m − 1 p ( x ) ∏ i = j p ( x + r i ) = i = j ∏ 1 − F ( x ) p ( x + r i ) .
The following corollary is immediate.
Corollary 6.5. Let J = argmin 1 ≤ i ≤ m { X i } J = \operatorname{argmin}_{1 \leq i \leq m}\{X_i\} J = argmin 1 ≤ i ≤ m { X i } . Conditioned on J J J and X J = x X_J = x X J = x as per previous lemma for all i ≠ J i \ne J i = J ,
E [ ( X i − X J ) ∣ J , X J = x ] ≤ E ( X 1 ) 1 − F ( x ) . \mathbb{E}[(X_i-X_J)\mid J,X_J=x] \leq\frac{\mathbb{E}(X_1)}{1-F(x)}. E [( X i − X J ) ∣ J , X J = x ] ≤ 1 − F ( x ) E ( X 1 ) . Proof. By Lemma 6.4 ,
E [ ( X i − X J ) ∣ J , X J = x ] = ∫ 0 ∞ t p ( x + t ) 1 − F ( x ) d t ≤ 1 1 − F ( x ) ( ∫ x ∞ y p ( y ) d y − x ∫ x ∞ p ( y ) d y ) . \mathbb{E}[(X_i-X_J)\mid J,X_J=x] = \int_0^\infty t\frac{p(x+t)}{1-F(x)}\,dt \leq\frac{1}{1-F(x)}\left(\int_x^\infty yp(y)\,dy-x\int_x^\infty p(y)\,dy\right). E [( X i − X J ) ∣ J , X J = x ] = ∫ 0 ∞ t 1 − F ( x ) p ( x + t ) d t ≤ 1 − F ( x ) 1 ( ∫ x ∞ y p ( y ) d y − x ∫ x ∞ p ( y ) d y ) . The difference of the integrals is bounded above by E ( X 1 ) \mathbb{E}(X_1) E ( X 1 ) .
From the previous lemma, we can derive a uniform lower bound to finally prove that the variables { X i − X J } i ≠ J \{X_i-X_J\}_{i\ne J} { X i − X J } i = J still have expectation O ( 1 / m ) O(1/m) O ( 1/ m ) . This allows us to extend our repair technique to these more general weights.
Lemma 6.6. Let p ( x ) p(x) p ( x ) and p x ( t ) p_x(t) p x ( t ) be densities defined as in the previous lemmas. Then there exist constants ε , c > 0 \varepsilon,c>0 ε , c > 0 such that if the minimum X J X_J X J is in the interval [ 0 , ε ] [0,\varepsilon] [ 0 , ε ]
for almost every x ∈ [ 0 , ε ] x\in[0,\varepsilon] x ∈ [ 0 , ε ] and 0 ≤ t ≤ ε 0\le t\le\varepsilon 0 ≤ t ≤ ε .
Proof. From the continuity of p ( x ) p(x) p ( x ) at 0 0 0 and the fact that p ( 0 ) > 0 p(0)>0 p ( 0 ) > 0 we can find a ε > 0 \varepsilon>0 ε > 0 such that p ( y ) > p ( 0 ) 2 > 0 p(y)>\frac{p(0)}{2}>0 p ( y ) > 2 p ( 0 ) > 0 for every y ∈ [ 0 , 2 ε ] y\in[0,2\varepsilon] y ∈ [ 0 , 2 ε ] . This implies that if the minimum X J = x X_J=x X J = x is in [ 0 , ε ] [0,\varepsilon] [ 0 , ε ] then
p x ( t ) = p ( x + t ) 1 − F ( x ) ≥ p ( x + t ) > p ( 0 ) 2 = c , p_x(t)=\frac{p(x+t)}{1-F(x)}\ge p(x+t)>\frac{p(0)}{2}=c, p x ( t ) = 1 − F ( x ) p ( x + t ) ≥ p ( x + t ) > 2 p ( 0 ) = c ,
for all t ∈ [ 0 , ε ] t\in[0,\varepsilon] t ∈ [ 0 , ε ] .
With the previous Lemma, we can apply the same technique as in Lemma Lemma 6.1 to bound the expectation of the minimum and finally conclude.
Lemma 6.7. Let X 1 , X 2 , … , X m X_1,X_2,\ldots,X_m X 1 , X 2 , … , X m be non-negative i.i.d. continuous random variables with density function the same as in Lemma Lemma 6.1 , then
E ( min i ≠ J ( X i − X J ) ∣ J ) = O ( 1 m ) . \mathbb{E}\left(\min_{i\ne J}(X_i-X_J)\mid J\right)=O\left(\frac{1}{m}\right). E ( i = J min ( X i − X J ) ∣ J ) = O ( m 1 ) .
Proof. Let
Z m = min i ≠ J ( X i − X J ) . Z_m=\min_{i\ne J}(X_i-X_J). Z m = i = J min ( X i − X J ) .
We consider two cases separately.
Case 1 (x ≤ ε x\le\varepsilon x ≤ ε ). Let G x G_x G x be the common distribution function of ( X i − X J ) (X_i-X_J) ( X i − X J ) for all i ≠ J i\ne J i = J . Then by Lemma Lemma 6.6 , for all t ∈ [ 0 , ε ] t\in[0,\varepsilon] t ∈ [ 0 , ε ] ,
G x ( t ) ≥ c t . G_x(t)\ge ct. G x ( t ) ≥ c t .
Therefore,
P ( Z m > t ∣ J , X J = x ) = ( 1 − G x ( t ) ) m − 1 ≤ e − ( m − 1 ) c t , 0 ≤ t ≤ ε . \mathbb{P}(Z_m>t\mid J,X_J=x)=(1-G_x(t))^{m-1}\le e^{-(m-1)ct},\quad0\le t\le\varepsilon. P ( Z m > t ∣ J , X J = x ) = ( 1 − G x ( t ) ) m − 1 ≤ e − ( m − 1 ) c t , 0 ≤ t ≤ ε .
For t > ε t>\varepsilon t > ε , by monotonicity, we get
( 1 − G x ( t ) ) m − 1 ≤ ( 1 − c ε ) m − 2 ( 1 − G x ( t ) ) . (1-G_x(t))^{m-1}\le(1-c\varepsilon)^{m-2}(1-G_x(t)). ( 1 − G x ( t ) ) m − 1 ≤ ( 1 − c ε ) m − 2 ( 1 − G x ( t )) .
Note that
∫ 0 ∞ ( 1 − G x ( t ) ) d t = ∫ x ∞ ( 1 − F ( u ) ) d u 1 − F ( x ) ≤ E ( X 1 ) 1 − F ( ε ) . \int_0^\infty(1-G_x(t))\,dt=\frac{\int_x^\infty(1-F(u))\,du}{1-F(x)}\le\frac{\mathbb{E}(X_1)}{1-F(\varepsilon)}. ∫ 0 ∞ ( 1 − G x ( t )) d t = 1 − F ( x ) ∫ x ∞ ( 1 − F ( u )) d u ≤ 1 − F ( ε ) E ( X 1 ) .
The last inequality comes from the fact that ∫ x ∞ ( 1 − F ( u ) ) d u ≤ ∫ 0 ∞ ( 1 − F ( u ) ) d u = E ( X 1 ) \int_x^\infty(1-F(u))\,du\le\int_0^\infty(1-F(u))\,du=\mathbb{E}(X_1) ∫ x ∞ ( 1 − F ( u )) d u ≤ ∫ 0 ∞ ( 1 − F ( u )) d u = E ( X 1 ) . Now, for almost all x ∈ [ 0 , ε ] x\in[0,\varepsilon] x ∈ [ 0 , ε ] ,
E ( Z m ∣ J , X J = x ) = ∫ 0 ε P ( Z m > t ∣ J , X J = x ) d t + ∫ ε ∞ P ( Z m > t ∣ J , X J = x ) d t ≤ ∫ 0 ε e − ( m − 1 ) c t d t + ( 1 − c ε ) m − 2 E ( X 1 ) 1 − F ( ε ) = O ( 1 m ) . \begin{aligned}
\mathbb{E}(Z_m\mid J,X_J=x)=\int_0^\varepsilon\mathbb{P}(Z_m>t\mid J,X_J=x)\,dt+\int_\varepsilon^\infty\mathbb{P}(Z_m>t\mid J,X_J=x)\,dt \\
&\le\int_0^\varepsilon e^{-(m-1)ct}\,dt+(1-c\varepsilon)^{m-2}\frac{\mathbb{E}(X_1)}{1-F(\varepsilon)}=O\left(\frac{1}{m}\right).
\end{aligned} E ( Z m ∣ J , X J = x ) = ∫ 0 ε P ( Z m > t ∣ J , X J = x ) d t + ∫ ε ∞ P ( Z m > t ∣ J , X J = x ) d t ≤ ∫ 0 ε e − ( m − 1 ) c t d t + ( 1 − c ε ) m − 2 1 − F ( ε ) E ( X 1 ) = O ( m 1 ) .
Integrating over X J ≤ ε X_J\le\varepsilon X J ≤ ε yields \mathbb{E}(Z_1_{X_J\le\varepsilon})=O(1/m) .
Case 2 (x > ε x>\varepsilon x > ε ). We know that Z m ≤ ∑ i = 1 m X i Z_m\le\sum_{i=1}^m X_i Z m ≤ ∑ i = 1 m X i . Thus we obtain
E ( Z m 1 X J > ε ) ≤ m E ( X 1 1 X 1 > ε ) ( 1 − F ( ε ) ) m − 1 = O ( 1 / m ) . \mathbb{E}\left(Z_m1_{X_J>\varepsilon}\right)\le m\mathbb{E}\left(X_11_{X_1>\varepsilon}\right)(1-F(\varepsilon))^{m-1}=O(1/m). E ( Z m 1 X J > ε ) ≤ m E ( X 1 1 X 1 > ε ) ( 1 − F ( ε ) ) m − 1 = O ( 1/ m ) .
Since J J J is uniform and independent of ordered sampled values, we have
E ( Z m ∣ J ) = E ( Z m ) = O ( 1 / m ) . \mathbb{E}(Z_m\mid J)=\mathbb{E}(Z_m)=O(1/m). E ( Z m ∣ J ) = E ( Z m ) = O ( 1/ m ) .
Remark 6.8. Notice that in all our repair steps, we are optimizing over many vertices and not just one. To justify the application of the previous lemma for repairs in this general-weight setting, we further require that all of the minima are simultaneously small, in the small interval [ 0 , ε ] [0,\varepsilon] [ 0 , ε ] . This follows directly from a union bound. Let A ⊆ V n ∖ { ∂ } A \subseteq V_n \setminus\{\partial\} A ⊆ V n ∖ { ∂ } , then
P ( max v ∈ A X v ( m ) > ε ) ≤ ∣ A ∣ ( 1 − F ( ε ) ) m \mathbb{P}\left(\max_{v\in A} X_v^{(m)} > \varepsilon\right) \leq|A|(1-F(\varepsilon))^m P ( v ∈ A max X v ( m ) > ε ) ≤ ∣ A ∣ ( 1 − F ( ε ) ) m
which decays to 0 0 0 exponentially fast.
We now verify an analogous result to Lemma 2.2 for the general family of weights. Combined with the previous lemmas in this section we can extend our arguments for exponential random variables to the general class of i.i.d. edge weights, and verify Theorem 1.5 .
Lemma 6.9. Let W m = ∑ i = 1 m Y m , i W_m = \sum_{i=1}^{m} Y_{m,i} W m = ∑ i = 1 m Y m , i where { Y m , i } 1 ≤ i ≤ m \{Y_{m,i}\}_{1\leq i\leq m} { Y m , i } 1 ≤ i ≤ m is a collection of independent copies of the variable Y m = min { X 1 , X 2 , … , X m } Y_m = \min\{X_1,X_2,\ldots,X_m\} Y m = min { X 1 , X 2 , … , X m } , then
m ( ∑ i = 1 m Y m , i − m E ( Y m , 1 ) ) → d N ( 0 , 1 p ( 0 ) 2 ) . \sqrt{m}\left(\sum_{i=1}^{m}Y_{m,i}-m\mathbb{E}(Y_{m,1})\right)\xrightarrow{d}\mathcal{N}\left(0,\frac{1}{p(0)^2}\right). m ( i = 1 ∑ m Y m , i − m E ( Y m , 1 ) ) d N ( 0 , p ( 0 ) 2 1 ) . Proof. To obtain a CLT for W m W_m W m it is enough to check that Lyapunov’s condition holds, namely:
lim m → ∞ ∑ i = 1 m E ( ( Y m , i − E ( Y m , i ) ) 4 ) ( Var ( ∑ i = 1 m Y m , i ) ) 2 = 0. \lim_{m\to\infty}\frac{\sum_{i=1}^{m}\mathbb{E}\left((Y_{m,i}-\mathbb{E}(Y_{m,i}))^4\right)}{\left(\operatorname{Var}\left(\sum_{i=1}^{m}Y_{m,i}\right)\right)^2}=0. m → ∞ lim ( Var ( ∑ i = 1 m Y m , i ) ) 2 ∑ i = 1 m E ( ( Y m , i − E ( Y m , i ) ) 4 ) = 0. By Lemma 6.1 ,
E ( ( Y m , 1 − E ( Y m , 1 ) ) 4 ) ∼ 9 m 4 p ( 0 ) 4 \mathbb{E}\left((Y_{m,1}-\mathbb{E}(Y_{m,1}))^4\right)\sim\frac{9}{m^4p(0)^4} E ( ( Y m , 1 − E ( Y m , 1 ) ) 4 ) ∼ m 4 p ( 0 ) 4 9 and
Var ( Y m , 1 ) ∼ 1 m 2 p ( 0 ) 2 , \operatorname{Var}(Y_{m,1})\sim\frac{1}{m^2p(0)^2}, Var ( Y m , 1 ) ∼ m 2 p ( 0 ) 2 1 , so therefore
∑ i = 1 m E ( ( Y m , i − E ( Y m , i ) ) 4 ) ( Var ( ∑ i = 1 m Y m , i ) ) 2 = E ( ( Y m , 1 − E ( Y m , 1 ) ) 4 ) m ( Var ( Y m , 1 ) ) 2 ∼ 9 m → 0. \frac{\sum_{i=1}^{m}\mathbb{E}\left((Y_{m,i}-\mathbb{E}(Y_{m,i}))^4\right)}{\left(\operatorname{Var}\left(\sum_{i=1}^{m}Y_{m,i}\right)\right)^2}=\frac{\mathbb{E}\left((Y_{m,1}-\mathbb{E}(Y_{m,1}))^4\right)}{m\left(\operatorname{Var}(Y_{m,1})\right)^2}\sim\frac{9}{m}\to0. ( Var ( ∑ i = 1 m Y m , i ) ) 2 ∑ i = 1 m E ( ( Y m , i − E ( Y m , i ) ) 4 ) = m ( Var ( Y m , 1 ) ) 2 E ( ( Y m , 1 − E ( Y m , 1 ) ) 4 ) ∼ m 9 → 0. We can conclude that
∑ i = 1 m Y m , i − m E ( Y m , 1 ) m Var ( Y m , 1 ) → d N ( 0 , 1 ) . \frac{\sum_{i=1}^{m}Y_{m,i}-m\mathbb{E}(Y_{m,1})}{\sqrt{m\operatorname{Var}(Y_{m,1})}}\xrightarrow{d}\mathcal{N}(0,1). m Var ( Y m , 1 ) ∑ i = 1 m Y m , i − m E ( Y m , 1 ) d N ( 0 , 1 ) . To simplify the expression we can consider
m ( ∑ i = 1 m Y m , i − m E ( Y m , 1 ) ) = m Var ( Y m , 1 ) ⋅ ∑ i = 1 m Y m , i − m E ( Y m , 1 ) m Var ( Y m , 1 ) \sqrt{m}\left(\sum_{i=1}^{m}Y_{m,i}-m\mathbb{E}(Y_{m,1})\right)=m\sqrt{\operatorname{Var}(Y_{m,1})}\cdot\frac{\sum_{i=1}^{m}Y_{m,i}-m\mathbb{E}(Y_{m,1})}{\sqrt{m\operatorname{Var}(Y_{m,1})}} m ( i = 1 ∑ m Y m , i − m E ( Y m , 1 ) ) = m Var ( Y m , 1 ) ⋅ m Var ( Y m , 1 ) ∑ i = 1 m Y m , i − m E ( Y m , 1 ) and from the asymptotics of the variance, the first factor is asymptotically 1 p ( 0 ) \frac{1}{p(0)} p ( 0 ) 1 . Thus,
m ( ∑ i = 1 m Y m , i − m E ( Y m , 1 ) ) → d N ( 0 , 1 p ( 0 ) 2 ) . \sqrt{m}\left(\sum_{i=1}^{m}Y_{m,i}-m\mathbb{E}(Y_{m,1})\right)\xrightarrow{d}\mathcal{N}\left(0,\frac{1}{p(0)^2}\right). m ( i = 1 ∑ m Y m , i − m E ( Y m , 1 ) ) d N ( 0 , p ( 0 ) 2 1 ) .
We have assembled all the ingredients needed to prove Theorem 1.5 in full generality. Note, we only need to establish that Lemmas 3.6 , 3.7 and 3.8 hold when our weights belong to the general class of distributions. In addition to the graph structure of K ⃗ n 1 \vec{K}_n^1 K n 1 , we include weights of the edges in K ⃗ n 1 \vec{K}_n^1 K n 1 in the conditioning. We restrict to the intersection of the good event E ε , δ , η \mathcal{E}_{\varepsilon,\delta,\eta} E ε , δ , η , and { max v ∈ V n X v ( n − 1 ) < ε } \{\max_{v\in V_n}X_v^{(n-1)}<\varepsilon\} { max v ∈ V n X v ( n − 1 ) < ε } where X v ( n − 1 ) X_v^{(n-1)} X v ( n − 1 ) is the weight of the outgoing edge at v v v in K ⃗ n 1 \vec{K}_n^1 K n 1 (the minimum of n − 1 n-1 n − 1 i.i.d.s), and ε \varepsilon ε is as per Remark 6.8. Clearly, the intersection of the two events hold with high probability. Note that each of our repair steps follow the same basic template. We begin with a collection of candidate repair sites. For a given site, situated at a vertex u u u , we consider the cheapest repair that can be executed at that site. Finally, we optimize over all candidate u u u . A crucial point, common to all three steps, is that at this first stage, identifying possible repairs at u u u , the number of repairs available is the same for all u u u ! We illustrate the method for Step 1, specifically the adaptation of Lemma 3.6 . Consider u ∈ C y c l e i u \in\mathrm{Cycle}_i u ∈ Cycle i , and the collection of all edges from u u u to C max C^{\max} C m a x , which we denoted E max ( u ) E_{\max}(u) E m a x ( u ) . Clearly, ∣ E max ( u ) ∣ = ∣ C max ∣ \lvert E_{\max}(u)\rvert=\lvert C^{\max}\rvert ∣ E m a x ( u )∣ = ∣ C m a x ∣ . On the event E ε , δ , η ∩ { max v ∈ V n X v ( n − 1 ) < ε } \mathcal{E}_{\varepsilon,\delta,\eta}\cap\{\max_{v\in V_n}X_v^{(n-1)}<\varepsilon\} E ε , δ , η ∩ { max v ∈ V n X v ( n − 1 ) < ε } , optimal repair cost at u u u , given by X u : = min { Y e ⃗ − Y e ⃗ ∗ ( u ) : e ⃗ ∈ E max ( u ) } X_u:=\min\{Y_{\vec e}-Y_{\vec e_*(u)}:\vec e\in E_{\max}(u)\} X u := min { Y e − Y e ∗ ( u ) : e ∈ E m a x ( u )} satisfies the hypotheses of Lemmas 6.4 and 6.6 . Finally, if we consider min { ∣ C max ∣ ⋅ X u : u ∈ C y c l e i } \min\{\lvert C^{\max}\rvert\cdot X_u:u\in\mathrm{Cycle}_i\} min {∣ C m a x ∣ ⋅ X u : u ∈ Cycle i } , this family satisfies the hypotheses of Lemma 6.3 , in particular using point 2 of Lemma 6.1 . Thus, the expectation bound of Lemma 3.6 can be recovered. The same points are applicable to Step 2 and Step 3.
Concluding Remarks
We take a moment to explain how Theorem 1.5 and the fact n ( W n ∗ − W n ) → 0 \sqrt{n}(W_n^*-W_n)\to0 n ( W n ∗ − W n ) → 0 in probability help us obtain the CLT of [10 ] for the family of weights considered in this article. Let T n T_n T n be the minimum spanning arborescence on K ⃗ n \vec K_n K n without a fixed boundary and let c ( T n ) c(T_n) c ( T n ) denote its cost. Then the CLT of [10 ] (paraphrased) states that
n ( c ( T n ) − n E ( X v ) ) → d N ( 0 , 1 / p ( 0 ) 2 ) . \sqrt{n}(c(T_n)-n\mathbb{E}(X_v))\xrightarrow{d}\mathcal{N}(0,1/p(0)^2). n ( c ( T n ) − n E ( X v )) d N ( 0 , 1/ p ( 0 ) 2 ) .
This can be extracted from the results of this paper, provided we are able to show that
n ( W n ∗ − c ( T n ) ) → 0 , \sqrt{n}(W_n^*-c(T_n))\to0, n ( W n ∗ − c ( T n )) → 0 ,
in probability. Let ρ \rho ρ be the boundary of T n T_n T n . Since c ( T n ) c(T_n) c ( T n ) minimizes the cost among all spanning arborescences (with all possible boundaries), we have
W n ∗ ≥ c ( T n ) . W_n^*\ge c(T_n). W n ∗ ≥ c ( T n ) .
Recall that X v X_v X v is the weight of minimal outgoing edge from v ∈ V n v\in V_n v ∈ V n . Note, c ( T n ) ≥ ∑ v ≠ ρ X v c(T_n)\ge\sum_{v\ne\rho}X_v c ( T n ) ≥ ∑ v = ρ X v (since every vertex apart from ρ \rho ρ must have exactly one out going edge),
W n ∗ − c ( T n ) ≤ W n ∗ − ∑ v ≠ ρ X v = W n ∗ − ( W n − X ρ + X ∂ ) ≤ W n ∗ − W n + max v ∈ V n X v . W_n^*-c(T_n)\le W_n^*-\sum_{v\ne\rho}X_v=W_n^*-(W_n-X_\rho+X_\partial)\le W_n^*-W_n+\max_{v\in V_n}X_v. W n ∗ − c ( T n ) ≤ W n ∗ − v = ρ ∑ X v = W n ∗ − ( W n − X ρ + X ∂ ) ≤ W n ∗ − W n + v ∈ V n max X v .
Next, we demonstrate that n max v ∈ V n X v → 0 \sqrt{n}\max_{v\in V_n}X_v\to0 n max v ∈ V n X v → 0 in probability. Since each X v X_v X v is the minimum of ( n − 1 ) (n-1) ( n − 1 ) random variables with finite expectation,
E ( X v ) ∼ c n − 1 and E ( X v − E ( X v ) ) 4 ≤ C n − 4 . \mathbb{E}(X_v)\sim cn^{-1}\quad\text{and}\quad\mathbb{E}(X_v-\mathbb{E}(X_v))^4\le Cn^{-4}. E ( X v ) ∼ c n − 1 and E ( X v − E ( X v ) ) 4 ≤ C n − 4 .
Indeed, these follow from Lemma 6.1 . Thus, for any ε > 0 \varepsilon>0 ε > 0
P ( X v > ε n − 1 / 2 ) ≤ P ( ∣ X v − E ( X v ) ∣ > ε n − 1 / 2 − c n − 1 ) ≤ P ( ∣ X v − E ( X v ) ∣ > 1 2 ε n − 1 / 2 ) , \mathbb{P}(X_v>\varepsilon n^{-1/2})\le\mathbb{P}(\lvert X_v-\mathbb{E}(X_v)\rvert>\varepsilon n^{-1/2}-cn^{-1})\le\mathbb{P}(\lvert X_v-\mathbb{E}(X_v)\rvert>\tfrac{1}{2}\varepsilon n^{-1/2}), P ( X v > ε n − 1/2 ) ≤ P (∣ X v − E ( X v )∣ > ε n − 1/2 − c n − 1 ) ≤ P (∣ X v − E ( X v )∣ > 2 1 ε n − 1/2 ) ,
final inequality holding for n n n large enough. Applying a union bound, we obtain
P ( n max v ∈ V n X v > ε ) ≤ ∑ v ∈ V n P ( X v > ε n − 1 / 2 ) ≤ n ⋅ 2 4 ⋅ C n − 4 ε 4 ⋅ n − 2 ≤ 2 4 ⋅ C ε 4 ⋅ n − 1 . \mathbb{P}\left(\sqrt{n}\max_{v\in V_n}X_v>\varepsilon\right)\le\sum_{v\in V_n}\mathbb{P}(X_v>\varepsilon n^{-1/2})\le n\cdot\frac{2^4\cdot Cn^{-4}}{\varepsilon^4\cdot n^{-2}}\le\frac{2^4\cdot C}{\varepsilon^4}\cdot n^{-1}. P ( n v ∈ V n max X v > ε ) ≤ v ∈ V n ∑ P ( X v > ε n − 1/2 ) ≤ n ⋅ ε 4 ⋅ n − 2 2 4 ⋅ C n − 4 ≤ ε 4 2 4 ⋅ C ⋅ n − 1 .
Therefore n max v ∈ V n X v → 0 \sqrt{n}\max_{v\in V_n}X_v\to0 n max v ∈ V n X v → 0 in probability. Combining the facts 0 ≤ W n ∗ − c ( T n ) ≤ W n ∗ − W n + max v ∈ V n X v 0\le W_n^*-c(T_n)\le W_n^*-W_n+\max_{v\in V_n}X_v 0 ≤ W n ∗ − c ( T n ) ≤ W n ∗ − W n + max v ∈ V n X v and n ( W n ∗ − W n ) → 0 \sqrt{n}(W_n^*-W_n)\to0 n ( W n ∗ − W n ) → 0 in probability, we can conclude that n ( W n ∗ − c ( T n ) ) → 0 \sqrt{n}(W_n^*-c(T_n))\to0 n ( W n ∗ − c ( T n )) → 0 in probability.
We expect that our method generalizes to families of non-negative random variables other than those with densities continuous at 0 0 0 , satisfying p ( 0 ) ∈ ( 0 , ∞ ) p(0)\in(0,\infty) p ( 0 ) ∈ ( 0 , ∞ ) . In particular, we anticipate that only the scaling changes, based on the application of Laplace asymptotics. If p ( x ) ∼ x β p(x)\sim x^\beta p ( x ) ∼ x β near zero for β ∈ ( − 1 , ∞ ) \beta\in(-1,\infty) β ∈ ( − 1 , ∞ ) , mirroring the sequence of steps in Lemma 6.1 , the minimal weight edge emanating from each vertex is now O ( n − 1 1 + β ) O\left(n^{-\frac{1}{1+\beta}}\right) O ( n − 1 + β 1 ) . The variance also transforms to O ( n − 2 1 + β ) O\left(n^{-\frac{2}{1+\beta}}\right) O ( n − 1 + β 2 ) . The Lyapunov condition also holds, yielding a CLT for W n W_n W n with the new scaling. However, subtleties could arise in verifying analogues of Lemmas 6.4 , 6.6 , and 6.7 . Where our methods possibly fail completely are densities which vanish to infinite order at 0, an example given by the canonical C ∞ C^\infty C ∞ bump function on [ 0 , 1 ] [0,1] [ 0 , 1 ] . Our methods are quite robust with respect to tail conditions on Y ⃗ e \vec{Y}_e Y e , power decay for P ( Y ⃗ e > t ) \mathbb{P}(\vec{Y}_e > t) P ( Y e > t ) is completely admissible, even without finite first moment. However, all our estimates break with pathological tail examples such as P ( Y ⃗ e > t ) ∼ C log t \mathbb{P}(\vec{Y}_e > t) \sim\frac{C}{\log t} P ( Y e > t ) ∼ l o g t C as t → ∞ t \to\infty t → ∞ .