Introduction
Fix integers d ≥ 3 d \ge3 d ≥ 3 and 1 ≤ k ≤ d − 1 1 \le k \le d-1 1 ≤ k ≤ d − 1 , and let n n n be a positive integer such that d n dn d n and k n kn k n are even. A k k k -factor of a graph G G G is a spanning k k k -regular subgraph. Let G ( n , d ) G(n,d) G ( n , d ) be the probability space of uniformly random labelled simple d d d -regular graphs on [ n ] = { 1 , … , n } [n]=\{1,\ldots,n\} [ n ] = { 1 , … , n } . Write Z k ( G ) Z_k(G) Z k ( G ) for the number of k k k -factors of G G G , and X i ( G ) X_i(G) X i ( G ) for the number of cycles of length i i i in G G G . Throughout,
λ i = ( d − 1 ) i 2 i , δ i = ( − 1 ) i ( d − 1 ) i ( i ≥ 1 ) , (1) \lambda_i=\frac{(d-1)^i}{2i},\qquad\delta_i=\frac{(-1)^i}{(d-1)^i}\qquad(i\ge1), \tag*{(1)} λ i = 2 i ( d − 1 ) i , δ i = ( d − 1 ) i ( − 1 ) i ( i ≥ 1 ) , (1)
so 1 + δ i > 0 1+\delta_i>0 1 + δ i > 0 for all i i i and ∑ i ≥ 1 λ i δ i 2 = 1 2 ∑ i ≥ 1 ( d − 1 ) − i / i = 1 2 log d − 1 d − 2 < ∞ \sum_{i\ge1}\lambda_i\delta_i^2=\frac{1}{2}\sum_{i\ge1}(d-1)^{-i}/i=\frac{1}{2}\log\frac{d-1}{d-2}<\infty ∑ i ≥ 1 λ i δ i 2 = 2 1 ∑ i ≥ 1 ( d − 1 ) − i / i = 2 1 log d − 2 d − 1 < ∞ . We prove that the short cycles of G G G govern the relative fluctuations of Z k ( G ) Z_k(G) Z k ( G ) around its mean, independently of k k k .
Theorem 1.1. Fix integers d ≥ 3 d\ge3 d ≥ 3 and 1 ≤ k ≤ d − 1 1\le k\le d-1 1 ≤ k ≤ d − 1 . Let n → ∞ n\to\infty n → ∞ along integers for which d n dn d n and k n kn k n are even, and let G ∼ G ( n , d ) G\sim G(n,d) G ∼ G ( n , d ) . Let ( ξ i ) i ≥ 3 (\xi_i)_{i\ge3} ( ξ i ) i ≥ 3 be independent Poisson( λ i ) (\lambda_i) ( λ i ) random variables.
(i) (mean)
E G ( n , d ) [ Z k ( G ) ] = 2 e 1 / 4 ( ( d k ) k k / 2 ( d − k ) ( d − k ) / 2 d − d / 2 ) n ( 1 + o ( 1 ) ) . (2) \mathbb{E}_{G(n,d)}[Z_k(G)]=\sqrt{2}e^{1/4}\left(\binom{d}{k}k^{k/2}(d-k)^{(d-k)/2}d^{-d/2}\right)^n(1+o(1)). \tag*{(2)} E G ( n , d ) [ Z k ( G )] = 2 e 1/4 ( ( k d ) k k /2 ( d − k ) ( d − k ) /2 d − d /2 ) n ( 1 + o ( 1 )) . (2) (ii) (second moment)
E G ( n , d ) [ Z k ( G ) 2 ] ( E G ( n , d ) [ Z k ( G ) ] ) 2 ⟶ exp ( ∑ i ≥ 3 λ i δ i 2 ) = e − 2 d − 1 4 ( d − 1 ) 2 d − 1 d − 2 . (3) \frac{\mathbb{E}_{G(n,d)}[Z_k(G)^2]}{\left(\mathbb{E}_{G(n,d)}[Z_k(G)]\right)^2}
\longrightarrow\exp\left(\sum_{i\ge3}\lambda_i\delta_i^2\right)
=e^{-\frac{2d-1}{4(d-1)^2}}\sqrt{\frac{d-1}{d-2}}. \tag*{(3)} ( E G ( n , d ) [ Z k ( G )] ) 2 E G ( n , d ) [ Z k ( G ) 2 ] ⟶ exp ( i ≥ 3 ∑ λ i δ i 2 ) = e − 4 ( d − 1 ) 2 2 d − 1 d − 2 d − 1 . (3) (iii) (limit distribution) The infinite product
W : = ∏ i = 3 ∞ ( 1 + δ i ) ξ i e − λ i δ i . (4) W:=\prod_{i=3}^{\infty}(1+\delta_i)^{\xi_i}e^{-\lambda_i\delta_i}. \tag*{(4)} W := i = 3 ∏ ∞ ( 1 + δ i ) ξ i e − λ i δ i . (4)
converges almost surely and in L 2 L^2 L 2 . It satisfies W > 0 W > 0 W > 0 almost surely, E W = 1 \mathbb{E}W = 1 E W = 1 , and E W 2 = exp ( ∑ i ≥ 3 λ i δ i 2 ) \mathbb{E}W^2 = \exp\left(\sum_{i\geq3}\lambda_i\delta_i^2\right) E W 2 = exp ( ∑ i ≥ 3 λ i δ i 2 ) . Moreover,
Z k ( G ) E G ( n , d ) [ Z k ( G ) ] ⟹ W , (5) \frac{Z_k(G)}{\mathbb{E}_{G(n,d)}[Z_k(G)]} \Longrightarrow W, \tag*{(5)} E G ( n , d ) [ Z k ( G )] Z k ( G ) ⟹ W , (5)
jointly with ( X 3 ( G ) , … , X m ( G ) ) ⟹ ( ξ 3 , … , ξ m ) (X_3(G),\ldots,X_m(G)) \Longrightarrow(\xi_3,\ldots,\xi_m) ( X 3 ( G ) , … , X m ( G )) ⟹ ( ξ 3 , … , ξ m ) for every fixed m m m .
(iv) (linkage) For any 1 ≤ k , ℓ ≤ d − 1 1 \leq k,\ell\leq d-1 1 ≤ k , ℓ ≤ d − 1 , let n n n tend to infinity along integers for which d n dn d n , k n kn k n , and ℓ n \ell n ℓ n are even. The normalised counts on the same graph G ∼ G ( n , d ) G \sim G(n,d) G ∼ G ( n , d ) satisfy
Z k ( G ) E G ( n , d ) [ Z k ( G ) ] − Z ℓ ( G ) E G ( n , d ) [ Z ℓ ( G ) ] → p 0 , (6) \frac{Z_k(G)}{\mathbb{E}_{G(n,d)}[Z_k(G)]} - \frac{Z_\ell(G)}{\mathbb{E}_{G(n,d)}[Z_\ell(G)]} \xrightarrow{p} 0, \tag*{(6)} E G ( n , d ) [ Z k ( G )] Z k ( G ) − E G ( n , d ) [ Z ℓ ( G )] Z ℓ ( G ) p 0 , (6)
and consequently Z k ( G ) / E G ( n , d ) [ Z k ( G ) ] Z ℓ ( G ) / E G ( n , d ) [ Z ℓ ( G ) ] → p 1 \frac{Z_k(G)/\mathbb{E}_{G(n,d)}[Z_k(G)]}{Z_\ell(G)/\mathbb{E}_{G(n,d)}[Z_\ell(G)]} \xrightarrow{p} 1 Z ℓ ( G ) / E G ( n , d ) [ Z ℓ ( G )] Z k ( G ) / E G ( n , d ) [ Z k ( G )] p 1 . Here the ratio is set equal to 1 on the event { Z ℓ ( G ) = 0 } \{Z_\ell(G) = 0\} { Z ℓ ( G ) = 0 } , whose probability tends to 0.
Previous work. For k = 1 k = 1 k = 1 (perfect matchings), Bollobás and McKay [2 ] determined the asymptotics of the first two moments of Z 1 ( G ) Z_1(G) Z 1 ( G ) . Janson [6 ] obtained the limit distribution of Z 1 ( G ) / E Z 1 ( G ) Z_1(G)/\mathbb{E}Z_1(G) Z 1 ( G ) / E Z 1 ( G ) by the small subgraph conditioning method. Robinson and Wormald introduced this method for Hamilton cycles in cubic graphs [9 ] and applied it to perfect matchings [10 ] . For k = 2 k = 2 k = 2 , Robalewska [8 ] computed the second moment and established the limit distribution.
The complement of a k k k -factor in a d d d -regular graph is a ( d − k ) (d-k) ( d − k ) -factor. Thus Z k ( G ) = Z d − k ( G ) Z_k(G) = Z_{d-k}(G) Z k ( G ) = Z d − k ( G ) , and the cases k = d − 1 k = d-1 k = d − 1 and k = d − 2 k = d-2 k = d − 2 follow. Theorem 1.1 was therefore known for k ∈ { 1 , 2 , d − 2 , d − 1 } k \in\{1,2,d-2,d-1\} k ∈ { 1 , 2 , d − 2 , d − 1 } . In particular, the normalised numbers of perfect matchings and 2-factors have the same limit distribution [8 Corollary 4] . Wormald also observed that they are asymptotically linked: Z 1 ( G ) / E Z 1 ( G ) ∼ Z 2 ( G ) / E Z 2 ( G ) Z_1(G)/\mathbb{E}Z_1(G) \sim Z_2(G)/\mathbb{E}Z_2(G) Z 1 ( G ) / E Z 1 ( G ) ∼ Z 2 ( G ) / E Z 2 ( G ) asymptotically almost surely [12 Corollary 4.10 and the remark following it] . Part (iv) extends this result to all pairs k , ℓ k,\ell k , ℓ .
The remaining cases 3 ≤ k ≤ d − 3 3 \leq k \leq d-3 3 ≤ k ≤ d − 3 occur when d ≥ 6 d \geq6 d ≥ 6 . For these k k k , the contiguity of G ( n , d ) G(n,d) G ( n , d ) and the edge-disjoint superposition G ( n , k ) ⊕ G ( n , d − k ) G(n,k) \oplus G(n,d-k) G ( n , k ) ⊕ G ( n , d − k ) follows from [12 Corollary 4.17] , which combines the contiguity results collected in [12 Theorem 4.15] ; see also [6 ] . The first moment in the pairing model is elementary; see (8) below. For fixed d d d , we are not aware of a previous determination of the second moment or the limit distribution of Z k ( G ) Z_k(G) Z k ( G ) for 3 ≤ k ≤ d − 3 3 \leq k \leq d-3 3 ≤ k ≤ d − 3 . Isaev et al. [5 Eq. (4.2)] prove the bound E [ Z k ( G ) 2 ] ≤ ( 1 + o ( 1 ) ) ( E Z k ( G ) ) 2 \mathbb{E}[Z_k(G)^2] \leq(1+o(1))(\mathbb{E}Z_k(G))^2 E [ Z k ( G ) 2 ] ≤ ( 1 + o ( 1 )) ( E Z k ( G ) ) 2 when k 2 { n / min { d − k , n − d + k } } 2 k ≤ 1 3 log n k^2\{n/\min\{d-k,n-d+k\}\}^{2k} \leq\frac{1}{3}\log n k 2 { n / min { d − k , n − d + k } } 2 k ≤ 3 1 log n .
In the growing-degree regime, Gao [3 ] proved the asymptotic normality of Z 1 ( G ) Z_1(G) Z 1 ( G ) for d → ∞ d \to\infty d → ∞ with d = O ( n 1 / 7 / log n ) d = O(n^{1/7}/\log n) d = O ( n 1/7 / log n ) . Gao conjectured this result for all Z k ( G ) Z_k(G) Z k ( G ) when min ( d , n − d ) → ∞ \min(d,n-d) \to\infty min ( d , n − d ) → ∞ .
For fixed d d d and k k k , the mean formula in part (i), including the constant 2 e 1 / 4 \sqrt{2}e^{1/4} 2 e 1/4 , follows from the enumeration of Hasheminezhad and McKay [4 ] . It equals the number of partitions of the complete graph into spanning regular subgraphs of degrees n − 1 − d n-1-d n − 1 − d , k k k and d − k d-k d − k , divided by the number of d d d -regular graphs. The second moment and the limit distribution are proved here.
Contribution. We prove Theorem 1.1 by Janson’s small subgraph conditioning method [6 ] in the pairing model. The proof uses two lemmas. Lemma 3.1 proves the joint factorial moments of Z k Z_k Z k and the short-cycle counts. A 2 × 2 2 \times2 2 × 2 transfer matrix with spectrum { d − 1 , − 1 } \{d-1,-1\} { d − 1 , − 1 } , independent of k k k , explains the universality in k k k . Janson states the same matrix and the resulting Poisson means without proof in his section on contiguity and asymptotic distributions [6 ] .
Next, Lemma 4.1 proves the second moment of Z k Z_k Z k . The overlap of two k k k -factors is a sum of i.i.d. hypergeometric random variables, one for each vertex, so the second moment reduces to a one-dimensional lattice sum over this overlap (Lemma 4.2). We evaluate this sum by a Laplace-type argument. The key step is that a hypergeometric distribution is a sum of independent Bernoulli variables with distinct parameters (Lemma 4.4 ; equivalently, its generating polynomial has only real zeros [11 , 7 ] ). This makes the tilted family explicit, gives a strictly concave rate-function comparison (Lemma 4.5 ), and yields a uniform local limit theorem for the tilted sums (Lemma 4.6). The passage from the pairing model to simple graphs is standard [12 Lemma 4.4] . For completeness, § 5 derives the conditional first and second moments from uniform integrability.
Organisation. § 2 recalls the pairing model, the first moment, and Janson’s small subgraph conditioning theorem. § 3 treats short cycles, § 4 treats the second moment, and § 5 proves Theorem 1.1.
The pairing model and small subgraph conditioning
We use the pairing model P n , d \mathcal{P}_{n,d} P n , d [1 , 12 ] . Each vertex v ∈ [ n ] v \in[n] v ∈ [ n ] is represented by a cell V v V_v V v of d d d labelled points, and a pairing P ∈ P n , d P \in\mathcal{P}_{n,d} P ∈ P n , d is a perfect matching of the d n dn d n points. The number of perfect matchings on 2 ℓ 2\ell 2 ℓ points is
M ( 2 ℓ ) = ( 2 ℓ ) ! ℓ ! 2 ℓ = ( 2 ℓ − 1 ) ! ! ( ℓ ≥ 0 ) , M(2\ell) = \frac{(2\ell)!}{\ell!2^\ell} = (2\ell-1)!! \qquad(\ell\ge0), M ( 2 ℓ ) = ℓ ! 2 ℓ ( 2 ℓ )! = ( 2 ℓ − 1 )!! ( ℓ ≥ 0 ) ,
where M ( 0 ) = 1 M(0)=1 M ( 0 ) = 1 ; set M ( x ) = 0 M(x)=0 M ( x ) = 0 for odd x x x .
Let P \mathbb{P} P and E \mathbb{E} E denote probability and expectation under the uniform distribution on P n , d \mathcal{P}_{n,d} P n , d . Contracting each cell V v V_v V v to a vertex projects P P P to a d d d -regular multigraph G ( P ) G(P) G ( P ) . A pair within a cell is a loop, and two pairs joining the same two cells are parallel edges. Let X i = X i ( P ) X_i=X_i(P) X i = X i ( P ) be the number of i i i -cycles of G ( P ) G(P) G ( P ) . Here X 1 X_1 X 1 is the number of loops, X 2 X_2 X 2 is the number of unordered pairs of parallel edges, and, for i ≥ 3 i\ge3 i ≥ 3 , X i X_i X i is the number of cycles of length i i i . With these conventions, for every fixed m m m ,
( X 1 , … , X m ) ⟹ ( ξ 1 , … , ξ m ) , ξ i ∼ Poisson ( λ i ) independent (7) (X_1,\ldots,X_m)\ \Longrightarrow\ (\xi_1,\ldots,\xi_m),\qquad\xi_i\sim\operatorname{Poisson}(\lambda_i)\text{ independent} \tag*{(7)} ( X 1 , … , X m ) ⟹ ( ξ 1 , … , ξ m ) , ξ i ∼ Poisson ( λ i ) independent (7)
[12 Theorem 2.6] ; see also the proof of Theorem 2 in [1 ] . The multigraph G ( P ) G(P) G ( P ) is simple precisely on the event S : = { X 1 = X 2 = 0 } S:=\{X_1=X_2=0\} S := { X 1 = X 2 = 0 } . The probability of this event tends to e − λ 1 − λ 2 = e − ( d 2 − 1 ) / 4 > 0 e^{-\lambda_1-\lambda_2}=e^{-(d^2-1)/4}>0 e − λ 1 − λ 2 = e − ( d 2 − 1 ) /4 > 0 . Conditional on S S S , the graph G ( P ) G(P) G ( P ) is uniformly distributed over simple d d d -regular graphs; that is, G ( P ) ∼ G ( n , d ) G(P)\sim\mathcal{G}(n,d) G ( P ) ∼ G ( n , d ) .
A k k k -factor of P P P is a subset F ⊆ P F\subseteq P F ⊆ P of pairs that covers exactly k k k points in each cell V v V_v V v . Let Z k ( P ) Z_k(P) Z k ( P ) denote the number of k k k -factors of P P P . If G ( P ) G(P) G ( P ) is simple, the pairs of P P P correspond bijectively to the edges of G ( P ) G(P) G ( P ) , and the k k k -factors of P P P correspond to those of G ( P ) G(P) G ( P ) . Thus Z k ( P ) = Z k ( G ( P ) ) Z_k(P)=Z_k(G(P)) Z k ( P ) = Z k ( G ( P )) on S S S .
A k k k -factor F F F determines the sets A v ⊆ V v A_v\subseteq V_v A v ⊆ V v of points that it covers, where ∣ A v ∣ = k |A_v|=k ∣ A v ∣ = k . There are ( d k ) n \binom{d}{k}^n ( k d ) n choices for these sets, M ( k n ) M(kn) M ( k n ) ways to pair the k n kn k n chosen points to form F F F , and M ( ( d − k ) n ) M((d-k)n) M (( d − k ) n ) ways to pair the remaining ( d − k ) n (d-k)n ( d − k ) n points to form R = P ∖ F R=P\setminus F R = P ∖ F . Hence the exact first moment is
E Z k ( P ) = ( d k ) n M ( k n ) M ( ( d − k ) n ) M ( d n ) = 2 ( ( d k ) k k / 2 ( d − k ) ( d − k ) / 2 d − d / 2 ) n ( 1 + O ( n − 1 ) ) , (8) \mathbb{E}Z_k(P)=\binom{d}{k}^n\frac{M(kn)M((d-k)n)}{M(dn)}
=\sqrt{2}\left(\binom{d}{k}k^{k/2}(d-k)^{(d-k)/2}d^{-d/2}\right)^n(1+O(n^{-1})), \tag*{(8)} E Z k ( P ) = ( k d ) n M ( d n ) M ( k n ) M (( d − k ) n ) = 2 ( ( k d ) k k /2 ( d − k ) ( d − k ) /2 d − d /2 ) n ( 1 + O ( n − 1 )) , (8)
where the asymptotic form follows from Stirling’s formula in the form M ( 2 ℓ ) = 2 ( 2 ℓ / e ) ℓ ( 1 + O ( ℓ − 1 ) ) M(2\ell)=\sqrt{2}(2\ell/e)^\ell(1+O(\ell^{-1})) M ( 2 ℓ ) = 2 ( 2 ℓ / e ) ℓ ( 1 + O ( ℓ − 1 )) . The powers of n n n and of e e e cancel because k n + ( d − k ) n = d n kn+(d-k)n=dn k n + ( d − k ) n = d n .
The same count describes the uniform distribution on pairs ( P , F ) (P,F) ( P , F ) in which F F F is a k k k -factor of P P P . The sets ( A v ) v ∈ [ n ] (A_v)_{v\in[n]} ( A v ) v ∈ [ n ] are independent uniform k k k -subsets of the cells. Conditional on these sets, F F F is a uniform perfect matching of the chosen points and R R R is an independent uniform perfect matching of the remaining points. Let E Ω \mathbb{E}_{\Omega} E Ω denote expectation for a uniformly random pair ( P , F ) (P,F) ( P , F ) in Ω : = { ( P , F ) : F is a k -factor of P } \Omega:=\{(P,F):F\text{ is a }k\text{-factor of }P\} Ω := {( P , F ) : F is a k -factor of P } . For every function Ψ \Psi Ψ of P P P ,
E [ Z k ( P ) Ψ ( P ) ] E Z k ( P ) = E Ω [ Ψ ( P ) ] . (9) \frac{\mathbb{E}[Z_k(P)\Psi(P)]}{\mathbb{E}Z_k(P)}=\mathbb{E}_{\Omega}[\Psi(P)]. \tag*{(9)} E Z k ( P ) E [ Z k ( P ) Ψ ( P )] = E Ω [ Ψ ( P )] . (9)
We use the following form of the small subgraph conditioning theorem. It is a special case of Theorem 1 of [6 ] , with his second condition replaced by the factorial-moment condition in the lemma following that theorem. It also follows from Theorems 4.1 and 4.3 of [12 ] . Here ( x ) r = x ( x − 1 ) ⋯ ( x − r + 1 ) (x)_r=x(x-1)\cdots(x-r+1) ( x ) r = x ( x − 1 ) ⋯ ( x − r + 1 ) denotes the falling factorial.
Theorem 2.1 (small subgraph conditioning). Let λ i > 0 \lambda_i>0 λ i > 0 and δ i > − 1 \delta_i>-1 δ i > − 1 ( i ≥ 1 ) (i\ge1) ( i ≥ 1 ) be constants. For each n n n , let Y n ≥ 0 Y_n\ge0 Y n ≥ 0 and X 1 n , X 2 n , … X_{1n},X_{2n},\ldots X 1 n , X 2 n , … be random variables on a common probability space, where the X i n X_{in} X in are nonnegative and integer valued and 0 < E Y n < ∞ 0<\mathbb{E}Y_n<\infty 0 < E Y n < ∞ . Suppose that
(i) for each fixed m m m , ( X 1 n , … , X m n ) ⟹ ( ξ 1 , … , ξ m ) (X_{1n},\ldots,X_{mn})\Longrightarrow(\xi_1,\ldots,\xi_m) ( X 1 n , … , X mn ) ⟹ ( ξ 1 , … , ξ m ) , where the ξ i ∼ Poisson ( λ i ) \xi_i\sim\operatorname{Poisson}(\lambda_i) ξ i ∼ Poisson ( λ i ) are independent;
(ii) for each fixed m m m and all nonnegative integers r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m ,
E [ Y n ∏ i = 1 m ( X i n ) r i ] E Y n ⟶ ∏ i = 1 m ( λ i ( 1 + δ i ) ) r i ; \frac{\mathbb{E}\left[Y_n\prod_{i=1}^{m}(X_{in})_{r_i}\right]}{\mathbb{E}Y_n}
\longrightarrow\prod_{i=1}^{m}\left(\lambda_i(1+\delta_i)\right)^{r_i}; E Y n E [ Y n ∏ i = 1 m ( X in ) r i ] ⟶ i = 1 ∏ m ( λ i ( 1 + δ i ) ) r i ;
(iii) ∑ i ≥ 1 λ i δ i 2 < ∞ \sum_{i\ge1}\lambda_i\delta_i^2<\infty ∑ i ≥ 1 λ i δ i 2 < ∞ ;
(iv) E Y n 2 ( E Y n ) 2 ⟶ exp ( ∑ i ≥ 1 λ i δ i 2 ) \frac{\mathbb{E}Y_n^2}{(\mathbb{E}Y_n)^2}\longrightarrow\exp\left(\sum_{i\ge1}\lambda_i\delta_i^2\right) ( E Y n ) 2 E Y n 2 ⟶ exp ( ∑ i ≥ 1 λ i δ i 2 ) .
Then the product W p a i r : = ∏ i ≥ 1 ( 1 + δ i ) ξ i e − λ i δ i W^{\mathrm{pair}}:=\prod_{i\ge1}(1+\delta_i)^{\xi_i}e^{-\lambda_i\delta_i} W pair := ∏ i ≥ 1 ( 1 + δ i ) ξ i e − λ i δ i converges almost surely, and, for each fixed m m m ,
( Y n E Y n , X 1 n , … , X m n ) ⟹ ( W p a i r , ξ 1 , … , ξ m ) \left(\frac{Y_n}{\mathbb{E}Y_n},X_{1n},\ldots,X_{mn}\right)\Longrightarrow\left(W^{\mathrm{pair}},\xi_1,\ldots,\xi_m\right) ( E Y n Y n , X 1 n , … , X mn ) ⟹ ( W pair , ξ 1 , … , ξ m )
jointly.
We need the following elementary properties of the limiting products for the constants λ i , δ i \lambda_i,\delta_i λ i , δ i in (1) .
Lemma 2.2. Let λ i , δ i \lambda_i,\delta_i λ i , δ i be as in (1) , let ( ξ i ) i ≥ 1 (\xi_i)_{i\ge1} ( ξ i ) i ≥ 1 be independent Poisson ( λ i ) \operatorname{Poisson}(\lambda_i) Poisson ( λ i ) variables, and let I ⊂ { 1 , 2 , … } I\subset\{1,2,\ldots\} I ⊂ { 1 , 2 , … } . Then the partial products W I ( m ) : = ∏ i ∈ I , i ≤ m ( 1 + δ i ) ξ i e − λ i δ i W_I^{(m)}:=\prod_{i\in I,\ i\le m}(1+\delta_i)^{\xi_i}e^{-\lambda_i\delta_i} W I ( m ) := ∏ i ∈ I , i ≤ m ( 1 + δ i ) ξ i e − λ i δ i converge as m → ∞ m\to\infty m → ∞ , almost surely and in L 2 L^2 L 2 , to a limit W I W_I W I such that W I > 0 W_I>0 W I > 0 almost surely, E W I = 1 \mathbb{E}W_I=1 E W I = 1 , and E W I 2 = exp ( ∑ i ∈ I λ i δ i 2 ) \mathbb{E}W_I^2=\exp\left(\sum_{i\in I}\lambda_i\delta_i^2\right) E W I 2 = exp ( ∑ i ∈ I λ i δ i 2 ) . If I ∩ J = ∅ I\cap J=\varnothing I ∩ J = ∅ , then W I W_I W I and W J W_J W J are independent.
Proof. Since ∣ δ i ∣ ≤ ( d − 1 ) − i ≤ 1 2 |\delta_i|\le(d-1)^{-i}\le\frac{1}{2} ∣ δ i ∣ ≤ ( d − 1 ) − i ≤ 2 1 , we have ∣ log ( 1 + δ i ) − δ i ∣ ≤ δ i 2 |\log(1+\delta_i)-\delta_i|\le\delta_i^2 ∣ log ( 1 + δ i ) − δ i ∣ ≤ δ i 2 and ∣ log ( 1 + δ i ) ∣ ≤ 2 ∣ δ i ∣ |\log(1+\delta_i)|\le2|\delta_i| ∣ log ( 1 + δ i ) ∣ ≤ 2∣ δ i ∣ . The summands ξ i log ( 1 + δ i ) − λ i δ i \xi_i\log(1+\delta_i)-\lambda_i\delta_i ξ i log ( 1 + δ i ) − λ i δ i of log W I ( m ) \log W_I^{(m)} log W I ( m ) are independent. Their means are λ i ( log ( 1 + δ i ) − δ i ) = O ( λ i δ i 2 ) \lambda_i(\log(1+\delta_i)-\delta_i)=O(\lambda_i\delta_i^2) λ i ( log ( 1 + δ i ) − δ i ) = O ( λ i δ i 2 ) , and their variances are λ i log 2 ( 1 + δ i ) = O ( λ i δ i 2 ) \lambda_i\log^2(1+\delta_i)=O(\lambda_i\delta_i^2) λ i log 2 ( 1 + δ i ) = O ( λ i δ i 2 ) . Both are summable because ∑ i ≥ 1 λ i δ i 2 < ∞ \sum_{i\ge1}\lambda_i\delta_i^2<\infty ∑ i ≥ 1 λ i δ i 2 < ∞ , as noted after (1) . Kolmogorov’s two-series theorem therefore shows that the series converges almost surely and that W I = exp ( lim m log W I ( m ) ) ∈ ( 0 , ∞ ) W_I=\exp(\lim_m\log W_I^{(m)})\in(0,\infty) W I = exp ( lim m log W I ( m ) ) ∈ ( 0 , ∞ ) almost surely.
Each factor ( 1 + δ i ) ξ i e − λ i δ i (1+\delta_i)^{\xi_i}e^{-\lambda_i\delta_i} ( 1 + δ i ) ξ i e − λ i δ i has mean e λ i δ i e − λ i δ i = 1 e^{\lambda_i\delta_i}e^{-\lambda_i\delta_i}=1 e λ i δ i e − λ i δ i = 1 and second moment e λ i ( ( 1 + δ i ) 2 − 1 ) e − 2 λ i δ i = e λ i δ i 2 e^{\lambda_i((1+\delta_i)^2-1)}e^{-2\lambda_i\delta_i}=e^{\lambda_i\delta_i^2} e λ i (( 1 + δ i ) 2 − 1 ) e − 2 λ i δ i = e λ i δ i 2 . Thus ( W I ( m ) ) m (W_I^{(m)})_m ( W I ( m ) ) m is a nonnegative martingale with bounded second moments, E ( W I ( m ) ) 2 = exp ( ∑ i ∈ I , i ≤ m λ i δ i 2 ) \mathbb{E}(W_I^{(m)})^2=\exp\left(\sum_{i\in I,i\le m}\lambda_i\delta_i^2\right) E ( W I ( m ) ) 2 = exp ( ∑ i ∈ I , i ≤ m λ i δ i 2 ) . It therefore converges in L 2 L^2 L 2 , and E W I = 1 \mathbb{E}W_I=1 E W I = 1 , E W I 2 = exp ( ∑ i ∈ I λ i δ i 2 ) \mathbb{E}W_I^2=\exp\left(\sum_{i\in I}\lambda_i\delta_i^2\right) E W I 2 = exp ( ∑ i ∈ I λ i δ i 2 ) . Independence for disjoint index sets follows from the independence of the ξ i \xi_i ξ i .
Short cycles
Lemma 3.1 (short-cycle moments). Fix d ≥ 3 d\ge3 d ≥ 3 and 1 ≤ k ≤ d − 1 1\le k\le d-1 1 ≤ k ≤ d − 1 . For any fixed m ≥ 1 m\ge1 m ≥ 1 and nonnegative integers r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m ,
E [ Z k ( P ) ∏ i = 1 m ( X i ) r i ] E Z k ( P ) ⟶ ∏ i = 1 m ( λ i ( 1 + δ i ) ) r i = ∏ i = 1 m ( ( d − 1 ) i + ( − 1 ) i 2 i ) r i . (10) \frac{\mathbb{E}\left[Z_k(P)\prod_{i=1}^{m}(X_i)_{r_i}\right]}{\mathbb{E}Z_k(P)}
\longrightarrow\prod_{i=1}^{m}\left(\lambda_i(1+\delta_i)\right)^{r_i}
=\prod_{i=1}^{m}\left(\frac{(d-1)^i+(-1)^i}{2i}\right)^{r_i}. \tag*{(10)} E Z k ( P ) E [ Z k ( P ) ∏ i = 1 m ( X i ) r i ] ⟶ i = 1 ∏ m ( λ i ( 1 + δ i ) ) r i = i = 1 ∏ m ( 2 i ( d − 1 ) i + ( − 1 ) i ) r i . (10)
Proof. By (9) , the left-hand side equals E Ω ∏ i ( X i ) r i \mathbb{E}_{\Omega}\prod_i(X_i)_{r_i} E Ω ∏ i ( X i ) r i for a uniform pair ( P , F ) ∈ Ω (P,F)\in\Omega ( P , F ) ∈ Ω . Generate ( P , F ) (P,F) ( P , F ) as described after (8) : choose independent uniform k k k -subsets A v ⊆ V v A_v\subseteq V_v A v ⊆ V v , then independent uniform perfect matchings F F F of A : = ⋃ v A v A:=\bigcup_v A_v A := ⋃ v A v and R R R of its complement, and set P = F ∪ R P=F\cup R P = F ∪ R . Call the points in A A A F F F -points and the remaining points R R R -points. Every pair of P P P joins either two F F F -points (an F F F -pair) or two R R R -points (an R R R -pair).
Directed closed walks. By dihedral symmetry, for every i ≥ 1 i\ge1 i ≥ 1 the number of directed closed walks of length i i i in P P P is 2 i X i 2iX_i 2 i X i . Such a walk consists of a sequence ( v 1 , … , v i ) (v_1,\ldots,v_i) ( v 1 , … , v i ) of distinct vertices together with points y j , x j ∈ V v j y_j,x_j\in V_{v_j} y j , x j ∈ V v j , y j ≠ x j y_j\ne x_j y j = x j , such that { x j , y j + 1 } ∈ P \{x_j,y_{j+1}\}\in P { x j , y j + 1 } ∈ P for each j j j , indices taken modulo i i i . The walk arrives at v j v_j v j through y j y_j y j and leaves through x j x_j x j .
A single cycle. Fix distinct vertices v 1 , … , v i v_1,\ldots,v_i v 1 , … , v i and a type τ j ∈ { F , R } \tau_j\in\{F,R\} τ j ∈ { F , R } for each edge j j j , that is, for the pair { x j , y j + 1 } \{x_j,y_{j+1}\} { x j , y j + 1 } . If τ j = F \tau_j=F τ j = F , the points x j x_j x j and y j + 1 y_{j+1} y j + 1 must both be F F F -points; if τ j = R \tau_j=R τ j = R , they must both be R R R -points. At vertex v j v_j v j , the entering edge j − 1 j-1 j − 1 and the leaving edge j j j have types ( τ j − 1 , τ j ) (\tau_{j-1},\tau_j) ( τ j − 1 , τ j ) . The number of ordered pairs ( y j , x j ) (y_j,x_j) ( y j , x j ) of distinct points of V v j V_{v_j} V v j with the prescribed memberships is w ( τ j − 1 , τ j ) w(\tau_{j-1},\tau_j) w ( τ j − 1 , τ j ) , where
w ( F , F ) = k ( k − 1 ) , w ( R , R ) = ( d − k ) ( d − k − 1 ) , w ( F , R ) = w ( R , F ) = k ( d − k ) . w(F,F)=k(k-1),\qquad w(R,R)=(d-k)(d-k-1),\qquad w(F,R)=w(R,F)=k(d-k). w ( F , F ) = k ( k − 1 ) , w ( R , R ) = ( d − k ) ( d − k − 1 ) , w ( F , R ) = w ( R , F ) = k ( d − k ) .
Conditional on the sets A v A_v A v , the i i i prescribed pairs are pairwise disjoint. If a a a of them have type F F F and b = i − a b=i-a b = i − a have type R R R , the independence of F F F and R R R gives the probability that all of them belong to P P P .
M ( k n − 2 a ) M ( k n ) ⋅ M ( ( d − k ) n − 2 b ) M ( ( d − k ) n ) = ∏ j = 0 a − 1 1 k n − 1 − 2 j ∏ j = 0 b − 1 1 ( d − k ) n − 1 − 2 j = ( k n ) − a ( ( d − k ) n ) − b ( 1 + O ( n − 1 ) ) . (11) \begin{aligned}
\frac{M(kn-2a)}{M(kn)}\cdot\frac{M((d-k)n-2b)}{M((d-k)n)}
=\prod_{j=0}^{a-1}\frac{1}{kn-1-2j}\prod_{j=0}^{b-1}\frac{1}{(d-k)n-1-2j} \\
&=(kn)^{-a}((d-k)n)^{-b}(1+O(n^{-1})). \tag*{(11)}
\end{aligned} M ( k n ) M ( k n − 2 a ) ⋅ M (( d − k ) n ) M (( d − k ) n − 2 b ) = j = 0 ∏ a − 1 k n − 1 − 2 j 1 j = 0 ∏ b − 1 ( d − k ) n − 1 − 2 j 1 = ( k n ) − a (( d − k ) n ) − b ( 1 + O ( n − 1 )) . (11)
Each F F F -edge has pairing probability ∼ 1 / ( k n ) \sim1/(kn) ∼ 1/ ( k n ) among the k n kn k n points assigned to F F F , and each R R R -edge has pairing probability ∼ 1 / ( ( d − k ) n ) \sim1/((d-k)n) ∼ 1/ (( d − k ) n ) among the remaining points. There are ( n ) i = n i ( 1 + O ( n − 1 ) ) (n)_i=n^i(1+O(n^{-1})) ( n ) i = n i ( 1 + O ( n − 1 )) choices for the vertices. At a vertex with entering type τ \tau τ and leaving type τ ′ \tau' τ ′ , the weight w ( τ , τ ′ ) w(\tau,\tau') w ( τ , τ ′ ) and the pairing probability of the leaving edge contribute the entry T τ τ ′ T_{\tau\tau'} T τ τ ′ , equal to w ( τ , τ ′ ) / k w(\tau,\tau')/k w ( τ , τ ′ ) / k or w ( τ , τ ′ ) / ( d − k ) w(\tau,\tau')/(d-k) w ( τ , τ ′ ) / ( d − k ) according as τ ′ \tau' τ ′ is F F F or R R R . Recording the sequence of edge types around the cycle by this transition matrix, and summing over the 2 i 2^i 2 i type sequences, shows that the expected number of directed closed walks of length i i i is
E Ω = ( 1 + O ( n − 1 ) ) tr ( T i ) . \mathbb{E}\Omega=(1+O(n^{-1}))\operatorname{tr}(T^i). E Ω = ( 1 + O ( n − 1 )) tr ( T i ) .
Order the types as ( F , R ) (F,R) ( F , R ) , so the first row and column refer to F F F -edges and the second to R R R -edges. Then
T = ( k − 1 k d − k d − k − 1 ) , tr T = d − 2 , det T = − ( d − 1 ) , T=\begin{pmatrix} k-1 & k \\ d-k & d-k-1 \end{pmatrix},\qquad\operatorname{tr}T=d-2,\qquad\det T=-(d-1), T = ( k − 1 d − k k d − k − 1 ) , tr T = d − 2 , det T = − ( d − 1 ) ,
so the eigenvalues of T T T are d − 1 d-1 d − 1 and − 1 -1 − 1 for every k k k . (With D = diag ( k , d − k ) D=\operatorname{diag}(\sqrt{k},\sqrt{d-k}) D = diag ( k , d − k ) , the matrix D − 1 T D D^{-1}TD D − 1 T D is symmetric, with diagonal entries k − 1 k-1 k − 1 , d − k − 1 d-k-1 d − k − 1 and off-diagonal entries k ( d − k ) \sqrt{k(d-k)} k ( d − k ) .) Hence tr ( T i ) = ( d − 1 ) i + ( − 1 ) i \operatorname{tr}(T^i)=(d-1)^i+(-1)^i tr ( T i ) = ( d − 1 ) i + ( − 1 ) i . Since the number of these walks is 2 i X i 2iX_i 2 i X i ,
E Ω X i ⟶ ( d − 1 ) i + ( − 1 ) i 2 i = λ i ( 1 + δ i ) . \mathbb{E}\Omega X_i\longrightarrow\frac{(d-1)^i+(-1)^i}{2i}=\lambda_i(1+\delta_i). E Ω X i ⟶ 2 i ( d − 1 ) i + ( − 1 ) i = λ i ( 1 + δ i ) .
Factorial moments. The product ∏ i ( X i ) r i \prod_i(X_i)_{r_i} ∏ i ( X i ) r i counts ordered tuples of r = ∑ i r i r=\sum_i r_i r = ∑ i r i pairwise distinct cycles, with r i r_i r i cycles of length i i i . It equals ∏ i ( 2 i ) − r i \prod_i(2i)^{-r_i} ∏ i ( 2 i ) − r i times the number of tuples of directed closed walks with pairwise distinct underlying cycles.
First consider tuples whose cycles are pairwise vertex-disjoint. Their vertices can be chosen in ( n ) u = n u ( 1 + O ( n − 1 ) ) (n)_u=n^u(1+O(n^{-1})) ( n ) u = n u ( 1 + O ( n − 1 )) ways, where u = ∑ i i r i u=\sum_i i r_i u = ∑ i i r i . The u u u prescribed pairs are pairwise disjoint, so (11) applies with a a a and b b b equal to the total numbers of F F F - and R R R -pairs. The weight therefore factorises over the cycles, and these tuples contribute ∏ i ( tr ( T i ) ) r i ( 1 + O ( n − 1 ) ) \prod_i(\operatorname{tr}(T^i))^{r_i}(1+O(n^{-1})) ∏ i ( tr ( T i ) ) r i ( 1 + O ( n − 1 )) . Dividing by ∏ i ( 2 i ) r i \prod_i(2i)^{r_i} ∏ i ( 2 i ) r i gives the right-hand side of (10) .
Now consider a tuple in which two cycles share a vertex. Let U U U be the union of its cycles, a multigraph with u ′ ≤ u u'\leq u u ′ ≤ u vertices and e ′ e' e ′ edges, where the edges are distinct pairs of P P P . There are O ( 1 ) O(1) O ( 1 ) possible isomorphism types, O ( n u ′ ) O(n^{u'}) O ( n u ′ ) choices of vertex labels and points for each type, and probability O ( n − e ′ ) O(n^{-e'}) O ( n − e ′ ) that the e ′ e' e ′ prescribed pairs belong to P P P , by (11) . This probability is zero unless the pairs are disjoint. Every connected component C C C of U U U contains a cycle, so e ( C ) ≥ u ( C ) e(C)\geq u(C) e ( C ) ≥ u ( C ) . If e ( C ) = u ( C ) e(C)=u(C) e ( C ) = u ( C ) , then C C C has cyclomatic number e ( C ) − u ( C ) + 1 = 1 e(C)-u(C)+1=1 e ( C ) − u ( C ) + 1 = 1 and contains exactly one cycle, with loops and pairs of parallel edges counted as cycles. Some component of U U U contains two distinct cycles from the tuple, so that component has e ( C ) ≥ u ( C ) + 1 e(C)\geq u(C)+1 e ( C ) ≥ u ( C ) + 1 . Therefore e ′ ≥ u ′ + 1 e'\geq u'+1 e ′ ≥ u ′ + 1 , and tuples with a shared vertex contribute O ( n u ′ − e ′ ) = O ( n − 1 ) O(n^{u'-e'})=O(n^{-1}) O ( n u ′ − e ′ ) = O ( n − 1 ) . This proves (10) . □
The second moment
In this section, we fix d ≥ 3 d\geq3 d ≥ 3 and 1 ≤ k ≤ d − 1 1\leq k\leq d-1 1 ≤ k ≤ d − 1 and prove the following lemma.
Lemma 4.1 (second moment). As n → ∞ n\to\infty n → ∞ with d n dn d n and k n kn k n even,
E [ Z k ( P ) 2 ] ( E Z k ( P ) ) 2 ⟶ d − 1 d − 2 = exp ( ∑ i = 1 ∞ λ i δ i 2 ) . (12) \frac{\mathbb{E}[Z_k(P)^2]}{(\mathbb{E}Z_k(P))^2}\longrightarrow\sqrt{\frac{d-1}{d-2}}=\exp\left(\sum_{i=1}^{\infty}\lambda_i\delta_i^2\right). \tag*{(12)} ( E Z k ( P ) ) 2 E [ Z k ( P ) 2 ] ⟶ d − 2 d − 1 = exp ( i = 1 ∑ ∞ λ i δ i 2 ) . (12)
For every pairing P P P , complementation F ↦ P ∖ F F \mapsto P \setminus F F ↦ P ∖ F is a bijection between the k k k -factors and the ( d − k ) (d-k) ( d − k ) -factors of P P P . Thus
Z d − k ( P ) = Z k ( P ) (13) Z_{d-k}(P)=Z_k(P) \tag*{(13)} Z d − k ( P ) = Z k ( P ) (13)
for every P ∈ P n , d P \in\mathcal{P}_{n,d} P ∈ P n , d and every n n n .
Both sides of (12) are invariant under k ↦ d − k k \mapsto d-k k ↦ d − k , so it suffices to prove Lemma 4.1 for k ≤ d / 2 k \le d/2 k ≤ d /2 . Throughout this section, we assume that 1 ≤ k ≤ d / 2 1 \le k \le d/2 1 ≤ k ≤ d /2 ; since d ≥ 3 d \ge3 d ≥ 3 , this excludes ( d , k ) = ( 2 , 1 ) (d,k)=(2,1) ( d , k ) = ( 2 , 1 ) . This reduction requires no asymptotic input such as contiguity: (13) is an identity of random variables, so all moments and limit distributions of Z k ( P ) Z_k(P) Z k ( P ) and Z d − k ( P ) Z_{d-k}(P) Z d − k ( P ) coincide exactly.
Let Hyp ( d , k , k ) \operatorname{Hyp}(d,k,k) Hyp ( d , k , k ) denote the hypergeometric distribution of the overlap of two independent uniform k k k -subsets of a d d d -set:
P ( H = j ) = ( k j ) ( d − k k − j ) ( d k ) ( 0 ≤ j ≤ k ) , \mathbb{P}(H=j)=\frac{\binom{k}{j}\binom{d-k}{k-j}}{\binom{d}{k}}
\qquad(0\le j\le k), P ( H = j ) = ( k d ) ( j k ) ( k − j d − k ) ( 0 ≤ j ≤ k ) ,
and all k + 1 k+1 k + 1 values have positive probability because k ≤ d − k k\le d-k k ≤ d − k . Its mean and variance are
μ H : = E H = k 2 d , σ H 2 : = Var H = k 2 ( d − k ) 2 d 2 ( d − 1 ) . (14) \mu_H:=\mathbb{E}H=\frac{k^2}{d},\qquad\sigma_H^2:=\operatorname{Var}H=\frac{k^2(d-k)^2}{d^2(d-1)}. \tag*{(14)} μ H := E H = d k 2 , σ H 2 := Var H = d 2 ( d − 1 ) k 2 ( d − k ) 2 . (14)
Reduction to a lattice sum
Lemma 4.2. Let H 1 , … , H n H_1,\ldots,H_n H 1 , … , H n be i.i.d. Hyp ( d , k , k ) \operatorname{Hyp}(d,k,k) Hyp ( d , k , k ) and S n = ∑ v = 1 n H v S_n=\sum_{v=1}^n H_v S n = ∑ v = 1 n H v . Then
E [ Z k ( P ) 2 ] ( E Z k ( P ) ) 2 = ∑ 0 ≤ σ ≤ k n σ e v e n P ( S n = σ ) R M ( σ ) , R M ( σ ) : = M ( σ ) M ( k n − σ ) 2 M ( ( d − 2 k ) n + σ ) M ( d n ) M ( k n ) 2 M ( ( d − k ) n ) 2 . (15) \frac{\mathbb{E}[Z_k(P)^2]}{(\mathbb{E}Z_k(P))^2}
=
\sum_{\substack{0\le\sigma\le kn\\ \sigma\ \mathrm{even}}}
\mathbb{P}(S_n=\sigma)R_M(\sigma),
\qquad
R_M(\sigma):=
\frac{M(\sigma)M(kn-\sigma)^2M((d-2k)n+\sigma)M(dn)}
{M(kn)^2M((d-k)n)^2}. \tag*{(15)} ( E Z k ( P ) ) 2 E [ Z k ( P ) 2 ] = 0 ≤ σ ≤ k n σ even ∑ P ( S n = σ ) R M ( σ ) , R M ( σ ) := M ( k n ) 2 M (( d − k ) n ) 2 M ( σ ) M ( k n − σ ) 2 M (( d − 2 k ) n + σ ) M ( d n ) . (15)
Proof. Z k ( P ) 2 Z_k(P)^2 Z k ( P ) 2 counts ordered pairs ( F 1 , F 2 ) (F_1,F_2) ( F 1 , F 2 ) of k k k -factors of P P P . Let A v , B v ⊆ V v A_v,B_v\subseteq V_v A v , B v ⊆ V v be the k k k -subsets of points covered by F 1 F_1 F 1 and F 2 F_2 F 2 , and put A = ⋃ v A v A=\bigcup_v A_v A = ⋃ v A v and B = ⋃ v B v B=\bigcup_v B_v B = ⋃ v B v . Given the sets ( A v , B v ) v (A_v,B_v)_v ( A v , B v ) v , the factors are determined by P P P : F 1 F_1 F 1 is the set of pairs of P P P within A A A , and F 2 F_2 F 2 is the set of pairs within B B B . Conversely, P P P extends ( A v , B v ) v (A_v,B_v)_v ( A v , B v ) v to a pair of k k k -factors if and only if P P P pairs A A A internally and pairs B B B internally.
We claim that this condition holds if and only if P P P pairs each of the four classes
A ∩ B , A ∖ B , B ∖ A , ( A ∪ B ) c A\cap B,\qquad A\setminus B,\qquad B\setminus A,\qquad(A\cup B)^c A ∩ B , A ∖ B , B ∖ A , ( A ∪ B ) c
internally. One direction is immediate. Conversely, suppose that A A A and B B B are paired internally. If x ∈ A ∩ B x\in A\cap B x ∈ A ∩ B , then its partner belongs to both A A A and B B B , and hence to A ∩ B A\cap B A ∩ B . If x ∈ A ∖ B x\in A\setminus B x ∈ A ∖ B , then its partner x ′ x' x ′ lies in A A A . If x ′ ∈ B x'\in B x ′ ∈ B , then x ′ ∈ A ∩ B x'\in A\cap B x ′ ∈ A ∩ B , so its partner x x x would lie in A ∩ B A\cap B A ∩ B , a contradiction. Hence x ′ ∈ A ∖ B x'\in A\setminus B x ′ ∈ A ∖ B . The argument for B ∖ A B\setminus A B ∖ A is symmetric, and the remaining class is then also paired internally.
Set H v : = ∣ A v ∩ B v ∣ H_v:=|A_v\cap B_v| H v := ∣ A v ∩ B v ∣ and σ : = ∑ v H v \sigma:=\sum_v H_v σ := ∑ v H v . The four classes have sizes σ \sigma σ , k n − σ kn-\sigma k n − σ , k n − σ kn-\sigma k n − σ , and ( d − 2 k ) n + σ (d-2k)n+\sigma ( d − 2 k ) n + σ . The number of pairings that extend ( A v , B v ) v (A_v,B_v)_v ( A v , B v ) v is therefore
M ( σ ) M ( k n − σ ) 2 M ( ( d − 2 k ) n + σ ) . M(\sigma)M(kn-\sigma)^2M((d-2k)n+\sigma). M ( σ ) M ( k n − σ ) 2 M (( d − 2 k ) n + σ ) .
Since k n kn k n and ( d − 2 k ) n = d n − 2 k n (d-2k)n=dn-2kn ( d − 2 k ) n = d n − 2 k n are even, all four sizes are even exactly when σ \sigma σ is even. Otherwise, there are no extensions. Summing over the ( d k ) 2 n \binom{d}{k}^{2n} ( k d ) 2 n choices of ( A v , B v ) v (A_v,B_v)_v ( A v , B v ) v and dividing by M ( d n ) M(dn) M ( d n ) gives
E [ Z k ( P ) 2 ] = ( d k ) 2 n M ( d n ) E [ M ( S n ) M ( k n − S n ) 2 M ( ( d − 2 k ) n + S n ) ] , \mathbb{E}[Z_k(P)^2]
=
\frac{\binom{d}{k}^{2n}}{M(dn)}
\mathbb{E}\left[M(S_n)M(kn-S_n)^2M((d-2k)n+S_n)\right], E [ Z k ( P ) 2 ] = M ( d n ) ( k d ) 2 n E [ M ( S n ) M ( k n − S n ) 2 M (( d − 2 k ) n + S n ) ] ,
where the overlaps H v = ∣ A v ∩ B v ∣ H_v=|A_v\cap B_v| H v = ∣ A v ∩ B v ∣ of independent uniform k k k -subsets A v , B v ⊆ V v A_v,B_v\subseteq V_v A v , B v ⊆ V v are i.i.d. Hyp ( d , k , k ) \operatorname{Hyp}(d,k,k) Hyp ( d , k , k ) . Dividing by ( E Z k ( P ) ) 2 = ( d k ) 2 n M ( k n ) 2 M ( ( d − k ) n ) 2 / M ( d n ) 2 (\mathbb{E}Z_k(P))^2=\binom{d}{k}^{2n}M(kn)^2M((d-k)n)^2/M(dn)^2 ( E Z k ( P ) ) 2 = ( k d ) 2 n M ( k n ) 2 M (( d − k ) n ) 2 / M ( d n ) 2 , from (8) , gives (15) . ∎
Stirling bounds
Define, with the convention 0 log 0 = 0 0\log0=0 0 log 0 = 0 ,
g ( s ) : = s 2 log s + ( k − s ) log ( k − s ) + d − 2 k + s 2 log ( d − 2 k + s ) + d 2 log d − k log k − ( d − k ) log ( d − k ) (16) g(s) := \frac{s}{2}\log s+(k-s)\log(k-s)+\frac{d-2k+s}{2}\log(d-2k+s)+\frac{d}{2}\log d-k\log k-(d-k)\log(d-k) \tag*{(16)} g ( s ) := 2 s log s + ( k − s ) log ( k − s ) + 2 d − 2 k + s log ( d − 2 k + s ) + 2 d log d − k log k − ( d − k ) log ( d − k ) (16)
for 0 ≤ s ≤ k 0\le s\le k 0 ≤ s ≤ k .
Lemma 4.3. (a) For every even σ \sigma σ with 0 ≤ σ ≤ k n 0\le\sigma\le kn 0 ≤ σ ≤ k n , R M ( σ ) ≤ 32 e n g ( σ / n ) R_M(\sigma)\le32e^{ng(\sigma/n)} R M ( σ ) ≤ 32 e n g ( σ / n ) .
(b) For every compact J ⊂ ( 0 , k ) J\subset(0,k) J ⊂ ( 0 , k ) , R M ( σ ) = 2 e n g ( σ / n ) ( 1 + O ( n − 1 ) ) R_M(\sigma)=\sqrt{2}e^{ng(\sigma/n)}(1+O(n^{-1})) R M ( σ ) = 2 e n g ( σ / n ) ( 1 + O ( n − 1 )) uniformly over even σ \sigma σ with σ / n ∈ J \sigma/n\in J σ / n ∈ J .
(c) g g g is continuous on [ 0 , k ] [0,k] [ 0 , k ] and smooth on ( 0 , k ) (0,k) ( 0 , k ) , with g ( μ H ) = g ′ ( μ H ) = 0 g(\mu_H)=g'(\mu_H)=0 g ( μ H ) = g ′ ( μ H ) = 0 ,
g ′ ′ ( s ) = 1 2 s + 1 k − s + 1 2 ( d − 2 k + s ) ( 0 < s < k ) , g ′ ′ ( μ H ) = d 3 2 k 2 ( d − k ) 2 . g''(s)=\frac{1}{2s}+\frac{1}{k-s}+\frac{1}{2(d-2k+s)}\qquad(0<s<k),\qquad g''(\mu_H)=\frac{d^3}{2k^2(d-k)^2}. g ′′ ( s ) = 2 s 1 + k − s 1 + 2 ( d − 2 k + s ) 1 ( 0 < s < k ) , g ′′ ( μ H ) = 2 k 2 ( d − k ) 2 d 3 .
Proof. (a) The bounds 2 π N ( N / e ) N ≤ N ! ≤ e N ( N / e ) N \sqrt{2\pi N}(N/e)^N\le N!\le e\sqrt{N}(N/e)^N 2 π N ( N / e ) N ≤ N ! ≤ e N ( N / e ) N for N ≥ 1 N\ge1 N ≥ 1 give, for all ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 ,
2 π e ( 2 ℓ e ) ℓ ≤ M ( 2 ℓ ) = ( 2 ℓ ) ! ℓ ! 2 ℓ ≤ e π ( 2 ℓ e ) ℓ , \frac{2\sqrt{\pi}}{e}\left(\frac{2\ell}{e}\right)^\ell\le M(2\ell)=\frac{(2\ell)!}{\ell!2^\ell}\le\frac{e}{\sqrt{\pi}}\left(\frac{2\ell}{e}\right)^\ell, e 2 π ( e 2 ℓ ) ℓ ≤ M ( 2 ℓ ) = ℓ ! 2 ℓ ( 2 ℓ )! ≤ π e ( e 2 ℓ ) ℓ ,
hence
( 2 ℓ e ) ℓ ≤ M ( 2 ℓ ) ≤ 2 ( 2 ℓ e ) ℓ \left(\frac{2\ell}{e}\right)^\ell\le M(2\ell)\le2\left(\frac{2\ell}{e}\right)^\ell ( e 2 ℓ ) ℓ ≤ M ( 2 ℓ ) ≤ 2 ( e 2 ℓ ) ℓ
for all ℓ ≥ 0 \ell\ge0 ℓ ≥ 0 , with 0 0 = 1 0^0=1 0 0 = 1 . For ℓ = 0 \ell=0 ℓ = 0 , the last display reads 1 ≤ 1 ≤ 2 1\le1\le2 1 ≤ 1 ≤ 2 . Apply the upper bound to the five factors in the numerator of R M ( σ ) R_M(\sigma) R M ( σ ) and the lower bound to the four factors in the denominator. The exponents of e e e and of n n n cancel because
σ 2 + ( k n − σ ) + ( d − 2 k ) n + σ 2 + d n 2 = d n = k n + ( d − k ) n . \frac{\sigma}{2}+(kn-\sigma)+\frac{(d-2k)n+\sigma}{2}+\frac{dn}{2}=dn=kn+(d-k)n. 2 σ + ( k n − σ ) + 2 ( d − 2 k ) n + σ + 2 d n = d n = k n + ( d − k ) n .
and hence R M ( σ ) ≤ 2 5 e n g ( σ / n ) R_M(\sigma)\le2^5e^{ng(\sigma/n)} R M ( σ ) ≤ 2 5 e n g ( σ / n ) . Here g g g collects the logarithms of σ / n \sigma/n σ / n , ( k n − σ ) / n (kn-\sigma)/n ( k n − σ ) / n , ( ( d − 2 k ) n + σ ) / n ((d-2k)n+\sigma)/n (( d − 2 k ) n + σ ) / n , d d d , k k k , and d − k d-k d − k , with the coefficients in (16) . Some of the arguments σ \sigma σ , k n − σ kn-\sigma k n − σ , and ( d − 2 k ) n + σ (d-2k)n+\sigma ( d − 2 k ) n + σ may vanish; the case ℓ = 0 \ell=0 ℓ = 0 and the convention 0 log 0 = 0 0\log0=0 0 log 0 = 0 cover these possibilities.
(b) If σ / n ∈ J \sigma/n\in J σ / n ∈ J , all nine arguments are of order n n n . Applying M ( 2 ℓ ) = 2 ( 2 ℓ / e ) ℓ ( 1 + O ( ℓ − 1 ) ) M(2\ell)=\sqrt{2}(2\ell/e)^\ell(1+O(\ell^{-1})) M ( 2 ℓ ) = 2 ( 2 ℓ / e ) ℓ ( 1 + O ( ℓ − 1 )) to each factor gives the result, with the factor ( 2 ) 5 − 4 = 2 (\sqrt{2})^{5-4}=\sqrt{2} ( 2 ) 5 − 4 = 2 .
(c) Continuity on [ 0 , k ] [0,k] [ 0 , k ] follows from x log x → 0 x\log x\to0 x log x → 0 as x ↓ 0 x\downarrow0 x ↓ 0 . Differentiation gives
g ′ ( s ) = 1 2 log s − log ( k − s ) + 1 2 log ( d − 2 k + s ) , g'(s)=\frac{1}{2}\log s-\log(k-s)+\frac{1}{2}\log(d-2k+s), g ′ ( s ) = 2 1 log s − log ( k − s ) + 2 1 log ( d − 2 k + s ) ,
and g ′ ′ g'' g ′′ has the stated form. At μ H = k 2 / d \mu_H=k^2/d μ H = k 2 / d , we have k − μ H = k ( d − k ) / d k-\mu_H=k(d-k)/d k − μ H = k ( d − k ) / d and d − 2 k + μ H = ( d − k ) 2 / d d-2k+\mu_H=(d-k)^2/d d − 2 k + μ H = ( d − k ) 2 / d . Thus g ′ ( μ H ) = log k − 1 2 log d − log k − log ( d − k ) + log d + log ( d − k ) − 1 2 log d = 0 g'(\mu_H)=\log k-\frac{1}{2}\log d-\log k-\log(d-k)+\log d+\log(d-k)-\frac{1}{2}\log d=0 g ′ ( μ H ) = log k − 2 1 log d − log k − log ( d − k ) + log d + log ( d − k ) − 2 1 log d = 0 . In g ( μ H ) g(\mu_H) g ( μ H ) , the coefficients of log k \log k log k , log ( d − k ) \log(d-k) log ( d − k ) , and log d \log d log d are k 2 d + k ( d − k ) d − k = 0 \frac{k^2}{d}+\frac{k(d-k)}{d}-k=0 d k 2 + d k ( d − k ) − k = 0 , k ( d − k ) d + ( d − k ) 2 d − ( d − k ) = 0 \frac{k(d-k)}{d}+\frac{(d-k)^2}{d}-(d-k)=0 d k ( d − k ) + d ( d − k ) 2 − ( d − k ) = 0 , and − k 2 + 2 k ( d − k ) + ( d − k ) 2 2 d + d 2 = 0 -\frac{k^2+2k(d-k)+(d-k)^2}{2d}+\frac{d}{2}=0 − 2 d k 2 + 2 k ( d − k ) + ( d − k ) 2 + 2 d = 0 , respectively. Finally,
g ′ ′ ( μ H ) = d 2 k 2 + d k ( d − k ) + d 2 ( d − k ) 2 = d 2 ( 1 k + 1 d − k ) 2 = d 3 2 k 2 ( d − k ) 2 . g''(\mu_H)=\frac{d}{2k^2}+\frac{d}{k(d-k)}+\frac{d}{2(d-k)^2}=\frac{d}{2}\left(\frac{1}{k}+\frac{1}{d-k}\right)^2=\frac{d^3}{2k^2(d-k)^2}. g ′′ ( μ H ) = 2 k 2 d + k ( d − k ) d + 2 ( d − k ) 2 d = 2 d ( k 1 + d − k 1 ) 2 = 2 k 2 ( d − k ) 2 d 3 .
The hypergeometric distribution is a Poisson-binomial distribution
Lemma 4.4. Let 1 ≤ k ≤ d / 2 1\le k\le d/2 1 ≤ k ≤ d /2 and H ∼ Hyp ( d , k , k ) H\sim\operatorname{Hyp}(d,k,k) H ∼ Hyp ( d , k , k ) . There exist distinct p 1 , … , p k ∈ ( 0 , 1 ) p_1,\ldots,p_k\in(0,1) p 1 , … , p k ∈ ( 0 , 1 ) such that
E [ t H ] = ∏ i = 1 k ( 1 − p i + p i t ) ( t ∈ R ) , \mathbb{E}[t^H]=\prod_{i=1}^{k}(1-p_i+p_it)\qquad(t\in\mathbb{R}), E [ t H ] = i = 1 ∏ k ( 1 − p i + p i t ) ( t ∈ R ) , that is, H H H has the distribution of a sum of k k k independent Bernoulli( p i ) (p_i) ( p i ) variables. In particular, ∑ i p i = μ H \sum_i p_i=\mu_H ∑ i p i = μ H and ∑ i p i ( 1 − p i ) = σ H 2 \sum_i p_i(1-p_i)=\sigma_H^2 ∑ i p i ( 1 − p i ) = σ H 2 .
Proof. Consider the polynomials
p ( u ) : = u d − k ( u − 1 ) k , Q ( u ) : = ∑ j = 0 k ( k j ) ( d − k k − j ) u j ( u − 1 ) k − j . p(u) := u^{d-k}(u-1)^k,\qquad Q(u) := \sum_{j=0}^{k} \binom{k}{j}\binom{d-k}{k-j}u^j(u-1)^{k-j}. p ( u ) := u d − k ( u − 1 ) k , Q ( u ) := j = 0 ∑ k ( j k ) ( k − j d − k ) u j ( u − 1 ) k − j .
The Leibniz rule gives
1 k ! d k d u k [ u d − k ( u − 1 ) k ] = ∑ i = 0 k ( k i ) ( d − k i ) u d − k − i ( u − 1 ) i = u d − 2 k ∑ j = 0 k ( k j ) ( d − k k − j ) u j ( u − 1 ) k − j , \frac{1}{k!}\frac{d^k}{du^k}\left[u^{d-k}(u-1)^k\right] = \sum_{i=0}^{k}\binom{k}{i}\binom{d-k}{i}u^{d-k-i}(u-1)^i = u^{d-2k}\sum_{j=0}^{k}\binom{k}{j}\binom{d-k}{k-j}u^j(u-1)^{k-j}, k ! 1 d u k d k [ u d − k ( u − 1 ) k ] = i = 0 ∑ k ( i k ) ( i d − k ) u d − k − i ( u − 1 ) i = u d − 2 k j = 0 ∑ k ( j k ) ( k − j d − k ) u j ( u − 1 ) k − j ,
where we substituted j = k − i j=k-i j = k − i . Hence 1 k ! p ( k ) ( u ) = u d − 2 k Q ( u ) \frac{1}{k!}p^{(k)}(u)=u^{d-2k}Q(u) k ! 1 p ( k ) ( u ) = u d − 2 k Q ( u ) .
We claim that, for 0 ≤ i ≤ k 0\le i\le k 0 ≤ i ≤ k , the polynomial p ( i ) p^{(i)} p ( i ) , of degree d − i d-i d − i , has a zero of multiplicity exactly d − k − i d-k-i d − k − i at 0, a zero of multiplicity exactly k − i k-i k − i at 1, and i i i distinct simple zeros in ( 0 , 1 ) (0,1) ( 0 , 1 ) . These are all its zeros. The claim holds for i = 0 i=0 i = 0 . Suppose it holds for some i < k i<k i < k . Then p ( i + 1 ) p^{(i+1)} p ( i + 1 ) vanishes to order exactly d − k − i − 1 ≥ 0 d-k-i-1\ge0 d − k − i − 1 ≥ 0 at 0 and k − i − 1 ≥ 0 k-i-1\ge0 k − i − 1 ≥ 0 at 1. By Rolle’s theorem, it has a zero strictly between every two consecutive zeros of p ( i ) p^{(i)} p ( i ) in [ 0 , 1 ] [0,1] [ 0 , 1 ] . This gives i + 1 i+1 i + 1 zeros in ( 0 , 1 ) (0,1) ( 0 , 1 ) : between 0 and the smallest interior zero, between consecutive interior zeros, and between the largest interior zero and 1. The listed zeros number ( d − k − i − 1 ) + ( k − i − 1 ) + ( i + 1 ) = d − i − 1 = deg p ( i + 1 ) (d-k-i-1)+(k-i-1)+(i+1)=d-i-1=\deg p^{(i+1)} ( d − k − i − 1 ) + ( k − i − 1 ) + ( i + 1 ) = d − i − 1 = deg p ( i + 1 ) . They are therefore all the zeros, and the interior zeros are simple.
For i = k i=k i = k , we conclude that u d − 2 k Q ( u ) u^{d-2k}Q(u) u d − 2 k Q ( u ) has exactly k k k simple zeros u 1 < ⋯ < u k u_1<\cdots<u_k u 1 < ⋯ < u k in ( 0 , 1 ) (0,1) ( 0 , 1 ) besides u = 0 u=0 u = 0 . Thus Q Q Q has the k k k simple zeros u 1 , … , u k ∈ ( 0 , 1 ) u_1,\ldots,u_k\in(0,1) u 1 , … , u k ∈ ( 0 , 1 ) . Since deg Q ≤ k \deg Q\le k deg Q ≤ k and the coefficient of u k u^k u k in Q Q Q is ∑ j ( k j ) ( d − k k − j ) = ( d k ) \sum_j\binom{k}{j}\binom{d-k}{k-j}=\binom{d}{k} ∑ j ( j k ) ( k − j d − k ) = ( k d ) ,
Q ( u ) = ( d k ) ∏ i = 1 k ( u − u i ) . Q(u)=\binom{d}{k}\prod_{i=1}^{k}(u-u_i). Q ( u ) = ( k d ) i = 1 ∏ k ( u − u i ) .
On the other hand, for u ≠ 1 u\ne1 u = 1 ,
Q ( u ) = ( u − 1 ) k ∑ j = 0 k ( k j ) ( d − k k − j ) ( u u − 1 ) j = ( d k ) ( u − 1 ) k E [ ( u u − 1 ) H ] . Q(u)=(u-1)^k\sum_{j=0}^{k}\binom{k}{j}\binom{d-k}{k-j}\left(\frac{u}{u-1}\right)^j=\binom{d}{k}(u-1)^k\mathbb{E}\left[\left(\frac{u}{u-1}\right)^H\right]. Q ( u ) = ( u − 1 ) k j = 0 ∑ k ( j k ) ( k − j d − k ) ( u − 1 u ) j = ( k d ) ( u − 1 ) k E [ ( u − 1 u ) H ] .
Compare the two expressions and substitute t = u / ( u − 1 ) t=u/(u-1) t = u / ( u − 1 ) , so u − 1 = 1 / ( t − 1 ) u-1=1/(t-1) u − 1 = 1/ ( t − 1 ) and ( u − u i ) / ( u − 1 ) = ( 1 − u i ) t + u i (u-u_i)/(u-1)=(1-u_i)t+u_i ( u − u i ) / ( u − 1 ) = ( 1 − u i ) t + u i . We obtain
E [ t H ] = ∏ i = 1 k u − u i u − 1 = ∏ i = 1 k ( u i + ( 1 − u i ) t ) \mathbb{E}[t^H]=\prod_{i=1}^{k}\frac{u-u_i}{u-1}=\prod_{i=1}^{k}\left(u_i+(1-u_i)t\right) E [ t H ] = i = 1 ∏ k u − 1 u − u i = i = 1 ∏ k ( u i + ( 1 − u i ) t )
for all t ≠ 1 t\ne1 t = 1 . At t = 1 t=1 t = 1 both sides equal 1, so the identity holds for all t t t . Set p i : = 1 − u i ∈ ( 0 , 1 ) p_i:=1-u_i\in(0,1) p i := 1 − u i ∈ ( 0 , 1 ) . The p i p_i p i are distinct, and
E [ t H ] = ∏ i = 1 k ( 1 − p i + p i t ) \mathbb{E}[t^H]=\prod_{i=1}^{k}(1-p_i+p_it) E [ t H ] = i = 1 ∏ k ( 1 − p i + p i t )
for all t t t . Thus H H H has the distribution of a sum of k k k independent Bernoulli( p i ) (p_i) ( p i ) variables, with mean ∑ i p i \sum_i p_i ∑ i p i and variance ∑ i p i ( 1 − p i ) \sum_i p_i(1-p_i) ∑ i p i ( 1 − p i ) . Hence ∑ i p i = μ H \sum_i p_i=\mu_H ∑ i p i = μ H and ∑ i p i ( 1 − p i ) = σ H 2 \sum_i p_i(1-p_i)=\sigma_H^2 ∑ i p i ( 1 − p i ) = σ H 2 , by (14).
Exponential tilting and the rate function
Let K ( θ ) : = log E e θ H K(\theta):=\log\mathbb{E}e^{\theta H} K ( θ ) := log E e θ H , θ ∈ R \theta\in\mathbb{R} θ ∈ R , be the cumulant generating function of H ∼ Hyp ( d , k , k ) H\sim\operatorname{Hyp}(d,k,k) H ∼ Hyp ( d , k , k ) . For θ ∈ R \theta\in\mathbb{R} θ ∈ R , let P θ \mathbb{P}_\theta P θ be the probability measure under which H 1 , … , H n H_1,\ldots,H_n H 1 , … , H n are i.i.d. with the tilted distribution
P θ ( H 1 = j ) = P ( H 1 = j ) e θ j − K ( θ ) ( 0 ≤ j ≤ k ) . \mathbb{P}_\theta(H_1=j)=\mathbb{P}(H_1=j)e^{\theta j-K(\theta)}\qquad(0\le j\le k). P θ ( H 1 = j ) = P ( H 1 = j ) e θ j − K ( θ ) ( 0 ≤ j ≤ k ) .
By Lemma 4.4 , K ( θ ) = ∑ i = 1 k log ( 1 − p i + p i e θ ) K(\theta)=\sum_{i=1}^{k}\log(1-p_i+p_ie^\theta) K ( θ ) = ∑ i = 1 k log ( 1 − p i + p i e θ ) , and the tilted probability generating function is
E θ [ t H 1 ] = E [ ( t e θ ) H 1 ] E [ e θ H 1 ] = ∏ i = 1 k ( 1 − q i ( θ ) + q i ( θ ) t ) , q i ( θ ) : = p i e θ 1 − p i + p i e θ . (17) \mathbb{E}_\theta[t^{H_1}]=\frac{\mathbb{E}[(te^\theta)^{H_1}]}{\mathbb{E}[e^{\theta H_1}]}=\prod_{i=1}^{k}(1-q_i(\theta)+q_i(\theta)t),\qquad q_i(\theta):=\frac{p_i e^\theta}{1-p_i+p_i e^\theta}. \tag*{(17)} E θ [ t H 1 ] = E [ e θ H 1 ] E [( t e θ ) H 1 ] = i = 1 ∏ k ( 1 − q i ( θ ) + q i ( θ ) t ) , q i ( θ ) := 1 − p i + p i e θ p i e θ . (17)
so that, under P θ P_\theta P θ , H 1 H_1 H 1 is again a sum of k k k independent Bernoulli variables. Their parameters q i ( θ ) q_i(\theta) q i ( θ ) are distinct for each fixed θ \theta θ because q i ( θ ) q_i(\theta) q i ( θ ) is strictly increasing in p i p_i p i . Consequently,
K ′ ( θ ) = E θ H 1 = ∑ i = 1 k q i ( θ ) , K ′ ′ ( θ ) = Var θ H 1 = ∑ i = 1 k q i ( θ ) ( 1 − q i ( θ ) ) > 0. (18) K'(\theta)=\mathbb{E}_\theta H_1=\sum_{i=1}^{k}q_i(\theta),\qquad K''(\theta)=\operatorname{Var}_\theta H_1=\sum_{i=1}^{k}q_i(\theta)(1-q_i(\theta))>0. \tag*{(18)} K ′ ( θ ) = E θ H 1 = i = 1 ∑ k q i ( θ ) , K ′′ ( θ ) = Var θ H 1 = i = 1 ∑ k q i ( θ ) ( 1 − q i ( θ )) > 0. (18)
Since q i ( θ ) → 0 q_i(\theta)\to0 q i ( θ ) → 0 as θ → − ∞ \theta\to-\infty θ → − ∞ and q i ( θ ) → 1 q_i(\theta)\to1 q i ( θ ) → 1 as θ → ∞ \theta\to\infty θ → ∞ , K ′ K' K ′ is a smooth increasing bijection from R \mathbb{R} R to ( 0 , k ) (0,k) ( 0 , k ) . Let θ ( s ) \theta(s) θ ( s ) , 0 < s < k 0<s<k 0 < s < k , be its inverse. This function is smooth, and θ ( μ H ) = 0 \theta(\mu_H)=0 θ ( μ H ) = 0 because K ′ ( 0 ) = E H = μ H K'(0)=\mathbb{E}H=\mu_H K ′ ( 0 ) = E H = μ H . Define the rate function and the comparison function by
ρ ( s ) : = sup θ ∈ R { θ s − K ( θ ) } ( 0 ≤ s ≤ k ) , Φ ( s ) : = g ( s ) − ρ ( s ) . (19) \rho(s):=\sup_{\theta\in\mathbb{R}}\{\theta s-K(\theta)\}\quad(0\leq s\leq k),\qquad\Phi(s):=g(s)-\rho(s). \tag*{(19)} ρ ( s ) := θ ∈ R sup { θ s − K ( θ )} ( 0 ≤ s ≤ k ) , Φ ( s ) := g ( s ) − ρ ( s ) . (19)
For 0 < s < k 0<s<k 0 < s < k , the supremum is attained at θ = θ ( s ) \theta=\theta(s) θ = θ ( s ) because the derivative of the concave function θ ↦ θ s − K ( θ ) \theta\mapsto\theta s-K(\theta) θ ↦ θ s − K ( θ ) is s − K ′ ( θ ) s-K'(\theta) s − K ′ ( θ ) . Thus ρ ( s ) = θ ( s ) s − K ( θ ( s ) ) \rho(s)=\theta(s)s-K(\theta(s)) ρ ( s ) = θ ( s ) s − K ( θ ( s )) .
Lemma 4.5. (a) ρ \rho ρ is smooth on ( 0 , k ) (0,k) ( 0 , k ) with ρ ′ ( s ) = θ ( s ) \rho'(s)=\theta(s) ρ ′ ( s ) = θ ( s ) and ρ ′ ′ ( s ) = 1 / K ′ ′ ( θ ( s ) ) \rho''(s)=1/K''(\theta(s)) ρ ′′ ( s ) = 1/ K ′′ ( θ ( s )) , and ρ ( μ H ) = ρ ′ ( μ H ) = 0 \rho(\mu_H)=\rho'(\mu_H)=0 ρ ( μ H ) = ρ ′ ( μ H ) = 0 .
(b) For 0 < s < k 0<s<k 0 < s < k ,
ρ ′ ′ ( s ) = 1 K ′ ′ ( θ ( s ) ) ≥ 1 s + 1 k − s ≥ g ′ ′ ( s ) , 1 s + 1 k − s − g ′ ′ ( s ) = d − 2 k 2 s ( d − 2 k + s ) , \rho''(s)=\frac{1}{K''(\theta(s))}\geq\frac{1}{s}+\frac{1}{k-s}\geq g''(s),\qquad\frac{1}{s}+\frac{1}{k-s}-g''(s)=\frac{d-2k}{2s(d-2k+s)}, ρ ′′ ( s ) = K ′′ ( θ ( s )) 1 ≥ s 1 + k − s 1 ≥ g ′′ ( s ) , s 1 + k − s 1 − g ′′ ( s ) = 2 s ( d − 2 k + s ) d − 2 k , and at least one of the two inequalities is strict. Hence Φ ′ ′ < 0 \Phi''<0 Φ ′′ < 0 on ( 0 , k ) (0,k) ( 0 , k ) , Φ ( μ H ) = Φ ′ ( μ H ) = 0 \Phi(\mu_H)=\Phi'(\mu_H)=0 Φ ( μ H ) = Φ ′ ( μ H ) = 0 , and
Φ ′ ′ ( μ H ) = g ′ ′ ( μ H ) − 1 σ H 2 = − d 2 ( d − 2 ) 2 k 2 ( d − k ) 2 < 0. \Phi''(\mu_H)=g''(\mu_H)-\frac{1}{\sigma_H^2}=-\frac{d^2(d-2)}{2k^2(d-k)^2}<0. Φ ′′ ( μ H ) = g ′′ ( μ H ) − σ H 2 1 = − 2 k 2 ( d − k ) 2 d 2 ( d − 2 ) < 0. (c) Φ \Phi Φ is continuous on [ 0 , k ] [0,k] [ 0 , k ] , and there is c = c ( d , k ) > 0 c=c(d,k)>0 c = c ( d , k ) > 0 such that Φ ( s ) ≤ − c ( s − μ H ) 2 \Phi(s)\leq-c(s-\mu_H)^2 Φ ( s ) ≤ − c ( s − μ H ) 2 for all 0 ≤ s ≤ k 0\leq s\leq k 0 ≤ s ≤ k .
(d) For every θ ∈ R \theta\in\mathbb{R} θ ∈ R and every integer σ \sigma σ with 0 ≤ σ ≤ k n 0\leq\sigma\leq kn 0 ≤ σ ≤ k n , writing s = σ / n s=\sigma/n s = σ / n ,
P ( S n = σ ) = e − n ( θ s − K ( θ ) ) P θ ( S n = σ ) , hence P ( S n = σ ) ≤ e − n ρ ( s ) (20) \mathbb{P}(S_n=\sigma)=e^{-n(\theta s-K(\theta))}\mathbb{P}_\theta(S_n=\sigma),\qquad\text{hence}\qquad\mathbb{P}(S_n=\sigma)\leq e^{-n\rho(s)} \tag*{(20)} P ( S n = σ ) = e − n ( θ s − K ( θ )) P θ ( S n = σ ) , hence P ( S n = σ ) ≤ e − n ρ ( s ) (20) and, for even σ \sigma σ , P ( S n = σ ) R M ( σ ) ≤ 32 e n Φ ( s ) \mathbb{P}(S_n=\sigma)R_M(\sigma)\leq32e^{n\Phi(s)} P ( S n = σ ) R M ( σ ) ≤ 32 e n Φ ( s ) .
Proof. (a) Differentiating ρ ( s ) = θ ( s ) s − K ( θ ( s ) ) \rho(s)=\theta(s)s-K(\theta(s)) ρ ( s ) = θ ( s ) s − K ( θ ( s )) gives ρ ′ ( s ) = θ ( s ) + θ ′ ( s ) ( s − K ′ ( θ ( s ) ) ) = θ ( s ) \rho'(s)=\theta(s)+\theta'(s)(s-K'(\theta(s)))=\theta(s) ρ ′ ( s ) = θ ( s ) + θ ′ ( s ) ( s − K ′ ( θ ( s ))) = θ ( s ) . The inverse function theorem gives ρ ′ ′ ( s ) = θ ′ ( s ) = 1 / K ′ ′ ( θ ( s ) ) \rho''(s)=\theta'(s)=1/K''(\theta(s)) ρ ′′ ( s ) = θ ′ ( s ) = 1/ K ′′ ( θ ( s )) . At μ H \mu_H μ H , θ ( μ H ) = 0 \theta(\mu_H)=0 θ ( μ H ) = 0 and K ( 0 ) = 0 K(0)=0 K ( 0 ) = 0 , so ρ ( μ H ) = ρ ′ ( μ H ) = 0 \rho(\mu_H)=\rho'(\mu_H)=0 ρ ( μ H ) = ρ ′ ( μ H ) = 0 .
(b) Put q i = q i ( θ ( s ) ) q_i=q_i(\theta(s)) q i = q i ( θ ( s )) , so ∑ i q i = s \sum_iq_i=s ∑ i q i = s by (18) . The Cauchy–Schwarz inequality gives ∑ i q i 2 ≥ ( ∑ i q i ) 2 / k = s 2 / k \sum_iq_i^2\geq(\sum_iq_i)^2/k=s^2/k ∑ i q i 2 ≥ ( ∑ i q i ) 2 / k = s 2 / k , with equality if and only if all q i q_i q i are equal. Hence
K ′ ′ ( θ ( s ) ) = ∑ i q i ( 1 − q i ) = s − ∑ i q i 2 ≤ s − s 2 k = s ( k − s ) k , i.e. 1 K ′ ′ ( θ ( s ) ) ≥ 1 s + 1 k − s . K''(\theta(s))=\sum_iq_i(1-q_i)=s-\sum_iq_i^2\leq s-\frac{s^2}{k}=\frac{s(k-s)}{k},\qquad\text{i.e.}\qquad\frac{1}{K''(\theta(s))}\geq\frac{1}{s}+\frac{1}{k-s}. K ′′ ( θ ( s )) = i ∑ q i ( 1 − q i ) = s − i ∑ q i 2 ≤ s − k s 2 = k s ( k − s ) , i.e. K ′′ ( θ ( s )) 1 ≥ s 1 + k − s 1 .
If k ≥ 2 k\geq2 k ≥ 2 , the q i q_i q i are distinct, so this inequality is strict. The identity for 1 s + 1 k − s − g ′ ′ ( s ) \frac{1}{s}+\frac{1}{k-s}-g''(s) s 1 + k − s 1 − g ′′ ( s ) follows from Lemma 4.3 (c):
1 s − 1 2 s − 1 2 ( d − 2 k + s ) = ( d − 2 k + s ) − s 2 s ( d − 2 k + s ) . \frac{1}{s}-\frac{1}{2s}-\frac{1}{2(d-2k+s)}=\frac{(d-2k+s)-s}{2s(d-2k+s)}. s 1 − 2 s 1 − 2 ( d − 2 k + s ) 1 = 2 s ( d − 2 k + s ) ( d − 2 k + s ) − s .
It is nonnegative and is strictly positive if d > 2 k d>2k d > 2 k . If k = 1 k=1 k = 1 , then d ≥ 3 > 2 k d\geq3>2k d ≥ 3 > 2 k . Thus ρ ′ ′ ( s ) > g ′ ′ ( s ) \rho''(s)>g''(s) ρ ′′ ( s ) > g ′′ ( s ) for 0 < s < k 0<s<k 0 < s < k , that is, Φ ′ ′ ( s ) < 0 \Phi''(s)<0 Φ ′′ ( s ) < 0 .
Part (a) and Lemma 4.3 (c) give Φ ( μ H ) = g ( μ H ) − ρ ( μ H ) = 0 \Phi(\mu_H)=g(\mu_H)-\rho(\mu_H)=0 Φ ( μ H ) = g ( μ H ) − ρ ( μ H ) = 0 and Φ ′ ( μ H ) = g ′ ( μ H ) − θ ( μ H ) = 0 \Phi'(\mu_H)=g'(\mu_H)-\theta(\mu_H)=0 Φ ′ ( μ H ) = g ′ ( μ H ) − θ ( μ H ) = 0 . Finally, K ′ ′ ( 0 ) = Var H = σ H 2 K''(0)=\operatorname{Var}H=\sigma_H^2 K ′′ ( 0 ) = Var H = σ H 2 , so
Φ ′ ′ ( μ H ) = g ′ ′ ( μ H ) − 1 σ H 2 = d 3 2 k 2 ( d − k ) 2 − d 2 ( d − 1 ) k 2 ( d − k ) 2 = − d 2 ( d − 2 ) 2 k 2 ( d − k ) 2 . \Phi''(\mu_H)=g''(\mu_H)-\frac{1}{\sigma_H^2}=\frac{d^3}{2k^2(d-k)^2}-\frac{d^2(d-1)}{k^2(d-k)^2}=-\frac{d^2(d-2)}{2k^2(d-k)^2}. Φ ′′ ( μ H ) = g ′′ ( μ H ) − σ H 2 1 = 2 k 2 ( d − k ) 2 d 3 − k 2 ( d − k ) 2 d 2 ( d − 1 ) = − 2 k 2 ( d − k ) 2 d 2 ( d − 2 ) .
(c) The function g g g is continuous on [ 0 , k ] [0,k] [ 0 , k ] by Lemma 4.3 (c). For ρ \rho ρ , since K K K is increasing, ρ ( 0 ) = − inf θ K ( θ ) = − lim θ → − ∞ K ( θ ) = − log P ( H = 0 ) = log ( d − k k ) \rho(0)=-\inf_\theta K(\theta)=-\lim_{\theta\to-\infty}K(\theta)=-\log\mathbb{P}(H=0)=\log\binom{d-k}{k} ρ ( 0 ) = − inf θ K ( θ ) = − lim θ → − ∞ K ( θ ) = − log P ( H = 0 ) = log ( k d − k ) , which is finite because k ≤ d − k k\leq d-k k ≤ d − k . Similarly, ρ ( k ) = − log P ( H = k ) = log ( d k ) \rho(k)=-\log\mathbb{P}(H=k)=\log\binom{d}{k} ρ ( k ) = − log P ( H = k ) = log ( k d ) . The function ρ \rho ρ is a finite convex function on [ 0 , k ] [0,k] [ 0 , k ] because it is a supremum of affine functions. It is therefore continuous on ( 0 , k ) (0,k) ( 0 , k ) and lower semicontinuous on [ 0 , k ] [0,k] [ 0 , k ] . Convexity also gives ρ ( s ) ≤ k − s k ρ ( 0 ) + s k ρ ( k ) \rho(s)\leq\frac{k-s}{k}\rho(0)+\frac{s}{k}\rho(k) ρ ( s ) ≤ k k − s ρ ( 0 ) + k s ρ ( k ) , and hence lim sup s ↓ 0 ρ ( s ) ≤ ρ ( 0 ) \limsup_{s\downarrow0}\rho(s)\leq\rho(0) lim sup s ↓ 0 ρ ( s ) ≤ ρ ( 0 ) and lim sup s ↑ k ρ ( s ) ≤ ρ ( k ) \limsup_{s\uparrow k}\rho(s)\leq\rho(k) lim sup s ↑ k ρ ( s ) ≤ ρ ( k ) . Thus ρ \rho ρ , and hence Φ \Phi Φ , is continuous on [ 0 , k ] [0,k] [ 0 , k ] .
By part (b), Φ \Phi Φ is strictly concave on ( 0 , k ) (0,k) ( 0 , k ) , with Φ ( μ H ) = Φ ′ ( μ H ) = 0 \Phi(\mu_H)=\Phi'(\mu_H)=0 Φ ( μ H ) = Φ ′ ( μ H ) = 0 . Thus Φ \Phi Φ is strictly increasing on ( 0 , μ H ] (0,\mu_H] ( 0 , μ H ] and strictly decreasing on [ μ H , k ) [\mu_H,k) [ μ H , k ) . By continuity, Φ ( s ) < 0 \Phi(s)<0 Φ ( s ) < 0 for all s ∈ [ 0 , k ] ∖ { μ H } s\in[0,k]\setminus\{\mu_H\} s ∈ [ 0 , k ] ∖ { μ H } . Taylor’s theorem and Φ ′ ′ ( μ H ) < 0 \Phi''(\mu_H)<0 Φ ′′ ( μ H ) < 0 give κ > 0 \kappa>0 κ > 0 such that Φ ( s ) ≤ 1 4 Φ ′ ′ ( μ H ) ( s − μ H ) 2 \Phi(s)\leq\frac{1}{4}\Phi''(\mu_H)(s-\mu_H)^2 Φ ( s ) ≤ 4 1 Φ ′′ ( μ H ) ( s − μ H ) 2 for ∣ s − μ H ∣ ≤ κ |s-\mu_H|\leq\kappa ∣ s − μ H ∣ ≤ κ . By compactness, η : = − max { Φ ( s ) : s ∈ [ 0 , k ] , ∣ s − μ H ∣ ≥ κ } > 0 \eta:=-\max\{\Phi(s):s\in[0,k],\ |s-\mu_H|\geq\kappa\}>0 η := − max { Φ ( s ) : s ∈ [ 0 , k ] , ∣ s − μ H ∣ ≥ κ } > 0 . The claim follows with c = min { ∣ Φ ′ ′ ( μ H ) ∣ / 4 , η / k 2 } c=\min\{|\Phi''(\mu_H)|/4,\eta/k^2\} c = min { ∣ Φ ′′ ( μ H ) ∣/4 , η / k 2 } .
(d) The density of P \mathbb{P} P with respect to P θ \mathbb{P}_\theta P θ on ( H 1 , … , H n ) (H_1,\ldots,H_n) ( H 1 , … , H n ) is e − θ S n + n K ( θ ) e^{-\theta S_n+nK(\theta)} e − θ S n + n K ( θ ) . Hence P ( S n = σ ) = E θ [ e − θ S n + n K ( θ ) 1 { S n = σ } ] = e − θ σ + n K ( θ ) P θ ( S n = σ ) \mathbb{P}(S_n=\sigma)=\mathbb{E}_\theta[e^{-\theta S_n+nK(\theta)}\mathbf{1}_{\{S_n=\sigma\}}]=e^{-\theta\sigma+nK(\theta)}\mathbb{P}_\theta(S_n=\sigma) P ( S n = σ ) = E θ [ e − θ S n + n K ( θ ) 1 { S n = σ } ] = e − θ σ + n K ( θ ) P θ ( S n = σ ) . Bounding P θ ( S n = σ ) ≤ 1 \mathbb{P}_\theta(S_n=\sigma)\leq1 P θ ( S n = σ ) ≤ 1 and taking the supremum over θ \theta θ gives P ( S n = σ ) ≤ e − n ρ ( s ) \mathbb{P}(S_n=\sigma)\leq e^{-n\rho(s)} P ( S n = σ ) ≤ e − n ρ ( s ) . Combining this bound with Lemma 4.3 (a) proves the last assertion.
A uniform local limit theorem for the tilted sums
Lemma 4.6. Fix θ 0 > 0 \theta_0>0 θ 0 > 0 . There is a sequence ε n → 0 \varepsilon_n\to0 ε n → 0 , depending only on d , k , θ 0 d,k,\theta_0 d , k , θ 0 , such that for all θ ∈ [ − θ 0 , θ 0 ] \theta\in[-\theta_0,\theta_0] θ ∈ [ − θ 0 , θ 0 ] and all n n n for which σ : = n K ′ ( θ ) \sigma:=nK'(\theta) σ := n K ′ ( θ ) is an integer,
∣ 2 π n K ′ ′ ( θ ) P θ ( S n = σ ) − 1 ∣ ≤ ε n . \left|\sqrt{2\pi nK''(\theta)}\,\mathbb{P}_\theta(S_n=\sigma)-1\right|\leq\varepsilon_n. 2 π n K ′′ ( θ ) P θ ( S n = σ ) − 1 ≤ ε n .
Proof. Fix θ ∈ [ − θ 0 , θ 0 ] \theta\in[-\theta_0,\theta_0] θ ∈ [ − θ 0 , θ 0 ] and write μ = K ′ ( θ ) \mu=K'(\theta) μ = K ′ ( θ ) and v = K ′ ′ ( θ ) v=K''(\theta) v = K ′′ ( θ ) . Then σ = n μ \sigma=n\mu σ = n μ and v ∈ [ v 0 , k 2 ] v\in[v_0,k^2] v ∈ [ v 0 , k 2 ] , where v 0 : = min ∣ θ ∣ ≤ θ 0 K ′ ′ ( θ ) > 0 v_0:=\min_{|\theta|\leq\theta_0}K''(\theta)>0 v 0 := min ∣ θ ∣ ≤ θ 0 K ′′ ( θ ) > 0 by (18) and continuity. Let ϕ θ ( t ) = E θ e i t H 1 \phi_\theta(t)=\mathbb{E}_\theta e^{itH_1} ϕ θ ( t ) = E θ e i t H 1 and ψ θ ( t ) = e − i t μ ϕ θ ( t ) = E θ e i t ( H 1 − μ ) \psi_\theta(t)=e^{-it\mu}\phi_\theta(t)=\mathbb{E}_\theta e^{it(H_1-\mu)} ψ θ ( t ) = e − i t μ ϕ θ ( t ) = E θ e i t ( H 1 − μ ) . By (17), ϕ θ ( t ) = ∏ i ( 1 − q i + q i e i t ) \phi_\theta(t)=\prod_i(1-q_i+q_i e^{it}) ϕ θ ( t ) = ∏ i ( 1 − q i + q i e i t ) , where q i = q i ( θ ) q_i=q_i(\theta) q i = q i ( θ ) . Since ∣ 1 − q + q e i t ∣ 2 = 1 − 2 q ( 1 − q ) ( 1 − cos t ) ≤ e − 2 q ( 1 − q ) ( 1 − cos t ) |1-q+qe^{it}|^2=1-2q(1-q)(1-\cos t)\leq e^{-2q(1-q)(1-\cos t)} ∣1 − q + q e i t ∣ 2 = 1 − 2 q ( 1 − q ) ( 1 − cos t ) ≤ e − 2 q ( 1 − q ) ( 1 − c o s t ) ,
∣ ψ θ ( t ) ∣ = ∣ ϕ θ ( t ) ∣ ≤ e − v ( 1 − cos t ) ≤ e − 2 v t 2 / π 2 ( ∣ t ∣ ≤ π ) . (21) |\psi_\theta(t)|=|\phi_\theta(t)|\leq e^{-v(1-\cos t)}\leq e^{-2vt^2/\pi^2}\qquad(|t|\leq\pi). \tag*{(21)} ∣ ψ θ ( t ) ∣ = ∣ ϕ θ ( t ) ∣ ≤ e − v ( 1 − c o s t ) ≤ e − 2 v t 2 / π 2 ( ∣ t ∣ ≤ π ) . (21)
where the last inequality uses 1 − cos t ≥ 2 t 2 / π 2 1-\cos t\geq2t^2/\pi^2 1 − cos t ≥ 2 t 2 / π 2 on [ − π , π ] [-\pi,\pi] [ − π , π ] .
Since ∣ H 1 − μ ∣ ≤ k |H_1-\mu|\leq k ∣ H 1 − μ ∣ ≤ k , the inequality ∣ e i x − 1 − i x + x 2 / 2 ∣ ≤ ∣ x ∣ 3 / 6 |e^{ix}-1-ix+x^2/2|\leq|x|^3/6 ∣ e i x − 1 − i x + x 2 /2∣ ≤ ∣ x ∣ 3 /6 gives ψ θ ( t ) = 1 + z ( t ) \psi_\theta(t)=1+z(t) ψ θ ( t ) = 1 + z ( t ) with ∣ z ( t ) + v t 2 / 2 ∣ ≤ k 3 ∣ t ∣ 3 / 6 |z(t)+vt^2/2|\leq k^3|t|^3/6 ∣ z ( t ) + v t 2 /2∣ ≤ k 3 ∣ t ∣ 3 /6 . Choose t 0 ∈ ( 0 , π ] t_0\in(0,\pi] t 0 ∈ ( 0 , π ] , depending only on k k k , such that k 2 t 0 2 / 2 + k 3 t 0 3 / 6 ≤ 1 / 2 k^2t_0^2/2+k^3t_0^3/6\leq1/2 k 2 t 0 2 /2 + k 3 t 0 3 /6 ≤ 1/2 . Then ∣ z ( t ) ∣ ≤ 1 / 2 |z(t)|\leq1/2 ∣ z ( t ) ∣ ≤ 1/2 for ∣ t ∣ ≤ t 0 |t|\leq t_0 ∣ t ∣ ≤ t 0 . Using ∣ log ( 1 + z ) − z ∣ ≤ ∣ z ∣ 2 |\log(1+z)-z|\leq|z|^2 ∣ log ( 1 + z ) − z ∣ ≤ ∣ z ∣ 2 for ∣ z ∣ ≤ 1 / 2 |z|\leq1/2 ∣ z ∣ ≤ 1/2 , we obtain a constant C = C ( k ) C=C(k) C = C ( k ) such that
∣ log ψ θ ( t ) + v t 2 2 ∣ ≤ C ∣ t ∣ 3 ( ∣ t ∣ ≤ t 0 ) , (22) \left|\log\psi_\theta(t)+\frac{vt^2}{2}\right|\leq C|t|^3\qquad(|t|\leq t_0), \tag*{(22)} log ψ θ ( t ) + 2 v t 2 ≤ C ∣ t ∣ 3 ( ∣ t ∣ ≤ t 0 ) , (22)
where log \log log is the principal branch.
Fourier inversion for the integer-valued variable S n S_n S n , followed by the substitution t = τ / n v t=\tau/\sqrt{nv} t = τ / n v , gives
2 π n v P θ ( S n = n μ ) = 2 π n v 1 2 π ∫ − π π e − i t n μ ϕ θ ( t ) n d t = 1 2 π ∫ ∣ τ ∣ ≤ π n v ψ θ ( τ n v ) n d τ . \sqrt{2\pi nv}\,\mathbb{P}_\theta(S_n=n\mu)=\sqrt{2\pi nv}\frac{1}{2\pi}\int_{-\pi}^{\pi}e^{-itn\mu}\phi_\theta(t)^n\,dt=\frac{1}{\sqrt{2\pi}}\int_{|\tau|\leq\pi\sqrt{nv}}\psi_\theta\left(\frac{\tau}{\sqrt{nv}}\right)^n\,d\tau. 2 π n v P θ ( S n = n μ ) = 2 π n v 2 π 1 ∫ − π π e − i t n μ ϕ θ ( t ) n d t = 2 π 1 ∫ ∣ τ ∣ ≤ π n v ψ θ ( n v τ ) n d τ .
Split the integral at ∣ τ ∣ = n 1 / 8 |\tau|=n^{1/8} ∣ τ ∣ = n 1/8 . For ∣ τ ∣ ≤ n 1 / 8 |\tau|\leq n^{1/8} ∣ τ ∣ ≤ n 1/8 and n n n large enough that n 1 / 8 / n v 0 ≤ t 0 n^{1/8}/\sqrt{nv_0}\leq t_0 n 1/8 / n v 0 ≤ t 0 , (22) gives
∣ n log ψ θ ( τ n v ) + τ 2 2 ∣ ≤ C n ∣ τ ∣ 3 ( n v ) 3 / 2 ≤ C v − 3 / 2 n − 1 / 8 = : ε n ′ , \left|n\log\psi_\theta\left(\frac{\tau}{\sqrt{nv}}\right)+\frac{\tau^2}{2}\right|\leq\frac{Cn|\tau|^3}{(nv)^{3/2}}\leq Cv^{-3/2}n^{-1/8}=:\varepsilon'_n, n log ψ θ ( n v τ ) + 2 τ 2 ≤ ( n v ) 3/2 C n ∣ τ ∣ 3 ≤ C v − 3/2 n − 1/8 =: ε n ′ ,
so
∣ ψ θ ( τ n v ) n − e − τ 2 / 2 ∣ ≤ e − τ 2 / 2 ( e ε n ′ − 1 ) . \left|\psi_\theta\left(\frac{\tau}{\sqrt{nv}}\right)^n-e^{-\tau^2/2}\right|\leq e^{-\tau^2/2}\left(e^{\varepsilon'_n}-1\right). ψ θ ( n v τ ) n − e − τ 2 /2 ≤ e − τ 2 /2 ( e ε n ′ − 1 ) .
Hence the integral over ∣ τ ∣ ≤ n 1 / 8 |\tau|\leq n^{1/8} ∣ τ ∣ ≤ n 1/8 equals ∫ ∣ τ ∣ ≤ n 1 / 8 e − τ 2 / 2 d τ + O ( ε n ′ ) = 2 π + O ( ε n ′ ) + O ( e − n 1 / 4 / 2 ) \int_{|\tau|\leq n^{1/8}}e^{-\tau^2/2}\,d\tau+O(\varepsilon'_n)=\sqrt{2\pi}+O(\varepsilon'_n)+O(e^{-n^{1/4}/2}) ∫ ∣ τ ∣ ≤ n 1/8 e − τ 2 /2 d τ + O ( ε n ′ ) = 2 π + O ( ε n ′ ) + O ( e − n 1/4 /2 ) . For n 1 / 8 < ∣ τ ∣ ≤ π n v n^{1/8}<|\tau|\leq\pi\sqrt{nv} n 1/8 < ∣ τ ∣ ≤ π n v , (21) gives ∣ ψ θ ( τ / n v ) ∣ n ≤ e − 2 τ 2 / π 2 |\psi_\theta(\tau/\sqrt{nv})|^n\leq e^{-2\tau^2/\pi^2} ∣ ψ θ ( τ / n v ) ∣ n ≤ e − 2 τ 2 / π 2 , so this part of the integral is O ( e − 2 n 1 / 4 / π 2 ) O(e^{-2n^{1/4}/\pi^2}) O ( e − 2 n 1/4 / π 2 ) . All constants depend only on d , k , θ 0 d,k,\theta_0 d , k , θ 0 . This proves the lemma.
Proof of Lemma 4.1
Proof of Lemma 4.1. Recall that 1 ≤ k ≤ d / 2 1 \le k \le d/2 1 ≤ k ≤ d /2 . Let a : = 1 σ H 2 − g ′ ′ ( μ H ) = − Φ ′ ′ ( μ H ) = d 2 ( d − 2 ) 2 k 2 ( d − k ) 2 > 0 a := \frac{1}{\sigma_H^2} - g''(\mu_H) = -\Phi''(\mu_H) = \frac{d^2(d-2)}{2k^2(d-k)^2} > 0 a := σ H 2 1 − g ′′ ( μ H ) = − Φ ′′ ( μ H ) = 2 k 2 ( d − k ) 2 d 2 ( d − 2 ) > 0 by Lemma 4.5 (b). Split the sum in (15) into Σ o u t \Sigma_{\mathrm{out}} Σ out , over even σ \sigma σ with ∣ σ − n μ H ∣ > n 3 / 5 |\sigma-n\mu_H| > n^{3/5} ∣ σ − n μ H ∣ > n 3/5 , and Σ i n \Sigma_{\mathrm{in}} Σ in , over even σ \sigma σ with ∣ σ − n μ H ∣ ≤ n 3 / 5 |\sigma-n\mu_H| \le n^{3/5} ∣ σ − n μ H ∣ ≤ n 3/5 .
The tail. By Lemma 4.5 (c),(d), every term of Σ o u t \Sigma_{\mathrm{out}} Σ out is at most 32 e n Φ ( σ / n ) ≤ 32 e − c n ( σ / n − μ H ) 2 ≤ 32 e − c n 1 / 5 32e^{n\Phi(\sigma/n)} \le32e^{-cn(\sigma/n-\mu_H)^2} \le32e^{-cn^{1/5}} 32 e n Φ ( σ / n ) ≤ 32 e − c n ( σ / n − μ H ) 2 ≤ 32 e − c n 1/5 . There are at most k n + 1 kn+1 k n + 1 terms, so Σ o u t = O ( n e − c n 1 / 5 ) → 0 \Sigma_{\mathrm{out}} = O(ne^{-cn^{1/5}}) \to0 Σ out = O ( n e − c n 1/5 ) → 0 .
The central window. Let σ \sigma σ be even with ∣ σ − n μ H ∣ ≤ n 3 / 5 |\sigma-n\mu_H| \le n^{3/5} ∣ σ − n μ H ∣ ≤ n 3/5 , and put s = σ / n s=\sigma/n s = σ / n and x = ( σ − n μ H ) / n x=(\sigma-n\mu_H)/\sqrt{n} x = ( σ − n μ H ) / n . Then ∣ s − μ H ∣ ≤ n − 2 / 5 |s-\mu_H| \le n^{-2/5} ∣ s − μ H ∣ ≤ n − 2/5 and ∣ x ∣ ≤ n 1 / 10 |x| \le n^{1/10} ∣ x ∣ ≤ n 1/10 . For large n n n , s s s lies in a fixed compact subset of ( 0 , k ) (0,k) ( 0 , k ) , and θ ( s ) = O ( n − 2 / 5 ) \theta(s)=O(n^{-2/5}) θ ( s ) = O ( n − 2/5 ) lies in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . Apply the tilting identity (20) with θ = θ ( s ) \theta=\theta(s) θ = θ ( s ) , for which n K ′ ( θ ( s ) ) = σ nK'(\theta(s))=\sigma n K ′ ( θ ( s )) = σ and θ ( s ) s − K ( θ ( s ) ) = ρ ( s ) \theta(s)s-K(\theta(s))=\rho(s) θ ( s ) s − K ( θ ( s )) = ρ ( s ) . Lemma 4.6, with θ 0 = 1 \theta_0=1 θ 0 = 1 , then gives
P ( S n = σ ) = e − n ρ ( s ) 1 + o ( 1 ) 2 π n K ′ ′ ( θ ( s ) ) = e − n ρ ( s ) 1 + o ( 1 ) 2 π n σ H 2 . \mathbb{P}(S_n=\sigma)=e^{-n\rho(s)}\frac{1+o(1)}{\sqrt{2\pi nK''(\theta(s))}}=e^{-n\rho(s)}\frac{1+o(1)}{\sqrt{2\pi n\sigma_H^2}}. P ( S n = σ ) = e − n ρ ( s ) 2 π n K ′′ ( θ ( s )) 1 + o ( 1 ) = e − n ρ ( s ) 2 π n σ H 2 1 + o ( 1 ) .
uniformly in the window, because K ′ ′ ( θ ( s ) ) = K ′ ′ ( 0 ) + O ( n − 2 / 5 ) = σ H 2 + O ( n − 2 / 5 ) K''(\theta(s))=K''(0)+O(n^{-2/5})=\sigma_H^2+O(n^{-2/5}) K ′′ ( θ ( s )) = K ′′ ( 0 ) + O ( n − 2/5 ) = σ H 2 + O ( n − 2/5 ) . Lemma 4.3 (b) gives R M ( σ ) = 2 e n g ( s ) ( 1 + O ( n − 1 ) ) R_M(\sigma)=\sqrt{2}e^{ng(s)}(1+O(n^{-1})) R M ( σ ) = 2 e n g ( s ) ( 1 + O ( n − 1 )) . Therefore, uniformly in the window,
P ( S n = σ ) R M ( σ ) = 2 2 π n σ H 2 e n Φ ( s ) ( 1 + o ( 1 ) ) = 2 4 π n σ H 2 e n Φ ( s ) ( 1 + o ( 1 ) ) . \mathbb{P}(S_n=\sigma)R_M(\sigma)=\frac{\sqrt{2}}{\sqrt{2\pi n\sigma_H^2}}e^{n\Phi(s)}(1+o(1))=\frac{2}{\sqrt{4\pi n\sigma_H^2}}e^{n\Phi(s)}(1+o(1)). P ( S n = σ ) R M ( σ ) = 2 π n σ H 2 2 e n Φ ( s ) ( 1 + o ( 1 )) = 4 π n σ H 2 2 e n Φ ( s ) ( 1 + o ( 1 )) .
The function Φ \Phi Φ is smooth near μ H \mu_H μ H , with Φ ( μ H ) = Φ ′ ( μ H ) = 0 \Phi(\mu_H)=\Phi'(\mu_H)=0 Φ ( μ H ) = Φ ′ ( μ H ) = 0 and Φ ′ ′ ( μ H ) = − a \Phi''(\mu_H)=-a Φ ′′ ( μ H ) = − a . Taylor’s theorem gives
n Φ ( s ) = − a 2 n ( s − μ H ) 2 + O ( n ∣ s − μ H ∣ 3 ) = − a 2 x 2 + O ( n − 1 / 5 ) . n\Phi(s)=-\frac{a}{2}n(s-\mu_H)^2+O(n|s-\mu_H|^3)=-\frac{a}{2}x^2+O(n^{-1/5}). n Φ ( s ) = − 2 a n ( s − μ H ) 2 + O ( n ∣ s − μ H ∣ 3 ) = − 2 a x 2 + O ( n − 1/5 ) .
Consequently,
Σ i n = ( 1 + o ( 1 ) ) 1 4 π σ H 2 ∑ ∣ σ − n μ H ∣ ≤ n 3 / 5 σ e v e n 2 n e − a x 2 / 2 . \Sigma_{\mathrm{in}}=(1+o(1))\frac{1}{\sqrt{4\pi\sigma_H^2}}\sum_{\substack{|\sigma-n\mu_H|\le n^{3/5}\\ \sigma\ \mathrm{even}}}\frac{2}{\sqrt{n}}e^{-ax^2/2}. Σ in = ( 1 + o ( 1 )) 4 π σ H 2 1 ∣ σ − n μ H ∣ ≤ n 3/5 σ even ∑ n 2 e − a x 2 /2 .
Consecutive even values of σ \sigma σ correspond to values of x x x spaced by 2 / n 2/\sqrt{n} 2/ n , and the window corresponds to ∣ x ∣ ≤ n 1 / 10 |x|\le n^{1/10} ∣ x ∣ ≤ n 1/10 . For fixed A > 0 A>0 A > 0 , the terms with ∣ x ∣ ≤ A |x|\le A ∣ x ∣ ≤ A form a Riemann sum that converges to ∫ − A A e − a x 2 / 2 d x \int_{-A}^{A}e^{-ax^2/2}\,dx ∫ − A A e − a x 2 /2 d x . Since e − a x 2 / 2 e^{-ax^2/2} e − a x 2 /2 is monotone on each half-line, the terms with ∣ x ∣ > A |x|>A ∣ x ∣ > A sum to at most ∫ ∣ x ∣ > A − 2 / n e − a x 2 / 2 d x \int_{|x|>A-2/\sqrt{n}}e^{-ax^2/2}\,dx ∫ ∣ x ∣ > A − 2/ n e − a x 2 /2 d x . Letting n → ∞ n\to\infty n → ∞ and then A → ∞ A\to\infty A → ∞ , we see that Σ i n \Sigma_{\mathrm{in}} Σ in converges to
1 4 π σ H 2 ∫ − ∞ ∞ e − a x 2 / 2 d x = 1 4 π σ H 2 2 π a = 1 2 a σ H 2 . \frac{1}{\sqrt{4\pi\sigma_H^2}}\int_{-\infty}^{\infty}e^{-ax^2/2}\,dx=\frac{1}{\sqrt{4\pi\sigma_H^2}}\sqrt{\frac{2\pi}{a}}=\frac{1}{\sqrt{2a\sigma_H^2}}. 4 π σ H 2 1 ∫ − ∞ ∞ e − a x 2 /2 d x = 4 π σ H 2 1 a 2 π = 2 a σ H 2 1 .
Finally, by (14) and Lemma 4.3 (c), 2 σ H 2 g ′ ′ ( μ H ) = 2 k 2 ( d − k ) 2 d 2 ( d − 1 ) ⋅ d 3 2 k 2 ( d − k ) 2 = d d − 1 2\sigma_H^2g''(\mu_H)=\frac{2k^2(d-k)^2}{d^2(d-1)}\cdot\frac{d^3}{2k^2(d-k)^2}=\frac{d}{d-1} 2 σ H 2 g ′′ ( μ H ) = d 2 ( d − 1 ) 2 k 2 ( d − k ) 2 ⋅ 2 k 2 ( d − k ) 2 d 3 = d − 1 d , so
2 a σ H 2 = 2 − 2 σ H 2 g ′ ′ ( μ H ) = 2 − d d − 1 = d − 2 d − 1 , lim n → ∞ E [ Z k ( P ) 2 ] ( E Z k ( P ) ) 2 = d − 1 d − 2 . 2a\sigma_H^2=2-2\sigma_H^2g''(\mu_H)=2-\frac{d}{d-1}=\frac{d-2}{d-1},\qquad\lim_{n\to\infty}\frac{\mathbb{E}[Z_k(P)^2]}{(\mathbb{E}Z_k(P))^2}=\sqrt{\frac{d-1}{d-2}}. 2 a σ H 2 = 2 − 2 σ H 2 g ′′ ( μ H ) = 2 − d − 1 d = d − 1 d − 2 , n → ∞ lim ( E Z k ( P ) ) 2 E [ Z k ( P ) 2 ] = d − 2 d − 1 .
The identity with exp ( ∑ i ≥ 1 λ i δ i 2 ) \exp(\sum_{i\ge1}\lambda_i\delta_i^2) exp ( ∑ i ≥ 1 λ i δ i 2 ) was noted after (1) . □
Remark 4.7. Within the window, P ( S n = σ ) \mathbb{P}(S_n=\sigma) P ( S n = σ ) can be as small as e − c n 1 / 5 e^{-cn^{1/5}} e − c n 1/5 , far below the n − 1 / 2 n^{-1/2} n − 1/2 scale of the ordinary local central limit theorem. Its additive error is therefore too large. The tilting identity (20) reduces the problem to a local limit theorem at the mean of the tilted distribution. Lemma 4.6 then gives a relative error o ( 1 ) o(1) o ( 1 ) uniformly in the tilt. The strict inequality Φ ′ ′ < 0 \Phi''<0 Φ ′′ < 0 in Lemma 4.5 (b) relies on the Poisson-binomial representation. When d = 2 k d=2k d = 2 k , so that g ′ ′ ( s ) = 1 s + 1 k − s g''(s)=\frac{1}{s}+\frac{1}{k-s} g ′′ ( s ) = s 1 + k − s 1 exactly, strictness follows from the distinct Bernoulli parameters.
Proof of Theorem 1.1
Throughout this section, d ≥ 3 d \ge3 d ≥ 3 and 1 ≤ k ≤ d − 1 1 \le k \le d-1 1 ≤ k ≤ d − 1 are fixed, and n → ∞ n \to\infty n → ∞ along integers for which d n dn d n and k n kn k n are even. Let
Y k , n : = Z k ( P ) E Z k ( P ) , P ∼ P n , d , Y_{k,n} := \frac{Z_k(P)}{\mathbb{E}Z_k(P)}, \qquad P \sim\mathcal{P}_{n,d}, Y k , n := E Z k ( P ) Z k ( P ) , P ∼ P n , d ,
where X i = X i ( P ) X_i = X_i(P) X i = X i ( P ) is defined as in § 2 . Write W p a i r : = ∏ i ≥ 1 ( 1 + δ i ) ξ i e − λ i δ i W^{\mathrm{pair}} := \prod_{i\ge1}(1+\delta_i)^{\xi_i}e^{-\lambda_i\delta_i} W pair := ∏ i ≥ 1 ( 1 + δ i ) ξ i e − λ i δ i , W : = ∏ i ≥ 3 ( 1 + δ i ) ξ i e − λ i δ i W := \prod_{i\ge3}(1+\delta_i)^{\xi_i}e^{-\lambda_i\delta_i} W := ∏ i ≥ 3 ( 1 + δ i ) ξ i e − λ i δ i as in (4), and W ( m ) ( ξ ) : = ∏ i ≤ m ( 1 + δ i ) ξ i e − λ i δ i W^{(m)}(\boldsymbol{\xi}) := \prod_{i\le m}(1+\delta_i)^{\xi_i}e^{-\lambda_i\delta_i} W ( m ) ( ξ ) := ∏ i ≤ m ( 1 + δ i ) ξ i e − λ i δ i . By Lemma 2.2 , these products converge almost surely and in L 2 L^2 L 2 , are almost surely positive, and have mean 1. Moreover, W W W is independent of ( ξ 1 , ξ 2 ) (\xi_1,\xi_2) ( ξ 1 , ξ 2 ) .
Step 1: small subgraph conditioning in the pairing model. Hypothesis (i) of Theorem 2.1 is (7), and (ii) is Lemma 3.1 . Hypothesis (iii) holds because ∑ i λ i δ i 2 = 1 2 log d − 1 d − 2 \sum_i \lambda_i\delta_i^2 = \frac{1}{2}\log\frac{d-1}{d-2} ∑ i λ i δ i 2 = 2 1 log d − 2 d − 1 , and (iv) is Lemma 4.1 , which applies to all 1 ≤ k ≤ d − 1 1 \le k \le d-1 1 ≤ k ≤ d − 1 by (13). Also, δ i > − 1 \delta_i > -1 δ i > − 1 for all i i i . Hence, for every fixed m m m ,
( Y k , n , X 1 , … , X m ) ⟹ ( W p a i r , ξ 1 , … , ξ m ) in P n , d . (23) (Y_{k,n},X_1,\ldots,X_m)\ \Longrightarrow\ (W^{\mathrm{pair}},\xi_1,\ldots,\xi_m)\quad\text{in }\mathcal{P}_{n,d}. \tag*{(23)} ( Y k , n , X 1 , … , X m ) ⟹ ( W pair , ξ 1 , … , ξ m ) in P n , d . (23)
Step 2: uniform integrability. By (23), Y k , n 2 ⇒ ( W p a i r ) 2 Y_{k,n}^2 \Rightarrow(W^{\mathrm{pair}})^2 Y k , n 2 ⇒ ( W pair ) 2 . By (iv) and Lemma 2.2 , E Y k , n 2 → exp ( ∑ i ≥ 1 λ i δ i 2 ) = E ( W p a i r ) 2 \mathbb{E}Y_{k,n}^2 \to\exp(\sum_{i\ge1}\lambda_i\delta_i^2)=\mathbb{E}(W^{\mathrm{pair}})^2 E Y k , n 2 → exp ( ∑ i ≥ 1 λ i δ i 2 ) = E ( W pair ) 2 . For K > 0 K>0 K > 0 , the function y ↦ ( y − K ) + y\mapsto(y-K)_+ y ↦ ( y − K ) + is continuous, and y ≤ 2 ( y − K ) + y\le2(y-K)_+ y ≤ 2 ( y − K ) + for y > 2 K y>2K y > 2 K . Therefore,
lim sup n → ∞ E [ Y k , n 2 1 { Y k , n 2 > 2 K } ] ≤ 2 lim sup n → ∞ E ( Y k , n 2 − K ) + = 2 lim n → ∞ ( E Y k , n 2 − E ( Y k , n 2 ∧ K ) ) = 2 E ( ( W p a i r ) 2 − K ) + , \begin{aligned}
\limsup_{n\to\infty}\mathbb{E}\left[Y_{k,n}^2\mathbf{1}_{\{Y_{k,n}^2>2K\}}\right]
\le2\limsup_{n\to\infty}\mathbb{E}(Y_{k,n}^2-K)_+ \\
&=2\lim_{n\to\infty}\left(\mathbb{E}Y_{k,n}^2-\mathbb{E}(Y_{k,n}^2\wedge K)\right)
=2\mathbb{E}\left((W^{\mathrm{pair}})^2-K\right)_+,
\end{aligned} n → ∞ lim sup E [ Y k , n 2 1 { Y k , n 2 > 2 K } ] ≤ 2 n → ∞ lim sup E ( Y k , n 2 − K ) + = 2 n → ∞ lim ( E Y k , n 2 − E ( Y k , n 2 ∧ K ) ) = 2 E ( ( W pair ) 2 − K ) + ,
which tends to 0 as K → ∞ K\to\infty K → ∞ . Thus ( Y k , n 2 ) n (Y_{k,n}^2)_n ( Y k , n 2 ) n is uniformly integrable, and so is ( Y k , n ) n (Y_{k,n})_n ( Y k , n ) n .
Step 3: conditioning on simplicity. Recall that S = { X 1 = X 2 = 0 } S=\{X_1=X_2=0\} S = { X 1 = X 2 = 0 } , P ( S ) → e − λ 1 − λ 2 > 0 \mathbb{P}(S)\to e^{-\lambda_1-\lambda_2}>0 P ( S ) → e − λ 1 − λ 2 > 0 , G ( P ) ∼ G ( n , d ) G(P)\sim G(n,d) G ( P ) ∼ G ( n , d ) conditional on S S S , and Z k ( P ) = Z k ( G ( P ) ) Z_k(P)=Z_k(G(P)) Z k ( P ) = Z k ( G ( P )) on S S S . Let h ( x 1 , x 2 ) : = ( 1 − ∣ x 1 ∣ − ∣ x 2 ∣ ) + h(x_1,x_2):=(1-|x_1|-|x_2|)_+ h ( x 1 , x 2 ) := ( 1 − ∣ x 1 ∣ − ∣ x 2 ∣ ) + , a bounded continuous function. Since X 1 , X 2 X_1,X_2 X 1 , X 2 are integer valued, h ( X 1 , X 2 ) = 1 S h(X_1,X_2)=1_S h ( X 1 , X 2 ) = 1 S . For any bounded continuous f f f on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) and any bounded continuous φ \varphi φ on R m − 2 \mathbb{R}^{m-2} R m − 2 , the continuous mapping theorem and (23) give
E [ f ( Y k , n ) φ ( X 3 , … , X m ) 1 S ] = E [ f ( Y k , n ) φ ( X 3 , … , X m ) h ( X 1 , X 2 ) ] → E [ f ( W p a i r ) φ ( ξ 3 , … , ξ m ) 1 { ξ 1 = ξ 2 = 0 } ] . \mathbb{E}[f(Y_{k,n})\varphi(X_3,\ldots,X_m)1_S]
=\mathbb{E}[f(Y_{k,n})\varphi(X_3,\ldots,X_m)h(X_1,X_2)]
\to\mathbb{E}[f(W^{\mathrm{pair}})\varphi(\xi_3,\ldots,\xi_m)1_{\{\xi_1=\xi_2=0\}}]. E [ f ( Y k , n ) φ ( X 3 , … , X m ) 1 S ] = E [ f ( Y k , n ) φ ( X 3 , … , X m ) h ( X 1 , X 2 )] → E [ f ( W pair ) φ ( ξ 3 , … , ξ m ) 1 { ξ 1 = ξ 2 = 0 } ] .
On the event { ξ 1 = ξ 2 = 0 } \{\xi_1=\xi_2=0\} { ξ 1 = ξ 2 = 0 } , the factors of W p a i r W^{\mathrm{pair}} W pair for i = 1 , 2 i=1,2 i = 1 , 2 are deterministic. Since λ 1 δ 1 = − 1 2 \lambda_1\delta_1=-\frac12 λ 1 δ 1 = − 2 1 and λ 2 δ 2 = 1 4 \lambda_2\delta_2=\frac14 λ 2 δ 2 = 4 1 ,
W p a i r = e − λ 1 δ 1 − λ 2 δ 2 W = e 1 / 4 W on { ξ 1 = ξ 2 = 0 } , W^{\mathrm{pair}}=e^{-\lambda_1\delta_1-\lambda_2\delta_2}W=e^{1/4}W\quad\text{on }\{\xi_1=\xi_2=0\}, W pair = e − λ 1 δ 1 − λ 2 δ 2 W = e 1/4 W on { ξ 1 = ξ 2 = 0 } ,
where W W W and ( ξ 3 , … , ξ m ) (\xi_3,\ldots,\xi_m) ( ξ 3 , … , ξ m ) are independent of ( ξ 1 , ξ 2 ) (\xi_1,\xi_2) ( ξ 1 , ξ 2 ) . Divide by P ( S ) → P ( ξ 1 = ξ 2 = 0 ) = e − λ 1 − λ 2 \mathbb{P}(S)\to\mathbb{P}(\xi_1=\xi_2=0)=e^{-\lambda_1-\lambda_2} P ( S ) → P ( ξ 1 = ξ 2 = 0 ) = e − λ 1 − λ 2 to obtain
L ( Y k , n , X 3 , … , X m ∣ S ) ⟹ L ( e 1 / 4 W , ξ 3 , … , ξ m ) . (24) \mathcal{L}(Y_{k,n},X_3,\ldots,X_m\mid S)\Longrightarrow\mathcal{L}(e^{1/4}W,\xi_3,\ldots,\xi_m). \tag*{(24)} L ( Y k , n , X 3 , … , X m ∣ S ) ⟹ L ( e 1/4 W , ξ 3 , … , ξ m ) . (24)
The same argument applies to the unbounded functions f ( y ) = y f(y)=y f ( y ) = y and f ( y ) = y 2 f(y)=y^2 f ( y ) = y 2 , with φ ≡ 1 \varphi\equiv1 φ ≡ 1 , by Step 2. Indeed, the continuous mapping theorem gives Y k , n 1 S ⇒ W p a i r 1 { ξ 1 = ξ 2 = 0 } Y_{k,n}1_S\Rightarrow W^{\mathrm{pair}}1_{\{\xi_1=\xi_2=0\}} Y k , n 1 S ⇒ W pair 1 { ξ 1 = ξ 2 = 0 } and Y k , n 2 1 S ⇒ ( W p a i r ) 2 1 { ξ 1 = ξ 2 = 0 } Y_{k,n}^2 1_S\Rightarrow(W^{\mathrm{pair}})^2 1_{\{\xi_1=\xi_2=0\}} Y k , n 2 1 S ⇒ ( W pair ) 2 1 { ξ 1 = ξ 2 = 0 } . These sequences are dominated by the uniformly integrable sequences Y k , n Y_{k,n} Y k , n and Y k , n 2 Y_{k,n}^2 Y k , n 2 , respectively, so their expectations converge. Lemma 2.2 gives E W = 1 \mathbb{E}W=1 E W = 1 and E W 2 = exp ( ∑ i ≥ 3 λ i δ i 2 ) \mathbb{E}W^2=\exp(\sum_{i\ge3}\lambda_i\delta_i^2) E W 2 = exp ( ∑ i ≥ 3 λ i δ i 2 ) . Hence
c k , n : = E [ Y k , n ∣ S ] ⟶ e 1 / 4 , E [ Y k , n 2 ∣ S ] ⟶ e 1 / 2 exp ( ∑ i ≥ 3 λ i δ i 2 ) . (25) c_{k,n}:=\mathbb{E}[Y_{k,n}\mid S]\longrightarrow e^{1/4},\qquad
\mathbb{E}[Y_{k,n}^2\mid S]\longrightarrow e^{1/2}\exp\left(\sum_{i\ge3}\lambda_i\delta_i^2\right). \tag*{(25)} c k , n := E [ Y k , n ∣ S ] ⟶ e 1/4 , E [ Y k , n 2 ∣ S ] ⟶ e 1/2 exp ( i ≥ 3 ∑ λ i δ i 2 ) . (25)
Proof of (i). Since E G ( n , d ) [ Z k ( G ) ] = E [ Z k ( P ) ∣ S ] = c k , n E Z k ( P ) \mathbb{E}_{G(n,d)}[Z_k(G)]=\mathbb{E}[Z_k(P)\mid S]=c_{k,n}\mathbb{E}Z_k(P) E G ( n , d ) [ Z k ( G )] = E [ Z k ( P ) ∣ S ] = c k , n E Z k ( P ) , part (i) follows from (25) and (8).
Proof of (ii). By (25) ,
E G ( n , d ) [ Z k ( G ) 2 ] ( E G ( n , d ) [ Z k ( G ) ] ) 2 = E [ Y k , n 2 ∣ S ] c k , n 2 ⟶ exp ( ∑ i ≥ 3 λ i δ i 2 ) = exp ( − 1 2 ( d − 1 ) − 1 4 ( d − 1 ) 2 ) d − 1 d − 2 , \frac{\mathbb{E}_{G(n,d)}[Z_k(G)^2]}{(\mathbb{E}_{G(n,d)}[Z_k(G)])^2}=\frac{\mathbb{E}[Y_{k,n}^2\mid S]}{c_{k,n}^2}\longrightarrow\exp\left(\sum_{i\geq3}\lambda_i\delta_i^2\right)=\exp\left(-\frac{1}{2(d-1)}-\frac{1}{4(d-1)^2}\right)\sqrt{\frac{d-1}{d-2}}, ( E G ( n , d ) [ Z k ( G )] ) 2 E G ( n , d ) [ Z k ( G ) 2 ] = c k , n 2 E [ Y k , n 2 ∣ S ] ⟶ exp ( i ≥ 3 ∑ λ i δ i 2 ) = exp ( − 2 ( d − 1 ) 1 − 4 ( d − 1 ) 2 1 ) d − 2 d − 1 ,
where we used λ 1 δ 1 2 = 1 2 ( d − 1 ) \lambda_1\delta_1^2=\frac{1}{2(d-1)} λ 1 δ 1 2 = 2 ( d − 1 ) 1 , λ 2 δ 2 2 = 1 4 ( d − 1 ) 2 \lambda_2\delta_2^2=\frac{1}{4(d-1)^2} λ 2 δ 2 2 = 4 ( d − 1 ) 2 1 , and 1 2 ( d − 1 ) + 1 4 ( d − 1 ) 2 = 2 d − 1 4 ( d − 1 ) 2 \frac{1}{2(d-1)}+\frac{1}{4(d-1)^2}=\frac{2d-1}{4(d-1)^2} 2 ( d − 1 ) 1 + 4 ( d − 1 ) 2 1 = 4 ( d − 1 ) 2 2 d − 1 .
Proof of (iii). Conditional on S S S , Z k ( G ) / E G ( n , d ) [ Z k ( G ) ] = Y k , n / c k , n Z_k(G)/\mathbb{E}_{G(n,d)}[Z_k(G)]=Y_{k,n}/c_{k,n} Z k ( G ) / E G ( n , d ) [ Z k ( G )] = Y k , n / c k , n , where c k , n → e 1 / 4 c_{k,n}\to e^{1/4} c k , n → e 1/4 . Thus (24) and Slutsky’s theorem give the joint convergence ( Z k ( G ) / E G ( n , d ) [ Z k ( G ) ] , X 3 ( G ) , … , X m ( G ) ) ⇒ ( W , ξ 3 , … , ξ m ) (Z_k(G)/\mathbb{E}_{G(n,d)}[Z_k(G)],X_3(G),\ldots,X_m(G))\Rightarrow(W,\xi_3,\ldots,\xi_m) ( Z k ( G ) / E G ( n , d ) [ Z k ( G )] , X 3 ( G ) , … , X m ( G )) ⇒ ( W , ξ 3 , … , ξ m ) for G ∼ G ( n , d ) G\sim G(n,d) G ∼ G ( n , d ) . Lemma 2.2 gives the stated properties of W W W .
Step 4: a common approximation. Let W n ( m ) : = ∏ i ≤ m ( 1 + δ i ) X i e − λ i δ i W_n^{(m)}:=\prod_{i\leq m}(1+\delta_i)^{X_i}e^{-\lambda_i\delta_i} W n ( m ) := ∏ i ≤ m ( 1 + δ i ) X i e − λ i δ i . This is a function of the pairing P P P alone and does not depend on k k k . The map ( y , x 1 , … , x m ) ↦ y − ∏ i ≤ m ( 1 + δ i ) x i e − λ i δ i (y,x_1,\ldots,x_m)\mapsto y-\prod_{i\leq m}(1+\delta_i)^{x_i}e^{-\lambda_i\delta_i} ( y , x 1 , … , x m ) ↦ y − ∏ i ≤ m ( 1 + δ i ) x i e − λ i δ i is continuous. Therefore (23) and the continuous mapping theorem give Y k , n − W n ( m ) ⇒ W p a i r − W ( m ) ( ξ ) Y_{k,n}-W_n^{(m)}\Rightarrow W^{\mathrm{pair}}-W^{(m)}(\xi) Y k , n − W n ( m ) ⇒ W pair − W ( m ) ( ξ ) . By the portmanteau theorem, for every ε > 0 \varepsilon>0 ε > 0 ,
lim sup n → ∞ P ( ∣ Y k , n − W n ( m ) ∣ ≥ ε ) ≤ P ( ∣ W p a i r − W ( m ) ( ξ ) ∣ ≥ ε ) ⟶ m → ∞ 0 , \limsup_{n\to\infty}\mathbb{P}(|Y_{k,n}-W_n^{(m)}|\geq\varepsilon)\leq\mathbb{P}(|W^{\mathrm{pair}}-W^{(m)}(\xi)|\geq\varepsilon)\longrightarrow_{m\to\infty}0, n → ∞ lim sup P ( ∣ Y k , n − W n ( m ) ∣ ≥ ε ) ≤ P ( ∣ W pair − W ( m ) ( ξ ) ∣ ≥ ε ) ⟶ m → ∞ 0 ,
because W ( m ) ( ξ ) → W p a i r W^{(m)}(\xi)\to W^{\mathrm{pair}} W ( m ) ( ξ ) → W pair almost surely. Thus
lim m → ∞ lim sup n → ∞ P ( ∣ Y k , n − W n ( m ) ∣ ≥ ε ) = 0 (26) \lim_{m\to\infty}\limsup_{n\to\infty}\mathbb{P}(|Y_{k,n}-W_n^{(m)}|\geq\varepsilon)=0 \tag*{(26)} m → ∞ lim n → ∞ lim sup P ( ∣ Y k , n − W n ( m ) ∣ ≥ ε ) = 0 (26)
for every ε > 0 \varepsilon>0 ε > 0 and every 1 ≤ k ≤ d − 1 1\leq k\leq d-1 1 ≤ k ≤ d − 1 .
Step 5: proof of (iv). Let 1 ≤ k , ℓ ≤ d − 1 1\leq k,\ell\leq d-1 1 ≤ k , ℓ ≤ d − 1 , and let n n n be such that d n dn d n , k n kn k n , and ℓ n \ell n ℓ n are even. Then Y k , n Y_{k,n} Y k , n and Y ℓ , n Y_{\ell,n} Y ℓ , n are defined on the same space P n , d \mathcal{P}_{n,d} P n , d . For ε > 0 \varepsilon>0 ε > 0 and every m m m ,
P ( ∣ Y k , n − Y ℓ , n ∣ ≥ 2 ε ) ≤ P ( ∣ Y k , n − W n ( m ) ∣ ≥ ε ) + P ( ∣ Y ℓ , n − W n ( m ) ∣ ≥ ε ) ; \mathbb{P}(|Y_{k,n}-Y_{\ell,n}|\geq2\varepsilon)\leq\mathbb{P}(|Y_{k,n}-W_n^{(m)}|\geq\varepsilon)+\mathbb{P}(|Y_{\ell,n}-W_n^{(m)}|\geq\varepsilon); P ( ∣ Y k , n − Y ℓ , n ∣ ≥ 2 ε ) ≤ P ( ∣ Y k , n − W n ( m ) ∣ ≥ ε ) + P ( ∣ Y ℓ , n − W n ( m ) ∣ ≥ ε ) ;
taking lim sup n → ∞ \limsup_{n\to\infty} lim sup n → ∞ and then m → ∞ m\to\infty m → ∞ in (26) gives Y k , n − Y ℓ , n → 0 Y_{k,n}-Y_{\ell,n}\to0 Y k , n − Y ℓ , n → 0 in probability in P n , d \mathcal{P}_{n,d} P n , d . Since P ( A ∣ S ) ≤ P ( A ) / P ( S ) \mathbb{P}(A\mid S)\leq\mathbb{P}(A)/\mathbb{P}(S) P ( A ∣ S ) ≤ P ( A ) / P ( S ) and P ( S ) \mathbb{P}(S) P ( S ) is bounded away from zero, also Y k , n − Y ℓ , n → 0 Y_{k,n}-Y_{\ell,n}\to0 Y k , n − Y ℓ , n → 0 in probability conditional on S S S , and hence for G ∼ G ( n , d ) G\sim G(n,d) G ∼ G ( n , d ) . Now, for G ∼ G ( n , d ) G\sim G(n,d) G ∼ G ( n , d ) ,
Z k ( G ) E G ( n , d ) [ Z k ( G ) ] − Z ℓ ( G ) E G ( n , d ) [ Z ℓ ( G ) ] = Y k , n c k , n − Y ℓ , n c ℓ , n = Y k , n − Y ℓ , n c k , n + Y ℓ , n ( 1 c k , n − 1 c ℓ , n ) . \frac{Z_k(G)}{\mathbb{E}_{G(n,d)}[Z_k(G)]}-\frac{Z_\ell(G)}{\mathbb{E}_{G(n,d)}[Z_\ell(G)]}=\frac{Y_{k,n}}{c_{k,n}}-\frac{Y_{\ell,n}}{c_{\ell,n}}=\frac{Y_{k,n}-Y_{\ell,n}}{c_{k,n}}+Y_{\ell,n}\left(\frac{1}{c_{k,n}}-\frac{1}{c_{\ell,n}}\right). E G ( n , d ) [ Z k ( G )] Z k ( G ) − E G ( n , d ) [ Z ℓ ( G )] Z ℓ ( G ) = c k , n Y k , n − c ℓ , n Y ℓ , n = c k , n Y k , n − Y ℓ , n + Y ℓ , n ( c k , n 1 − c ℓ , n 1 ) .
The first term tends to 0 in probability because c k , n → e 1 / 4 c_{k,n}\to e^{1/4} c k , n → e 1/4 . The second does likewise because Y ℓ , n Y_{\ell,n} Y ℓ , n is tight, by part (iii), while 1 / c k , n − 1 / c ℓ , n → 0 1/c_{k,n}-1/c_{\ell,n}\to0 1/ c k , n − 1/ c ℓ , n → 0 by (25) . This proves the first assertion in (6) .
For the second assertion, let D n D_n D n be the difference just shown to be o p ( 1 ) o_p(1) o p ( 1 ) , and let V n : = Z ℓ ( G ) / E G ( n , d ) [ Z ℓ ( G ) ] V_n:=Z_\ell(G)/\mathbb{E}_{G(n,d)}[Z_\ell(G)] V n := Z ℓ ( G ) / E G ( n , d ) [ Z ℓ ( G )] . Then V n ⇒ W V_n\Rightarrow W V n ⇒ W , where W > 0 W>0 W > 0 almost surely by part (iii). Given η > 0 \eta>0 η > 0 , choose ε > 0 \varepsilon>0 ε > 0 such that P ( W ≤ ε ) ≤ η \mathbb{P}(W\leq\varepsilon)\leq\eta P ( W ≤ ε ) ≤ η and ε \varepsilon ε is a continuity point of the distribution of W W W . Then lim sup n P ( V n ≤ ε ) ≤ η \limsup_n\mathbb{P}(V_n\leq\varepsilon)\leq\eta lim sup n P ( V n ≤ ε ) ≤ η . On { V n > ε } \{V_n>\varepsilon\} { V n > ε } , we have Z ℓ ( G ) > 0 Z_\ell(G)>0 Z ℓ ( G ) > 0 and
∣ Z k ( G ) / E G ( n , d ) [ Z k ( G ) ] Z ℓ ( G ) / E G ( n , d ) [ Z ℓ ( G ) ] − 1 ∣ = ∣ D n ∣ V n ≤ ∣ D n ∣ ε → p 0. \left|\frac{Z_k(G)/\mathbb{E}_{G(n,d)}[Z_k(G)]}{Z_\ell(G)/\mathbb{E}_{G(n,d)}[Z_\ell(G)]}-1\right|=\frac{|D_n|}{V_n}\leq\frac{|D_n|}{\varepsilon}\xrightarrow{p}0. Z ℓ ( G ) / E G ( n , d ) [ Z ℓ ( G )] Z k ( G ) / E G ( n , d ) [ Z k ( G )] − 1 = V n ∣ D n ∣ ≤ ε ∣ D n ∣ p 0.
Since η > 0 \eta>0 η > 0 is arbitrary, the ratio converges to 1 in probability. This completes the proof of Theorem 1.1. □
Remark 5.1. The argument gives a stronger form of (6) . By (26) , for every k k k , the normalised count Z k ( G ) / E G ( n , d ) [ Z k ( G ) ] Z_k(G)/\mathbb{E}_{G(n,d)}[Z_k(G)] Z k ( G ) / E G ( n , d ) [ Z k ( G )] is approximated in probability, as n → ∞ n\to\infty n → ∞ followed by m → ∞ m\to\infty m → ∞ , by the explicit function e − 1 / 4 W n ( m ) = ∏ i = 3 m ( 1 + δ i ) X i ( G ) e − λ i δ i e^{-1/4}W_n^{(m)}=\prod_{i=3}^{m}(1+\delta_i)^{X_i(G)}e^{-\lambda_i\delta_i} e − 1/4 W n ( m ) = ∏ i = 3 m ( 1 + δ i ) X i ( G ) e − λ i δ i of the short cycles of G G G . On simple graphs, X 1 = X 2 = 0 X_1=X_2=0 X 1 = X 2 = 0 , and the factors for i = 1 , 2 i=1,2 i = 1 , 2 in W n ( m ) W_n^{(m)} W n ( m ) reduce to the constant e 1 / 4 e^{1/4} e 1/4 . The approximation does not depend on k k k because the transfer matrix T T T in Lemma 3.1 has the same spectrum { d − 1 , − 1 } \{d-1,-1\} { d − 1 , − 1 } for every k k k , although the matrix itself depends on k k k .