Introduction
The critical beta-splitting tree is a particular case of a one-parameter family of random binary trees called beta-splitting models. The model was introduced in [2 ] as a more realistic model of real-world phylogenetic trees, and it has seen renewed interest in recent years [4 , 5 , 6 , 3 , 7 ] . Under a beta-splitting model, a random tree is generated by recursively partitioning { 1 , … , n } \{1,\ldots,n\} { 1 , … , n } according to a splitting probability distribution q ( n , i ) q(n,i) q ( n , i ) , 1 ≤ i < n 1 \le i < n 1 ≤ i < n , which gives the probability that a clade of size n n n is split into clades of size i i i and n − i n-i n − i . For the critical beta-splitting tree, this probability is
q ( n , i ) : = n 2 H n − 1 1 i ( n − i ) , (1) q(n,i) := \frac{n}{2H_{n-1}}\frac{1}{i(n-i)}, \tag*{(1)} q ( n , i ) := 2 H n − 1 n i ( n − i ) 1 , (1)
where H n − 1 H_{n-1} H n − 1 denotes the ( n − 1 ) (n-1) ( n − 1 ) th harmonic number.
The harmonic descent chain, described in [4 , 5 , 6 , 7 ] , is a discrete-time Markov chain on the states { 1 , 2 , 3 , … } \{1,2,3,\ldots\} { 1 , 2 , 3 , … } with transition probabilities
p ( j , i ) = 1 ( j − i ) H j − 1 , 1 ≤ i < j , j ≥ 2 , p(j,i) = \frac{1}{(j-i)H_{j-1}}, \qquad1 \le i < j,\ j \ge2, p ( j , i ) = ( j − i ) H j − 1 1 , 1 ≤ i < j , j ≥ 2 ,
and p ( 1 , 1 ) = 1 p(1,1)=1 p ( 1 , 1 ) = 1 . Started at state n n n , this Markov chain describes the sequence of clade sizes in the critical beta-splitting tree with n n n leaves along a path from the root to a uniformly random leaf. Of interest are the “occupation probabilities”, a ( n , k ) a(n,k) a ( n , k ) , defined as the probability that the chain started at state n n n is ever in state k k k . These characterize the asymptotic fringe distribution of the tree (see [1 ] in general), that is, the n → ∞ n \to\infty n → ∞ weak limit of the tree relative to a uniformly random leaf. In particular, it has been shown [3 , 6 , 7 , 13 ] that the limits lim n → ∞ a ( n , k ) = : a ( k ) \lim_{n\to\infty} a(n,k) =: a(k) lim n → ∞ a ( n , k ) =: a ( k ) exist,
a ( k ) = H k − 1 ζ ( 2 ) ( k − 1 ) , k ≥ 2 , (2) a(k)=\frac{H_{k-1}}{\zeta(2)(k-1)},\qquad k\ge2, \tag*{(2)} a ( k ) = ζ ( 2 ) ( k − 1 ) H k − 1 , k ≥ 2 , (2)
and a ( 1 ) = 1 a(1)=1 a ( 1 ) = 1 . In turn, the “reverse harmonic descent chain” is a Markov chain with “upward” transition probabilities
q ↑ ( i , j ) = a ( j ) a ( i ) p ( j , i ) . q^{\uparrow}(i,j)=\frac{a(j)}{a(i)}p(j,i). q ↑ ( i , j ) = a ( i ) a ( j ) p ( j , i ) .
Letting, at each upward step i → j i \to j i → j , the sibling clade be distributed according to the critical beta-splitting distribution with j − i j-i j − i leaves, the resulting infinite tree described by the upward chain is the extended fringe [1 ] relative to a typical leaf.
Many quantities of interest obey the recursion
x n = 1 H n − 1 ∑ i = 1 n − 1 x i n − i , n > M , (3) x_n=\frac{1}{H_{n-1}}\sum_{i=1}^{n-1}\frac{x_i}{n-i},\qquad n>M, \tag*{(3)} x n = H n − 1 1 i = 1 ∑ n − 1 n − i x i , n > M , (3)
with some set of initial conditions. For example, if N n ( k ) N_n(k) N n ( k ) is the number of k k k -leaf subtrees of a critical beta-splitting tree with n n n leaves and I n I_n I n is the size of the split at the root, then the conditional distribution of N n ( k ) N_n(k) N n ( k ) given I n = i I_n=i I n = i is the same as N i ( k ) + N n − i ( k ) + 1 ( n = k ) N_i(k)+N_{n-i}(k)+1(n=k) N i ( k ) + N n − i ( k ) + 1 ( n = k ) . So, the law of total probability yields
E ( N n ( k ) ) n = 1 H n − 1 ∑ i = 1 n − 1 E ( N i ( k ) ) / i n − i \frac{\mathbb{E}(N_n(k))}{n}=\frac{1}{H_{n-1}}\sum_{i=1}^{n-1}\frac{\mathbb{E}(N_i(k))/i}{n-i} n E ( N n ( k )) = H n − 1 1 i = 1 ∑ n − 1 n − i E ( N i ( k )) / i
for n > k n>k n > k , that is, the quantity E ( N n ( k ) ) / n = a ( n , k ) / k \mathbb{E}(N_n(k))/n=a(n,k)/k E ( N n ( k )) / n = a ( n , k ) / k obeys the recursion described.
Recently, Brandenberger et al. [8 ] analyzed such recursions and found bounds on the rate of convergence to the limit x : = lim n → ∞ x n x:=\lim_{n\to\infty}x_n x := lim n → ∞ x n when x n x_n x n has the initial conditions x 1 = ⋯ = x k − 1 = 0 x_1=\cdots=x_{k-1}=0 x 1 = ⋯ = x k − 1 = 0 and x k > 0 x_k>0 x k > 0 . Because a ( n , k ) = k E ( N n ( k ) ) / n a(n,k)=k\mathbb{E}(N_n(k))/n a ( n , k ) = k E ( N n ( k )) / n , this analysis yielded, in turn, a description of the asymptotic behavior of a ( n , k ) a(n,k) a ( n , k ) ; in particular, they showed [8 eqn. (1.6)]
a ( n , k ) − a ( k ) = n − γ ∗ + o ( 1 ) (4) a(n,k)-a(k)=n^{-\gamma_*+o(1)} \tag*{(4)} a ( n , k ) − a ( k ) = n − γ ∗ + o ( 1 ) (4)
for some 1.5 < γ ∗ < 2 1.5<\gamma_*<2 1.5 < γ ∗ < 2 . Moreover, they showed a central limit theorem based on the contraction method (e.g., see [16 , 17 ] for this method in general) for statistics of the critical beta-splitting tree:
Proposition 1.1 (Proposition 1.3 of [8 ] ). Let ( X n ′ ) n ≥ 1 (X'_n)_{n\ge1} ( X n ′ ) n ≥ 1 and ( X n ′ ′ ) n ≥ 1 (X''_n)_{n\ge1} ( X n ′′ ) n ≥ 1 be independent copies of the random sequence ( X n ) n ≥ 1 (X_n)_{n\ge1} ( X n ) n ≥ 1 , independent also of ( I n , b n ) n ≥ 2 (I_n,b_n)_{n\ge2} ( I n , b n ) n ≥ 2 , and suppose that
X n = d X I n ′ + X n − I n ′ ′ + b n , n ≥ 2. (5) X_n \mathrel{\overset{d}{=}} X'_{I_n}+X''_{n-I_n}+b_n,\qquad n\ge2. \tag*{(5)} X n = d X I n ′ + X n − I n ′′ + b n , n ≥ 2. (5) Suppose further that there exist constants μ , σ , ϵ , C > 0 \mu,\sigma,\epsilon,C>0 μ , σ , ϵ , C > 0 such that ∣ E ( X n ) − μ n ∣ ≤ C n 1 / 2 − ϵ |\mathbb{E}(X_n)-\mu n|\le Cn^{1/2-\epsilon} ∣ E ( X n ) − μ n ∣ ≤ C n 1/2 − ϵ and ∣ Var ( X n ) − σ 2 n ∣ ≤ C n 1 − ϵ |\operatorname{Var}(X_n)-\sigma^2n|\le Cn^{1-\epsilon} ∣ Var ( X n ) − σ 2 n ∣ ≤ C n 1 − ϵ and E ( ∣ b n ∣ 3 ) ≤ n 3 / 2 − ϵ \mathbb{E}(|b_n|^3)\le n^{3/2-\epsilon} E ( ∣ b n ∣ 3 ) ≤ n 3/2 − ϵ . Then
X n − E ( X n ) Var ( X n ) ⟶ d N ( 0 , 1 ) . (6) \frac{X_n-\mathbb{E}(X_n)}{\sqrt{\operatorname{Var}(X_n)}}\mathrel{\overset{d}{\longrightarrow}}\mathcal{N}(0,1). \tag*{(6)} Var ( X n ) X n − E ( X n ) ⟶ d N ( 0 , 1 ) . (6)
See [14 ] as well for another example of the contraction method applied specifically to the critical beta-splitting tree. Of interest to us in particular, Brandenberger et al. [8 ] demonstrated that their analysis of x n x_n x n can be used to determine that ( X n ) n ≥ 1 (X_n)_{n\geq1} ( X n ) n ≥ 1 satisfies the conditions of the CLT when ( E ( X n ) / n ) n ≥ 1 (\mathbb{E}(X_n)/n)_{n\geq1} ( E ( X n ) / n ) n ≥ 1 obeys this recursion and initial conditions.
Our first main result is to present an exact asymptotic expansion of a ( n , k ) a(n,k) a ( n , k ) in terms of a ( k ) a(k) a ( k ) , as n → ∞ n \to\infty n → ∞ with k ∈ o ( n ) k \in o(\sqrt{n}) k ∈ o ( n ) . Our result refines the asymptotic estimate shown in [8 ] and confirms the exact value of γ ∗ \gamma_* γ ∗ , given numerically in [8 ] , as γ ∗ = ∣ s 1 ∣ + 1 = 1.567 … \gamma_* = |s_1| + 1 = 1.567\ldots γ ∗ = ∣ s 1 ∣ + 1 = 1.567 … where s 1 s_1 s 1 denotes the largest negative root of ψ ( s ) − ψ ( 1 ) \psi(s)-\psi(1) ψ ( s ) − ψ ( 1 ) . Our second result gives convergence bounds for a sequence x n x_n x n obeying the recursion (1.3) with a more general set of initial conditions than in Theorem 1.1 of [8 ] , in particular, x k ≥ 0 x_k \geq0 x k ≥ 0 for all 1 ≤ k ≤ M 1 \leq k \leq M 1 ≤ k ≤ M and x k > 0 x_k > 0 x k > 0 for at least one k k k . For appropriate random variables, this result enables Proposition 1.1 to be applied when ( E ( X n ) / n ) n ≥ 1 (\mathbb{E}(X_n)/n)_{n\geq1} ( E ( X n ) / n ) n ≥ 1 obeys our more general initial conditions, and as a demonstration we give a CLT for a random variable of interest which falls outside the scope of Theorem 1.1 of [8 ] .
Notation and Terminology
1 A ( x ) 1_A(x) 1 A ( x ) denotes the indicator function over the event A A A . We may often write, for example, 1 ( x ≤ N ) 1(x \leq N) 1 ( x ≤ N ) for 1 { y ≤ N } ( x ) 1_{\{y\leq N\}}(x) 1 { y ≤ N } ( x ) .
We use standard terminology for trees and consider ordered, unlabelled binary trees. For a tree T T T , let ∣ T ∣ |T| ∣ T ∣ denote the number of vertices in T T T , and let [ T ] [T] [ T ] denote the number of leaves of T T T . For a vertex v ∈ T v \in T v ∈ T , let T ( v ) T(v) T ( v ) denote the subtree of T T T rooted at v v v , and let p ( v ) p(v) p ( v ) denote the parent vertex of v v v .
Unless otherwise stated, T n T_n T n is a random critical beta-splitting tree with n n n leaves.
Write ψ ( s ) \psi(s) ψ ( s ) for the digamma function, H n = ∑ i = 1 n i − 1 H_n = \sum_{i=1}^{n} i^{-1} H n = ∑ i = 1 n i − 1 for the n n n th harmonic number, and ζ ( s ) \zeta(s) ζ ( s ) for the Riemann zeta function.
We denote that f ( n ) f(n) f ( n ) and g ( n ) g(n) g ( n ) are asymptotically equivalent by f ( n ) ∼ g ( n ) f(n) \sim g(n) f ( n ) ∼ g ( n ) .
Main Results
Asymptotics for the Harmonic Descent Chain
Our first result is an exact asymptotic expansion of the occupation probabilities, a ( n , k ) a(n,k) a ( n , k ) . It was shown in Brandenberger et al. [8 ] , eqn. (1.6) that for x n x_n x n obeying the recursion (1.3) with initial conditions x n = 0 x_n = 0 x n = 0 for n < k n < k n < k and x k > 0 x_k > 0 x k > 0 , that x : = lim n → ∞ x n x := \lim_{n\to\infty} x_n x := lim n → ∞ x n exists and
x n − x = n − γ ∗ + o ( 1 ) x_n - x = n^{-\gamma_*+o(1)} x n − x = n − γ ∗ + o ( 1 )
for some 1.5 < γ ∗ < 2 1.5 < \gamma_* < 2 1.5 < γ ∗ < 2 . They reported that γ ∗ = 1.567353 … \gamma_* = 1.567353\ldots γ ∗ = 1.567353 … numerically. Because a ( n , k ) = k E ( N n ( k ) ) / n a(n,k) = k\mathbb{E}(N_n(k))/n a ( n , k ) = k E ( N n ( k )) / n and E ( N n ( k ) ) / n \mathbb{E}(N_n(k))/n E ( N n ( k )) / n follows this behavior of x n x_n x n , the result gives an asymptotic estimate for a ( n , k ) − a ( k ) a(n,k)-a(k) a ( n , k ) − a ( k ) .
We further refine this asymptotic estimate by providing a full asymptotic expansion for a ( n , k ) − a ( k ) a(n,k)-a(k) a ( n , k ) − a ( k ) ; moreover, this expansion analytically confirms the value of γ ∗ \gamma_* γ ∗ as ∣ s 1 ∣ + 1 = 1.567 … |s_1|+1 = 1.567\ldots ∣ s 1 ∣ + 1 = 1.567 … , where s 1 s_1 s 1 is the largest negative root of ψ ( s ) − ψ ( 1 ) \psi(s)-\psi(1) ψ ( s ) − ψ ( 1 ) , and gives the exact coefficient of the leading term in the expansion. The proof proceeds by first noticing that an expression for a ( n , k ) a(n,k) a ( n , k ) given in eqn. (5.4) of [3 ] ,
a ( n , k ) = ( n − 1 k − 1 ) H k − 1 ∑ j = 0 n − k ( n − k j ) ( − 1 ) j ψ ( k + j ) − ψ ( 1 ) , a(n,k) = \binom{n-1}{k-1} H_{k-1} \sum_{j=0}^{n-k} \binom{n-k}{j} \frac{(-1)^j}{\psi(k+j)-\psi(1)}, a ( n , k ) = ( k − 1 n − 1 ) H k − 1 j = 0 ∑ n − k ( j n − k ) ψ ( k + j ) − ψ ( 1 ) ( − 1 ) j ,
can be viewed as a forward difference of the function
1 ψ ( k + x ) − ψ ( 1 ) , \frac{1}{\psi(k+x)-\psi(1)}, ψ ( k + x ) − ψ ( 1 ) 1 ,
then analyzing the corresponding Rice integral by the Cauchy residue theorem.
Theorem 2.1. As n → ∞ n \to\infty n → ∞ with k ∈ o ( n ) k \in o(\sqrt{n}) k ∈ o ( n ) and k ≥ 2 k \ge2 k ≥ 2 ,
a ( n , k ) − a ( k ) ∼ ∑ i = 1 ∞ H k − 1 Γ ( k + ∣ s i ∣ ) Γ ( k ) ψ ′ ( s i ) Γ ( n ) Γ ( n + 1 + ∣ s i ∣ ) , (7) a(n,k)-a(k) \sim\sum_{i=1}^{\infty}\frac{H_{k-1}\Gamma(k+|s_i|)}{\Gamma(k)\psi'(s_i)}\frac{\Gamma(n)}{\Gamma(n+1+|s_i|)}, \tag*{(7)} a ( n , k ) − a ( k ) ∼ i = 1 ∑ ∞ Γ ( k ) ψ ′ ( s i ) H k − 1 Γ ( k + ∣ s i ∣ ) Γ ( n + 1 + ∣ s i ∣ ) Γ ( n ) , (7) where 0 > s 1 > s 2 > … 0>s_1>s_2>\ldots 0 > s 1 > s 2 > … are the negative roots of ψ ( s ) − ψ ( 1 ) \psi(s)-\psi(1) ψ ( s ) − ψ ( 1 ) . Moreover, for fixed k ≥ 2 k\ge2 k ≥ 2 , we have
a ( n , k ) − a ( k ) ∼ ∑ i = 1 ∞ ∑ j = 1 ∞ c i , j ( k ) n − ∣ s i ∣ − j (8) a(n,k)-a(k) \sim\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}c_{i,j}(k)n^{-|s_i|-j} \tag*{(8)} a ( n , k ) − a ( k ) ∼ i = 1 ∑ ∞ j = 1 ∑ ∞ c i , j ( k ) n − ∣ s i ∣ − j (8) for some computable constants c i , j ( k ) c_{i,j}(k) c i , j ( k ) , and in particular,
a ( n , k ) − a ( k ) = H k − 1 Γ ( k + ∣ s 1 ∣ ) Γ ( k ) ψ ′ ( s 1 ) n − ∣ s 1 ∣ − 1 + O ( n − ∣ s 1 ∣ − 2 ) . (9) a(n,k)-a(k)=\frac{H_{k-1}\Gamma(k+|s_1|)}{\Gamma(k)\psi'(s_1)}n^{-|s_1|-1}+O\left(n^{-|s_1|-2}\right). \tag*{(9)} a ( n , k ) − a ( k ) = Γ ( k ) ψ ′ ( s 1 ) H k − 1 Γ ( k + ∣ s 1 ∣ ) n − ∣ s 1 ∣ − 1 + O ( n − ∣ s 1 ∣ − 2 ) . (9)
Extension of Convergence Bounds for a Recursive Sequence
Our second result gives convergence bounds on a sequence obeying the recursion (1.3) with a more general set of initial conditions. An analogous result was shown in Brandenberger et al. for the initial conditions x n = 0 x_n=0 x n = 0 for n < k n<k n < k and x k > 0 x_k>0 x k > 0 . We extend their result to the initial conditions x n = 0 x_n=0 x n = 0 for n ≤ M n\le M n ≤ M except x k > 0 x_k>0 x k > 0 for some k ≤ M k\le M k ≤ M , that is, allowing the non-zero initial condition to occur anywhere in the first M M M terms, rather than strictly at the first non-zero index. As a corollary, we find that the result easily extends to arbitrary non-negative initial conditions.
The following theorem is analogous to [8 Theorem 1.1] ; in particular, our parts (i) and (ii) are analogous to their parts (i) and (ii).
Outline of the proof. As in Brandenberger et al. [8 ] , considering the more general recursion
x n = ∑ i = 1 n − 1 p ( n , i ) x i , n > M , x_n=\sum_{i=1}^{n-1}p(n,i)x_i,\qquad n>M, x n = i = 1 ∑ n − 1 p ( n , i ) x i , n > M ,
for some probability mass function (p.m.f.) p ( n , i ) p(n,i) p ( n , i ) , one finds a recursion for the sequence of differences x n + 1 − x n x_{n+1}-x_n x n + 1 − x n . In our case, this recursion retains a forcing term which depends on the initial conditions. In Lemma 4.1 , which plays an analogous role to [8 ] , Proposition 1.2, we impose an additional restriction on p ( n , i ) p(n,i) p ( n , i ) which is sufficient to control the behavior of the forcing term. In particular, define
s ( n , i ) = ∑ j = 1 i q ( n , j ) and α i , n = s ( n + 1 , i ) s ( n + 1 , M ) − s ( n , i ) s ( n , M ) . s(n,i)=\sum_{j=1}^{i}q(n,j)\quad\text{and}\quad\alpha_{i,n}=\frac{s(n+1,i)}{s(n+1,M)}-\frac{s(n,i)}{s(n,M)}. s ( n , i ) = j = 1 ∑ i q ( n , j ) and α i , n = s ( n + 1 , M ) s ( n + 1 , i ) − s ( n , M ) s ( n , i ) .
We impose that for all n n n , α i , n / α i , n + 1 ≥ α j , n / α j , n + 1 \alpha_{i,n}/\alpha_{i,n+1}\ge\alpha_{j,n}/\alpha_{j,n+1} α i , n / α i , n + 1 ≥ α j , n / α j , n + 1 whenever i ≥ j i\ge j i ≥ j , for i , j ≠ M i,j\ne M i , j = M . We find, then, that the behavior of the sequence falls into two distinct regimes: the differences are non-negative for all n > M n>M n > M , or the differences are initially non-negative but finally strictly negative, changing sign no more than once.
Theorem 2.2 (i) then follows by showing that q ( n , i ) q(n,i) q ( n , i ) obeys the additional constraint. To this end, we define Q ( n , x ) : = [ ψ ( n ) − ψ ( n − x ) ] / [ ψ ( n ) − ψ ( n − M ) ] Q(n,x):=[\psi(n)-\psi(n-x)]/[\psi(n)-\psi(n-M)] Q ( n , x ) := [ ψ ( n ) − ψ ( n − x )] / [ ψ ( n ) − ψ ( n − M )] , A ( n , x ) : = Q ( n + 1 , x ) − Q ( n , x ) A(n,x):=Q(n+1,x)-Q(n,x) A ( n , x ) := Q ( n + 1 , x ) − Q ( n , x ) and R ( n , x ) : = A ( n , x ) / A ( n + 1 , x ) R(n,x):=A(n,x)/A(n+1,x) R ( n , x ) := A ( n , x ) / A ( n + 1 , x ) , so that A ( n , i ) = α i , n A(n,i)=\alpha_{i,n} A ( n , i ) = α i , n and the result follows from ∂ x R ( n , x ) > 0 \partial_xR(n,x)>0 ∂ x R ( n , x ) > 0 . This is equivalent to showing that
A ′ ( n , x ) A ( n , x ) \frac{A'(n,x)}{A(n,x)} A ( n , x ) A ′ ( n , x )
is decreasing in n n n , which we prove by showing that under a change of measure A ′ ( n , x ) / A ( n , x ) A'(n,x)/A(n,x) A ′ ( n , x ) / A ( n , x ) can be seen as the expectation of a decreasing function Ψ ( t ) \Psi(t) Ψ ( t ) , defined in the proof, under a probability measure η n , x \eta_{n,x} η n , x for which η n + 1 , x ⪰ s t η n , x \eta_{n+1,x}\succeq_{\mathrm{st}}\eta_{n,x} η n + 1 , x ⪰ st η n , x .
To show Theorem 2.2 (ii), we bound the rate of convergence, as in [8 ] , using that the sequence of differences changes sign at most once.
Theorem 2.2. Let M ≥ 1 M \ge1 M ≥ 1 . Consider ( x i ) i = 1 ∞ (x_i)_{i=1}^{\infty} ( x i ) i = 1 ∞ a sequence defined by
x n = 1 H n − 1 ∑ i = 1 n − 1 x i n − i , for n > M , (10) x_n = \frac{1}{H_{n-1}}\sum_{i=1}^{n-1}\frac{x_i}{n-i}, \quad\text{for } n > M, \tag*{(10)} x n = H n − 1 1 i = 1 ∑ n − 1 n − i x i , for n > M , (10) with initial conditions x n = 0 x_n = 0 x n = 0 for n ≤ M n \le M n ≤ M except that x k > 0 x_k > 0 x k > 0 for a k ≤ M k \le M k ≤ M . Then we have the following:
(i) Either x n x_n x n is monotone increasing for all n > M n > M n > M , or there exists N ≥ M N \ge M N ≥ M such that x n x_n x n is monotone increasing for M < n ≤ N M < n \le N M < n ≤ N and strictly monotone decreasing for n > N n > N n > N ; in particular, the limit x : = lim n → ∞ x n x := \lim_{n\to\infty} x_n x := lim n → ∞ x n exists;
(ii) There exists a constant N ≥ M N \ge M N ≥ M such that for all n > M n > M n > M , ∣ x n − x ∣ ≤ 4 ln ( 2 ) N n − M x k |x_n-x| \le\frac{4}{\ln(2)}\frac{N}{n-M}x_k ∣ x n − x ∣ ≤ l n ( 2 ) 4 n − M N x k .
Corollary 2.3. If ( x i ) i = 1 ∞ (x_i)_{i=1}^{\infty} ( x i ) i = 1 ∞ is a sequence defined as in (2.4) but with the initial conditions x k ≥ 0 x_k \ge0 x k ≥ 0 for all 1 ≤ k ≤ M 1 \le k \le M 1 ≤ k ≤ M and x k > 0 x_k > 0 x k > 0 for at least one k k k , then x : = lim n → ∞ x n x := \lim_{n\to\infty}x_n x := lim n → ∞ x n exists, and there exists N ′ ≥ M N' \ge M N ′ ≥ M such that for all n > M n > M n > M , ∣ x n − x ∣ ≤ 4 ln ( 2 ) N ′ n − M ∑ k = 1 M x k |x_n-x| \le\frac{4}{\ln(2)}\frac{N'}{n-M}\sum_{k=1}^{M}x_k ∣ x n − x ∣ ≤ l n ( 2 ) 4 n − M N ′ ∑ k = 1 M x k .
To fix ideas about Theorem 2.2 (i), see Figure 1 .
Figure 1. Illustration of tail behavior regimes. The left plot shows x n + 1 − x n ≥ 0 x_{n+1}-x_n \ge0 x n + 1 − x n ≥ 0 for all n > M n > M n > M ; the right plot shows x n + 1 − x n x_{n+1}-x_n x n + 1 − x n initially non-negative, changing sign once before a strictly negative tail.
Remark 2.4. From the proof of Theorem 2.2 (ii), we see that N = M N=M N = M whenever k = M k=M k = M or x n x_n x n is monotone increasing for all n n n . Otherwise, N N N is the index of the last non-negative term in ( x n + 1 − x n ) (x_{n+1}-x_n) ( x n + 1 − x n ) and, for a particular set of initial conditions, may be found explicitly by computing the first terms of x n x_n x n .
Example: A Central Limit Theorem
As an application of Theorem 2.2 , we show a central limit theorem for a random variable of interest which does not fall in the setting of [8 Theorem 1.1] .
For fixed M > 0 M>0 M > 0 , define B n ( M ) \mathcal{B}_n^{(M)} B n ( M ) as the minimal set of vertices v ∈ T n v\in\mathcal{T}_n v ∈ T n which satisfies: (1) [ T n ( v ) ] ≤ M [\mathcal{T}_n(v)]\le M [ T n ( v )] ≤ M for all v v v , and (2) the collection of leaf sets of T n ( v ) \mathcal{T}_n(v) T n ( v ) partitions the leaf set of T n \mathcal{T}_n T n . In particular,
B n ( M ) : = { v ∣ [ T n ( v ) ] ≤ M < [ T n ( p ( v ) ) ] } (11) \mathcal{B}_n^{(M)}:=\{v\mid[\mathcal{T}_n(v)]\le M<[\mathcal{T}_n(p(v))]\} \tag*{(11)} B n ( M ) := { v ∣ [ T n ( v )] ≤ M < [ T n ( p ( v ))]} (11)
Then define N n , k ( M ) N_{n,k}^{(M)} N n , k ( M ) to be the number of subtrees in B n ( M ) \mathcal{B}_n^{(M)} B n ( M ) with k k k leaves. Note that N n , k ( M ) = 1 ( n = k ) N_{n,k}^{(M)}=\mathbb{1}(n=k) N n , k ( M ) = 1 ( n = k ) deterministically for n ≤ M n\le M n ≤ M .
Corollary 2.5. Let X n = ∑ k = 1 M x k N n , k ( M ) X_n=\sum_{k=1}^{M}x_kN_{n,k}^{(M)} X n = ∑ k = 1 M x k N n , k ( M ) , for some constants x k x_k x k , be a non-constant random variable. Then
X n − E ( X n ) Var ( X n ) → d N ( 0 , 1 ) . (12) \frac{X_n-\mathbb{E}(X_n)}{\sqrt{\operatorname{Var}(X_n)}}\xrightarrow{d}\mathcal{N}(0,1). \tag*{(12)} Var ( X n ) X n − E ( X n ) d N ( 0 , 1 ) . (12)
Remark 2.6. For example, if x k = k x_k=k x k = k , then X n = n X_n=n X n = n deterministically, and the CLT does not hold.
Lemma 2.7. Let E n : = n − 1 E ( X n ) E_n:=n^{-1}\mathbb{E}(X_n) E n := n − 1 E ( X n ) . There exist μ \mu μ and C C C such that ∣ E n − μ ∣ ≤ C n − 1 |E_n-\mu|\le Cn^{-1} ∣ E n − μ ∣ ≤ C n − 1 .
Proof. Let
X n + : = ∑ k = 1 M x k 1 ( x k > 0 ) N n , k ( M ) and X n − : = − ∑ k = 1 M x k 1 ( x k < 0 ) N n , k ( M ) X_n^+:=\sum_{k=1}^{M}x_k\mathbb{1}(x_k>0)N_{n,k}^{(M)}
\qquad\text{and}\qquad
X_n^-:=-\sum_{k=1}^{M}x_k\mathbb{1}(x_k<0)N_{n,k}^{(M)} X n + := k = 1 ∑ M x k 1 ( x k > 0 ) N n , k ( M ) and X n − := − k = 1 ∑ M x k 1 ( x k < 0 ) N n , k ( M ) be the positive and negative parts of X n X_n X n , respectively, so that X n = X n + − X n − X_n=X_n^+-X_n^- X n = X n + − X n − . Then write E n + : = n − 1 E ( X n + ) E_n^+:=n^{-1}\mathbb{E}(X_n^+) E n + := n − 1 E ( X n + ) and E n − : = n − 1 E ( X n − ) E_n^-:=n^{-1}\mathbb{E}(X_n^-) E n − := n − 1 E ( X n − ) . The law of total expectation yields for n > M n>M n > M
E ( X n + ) = n 2 H n − 1 ∑ i = 1 n − 1 E ( X i + ) + E ( X n − i + ) i ( n − i ) \mathbb{E}(X_n^+)=\frac{n}{2H_{n-1}}\sum_{i=1}^{n-1}\frac{\mathbb{E}(X_i^+)+\mathbb{E}(X_{n-i}^+)}{i(n-i)} E ( X n + ) = 2 H n − 1 n i = 1 ∑ n − 1 i ( n − i ) E ( X i + ) + E ( X n − i + ) = n H n − 1 ∑ i = 1 n − 1 E ( X i + ) i ( n − i ) =\frac{n}{H_{n-1}}\sum_{i=1}^{n-1}\frac{\mathbb{E}(X_i^+)}{i(n-i)} = H n − 1 n i = 1 ∑ n − 1 i ( n − i ) E ( X i + ) E n + = 1 H n − 1 ∑ i = 1 n − 1 E i + n − i E_n^+=\frac{1}{H_{n-1}}\sum_{i=1}^{n-1}\frac{E_i^+}{n-i} E n + = H n − 1 1 i = 1 ∑ n − 1 n − i E i + and similarly for X n − X_n^- X n − . X n + X_n^+ X n + has the initial conditions ( x k / k ) 1 ( x k > 0 ) (x_k/k)\mathbb{1}(x_k>0) ( x k / k ) 1 ( x k > 0 ) and X n − X_n^- X n − the initial conditions ( ∣ x k ∣ / k ) 1 ( x k < 0 ) (|x_k|/k)\mathbb{1}(x_k<0) ( ∣ x k ∣/ k ) 1 ( x k < 0 ) for k = 1 , … , M k=1,\ldots,M k = 1 , … , M . By Corollary 2.3, there exist μ + \mu^+ μ + and μ − \mu^- μ − such that
∣ E n + − μ + ∣ ≤ 4 ln ( 2 ) N ′ n − M ∑ k = 1 M x k 1 ( x k > 0 ) , |E_n^+-\mu^+|\le\frac{4}{\ln(2)}\frac{N'}{n-M}\sum_{k=1}^{M}x_k\mathbb{1}(x_k>0), ∣ E n + − μ + ∣ ≤ ln ( 2 ) 4 n − M N ′ k = 1 ∑ M x k 1 ( x k > 0 ) , and
∣ E n − − μ − ∣ ≤ 4 ln ( 2 ) N ′ ′ n − M ∑ k = 1 M ∣ x k ∣ 1 ( x k < 0 ) , |E_n^--\mu^-|\le\frac{4}{\ln(2)}\frac{N''}{n-M}\sum_{k=1}^{M}|x_k|\mathbb{1}(x_k<0), ∣ E n − − μ − ∣ ≤ ln ( 2 ) 4 n − M N ′′ k = 1 ∑ M ∣ x k ∣1 ( x k < 0 ) , for some N ′ , N ′ ′ ≥ M N',N''\ge M N ′ , N ′′ ≥ M . Then
∣ E n − ( μ + − μ − ) ∣ ≤ ∣ E n + − μ + ∣ + ∣ E n − − μ − ∣ |E_n-(\mu^+-\mu^-)|\le|E_n^+-\mu^+|+|E_n^--\mu^-| ∣ E n − ( μ + − μ − ) ∣ ≤ ∣ E n + − μ + ∣ + ∣ E n − − μ − ∣ ≤ 1 n − M 4 ln ( 2 ) ∑ k = 1 M ∣ x k ∣ [ N ′ 1 ( x k > 0 ) + N ′ ′ 1 ( x k < 0 ) ] . \le\frac{1}{n-M}\frac{4}{\ln(2)}\sum_{k=1}^{M}|x_k|\left[N'\mathbb{1}(x_k>0)+N''\mathbb{1}(x_k<0)\right]. ≤ n − M 1 ln ( 2 ) 4 k = 1 ∑ M ∣ x k ∣ [ N ′ 1 ( x k > 0 ) + N ′′ 1 ( x k < 0 ) ] .
Lemma 2.8. Let V n : = n − 1 Var ( X n ) V_n:=n^{-1}\operatorname{Var}(X_n) V n := n − 1 Var ( X n ) . There exist σ \sigma σ and C C C such that ∣ V n − σ 2 ∣ ≤ C n − 1 / 6 |V_n-\sigma^2|\le Cn^{-1/6} ∣ V n − σ 2 ∣ ≤ C n − 1/6 .
Proof. For n > M n>M n > M , the law of total variance yields
V n = 1 n E ( Var ( X I n + X n − I n ∣ I n ) ) + 1 n Var ( E ( X I n + X n − I n ∣ I n ) ) = 1 H n − 1 ∑ i = 1 n − 1 V i n − i + ϵ n \begin{aligned}
V_n=\frac{1}{n}\mathbb{E}\left(\operatorname{Var}\left(X_{I_n}+X_{n-I_n}\mid I_n\right)\right)+\frac{1}{n}\operatorname{Var}\left(\mathbb{E}\left(X_{I_n}+X_{n-I_n}\mid I_n\right)\right) \\
&=\frac{1}{H_{n-1}}\sum_{i=1}^{n-1}\frac{V_i}{n-i}+\epsilon_n
\end{aligned} V n = n 1 E ( Var ( X I n + X n − I n ∣ I n ) ) + n 1 Var ( E ( X I n + X n − I n ∣ I n ) ) = H n − 1 1 i = 1 ∑ n − 1 n − i V i + ϵ n
where
ϵ n : = 1 n Var ( E ( X I n + X n − I n ∣ I n ) ) = O ( 1 n ) \epsilon_n:=\frac{1}{n}\operatorname{Var}\left(\mathbb{E}\left(X_{I_n}+X_{n-I_n}\mid I_n\right)\right)=O\left(\frac{1}{n}\right) ϵ n := n 1 Var ( E ( X I n + X n − I n ∣ I n ) ) = O ( n 1 )
by Lemma 2.7. Since X n X_n X n is deterministic for n ≤ M n\le M n ≤ M , we have V 1 = ⋯ = V M = 0 V_1=\cdots=V_M=0 V 1 = ⋯ = V M = 0 . This recursion is identical to that of [8 Lemma 4.2] , and we obtain the same result.
Proof of Corollary 2.5. Notice that N n , k ( M ) = 1 ( n = k ) N_{n,k}^{(M)}=1(n=k) N n , k ( M ) = 1 ( n = k ) for n ≤ M n\le M n ≤ M . If we define
b n = ∑ k = 1 M x k [ 1 ( n = k ) − ( 1 ( I n = k ) + 1 ( n − I n = k ) ) 1 ( 2 ≤ n ≤ M ) ] , b_n=\sum_{k=1}^{M}x_k\left[1(n=k)-\left(1(I_n=k)+1(n-I_n=k)\right)1(2\le n\le M)\right], b n = k = 1 ∑ M x k [ 1 ( n = k ) − ( 1 ( I n = k ) + 1 ( n − I n = k ) ) 1 ( 2 ≤ n ≤ M ) ] ,
we can write X n = X I n ′ + X n − I n ′ ′ + b n X_n=X'_{I_n}+X''_{n-I_n}+b_n X n = X I n ′ + X n − I n ′′ + b n for n ≥ 2 n\ge2 n ≥ 2 , where X n ′ X'_n X n ′ and X n ′ ′ X''_n X n ′′ are independent copies of X n X_n X n also independent of ( I n , b n ) (I_n,b_n) ( I n , b n ) . So, this sequence is amenable to [8 Proposition 1.3] . Using the estimates for E n E_n E n and V n V_n V n from Lemmas 2.7 and 2.8, the result follows from Proposition 1.1.
Proof of Theorem 2.1
Proof of Theorem 2.1 (2.1). For k ≥ 2 k \ge2 k ≥ 2 , we note the exact formula for a ( n , k ) a(n,k) a ( n , k ) given in [3 eqn. (5.4)] :
a ( n , k ) = ( n − 1 k − 1 ) H k − 1 ∑ j = 0 n − k ( n − k j ) ( − 1 ) j ψ ( k + j ) − ψ ( 1 ) (14) a(n,k)=\binom{n-1}{k-1}H_{k-1}\sum_{j=0}^{n-k}\binom{n-k}{j}\frac{(-1)^j}{\psi(k+j)-\psi(1)} \tag*{(14)} a ( n , k ) = ( k − 1 n − 1 ) H k − 1 j = 0 ∑ n − k ( j n − k ) ψ ( k + j ) − ψ ( 1 ) ( − 1 ) j (14)
which, letting N = n − k N=n-k N = n − k , is the N N N th forward difference of
f k ( x ) : = 1 ψ ( k + x ) − ψ ( 1 ) (15) f_k(x):=\frac{1}{\psi(k+x)-\psi(1)} \tag*{(15)} f k ( x ) := ψ ( k + x ) − ψ ( 1 ) 1 (15)
multiplied by ( n − 1 k − 1 ) H k − 1 \binom{n-1}{k-1}H_{k-1} ( k − 1 n − 1 ) H k − 1 . As a forward difference, we will consider its corresponding Rice integral (e.g., see [11 ] ), that is,
∑ j = 0 N ( N j ) ( − 1 ) j f k ( j ) = − 1 2 π i ∮ C Γ ( N + 1 ) Γ ( − s ) Γ ( N + 1 − s ) f k ( s ) d s . (16) \sum_{j=0}^{N}\binom{N}{j}(-1)^jf_k(j)=-\frac{1}{2\pi i}\oint_C\frac{\Gamma(N+1)\Gamma(-s)}{\Gamma(N+1-s)}f_k(s)\,ds. \tag*{(16)} j = 0 ∑ N ( j N ) ( − 1 ) j f k ( j ) = − 2 π i 1 ∮ C Γ ( N + 1 − s ) Γ ( N + 1 ) Γ ( − s ) f k ( s ) d s . (16)
It is required that the contour C C C be positively oriented and chosen to encircle the poles located at s = 0 , 1 , … , N s=0,1,\ldots,N s = 0 , 1 , … , N but not the poles of f k ( s ) f_k(s) f k ( s ) , which here occur where ψ ( m + s ) = ψ ( 1 ) \psi(m+s)=\psi(1) ψ ( m + s ) = ψ ( 1 ) .
We will first determine a contour which satisfies these criteria. Let 0 > s k , 0 > s k , 1 > … 0>s_{k,0}>s_{k,1}>\ldots 0 > s k , 0 > s k , 1 > … denote the roots of ψ ( k + s ) − ψ ( 1 ) \psi(k+s)-\psi(1) ψ ( k + s ) − ψ ( 1 ) in decreasing order. Note s k , j = s j − k s_{k,j}=s_j-k s k , j = s j − k for j ≥ 1 j\ge1 j ≥ 1 . It is well known that ψ ( s ) − a = 0 \psi(s)-a=0 ψ ( s ) − a = 0 has only real solutions for a ∈ R a\in\mathbb{R} a ∈ R , since ψ ( s ) = − γ + ∑ n = 0 ∞ ( 1 n + 1 − 1 n + z ) \psi(s)=-\gamma+\sum_{n=0}^{\infty}\left(\frac{1}{n+1}-\frac{1}{n+z}\right) ψ ( s ) = − γ + ∑ n = 0 ∞ ( n + 1 1 − n + z 1 ) implies Im ( ψ ( z ) − a ) = Im ( z ) ∑ n = 0 ∞ 1 ∣ n + z ∣ 2 \operatorname{Im}(\psi(z)-a)=\operatorname{Im}(z)\sum_{n=0}^{\infty}\frac{1}{\lvert n+z\rvert^2} Im ( ψ ( z ) − a ) = Im ( z ) ∑ n = 0 ∞ ∣ n + z ∣ 2 1 . Then, since ψ ( s ) \psi(s) ψ ( s ) is strictly increasing for s ∈ R > 0 s\in\mathbb{R}_{>0} s ∈ R > 0 , the largest pole of f k f_k f k is s k , 0 = 1 − k s_{k,0}=1-k s k , 0 = 1 − k , which is negative for k ≥ 2 k\ge2 k ≥ 2 . That is, the poles of f k f_k f k lie strictly on R < 0 \mathbb{R}_{<0} R < 0 . So, let R R R be the rectangle with vertices − ( 1 / 2 ) ± i -(1/2)\pm i − ( 1/2 ) ± i and ( N + 1 / 2 ) ± i (N+1/2)\pm i ( N + 1/2 ) ± i and let C = ∂ R C=\partial R C = ∂ R be its boundary. In addition, as ψ ( s ) \psi(s) ψ ( s ) is strictly increasing on ( − m , − m + 1 ) (-m,-m+1) ( − m , − m + 1 ) for m = 1 , 2 , … m=1,2,\ldots m = 1 , 2 , … , we can be sure that f k f_k f k has no poles in ( − k , 1 − k ) (-k,1-k) ( − k , 1 − k ) , and that f k f_k f k has exactly one pole, s k , m s_{k,m} s k , m in each interval ( − m − k , − m − k + 1 ) (-m-k,-m-k+1) ( − m − k , − m − k + 1 ) for m ≥ 1 m\ge1 m ≥ 1 . See [19 Chapter XII] or [15 ] for additional details. In particular, the second pole, corresponding to the largest negative root of ψ ( s ) − ψ ( 1 ) \psi(s)-\psi(1) ψ ( s ) − ψ ( 1 ) , is located at s k , 1 = − ∣ s 1 ∣ − k = − k − 0.567 … s_{k,1}=-\lvert s_1\rvert-k=-k-0.567\ldots s k , 1 = − ∣ s 1 ∣ − k = − k − 0.567 … .
Lemma 3.1. For each m ≥ 1 m\ge1 m ≥ 1 ,
∣ s m + 1 ∣ > ∣ s m ∣ + 1 + ϵ m , (17) \lvert s_{m+1}\rvert>\lvert s_m\rvert+1+\epsilon_m, \tag*{(17)} ∣ s m + 1 ∣ > ∣ s m ∣ + 1 + ϵ m , (17) for some ϵ m > 0 \epsilon_m>0 ϵ m > 0 .
Proof. We use the reflection formula for ψ ( s ) \psi(s) ψ ( s ) :
ψ ( 1 − s ) − ψ ( s ) = π cot ( π s ) . \psi(1-s)-\psi(s)=\pi\cot(\pi s). ψ ( 1 − s ) − ψ ( s ) = π cot ( π s ) .
As s m ∈ ( − m , − m + 1 ) s_m\in(-m,-m+1) s m ∈ ( − m , − m + 1 ) , write s m = − m + δ m s_m=-m+\delta_m s m = − m + δ m , δ m ∈ ( 0 , 1 ) \delta_m\in(0,1) δ m ∈ ( 0 , 1 ) . For s = s m s=s_m s = s m , the reflection formula becomes
ψ ( 1 + m − δ m ) + γ = π cot ( π δ m ) . \psi(1+m-\delta_m)+\gamma=\pi\cot(\pi\delta_m). ψ ( 1 + m − δ m ) + γ = π cot ( π δ m ) .
Note that ψ ( s ) \psi(s) ψ ( s ) is strictly increasing for s > 1 s>1 s > 1 , and 2 + m − δ m + 1 > 1 + m > 1 + m − δ m 2+m-\delta_{m+1}>1+m>1+m-\delta_m 2 + m − δ m + 1 > 1 + m > 1 + m − δ m . Since cot ( π z ) \cot(\pi z) cot ( π z ) is decreasing on ( 0 , 1 ) (0,1) ( 0 , 1 ) , then
cot ( π δ m + 1 ) − cot ( π δ m ) = 1 π [ ψ ( 2 + m − δ m + 1 ) − ψ ( 1 + m − δ m ) ] > 0 \cot(\pi\delta_{m+1})-\cot(\pi\delta_m)=\frac{1}{\pi}\left[\psi(2+m-\delta_{m+1})-\psi(1+m-\delta_m)\right]>0 cot ( π δ m + 1 ) − cot ( π δ m ) = π 1 [ ψ ( 2 + m − δ m + 1 ) − ψ ( 1 + m − δ m ) ] > 0
implies δ m > δ m + 1 \delta_m>\delta_{m+1} δ m > δ m + 1 . In turn
∣ s m + 1 ∣ − ∣ s m ∣ = m + 1 − δ m + 1 − m + δ m = 1 + ( δ m − δ m + 1 ) > 1. \lvert s_{m+1}\rvert-\lvert s_m\rvert=m+1-\delta_{m+1}-m+\delta_m=1+(\delta_m-\delta_{m+1})>1. ∣ s m + 1 ∣ − ∣ s m ∣ = m + 1 − δ m + 1 − m + δ m = 1 + ( δ m − δ m + 1 ) > 1.
We see ϵ m = δ m − δ m + 1 > 0 \epsilon_m=\delta_m-\delta_{m+1}>0 ϵ m = δ m − δ m + 1 > 0 .
Our next step is an application of the Cauchy residue theorem.
Lemma 3.2. For each m ≥ 1 m \ge1 m ≥ 1 ,
− 1 2 π i ∮ C K ( N , s ) f k ( s ) d s = − 1 2 π i ∫ L k , m K ( N , s ) f k ( s ) d s + 1 ζ ( 2 ) ( k − 1 ) 1 ( N + k − 1 k − 1 ) + ∑ j = 1 ∞ Γ ( n − k + 1 ) Γ ( k + ∣ s j ∣ ) Γ ( n + 1 + ∣ s j ∣ ) ψ ′ ( s j ) . (18) -\frac{1}{2\pi i}\oint_C K(N,s)f_k(s)\,ds
=
-\frac{1}{2\pi i}\int_{L_{k,m}} K(N,s)f_k(s)\,ds
+\frac{1}{\zeta(2)(k-1)}\frac{1}{\binom{N+k-1}{k-1}}
+\sum_{j=1}^{\infty}\frac{\Gamma(n-k+1)\Gamma(k+\lvert s_j\rvert)}{\Gamma(n+1+\lvert s_j\rvert)\psi'(s_j)}. \tag*{(18)} − 2 π i 1 ∮ C K ( N , s ) f k ( s ) d s = − 2 π i 1 ∫ L k , m K ( N , s ) f k ( s ) d s + ζ ( 2 ) ( k − 1 ) 1 ( k − 1 N + k − 1 ) 1 + j = 1 ∑ ∞ Γ ( n + 1 + ∣ s j ∣) ψ ′ ( s j ) Γ ( n − k + 1 ) Γ ( k + ∣ s j ∣) . (18) where L k , m = c k , m + i R L_{k,m}=c_{k,m}+i\mathbb{R} L k , m = c k , m + i R and c k , m : = s k , m + 1 + ϵ m c_{k,m}:=s_{k,m+1}+\epsilon_m c k , m := s k , m + 1 + ϵ m , for some ϵ m > 0 \epsilon_m>0 ϵ m > 0 as given in Lemma 3.1 .
Proof. We take c k , m c_{k,m} c k , m and ϵ m \epsilon_m ϵ m as defined in the statement of the lemma. Define R X , Y \mathcal{R}_{X,Y} R X , Y to be the rectangle with vertices c k , m ± i Y c_{k,m}\pm iY c k , m ± iY and X ± i Y X\pm iY X ± iY for Y > r 0 Y>r_0 Y > r 0 and X > N + 1 / 2 X>N+1/2 X > N + 1/2 , and consider the contour C X , Y : = ∂ R X , Y \mathcal{C}_{X,Y}:=\partial\mathcal{R}_{X,Y} C X , Y := ∂ R X , Y . That is, we deform C C C into C X , Y \mathcal{C}_{X,Y} C X , Y so that it encircles the m + 1 m+1 m + 1 largest poles of f k f_k f k . Write
K ( N , s ) : = Γ ( N + 1 ) Γ ( − s ) Γ ( N − s + 1 ) = N ! ∏ j = 0 N ( j − s ) (19) K(N,s):=\frac{\Gamma(N+1)\Gamma(-s)}{\Gamma(N-s+1)}
=\frac{N!}{\prod_{j=0}^{N}(j-s)} \tag*{(19)} K ( N , s ) := Γ ( N − s + 1 ) Γ ( N + 1 ) Γ ( − s ) = ∏ j = 0 N ( j − s ) N ! (19)
for the kernel of the integral in (16) . Then
− 1 2 π i ∮ C K ( N , s ) f k ( s ) d s = − 1 2 π i ∮ C X , Y K ( N , s ) f k ( s ) d s + Res s = s k , 0 [ K ( N , s ) f k ( s ) ] + ∑ j = 1 m Res s = s k , j [ K ( N , s ) f k ( s ) ] . (20) -\frac{1}{2\pi i}\oint_C K(N,s)f_k(s)\,ds
=
-\frac{1}{2\pi i}\oint_{\mathcal{C}_{X,Y}} K(N,s)f_k(s)\,ds
+\mathop{\operatorname{Res}}_{s=s_{k,0}}\left[K(N,s)f_k(s)\right]
+\sum_{j=1}^{m}\mathop{\operatorname{Res}}_{s=s_{k,j}}\left[K(N,s)f_k(s)\right]. \tag*{(20)} − 2 π i 1 ∮ C K ( N , s ) f k ( s ) d s = − 2 π i 1 ∮ C X , Y K ( N , s ) f k ( s ) d s + Res s = s k , 0 [ K ( N , s ) f k ( s ) ] + j = 1 ∑ m Res s = s k , j [ K ( N , s ) f k ( s ) ] . (20)
Denote the left segment of C X , Y \mathcal{C}_{X,Y} C X , Y from c k , m − i Y c_{k,m}-iY c k , m − iY to c k , m + i Y c_{k,m}+iY c k , m + iY by L m , Y L_{m,Y} L m , Y , and denote the remainder of the contour by R X , Y \mathcal{R}_{X,Y} R X , Y . For ∣ s ∣ > N \lvert s\rvert>N ∣ s ∣ > N , ∣ s − j ∣ ≥ ∣ s ∣ − N \lvert s-j\rvert\ge\lvert s\rvert-N ∣ s − j ∣ ≥ ∣ s ∣ − N , so
∣ K ( N , s ) ∣ ≤ N ! ( ∣ s ∣ − N ) − N − 1 = O ( ∣ s ∣ − N − 1 ) . (21) \lvert K(N,s)\rvert\le N!(\lvert s\rvert-N)^{-N-1}=O\left(\lvert s\rvert^{-N-1}\right). \tag*{(21)} ∣ K ( N , s )∣ ≤ N ! (∣ s ∣ − N ) − N − 1 = O ( ∣ s ∣ − N − 1 ) . (21)
Note that s s s is bounded away from R < 0 \mathbb{R}_{<0} R < 0 and ψ ( s ) = ln ( s ) + O ( ∣ s ∣ − 1 ) ∼ ln ∣ s ∣ \psi(s)=\ln(s)+O\left(\lvert s\rvert^{-1}\right)\sim\ln\lvert s\rvert ψ ( s ) = ln ( s ) + O ( ∣ s ∣ − 1 ) ∼ ln ∣ s ∣ as ∣ s ∣ → ∞ \lvert s\rvert\to\infty ∣ s ∣ → ∞ , so that f k ( s ) ∼ ln − 1 ∣ s ∣ f_k(s)\sim\ln^{-1}\lvert s\rvert f k ( s ) ∼ ln − 1 ∣ s ∣ as ∣ s ∣ → ∞ \lvert s\rvert\to\infty ∣ s ∣ → ∞ . As a result, the portion of (20) along R X , Y \mathcal{R}_{X,Y} R X , Y converges to zero as X , Y → ∞ X,Y\to\infty X , Y → ∞ . Since f k f_k f k has no poles and is bounded on L m , Y L_{m,Y} L m , Y , so that the integral over L k , m : = lim Y → ∞ L m , Y L_{k,m}:=\lim_{Y\to\infty}L_{m,Y} L k , m := lim Y → ∞ L m , Y exists, we have
− 1 2 π i ∮ C K ( N , s ) f k ( s ) d s = − 1 2 π i ∫ L k , m K ( N , s ) f k ( s ) d s + Res s = s k , 0 [ K ( N , s ) f k ( s ) ] + ∑ j = 1 m Res s = s k , j [ K ( N , s ) f k ( s ) ] , (22) -\frac{1}{2\pi i}\oint_C K(N,s)f_k(s)\,ds
=
-\frac{1}{2\pi i}\int_{L_{k,m}} K(N,s)f_k(s)\,ds
+\mathop{\operatorname{Res}}_{s=s_{k,0}}\left[K(N,s)f_k(s)\right]
+\sum_{j=1}^{m}\mathop{\operatorname{Res}}_{s=s_{k,j}}\left[K(N,s)f_k(s)\right], \tag*{(22)} − 2 π i 1 ∮ C K ( N , s ) f k ( s ) d s = − 2 π i 1 ∫ L k , m K ( N , s ) f k ( s ) d s + Res s = s k , 0 [ K ( N , s ) f k ( s ) ] + j = 1 ∑ m Res s = s k , j [ K ( N , s ) f k ( s ) ] , (22)
where L k , m = c k , m + i R L_{k,m}=c_{k,m}+i\mathbb{R} L k , m = c k , m + i R , for each m ≥ 0 m\ge0 m ≥ 0 .
We handle the first residue at s = s k , 0 s=s_{k,0} s = s k , 0 explicitly, since this yields the term a ( k ) a(k) a ( k ) . Since K ( N , s ) K(N,s) K ( N , s ) is analytic for Re ( s ) = 1 − k \operatorname{Re}(s)=1-k Re ( s ) = 1 − k , write
Res s = s k , 0 [ K ( N , s ) f k ( s ) ] = K ( N , s k , 0 ) Res s = s k , 0 f k ( s ) \mathop{\operatorname{Res}}_{s=s_{k,0}}\left[K(N,s)f_k(s)\right]
=
K(N,s_{k,0})\mathop{\operatorname{Res}}_{s=s_{k,0}}f_k(s) Res s = s k , 0 [ K ( N , s ) f k ( s ) ] = K ( N , s k , 0 ) Res s = s k , 0 f k ( s )
where
K ( N , s k , 0 ) = N ! ( k − 2 ) ! ( N + k − 1 ) ! = 1 ( k − 1 ) ( N + k − 1 k − 1 ) . K(N,s_{k,0})=\frac{N!(k-2)!}{(N+k-1)!}
=\frac{1}{(k-1)\binom{N+k-1}{k-1}}. K ( N , s k , 0 ) = ( N + k − 1 )! N ! ( k − 2 )! = ( k − 1 ) ( k − 1 N + k − 1 ) 1 .
From the Taylor series of ψ ( k + s ) \psi(k+s) ψ ( k + s ) about s k , 0 s_{k,0} s k , 0 and writing u = s − s k , 0 u=s-s_{k,0} u = s − s k , 0 ,
f k ( s ) = [ ψ ( k + s ) − ψ ( 1 ) ] − 1 = 1 ψ ′ ( 1 ) u [ 1 − ψ ′ ′ ( 1 ) 2 ψ ′ ( 1 ) u + O ( u 2 ) ] . f_k(s)=\left[\psi(k+s)-\psi(1)\right]^{-1}
=\frac{1}{\psi'(1)u}\left[1-\frac{\psi''(1)}{2\psi'(1)}u+O\left(u^2\right)\right]. f k ( s ) = [ ψ ( k + s ) − ψ ( 1 ) ] − 1 = ψ ′ ( 1 ) u 1 [ 1 − 2 ψ ′ ( 1 ) ψ ′′ ( 1 ) u + O ( u 2 ) ] .
And, of course, ψ ′ ( 1 ) = ζ ( 2 ) \psi'(1)=\zeta(2) ψ ′ ( 1 ) = ζ ( 2 ) . That is,
Res s = s k , 0 [ K ( N , s ) f k ( s ) ] = 1 ζ ( 2 ) ( k − 1 ) 1 ( N + k − 1 k − 1 ) . \operatorname{Res}_{s=s_{k,0}}[K(N,s)f_k(s)] = \frac{1}{\zeta(2)(k-1)}\frac{1}{\binom{N+k-1}{k-1}}. Res s = s k , 0 [ K ( N , s ) f k ( s )] = ζ ( 2 ) ( k − 1 ) 1 ( k − 1 N + k − 1 ) 1 .
For s = s k , j s=s_{k,j} s = s k , j , j ≥ 1 j\ge1 j ≥ 1 , K ( N , s ) K(N,s) K ( N , s ) is again analytic, and we have
Res s = s k , j [ K ( N , s ) f k ( s ) ] = K ( N , s k , j ) Res s = s k , j [ f k ( s ) ] = Γ ( N + 1 ) Γ ( k + ∣ s j ∣ ) Γ ( N + k + 1 + ∣ s j ∣ ) ψ ′ ( s j ) . \operatorname{Res}_{s=s_{k,j}}[K(N,s)f_k(s)] = K(N,s_{k,j})\operatorname{Res}_{s=s_{k,j}}[f_k(s)] = \frac{\Gamma(N+1)\Gamma(k+|s_j|)}{\Gamma(N+k+1+|s_j|)\psi'(s_j)}. Res s = s k , j [ K ( N , s ) f k ( s )] = K ( N , s k , j ) Res s = s k , j [ f k ( s )] = Γ ( N + k + 1 + ∣ s j ∣ ) ψ ′ ( s j ) Γ ( N + 1 ) Γ ( k + ∣ s j ∣ ) .
Substituting these values into (22) yields (18) .
Without yet checking that this results in a valid asymptotic expansion, the above work suggests the expansion
− 1 2 π i ∮ C K ( N , s ) f k ( s ) d s ∼ 1 ζ ( 2 ) ( k − 1 ) 1 ( N + k − 1 k − 1 ) + ∑ j = 1 ∞ Γ ( n − k + 1 ) Γ ( k + ∣ s j ∣ ) Γ ( n + 1 + ∣ s j ∣ ) ψ ′ ( s j ) . (23) -\frac{1}{2\pi i}\oint_{\mathcal{C}}K(N,s)f_k(s)\,ds\sim\frac{1}{\zeta(2)(k-1)}\frac{1}{\binom{N+k-1}{k-1}}+\sum_{j=1}^{\infty}\frac{\Gamma(n-k+1)\Gamma(k+|s_j|)}{\Gamma(n+1+|s_j|)\psi'(s_j)}. \tag*{(23)} − 2 π i 1 ∮ C K ( N , s ) f k ( s ) d s ∼ ζ ( 2 ) ( k − 1 ) 1 ( k − 1 N + k − 1 ) 1 + j = 1 ∑ ∞ Γ ( n + 1 + ∣ s j ∣ ) ψ ′ ( s j ) Γ ( n − k + 1 ) Γ ( k + ∣ s j ∣ ) . (23)
Then, substituting this expression into (14) and writing the coefficient as H k − 1 ( n − 1 k − 1 ) − 1 = H k − 1 ( N + k − 1 k − 1 ) − 1 H_{k-1}\binom{n-1}{k-1}^{-1}=H_{k-1}\binom{N+k-1}{k-1}^{-1} H k − 1 ( k − 1 n − 1 ) − 1 = H k − 1 ( k − 1 N + k − 1 ) − 1 for the first term and H k − 1 ( n − 1 k − 1 ) − 1 = H k − 1 Γ ( n ) / Γ ( k ) Γ ( n − k + 1 ) H_{k-1}\binom{n-1}{k-1}^{-1}=H_{k-1}\Gamma(n)/\Gamma(k)\Gamma(n-k+1) H k − 1 ( k − 1 n − 1 ) − 1 = H k − 1 Γ ( n ) /Γ ( k ) Γ ( n − k + 1 ) for the sum gives (7) .
To check that (7) is an asymptotic expansion, consider its the truncation at m m m terms:
a ( n , k ) − a ( k ) = H k − 1 ( n − 1 k − 1 ) ⋅ − 1 2 π i ∫ L k , m K ( N , s ) f k ( s ) d s + ∑ i = 1 m H k − 1 Γ ( k + ∣ s i ∣ ) Γ ( k ) ψ ′ ( s i ) Γ ( n ) Γ ( n + 1 + ∣ s i ∣ ) . (24) \begin{aligned}
a(n,k)-a(k)=H_{k-1}\binom{n-1}{k-1}\cdot\frac{-1}{2\pi i}\int_{L_{k,m}}K(N,s)f_k(s)\,ds \\
&+\sum_{i=1}^{m}\frac{H_{k-1}\Gamma(k+|s_i|)}{\Gamma(k)\psi'(s_i)}\frac{\Gamma(n)}{\Gamma(n+1+|s_i|)}. \tag*{(24)}
\end{aligned} a ( n , k ) − a ( k ) = H k − 1 ( k − 1 n − 1 ) ⋅ 2 π i − 1 ∫ L k , m K ( N , s ) f k ( s ) d s + i = 1 ∑ m Γ ( k ) ψ ′ ( s i ) H k − 1 Γ ( k + ∣ s i ∣ ) Γ ( n + 1 + ∣ s i ∣ ) Γ ( n ) . (24)
Note that each term in the sum is O ( ln ( k ) k ∣ s i ∣ n − ∣ s i ∣ − 1 ) O(\ln(k)k^{|s_i|}n^{-|s_i|-1}) O ( ln ( k ) k ∣ s i ∣ n − ∣ s i ∣ − 1 ) , and for k ∈ o ( n ) k\in o(\sqrt{n}) k ∈ o ( n ) , this is O ( ln ( n ) n − ∣ s i ∣ / 2 − 1 ) O(\ln(n)n^{-|s_i|/2-1}) O ( ln ( n ) n − ∣ s i ∣/2 − 1 ) . Write s = c k , m + i y s=c_{k,m}+iy s = c k , m + i y and recall c k , m = − ∣ s k , m + 1 ∣ + ϵ m = − ∣ s m + 1 ∣ − k + ϵ m c_{k,m}=-|s_{k,m+1}|+\epsilon_m=-|s_{m+1}|-k+\epsilon_m c k , m = − ∣ s k , m + 1 ∣ + ϵ m = − ∣ s m + 1 ∣ − k + ϵ m , for some small ϵ m > 0 \epsilon_m>0 ϵ m > 0 . As ∣ y ∣ → ∞ |y|\to\infty ∣ y ∣ → ∞ , for s ∈ L k , m s\in L_{k,m} s ∈ L k , m ,
∣ K ( N , s ) ∣ = N ! ∏ j = 0 N ∣ j − s ∣ = K ( N , c k , m ) ∏ j = 0 N [ 1 + y 2 ( j − c k , m ) 2 ] − 1 / 2 ≤ K ( N , c k , m ) ( 1 + y 2 c k , m 2 ) ( 1 + y 2 ( 1 − c k , m ) 2 ) − 1 / 2 , \begin{aligned}
|K(N,s)|=\frac{N!}{\prod_{j=0}^{N}|j-s|}=K(N,c_{k,m})\prod_{j=0}^{N}\left[1+\frac{y^2}{(j-c_{k,m})^2}\right]^{-1/2} \\
&\le K(N,c_{k,m})\left(1+\frac{y^2}{c_{k,m}^2}\right)\left(1+\frac{y^2}{(1-c_{k,m})^2}\right)^{-1/2},
\end{aligned} ∣ K ( N , s ) ∣ = ∏ j = 0 N ∣ j − s ∣ N ! = K ( N , c k , m ) j = 0 ∏ N [ 1 + ( j − c k , m ) 2 y 2 ] − 1/2 ≤ K ( N , c k , m ) ( 1 + c k , m 2 y 2 ) ( 1 + ( 1 − c k , m ) 2 y 2 ) − 1/2 ,
where in the final line we used that each term in the product is less than one. Now, notice that as k ≥ 2 k\ge2 k ≥ 2 , c k , m = − ∣ s m + 1 ∣ − k + ϵ m ≤ − 2 c_{k,m}=-|s_{m+1}|-k+\epsilon_m\le-2 c k , m = − ∣ s m + 1 ∣ − k + ϵ m ≤ − 2 , and in turn, c k , m 2 ( 1 − c k , m ) 2 > 1 c_{k,m}^2(1-c_{k,m})^2>1 c k , m 2 ( 1 − c k , m ) 2 > 1 . It follows
( 1 + y 2 c k , m 2 ) ( 1 + y 2 ( 1 − c k , m ) 2 ) = 1 + y 2 c k , m 2 + ( 1 − c k , m ) 2 c k , m 2 ( 1 − c k , m ) 2 + y 4 1 c k , m 2 ( 1 − c k , m ) 2 \left(1+\frac{y^2}{c_{k,m}^2}\right)\left(1+\frac{y^2}{(1-c_{k,m})^2}\right)=1+y^2\frac{c_{k,m}^2+(1-c_{k,m})^2}{c_{k,m}^2(1-c_{k,m})^2}+y^4\frac{1}{c_{k,m}^2(1-c_{k,m})^2} ( 1 + c k , m 2 y 2 ) ( 1 + ( 1 − c k , m ) 2 y 2 ) = 1 + y 2 c k , m 2 ( 1 − c k , m ) 2 c k , m 2 + ( 1 − c k , m ) 2 + y 4 c k , m 2 ( 1 − c k , m ) 2 1
≥ 1 + y 2 2 c k , m ( 1 − c k , m ) + y 4 1 c k , m 2 ( 1 − c k , m ) 2 = [ 1 + y 2 c k , m ( 1 − c k , m ) ] 2 , \begin{aligned}
\ge1+y^2\frac{2}{c_{k,m}(1-c_{k,m})}+y^4\frac{1}{c_{k,m}^2(1-c_{k,m})^2} \\
&=\left[1+\frac{y^2}{c_{k,m}(1-c_{k,m})}\right]^2,
\end{aligned} ≥ 1 + y 2 c k , m ( 1 − c k , m ) 2 + y 4 c k , m 2 ( 1 − c k , m ) 2 1 = [ 1 + c k , m ( 1 − c k , m ) y 2 ] 2 ,
so
∣ K ( N , s ) ∣ ≤ K ( N , c k , m ) [ 1 + y 2 c k , m ( 1 − c k , m ) ] − 1 . |K(N,s)|\le K(N,c_{k,m})\left[1+\frac{y^2}{c_{k,m}(1-c_{k,m})}\right]^{-1}. ∣ K ( N , s ) ∣ ≤ K ( N , c k , m ) [ 1 + c k , m ( 1 − c k , m ) y 2 ] − 1 .
Note that, as f k f_k f k is bounded nearby c k , m c_{k,m} c k , m on L k , m L_{k,m} L k , m and f k ( s ) ∼ ln − 1 ∣ y ∣ f_k(s) \sim\ln^{-1}|y| f k ( s ) ∼ ln − 1 ∣ y ∣ as ∣ y ∣ → ∞ |y| \to\infty ∣ y ∣ → ∞ , f k f_k f k is bounded on L k , m L_{k,m} L k , m . So, for some C > 0 C > 0 C > 0 , we have
∫ L k , m ∣ K ( N , s ) f k ( s ) ∣ d s ≤ K ( N , c k , m ) ∫ − ∞ ∞ [ 1 + y 2 c k , m ( 1 − c k , m ) ] − 1 d y . (25) \int_{L_{k,m}} |K(N,s)f_k(s)|\,ds \leq K(N,c_{k,m}) \int_{-\infty}^{\infty} \left[1+\frac{y^2}{c_{k,m}(1-c_{k,m})}\right]^{-1}\,dy . \tag*{(25)} ∫ L k , m ∣ K ( N , s ) f k ( s ) ∣ d s ≤ K ( N , c k , m ) ∫ − ∞ ∞ [ 1 + c k , m ( 1 − c k , m ) y 2 ] − 1 d y . (25)
The integral here evaluates as
∫ − ∞ ∞ [ 1 + y 2 c k , m ( 1 − c k , m ) ] − 1 d y = π c k , m ( 1 − c k , m ) = O ( k ) . (26) \int_{-\infty}^{\infty} \left[1+\frac{y^2}{c_{k,m}(1-c_{k,m})}\right]^{-1}\,dy = \pi\sqrt{c_{k,m}(1-c_{k,m})}=O(k). \tag*{(26)} ∫ − ∞ ∞ [ 1 + c k , m ( 1 − c k , m ) y 2 ] − 1 d y = π c k , m ( 1 − c k , m ) = O ( k ) . (26)
Lemma 3.3. As n , k → ∞ n,k \to\infty n , k → ∞ ,
H k − 1 ( n − 1 k − 1 ) ⋅ K ( N , c k , m ) = O ( ( ln ( k ) ) k ∣ s m + 1 ∣ − ϵ m n − ∣ s m + 1 ∣ − 1 + ϵ m ) . (27) H_{k-1}\binom{n-1}{k-1}\cdot K(N,c_{k,m})=O\left((\ln(k))k^{|s_{m+1}|-\epsilon_m}n^{-|s_{m+1}|-1+\epsilon_m}\right). \tag*{(27)} H k − 1 ( k − 1 n − 1 ) ⋅ K ( N , c k , m ) = O ( ( ln ( k )) k ∣ s m + 1 ∣ − ϵ m n − ∣ s m + 1 ∣ − 1 + ϵ m ) . (27) Proof. We use Stirling’s approximation to handle the ratio of Gamma functions, which states Γ ( s ) = 2 π s s − 1 / 2 e − s [ 1 + O ( s − 1 ) ] \Gamma(s)=\sqrt{2\pi}s^{s-1/2}e^{-s}[1+O(s^{-1})] Γ ( s ) = 2 π s s − 1/2 e − s [ 1 + O ( s − 1 )] uniformly for ∣ s ∣ ≥ r 0 > 0 |s|\geq r_0>0 ∣ s ∣ ≥ r 0 > 0 and ∣ arg ( s ) ∣ ≤ π − δ 0 |\arg(s)|\leq\pi-\delta_0 ∣ arg ( s ) ∣ ≤ π − δ 0 for fixed r 0 r_0 r 0 and δ 0 > 0 \delta_0>0 δ 0 > 0 (e.g., see [19 Chapter XIII] ) For s = c k , m s=c_{k,m} s = c k , m , this yields
Γ ( N + 1 ) Γ ( N + 1 − c k , m ) ∼ ( N + 1 ) c k , m e − c k , m ( 1 − c k , m N + 1 ) N + 1 / 2 − c k , m . \frac{\Gamma(N+1)}{\Gamma(N+1-c_{k,m})}\sim(N+1)^{c_{k,m}}e^{-c_{k,m}}\left(1-\frac{c_{k,m}}{N+1}\right)^{N+1/2-c_{k,m}}. Γ ( N + 1 − c k , m ) Γ ( N + 1 ) ∼ ( N + 1 ) c k , m e − c k , m ( 1 − N + 1 c k , m ) N + 1/2 − c k , m . For large n n n , using the series expansion − ln ( 1 + x ) = x + O ( x 2 ) -\ln(1+x)=x+O(x^2) − ln ( 1 + x ) = x + O ( x 2 ) , valid for ∣ x ∣ < 1 |x|<1 ∣ x ∣ < 1 , and writing N + 1 / 2 − c k , m = N + 1 − c k , m − 1 / 2 N+1/2-c_{k,m}=N+1-c_{k,m}-1/2 N + 1/2 − c k , m = N + 1 − c k , m − 1/2 ,
( 1 − c k , m N + 1 ) N + 1 / 2 − c k , m = exp { − ( N + 1 − c k , m − 1 / 2 ) ln ( 1 − c k , m N + 1 ) } = exp { ( N + 1 − c k , m − 1 / 2 ) ( c k , m N + 1 + O ( c k , m 2 N 2 ) ) } = exp { c k , m + o ( 1 ) } . \begin{aligned}
\left(1-\frac{c_{k,m}}{N+1}\right)^{N+1/2-c_{k,m}}
&=\exp\left\{-(N+1-c_{k,m}-1/2)\ln\left(1-\frac{c_{k,m}}{N+1}\right)\right\}\\
&=\exp\left\{(N+1-c_{k,m}-1/2)\left(\frac{c_{k,m}}{N+1}+O\left(\frac{c_{k,m}^2}{N^2}\right)\right)\right\}\\
&=\exp\{c_{k,m}+o(1)\}.
\end{aligned} ( 1 − N + 1 c k , m ) N + 1/2 − c k , m = exp { − ( N + 1 − c k , m − 1/2 ) ln ( 1 − N + 1 c k , m ) } = exp { ( N + 1 − c k , m − 1/2 ) ( N + 1 c k , m + O ( N 2 c k , m 2 ) ) } = exp { c k , m + o ( 1 )} . (Note that this step requires k ∈ o ( n ) k\in o(\sqrt{n}) k ∈ o ( n ) .) Substituting this into the previous expression and noting ( N + 1 ) c k , m ∼ n c k , m (N+1)^{c_{k,m}}\sim n^{c_{k,m}} ( N + 1 ) c k , m ∼ n c k , m , we have
Γ ( N + 1 ) Γ ( N + 1 − c k , m ) ∼ n c k , m = n − ∣ s m + 1 ∣ − k + ϵ m . (28) \frac{\Gamma(N+1)}{\Gamma(N+1-c_{k,m})}\sim n^{c_{k,m}}=n^{-|s_{m+1}|-k+\epsilon_m}. \tag*{(28)} Γ ( N + 1 − c k , m ) Γ ( N + 1 ) ∼ n c k , m = n − ∣ s m + 1 ∣ − k + ϵ m . (28) It similarly follows that
∣ Γ ( − c k , m ) ∣ ∼ 2 π k k − 1 / 2 + ∣ s m + 1 ∣ − ϵ m e − k − ∣ s m + 1 ∣ + ϵ m , |\Gamma(-c_{k,m})|\sim\sqrt{2\pi}k^{k-1/2+|s_{m+1}|-\epsilon_m}e^{-k-|s_{m+1}|+\epsilon_m}, ∣Γ ( − c k , m ) ∣ ∼ 2 π k k − 1/2 + ∣ s m + 1 ∣ − ϵ m e − k − ∣ s m + 1 ∣ + ϵ m , and
( n − 1 k − 1 ) ∼ 1 2 π n k − 1 e k − 1 k − k + 1 / 2 . \binom{n-1}{k-1}\sim\frac{1}{\sqrt{2\pi}}n^{k-1}e^{k-1}k^{-k+1/2}. ( k − 1 n − 1 ) ∼ 2 π 1 n k − 1 e k − 1 k − k + 1/2 . Together, these estimates give (27) .
Lastly, we combine (26) with (27) and (25) to get
H k − 1 ( n − 1 k − 1 ) ⋅ − 1 2 π i ∫ L k , m K ( N , s ) f k ( s ) d s = O ( ( ln ( k ) ) k ∣ s m + 1 ∣ + 1 − ϵ m n − ∣ s m + 1 ∣ − 1 + ϵ m ) . H_{k-1}\binom{n-1}{k-1}\cdot\frac{-1}{2\pi i}\int_{L_{k,m}}K(N,s)f_k(s)\,ds=O\left((\ln(k))k^{|s_{m+1}|+1-\epsilon_m}n^{-|s_{m+1}|-1+\epsilon_m}\right). H k − 1 ( k − 1 n − 1 ) ⋅ 2 π i − 1 ∫ L k , m K ( N , s ) f k ( s ) d s = O ( ( ln ( k )) k ∣ s m + 1 ∣ + 1 − ϵ m n − ∣ s m + 1 ∣ − 1 + ϵ m ) . Since
k ∣ s m + 1 ∣ + 1 − ϵ m n − ∣ s m + 1 ∣ − 1 + ϵ m = k ∣ s m ∣ n − ∣ s m ∣ − 1 ⋅ o ( n ( ∣ s m ∣ − ∣ s m + 1 ∣ + ϵ m + 1 ) / 2 ) , k^{|s_{m+1}|+1-\epsilon_m}n^{-|s_{m+1}|-1+\epsilon_m}=k^{|s_m|}n^{-|s_m|-1}\cdot o\left(n^{(|s_m|-|s_{m+1}|+\epsilon_m+1)/2}\right), k ∣ s m + 1 ∣ + 1 − ϵ m n − ∣ s m + 1 ∣ − 1 + ϵ m = k ∣ s m ∣ n − ∣ s m ∣ − 1 ⋅ o ( n ( ∣ s m ∣ − ∣ s m + 1 ∣ + ϵ m + 1 ) /2 ) , the result follows from ∣ s m + 1 ∣ > ∣ s m ∣ + 1 + ϵ m |s_{m+1}|>|s_m|+1+\epsilon_m ∣ s m + 1 ∣ > ∣ s m ∣ + 1 + ϵ m , which was shown in Lemma 3.1 .
Proof of Theorem 2.1 (2.2)–(2.3). To obtain (2.2), we have the following expansion for the ratio Γ ( n ) / Γ ( n + 1 + ∣ s i ∣ ) \Gamma(n)/\Gamma(n+1+|s_i|) Γ ( n ) /Γ ( n + 1 + ∣ s i ∣ ) [10 eqn. (12)] :
Γ ( n ) Γ ( n + 1 + ∣ s i ∣ ) ∼ ∑ j = 0 ∞ C i , j n − ∣ s i ∣ − 1 − j \frac{\Gamma(n)}{\Gamma(n+1+|s_i|)} \sim\sum_{j=0}^{\infty} C_{i,j}n^{-|s_i|-1-j} Γ ( n + 1 + ∣ s i ∣ ) Γ ( n ) ∼ j = 0 ∑ ∞ C i , j n − ∣ s i ∣ − 1 − j
where the coefficients C i , j C_{i,j} C i , j are given in [10 ] . Substituting this into (2.1) yields
a ( n , k ) − a ( k ) ∼ ∑ i = 1 ∞ ∑ j = 1 ∞ c i , j ( k ) n − ∣ s i ∣ − j , a(n,k)-a(k) \sim\sum_{i=1}^{\infty}\sum_{j=1}^{\infty} c_{i,j}(k)n^{-|s_i|-j}, a ( n , k ) − a ( k ) ∼ i = 1 ∑ ∞ j = 1 ∑ ∞ c i , j ( k ) n − ∣ s i ∣ − j ,
where
c i , j ( k ) : = H k − 1 Γ ( k + ∣ s i ∣ ) Γ ( k ) ψ ′ ( s i ) C i , j − 1 . c_{i,j}(k):=\frac{H_{k-1}\Gamma(k+|s_i|)}{\Gamma(k)\psi'(s_i)}C_{i,j-1}. c i , j ( k ) := Γ ( k ) ψ ′ ( s i ) H k − 1 Γ ( k + ∣ s i ∣ ) C i , j − 1 .
Lastly, (2.3) follows from the definition of c i , j ( k ) c_{i,j}(k) c i , j ( k ) , and in particular that C i , 0 = 1 C_{i,0}=1 C i , 0 = 1 , and noticing that s 1 = − 0.567 … s_1=-0.567\ldots s 1 = − 0.567 … and s 2 = − 1.628 … s_2=-1.628\ldots s 2 = − 1.628 … , so that − ∣ s 1 ∣ − 2 > − ∣ s 2 ∣ − 1 -|s_1|-2>-|s_2|-1 − ∣ s 1 ∣ − 2 > − ∣ s 2 ∣ − 1 and the remainder term is O ( n − ∣ s 1 ∣ − 2 ) O(n^{-|s_1|-2}) O ( n − ∣ s 1 ∣ − 2 ) .
Proof of Theorem 2.2 and Corollary 2.3
The next result is analogous to [8 Proposition 1.2] and may be considered an extension of it. The proof will be broadly similar and borrow many of its techniques.
Lemma 4.1. Consider the sequence ( x i ) i = 1 ∞ (x_i)_{i=1}^{\infty} ( x i ) i = 1 ∞ with x 1 , … , x k − 1 , x k + 1 , … , x M = 0 x_1,\ldots,x_{k-1},x_{k+1},\ldots,x_M=0 x 1 , … , x k − 1 , x k + 1 , … , x M = 0 and x k > 0 x_k>0 x k > 0 for 1 ≤ k ≤ M 1\le k\le M 1 ≤ k ≤ M , and
x n = ∑ i = 1 n − 1 p ( n , i ) x i for n > M , (29) x_n=\sum_{i=1}^{n-1}p(n,i)x_i\quad\text{for }n>M, \tag*{(29)} x n = i = 1 ∑ n − 1 p ( n , i ) x i for n > M , (29) and define s ( n , i ) : = ∑ j = 1 i p ( n , j ) s(n,i):=\sum_{j=1}^{i}p(n,j) s ( n , i ) := ∑ j = 1 i p ( n , j ) and
α i , n : = s ( n + 1 , i ) s ( n + 1 , M ) − s ( n , i ) s ( n , M ) . (30) \alpha_{i,n}:=\frac{s(n+1,i)}{s(n+1,M)}-\frac{s(n,i)}{s(n,M)}. \tag*{(30)} α i , n := s ( n + 1 , M ) s ( n + 1 , i ) − s ( n , M ) s ( n , i ) . (30) Further suppose
(i) p ( n , i ) > 0 p(n,i)>0 p ( n , i ) > 0 and ∑ i = 1 n − 1 p ( n , i ) = 1 \sum_{i=1}^{n-1}p(n,i)=1 ∑ i = 1 n − 1 p ( n , i ) = 1 ;
(ii) p ( n , i ) / p ( n + 1 , i ) p(n,i)/p(n+1,i) p ( n , i ) / p ( n + 1 , i ) is non-decreasing in i i i for every n n n ;
(iii) for every n n n , α i , n / α i , n + 1 ≥ α j , n / α j , n + 1 \alpha_{i,n}/\alpha_{i,n+1}\ge\alpha_{j,n}/\alpha_{j,n+1} α i , n / α i , n + 1 ≥ α j , n / α j , n + 1 whenever i ≥ j i\ge j i ≥ j , for i , j ≠ M i,j\ne M i , j = M .
Then either x n x_n x n is monotone increasing for all n > M n>M n > M , or there exists N ≥ M N\ge M N ≥ M such that x n x_n x n is monotone increasing for M < n ≤ N M<n\le N M < n ≤ N and strictly monotone decreasing for n > M n>M n > M ; in particular, the limit x : = lim n → ∞ x n x:=\lim_{n\to\infty}x_n x := lim n → ∞ x n exists.
Proof. For M ≥ 2 M\ge2 M ≥ 2 , we will assume that k < M k<M k < M , since the case k = M k=M k = M is simply the original result by Brandenberger et al. [8 ] .
First suppose M , k ≥ 2 M,k\ge2 M , k ≥ 2 and k < M k<M k < M . Summation by parts yields
0 = x n − x n − 1 + ∑ i = 1 n − 2 s ( n , i ) ( x i + 1 − x i ) . 0=x_n-x_{n-1}+\sum_{i=1}^{n-2}s(n,i)(x_{i+1}-x_i). 0 = x n − x n − 1 + i = 1 ∑ n − 2 s ( n , i ) ( x i + 1 − x i ) .
Separating the i = k − 1 i=k-1 i = k − 1 , k k k , and M M M terms, we have
0 = ( x n − x n − 1 ) 1 s ( n , M ) + ∑ i = M + 1 n − 2 ( x i + 1 − x i ) s ( n , i ) s ( n , M ) + ( x M + 1 − x M ) + ( x k − x k − 1 ) s ( n , k − 1 ) s ( n , M ) + ( x k + 1 − x k ) s ( n , k ) s ( n , M ) 0=(x_n-x_{n-1})\frac{1}{s(n,M)}+\sum_{i=M+1}^{n-2}(x_{i+1}-x_i)\frac{s(n,i)}{s(n,M)}+(x_{M+1}-x_M)
+(x_k-x_{k-1})\frac{s(n,k-1)}{s(n,M)}+(x_{k+1}-x_k)\frac{s(n,k)}{s(n,M)} 0 = ( x n − x n − 1 ) s ( n , M ) 1 + i = M + 1 ∑ n − 2 ( x i + 1 − x i ) s ( n , M ) s ( n , i ) + ( x M + 1 − x M ) + ( x k − x k − 1 ) s ( n , M ) s ( n , k − 1 ) + ( x k + 1 − x k ) s ( n , M ) s ( n , k )
for n > M + 1 n>M+1 n > M + 1 and
0 = ( x n + 1 − x n ) 1 s ( n + 1 , M ) + ∑ i = M + 1 n − 1 ( x i + 1 − x i ) s ( n + 1 , i ) s ( n + 1 , M ) + ( x M + 1 − x M ) + ( x k − x k − 1 ) s ( n + 1 , k − 1 ) s ( n + 1 , M ) + ( x k + 1 − x k ) s ( n + 1 , k ) s ( n + 1 , M ) 0=(x_{n+1}-x_n)\frac{1}{s(n+1,M)}+\sum_{i=M+1}^{n-1}(x_{i+1}-x_i)\frac{s(n+1,i)}{s(n+1,M)}+(x_{M+1}-x_M)
+(x_k-x_{k-1})\frac{s(n+1,k-1)}{s(n+1,M)}+(x_{k+1}-x_k)\frac{s(n+1,k)}{s(n+1,M)} 0 = ( x n + 1 − x n ) s ( n + 1 , M ) 1 + i = M + 1 ∑ n − 1 ( x i + 1 − x i ) s ( n + 1 , M ) s ( n + 1 , i ) + ( x M + 1 − x M ) + ( x k − x k − 1 ) s ( n + 1 , M ) s ( n + 1 , k − 1 ) + ( x k + 1 − x k ) s ( n + 1 , M ) s ( n + 1 , k )
for n ≥ M + 1 n\ge M+1 n ≥ M + 1 . Subtracting the first expression from the second, we obtain
0 = ( x n + 1 − x n ) 1 s ( n + 1 , M ) − ∑ i = M + 1 n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ + x k ( α k − 1 , n − α k , n ) . (31) 0=(x_{n+1}-x_n)\frac{1}{s(n+1,M)}-\sum_{i=M+1}^{n-1}(x_{i+1}-x_i)|\alpha_{i,n}|+x_k(\alpha_{k-1,n}-\alpha_{k,n}). \tag*{(31)} 0 = ( x n + 1 − x n ) s ( n + 1 , M ) 1 − i = M + 1 ∑ n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ + x k ( α k − 1 , n − α k , n ) . (31)
Note α i , n < 0 \alpha_{i,n}<0 α i , n < 0 for i > M i>M i > M as shown in [8 ] following from assumption (ii). We find by similar reasoning that α i , n > 0 \alpha_{i,n}>0 α i , n > 0 for i < M i<M i < M .
Since x k > 0 x_k>0 x k > 0 and p ( n , i ) > 0 p(n,i)>0 p ( n , i ) > 0 by assumption, it is easy to see from (29) that x n > 0 x_n>0 x n > 0 for all n > M n>M n > M . Similarly, suppose x i ≤ C x_i\le C x i ≤ C for all i < n i<n i < n and some C > 0 C>0 C > 0 . Then
x n ≤ C ∑ i = 1 n − 1 p ( n , i ) = C , x_n\le C\sum_{i=1}^{n-1}p(n,i)=C, x n ≤ C i = 1 ∑ n − 1 p ( n , i ) = C ,
so x n ≤ x k x_n\le x_k x n ≤ x k for all n n n by induction. Since the sequence is bounded above and below, we need only show that the tail of the sequence is monotone in order to conclude convergence.
We can study the behavior of the sequence by splitting over cases depending on the sign of x k ( α k − 1 , n − α k , n ) x_k(\alpha_{k-1,n}-\alpha_{k,n}) x k ( α k − 1 , n − α k , n ) at step n = M + 1 n=M+1 n = M + 1 :
Case 1 (α k − 1 , M + 1 − α k , M + 1 = 0 \alpha_{k-1,M+1}-\alpha_{k,M+1}=0 α k − 1 , M + 1 − α k , M + 1 = 0 ). Note that in this case, x M + 2 − x M + 1 = 0 x_{M+2}-x_{M+1}=0 x M + 2 − x M + 1 = 0 as well, and the recursion takes the form
0 = ( x n + 1 − x n ) 1 s ( n + 1 , M ) − ∑ i = M + 2 n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ + x k ( α k − 1 , n − α k , n ) 0=(x_{n+1}-x_n)\frac{1}{s(n+1,M)}-\sum_{i=M+2}^{n-1}(x_{i+1}-x_i)|\alpha_{i,n}|+x_k(\alpha_{k-1,n}-\alpha_{k,n}) 0 = ( x n + 1 − x n ) s ( n + 1 , M ) 1 − i = M + 2 ∑ n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ + x k ( α k − 1 , n − α k , n )
for n ≥ M + 2 n\ge M+2 n ≥ M + 2 . One can compute from (29) that the first non-zero term after n = k n=k n = k is x M + 1 = p ( M + 1 , k ) x k x_{M+1}=p(M+1,k)x_k x M + 1 = p ( M + 1 , k ) x k . If α k − 1 , n − α k , n = 0 \alpha_{k-1,n}-\alpha_{k,n}=0 α k − 1 , n − α k , n = 0 for all n ≥ M + 2 n\ge M+2 n ≥ M + 2 , then by induction all the differences are zero, and x n = p ( M + 1 , k ) x k x_n=p(M+1,k)x_k x n = p ( M + 1 , k ) x k for all n ≥ M + 1 n\ge M+1 n ≥ M + 1 . Otherwise, α k − 1 , n − α k , n ≠ 0 \alpha_{k-1,n}-\alpha_{k,n}\ne0 α k − 1 , n − α k , n = 0 at some step N N N , at which point
0 = ( x n + 1 − x n ) 1 s ( n + 1 , M ) − ∑ i = N n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ + x k ( α k − 1 , n − α k , n ) 0=(x_{n+1}-x_n)\frac{1}{s(n+1,M)}-\sum_{i=N}^{n-1}(x_{i+1}-x_i)|\alpha_{i,n}|+x_k(\alpha_{k-1,n}-\alpha_{k,n}) 0 = ( x n + 1 − x n ) s ( n + 1 , M ) 1 − i = N ∑ n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ + x k ( α k − 1 , n − α k , n )
for i ≥ N i\ge N i ≥ N , and the subsequent terms are handled under case 2, since by assumption (iii), if α i , n − α j , n ≥ 0 \alpha_{i,n}-\alpha_{j,n}\ge0 α i , n − α j , n ≥ 0 for i < j i<j i < j and i , j ≠ M i,j\ne M i , j = M , then
α i , n + 1 − α j , n + 1 = α i , n α i , n + 1 α i , n − α j , n α j , n + 1 α j , n ≥ 0. \alpha_{i,n+1}-\alpha_{j,n+1}
=\alpha_{i,n}\frac{\alpha_{i,n+1}}{\alpha_{i,n}}
-\alpha_{j,n}\frac{\alpha_{j,n+1}}{\alpha_{j,n}}
\ge0. α i , n + 1 − α j , n + 1 = α i , n α i , n α i , n + 1 − α j , n α j , n α j , n + 1 ≥ 0.
In particular, if α k − 1 , n − α k , n ≥ 0 \alpha_{k-1,n}-\alpha_{k,n}\ge0 α k − 1 , n − α k , n ≥ 0 , then α k − 1 , n + 1 − α k , n + 1 ≥ 0 \alpha_{k-1,n+1}-\alpha_{k,n+1}\ge0 α k − 1 , n + 1 − α k , n + 1 ≥ 0 as well, so this first non-zero α k − 1 , n + 1 − α k , n + 1 \alpha_{k-1,n+1}-\alpha_{k,n+1} α k − 1 , n + 1 − α k , n + 1 must, in fact, be positive, and the corresponding difference negative. Case 2 (α k − 1 , M + 1 − α k , M + 1 > 0 \alpha_{k-1,M+1}-\alpha_{k,M+1}>0 α k − 1 , M + 1 − α k , M + 1 > 0 ). Similar to before, by assumption (iii), if α i , n − α j , n > 0 \alpha_{i,n}-\alpha_{j,n}>0 α i , n − α j , n > 0 for i < j i<j i < j and i , j ≠ M i,j\ne M i , j = M , then
α i , n + 1 − α j , n + 1 = α i , n α i , n + 1 α i , n − α j , n α j , n + 1 α j , n > 0. \alpha_{i,n+1}-\alpha_{j,n+1}=\alpha_{i,n}\frac{\alpha_{i,n+1}}{\alpha_{i,n}}-\alpha_{j,n}\frac{\alpha_{j,n+1}}{\alpha_{j,n}}>0. α i , n + 1 − α j , n + 1 = α i , n α i , n α i , n + 1 − α j , n α j , n α j , n + 1 > 0.
In particular, if α k − 1 , n − α k , n > 0 \alpha_{k-1,n}-\alpha_{k,n}>0 α k − 1 , n − α k , n > 0 , then α k − 1 , n + 1 − α k , n + 1 > 0 \alpha_{k-1,n+1}-\alpha_{k,n+1}>0 α k − 1 , n + 1 − α k , n + 1 > 0 as well. It is clear from (31) that x M + 2 − x M + 1 < 0 x_{M+2}-x_{M+1}<0 x M + 2 − x M + 1 < 0 and by induction the remaining differences must be negative as well. The tail of the sequence is strictly monotone decreasing.
Case 3 (α k − 1 , M + 1 − α k , M + 1 < 0 \alpha_{k-1,M+1}-\alpha_{k,M+1}<0 α k − 1 , M + 1 − α k , M + 1 < 0 ). Note that in this case, x M + 2 − x M + 1 > 0 x_{M+2}-x_{M+1}>0 x M + 2 − x M + 1 > 0 . If all subsequent differences are non-negative as well, then the tail of the sequence is monotone increasing. If not, then at some step N N N , x N + 1 − x N < 0 x_{N+1}-x_N<0 x N + 1 − x N < 0 , and
0 = ( x N + 1 − x N ) 1 s ( N + 1 , M ) − ∑ i = M + 1 N − 1 ( x i + 1 − x i ) ∣ α i , N ∣ + x k ( α k − 1 , N − α k , N ) . 0=(x_{N+1}-x_N)\frac{1}{s(N+1,M)}-\sum_{i=M+1}^{N-1}(x_{i+1}-x_i)|\alpha_{i,N}|+x_k(\alpha_{k-1,N}-\alpha_{k,N}). 0 = ( x N + 1 − x N ) s ( N + 1 , M ) 1 − i = M + 1 ∑ N − 1 ( x i + 1 − x i ) ∣ α i , N ∣ + x k ( α k − 1 , N − α k , N ) .
implies x k ( α k − 1 , N − α k , N ) > 0 x_k(\alpha_{k-1,N}-\alpha_{k,N})>0 x k ( α k − 1 , N − α k , N ) > 0 and in turn α k − 1 , N − α k , N > 0 \alpha_{k-1,N}-\alpha_{k,N}>0 α k − 1 , N − α k , N > 0 .
We note two preliminary results regarding α i , n \alpha_{i,n} α i , n which follow from assumption (iii). First, by the induction used in the previous case, α k − 1 , n − α k , n > 0 \alpha_{k-1,n}-\alpha_{k,n}>0 α k − 1 , n − α k , n > 0 for all n ≥ N n\ge N n ≥ N . Second, we find
α k − 1 , n − α k , n α k − 1 , N − α k , N ≥ ∣ α i , n ∣ ∣ α i , N ∣ (32) \frac{\alpha_{k-1,n}-\alpha_{k,n}}{\alpha_{k-1,N}-\alpha_{k,N}}\ge\frac{|\alpha_{i,n}|}{|\alpha_{i,N}|} \tag*{(32)} α k − 1 , N − α k , N α k − 1 , n − α k , n ≥ ∣ α i , N ∣ ∣ α i , n ∣ (32)
for k < M < i k<M<i k < M < i and n > N n>N n > N . In particular, showing the result for n n n and n − 1 n-1 n − 1 , this is equivalent to ∣ α i , n − 1 ∣ ( α k − 1 , n − α k , n ) − ∣ α i , n ∣ ( α k − 1 , n − 1 − α k , n − 1 ) ≥ 0 |\alpha_{i,n-1}|(\alpha_{k-1,n}-\alpha_{k,n})-|\alpha_{i,n}|(\alpha_{k-1,n-1}-\alpha_{k,n-1})\ge0 ∣ α i , n − 1 ∣ ( α k − 1 , n − α k , n ) − ∣ α i , n ∣ ( α k − 1 , n − 1 − α k , n − 1 ) ≥ 0 , and
∣ α i , n − 1 ∣ ( α k − 1 , n − α k , n ) − ∣ α i , n ∣ ( α k − 1 , n − 1 − α k , n − 1 ) = ∣ α i , n ∣ α k , n − 1 − ∣ α i , n − 1 ∣ α k , n + ∣ α i , n − 1 ∣ α k − 1 , n − ∣ α i , n ∣ α k − 1 , n − 1 = ∣ α i , n ∣ α k , n ( α k , n − 1 α k , n − α i , n − 1 α i , n ) + ∣ α i , n ∣ α k , n ( α i , n − 1 α i , n − α k − 1 , n − 1 α k − 1 , n ) = ∣ α i , n ∣ [ ( α k , n − α k − 1 , n ) ( α k , n − 1 α k , n − α i , n − 1 α i , n ) + α k − 1 , n ( α k , n − 1 α k , n − α k − 1 , n − 1 α k − 1 , n ) ] . \begin{aligned}
&|\alpha_{i,n-1}|(\alpha_{k-1,n}-\alpha_{k,n})-|\alpha_{i,n}|(\alpha_{k-1,n-1}-\alpha_{k,n-1})\\
&=|\alpha_{i,n}|\alpha_{k,n-1}-|\alpha_{i,n-1}|\alpha_{k,n}+|\alpha_{i,n-1}|\alpha_{k-1,n}-|\alpha_{i,n}|\alpha_{k-1,n-1}\\
&=|\alpha_{i,n}|\alpha_{k,n}\left(\frac{\alpha_{k,n-1}}{\alpha_{k,n}}-\frac{\alpha_{i,n-1}}{\alpha_{i,n}}\right)+|\alpha_{i,n}|\alpha_{k,n}\left(\frac{\alpha_{i,n-1}}{\alpha_{i,n}}-\frac{\alpha_{k-1,n-1}}{\alpha_{k-1,n}}\right)\\
&=|\alpha_{i,n}|\left[(\alpha_{k,n}-\alpha_{k-1,n})\left(\frac{\alpha_{k,n-1}}{\alpha_{k,n}}-\frac{\alpha_{i,n-1}}{\alpha_{i,n}}\right)+\alpha_{k-1,n}\left(\frac{\alpha_{k,n-1}}{\alpha_{k,n}}-\frac{\alpha_{k-1,n-1}}{\alpha_{k-1,n}}\right)\right].
\end{aligned} ∣ α i , n − 1 ∣ ( α k − 1 , n − α k , n ) − ∣ α i , n ∣ ( α k − 1 , n − 1 − α k , n − 1 ) = ∣ α i , n ∣ α k , n − 1 − ∣ α i , n − 1 ∣ α k , n + ∣ α i , n − 1 ∣ α k − 1 , n − ∣ α i , n ∣ α k − 1 , n − 1 = ∣ α i , n ∣ α k , n ( α k , n α k , n − 1 − α i , n α i , n − 1 ) + ∣ α i , n ∣ α k , n ( α i , n α i , n − 1 − α k − 1 , n α k − 1 , n − 1 ) = ∣ α i , n ∣ [ ( α k , n − α k − 1 , n ) ( α k , n α k , n − 1 − α i , n α i , n − 1 ) + α k − 1 , n ( α k , n α k , n − 1 − α k − 1 , n α k − 1 , n − 1 ) ] .
which is non-negative by assumption (iii) and the result that α k − 1 , n − α k , n > 0 \alpha_{k-1,n}-\alpha_{k,n}>0 α k − 1 , n − α k , n > 0 for n ≥ N n\ge N n ≥ N and α k − 1 , n > 0 \alpha_{k-1,n}>0 α k − 1 , n > 0 . This will justify our inductive step, and by the same logic we obtain the base case when n = N + 1 n=N+1 n = N + 1 . Supposing this holds up to n − 1 n-1 n − 1 for some n n n , then,
α k − 1 , n − α k , n α k − 1 , N − α k , N = ∣ α i , n ∣ ∣ α i , N ∣ = α k − 1 , n − α k , n α k − 1 , n − 1 − α k , n − 1 ⋅ α k − 1 , n − 1 − α k , n − 1 α k − 1 , n − 2 − α k , n − 2 ⋯ α k − 1 , N + 1 − α k , N + 1 α k − 1 , N − α k , N = ∣ α i , n ∣ ∣ α i , n − 1 ∣ ⋅ ∣ α i , n − 1 ∣ ∣ α i , n − 2 ∣ ⋯ ∣ α i , N + 1 ∣ ∣ α i , N ∣ \begin{aligned}
\frac{\alpha_{k-1,n}-\alpha_{k,n}}{\alpha_{k-1,N}-\alpha_{k,N}}=\frac{|\alpha_{i,n}|}{|\alpha_{i,N}|}=\frac{\alpha_{k-1,n}-\alpha_{k,n}}{\alpha_{k-1,n-1}-\alpha_{k,n-1}}\cdot\frac{\alpha_{k-1,n-1}-\alpha_{k,n-1}}{\alpha_{k-1,n-2}-\alpha_{k,n-2}}\cdots\frac{\alpha_{k-1,N+1}-\alpha_{k,N+1}}{\alpha_{k-1,N}-\alpha_{k,N}} \\
&=\frac{|\alpha_{i,n}|}{|\alpha_{i,n-1}|}\cdot\frac{|\alpha_{i,n-1}|}{|\alpha_{i,n-2}|}\cdots\frac{|\alpha_{i,N+1}|}{|\alpha_{i,N}|}
\end{aligned} α k − 1 , N − α k , N α k − 1 , n − α k , n = ∣ α i , N ∣ ∣ α i , n ∣ = α k − 1 , n − 1 − α k , n − 1 α k − 1 , n − α k , n ⋅ α k − 1 , n − 2 − α k , n − 2 α k − 1 , n − 1 − α k , n − 1 ⋯ α k − 1 , N − α k , N α k − 1 , N + 1 − α k , N + 1 = ∣ α i , n − 1 ∣ ∣ α i , n ∣ ⋅ ∣ α i , n − 2 ∣ ∣ α i , n − 1 ∣ ⋯ ∣ α i , N ∣ ∣ α i , N + 1 ∣
which is non-negative, so the result holds by induction.
Now suppose x i + 1 − x i ≥ 0 x_{i+1}-x_i\ge0 x i + 1 − x i ≥ 0 for M + 1 ≤ i < N M+1\le i<N M + 1 ≤ i < N and < 0 <0 < 0 for N ≤ i ≤ n − 1 N\le i\le n-1 N ≤ i ≤ n − 1 . Then
0 = ( x n + 1 − x n ) 1 s ( n + 1 , M ) − ∑ i = M + 1 N − 1 ( x i + 1 − x i ) ∣ α i , n ∣ − ∑ i = N n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ + x k ( α k − 1 , n − α k , n ) 0=(x_{n+1}-x_n)\frac{1}{s(n+1,M)}-\sum_{i=M+1}^{N-1}(x_{i+1}-x_i)|\alpha_{i,n}|-\sum_{i=N}^{n-1}(x_{i+1}-x_i)|\alpha_{i,n}|+x_k(\alpha_{k-1,n}-\alpha_{k,n}) 0 = ( x n + 1 − x n ) s ( n + 1 , M ) 1 − i = M + 1 ∑ N − 1 ( x i + 1 − x i ) ∣ α i , n ∣ − i = N ∑ n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ + x k ( α k − 1 , n − α k , n )
where the sum over i = N , … , n − 1 i=N,\ldots,n-1 i = N , … , n − 1 is positive, and
x k ( α k − 1 , n − α k , n ) − ∑ i = M + 1 N − 1 ( x i + 1 − x i ) ∣ α i , n ∣ = x k ( α k − 1 , N − α k , N ) α k − 1 , n − α k , n α k − 1 , N − α k , N − ∑ i = M + 1 N − 1 ( x i + 1 − x i ) ∣ α i , N ∣ ∣ α i , n ∣ ∣ α i , N ∣ > 0 \begin{aligned}
x_k(\alpha_{k-1,n}-\alpha_{k,n})-\sum_{i=M+1}^{N-1}(x_{i+1}-x_i)|\alpha_{i,n}|
&=x_k(\alpha_{k-1,N}-\alpha_{k,N})\frac{\alpha_{k-1,n}-\alpha_{k,n}}{\alpha_{k-1,N}-\alpha_{k,N}}\\
&\quad-\sum_{i=M+1}^{N-1}(x_{i+1}-x_i)|\alpha_{i,N}|\frac{|\alpha_{i,n}|}{|\alpha_{i,N}|}>0
\end{aligned} x k ( α k − 1 , n − α k , n ) − i = M + 1 ∑ N − 1 ( x i + 1 − x i ) ∣ α i , n ∣ = x k ( α k − 1 , N − α k , N ) α k − 1 , N − α k , N α k − 1 , n − α k , n − i = M + 1 ∑ N − 1 ( x i + 1 − x i ) ∣ α i , N ∣ ∣ α i , N ∣ ∣ α i , n ∣ > 0
by (32) and the assumption that
− ( x N + 1 − x N ) 1 s ( N + 1 , M ) = x k ( α k − 1 , N − α k , N ) − ∑ i = M + 1 N − 1 ( x i + 1 − x i ) ∣ α i , N ∣ > 0. -(x_{N+1}-x_N)\frac{1}{s(N+1,M)}=x_k(\alpha_{k-1,N}-\alpha_{k,N})-\sum_{i=M+1}^{N-1}(x_{i+1}-x_i)|\alpha_{i,N}|>0. − ( x N + 1 − x N ) s ( N + 1 , M ) 1 = x k ( α k − 1 , N − α k , N ) − i = M + 1 ∑ N − 1 ( x i + 1 − x i ) ∣ α i , N ∣ > 0.
So, the tail of the sequence after step N N N is strictly monotone decreasing.
Next suppose M ≥ 2 M\ge2 M ≥ 2 and k = 1 k=1 k = 1 . Because there is no x k − x k − 1 x_k-x_{k-1} x k − x k − 1 term, we have instead the recursion
0 = ( x n + 1 − x n ) 1 s ( n + 1 , M ) − ∑ i = M + 1 n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ − x 1 α 1 , n . 0=(x_{n+1}-x_n)\frac{1}{s(n+1,M)}-\sum_{i=M+1}^{n-1}(x_{i+1}-x_i)|\alpha_{i,n}|-x_1\alpha_{1,n}. 0 = ( x n + 1 − x n ) s ( n + 1 , M ) 1 − i = M + 1 ∑ n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ − x 1 α 1 , n .
Since α i , n > 0 \alpha_{i,n}>0 α i , n > 0 for i < M i<M i < M and all n n n and x 1 > 0 x_1>0 x 1 > 0 , we know − x 1 α 1 , n < 0 -x_1\alpha_{1,n}<0 − x 1 α 1 , n < 0 . Following logic similar to that of case 3 above for a negative forcing term, we have x n + 1 − x n > 0 x_{n+1}-x_n>0 x n + 1 − x n > 0 for all n ≥ M + 1 n\ge M+1 n ≥ M + 1 by induction, so again the tail of the sequence is strictly monotone increasing. (In particular, we do not need to consider the forcing term changing sign, since − x 1 α 1 , n < 0 -x_1\alpha_{1,n}<0 − x 1 α 1 , n < 0 for all n ≥ M + 1 n\ge M+1 n ≥ M + 1 .)
Lastly, suppose k = M = 1 k=M=1 k = M = 1 . Now the x k + 1 − x k x_{k+1}-x_k x k + 1 − x k term in the original recursion is just the x M + 1 − x M x_{M+1}-x_M x M + 1 − x M term cancelled out, since now k k k and M M M coincide, so
0 = ( x n + 1 − x n ) 1 s ( n + 1 , 1 ) − ∑ i = 2 n − 1 ( x i + 1 − x i ) ∣ α i , n ∣ . 0=(x_{n+1}-x_n)\frac{1}{s(n+1,1)}-\sum_{i=2}^{n-1}(x_{i+1}-x_i)|\alpha_{i,n}|. 0 = ( x n + 1 − x n ) s ( n + 1 , 1 ) 1 − i = 2 ∑ n − 1 ( x i + 1 − x i ) ∣ α i , n ∣.
Following the logic of case 1 for a zero forcing term, we see that x n = x 1 x_n=x_1 x n = x 1 for n > 1 n>1 n > 1 .
Proof of Theorem 2.2(i). It was shown in [8 ] that assumption (ii) of Lemma 4.1 is satisfied when p ( n , i ) = [ H n − 1 ( n − i ) ] − 1 p(n,i)=[H_{n-1}(n-i)]^{-1} p ( n , i ) = [ H n − 1 ( n − i ) ] − 1 . It will suffice to show assumption (iii) is satisfied as well. Define Q ( n , x ) : = [ ψ ( n ) − ψ ( n − x ) ] / [ ψ ( n ) − ψ ( n − M ) ] Q(n,x):=[\psi(n)-\psi(n-x)]/[\psi(n)-\psi(n-M)] Q ( n , x ) := [ ψ ( n ) − ψ ( n − x )] / [ ψ ( n ) − ψ ( n − M )] , A ( n , x ) : = Q ( n + 1 , x ) − Q ( n , x ) A(n,x):=Q(n+1,x)-Q(n,x) A ( n , x ) := Q ( n + 1 , x ) − Q ( n , x ) and R ( n , x ) : = A ( n , x ) / A ( n + 1 , x ) R(n,x):=A(n,x)/A(n+1,x) R ( n , x ) := A ( n , x ) / A ( n + 1 , x ) . We wish to show R ′ ( n , x ) = ∂ x R ( n , x ) > 0 R'(n,x)=\partial_xR(n,x)>0 R ′ ( n , x ) = ∂ x R ( n , x ) > 0 . Because R ( n , x ) R(n,x) R ( n , x ) is undefined at x = M x=M x = M , we will first show R ′ ( n , x ) > 0 R'(n,x)>0 R ′ ( n , x ) > 0 for x < M x<M x < M and x > M x>M x > M separately, then verify that R ( n , x ) R(n,x) R ( n , x ) has a continuous extension to x = M x=M x = M . To begin, notice
R ′ ( n , x ) = A ( n , x ) A ( n + 1 , x ) [ A ( n + 1 , x ) ] 2 [ A ′ ( n , x ) A ( n , x ) − A ′ ( n + 1 , x ) A ( n + 1 , x ) ] . R'(n,x)=\frac{A(n,x)A(n+1,x)}{[A(n+1,x)]^2}\left[\frac{A'(n,x)}{A(n,x)}-\frac{A'(n+1,x)}{A(n+1,x)}\right]. R ′ ( n , x ) = [ A ( n + 1 , x ) ] 2 A ( n , x ) A ( n + 1 , x ) [ A ( n , x ) A ′ ( n , x ) − A ( n + 1 , x ) A ′ ( n + 1 , x ) ] .
so, since A ( n , x ) A(n,x) A ( n , x ) and A ( n + 1 , x ) A(n+1,x) A ( n + 1 , x ) have the same sign for all x x x , this is equivalent to showing
A ′ ( n , x ) A ( n , x ) − A ′ ( n + 1 , x ) A ( n + 1 , x ) > 0. \frac{A'(n,x)}{A(n,x)}-\frac{A'(n+1,x)}{A(n+1,x)}>0. A ( n , x ) A ′ ( n , x ) − A ( n + 1 , x ) A ′ ( n + 1 , x ) > 0.
We first show that this ratio can be viewed as a ratio of covariances under a probability measure μ n \mu_n μ n .
Lemma 4.2. For g x ( t ) g_x(t) g x ( t ) and μ n \mu_n μ n as defined in (34) and (35) ,
A ′ ( n , x ) A ( n , x ) = Cov μ n ( ∂ x g x ( τ ) , τ ) Cov μ n ( g x ( τ ) , τ ) . (33) \frac{A'(n,x)}{A(n,x)}=\frac{\operatorname{Cov}_{\mu_n}(\partial_xg_x(\tau),\tau)}{\operatorname{Cov}_{\mu_n}(g_x(\tau),\tau)}. \tag*{(33)} A ( n , x ) A ′ ( n , x ) = Cov μ n ( g x ( τ ) , τ ) Cov μ n ( ∂ x g x ( τ ) , τ ) . (33)
Proof. Note the integral definition of the digamma function:
ψ ( n ) = − γ + ∫ 0 1 ( 1 − t n 1 − t ) d t ⟹ ψ ( n ) − ψ ( n − x ) = ∫ 0 1 t n − 1 ( t − x − 1 1 − t ) d t . \psi(n)=-\gamma+\int_0^1\left(\frac{1-t^n}{1-t}\right)\,dt\quad\Longrightarrow\quad\psi(n)-\psi(n-x)=\int_0^1t^{n-1}\left(\frac{t^{-x}-1}{1-t}\right)\,dt. ψ ( n ) = − γ + ∫ 0 1 ( 1 − t 1 − t n ) d t ⟹ ψ ( n ) − ψ ( n − x ) = ∫ 0 1 t n − 1 ( 1 − t t − x − 1 ) d t .
To begin, we express the function Q ( n , x ) Q(n,x) Q ( n , x ) as an expectation: Define the weight function w n ( t ) : = t n − 1 ( t − M − 1 1 − t ) w_n(t):=t^{n-1}\left(\frac{t^{-M}-1}{1-t}\right) w n ( t ) := t n − 1 ( 1 − t t − M − 1 ) and its integral W n : = ∫ 0 1 w n ( t ) d t = ψ ( n ) − ψ ( n − M ) W_n:=\int_0^1w_n(t)\,dt=\psi(n)-\psi(n-M) W n := ∫ 0 1 w n ( t ) d t = ψ ( n ) − ψ ( n − M ) . Then
Q ( n , x ) = ∫ 0 1 t n − 1 ( t − x − 1 1 − t ) d t W n = ∫ 0 1 ( t − x − 1 t − M − 1 ) w n ( t ) d t W n = E μ n ( g x ( τ ) ) Q(n,x)=\int_0^1t^{n-1}\left(\frac{t^{-x}-1}{1-t}\right)\frac{dt}{W_n}=\int_0^1\left(\frac{t^{-x}-1}{t^{-M}-1}\right)\frac{w_n(t)\,dt}{W_n}=\mathbb{E}_{\mu_n}(g_x(\tau)) Q ( n , x ) = ∫ 0 1 t n − 1 ( 1 − t t − x − 1 ) W n d t = ∫ 0 1 ( t − M − 1 t − x − 1 ) W n w n ( t ) d t = E μ n ( g x ( τ ))
where
g x ( t ) : = t − x − 1 t − M − 1 , (34) g_x(t) := \frac{t^{-x}-1}{t^{-M}-1}, \tag*{(34)} g x ( t ) := t − M − 1 t − x − 1 , (34)
and
d μ n : = w n ( t ) W n d t (35) d\mu_n := \frac{w_n(t)}{W_n}\,dt \tag*{(35)} d μ n := W n w n ( t ) d t (35)
is a probability measure with density function f n ( t ) = w n ( t ) / W n f_n(t)=w_n(t)/W_n f n ( t ) = w n ( t ) / W n . Since w n + 1 ( t ) = t w n ( t ) w_{n+1}(t)=t\,w_n(t) w n + 1 ( t ) = t w n ( t ) , W n + 1 W_{n+1} W n + 1 and W n W_n W n are related by
W n + 1 = ∫ 0 1 t w n ( t ) d t = W n ∫ 0 1 t w n ( t ) W n d t = W n E μ n ( τ ) W_{n+1}=\int_0^1 t\,w_n(t)\,dt=W_n\int_0^1 t\frac{w_n(t)}{W_n}\,dt=W_n\mathbb{E}_{\mu_n}(\tau) W n + 1 = ∫ 0 1 t w n ( t ) d t = W n ∫ 0 1 t W n w n ( t ) d t = W n E μ n ( τ )
and, in turn,
d μ n + 1 = t w n ( t ) W n + 1 d t = t E μ n ( τ ) d μ n . d\mu_{n+1}=\frac{t\,w_n(t)}{W_{n+1}}\,dt=\frac{t}{\mathbb{E}_{\mu_n}(\tau)}\,d\mu_n. d μ n + 1 = W n + 1 t w n ( t ) d t = E μ n ( τ ) t d μ n .
We note that μ n + 1 \mu_{n+1} μ n + 1 is the τ \tau τ -size bias of μ n \mu_n μ n , but we do not use this fact explicitly. In particular,
E μ n + 1 ( g x ( τ ) ) = E μ n ( τ g x ( τ ) ) E μ n ( τ ) . \mathbb{E}_{\mu_{n+1}}(g_x(\tau))=\frac{\mathbb{E}_{\mu_n}(\tau g_x(\tau))}{\mathbb{E}_{\mu_n}(\tau)}. E μ n + 1 ( g x ( τ )) = E μ n ( τ ) E μ n ( τ g x ( τ )) .
It follows, since A ( n , x ) = Q ( n + 1 , x ) − Q ( n , x ) A(n,x)=Q(n+1,x)-Q(n,x) A ( n , x ) = Q ( n + 1 , x ) − Q ( n , x ) , that
A ( n , x ) = E μ n + 1 ( g x ( τ ) ) − E μ n ( g x ( τ ) ) = Cov μ n ( g x ( τ ) , τ ) E μ n ( τ ) , A(n,x)=\mathbb{E}_{\mu_{n+1}}(g_x(\tau))-\mathbb{E}_{\mu_n}(g_x(\tau))=\frac{\operatorname{Cov}_{\mu_n}(g_x(\tau),\tau)}{\mathbb{E}_{\mu_n}(\tau)}, A ( n , x ) = E μ n + 1 ( g x ( τ )) − E μ n ( g x ( τ )) = E μ n ( τ ) Cov μ n ( g x ( τ ) , τ ) ,
and similarly
A ′ ( n , x ) = Cov μ n ( ∂ x g x ( τ ) , τ ) E μ n ( τ ) . A'(n,x)=\frac{\operatorname{Cov}_{\mu_n}(\partial_xg_x(\tau),\tau)}{\mathbb{E}_{\mu_n}(\tau)}. A ′ ( n , x ) = E μ n ( τ ) Cov μ n ( ∂ x g x ( τ ) , τ ) .
From here the proof proceeds as follows: We express the ratio A ′ ( n , x ) / A ( n , x ) A'(n,x)/A(n,x) A ′ ( n , x ) / A ( n , x ) as E η n , x ( Ψ ( t ) ) \mathbb{E}_{\eta_{n,x}}(\Psi(t)) E η n , x ( Ψ ( t )) (Ψ \Psi Ψ and η n , x \eta_{n,x} η n , x defined below), and then show that Ψ ( t ) \Psi(t) Ψ ( t ) is decreasing and η n + 1 , x ≥ s t η n , x \eta_{n+1,x}\ge_{\mathrm{st}}\eta_{n,x} η n + 1 , x ≥ st η n , x (η n + 1 , x \eta_{n+1,x} η n + 1 , x stochastically dominates η n , x \eta_{n,x} η n , x ), from which the result follows (e.g., see [18 Theorem 1.A.3] ).
Lemma 4.3. For η n , x \eta_{n,x} η n , x as defined in (4.12), η n + 1 , x ≥ s t η n , x \eta_{n+1,x}\ge_{\mathrm{st}}\eta_{n,x} η n + 1 , x ≥ st η n , x , and A ′ ( n , x ) / A ( n , x ) = E η n , x ( Ψ ( τ ) ) A'(n,x)/A(n,x)=\mathbb{E}_{\eta_{n,x}}(\Psi(\tau)) A ′ ( n , x ) / A ( n , x ) = E η n , x ( Ψ ( τ )) with Ψ ( t ) = ∂ x ln ∣ g x ( t ) ∣ \Psi(t)=\partial_x\ln|g_x(t)| Ψ ( t ) = ∂ x ln ∣ g x ( t ) ∣ .
Proof. Define E n : = E μ n ( τ ) E_n:=\mathbb{E}_{\mu_n}(\tau) E n := E μ n ( τ ) . Writing f ( t ) = ∫ 0 t f ′ ( u ) d u f(t)=\int_0^t f'(u)\,du f ( t ) = ∫ 0 t f ′ ( u ) d u and changing the order of integration yields
Cov μ n ( f ( t ) , t ) = ∫ 0 1 f ( t ) ( t − E n ) d μ n = ∫ 0 1 f ′ ( u ) ( ∫ u 1 ( E n − t ) d μ n ) d u = ∫ 0 1 f ′ ( u ) I n ( u ) d u (36) \begin{aligned}
\operatorname{Cov}_{\mu_n}(f(t),t)
&=\int_0^1 f(t)(t-E_n)\,d\mu_n\\
&=\int_0^1 f'(u)\left(\int_u^1(E_n-t)\,d\mu_n\right)\,du\\
&=\int_0^1 f'(u)I_n(u)\,du \tag*{(36)}
\end{aligned} Cov μ n ( f ( t ) , t ) = ∫ 0 1 f ( t ) ( t − E n ) d μ n = ∫ 0 1 f ′ ( u ) ( ∫ u 1 ( E n − t ) d μ n ) d u = ∫ 0 1 f ′ ( u ) I n ( u ) d u (36)
where
I n ( u ) : = ∫ 0 u ( E n − t ) d μ n ( t ) . (37) I_n(u):=\int_0^u(E_n-t)\,d\mu_n(t). \tag*{(37)} I n ( u ) := ∫ 0 u ( E n − t ) d μ n ( t ) . (37)
We have used that
∫ 0 1 ( t − E n ) d μ n ( t ) = ∫ 0 u ( t − E n ) d μ n ( t ) + ∫ u 1 ( t − E n ) d μ n ( t ) = 0 , \int_0^1(t-E_n)\,d\mu_n(t)=\int_0^u(t-E_n)\,d\mu_n(t)+\int_u^1(t-E_n)\,d\mu_n(t)=0, ∫ 0 1 ( t − E n ) d μ n ( t ) = ∫ 0 u ( t − E n ) d μ n ( t ) + ∫ u 1 ( t − E n ) d μ n ( t ) = 0 ,
which yields the following equivalent definition, which will become useful shortly:
I n ( u ) : = − ∫ u 1 ( E n − t ) d μ n ( t ) . (38) I_n(u) := -\int_u^1 (E_n-t)\,d\mu_n(t). \tag*{(38)} I n ( u ) := − ∫ u 1 ( E n − t ) d μ n ( t ) . (38)
Since I n ( u ) = 0 I_n(u)=0 I n ( u ) = 0 for u = 0 , 1 u=0,1 u = 0 , 1 , increasing on 0 ≤ u ≤ E n 0\le u\le E_n 0 ≤ u ≤ E n decreasing on the rest of the interval, I n ( u ) > 0 I_n(u)>0 I n ( u ) > 0 for 0 < u < 1 0<u<1 0 < u < 1 . This transform is inspired by the method of zero-biasing found used with Stein’s method. See, e.g., [12 ] or [9 §2.3.3] .
When f ( t ) = g x ( t ) f(t)=g_x(t) f ( t ) = g x ( t ) , we have
g x ′ ( t ) = t M − x − 1 ( t M − 1 ) 2 [ x ( t M − 1 ) − M ( t x − 1 ) ] . (39) g_x'(t)=\frac{t^{M-x-1}}{(t^M-1)^2}\left[x(t^M-1)-M(t^x-1)\right]. \tag*{(39)} g x ′ ( t ) = ( t M − 1 ) 2 t M − x − 1 [ x ( t M − 1 ) − M ( t x − 1 ) ] . (39)
Of course, the leading factor is positive for 0 < t < 1 0<t<1 0 < t < 1 . The second factor equals zero at t = 1 t=1 t = 1 , and we find its derivative with respect to t t t ,
∂ t [ x ( t M − 1 ) − M ( t x − 1 ) ] = x M t x − 1 [ t M − x − 1 ] , \partial_t\left[x(t^M-1)-M(t^x-1)\right]=xMt^{x-1}\left[t^{M-x}-1\right], ∂ t [ x ( t M − 1 ) − M ( t x − 1 ) ] = x M t x − 1 [ t M − x − 1 ] ,
is negative if x < M x<M x < M and positive if x > M x>M x > M , for all 0 < t < 1 0<t<1 0 < t < 1 . That is, the term is either monotone increasing or monotone decreasing towards zero. It follows that g x ′ ( t ) g_x'(t) g x ′ ( t ) has the same sign for all 0 < t < 1 0<t<1 0 < t < 1 , and in particular g x ′ ( t ) > 0 g_x'(t)>0 g x ′ ( t ) > 0 when x < M x<M x < M and g x ′ ( t ) < 0 g_x'(t)<0 g x ′ ( t ) < 0 when x > M x>M x > M . So, writing K n , x : = Cov μ n ( g x ( τ ) , τ ) K_{n,x}:=\operatorname{Cov}_{\mu_n}(g_x(\tau),\tau) K n , x := Cov μ n ( g x ( τ ) , τ ) ,
d η n , x : = g x ′ ( t ) I n ( t ) d t K n , x = ∣ g x ′ ( t ) ∣ I n ( t ) d t ∫ 0 1 ∣ g x ′ ( u ) ∣ I n ( u ) d u (40) d\eta_{n,x}:=\frac{g_x'(t)I_n(t)\,dt}{K_{n,x}}=\frac{\lvert g_x'(t)\rvert I_n(t)\,dt}{\int_0^1\lvert g_x'(u)\rvert I_n(u)\,du} \tag*{(40)} d η n , x := K n , x g x ′ ( t ) I n ( t ) d t = ∫ 0 1 ∣ g x ′ ( u )∣ I n ( u ) d u ∣ g x ′ ( t )∣ I n ( t ) d t (40)
is a valid probability measure with density function ϕ n , x ( t ) : = g x ′ ( t ) I n ( t ) / K n , x \phi_{n,x}(t):=g_x'(t)I_n(t)/K_{n,x} ϕ n , x ( t ) := g x ′ ( t ) I n ( t ) / K n , x .
To show η n + 1 , x ≥ s t η n , x \eta_{n+1,x}\ge_{\mathrm{st}}\eta_{n,x} η n + 1 , x ≥ st η n , x , it is sufficient to show that η n + 1 , x \eta_{n+1,x} η n + 1 , x dominates η n , x \eta_{n,x} η n , x in likelihood ratio [18 Theorem 1.C.1] . Notice that the ratio of the densities of η n + 1 , x \eta_{n+1,x} η n + 1 , x and η n , x \eta_{n,x} η n , x is
ϕ n + 1 , x ( t ) ϕ n , x ( t ) = K n , x K n + 1 , x I n + 1 ( t ) I n ( t ) , \frac{\phi_{n+1,x}(t)}{\phi_{n,x}(t)}=\frac{K_{n,x}}{K_{n+1,x}}\frac{I_{n+1}(t)}{I_n(t)}, ϕ n , x ( t ) ϕ n + 1 , x ( t ) = K n + 1 , x K n , x I n ( t ) I n + 1 ( t ) ,
so we need only show that I n + 1 ( t ) / I n ( t ) I_{n+1}(t)/I_n(t) I n + 1 ( t ) / I n ( t ) is increasing in t t t . The sign of the derivative is the same as the sign of
I n + 1 ′ ( t ) I n ( t ) − I n + 1 ( t ) I n ′ ( t ) = [ ( E n + 1 − t ) t f n ( t ) E n ] I n ( t ) − I n + 1 ( t ) [ ( E n − t ) f n ( t ) ] = f n ( t ) E n [ t ( E n + 1 − t ) I n ( t ) − E n ( E n − t ) I n + 1 ( t ) ] . \begin{aligned}
I_{n+1}'(t)I_n(t)-I_{n+1}(t)I_n'(t)
&=\left[(E_{n+1}-t)\frac{tf_n(t)}{E_n}\right]I_n(t)-I_{n+1}(t)\left[(E_n-t)f_n(t)\right]\\
&=\frac{f_n(t)}{E_n}\left[t(E_{n+1}-t)I_n(t)-E_n(E_n-t)I_{n+1}(t)\right].
\end{aligned} I n + 1 ′ ( t ) I n ( t ) − I n + 1 ( t ) I n ′ ( t ) = [ ( E n + 1 − t ) E n t f n ( t ) ] I n ( t ) − I n + 1 ( t ) [ ( E n − t ) f n ( t ) ] = E n f n ( t ) [ t ( E n + 1 − t ) I n ( t ) − E n ( E n − t ) I n + 1 ( t ) ] .
Of course, the leading factor is positive, since f n f_n f n is a probability density and E n E_n E n is the mean of a random variable that is positive almost surely. Define H ( t ) : = t ( E n + 1 − t ) I n ( t ) − E n ( E n − t ) I n + 1 H(t):=t(E_{n+1}-t)I_n(t)-E_n(E_n-t)I_{n+1} H ( t ) := t ( E n + 1 − t ) I n ( t ) − E n ( E n − t ) I n + 1 . We show in the following cases that H ( t ) > 0 H(t)>0 H ( t ) > 0 , from which η n + 1 , x ≥ s t η n , x \eta_{n+1,x}\ge_{\mathrm{st}}\eta_{n,x} η n + 1 , x ≥ st η n , x :
Case 1 (0 < t ≤ E n 0<t\le E_n 0 < t ≤ E n ). Write H ( t ) H(t) H ( t ) under a single integral using the first definition of I n ( t ) I_n(t) I n ( t ) in (4.9):
H ( t ) = ∫ 0 t [ t ( E n + 1 − t ) ( E n − s ) − s ( E n − t ) ( E n + 1 − s ) ] d μ n ( s ) . H(t)=\int_0^t\left[t(E_{n+1}-t)(E_n-s)-s(E_n-t)(E_{n+1}-s)\right]d\mu_n(s). H ( t ) = ∫ 0 t [ t ( E n + 1 − t ) ( E n − s ) − s ( E n − t ) ( E n + 1 − s ) ] d μ n ( s ) .
Expanding the integrand, writing V n : = Var μ n ( τ ) V_n:=\operatorname{Var}_{\mu_n}(\tau) V n := Var μ n ( τ ) , and noticing that (because μ n + 1 \mu_{n+1} μ n + 1 is a size-bias of μ n \mu_n μ n ) E n E n + 1 = V n + E n 2 E_nE_{n+1}=V_n+E_n^2 E n E n + 1 = V n + E n 2 , one finds
H ( t ) = ∫ 0 t ( t − s ) [ E n E n + 1 − ( t + s ) E n + t s ] d μ n ( s ) = ∫ 0 t ( t − s ) [ V n + ( E n − t ) ( E n − s ) ] d μ n ( s ) . H(t)=\int_0^t(t-s)\left[E_nE_{n+1}-(t+s)E_n+ts\right]d\mu_n(s)=\int_0^t(t-s)\left[V_n+(E_n-t)(E_n-s)\right]d\mu_n(s). H ( t ) = ∫ 0 t ( t − s ) [ E n E n + 1 − ( t + s ) E n + t s ] d μ n ( s ) = ∫ 0 t ( t − s ) [ V n + ( E n − t ) ( E n − s ) ] d μ n ( s ) .
Then it is straightforward to check: t − s > 0 t-s>0 t − s > 0 for 0 < s < t 0<s<t 0 < s < t ; E n − t ≥ 0 E_n-t\ge0 E n − t ≥ 0 and E n − s > 0 E_n-s>0 E n − s > 0 for s < t ≤ E n s<t\le E_n s < t ≤ E n ; V n > 0 V_n>0 V n > 0 as a variance of a non-degenerate random variable.
Case 2 (E n < t ≤ E n + 1 E_n < t \le E_{n+1} E n < t ≤ E n + 1 ). Write H ( t ) H(t) H ( t ) simply as
H ( t ) = t ( E n + 1 − t ) I n ( t ) + E n ( t − E n ) I n + 1 . H(t) = t(E_{n+1} - t)I_n(t) + E_n(t - E_n)I_{n+1}. H ( t ) = t ( E n + 1 − t ) I n ( t ) + E n ( t − E n ) I n + 1 .
We have already shown that I n ( t ) > 0 I_n(t) > 0 I n ( t ) > 0 for 0 < t < 1 0 < t < 1 0 < t < 1 and all n n n , and since E n < t ≤ E n + 1 E_n < t \le E_{n+1} E n < t ≤ E n + 1 , both terms in the sum are positive.
Case 3 (E n + 1 < t < 1 E_{n+1} < t < 1 E n + 1 < t < 1 ). Write H ( t ) H(t) H ( t ) under a single integral, but now using the second definition (38) :
H ( t ) = ∫ t 1 ( s − t ) [ V n + ( E n − t ) ( E n − s ) ] d μ n ( s ) . H(t) = \int_t^1 (s-t)\left[V_n + (E_n-t)(E_n-s)\right]\,d\mu_n(s). H ( t ) = ∫ t 1 ( s − t ) [ V n + ( E n − t ) ( E n − s ) ] d μ n ( s ) .
As before: s − t > 0 s-t > 0 s − t > 0 for t < s < 1 t < s < 1 t < s < 1 ; ( E n − t ) < 0 (E_n-t) < 0 ( E n − t ) < 0 and E n − s < 0 E_n-s < 0 E n − s < 0 , so their product is positive; V n > 0 V_n > 0 V n > 0 .
Applying (36) to (33) with f ( t ) = ∂ x g x ( t ) f(t) = \partial_x g_x(t) f ( t ) = ∂ x g x ( t ) , since ∂ t ∂ x g x ( t ) = ∂ x ∂ t g x ( t ) \partial_t\partial_x g_x(t) = \partial_x\partial_t g_x(t) ∂ t ∂ x g x ( t ) = ∂ x ∂ t g x ( t ) , yields
A ′ ( n , x ) A ( n , x ) = ∫ 0 1 ( ∂ x g x ( t ) ) ′ g x ′ ( t ) g x ′ ( t ) I n ( t ) K n , x d t = E η n , x ( Ψ ( τ ) ) ; Ψ ( t ) : = ∂ x ln ∣ g x ′ ( t ) ∣ . \frac{A'(n,x)}{A(n,x)} = \int_0^1 \frac{(\partial_x g_x(t))'}{g_x'(t)}\frac{g_x'(t)I_n(t)}{K_{n,x}}\,dt = \mathbb{E}_{\eta_{n,x}}(\Psi(\tau));\qquad\Psi(t) := \partial_x\ln|g_x'(t)|. A ( n , x ) A ′ ( n , x ) = ∫ 0 1 g x ′ ( t ) ( ∂ x g x ( t ) ) ′ K n , x g x ′ ( t ) I n ( t ) d t = E η n , x ( Ψ ( τ )) ; Ψ ( t ) := ∂ x ln ∣ g x ′ ( t ) ∣.
Lemma 4.4. Ψ ′ ( t ) < 0 \Psi'(t) < 0 Ψ ′ ( t ) < 0 .
Proof. It will be more convenient to work under the change of variables u = − ln ( t ) u=-\ln(t) u = − ln ( t ) . Using (39) and applying this change of variables, for which ∂ t = − e u ∂ u \partial_t=-e^u\partial_u ∂ t = − e u ∂ u , we can express Ψ ( t ) \Psi(t) Ψ ( t ) as:
Ψ ( u ) = u − N ( u ) D ( u ) ; N ( u ) = e − M u − 1 + M u e − x u ; D ( u ) = x ( 1 − e − M u ) − M ( 1 − e − x u ) . \Psi(u) = u - \frac{N(u)}{D(u)};\qquad N(u) = e^{-Mu}-1+Mue^{-xu};\qquad D(u) = x(1-e^{-Mu})-M(1-e^{-xu}). Ψ ( u ) = u − D ( u ) N ( u ) ; N ( u ) = e − M u − 1 + M u e − xu ; D ( u ) = x ( 1 − e − M u ) − M ( 1 − e − xu ) . Then, writing Ψ ˙ \dot{\Psi} Ψ ˙ for differentiation with respect to u u u ,
Ψ ′ ( t ) = − e u Ψ ˙ ( u ) . \Psi'(t) = -e^u\dot{\Psi}(u). Ψ ′ ( t ) = − e u Ψ ˙ ( u ) . The result will follow from showing that Ψ ˙ ( u ) > 0 \dot{\Psi}(u) > 0 Ψ ˙ ( u ) > 0 , or D ( u ) 2 > N ˙ ( u ) D ( u ) − N ( u ) D ˙ ( u ) D(u)^2 > \dot{N}(u)D(u)-N(u)\dot{D}(u) D ( u ) 2 > N ˙ ( u ) D ( u ) − N ( u ) D ˙ ( u ) . To begin, the derivatives of N N N and D D D are
N ˙ ( u ) = M [ ( 1 − e − M u ) − ( 1 − e − x u ) ] − M x u e − x u ; (41) \dot{N}(u) = M\left[(1-e^{-Mu})-(1-e^{-xu})\right]-Mxu e^{-xu}; \tag*{(41)} N ˙ ( u ) = M [ ( 1 − e − M u ) − ( 1 − e − xu ) ] − M xu e − xu ; (41) D ˙ ( u ) = M x [ ( 1 − e − x u ) − ( 1 − e − M u ) ] . (42) \dot{D}(u) = Mx\left[(1-e^{-xu})-(1-e^{-Mu})\right]. \tag*{(42)} D ˙ ( u ) = M x [ ( 1 − e − xu ) − ( 1 − e − M u ) ] . (42) Next, we write D ( u ) 2 − N ˙ ( u ) D ( u ) + N ( u ) D ˙ ( u ) D(u)^2-\dot{N}(u)D(u)+N(u)\dot{D}(u) D ( u ) 2 − N ˙ ( u ) D ( u ) + N ( u ) D ˙ ( u ) explicitly and collect terms:
x 2 ( 1 − e − M u ) 2 + ( M 2 − 2 M x ) ( 1 − e − M u ) ( 1 − e − x u ) + M x ( x − M ) u e − x u ( 1 − e − M u ) x^2(1-e^{-Mu})^2+(M^2-2Mx)(1-e^{-Mu})(1-e^{-xu})+Mx(x-M)ue^{-xu}(1-e^{-Mu}) x 2 ( 1 − e − M u ) 2 + ( M 2 − 2 M x ) ( 1 − e − M u ) ( 1 − e − xu ) + M x ( x − M ) u e − xu ( 1 − e − M u ) = e − x u ( 1 − e − M u ) [ x 2 ( e x u − e ( x − M ) u ) + ( M 2 − 2 M x ) ( e x u − 1 ) + M x ( x − M ) u ] = e^{-xu}(1-e^{-Mu})\left[x^2(e^{xu}-e^{(x-M)u})+(M^2-2Mx)(e^{xu}-1)+Mx(x-M)u\right] = e − xu ( 1 − e − M u ) [ x 2 ( e xu − e ( x − M ) u ) + ( M 2 − 2 M x ) ( e xu − 1 ) + M x ( x − M ) u ] = e − x u ( 1 − e − M u ) [ ( x − M ) 2 e x u − x 2 e ( x − M ) u + ( 2 M x − M 2 ) + M x ( x − M ) u ] . = e^{-xu}(1-e^{-Mu})\left[(x-M)^2e^{xu}-x^2e^{(x-M)u}+(2Mx-M^2)+Mx(x-M)u\right]. = e − xu ( 1 − e − M u ) [ ( x − M ) 2 e xu − x 2 e ( x − M ) u + ( 2 M x − M 2 ) + M x ( x − M ) u ] . The leading terms are clearly positive. Write
H ( u ) : = ( x − M ) 2 e x u − x 2 e ( x − M ) u + ( 2 M x − M 2 ) + M x ( x − M ) u H(u):=(x-M)^2e^{xu}-x^2e^{(x-M)u}+(2Mx-M^2)+Mx(x-M)u H ( u ) := ( x − M ) 2 e xu − x 2 e ( x − M ) u + ( 2 M x − M 2 ) + M x ( x − M ) u and note
H ˙ ( u ) = x ( x − M ) [ ( x − M ) e x u − x e ( x − M ) u + M ] , H ¨ ( u ) = x 2 ( x − M ) 2 e x u ( 1 − e − M u ) \dot{H}(u)=x(x-M)\left[(x-M)e^{xu}-xe^{(x-M)u}+M\right],\qquad\ddot{H}(u)=x^2(x-M)^2e^{xu}(1-e^{-Mu}) H ˙ ( u ) = x ( x − M ) [ ( x − M ) e xu − x e ( x − M ) u + M ] , H ¨ ( u ) = x 2 ( x − M ) 2 e xu ( 1 − e − M u ) and that H ( 0 ) = H ˙ ( 0 ) = 0 H(0)=\dot{H}(0)=0 H ( 0 ) = H ˙ ( 0 ) = 0 . Clearly, H ¨ ( u ) > 0 \ddot{H}(u)>0 H ¨ ( u ) > 0 and so H ˙ ( u ) \dot{H}(u) H ˙ ( u ) and, in turn, H ( u ) H(u) H ( u ) are positive as well. It follows that D ( u ) 2 > N ˙ ( u ) D ( u ) − N ( u ) D ˙ ( u ) D(u)^2>\dot{N}(u)D(u)-N(u)\dot{D}(u) D ( u ) 2 > N ˙ ( u ) D ( u ) − N ( u ) D ˙ ( u ) and therefore Ψ ˙ ( u ) > 0 \dot{\Psi}(u)>0 Ψ ˙ ( u ) > 0 as desired.
As stated, the result follows from η n + 1 , x ≥ s t η n , x \eta_{n+1,x} \ge_{\mathrm{st}} \eta_{n,x} η n + 1 , x ≥ st η n , x and Ψ ′ ( t ) < 0 \Psi'(t)<0 Ψ ′ ( t ) < 0 , for x ≠ M x \ne M x = M . To show that R ( n , x ) R(n,x) R ( n , x ) has a continuous extension to x = M x=M x = M , write x = M + δ x=M+\delta x = M + δ . Taking the Taylor series of ψ ( n − x ) = ψ ( n − M − δ ) \psi(n-x)=\psi(n-M-\delta) ψ ( n − x ) = ψ ( n − M − δ ) about n − M n-M n − M ,
Q ( n , x ) = ψ ( n ) − [ ψ ( n − M ) − δ ψ ′ ( n − M ) + O ( δ 2 ) ] ψ ( n ) − ψ ( n − M ) = 1 + δ ⋅ ψ ′ ( n − M ) ψ ( n ) − ψ ( n − M ) + O ( δ 2 ) = 1 + δ C ( n ) + O ( δ 2 ) , \begin{aligned}
Q(n,x)=\frac{\psi(n)-[\psi(n-M)-\delta\psi'(n-M)+O(\delta^2)]}{\psi(n)-\psi(n-M)} \\
&=1+\delta\cdot\frac{\psi'(n-M)}{\psi(n)-\psi(n-M)}+O(\delta^2) \\
&=1+\delta C(n)+O(\delta^2),
\end{aligned} Q ( n , x ) = ψ ( n ) − ψ ( n − M ) ψ ( n ) − [ ψ ( n − M ) − δ ψ ′ ( n − M ) + O ( δ 2 )] = 1 + δ ⋅ ψ ( n ) − ψ ( n − M ) ψ ′ ( n − M ) + O ( δ 2 ) = 1 + δ C ( n ) + O ( δ 2 ) ,
where C ( n ) : = ψ ′ ( n − M ) / [ ψ ( n ) − ψ ( n − M ) ] C(n):=\psi'(n-M)/[\psi(n)-\psi(n-M)] C ( n ) := ψ ′ ( n − M ) / [ ψ ( n ) − ψ ( n − M )] . In turn, writing Δ C ( n ) = C ( n + 1 ) − C ( n ) \Delta C(n)=C(n+1)-C(n) Δ C ( n ) = C ( n + 1 ) − C ( n ) ,
A ( n , x ) = Q ( n + 1 , x ) − Q ( n , x ) = δ Δ C ( n ) + O ( δ 2 ) , A(n,x)=Q(n+1,x)-Q(n,x)=\delta\Delta C(n)+O(\delta^2), A ( n , x ) = Q ( n + 1 , x ) − Q ( n , x ) = δ Δ C ( n ) + O ( δ 2 ) ,
and
R ( n , x ) = A ( n , x ) A ( n + 1 , x ) = δ Δ C ( n ) + O ( δ 2 ) δ Δ C ( n + 1 ) + O ( δ 2 ) = Δ C ( n ) + O ( δ ) Δ C ( n + 1 ) + O ( δ ) → Δ C ( n ) Δ C ( n + 1 ) R(n,x)=\frac{A(n,x)}{A(n+1,x)}=\frac{\delta\Delta C(n)+O(\delta^2)}{\delta\Delta C(n+1)+O(\delta^2)}=\frac{\Delta C(n)+O(\delta)}{\Delta C(n+1)+O(\delta)}\to\frac{\Delta C(n)}{\Delta C(n+1)} R ( n , x ) = A ( n + 1 , x ) A ( n , x ) = δ Δ C ( n + 1 ) + O ( δ 2 ) δ Δ C ( n ) + O ( δ 2 ) = Δ C ( n + 1 ) + O ( δ ) Δ C ( n ) + O ( δ ) → Δ C ( n + 1 ) Δ C ( n )
as δ → 0 \delta\to0 δ → 0 .
Proof of Theorem 2.2(ii). Note that s ( n , i ) = H n − 1 − H n − i − 1 s(n,i)=H_{n-1}-H_{n-i-1} s ( n , i ) = H n − 1 − H n − i − 1 . From (29) , dropping the normalization factor 1 / H n − 1 1/H_{n-1} 1/ H n − 1 , we have
∑ i = 1 n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) = 0. (43) \sum_{i=1}^{n-1}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i)=0. \tag*{(43)} i = 1 ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) = 0. (43)
Recall that x i = 0 x_i=0 x i = 0 for 1 ≤ i ≤ M 1\le i\le M 1 ≤ i ≤ M , except for x k > 0 x_k>0 x k > 0 , so for k < M k<M k < M , x M + 1 − x M > 0 x_{M+1}-x_M>0 x M + 1 − x M > 0 . Lemma 4.1 showed that either the tail of x n x_n x n is monotone increasing for n ≥ M + 1 n\ge M+1 n ≥ M + 1 or the sequence of differences x n + 1 − x n x_{n+1}-x_n x n + 1 − x n is initially positive, changes sign exactly once, and the tail of x n x_n x n is strictly monotone decreasing. For 1 ≤ k < M 1\le k<M 1 ≤ k < M , we derive the error bound separately for each of these cases.
Case 1 (Tail of x n x_n x n strictly monotone decreasing). Suppose that x i + 1 − x i ≥ 0 x_{i+1}-x_i\ge0 x i + 1 − x i ≥ 0 for i = M + 1 , … , N i=M+1,\ldots,N i = M + 1 , … , N and < 0 <0 < 0 otherwise, with M ≤ N < ∞ M\le N<\infty M ≤ N < ∞ . For k , M ≥ 2 k,M\ge2 k , M ≥ 2 and k < M k<M k < M , the terms of (43) up to i = M − 1 i=M-1 i = M − 1 are zero except for
( H n − 1 − H n − k − 1 ) ( x k + 1 − x k ) + ( H n − 1 − H n − k ) ( x k − x k − 1 ) = x k ( H n − k − 1 − H n − k ) = − x k n − k . (H_{n-1}-H_{n-k-1})(x_{k+1}-x_k)+(H_{n-1}-H_{n-k})(x_k-x_{k-1})=x_k(H_{n-k-1}-H_{n-k})=-\frac{x_k}{n-k}. ( H n − 1 − H n − k − 1 ) ( x k + 1 − x k ) + ( H n − 1 − H n − k ) ( x k − x k − 1 ) = x k ( H n − k − 1 − H n − k ) = − n − k x k .
Then, decomposing the sum as
− x k n − k + ∑ i = M N ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) + ∑ i = N + 1 n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) -\frac{x_k}{n-k}+\sum_{i=M}^{N}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i)+\sum_{i=N+1}^{n-1}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i) − n − k x k + i = M ∑ N ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) + i = N + 1 ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i )
we notice that the first term is negative, the first sum over i = M , … , N i=M,\ldots,N i = M , … , N non-negative, and the second sum negative. Recall that x n ≤ x k x_n\le x_k x n ≤ x k for all n ≥ M + 1 n\ge M+1 n ≥ M + 1 . Then we have, below separating the x N + 1 x_{N+1} x N + 1 term from the sum and grouping the remaining telescoping terms,
∑ i = N + 1 n − 1 ( H n − 1 − H n − i − 1 ) ( x i − x i + 1 ) = − x k n − k + ∑ i = M N ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) = ( H n − 1 − H n − N − 1 ) x N + 1 − x k n − k − ∑ i = M + 1 N x i n − i ≤ N n − N x k \begin{aligned}
\sum_{i=N+1}^{n-1}(H_{n-1}-H_{n-i-1})(x_i-x_{i+1})=-\frac{x_k}{n-k}+\sum_{i=M}^{N}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i) \\
&=(H_{n-1}-H_{n-N-1})x_{N+1}-\frac{x_k}{n-k}-\sum_{i=M+1}^{N}\frac{x_i}{n-i} \\
&\le\frac{N}{n-N}x_k
\end{aligned} i = N + 1 ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i − x i + 1 ) = − n − k x k + i = M ∑ N ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) = ( H n − 1 − H n − N − 1 ) x N + 1 − n − k x k − i = M + 1 ∑ N n − i x i ≤ n − N N x k
where in the final line we have simply dropped the negative terms in the upper bound and used that H n − 1 − H n − N − 1 ≤ N n − N H_{n-1}-H_{n-N-1}\le\frac{N}{n-N} H n − 1 − H n − N − 1 ≤ n − N N . We can now bound the error in the same manner as [8 ] : since H n − 1 − H n − i − 1 ≥ H n − 1 − H ⌊ n / 2 ⌋ − 1 ≥ ln ( 2 ) H_{n-1}-H_{n-i-1}\ge H_{n-1}-H_{\lfloor n/2\rfloor-1}\ge\ln(2) H n − 1 − H n − i − 1 ≥ H n − 1 − H ⌊ n /2 ⌋ − 1 ≥ ln ( 2 ) for ⌈ n / 2 ⌉ ≤ i ≤ n − 1 \lceil n/2\rceil\le i\le n-1 ⌈ n /2 ⌉ ≤ i ≤ n − 1 we have whenever ⌈ n / 2 ⌉ > N \lceil n/2\rceil>N ⌈ n /2 ⌉ > N
∣ x ⌈ n / 2 ⌉ − x n ∣ ≤ 1 ln ( 2 ) ∑ i = ⌈ n / 2 ⌉ n − 1 ( H n − 1 − H n − i − 1 ) ∣ x i − x i + 1 ∣ = 1 ln ( 2 ) ∑ i = ⌈ n / 2 ⌉ n − 1 ( H n − 1 − H n − i − 1 ) ( x i − x i + 1 ) ≤ 1 ln ( 2 ) N n − N x k \begin{aligned}
\left|x_{\lceil n/2\rceil}-x_n\right|\le\frac{1}{\ln(2)}\sum_{i=\lceil n/2\rceil}^{n-1}(H_{n-1}-H_{n-i-1})\left|x_i-x_{i+1}\right| \\
&=\frac{1}{\ln(2)}\sum_{i=\lceil n/2\rceil}^{n-1}(H_{n-1}-H_{n-i-1})(x_i-x_{i+1}) \\
&\le\frac{1}{\ln(2)}\frac{N}{n-N}x_k
\end{aligned} x ⌈ n /2 ⌉ − x n ≤ ln ( 2 ) 1 i = ⌈ n /2 ⌉ ∑ n − 1 ( H n − 1 − H n − i − 1 ) ∣ x i − x i + 1 ∣ = ln ( 2 ) 1 i = ⌈ n /2 ⌉ ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i − x i + 1 ) ≤ ln ( 2 ) 1 n − N N x k
since x i − x i + 1 > 0 x_i-x_{i+1}>0 x i − x i + 1 > 0 for i ≥ ⌈ n / 2 ⌉ > N i\ge\lceil n/2\rceil>N i ≥ ⌈ n /2 ⌉ > N . Writing x n − x = ( x n − x 2 n ) + ( x 2 n − x 4 n ) + … x_n-x=(x_n-x_{2n})+(x_{2n}-x_{4n})+\ldots x n − x = ( x n − x 2 n ) + ( x 2 n − x 4 n ) + … , we find
∣ x n − x ∣ ≤ N x k ln ( 2 ) ∑ j = 0 ∞ 1 2 j n − N ≤ 1 ln ( 2 ) N x k n − N ∑ j = 0 ∞ 1 2 j = 2 ln ( 2 ) N n − N x k |x_n-x|\le\frac{Nx_k}{\ln(2)}\sum_{j=0}^{\infty}\frac{1}{2^j n-N}\le\frac{1}{\ln(2)}\frac{Nx_k}{n-N}\sum_{j=0}^{\infty}\frac{1}{2^j}=\frac{2}{\ln(2)}\frac{N}{n-N}x_k ∣ x n − x ∣ ≤ ln ( 2 ) N x k j = 0 ∑ ∞ 2 j n − N 1 ≤ ln ( 2 ) 1 n − N N x k j = 0 ∑ ∞ 2 j 1 = ln ( 2 ) 2 n − N N x k
for ⌈ n / 2 ⌉ > N \lceil n/2\rceil>N ⌈ n /2 ⌉ > N . Lastly, for n ≥ 2 N n\ge2N n ≥ 2 N , n − N ≥ n / 2 ≥ ( n − M ) / 2 n-N\ge n/2\ge(n-M)/2 n − N ≥ n /2 ≥ ( n − M ) /2 , so N / ( n − N ) ≤ 2 N / ( n − M ) N/(n-N)\le2N/(n-M) N / ( n − N ) ≤ 2 N / ( n − M ) , and for M < n < 2 N M<n<2N M < n < 2 N , we have simply x n − x ≤ x n ≤ x k x_n-x\le x_n\le x_k x n − x ≤ x n ≤ x k while 2 N x k / ( n − M ) ≥ 2 N x k / n > x k 2Nx_k/(n-M)\ge2Nx_k/n>x_k 2 N x k / ( n − M ) ≥ 2 N x k / n > x k . In either case we obtain
∣ x n − x ∣ ≤ 4 ln ( 2 ) N n − M x k |x_n-x|\le\frac{4}{\ln(2)}\frac{N}{n-M}x_k ∣ x n − x ∣ ≤ ln ( 2 ) 4 n − M N x k
for 2 ≤ k < M 2\le k<M 2 ≤ k < M and some finite N ≥ M N\ge M N ≥ M . (Note that we are weakening our upper here in order to avoid having n − N = 0 n-N=0 n − N = 0 for n = N n=N n = N .) When instead k = 1 k=1 k = 1 , we decompose (43) as
− x k ( H n − 1 − H n − k − 1 ) + ∑ i = M N ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) + ∑ i = N + 1 n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) -x_k(H_{n-1}-H_{n-k-1})+\sum_{i=M}^{N}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i)+\sum_{i=N+1}^{n-1}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i) − x k ( H n − 1 − H n − k − 1 ) + i = M ∑ N ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) + i = N + 1 ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i )
and because the first term, still negative, was simply dropped in the previous argument, we obtain the same upper bound when 1 = k < M 1=k<M 1 = k < M .
Case 2 (Tail of x n x_n x n monotone increasing). Now consider when the sequence is monotone increasing, that is, when N N N is infinite. Then for 2 ≤ k < M 2\le k<M 2 ≤ k < M we instead decompose (43) as
− x k n − k + ∑ i = M n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) . -\frac{x_k}{n-k}+\sum_{i=M}^{n-1}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i). − n − k x k + i = M ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) .
The sum has non-negative terms, and we find simply
∑ i = M n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) = x k n − k ≤ k n − k x k . \sum_{i=M}^{n-1}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i)=\frac{x_k}{n-k}\le\frac{k}{n-k}x_k. i = M ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) = n − k x k ≤ n − k k x k .
Using a similar bound to before on ∣ x ⌈ n / 2 ⌉ − x n ∣ \left|x_{\lceil n/2\rceil}-x_n\right| x ⌈ n /2 ⌉ − x n whenever ⌈ n / 2 ⌉ ≥ M \lceil n/2\rceil\ge M ⌈ n /2 ⌉ ≥ M , that is,
∣ x ⌈ n / 2 ⌉ − x n ∣ ≤ 1 ln ( 2 ) k n − k x k , \left|x_{\lceil n/2\rceil}-x_n\right|\le\frac{1}{\ln(2)}\frac{k}{n-k}x_k, x ⌈ n /2 ⌉ − x n ≤ ln ( 2 ) 1 n − k k x k ,
we find
∣ x n − x ∣ ≤ x k ln ( 2 ) ∑ j = 0 ∞ 1 2 j n − k ≤ 1 ln ( 2 ) x k n − k ∑ j = 0 ∞ 1 2 j ≤ 2 ln ( 2 ) k n − k x k |x_n-x|\le\frac{x_k}{\ln(2)}\sum_{j=0}^{\infty}\frac{1}{2^j n-k}\le\frac{1}{\ln(2)}\frac{x_k}{n-k}\sum_{j=0}^{\infty}\frac{1}{2^j}\le\frac{2}{\ln(2)}\frac{k}{n-k}x_k ∣ x n − x ∣ ≤ ln ( 2 ) x k j = 0 ∑ ∞ 2 j n − k 1 ≤ ln ( 2 ) 1 n − k x k j = 0 ∑ ∞ 2 j 1 ≤ ln ( 2 ) 2 n − k k x k
for ⌈ n / 2 ⌉ ≥ M \lceil n/2\rceil\ge M ⌈ n /2 ⌉ ≥ M . For M ≤ n < 2 M M \le n < 2M M ≤ n < 2 M , we again have the trivial bound x n − x ≤ x n ≤ x k ≤ 2 M x k / ( n − M ) x_n-x \le x_n \le x_k \le2Mx_k/(n-M) x n − x ≤ x n ≤ x k ≤ 2 M x k / ( n − M ) . As before, we loosen the bound to
∣ x n − x ∣ ≤ 4 ln ( 2 ) M n − M x k , |x_n-x| \le\frac{4}{\ln(2)}\frac{M}{n-M}x_k, ∣ x n − x ∣ ≤ ln ( 2 ) 4 n − M M x k ,
for 2 ≤ k < M 2 \le k < M 2 ≤ k < M , to match our previous bound. When 1 = k < M 1 = k < M 1 = k < M , we instead write (43) as
− x k ( H n − 1 − H n − k − 1 ) + ∑ i = M n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) , -x_k(H_{n-1}-H_{n-k-1})+\sum_{i=M}^{n-1}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i), − x k ( H n − 1 − H n − k − 1 ) + i = M ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) ,
from which
∑ i = M n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) = x k ( H n − 1 − H n − k − 1 ) ≤ k n − k x k , \sum_{i=M}^{n-1}(H_{n-1}-H_{n-i-1})(x_{i+1}-x_i)=x_k(H_{n-1}-H_{n-k-1})\le\frac{k}{n-k}x_k, i = M ∑ n − 1 ( H n − 1 − H n − i − 1 ) ( x i + 1 − x i ) = x k ( H n − 1 − H n − k − 1 ) ≤ n − k k x k ,
and the same upper bound follows.
When 1 = k = M 1=k=M 1 = k = M , we found in Lemma 4.1 that the sequence is constant, so the error bound holds trivially.
Proof of Corollary 2.3. Let ( x n ( k ) ) (x_n^{(k)}) ( x n ( k ) ) be the sequence determined by (29) with the initial conditions x n ( k ) = 0 x_n^{(k)}=0 x n ( k ) = 0 for n ≤ M n\le M n ≤ M except x k ( k ) = x k > 0 x_k^{(k)}=x_k>0 x k ( k ) = x k > 0 . Then as before
x M + 1 ( k ) = p ( M + 1 , k ) x k x_{M+1}^{(k)}=p(M+1,k)x_k x M + 1 ( k ) = p ( M + 1 , k ) x k
and by linearity of (10) we find
x M + 1 = ∑ k = 1 M p ( M + 1 , k ) x k = ∑ k = 1 M x M + 1 ( k ) . x_{M+1}=\sum_{k=1}^{M}p(M+1,k)x_k=\sum_{k=1}^{M}x_{M+1}^{(k)}. x M + 1 = k = 1 ∑ M p ( M + 1 , k ) x k = k = 1 ∑ M x M + 1 ( k ) .
It follows by induction (and again linearity) that x n = ∑ k = 1 M x n ( k ) x_n=\sum_{k=1}^{M}x_n^{(k)} x n = ∑ k = 1 M x n ( k ) for all n ≥ M + 1 n\ge M+1 n ≥ M + 1 . Define x ( k ) = lim n → ∞ x n ( k ) x^{(k)}=\lim_{n\to\infty}x_n^{(k)} x ( k ) = lim n → ∞ x n ( k ) and x : = ∑ k = 1 M x ( k ) x:=\sum_{k=1}^{M}x^{(k)} x := ∑ k = 1 M x ( k ) , and let N k N_k N k be defined as N N N before for the sequence x n ( k ) x_n^{(k)} x n ( k ) . Then by Theorem 2.2 (ii) we have
∣ x n − x ∣ ≤ ∑ k = 1 M ∣ x n ( k ) − x ( k ) ∣ ≤ 4 ln ( 2 ) N ′ n − M ∑ k = 1 M x k , |x_n-x|\le\sum_{k=1}^{M}|x_n^{(k)}-x^{(k)}|\le\frac{4}{\ln(2)}\frac{N'}{n-M}\sum_{k=1}^{M}x_k, ∣ x n − x ∣ ≤ k = 1 ∑ M ∣ x n ( k ) − x ( k ) ∣ ≤ ln ( 2 ) 4 n − M N ′ k = 1 ∑ M x k ,
where N ′ : = max 1 ≤ k ≤ M N k N':=\max_{1\le k\le M}N_k N ′ := max 1 ≤ k ≤ M N k .
References
Acknowledgments
Acknowledgments. The author used Claude Sonnet 5.5 during the preparation of this manuscript for proofreading and copyediting purposes. LLMs were not otherwise used to generate the content of this work, and all proofs and writing in the manuscript were produced by the author.