Introduction
Dynamic graph models have emerged as useful tools for modeling systems whose interaction structure changes over time. Examples include social networks, where the times at which interactions occur form an essential part of the data [7 ] , and stochastic graph-rewriting models for biochemical systems [6]. More broadly, random graph theory contains a wide variety of static and evolving models. It started with the classical Erdős–Rényi random graph process [21 ] , which has been extensively studied and is nowadays well-covered by [9 , 27 ] and ranges to more recent models for social networks like the preferential attachment model surveyed by Albert and Barabási [1].
In the classical dynamic models there is typically no or no strict separation between the growth in the number of vertices and the growth in the number of edges, see [14 ] [1]. For instance, in the Erdős–Rényi models the number of vertices, say n n n , is fixed and the number of edges grows. Then one lets n n n tend to infinity and studies asymptotic properties, where a dependence on n n n for the number of edges is usually imposed on the model. In [23 ] a new random graph growth model is suggested where the size as well as the order of a graph may grow according to the inherent structure of the graph process itself. Classical accounts on dynamic random graphs focus on the study of several popular models such as the copying model, the small-world graph, and the preferential attachment model as well as variations in [10 ] , power law graphs and duplication models (static and dynamic) in [12 ] and the treatment largely based branching processes in [20 ] .
In this paper, we study a process on multi-graphs which may grow independently with respect to order as well as size and where the vertices and the edges receive a time stamp. The evolution is accomplished through one of two operations at each discrete time step: the creation of a new vertex or the addition of an edge between two existing vertices. There are several ways to do that and in this work we consider two particular models: the undirected independent growth model (UIG-model) with undirected edges and where no loops are allowed, and the directed independent growth model (DIG-model) with directed edges and where loops are allowed.
For both models, the counting sequence is related to the Legendre–Stirling numbers introduced in [22 ] . The counting sequence for the UIG-model is, up to a one-step shift, OEIS A124373, while the DIG-model gives the sequence of generalized Bell numbers, OEIS A135920. These sequences belong to a broader algebraic framework of polynomial base changes that traces back to Carlitz [11 ] and arises naturally in spectral analysis [22 ] . It was later systematically extended to the Legendre–Stirling framework by Andrews and Littlejohn [2, 3], who also gave a combinatorial interpretation in terms of certain set partitions over sets of integers present in two colors. Across these families, the counting sequences satisfy analogous recurrence relations, and the functional equations for their generating functions differ only by a single parameter. Furthermore, they all admit natural graph-theoretic interpretations as special instances of the diagram families studied in [8 ] .
Our contributions are twofold. First, we derive explicit formulas and asymptotic expressions for the number of random graphs obtainable in n n n steps. We regard these graphs as combinatorial structures in the sense of analytic combinatorics and use the machinery developed in [24 ] to derive differential equations for the generating functions associated with these graphs, which are then analyzed asymptotically. The generating functions we encounter have a radius of convergence equal to zero. In the UIG-model, we express the coefficients as sums involving Bessel functions. The terms of the sum are Gaussian and therefore the asymptotic analysis can be based on the discrete Laplace method (see [24 p. 761–762] ). For the DIG-model, we transform the generating function with a rescaled Borel transform [5] (see also [16 ] for a general introduction to Borel transforms), making it entire after all. For the transformed function we obtain an explicit closed form. We show that it is Hayman admissible [26 ] in one variable.
Second, we analyze the distribution of the number of vertices that are created after n n n steps in both models. In the UIG-model, a perturbed discrete Laplace method applies and so we show a central limit theorem. The Borel transform of the bivariate function of the DIG-model is shown to be e-admissible [18 ] , which yields a normal limit law. We note that in the extended abstract of this work [4], a custom modification of bivariate Hayman admissibility [25 ] was developed to prove the limit theorem. Bivariate Hayman admissibility is an inherently stronger concept, as it establishes a full bivariate normal distribution. However, since our generating function narrowly misses its conditions, we opt for e-admissibility in this work, which presents a cleaner and more direct approach to derive the result without the need for a conceptual extension.
The paper is organized as follows. Section 2 presents the UIG-model and is devoted to the asymptotic number of graphs that can be generated in n n n growth steps. Section 3 is devoted to the central limit theorem for the distribution of the number of vertices in that model. Out of a desire to tune the growth rate of the number of vertices relative to that for the number of edges, we briefly discuss a weighted version of this the UIG-model in Section 4. The DIG-model is introduced in Section 5, where we derive the asymptotic number of graphs that can be generated in n n n steps. The central limit theorem for the number of vertices is shown in Section 6. An interesting correspondence to set partitions into even-sized subsets is presented in Section 7. This correspondence can be used to design a uniform sampling algorithm based on Boltzmann samplers [19 ] , which we present in Section 8.
Notations and facts. Throughout the paper we write ∂ x \partial_x ∂ x for denoting the partial derivative with respect to x x x . For sequences ( a n ) n ∈ N (a_n)_{n\in\mathbb{N}} ( a n ) n ∈ N and ( b n ) n ∈ N (b_n)_{n\in\mathbb{N}} ( b n ) n ∈ N we write a n ≍ b n a_n \asymp b_n a n ≍ b n synonymous to a n = Θ ( b n ) a_n = \Theta(b_n) a n = Θ ( b n ) .
We denote by j ν , 1 j_{\nu,1} j ν , 1 the smallest positive zero of the Bessel function J ν J_\nu J ν . It is well-known that for ν > − 1 \nu> -1 ν > − 1 the Bessel function J ν ( z ) J_\nu(z) J ν ( z ) is positive on the interval ( 0 , j ν , 1 ) (0,j_{\nu,1}) ( 0 , j ν , 1 ) . Moreover, ν ↦ j ν , 1 \nu\mapsto j_{\nu,1} ν ↦ j ν , 1 is increasing, j ν , 1 > ν j_{\nu,1} > \nu j ν , 1 > ν , and j 1 , 1 = 3.8317 … j_{1,1} = 3.8317\ldots j 1 , 1 = 3.8317 … , see [17 §10.21] .
The UIG-model: undirected graphs without loops
We start out by describing the first graph evolution model we want to analyze. At each discrete time step we create a vertex or an edge and each created item gets a time stamp. Precisely, either (i) a new vertex is created, or (ii) a new undirected edge is added between two distinct existing vertices. The two vertices may already be adjacent. So, loops are forbidden while multiple edges are allowed. We investigate the bivariate generating function that corresponding to all histories generated by this process and keeping track of the number of steps and the number of vertices.
Definition 1. A history in the UIG-model is a multigraph obtained by the construction described above, using steps (i) and (ii), such that each vertex and each edge receives a time stamp.
Thus, a history records not only the resulting multigraph but also the order in which its vertices and edges were created. In particular, two histories may have the same underlying multigraph while differing in their time labels.
Note that the time stamps are not labels in the classical sense of analytic combinatorics, as there are restrictions on where to put them. For instance, two vertices are needed to create edges. So, no edge can have time stamp one or two. So, technically, the class of histories is an unlabelled combinatorial class in the sense of [24 ] , which means that we have to set up ordinary generating functions. To this end, let the variable t t t mark time (number of steps) and u u u mark the number of vertices, i.e. , write
T ( t , u ) = ∑ n ≥ 0 ∑ m ≥ 0 T n , m t n u m T(t,u) = \sum_{n\geq0}\sum_{m\geq0} T_{n,m}t^n u^m T ( t , u ) = n ≥ 0 ∑ m ≥ 0 ∑ T n , m t n u m
where the coefficient T n , m = [ t n u m ] T ( t , u ) T_{n,m} = [t^n u^m]T(t,u) T n , m = [ t n u m ] T ( t , u ) is the number of histories that can be generated in n n n steps and have m m m vertices (and hence n − m n-m n − m edges). A step creating a vertex corresponds to a factor u t ut u t in the generating function, as we add a vertex and a step. When creating an edge, we must add a step and then choose two distinct vertices. This amounts to two pointing-and-removing operations and then reverting the removals. Moreover, as the edge is undirected, the order of the vertices must not be taken into account. After all, this yields the following differential equation for the generating function T ( t , u ) T(t,u) T ( t , u ) :
T ( t , u ) = 1 + u t T ( t , u ) + u 2 t 2 ∂ u 2 T ( t , u ) . T(t,u)=1+utT(t,u)+\frac{u^2t}{2}\partial_u^2T(t,u). T ( t , u ) = 1 + u tT ( t , u ) + 2 u 2 t ∂ u 2 T ( t , u ) .
Equivalently, as a formal power series in t t t ,
T ( t , u ) = ∑ m ≥ 0 ∏ k = 1 m t u 1 − ( k 2 ) t . (1) T(t,u)=\sum_{m\geq0}\prod_{k=1}^{m}\frac{tu}{1-\binom{k}{2}t}. \tag*{(1)} T ( t , u ) = m ≥ 0 ∑ k = 1 ∏ m 1 − ( 2 k ) t t u . (1)
This can be seen, as each vertex creation yields a factor t u tu t u and after having created k k k vertices so far, there are ( k 2 ) \binom{k}{2} ( 2 k ) possibilities for each edge that is created before the creation of the ( k + 1 ) (k+1) ( k + 1 ) -th vertex.
We are primarily interested in asymptotics of [ t n ] T ( t , 1 ) [t^n]T(t,1) [ t n ] T ( t , 1 ) , as n → ∞ n\to\infty n → ∞ . The first few terms can be seen from the expansion
T ( t , 1 ) = 1 + t + t 2 + 2 t 3 + 6 t 4 + 25 t 5 + 135 t 6 + 909 t 7 + O ( t 8 ) . T(t,1)=1+t+t^2+2t^3+6t^4+25t^5+135t^6+909t^7+O\left(t^8\right). T ( t , 1 ) = 1 + t + t 2 + 2 t 3 + 6 t 4 + 25 t 5 + 135 t 6 + 909 t 7 + O ( t 8 ) .
Remark 1. The m m m -th summand in (1) has poles at t = 2 / ( k ( k − 1 ) ) t=2/(k(k-1)) t = 2/ ( k ( k − 1 )) for k = 2 , … , m k=2,\ldots,m k = 2 , … , m . Thus, the poles of T ( t , 1 ) T(t,1) T ( t , 1 ) accumulate at t = 0 t=0 t = 0 and hence the radius of convergence of the series T ( t , 1 ) T(t,1) T ( t , 1 ) is zero unless there are some miraculous cancellations. (Note that for any z > 0 z>0 z > 0 the sum has positive and negative terms!) But a simple lower bound shows that this is indeed the case: Take 1 ≤ k ≤ n 1\leq k\leq n 1 ≤ k ≤ n and consider the histories that first create k k k vertices and then n − k n-k n − k edges. They are easy to count and yield [ t n ] T ( t , 1 ) ≥ ( k 2 ) n − k [t^n]T(t,1)\geq\binom{k}{2}^{n-k} [ t n ] T ( t , 1 ) ≥ ( 2 k ) n − k . Choosing k = ⌊ n ⌋ k=\lfloor\sqrt{n}\rfloor k = ⌊ n ⌋ gives ( [ t n ] T ( t , 1 ) ) 1 / n → ∞ ([t^n]T(t,1))^{1/n}\to\infty ([ t n ] T ( t , 1 ) ) 1/ n → ∞ . To circumvent this problem, the asymptotic analysis is performed at the coefficient level rather than by classical singularity analysis at a dominant singularity.
Proposition 1. For n ≥ 1 n\geq1 n ≥ 1 , the coefficients of T ( t , u ) T(t,u) T ( t , u ) are given by
[ t n ] T ( t , u ) = ∑ r = 1 n u r ∑ k = 1 r ( k 2 ) n − 1 ( − 1 ) k − r 2 r − 1 ( 2 k − 1 ) ( k + r − 1 ) ! ( r − k ) ! . (2) [t^n]T(t,u)=\sum_{r=1}^{n}u^r\sum_{k=1}^{r}\frac{\binom{k}{2}^{n-1}(-1)^{k-r}2^{r-1}(2k-1)}{(k+r-1)!(r-k)!}. \tag*{(2)} [ t n ] T ( t , u ) = r = 1 ∑ n u r k = 1 ∑ r ( k + r − 1 )! ( r − k )! ( 2 k ) n − 1 ( − 1 ) k − r 2 r − 1 ( 2 k − 1 ) . (2) with the convention 0 0 = 1 0^0=1 0 0 = 1 . In particular, for u = 1 u=1 u = 1 , there is a constant c > 0 c>0 c > 0 such that
[ t n ] T ( t , 1 ) = ∑ k = 1 2 n ( k 2 ) n − 1 2 k − 1 2 J 2 k − 1 ( 2 2 ) + O ( e − c n log n ) . (3) [t^n]T(t,1)=\sum_{k=1}^{2n}\binom{k}{2}^{n-1}\frac{2k-1}{\sqrt{2}}J_{2k-1}(2\sqrt{2})+O\left(e^{-cn\log n}\right). \tag*{(3)} [ t n ] T ( t , 1 ) = k = 1 ∑ 2 n ( 2 k ) n − 1 2 2 k − 1 J 2 k − 1 ( 2 2 ) + O ( e − c n l o g n ) . (3) where J α ( z ) J_\alpha(z) J α ( z ) denotes the Bessel function of the first kind.
Proof. We decompose the product into partial fractions. One obtains
T ( t , u ) = 1 + ∑ r = 0 ∞ u r ∑ k = 1 r t 1 − ( k 2 ) t ∏ s = 1 k − 1 1 ( k 2 ) − ( s 2 ) ∏ s = k + 1 r 1 ( k 2 ) − ( s 2 ) . T(t,u)=1+\sum_{r=0}^{\infty}u^r\sum_{k=1}^{r}\frac{t}{1-\binom{k}{2}t}\prod_{s=1}^{k-1}\frac{1}{\binom{k}{2}-\binom{s}{2}}\prod_{s=k+1}^{r}\frac{1}{\binom{k}{2}-\binom{s}{2}}. T ( t , u ) = 1 + r = 0 ∑ ∞ u r k = 1 ∑ r 1 − ( 2 k ) t t s = 1 ∏ k − 1 ( 2 k ) − ( 2 s ) 1 s = k + 1 ∏ r ( 2 k ) − ( 2 s ) 1 .
Using the Gamma function, this can be rewritten as
T ( t , u ) = 1 + ∑ r = 0 ∞ u r ∑ k = 1 r t ( − 1 ) k − r 2 r − 1 ( 2 k − 1 ) ( 1 − ( k 2 ) t ) Γ ( k + r ) Γ ( r + 1 − k ) . T(t,u)=1+\sum_{r=0}^{\infty}u^r\sum_{k=1}^{r}\frac{t(-1)^{k-r}2^{r-1}(2k-1)}{\left(1-\binom{k}{2}t\right)\Gamma(k+r)\Gamma(r+1-k)}. T ( t , u ) = 1 + r = 0 ∑ ∞ u r k = 1 ∑ r ( 1 − ( 2 k ) t ) Γ ( k + r ) Γ ( r + 1 − k ) t ( − 1 ) k − r 2 r − 1 ( 2 k − 1 ) .
Observe that the r r r -th summand in the original product (1) is of order O ( t r ) O(t^r) O ( t r ) . Therefore, any term with r > n r>n r > n does not contribute to the coefficient of t n t^n t n . Extracting the coefficient of t n t^n t n from the terms 1 ≤ r ≤ n 1\le r\le n 1 ≤ r ≤ n yields (2). Setting u = 1 u=1 u = 1 and rewriting the resulting expression in terms of Bessel functions gives
[ t n ] T ( t , 1 ) = ∑ k > 1 ( k 2 ) n − 1 2 k − 1 2 J 2 k − 1 ( 2 2 ) . [t^n]T(t,1)=\sum_{k>1}\binom{k}{2}^{n-1}\frac{2k-1}{\sqrt{2}}J_{2k-1}(2\sqrt{2}). [ t n ] T ( t , 1 ) = k > 1 ∑ ( 2 k ) n − 1 2 2 k − 1 J 2 k − 1 ( 2 2 ) .
It remains to show that this sum may be truncated at k = 2 n k=2n k = 2 n with a superexponentially small error. For fixed z z z and ν → ∞ \nu\to\infty ν → ∞ , we use the standard large-order estimate
J ν ( z ) = 1 Γ ( ν + 1 ) ( z 2 ) ν ( 1 + O ( ν − 1 ) ) . J_\nu(z)=\frac{1}{\Gamma(\nu+1)}\left(\frac{z}{2}\right)^\nu\left(1+O(\nu^{-1})\right). J ν ( z ) = Γ ( ν + 1 ) 1 ( 2 z ) ν ( 1 + O ( ν − 1 ) ) .
With z = 2 2 z=2\sqrt{2} z = 2 2 and ν = 2 k − 1 \nu=2k-1 ν = 2 k − 1 , Stirling’s formula gives
J 2 k − 1 ( 2 2 ) = 1 4 π k exp ( − 2 k log k + O ( k ) ) . J_{2k-1}(2\sqrt{2})=\frac{1}{\sqrt{4\pi k}}\exp(-2k\log k+O(k)). J 2 k − 1 ( 2 2 ) = 4 π k 1 exp ( − 2 k log k + O ( k )) .
On the other hand,
( k 2 ) n − 1 = exp ( 2 n log k + O ( n ) ) . \binom{k}{2}^{n-1}=\exp(2n\log k+O(n)). ( 2 k ) n − 1 = exp ( 2 n log k + O ( n )) .
Hence the logarithm of the absolute value of the k k k -th summand in the Bessel representation is bounded by
2 n log k − 2 k log k + O ( k + n ) . 2n\log k-2k\log k+O(k+n). 2 n log k − 2 k log k + O ( k + n ) .
For k > 2 n k>2n k > 2 n this is at most
− k log k + O ( k ) , -k\log k+O(k), − k log k + O ( k ) ,
and therefore, for all sufficiently large n n n ,
∑ k > 2 n ( k 2 ) n − 1 2 k − 1 2 ∣ J 2 k − 1 ( 2 2 ) ∣ = O ( e − c n log n ) \sum_{k>2n}\binom{k}{2}^{n-1}\frac{2k-1}{\sqrt{2}}\left|J_{2k-1}(2\sqrt{2})\right|=O\left(e^{-cn\log n}\right) k > 2 n ∑ ( 2 k ) n − 1 2 2 k − 1 J 2 k − 1 ( 2 2 ) = O ( e − c n l o g n )
for some constant c > 0 c>0 c > 0 . This proves (3). □
Asymptotic analysis
By (3), it remains to estimate
S n = ∑ k = 2 2 n ( k 2 ) n − 1 2 k − 1 2 J 2 k − 1 ( 2 2 ) = ∑ k = 2 2 n exp ( Φ n ( k ) ) , S_n=\sum_{k=2}^{2n}\binom{k}{2}^{n-1}\frac{2k-1}{\sqrt{2}}J_{2k-1}(2\sqrt{2})=\sum_{k=2}^{2n}\exp(\Phi_n(k)), S n = k = 2 ∑ 2 n ( 2 k ) n − 1 2 2 k − 1 J 2 k − 1 ( 2 2 ) = k = 2 ∑ 2 n exp ( Φ n ( k )) ,
where
Φ n ( x ) = ( n − 1 ) ( log x + log ( x − 1 ) − log 2 ) + log ( 2 x − 1 ) − 1 2 log 2 + log J 2 x − 1 ( 2 2 ) . (4) \Phi_n(x)=(n-1)(\log x+\log(x-1)-\log2)+\log(2x-1)-\frac{1}{2}\log2+\log J_{2x-1}(2\sqrt{2}). \tag*{(4)} Φ n ( x ) = ( n − 1 ) ( log x + log ( x − 1 ) − log 2 ) + log ( 2 x − 1 ) − 2 1 log 2 + log J 2 x − 1 ( 2 2 ) . (4)
Remark 2. Note that for n ≥ 2 n\ge2 n ≥ 2 the first term of the sum in (2) is zero. Thus, we define S n S_n S n as sum starting at k = 2 k=2 k = 2 and avoid the singularity of the logarithm in (4).
Remark 3. Recall the notations and facts on Bessel function presented at the end of Section 1. As x ≥ 1 x\ge1 x ≥ 1 , we have j 2 x − 1 , 1 ≥ j 1 , 1 > 2 2 j_{2x-1,1}\ge j_{1,1}>2\sqrt{2} j 2 x − 1 , 1 ≥ j 1 , 1 > 2 2 and hence J 2 x − 1 ( 2 2 ) > 0 J_{2x-1}(2\sqrt{2})>0 J 2 x − 1 ( 2 2 ) > 0 for all real x > 1 x>1 x > 1 . Thus Φ n \Phi_n Φ n is well defined and smooth on ( 1 , ∞ ) (1,\infty) ( 1 , ∞ ) (in fact, the Bessel function J ν ( z ) J_\nu(z) J ν ( z ) is analytic in ν \nu ν ). In particular, all summands of S n S_n S n are positive.
We apply the discrete Laplace method to determine the asymptotic behaviour of S n S_n S n and show the following result.
Theorem 1. Let W W W denote the principal Lambert W-function [15 ] , defined for x > 0 x>0 x > 0 by
W ( x ) e W ( x ) = x . W(x)e^{W(x)}=x. W ( x ) e W ( x ) = x . The number of undirected histories that can be generated in exactly n n n steps satisfies
[ t n ] T ( t , 1 ) ∼ 2 W ( n 2 ) n 2 2 n 1 + W ( n 2 ) exp ( 2 n ( W ( n 2 ) − 1 + 1 W ( n 2 ) ) ) . [t^n]T(t,1)\sim\sqrt{2}\,\frac{W\left(n\sqrt{2}\right)}{n2^{2n}\sqrt{1+W\left(n\sqrt{2}\right)}}\exp\left(2n\left(W\left(n\sqrt{2}\right)-1+\frac{1}{W\left(n\sqrt{2}\right)}\right)\right). [ t n ] T ( t , 1 ) ∼ 2 n 2 2 n 1 + W ( n 2 ) W ( n 2 ) exp ( 2 n ( W ( n 2 ) − 1 + W ( n 2 ) 1 ) ) .
Proof. Throughout the proof we write
ω n : = W ( n 2 ) . \omega_n:=W\left(n\sqrt{2}\right). ω n := W ( n 2 ) .
We also set
f ( x ) : = J 2 x − 1 ( 2 2 ) . f(x):=J_{2x-1}(2\sqrt{2}). f ( x ) := J 2 x − 1 ( 2 2 ) .
Step 1: Estimates for the Bessel factor. From the series expansion of the Bessel function we have, for x x x tending to infinity,
f ( x ) = ∑ ℓ ≥ 0 ( − 1 ) ℓ 2 ℓ + x − 1 2 ℓ ! Γ ( ℓ + 2 x ) = 2 x − 1 2 Γ ( 2 x ) ( 1 − 1 x + O ( 1 x 2 ) ) . (5) f(x)=\sum_{\ell\geq0}\frac{(-1)^\ell2^{\ell+x-\frac{1}{2}}}{\ell!\,\Gamma(\ell+2x)}=\frac{2^{x-\frac{1}{2}}}{\Gamma(2x)}\left(1-\frac{1}{x}+O\left(\frac{1}{x^2}\right)\right). \tag*{(5)} f ( x ) = ℓ ≥ 0 ∑ ℓ ! Γ ( ℓ + 2 x ) ( − 1 ) ℓ 2 ℓ + x − 2 1 = Γ ( 2 x ) 2 x − 2 1 ( 1 − x 1 + O ( x 2 1 ) ) . (5)
Consequently,
log f ( x ) = ( x − 1 2 ) log 2 − log Γ ( 2 x ) + O ( 1 x ) . \log f(x)=\left(x-\frac{1}{2}\right)\log2-\log\Gamma(2x)+O\left(\frac{1}{x}\right). log f ( x ) = ( x − 2 1 ) log 2 − log Γ ( 2 x ) + O ( x 1 ) .
Furthermore, by differentiating the series termwise and using the standard digamma expansion
Γ ′ ( z ) Γ ( z ) = log z − 1 2 z + O ( 1 z 2 ) , z → ∞ , \frac{\Gamma'(z)}{\Gamma(z)}=\log z-\frac{1}{2z}+O\left(\frac{1}{z^2}\right),\qquad z\to\infty, Γ ( z ) Γ ′ ( z ) = log z − 2 z 1 + O ( z 2 1 ) , z → ∞ ,
we get
f ′ ( x ) f ( x ) = log 2 − 2 log ( 2 x ) + 1 2 x + O ( log x x 2 ) , as x → ∞ . (6) \frac{f'(x)}{f(x)}=\log2-2\log(2x)+\frac{1}{2x}+O\left(\frac{\log x}{x^2}\right),\qquad\text{as }x\to\infty. \tag*{(6)} f ( x ) f ′ ( x ) = log 2 − 2 log ( 2 x ) + 2 x 1 + O ( x 2 log x ) , as x → ∞. (6)
Differentiating the preceding asymptotic expansion gives, as x → ∞ x\to\infty x → ∞ ,
( f ′ f ) ′ ( x ) = − 2 x − 1 2 x 2 + O ( log x x 3 ) , (7) \left(\frac{f'}{f}\right)'(x)=-\frac{2}{x}-\frac{1}{2x^2}+O\left(\frac{\log x}{x^3}\right), \tag*{(7)} ( f f ′ ) ′ ( x ) = − x 2 − 2 x 2 1 + O ( x 3 log x ) , (7)
and
( f ′ f ) ′ ′ ( x ) = O ( 1 x 2 ) . (8) \left(\frac{f'}{f}\right)''(x)=O\left(\frac{1}{x^2}\right). \tag*{(8)} ( f f ′ ) ′′ ( x ) = O ( x 2 1 ) . (8)
Step 2: Location of the saddle point. Differentiating (4) gives
Φ n ′ ( x ) = ( n − 1 ) ( 1 x + 1 x − 1 ) + 2 2 x − 1 + f ′ ( x ) f ( x ) . \Phi_n'(x)=(n-1)\left(\frac{1}{x}+\frac{1}{x-1}\right)+\frac{2}{2x-1}+\frac{f'(x)}{f(x)}. Φ n ′ ( x ) = ( n − 1 ) ( x 1 + x − 1 1 ) + 2 x − 1 2 + f ( x ) f ′ ( x ) .
Using (6) and expanding in powers of 1 / x 1/x 1/ x , we obtain
Φ n ′ ( x ) = 2 n x − 2 log x − log 2 − 1 2 x + O ( n x 2 ) . (9) \Phi_n'(x)=\frac{2n}{x}-2\log x-\log2-\frac{1}{2x}+O\left(\frac{n}{x^2}\right). \tag*{(9)} Φ n ′ ( x ) = x 2 n − 2 log x − log 2 − 2 x 1 + O ( x 2 n ) . (9)
Existence and uniqueness of the critical point. By (7) there is X 0 > 1 X_0>1 X 0 > 1 , independent of n n n , such that ( f ′ / f ) ′ ( x ) < 0 \left(f'/f\right)'(x)<0 ( f ′ / f ) ′ ( x ) < 0 for x ≥ X 0 x\geq X_0 x ≥ X 0 . Since
Φ n ′ ′ ( x ) = − ( n − 1 ) ( 1 x 2 + 1 ( x − 1 ) 2 ) − 4 ( 2 x − 1 ) 2 + ( f ′ f ) ′ ( x ) , \Phi_n''(x)=-(n-1)\left(\frac{1}{x^2}+\frac{1}{(x-1)^2}\right)-\frac{4}{(2x-1)^2}+\left(\frac{f'}{f}\right)'(x), Φ n ′′ ( x ) = − ( n − 1 ) ( x 2 1 + ( x − 1 ) 2 1 ) − ( 2 x − 1 ) 2 4 + ( f f ′ ) ′ ( x ) ,
all terms are negative on [ X 0 , ∞ ) [X_0,\infty) [ X 0 , ∞ ) , so Φ n ′ \Phi'_n Φ n ′ is strictly decreasing there. Note that f f f is analytic in C \mathbb{C} C and positive on the compact interval [ 1 , X 0 ] [1,X_0] [ 1 , X 0 ] . So, f ′ / f f'/f f ′ / f is continuous there and hence bounded by some constant C C C . Therefore, Φ n ′ ( x ) ≥ 2 ( n − 1 ) / X 0 − C > 0 \Phi'_n(x) \ge2(n-1)/X_0-C>0 Φ n ′ ( x ) ≥ 2 ( n − 1 ) / X 0 − C > 0 for x ∈ ( 1 , X 0 ] x\in(1,X_0] x ∈ ( 1 , X 0 ] and all sufficiently large n n n . Finally, Φ n ′ ( x ) → − ∞ \Phi'_n(x)\to-\infty Φ n ′ ( x ) → − ∞ as x → ∞ x\to\infty x → ∞ by (9) . Consequently, for all sufficiently large n n n , Φ n ′ \Phi'_n Φ n ′ has exactly one zero x ⋆ ∈ ( X 0 , ∞ ) x^\star\in(X_0,\infty) x ⋆ ∈ ( X 0 , ∞ ) ; Φ n \Phi_n Φ n is increasing on ( 1 , x ⋆ ] (1,x^\star] ( 1 , x ⋆ ] and decreasing on [ x ⋆ , ∞ ) [x^\star,\infty) [ x ⋆ , ∞ ) , and attains its unique maximum at x ⋆ x^\star x ⋆ .
Asymptotic location. From the saddle-point equation Φ n ′ ( x ) = 0 \Phi'_n(x)=0 Φ n ′ ( x ) = 0 , we obtain the asymptotic saddle-point equation
n x ∼ log ( x 2 ) , n → ∞ . \frac{n}{x}\sim\log\left(x\sqrt{2}\right),\qquad n\to\infty. x n ∼ log ( x 2 ) , n → ∞.
To solve this equation, set y = n / x y=n/x y = n / x . Then
y = log ( n 2 y ) , y=\log\left(\frac{n\sqrt{2}}{y}\right), y = log ( y n 2 ) ,
and hence
y e y = n 2 . ye^y=n\sqrt{2}. y e y = n 2 .
Therefore,
y = W ( n 2 ) = : ω n , x = n ω n . y=W\left(n\sqrt{2}\right)=:\omega_n,\qquad x=\frac{n}{\omega_n}. y = W ( n 2 ) =: ω n , x = ω n n .
Now let x ⋆ x^\star x ⋆ denote the solution of the saddle-point equation Φ n ′ ( x ) = 0 \Phi'_n(x)=0 Φ n ′ ( x ) = 0 . Writing v = log ( x ⋆ 2 ) v=\log(x^\star\sqrt{2}) v = log ( x ⋆ 2 ) , the saddle-point equation becomes
n x ⋆ = v + O ( 1 x ⋆ ) + O ( n ( x ⋆ ) 2 ) . \frac{n}{x^\star}=v+O\left(\frac{1}{x^\star}\right)+O\left(\frac{n}{(x^\star)^2}\right). x ⋆ n = v + O ( x ⋆ 1 ) + O ( ( x ⋆ ) 2 n ) .
Since x ⋆ x^\star x ⋆ is of order n / ω n n/\omega_n n / ω n , this implies
n x ⋆ = v + O ( ω n 2 n ) . \frac{n}{x^\star}=v+O\left(\frac{\omega_n^2}{n}\right). x ⋆ n = v + O ( n ω n 2 ) .
Using x ⋆ = e v / 2 x^\star=e^v/\sqrt{2} x ⋆ = e v / 2 , we obtain
v e v = n 2 + O ( ω n ) . ve^v=n\sqrt{2}+O(\omega_n). v e v = n 2 + O ( ω n ) .
By the mean value theorem applied to z ↦ z e z z\mapsto ze^z z ↦ z e z , and since
∂ v ( v e v ) ∣ v = ω n = ( 1 + ω n ) e ω n ≍ n . \left.\partial_v(ve^v)\right|_{v=\omega_n}=(1+\omega_n)e^{\omega_n}\asymp n. ∂ v ( v e v ) ∣ v = ω n = ( 1 + ω n ) e ω n ≍ n .
we obtain
v = ω n + O ( ω n n ) . v=\omega_n+O\left(\frac{\omega_n}{n}\right). v = ω n + O ( n ω n ) .
Converting back and inserting the expansion for v v v we get
x ⋆ = e ω n 2 exp ( O ( ω n n ) ) = n ω n ( 1 + O ( ω n n ) ) . x^\star=\frac{e^{\omega_n}}{\sqrt{2}}\exp\left(O\left(\frac{\omega_n}{n}\right)\right)=\frac{n}{\omega_n}\left(1+O\left(\frac{\omega_n}{n}\right)\right). x ⋆ = 2 e ω n exp ( O ( n ω n ) ) = ω n n ( 1 + O ( n ω n ) ) .
Thus the saddle point satisfies
x ⋆ = n ω n + O ( 1 ) . x^\star=\frac{n}{\omega_n}+O(1). x ⋆ = ω n n + O ( 1 ) .
We shall also use that this critical point is unique. For x ≤ n 1 / 2 + ε x\le n^{1/2+\varepsilon} x ≤ n 1/2 + ε , with fixed 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 , the positive term 2 n / x 2n/x 2 n / x in (9) dominates the logarithmic terms, and therefore Φ n ′ ( x ) > 0 \Phi'_n(x)>0 Φ n ′ ( x ) > 0 for all sufficiently large n n n . For x ≥ n 1 / 2 + ε x\ge n^{1/2+\varepsilon} x ≥ n 1/2 + ε , the right-hand side of (9) is strictly decreasing up to an error which is smaller than the main derivative. Hence Φ n ′ \Phi'_n Φ n ′ has exactly one zero. Thus Φ n \Phi_n Φ n has a unique maximum at x ⋆ x^\star x ⋆ .
Step 3: Local quadratic expansion. Differentiating once more gives
Φ n ′ ′ ( x ) = − ( n − 1 ) ( 1 x 2 + 1 ( x − 1 ) 2 ) − 4 ( 2 x − 1 ) 2 + ( f ′ f ) ′ ( x ) . \Phi_n''(x)=-(n-1)\left(\frac{1}{x^2}+\frac{1}{(x-1)^2}\right)-\frac{4}{(2x-1)^2}+\left(\frac{f'}{f}\right)'(x). Φ n ′′ ( x ) = − ( n − 1 ) ( x 2 1 + ( x − 1 ) 2 1 ) − ( 2 x − 1 ) 2 4 + ( f f ′ ) ′ ( x ) .
Using (7), we obtain
Φ n ′ ′ ( x ) = − 2 n x 2 − 2 x + O ( n x 3 ) + O ( 1 x 2 ) . (10) \Phi_n''(x)=-\frac{2n}{x^2}-\frac{2}{x}+O\left(\frac{n}{x^3}\right)+O\left(\frac{1}{x^2}\right). \tag*{(10)} Φ n ′′ ( x ) = − x 2 2 n − x 2 + O ( x 3 n ) + O ( x 2 1 ) . (10)
At the saddle point this yields
Φ n ′ ′ ( x ∗ ) = − 2 ω n ( ω n + 1 ) n ( 1 + o ( 1 ) ) . (11) \Phi_n''(x^*)=-\frac{2\omega_n(\omega_n+1)}{n}(1+o(1)). \tag*{(11)} Φ n ′′ ( x ∗ ) = − n 2 ω n ( ω n + 1 ) ( 1 + o ( 1 )) . (11)
We define
λ n : = − Φ n ′ ′ ( x ∗ ) . \lambda_n:=-\Phi_n''(x^*). λ n := − Φ n ′′ ( x ∗ ) .
Hence
λ n = 2 ω n ( ω n + 1 ) n ( 1 + o ( 1 ) ) . \lambda_n=\frac{2\omega_n(\omega_n+1)}{n}(1+o(1)). λ n = n 2 ω n ( ω n + 1 ) ( 1 + o ( 1 )) .
In particular, the saddle point x ∗ x^* x ∗ corresponds to a strict local maximum of Φ n \Phi_n Φ n . Similarly,
Φ n ′ ′ ′ ( x ) = 2 ( n − 1 ) ( 1 x 3 + 1 ( x − 1 ) 3 ) + 16 ( 2 x − 1 ) 3 + ( f ′ f ) ′ ′ ( x ) , \Phi_n'''(x)=2(n-1)\left(\frac{1}{x^3}+\frac{1}{(x-1)^3}\right)+\frac{16}{(2x-1)^3}+\left(\frac{f'}{f}\right)''(x), Φ n ′′′ ( x ) = 2 ( n − 1 ) ( x 3 1 + ( x − 1 ) 3 1 ) + ( 2 x − 1 ) 3 16 + ( f f ′ ) ′′ ( x ) ,
and from (8) we get, uniformly for ∣ x − x ∗ ∣ ≤ n |x-x^*|\le\sqrt{n} ∣ x − x ∗ ∣ ≤ n ,
Φ n ′ ′ ′ ( x ) = O ( ω n 3 n 2 ) , as n → ∞ . (12) \Phi_n'''(x)=O\left(\frac{\omega_n^3}{n^2}\right),\quad\text{as }n\to\infty. \tag*{(12)} Φ n ′′′ ( x ) = O ( n 2 ω n 3 ) , as n → ∞. (12)
Let
W n : = { k ∈ Z : ∣ k − x ∗ ∣ ≤ n } . W_n:=\{k\in\mathbb{Z}:|k-x^*|\le\sqrt{n}\}. W n := { k ∈ Z : ∣ k − x ∗ ∣ ≤ n } .
Using (12), Taylor’s theorem gives, for x x x with ∣ x − x ∗ ∣ ≤ n |x-x^*|\le\sqrt{n} ∣ x − x ∗ ∣ ≤ n ,
Φ n ( x ) = Φ n ( x ∗ ) + 1 2 Φ n ′ ′ ( x ∗ ) ( x − x ∗ ) 2 + O ( ω n 3 n 2 ∣ x − x ∗ ∣ 3 ) . \Phi_n(x)=\Phi_n(x^*)+\frac{1}{2}\Phi_n''(x^*)(x-x^*)^2+O\left(\frac{\omega_n^3}{n^2}|x-x^*|^3\right). Φ n ( x ) = Φ n ( x ∗ ) + 2 1 Φ n ′′ ( x ∗ ) ( x − x ∗ ) 2 + O ( n 2 ω n 3 ∣ x − x ∗ ∣ 3 ) .
Since ∣ x − x ∗ ∣ ≤ n |x-x^*|\le\sqrt{n} ∣ x − x ∗ ∣ ≤ n , the remainder is
O ( ω n 3 n ) = o ( 1 ) . O\left(\frac{\omega_n^3}{\sqrt{n}}\right)=o(1). O ( n ω n 3 ) = o ( 1 ) .
Thus, uniformly on W n W_n W n ,
Φ n ( k ) = Φ n ( x ∗ ) + 1 2 Φ n ′ ′ ( x ∗ ) ( k − x ∗ ) 2 + o ( 1 ) . (13) \Phi_n(k)=\Phi_n(x^*)+\frac{1}{2}\Phi_n''(x^*)(k-x^*)^2+o(1). \tag*{(13)} Φ n ( k ) = Φ n ( x ∗ ) + 2 1 Φ n ′′ ( x ∗ ) ( k − x ∗ ) 2 + o ( 1 ) . (13)
Exponentiating this expansion yields
e Φ n ( k ) ∼ e Φ n ( x ∗ ) exp ( − λ n 2 ( k − x ∗ ) 2 ) . e^{\Phi_n(k)}\sim e^{\Phi_n(x^*)}\exp\left(-\frac{\lambda_n}{2}(k-x^*)^2\right). e Φ n ( k ) ∼ e Φ n ( x ∗ ) exp ( − 2 λ n ( k − x ∗ ) 2 ) .
The second exponential is referred to as the Gaussian factor arising from the quadratic expansion. It describes the local concentration of the summands around the saddle point.
Step 4: Negligibility of the tails and the Gaussian sum. We split the sum into a central part and a tail part. Then
S n = S n c e n t + S n t a i l S_n=S_n^{\mathrm{cent}}+S_n^{\mathrm{tail}} S n = S n cent + S n tail
where
S n c e n t : = ∑ k ∈ W n e Φ n ( k ) and S n t a i l : = ∑ 1 ≤ k ≤ 2 n ∣ k − x ⋆ ∣ > n e Φ n ( k ) . S_n^{\mathrm{cent}} := \sum_{k\in W_n} e^{\Phi_n(k)}
\quad\text{and}\quad
S_n^{\mathrm{tail}} := \sum_{\substack{1\le k\le2n\\ |k-x^\star|>\sqrt{n}}} e^{\Phi_n(k)}. S n cent := k ∈ W n ∑ e Φ n ( k ) and S n tail := 1 ≤ k ≤ 2 n ∣ k − x ⋆ ∣ > n ∑ e Φ n ( k ) .
Since Φ n \Phi_n Φ n is increasing on ( 1 , x ⋆ ) (1,x^\star) ( 1 , x ⋆ ) and decreasing on ( x ⋆ , 2 n ) (x^\star,2n) ( x ⋆ , 2 n ) , every k k k with ∣ k − x ⋆ ∣ > n |k-x^\star|>\sqrt{n} ∣ k − x ⋆ ∣ > n satisfies
Φ n ( k ) ≤ max ε ∈ { − 1 , 1 } Φ n ( x ⋆ + ε n ) . \Phi_n(k) \le\max_{\varepsilon\in\{-1,1\}} \Phi_n(x^\star+\varepsilon\sqrt{n}). Φ n ( k ) ≤ ε ∈ { − 1 , 1 } max Φ n ( x ⋆ + ε n ) .
Hence, by Taylor’s theorem, for some points ξ ± \xi_\pm ξ ± between x ⋆ x^\star x ⋆ and x ⋆ ± n x^\star\pm\sqrt{n} x ⋆ ± n ,
Φ n ( x ⋆ ± n ) = Φ n ( x ⋆ ) + n 2 Φ n ′ ′ ( ξ ± ) ≤ Φ n ( x ⋆ ) − c ω n 2 \Phi_n(x^\star\pm\sqrt{n})
=
\Phi_n(x^\star)+\frac{n}{2}\Phi_n''(\xi_\pm)
\le
\Phi_n(x^\star)-c\omega_n^2 Φ n ( x ⋆ ± n ) = Φ n ( x ⋆ ) + 2 n Φ n ′′ ( ξ ± ) ≤ Φ n ( x ⋆ ) − c ω n 2
for some c > 0 c>0 c > 0 and all sufficiently large n n n . Consequently,
S n t a i l ≤ 2 n exp ( Φ n ( x ⋆ ) − c ω n 2 ) = e Φ n ( x ⋆ ) ⋅ O ( n e − c ω n 2 ) . S_n^{\mathrm{tail}}
\le
2n\exp\left(\Phi_n(x^\star)-c\omega_n^2\right)
=
e^{\Phi_n(x^\star)}\cdot O\left(ne^{-c\omega_n^2}\right). S n tail ≤ 2 n exp ( Φ n ( x ⋆ ) − c ω n 2 ) = e Φ n ( x ⋆ ) ⋅ O ( n e − c ω n 2 ) .
Since ω n ∼ log n \omega_n\sim\log n ω n ∼ log n , this is negligible compared to the central contribution.
It remains to estimate S n c e n t S_n^{\mathrm{cent}} S n cent . Using (13) , we get
S n c e n t = e Φ n ( x ⋆ ) ∑ k ∈ W n exp ( − λ n 2 ( k − x ⋆ ) 2 ) ( 1 + o ( 1 ) ) . S_n^{\mathrm{cent}}
=
e^{\Phi_n(x^\star)}
\sum_{k\in W_n}
\exp\left(-\frac{\lambda_n}{2}(k-x^\star)^2\right)(1+o(1)). S n cent = e Φ n ( x ⋆ ) k ∈ W n ∑ exp ( − 2 λ n ( k − x ⋆ ) 2 ) ( 1 + o ( 1 )) .
The Gaussian tail outside W n W_n W n is exponentially small, hence the sum may be extended to all integers:
∑ k ∈ W n exp ( − λ n 2 ( k − x ⋆ ) 2 ) ∼ ∑ k ∈ Z exp ( − λ n 2 ( k − x ⋆ ) 2 ) , as n → ∞ . \sum_{k\in W_n}
\exp\left(-\frac{\lambda_n}{2}(k-x^\star)^2\right)
\sim
\sum_{k\in\mathbb{Z}}
\exp\left(-\frac{\lambda_n}{2}(k-x^\star)^2\right),
\qquad\text{as }n\to\infty. k ∈ W n ∑ exp ( − 2 λ n ( k − x ⋆ ) 2 ) ∼ k ∈ Z ∑ exp ( − 2 λ n ( k − x ⋆ ) 2 ) , as n → ∞.
By Poisson summation,
∑ k ∈ Z exp ( − λ n 2 ( k − x ⋆ ) 2 ) = 2 π λ n ( 1 + O ( e − 2 π 2 / λ n ) ) , \sum_{k\in\mathbb{Z}}
\exp\left(-\frac{\lambda_n}{2}(k-x^\star)^2\right)
=
\sqrt{\frac{2\pi}{\lambda_n}}
\left(1+O\left(e^{-2\pi^2/\lambda_n}\right)\right), k ∈ Z ∑ exp ( − 2 λ n ( k − x ⋆ ) 2 ) = λ n 2 π ( 1 + O ( e − 2 π 2 / λ n ) ) ,
Since λ n → 0 \lambda_n\to0 λ n → 0 , this is asymptotically equal to 2 π / λ n \sqrt{2\pi/\lambda_n} 2 π / λ n . Consequently,
S n c e n t = e Φ n ( x ⋆ ) 2 π − Φ n ′ ′ ( x ⋆ ) ( 1 + o ( 1 ) ) . S_n^{\mathrm{cent}}
=
e^{\Phi_n(x^\star)}
\sqrt{\frac{2\pi}{-\Phi_n''(x^\star)}}(1+o(1)). S n cent = e Φ n ( x ⋆ ) − Φ n ′′ ( x ⋆ ) 2 π ( 1 + o ( 1 )) .
Since S n t a i l S_n^{\mathrm{tail}} S n tail is negligible, we obtain
S n = e Φ n ( x ⋆ ) 2 π − Φ n ′ ′ ( x ⋆ ) ( 1 + o ( 1 ) ) . (14) S_n
=
e^{\Phi_n(x^\star)}
\sqrt{\frac{2\pi}{-\Phi_n''(x^\star)}}(1+o(1)). \tag*{(14)} S n = e Φ n ( x ⋆ ) − Φ n ′′ ( x ⋆ ) 2 π ( 1 + o ( 1 )) . (14)
Step 5: Evaluation of the saddle point and curvature. It remains to evaluate the two factors in (14). From Step 1,
log f ( x ) = ( x − 1 2 ) log 2 − log Γ ( 2 x ) + O ( 1 x ) . \log f(x)
=
\left(x-\frac{1}{2}\right)\log2-\log\Gamma(2x)+O\left(\frac{1}{x}\right). log f ( x ) = ( x − 2 1 ) log 2 − log Γ ( 2 x ) + O ( x 1 ) .
Using Stirling’s formula,
log Γ ( 2 x ) = ( 2 x − 1 2 ) log ( 2 x ) − 2 x + 1 2 log ( 2 π ) + O ( 1 x ) . \log\Gamma(2x)
=
\left(2x-\frac{1}{2}\right)\log(2x)-2x+\frac{1}{2}\log(2\pi)+O\left(\frac{1}{x}\right). log Γ ( 2 x ) = ( 2 x − 2 1 ) log ( 2 x ) − 2 x + 2 1 log ( 2 π ) + O ( x 1 ) .
we obtain
log f ( x ) = − ( 2 x − 1 2 ) log x + 2 x − x log 2 − 1 2 log ( 2 π ) + O ( 1 x ) . \log f(x)=-\left(2x-\frac{1}{2}\right)\log x+2x-x\log2-\frac{1}{2}\log(2\pi)+O\left(\frac{1}{x}\right). log f ( x ) = − ( 2 x − 2 1 ) log x + 2 x − x log 2 − 2 1 log ( 2 π ) + O ( x 1 ) .
Substituting this into (4) and expanding
log ( x − 1 ) = log x − 1 x + O ( 1 x 2 ) , log ( 2 x − 1 ) = log x + log 2 + O ( 1 x ) , \log(x-1)=\log x-\frac{1}{x}+O\left(\frac{1}{x^{2}}\right),\qquad\log(2x-1)=\log x+\log2+O\left(\frac{1}{x}\right), log ( x − 1 ) = log x − x 1 + O ( x 2 1 ) , log ( 2 x − 1 ) = log x + log 2 + O ( x 1 ) ,
gives
Φ n ( x ) = ( 2 n − 1 2 ) log x − 2 x log x + 2 x − x log 2 − n log 2 + 3 2 log 2 − 1 2 log ( 2 π ) − n − 1 x + O ( n x 2 + 1 x ) . (15) \Phi_n(x)=\left(2n-\frac{1}{2}\right)\log x-2x\log x+2x-x\log2-n\log2+\frac{3}{2}\log2-\frac{1}{2}\log(2\pi)-\frac{n-1}{x}+O\left(\frac{n}{x^{2}}+\frac{1}{x}\right). \tag*{(15)} Φ n ( x ) = ( 2 n − 2 1 ) log x − 2 x log x + 2 x − x log 2 − n log 2 + 2 3 log 2 − 2 1 log ( 2 π ) − x n − 1 + O ( x 2 n + x 1 ) . (15)
By the saddle-point estimate established in Step 2,
x ∗ − n ω n = O ( 1 ) . x^{*}-\frac{n}{\omega_n}=O(1). x ∗ − ω n n = O ( 1 ) .
Since Φ n ′ ( x ∗ ) = 0 \Phi_n'(x^{*})=0 Φ n ′ ( x ∗ ) = 0 and
Φ n ′ ′ ( x ) = O ( ω n 2 n ) \Phi_n''(x)=O\left(\frac{\omega_n^{2}}{n}\right) Φ n ′′ ( x ) = O ( n ω n 2 )
uniformly for x x x between x ∗ x^{*} x ∗ and n / ω n n/\omega_n n / ω n , Taylor’s theorem gives
Φ n ( x ∗ ) = Φ n ( n ω n ) + O ( ω n 2 n ) = Φ n ( n ω n ) + o ( 1 ) . \Phi_n(x^{*})=\Phi_n\left(\frac{n}{\omega_n}\right)+O\left(\frac{\omega_n^{2}}{n}\right)=\Phi_n\left(\frac{n}{\omega_n}\right)+o(1). Φ n ( x ∗ ) = Φ n ( ω n n ) + O ( n ω n 2 ) = Φ n ( ω n n ) + o ( 1 ) .
Evaluating (15) at x = n / ω n x=n/\omega_n x = n / ω n and using
log ( n ω n ) = ω n − 1 2 log 2 \log\left(\frac{n}{\omega_n}\right)=\omega_n-\frac{1}{2}\log2 log ( ω n n ) = ω n − 2 1 log 2
therefore gives
Φ n ( x ∗ ) = − 2 n log 2 + 2 n ( ω n − 1 + 1 ω n ) − 3 2 ω n + 5 4 log 2 − 1 2 log π + o ( 1 ) . (16) \Phi_n(x^{*})=-2n\log2+2n\left(\omega_n-1+\frac{1}{\omega_n}\right)-\frac{3}{2}\omega_n+\frac{5}{4}\log2-\frac{1}{2}\log\pi+o(1). \tag*{(16)} Φ n ( x ∗ ) = − 2 n log 2 + 2 n ( ω n − 1 + ω n 1 ) − 2 3 ω n + 4 5 log 2 − 2 1 log π + o ( 1 ) . (16)
Using the curvature estimate (11) derived in Step 3, we obtain
2 π − Φ n ′ ′ ( x ∗ ) = π n ω n ( ω n + 1 ) ( 1 + o ( 1 ) ) . (17) \sqrt{\frac{2\pi}{-\Phi_n''(x^{*})}}=\sqrt{\frac{\pi n}{\omega_n(\omega_n+1)}}(1+o(1)). \tag*{(17)} − Φ n ′′ ( x ∗ ) 2 π = ω n ( ω n + 1 ) π n ( 1 + o ( 1 )) . (17)
Combining (14) , (16) , and (17) , we obtain
S n ∼ exp ( − 2 n log 2 + 2 n ( ω n − 1 + 1 ω n ) ) exp ( − 3 2 ω n + 5 4 log 2 − 1 2 log π ) π n ω n ( ω n + 1 ) . S_n\sim\exp\left(-2n\log2+2n\left(\omega_n-1+\frac{1}{\omega_n}\right)\right)\exp\left(-\frac{3}{2}\omega_n+\frac{5}{4}\log2-\frac{1}{2}\log\pi\right)\sqrt{\frac{\pi n}{\omega_n(\omega_n+1)}}. S n ∼ exp ( − 2 n log 2 + 2 n ( ω n − 1 + ω n 1 ) ) exp ( − 2 3 ω n + 4 5 log 2 − 2 1 log π ) ω n ( ω n + 1 ) π n .
Equivalently,
S n ∼ 2 − 2 n exp ( 2 n ( ω n − 1 + 1 ω n ) ) 2 5 / 4 n 1 / 2 e − 3 ω n / 2 1 ω n ( ω n + 1 ) . S_n\sim2^{-2n}\exp\left(2n\left(\omega_n-1+\frac{1}{\omega_n}\right)\right)2^{5/4}n^{1/2}e^{-3\omega_n/2}\frac{1}{\sqrt{\omega_n(\omega_n+1)}}. S n ∼ 2 − 2 n exp ( 2 n ( ω n − 1 + ω n 1 ) ) 2 5/4 n 1/2 e − 3 ω n /2 ω n ( ω n + 1 ) 1 .
Finally, since ω n e ω n = n 2 \omega_n e^{\omega_n}=n\sqrt{2} ω n e ω n = n 2 , we have
e − 3 ω n / 2 = ( ω n n 2 ) 3 / 2 . e^{-3\omega_n/2}=\left(\frac{\omega_n}{n\sqrt{2}}\right)^{3/2}. e − 3 ω n /2 = ( n 2 ω n ) 3/2 .
Therefore
2 5 / 4 n 1 / 2 e − 3 ω n / 2 1 ω n ( ω n + 1 ) = 2 ω n n 1 + ω n . 2^{5/4}n^{1/2}e^{-3\omega_n/2}\frac{1}{\sqrt{\omega_n(\omega_n+1)}}=\sqrt{2}\frac{\omega_n}{n\sqrt{1+\omega_n}}. 2 5/4 n 1/2 e − 3 ω n /2 ω n ( ω n + 1 ) 1 = 2 n 1 + ω n ω n .
Hence
S n ∼ 2 ω n 2 2 n n 1 + ω n exp ( 2 n ( ω n − 1 + 1 ω n ) ) . S_n\sim\sqrt{2}\frac{\omega_n}{2^{2n}n\sqrt{1+\omega_n}}\exp\left(2n\left(\omega_n-1+\frac{1}{\omega_n}\right)\right). S n ∼ 2 2 2 n n 1 + ω n ω n exp ( 2 n ( ω n − 1 + ω n 1 ) ) .
Distribution of the number of vertices in the UIG-model
We now refine the enumeration of histories of the UIG-model by keeping track of the number of vertices as well. Let U n U_n U n denote the number of vertices in a uniformly random history generated in n n n steps. Its probability generating function is
P n ( u ) = [ t n ] T ( t , u ) [ t n ] T ( t , 1 ) . P_n(u)=\frac{[t^n]T(t,u)}{[t^n]T(t,1)}. P n ( u ) = [ t n ] T ( t , 1 ) [ t n ] T ( t , u ) .
As in the univariate case, the coefficient admits a similar representation involving Bessel functions, namely, for n ≥ 2 n\ge2 n ≥ 2 , we have
[ t n ] T ( t , u ) = ∑ k ≥ 2 ( k 2 ) n − 1 2 k − 1 2 u J 2 k − 1 ( 2 2 u ) , (18) [t^n]T(t,u)=\sum_{k\ge2}\binom{k}{2}^{n-1}\frac{2k-1}{\sqrt{2}}\sqrt{u}J_{2k-1}(2\sqrt{2u}), \tag*{(18)} [ t n ] T ( t , u ) = k ≥ 2 ∑ ( 2 k ) n − 1 2 2 k − 1 u J 2 k − 1 ( 2 2 u ) , (18)
for u u u in a suitable fixed compact neighbourhood K K K of 1 1 1 . More precisely, put u 0 : = j 1 , 1 2 / 8 = 1.835 … u_0:=j_{1,1}^2/8=1.835\ldots u 0 := j 1 , 1 2 /8 = 1.835 … . For 0 < u < u 0 0<u<u_0 0 < u < u 0 we have 2 2 u < j 1 , 1 ≤ j 2 k − 1 , 1 2\sqrt{2u}<j_{1,1}\le j_{2k-1,1} 2 2 u < j 1 , 1 ≤ j 2 k − 1 , 1 , so that all summands in (18) are positive. Throughout this section we fix a compact interval U U U containing 0 0 0 and such that e s < u 0 e^s<u_0 e s < u 0 for all s ∈ U s\in U s ∈ U . We write u = e s u=e^s u = e s . The sum can again be truncated at 2 n 2n 2 n , with an error being exponentially smaller than the main term and uniform for s ∈ U s\in U s ∈ U . As in the univariate case we write
[ t n ] T ( t , u ) ∼ ∑ k = 2 2 n exp ( Φ n , u ( k ) ) (19) [t^n]T(t,u)\sim\sum_{k=2}^{2n}\exp(\Phi_{n,u}(k)) \tag*{(19)} [ t n ] T ( t , u ) ∼ k = 2 ∑ 2 n exp ( Φ n , u ( k )) (19)
with
Φ n , u ( x ) : = log ( ( x 2 ) n − 1 2 x − 1 2 u J 2 x − 1 ( 2 2 u ) ) . (20) \Phi_{n,u}(x):=\log\left(\binom{x}{2}^{n-1}\frac{2x-1}{\sqrt{2}}\sqrt{u}J_{2x-1}(2\sqrt{2u})\right). \tag*{(20)} Φ n , u ( x ) := log ( ( 2 x ) n − 1 2 2 x − 1 u J 2 x − 1 ( 2 2 u ) ) . (20)
By the series expansion of the Bessel function,
u J 2 x − 1 ( 2 2 u ) = 2 x − 1 2 u x Γ ( 2 x ) ψ ( x , s ) with ψ ( x , s ) : = ∑ ℓ ≥ 0 ( − 2 e s ) ℓ Γ ( 2 x ) ℓ ! Γ ( ℓ + 2 x ) , \sqrt{u}J_{2x-1}(2\sqrt{2u})=\frac{2^{x-\frac{1}{2}}u^x}{\Gamma(2x)}\psi(x,s)
\quad\text{with}\quad
\psi(x,s):=\sum_{\ell\ge0}\frac{(-2e^s)^\ell\Gamma(2x)}{\ell!\,\Gamma(\ell+2x)}, u J 2 x − 1 ( 2 2 u ) = Γ ( 2 x ) 2 x − 2 1 u x ψ ( x , s ) with ψ ( x , s ) := ℓ ≥ 0 ∑ ℓ ! Γ ( ℓ + 2 x ) ( − 2 e s ) ℓ Γ ( 2 x ) ,
we obtain
Φ n , e s ( x ) = Φ n ( x ) + s x + R ( x , s ) (21) \Phi_{n,e^s}(x)=\Phi_n(x)+sx+R(x,s) \tag*{(21)} Φ n , e s ( x ) = Φ n ( x ) + s x + R ( x , s ) (21)
where
R ( x , s ) : = log ψ ( x , s ) − log ψ ( x , 0 ) . R(x,s):=\log\psi(x,s)-\log\psi(x,0). R ( x , s ) := log ψ ( x , s ) − log ψ ( x , 0 ) .
Since 0 < Γ ( 2 x ) / Γ ( ℓ + 2 x ) ≤ ( 2 x ) − ℓ 0<\Gamma(2x)/\Gamma(\ell+2x)\le(2x)^{-\ell} 0 < Γ ( 2 x ) /Γ ( ℓ + 2 x ) ≤ ( 2 x ) − ℓ and 0 ≤ ∂ x log ( Γ ( ℓ + 2 x ) / Γ ( 2 x ) ) ≤ ℓ / x 0\le\partial_x\log(\Gamma(\ell+2x)/\Gamma(2x))\le\ell/x 0 ≤ ∂ x log ( Γ ( ℓ + 2 x ) /Γ ( 2 x )) ≤ ℓ / x , term-wise differentiation shows that ψ ( x , s ) = 1 − e s / x + O ( x − 2 ) \psi(x,s)=1-e^s/x+O(x^{-2}) ψ ( x , s ) = 1 − e s / x + O ( x − 2 ) , that ∂ s j ψ ( x , s ) = − e s / x + O ( x − 2 ) \partial_s^j\psi(x,s)=-e^s/x+O(x^{-2}) ∂ s j ψ ( x , s ) = − e s / x + O ( x − 2 ) for j ≥ 1 j\ge1 j ≥ 1 . Likewise, we obtain ∂ x ∂ s j ψ ( x , s ) = O ( x − 2 ) \partial_x\partial_s^j\psi(x,s)=O(x^{-2}) ∂ x ∂ s j ψ ( x , s ) = O ( x − 2 ) for j ≥ 0 j\ge0 j ≥ 0 , uniformly for s ∈ U s\in U s ∈ U . Consequently,
∂ s j R ( x , s ) = O ( 1 x ) , ∂ x ∂ s j R ( x , s ) = O ( 1 x 2 ) , for j = 0 , 1 , 2 , (22) \partial_s^jR(x,s)=O\left(\frac{1}{x}\right),\qquad
\partial_x\partial_s^jR(x,s)=O\left(\frac{1}{x^2}\right),\qquad\text{for }j=0,1,2, \tag*{(22)} ∂ s j R ( x , s ) = O ( x 1 ) , ∂ x ∂ s j R ( x , s ) = O ( x 2 1 ) , for j = 0 , 1 , 2 , (22)
as x → ∞ x \to\infty x → ∞ , uniformly for s ∈ U s \in U s ∈ U .
Proposition 2. For s ∈ U s \in U s ∈ U and n n n sufficiently large, the equation Φ n , e s ′ ( x ) = 0 \Phi'_{n,e^s}(x)=0 Φ n , e s ′ ( x ) = 0 has a unique solution x n ( s ) x_n(s) x n ( s ) in ( 1 , ∞ ) (1,\infty) ( 1 , ∞ ) ; it is a smooth function of s s s . Set ω n ( s ) : = W ( n 2 e − s / 2 ) \omega_n(s):=W(n\sqrt{2}e^{-s/2}) ω n ( s ) := W ( n 2 e − s /2 ) . Then, uniformly for s ∈ U s \in U s ∈ U ,
x n ( s ) = n ω n ( s ) + O ( 1 ) . x_n(s)=\frac{n}{\omega_n(s)}+O(1). x n ( s ) = ω n ( s ) n + O ( 1 ) .
Proof. Existence and uniqueness follow verbatim as in Step 2 of the proof of Theorem 1. Indeed, by (21) and (22) the function Φ n , e s \Phi_{n,e^s} Φ n , e s satisfies the same estimates as Φ n \Phi_n Φ n , uniformly for s ∈ U s \in U s ∈ U ; smoothness in s s s follows from the implicit function theorem, as ∂ x 2 Φ n , e s ( x n ( s ) ) < 0 \partial_x^2\Phi_{n,e^s}(x_n(s))<0 ∂ x 2 Φ n , e s ( x n ( s )) < 0 . Together with (9), (21) and (22) yield
Φ n , e s ′ ( x ) = 2 n x − 2 log x − log 2 + s + O ( n x 2 ) + O ( 1 x ) . \Phi'_{n,e^s}(x)=\frac{2n}{x}-2\log x-\log2+s+O\left(\frac{n}{x^2}\right)+O\left(\frac{1}{x}\right). Φ n , e s ′ ( x ) = x 2 n − 2 log x − log 2 + s + O ( x 2 n ) + O ( x 1 ) .
Hence the saddle-point equation Φ n , e s ′ ( x ) = 0 \Phi'_{n,e^s}(x)=0 Φ n , e s ′ ( x ) = 0 implies
n x n ( s ) = log ( x n ( s ) 2 e − s / 2 ) + O ( n x n ( s ) 2 ) + O ( 1 x n ( s ) ) . \frac{n}{x_n(s)}=\log\left(x_n(s)\sqrt{2}e^{-s/2}\right)+O\left(\frac{n}{x_n(s)^2}\right)+O\left(\frac{1}{x_n(s)}\right). x n ( s ) n = log ( x n ( s ) 2 e − s /2 ) + O ( x n ( s ) 2 n ) + O ( x n ( s ) 1 ) .
As in the unmarked case, this shows uniformly for s s s near 0 that
x n ( s ) ≍ n log n , as n → ∞ . x_n(s)\asymp\frac{n}{\log n},\qquad\text{as }n\to\infty. x n ( s ) ≍ log n n , as n → ∞.
Set
v : = log ( x n ( s ) 2 e − s / 2 ) . v:=\log\left(x_n(s)\sqrt{2}e^{-s/2}\right). v := log ( x n ( s ) 2 e − s /2 ) .
Multiplying the saddle-point equation by x n ( s ) x_n(s) x n ( s ) and using x n ( s ) ≍ n / log n x_n(s)\asymp n/\log n x n ( s ) ≍ n / log n , we obtain
v e v = n 2 e − s / 2 + O ( ω n ( s ) ) , as n → ∞ . ve^v=n\sqrt{2}e^{-s/2}+O\left(\omega_n(s)\right),\qquad\text{as }n\to\infty. v e v = n 2 e − s /2 + O ( ω n ( s ) ) , as n → ∞.
On the other hand,
ω n ( s ) e ω n ( s ) = n 2 e − s / 2 . \omega_n(s)e^{\omega_n(s)}=n\sqrt{2}e^{-s/2}. ω n ( s ) e ω n ( s ) = n 2 e − s /2 .
Since s s s stays in the fixed neighbourhood U U U of 0, we have the uniform estimate ω n ( s ) ≍ log n \omega_n(s)\asymp\log n ω n ( s ) ≍ log n . The mean value theorem applied to v ↦ v e v v\mapsto ve^v v ↦ v e v therefore gives
v = ω n ( s ) + O ( ω n ( s ) n ) . v=\omega_n(s)+O\left(\frac{\omega_n(s)}{n}\right). v = ω n ( s ) + O ( n ω n ( s ) ) .
Consequently, for n → ∞ n\to\infty n → ∞ , we obtain
x n ( s ) = e s / 2 2 e v = n ω n ( s ) exp ( O ( ω n ( s ) n ) ) = n ω n ( s ) + O ( 1 ) . x_n(s)=\frac{e^{s/2}}{\sqrt{2}}e^v=\frac{n}{\omega_n(s)}\exp\left(O\left(\frac{\omega_n(s)}{n}\right)\right)=\frac{n}{\omega_n(s)}+O(1). x n ( s ) = 2 e s /2 e v = ω n ( s ) n exp ( O ( n ω n ( s ) ) ) = ω n ( s ) n + O ( 1 ) .
Theorem 2 (Gaussian limit law for the number of vertices). Let U n U_n U n denote the number of vertices in a uniformly random history of the UIG-model generated in n n n steps. With
ω n : = W ( n 2 ) , \omega_n:=W(n\sqrt{2}), ω n := W ( n 2 ) , we have
E [ U n ] ∼ n ω n , V ( U n ) ∼ n 2 ω n ( ω n + 1 ) . \mathbb{E}[U_n]\sim\frac{n}{\omega_n},\qquad\mathbb{V}(U_n)\sim\frac{n}{2\omega_n(\omega_n+1)}. E [ U n ] ∼ ω n n , V ( U n ) ∼ 2 ω n ( ω n + 1 ) n . Moreover,
U n − E [ U n ] V ( U n ) → d n → ∞ N ( 0 , 1 ) . \frac{U_n-\mathbb{E}[U_n]}{\sqrt{\mathbb{V}(U_n)}}\xrightarrow{d}_{n\to\infty}\mathcal{N}(0,1). V ( U n ) U n − E [ U n ] d n → ∞ N ( 0 , 1 ) .
Proof. We study the moment generating function
P n ( e s ) = [ t n ] T ( t , e s ) [ t n ] T ( t , 1 ) P_n(e^s) = \frac{[t^n]T(t,e^s)}{[t^n]T(t,1)} P n ( e s ) = [ t n ] T ( t , 1 ) [ t n ] T ( t , e s )
for s s s in a fixed neighbourhood of 0 and write
K n ( s ) : = log P n ( e s ) . K_n(s) := \log P_n(e^s). K n ( s ) := log P n ( e s ) .
By virtue of the uniform bounds on the remainder R ( x , s ) R(x,s) R ( x , s ) established in (22), the discrete Laplace argument used in the univariate enumeration applies uniformly for s s s near 0. This yields
[ t n ] T ( t , e s ) = exp ( Φ n , e s ( x n ( s ) ) ) 2 π − Φ n , e s ′ ′ ( x n ( s ) ) ( 1 + o ( 1 ) ) . [t^n]T(t,e^s) = \exp\bigl(\Phi_{n,e^s}(x_n(s))\bigr)\sqrt{\frac{2\pi}{-\Phi''_{n,e^s}(x_n(s))}}(1+o(1)). [ t n ] T ( t , e s ) = exp ( Φ n , e s ( x n ( s )) ) − Φ n , e s ′′ ( x n ( s )) 2 π ( 1 + o ( 1 )) .
To justify the extraction of moments, let G n ( s ) : = Φ n , e s ( x n ( s ) ) G_n(s) := \Phi_{n,e^s}(x_n(s)) G n ( s ) := Φ n , e s ( x n ( s )) denote the dominant saddle-point exponent. We must verify that differentiating the exact sum representation (18) of [ t n ] T ( t , e s ) [t^n]T(t,e^s) [ t n ] T ( t , e s ) with respect to s s s is asymptotically equivalent to differentiating its dominant term. Recall from (19) that the k k k -th summand is exp ( Φ n , e s ( k ) ) \exp(\Phi_{n,e^s}(k)) exp ( Φ n , e s ( k )) . Differentiating this with respect to s s s brings a factor
∂ s Φ n , e s ( k ) = k + ∂ s R ( k , s ) = x n ( s ) + ( k − x n ( s ) ) + ∂ s R ( k , s ) . \partial_s\Phi_{n,e^s}(k) = k + \partial_sR(k,s) = x_n(s) + (k-x_n(s)) + \partial_sR(k,s). ∂ s Φ n , e s ( k ) = k + ∂ s R ( k , s ) = x n ( s ) + ( k − x n ( s )) + ∂ s R ( k , s ) .
Repeated differentiation with respect to s s s thus introduces polynomial factors in ( k − x n ( s ) ) (k-x_n(s)) ( k − x n ( s )) , as well as derivatives of R ( k , s ) R(k,s) R ( k , s ) . Thanks to the uniform bounds provided by (22), the derivatives of the remainder are asymptotically negligible. The polynomial factors ( k − x n ( s ) ) j (k-x_n(s))^j ( k − x n ( s ) ) j cannot counter the strong Gaussian decay within the central window. As the summands remain exponentially small outside this window, the derivatives of K n ( s ) K_n(s) K n ( s ) up to third order are asymptotically equivalent to the corresponding derivatives of G n ( s ) G_n(s) G n ( s ) . Thus, we can evaluate them by applying the multivariate chain rule directly to G n ( s ) G_n(s) G n ( s ) , which yields
G n ′ ( s ) = ∂ x Φ n , e s ( x n ( s ) ) x n ′ ( s ) + ∂ s Φ n , e s ( x n ( s ) ) . G'_n(s) = \partial_x\Phi_{n,e^s}(x_n(s))x'_n(s) + \partial_s\Phi_{n,e^s}(x_n(s)). G n ′ ( s ) = ∂ x Φ n , e s ( x n ( s )) x n ′ ( s ) + ∂ s Φ n , e s ( x n ( s )) .
By definition, the saddle point satisfies
Φ n , e s ′ ( x n ( s ) ) = 0 , \Phi'_{n,e^s}(x_n(s)) = 0, Φ n , e s ′ ( x n ( s )) = 0 ,
Note that despite Φ n , e s \Phi_{n,e^s} Φ n , e s has s s s in its index, we can rely on the representation given in (21) for the computation. Doing so, we obtain
K n ′ ( s ) = x n ( s ) + O ( 1 ) , K n ′ ′ ( s ) = x n ′ ( s ) + O ( 1 ) , K n ′ ′ ′ ( s ) = O ( n ω n ( s ) 3 ) . K'_n(s) = x_n(s) + O(1), \qquad K''_n(s) = x'_n(s) + O(1), \qquad K'''_n(s) = O\left(\frac{n}{\omega_n(s)^3}\right). K n ′ ( s ) = x n ( s ) + O ( 1 ) , K n ′′ ( s ) = x n ′ ( s ) + O ( 1 ) , K n ′′′ ( s ) = O ( ω n ( s ) 3 n ) .
Here, in the first derivative, the term involving x n ′ ( s ) x'_n(s) x n ′ ( s ) vanishes, because x n ( s ) x_n(s) x n ( s ) is the saddle point.
Likewise, we determine the variance by differentiation of the the saddle-point equation with respect to s s s and relying on (21). Hence, we get
( ∂ x x Φ n , e s ) ( x n ( s ) ) x n ′ ( s ) + ( ∂ x s Φ n , e s ) ( x n ( s ) ) = 0 , (\partial_{xx}\Phi_{n,e^s})(x_n(s))x'_n(s) + (\partial_{xs}\Phi_{n,e^s})(x_n(s)) = 0, ( ∂ xx Φ n , e s ) ( x n ( s )) x n ′ ( s ) + ( ∂ x s Φ n , e s ) ( x n ( s )) = 0 ,
and hence
x n ′ ( s ) = − ( ∂ x s Φ n , e s ) ( x n ( s ) ) ( ∂ x x Φ n , e s ) ( x n ( s ) ) . x'_n(s) = -\frac{(\partial_{xs}\Phi_{n,e^s})(x_n(s))}{(\partial_{xx}\Phi_{n,e^s})(x_n(s))}. x n ′ ( s ) = − ( ∂ xx Φ n , e s ) ( x n ( s )) ( ∂ x s Φ n , e s ) ( x n ( s )) .
From (21) we directly obtain
( ∂ x s Φ n , e s ) ( x n ( s ) ) = 1 + o ( 1 ) , (\partial_{xs}\Phi_{n,e^s})(x_n(s)) = 1 + o(1), ( ∂ x s Φ n , e s ) ( x n ( s )) = 1 + o ( 1 ) ,
whereas the refined curvature estimate from the univariate saddle-point analysis yields
− ( ∂ x x Φ n , e s ) ( x n ( s ) ) = 2 ω n ( s ) ( ω n ( s ) + 1 ) n ( 1 + o ( 1 ) ) . -\left(\partial_{xx}\Phi_{n,e^s}\right)\left(x_n(s)\right)=\frac{2\omega_n(s)(\omega_n(s)+1)}{n}\left(1+o(1)\right). − ( ∂ xx Φ n , e s ) ( x n ( s ) ) = n 2 ω n ( s ) ( ω n ( s ) + 1 ) ( 1 + o ( 1 ) ) .
Consequently,
x n ′ ( s ) = n 2 ω n ( s ) ( ω n ( s ) + 1 ) ( 1 + o ( 1 ) ) . x_n'(s)=\frac{n}{2\omega_n(s)(\omega_n(s)+1)}\left(1+o(1)\right). x n ′ ( s ) = 2 ω n ( s ) ( ω n ( s ) + 1 ) n ( 1 + o ( 1 ) ) .
Evaluating at s = 0 s=0 s = 0 now gives
E [ U n ] = K n ′ ( 0 ) = n ω n + O ( 1 ) \mathbb{E}[U_n]=K_n'(0)=\frac{n}{\omega_n}+O(1) E [ U n ] = K n ′ ( 0 ) = ω n n + O ( 1 )
and
V ( U n ) = K n ′ ′ ( 0 ) = n 2 ω n ( ω n + 1 ) ( 1 + o ( 1 ) ) . \mathop{\mathrm{V}}(U_n)=K_n''(0)=\frac{n}{2\omega_n(\omega_n+1)}\left(1+o(1)\right). V ( U n ) = K n ′′ ( 0 ) = 2 ω n ( ω n + 1 ) n ( 1 + o ( 1 ) ) .
For the limit law, set
μ n : = E [ U n ] , σ n 2 : = V ( U n ) . \mu_n:=\mathbb{E}[U_n],\qquad\sigma_n^2:=\mathop{\mathrm{V}}(U_n). μ n := E [ U n ] , σ n 2 := V ( U n ) .
For fixed τ ∈ R \tau\in\mathbb{R} τ ∈ R , let h n = τ / σ n h_n=\tau/\sigma_n h n = τ / σ n . Taylor’s theorem gives
K n ( h n ) = μ n h n + σ n 2 h n 2 2 + K n ′ ′ ′ ( ξ n ) 6 h n 3 K_n(h_n)=\mu_n h_n+\frac{\sigma_n^2h_n^2}{2}+\frac{K_n'''(\xi_n)}{6}h_n^3 K n ( h n ) = μ n h n + 2 σ n 2 h n 2 + 6 K n ′′′ ( ξ n ) h n 3
for some ξ n \xi_n ξ n between 0 0 0 and h n h_n h n . Since
K n ′ ′ ′ ( ξ n ) = O ( n ω n 3 ) and σ n 2 ∼ n ω n 2 , K_n'''(\xi_n)=O\left(\frac{n}{\omega_n^3}\right)\qquad\text{and}\qquad\sigma_n^2\sim\frac{n}{\omega_n^2}, K n ′′′ ( ξ n ) = O ( ω n 3 n ) and σ n 2 ∼ ω n 2 n ,
the remainder is O ( n − 1 / 2 ) = o ( 1 ) O(n^{-1/2})=o(1) O ( n − 1/2 ) = o ( 1 ) . Therefore,
log E exp ( τ U n − μ n σ n ) = τ 2 2 + o ( 1 ) . \log\mathbb{E}\exp\left(\tau\frac{U_n-\mu_n}{\sigma_n}\right)=\frac{\tau^2}{2}+o(1). log E exp ( τ σ n U n − μ n ) = 2 τ 2 + o ( 1 ) .
The moment generating functions therefore converge in a neighbourhood of the origin to that of the standard normal distribution, which proves the claim. □
Remark 4. The proof gives E [ U n ] = n / ω n + o ( n / ω n ) \mathbb{E}[U_n]=n/\omega_n+o(\sqrt{n}/\omega_n) E [ U n ] = n / ω n + o ( n / ω n ) . Numerical computations suggest that in fact E [ U n ] = n / ω n + O ( 1 ) \mathbb{E}[U_n]=n/\omega_n+O(1) E [ U n ] = n / ω n + O ( 1 ) .
A weighted version of the UIG-model
In this section we are interested in what changes if one introduces weights on the creation of vertices and edges. In particular, phase transitions can be expected here, but a totally rigorous treatment of these would require a delicate saddle-point analysis that is uniform in the weights. This is beyond the scope of this paper and so we confine ourselves with a treatment of the case of constant weights and discuss expected phenomena briefly.
The parameter analysis in the previous section shows that in the unweighted model the number of vertices is typically of order
n W ( n 2 ) ∼ n log n . \frac{n}{W(n\sqrt{2})}\sim\frac{n}{\log n}. W ( n 2 ) n ∼ log n n .
Thus the proportion of vertex-creation steps tends to zero, and asymptotically almost all steps are edge-creation steps. It is therefore natural to introduce a relative weight for vertex creation as a way to tune the vertex–edge balance. We assign weight α > 0 \alpha> 0 α > 0 to a vertex-creation step and weight β > 0 \beta> 0 β > 0 to an edge-creation step, obtaining
T α , β ( t , u ) = 1 + α u t T α , β ( t , u ) + β u 2 t 2 ∂ u 2 T α , β ( t , u ) . T_{\alpha,\beta}(t,u)=1+\alpha u t T_{\alpha,\beta}(t,u)+\beta\frac{u^2t}{2}\partial_u^2T_{\alpha,\beta}(t,u). T α , β ( t , u ) = 1 + α u t T α , β ( t , u ) + β 2 u 2 t ∂ u 2 T α , β ( t , u ) .
We may set τ = β t \tau=\beta t τ = β t and replace α \alpha α by α / β \alpha/\beta α / β . Since this only contributes a global factor β n \beta^n β n to coefficients of t n t^n t n , it cancels in all conditional distributions with n n n steps. Hence, without loss of generality, we take β = 1 \beta=1 β = 1 from now on and write simply α \alpha α for the relative vertex weight. Thus, no new coefficient extraction is needed: the weighted model is obtained from the previous bivariate series by the substitution u ↦ α u u\mapsto\alpha u u ↦ α u .
For α > 0 \alpha>0 α > 0 , let U n ( α ) U_n^{(\alpha)} U n ( α ) denote the number of vertices in a random history chosen with probability proportional to α m \alpha^m α m , where m m m is its number of vertices. Its probability generating function is
P n , α ( u ) = [ t n ] T ( t , α u ) [ t n ] T ( t , α ) . P_{n,\alpha}(u)=\frac{[t^n]T(t,\alpha u)}{[t^n]T(t,\alpha)}. P n , α ( u ) = [ t n ] T ( t , α ) [ t n ] T ( t , α u ) .
For each fixed α \alpha α , the same saddle-point argument applies with the marking parameter centred at s = log α s=\log\alpha s = log α . Since α e s = e log α + s \alpha e^s=e^{\log\alpha+s} α e s = e l o g α + s , the weighted model is obtained by shifting the logarithmic marking parameter by log α \log\alpha log α . Thus the relevant saddle at s = 0 s=0 s = 0 is the saddle of the original model at s = log α s=\log\alpha s = log α .
Since α e s = e log α + s \alpha e^s=e^{\log\alpha+s} α e s = e l o g α + s , the weighted model is obtained by shifting the logarithmic marking parameter by log α \log\alpha log α . Thus the relevant saddle-point at s = 0 s=0 s = 0 in the weighted model corresponds to a saddle at s = log α s=\log\alpha s = log α in the original model. Therefore, for fixed α ∈ ( 0 , u 0 ) \alpha\in(0,u_0) α ∈ ( 0 , u 0 ) , the results of Section 3 apply verbatim, with U U U replaced by a compact interval containing log α \log\alpha log α and contained in ( − ∞ , log u 0 ) (-\infty,\log u_0) ( − ∞ , log u 0 ) . For fixed α ≥ u 0 \alpha\geq u_0 α ≥ u 0 , finitely many summands of (18) (those with 2 k − 1 < 2 2 α 2k-1<2\sqrt{2\alpha} 2 k − 1 < 2 2 α , since j ν , 1 > ν j_{\nu,1}>\nu j ν , 1 > ν ) may be nonpositive; their total contribution is O ( k 0 2 n ) O(k_0^{2n}) O ( k 0 2 n ) for some fixed k 0 k_0 k 0 , which is negligible compared with the main term, and the analysis restricted to k > k 0 k>k_0 k > k 0 goes through unchanged. We omit the details. Hence, with
ω n , α : = W ( n 2 α ) , \omega_{n,\alpha}:=W\left(n\sqrt{\frac{2}{\alpha}}\right), ω n , α := W ( n α 2 ) ,
we obtain
E [ U n ( α ) ] ∼ n ω n , α , V a r [ U n ( α ) ] ∼ n 2 ω n , α ( ω n , α + 1 ) ∼ n 2 ω n , α 2 . \mathbb{E}\left[U_n^{(\alpha)}\right]\sim\frac{n}{\omega_{n,\alpha}},\qquad
\mathop{\mathrm{Var}}\left[U_n^{(\alpha)}\right]\sim\frac{n}{2\omega_{n,\alpha}(\omega_{n,\alpha}+1)}\sim\frac{n}{2\omega_{n,\alpha}^2}. E [ U n ( α ) ] ∼ ω n , α n , Var [ U n ( α ) ] ∼ 2 ω n , α ( ω n , α + 1 ) n ∼ 2 ω n , α 2 n .
Moreover, the same logarithmic moment-generating-function argument gives asymptotic normality after centering and normalization.
As long as α > 0 \alpha>0 α > 0 stays fixed, we still have ω n , α ∼ log n \omega_{n,\alpha}\sim\log n ω n , α ∼ log n , and consequently
E [ U n ( α ) ] ∼ n log n . \mathbb{E}\left[U_n^{(\alpha)}\right]\sim\frac{n}{\log n}. E [ U n ( α ) ] ∼ log n n .
Thus, for every such α \alpha α the vertex proportion still tends to zero. The weight changes the lower-order location and variance of the vertex count, but not its leading term n / log n n/\log n n / log n .
Finally, it is instructive to consider heuristically what happens when α = α n \alpha=\alpha_n α = α n is allowed to grow with n n n . The saddle-point expression suggests that, as long as α n = o ( n 2 ) \alpha_n=o(n^2) α n = o ( n 2 ) , the dominant number of vertices remains sublinear. A crossover is expected when α n \alpha_n α n is of order n 2 n^2 n 2 . The Lambert W W W term is then of constant order, and the saddle becomes linear in n n n .
This is coherent with the fact that, for a generic weight α \alpha α , the recurrence relation for the coefficients a n , k ( α ) : = [ t n u k ] T ( t , α u ) a_{n,k}^{(\alpha)} := [t^n u^k]T(t,\alpha u) a n , k ( α ) := [ t n u k ] T ( t , α u ) becomes
a n + 1 , k + 1 ( α ) = α a n , k ( α ) + k ( k + 1 ) 2 a n , k + 1 ( α ) . a_{n+1,k+1}^{(\alpha)}=\alpha a_{n,k}^{(\alpha)}+\frac{k(k+1)}{2}a_{n,k+1}^{(\alpha)}. a n + 1 , k + 1 ( α ) = α a n , k ( α ) + 2 k ( k + 1 ) a n , k + 1 ( α ) .
The vertex-creation weight is of order α \alpha α , whereas the number of possible edge-creation steps is quadratic in the number of vertices. Thus, when the relevant number of vertices is of order n n n , the scale α n ≍ n 2 \alpha_n\asymp n^2 α n ≍ n 2 is the natural one at which the balance between vertex and edge creation may change. A rigorous treatment of this regime would require a saddle-point analysis uniform in α n \alpha_n α n . But this at the first glance innocent looking modification seems to be a Herculean task, as we expect that this requires taking into account the more error terms in all the computations the closer α n \alpha_n α n is to the order n 2 n^2 n 2 .
The DIG-model: directed graphs with loops allowed
We now consider the directed variant of the previous model. At each discrete time step, either (i) a new vertex is created, or (ii) a new directed edge is added between two existing vertices. In this model loops are allowed. Thus, if there are currently k k k vertices, there are k 2 k^2 k 2 possible directed edges that may be created. We again refer to the resulting time-labelled multigraph as a history.
Let t t t mark time and let u u u mark the number of vertices. A vertex creation contributes a factor u t ut u t . Edge creation corresponds to choosing an ordered pair of vertices, possibly the same vertex twice, and is represented by the operator u ∂ u ( u t ∂ u ) u\partial_u(ut\partial_u) u ∂ u ( u t ∂ u ) . Therefore the generating function T → ( t , u ) \overrightarrow{T}(t,u) T ( t , u ) satisfies
T → ( t , u ) = 1 + u t T → ( t , u ) + u ∂ u ( u t ∂ u T → ( t , u ) ) . (23) \overrightarrow{T}(t,u)=1+ut\overrightarrow{T}(t,u)+u\partial_u\left(ut\partial_u\overrightarrow{T}(t,u)\right). \tag*{(23)} T ( t , u ) = 1 + u t T ( t , u ) + u ∂ u ( u t ∂ u T ( t , u ) ) . (23)
The coefficient [ t n u m ] T → ( t , u ) [t^n u^m]\overrightarrow{T}(t,u) [ t n u m ] T ( t , u ) is the number of directed graph histories generated in n n n steps with m m m vertices. We are interested in the asymptotic behaviour of
[ t n ] T → ( t , 1 ) , as n → ∞ . [t^n]\overrightarrow{T}(t,1),\qquad\text{as }n\to\infty. [ t n ] T ( t , 1 ) , as n → ∞.
At u = 1 u=1 u = 1 , the first few terms are
T → ( t , 1 ) = 1 + t + 2 t 2 + 7 t 3 + 37 t 4 + 264 t 5 + 2433 t 6 + 27913 t 7 + O ( t 8 ) . \overrightarrow{T}(t,1)=1+t+2t^2+7t^3+37t^4+264t^5+2433t^6+27913t^7+O(t^8). T ( t , 1 ) = 1 + t + 2 t 2 + 7 t 3 + 37 t 4 + 264 t 5 + 2433 t 6 + 27913 t 7 + O ( t 8 ) .
We start with an auxiliary lemma.
Lemma 1. For integers m > ℓ ≥ 1 m>\ell\ge1 m > ℓ ≥ 1 the following identity holds:
∑ k = 1 m 2 ( − 1 ) m − k ( m − k ) ! ( m + k ) ! k 2 ℓ = 0. \sum_{k=1}^{m}\frac{2(-1)^{m-k}}{(m-k)!(m+k)!}k^{2\ell}=0. k = 1 ∑ m ( m − k )! ( m + k )! 2 ( − 1 ) m − k k 2 ℓ = 0.
Proof. Consider the function f ( z ) = ∏ j = 1 m 1 / ( z − j 2 ) f(z)=\prod_{j=1}^{m}1/(z-j^2) f ( z ) = ∏ j = 1 m 1/ ( z − j 2 ) and write it as a partial fraction decomposition f ( z ) = ∑ k = 1 m C k / ( z − k 2 ) f(z)=\sum_{k=1}^{m}C_k/(z-k^2) f ( z ) = ∑ k = 1 m C k / ( z − k 2 ) . Then, computing the coefficients with the help of residues gives
C k = ∏ 1 ≤ j ≤ m j ≠ k 1 k 2 − j 2 = 2 k 2 ( − 1 ) m − k ( m − k ) ! ( m + k ) ! . (24) C_k=\prod_{\substack{1\le j\le m\\j\ne k}}\frac{1}{k^2-j^2}=\frac{2k^2(-1)^{m-k}}{(m-k)!(m+k)!}. \tag*{(24)} C k = 1 ≤ j ≤ m j = k ∏ k 2 − j 2 1 = ( m − k )! ( m + k )! 2 k 2 ( − 1 ) m − k . (24)
Now expand 1 / ( z − k 2 ) 1/(z-k^2) 1/ ( z − k 2 ) into a geometric series for large z z z . We get
f ( z ) = ∑ k = 1 m ∑ r ≥ 0 C k k 2 r z r + 1 = ∑ r ≥ 0 ∑ k = 1 m C k k 2 r z r + 1 f(z)=\sum_{k=1}^{m}\sum_{r\geq0}\frac{C_k k^{2r}}{z^{r+1}}=\sum_{r\geq0}\sum_{k=1}^{m}\frac{C_k k^{2r}}{z^{r+1}} f ( z ) = k = 1 ∑ m r ≥ 0 ∑ z r + 1 C k k 2 r = r ≥ 0 ∑ k = 1 ∑ m z r + 1 C k k 2 r
and thus
[ z − ℓ ] F ( z ) = ∑ k = 1 m C k k 2 ℓ − 2 = ∑ k = 1 m 2 ( − 1 ) m − k ( m − k ) ! ( m + k ) ! k 2 ℓ . [z^{-\ell}]F(z)=\sum_{k=1}^{m}C_k k^{2\ell-2}=\sum_{k=1}^{m}\frac{2(-1)^{m-k}}{(m-k)!(m+k)!}k^{2\ell}. [ z − ℓ ] F ( z ) = k = 1 ∑ m C k k 2 ℓ − 2 = k = 1 ∑ m ( m − k )! ( m + k )! 2 ( − 1 ) m − k k 2 ℓ .
As f ( z ) = O ( z − m ) f(z)=\mathcal{O}(z^{-m}) f ( z ) = O ( z − m ) for z → ∞ z\to\infty z → ∞ , the inner sum must be zero for ℓ < m \ell<m ℓ < m , as claimed. □
Now we turn back to the generating function of our graph histories. The next result shows that the radius of convergence is zero, but a certain Borel-like transform of it has an explicit and simple shape.
Proposition 3. The bivariate generating function T ⃗ ( t , u ) \vec{T}(t,u) T ( t , u ) of the number of histories in the DIG-model keeping track of the number of vertices as well has radius of convergence zero, when regarded as power series in t t t and can be expressed as
T ⃗ ( t , u ) = ∑ m = 0 ∞ ∏ k = 1 m t u 1 − k 2 t . (25) \vec{T}(t,u)=\sum_{m=0}^{\infty}\prod_{k=1}^{m}\frac{tu}{1-k^2t}. \tag*{(25)} T ( t , u ) = m = 0 ∑ ∞ k = 1 ∏ m 1 − k 2 t t u . (25)
Let
B ( ∑ n ≥ 0 a n t n ) : = ∑ n ≥ 0 a n ( 2 t ) n ( 2 n ) ! . (26) \mathcal{B}\left(\sum_{n\geq0}a_nt^n\right):=\sum_{n\geq0}a_n\frac{(2t)^n}{(2n)!}. \tag*{(26)} B ( n ≥ 0 ∑ a n t n ) := n ≥ 0 ∑ a n ( 2 n )! ( 2 t ) n . (26)
and define B ⃗ ( t , u ) : = B ( T ⃗ ( ⋅ , u ) ) ( t ) \vec{B}(t,u):=\mathcal{B}(\vec{T}(\mathord{\cdot},u))(t) B ( t , u ) := B ( T ( ⋅ , u )) ( t ) , i.e., we apply B \mathcal{B} B to T ⃗ ( t , u ) \vec{T}(t,u) T ( t , u ) regarded as power series in t t t . Then we have the explicit closed form
B ⃗ ( t , u ) = E ( u ( E ( t ) − 1 ) ) , where E ( y ) : = cosh ( 2 y ) . (27) \vec{B}(t,u)=E\left(u(E(t)-1)\right),\qquad\text{where }E(y):=\cosh\left(\sqrt{2y}\right). \tag*{(27)} B ( t , u ) = E ( u ( E ( t ) − 1 ) ) , where E ( y ) := cosh ( 2 y ) . (27)
Remark 5. In general, the Borel transform of order κ \kappa κ is defined by
B ^ κ ( ∑ n ≥ 0 a n t n ) : = ∑ n ≥ 0 a n Γ ( 1 + n / κ ) t n , \widehat{\mathcal{B}}_{\kappa}\left(\sum_{n\geq0}a_nt^n\right):=\sum_{n\geq0}\frac{a_n}{\Gamma(1+n/\kappa)}t^n, B κ ( n ≥ 0 ∑ a n t n ) := n ≥ 0 ∑ Γ ( 1 + n / κ ) a n t n ,
see [30 ] [5]. For κ = 1 / 2 \kappa=1/2 κ = 1/2 , Γ ( 1 + n / κ ) = Γ ( 1 + 2 n ) = ( 2 n ) ! \Gamma(1+n/\kappa)=\Gamma(1+2n)=(2n)! Γ ( 1 + n / κ ) = Γ ( 1 + 2 n ) = ( 2 n )! . Thus, B \mathcal{B} B is the Borel transform of order 1 / 2 1/2 1/2 followed by the rescaling t ↦ 2 t t\mapsto2t t ↦ 2 t .
Remark 6. The formula (24) suggests that the radius of convergence is zero. As in the UIG-model, there may occur cancellations in the sum such not all poles of a term are actual poles of T ⃗ ( t , u ) \vec{T}(t,u) T ( t , u ) . But a simple lower bound for the number of histories can be obtained by considering the histories that first create k k k vertices and then n − k n-k n − k edges. This gives [ t n ] T ⃗ ( t , 1 ) ≥ k 2 ( n − k ) [t^n]\vec{T}(t,1)\geq k^{2(n-k)} [ t n ] T ( t , 1 ) ≥ k 2 ( n − k ) . The choice k = ⌊ n ⌋ k=\lfloor\sqrt{n}\rfloor k = ⌊ n ⌋ shows that the radius of convergence is indeed zero.
Proof. We get (24) directly from the k 2 k^2 k 2 possible edge creation steps between the creation of the k k k -th and ( k + 1 ) (k+1) ( k + 1 ) -st vertices. A partial fraction decomposition gives
∏ k = 1 m 1 1 − k 2 t = 2 ∑ k = 1 m ( − 1 ) m − k k 2 m ( m − k ) ! ( m + k ) ! ⋅ 1 1 − k 2 t , \prod_{k=1}^{m}\frac{1}{1-k^2t}
=2\sum_{k=1}^{m}(-1)^{m-k}\frac{k^{2m}}{(m-k)!(m+k)!}\cdot\frac{1}{1-k^2t}, k = 1 ∏ m 1 − k 2 t 1 = 2 k = 1 ∑ m ( − 1 ) m − k ( m − k )! ( m + k )! k 2 m ⋅ 1 − k 2 t 1 ,
since the residue coefficients are ∏ j ≠ k k 2 / ( k 2 − j 2 ) = k 2 m − 2 C k \prod_{j\ne k} k^2/(k^2-j^2)=k^{2m-2}C_k ∏ j = k k 2 / ( k 2 − j 2 ) = k 2 m − 2 C k with C k C_k C k as in the proof of Lemma 1. Thus
T ⃗ ( t , u ) = 1 + 2 ∑ m ≥ 1 ∑ k = 1 m ( − 1 ) m − k u m ( m − k ) ! ( m + k ) ! ∑ n ≥ 0 k 2 ( n + m ) t n + m = 1 + 2 ∑ ℓ ≥ 1 t ℓ ∑ m = 1 ℓ u m ∑ k = 1 m k 2 ℓ ( − 1 ) m − k ( m − k ) ! ( m + k ) ! = 1 + 2 ∑ ℓ ≥ 1 t ℓ ∑ m ≥ 1 u m ∑ k = 1 m k 2 ℓ ( − 1 ) m − k ( m − k ) ! ( m + k ) ! = 1 + 2 ∑ ℓ ≥ 1 t ℓ ∑ k ≥ 1 k 2 ℓ ∑ m ≥ k ( − 1 ) m − k u ( m − k ) + k ( m − k ) ! ( ( m − k ) + 2 k ) ! = 1 + 2 ∑ ℓ ≥ 1 t ℓ ∑ k ≥ 1 k 2 ℓ J 2 k ( 2 u ) \begin{aligned}
\vec{T}(t,u)&=1+2\sum_{m\ge1}\sum_{k=1}^{m}\frac{(-1)^{m-k}u^m}{(m-k)!(m+k)!}\sum_{n\ge0}k^{2(n+m)}t^{n+m}\\
&=1+2\sum_{\ell\ge1}t^\ell\sum_{m=1}^{\ell}u^m\sum_{k=1}^{m}k^{2\ell}\frac{(-1)^{m-k}}{(m-k)!(m+k)!}\\
&=1+2\sum_{\ell\ge1}t^\ell\sum_{m\ge1}u^m\sum_{k=1}^{m}k^{2\ell}\frac{(-1)^{m-k}}{(m-k)!(m+k)!}\\
&=1+2\sum_{\ell\ge1}t^\ell\sum_{k\ge1}k^{2\ell}\sum_{m\ge k}\frac{(-1)^{m-k}u^{(m-k)+k}}{(m-k)!((m-k)+2k)!}\\
&=1+2\sum_{\ell\ge1}t^\ell\sum_{k\ge1}k^{2\ell}J_{2k}(2\sqrt{u})
\end{aligned} T ( t , u ) = 1 + 2 m ≥ 1 ∑ k = 1 ∑ m ( m − k )! ( m + k )! ( − 1 ) m − k u m n ≥ 0 ∑ k 2 ( n + m ) t n + m = 1 + 2 ℓ ≥ 1 ∑ t ℓ m = 1 ∑ ℓ u m k = 1 ∑ m k 2 ℓ ( m − k )! ( m + k )! ( − 1 ) m − k = 1 + 2 ℓ ≥ 1 ∑ t ℓ m ≥ 1 ∑ u m k = 1 ∑ m k 2 ℓ ( m − k )! ( m + k )! ( − 1 ) m − k = 1 + 2 ℓ ≥ 1 ∑ t ℓ k ≥ 1 ∑ k 2 ℓ m ≥ k ∑ ( m − k )! (( m − k ) + 2 k )! ( − 1 ) m − k u ( m − k ) + k = 1 + 2 ℓ ≥ 1 ∑ t ℓ k ≥ 1 ∑ k 2 ℓ J 2 k ( 2 u )
where the extension of the summation range of m m m to m > ℓ m>\ell m > ℓ in the third line is justified by Lemma 1, and the interchange of summations in the fourth line by absolute convergence (for fixed ℓ \ell ℓ and u u u ).
Next we apply the rescaled Borel transform B \mathcal{B} B and obtain
B ⃗ ( t , u ) = 1 + 2 ∑ ℓ ≥ 1 ( 2 t ) ℓ ( 2 ℓ ) ! ∑ k ≥ 1 k 2 ℓ J 2 k ( 2 u ) = 1 + 2 ∑ k ≥ 1 J 2 k ( 2 u ) ∑ ℓ ≥ 1 ( k 2 t ) 2 ℓ ( 2 ℓ ) ! = 1 + 2 ∑ k ≥ 1 J 2 k ( 2 u ) ( cosh ( k 2 t ) − 1 ) = 1 + J 0 ( 2 u ) + 2 ∑ k ≥ 1 J 2 k ( 2 u ) cosh ( k 2 t ) − ( J 0 ( 2 u ) + 2 ∑ k ≥ 1 J 2 k ( 2 u ) ) . \begin{aligned}
\vec{\mathcal{B}}(t,u)&=1+2\sum_{\ell\ge1}\frac{(2t)^\ell}{(2\ell)!}\sum_{k\ge1}k^{2\ell}J_{2k}(2\sqrt{u})\\
&=1+2\sum_{k\ge1}J_{2k}(2\sqrt{u})\sum_{\ell\ge1}\frac{(k\sqrt{2t})^{2\ell}}{(2\ell)!}\\
&=1+2\sum_{k\ge1}J_{2k}(2\sqrt{u})\left(\cosh(k\sqrt{2t})-1\right)\\
&=1+J_0(2\sqrt{u})+2\sum_{k\ge1}J_{2k}(2\sqrt{u})\cosh(k\sqrt{2t})-\left(J_0(2\sqrt{u})+2\sum_{k\ge1}J_{2k}(2\sqrt{u})\right).
\end{aligned} B ( t , u ) = 1 + 2 ℓ ≥ 1 ∑ ( 2 ℓ )! ( 2 t ) ℓ k ≥ 1 ∑ k 2 ℓ J 2 k ( 2 u ) = 1 + 2 k ≥ 1 ∑ J 2 k ( 2 u ) ℓ ≥ 1 ∑ ( 2 ℓ )! ( k 2 t ) 2 ℓ = 1 + 2 k ≥ 1 ∑ J 2 k ( 2 u ) ( cosh ( k 2 t ) − 1 ) = 1 + J 0 ( 2 u ) + 2 k ≥ 1 ∑ J 2 k ( 2 u ) cosh ( k 2 t ) − ( J 0 ( 2 u ) + 2 k ≥ 1 ∑ J 2 k ( 2 u ) ) .
Now, we use the generating function
∑ n ∈ Z J n ( z ) v n = exp ( z 2 ( v − 1 v ) ) , v ≠ 0 , \sum_{n\in\mathbb{Z}}J_n(z)v^n=\exp\left(\frac{z}{2}\left(v-\frac{1}{v}\right)\right),\qquad v\ne0, n ∈ Z ∑ J n ( z ) v n = exp ( 2 z ( v − v 1 ) ) , v = 0 ,
see [17 Eq. 10.12.1] , together with J − n = ( − 1 ) n J n J_{-n}=(-1)^nJ_n J − n = ( − 1 ) n J n . Putting v = e θ v=e^\theta v = e θ and taking the part that is even in θ \theta θ gives
J 0 ( z ) + 2 ∑ k ≥ 1 J 2 k ( z ) cosh ( 2 k θ ) = cosh ( z sinh θ ) ; J_0(z)+2\sum_{k\ge1}J_{2k}(z)\cosh(2k\theta)=\cosh(z\sinh\theta); J 0 ( z ) + 2 k ≥ 1 ∑ J 2 k ( z ) cosh ( 2 k θ ) = cosh ( z sinh θ ) ;
in particular, for θ = 0 \theta=0 θ = 0 , J 0 ( z ) + 2 ∑ k ≥ 1 J 2 k ( z ) = 1 J_0(z)+2\sum_{k\ge1}J_{2k}(z)=1 J 0 ( z ) + 2 ∑ k ≥ 1 J 2 k ( z ) = 1 . With z = 2 u z=2\sqrt{u} z = 2 u and θ = 2 t / 2 \theta=\sqrt{2t}/2 θ = 2 t /2 we obtain
B ⃗ ( t , u ) = cosh ( 2 u sinh 2 t 2 ) = cosh ( 2 u ( cosh 2 t − 1 ) ) , \vec{\mathcal{B}}(t,u)=\cosh\left(2\sqrt{u}\sinh\frac{\sqrt{2t}}{2}\right)=\cosh\left(\sqrt{2u(\cosh\sqrt{2t}-1)}\right), B ( t , u ) = cosh ( 2 u sinh 2 2 t ) = cosh ( 2 u ( cosh 2 t − 1 ) ) ,
because cosh 2 t − 1 = 2 sinh 2 ( 2 t / 2 ) \cosh\sqrt{2t}-1=2\sinh^2(\sqrt{2t}/2) cosh 2 t − 1 = 2 sinh 2 ( 2 t /2 ) . This is (27) , as desired. □
Remark 7. This closed form is structurally analogous to the exponential generating function exp ( u ( e t − 1 ) ) \exp(u(e^t-1)) exp ( u ( e t − 1 )) for set partitions: both occurrences of the exponential function are replaced by E ( y ) = cosh ( 2 y ) E(y)=\cosh(\sqrt{2}y) E ( y ) = cosh ( 2 y ) . More precisely, the coefficients [ t n ] T → ( t , 1 ) [t^n]\overrightarrow{T}(t,1) [ t n ] T ( t , 1 ) form the even-index subsequence of the central Bell numbers associated with the central factorial numbers of the second kind [28 ] . The same sequence is listed in OEIS A135920, where it is referred to as a generalized Bell number sequence. A combinatorial explanation of this analogy, in terms of partitions into blocks of even size, is given in § 7 .
Remark 8. The (exponential generating) function in (26) has also been studied in the literature, but in a different context. It is obviously differentially algebraic, but its ordinary counterpart, (its inverse Borel transform) is not, as Klazar [29 ] has shown.
To obtain coefficient asymptotics for B → ( t , 1 ) \overrightarrow{B}(t,1) B ( t , 1 ) , we use Hayman’s theory of H \mathcal{H} H -admissible functions [26 ] . They are amenable to the saddle-point method in a straight-forward fashion by design. For such functions, say f ( z ) f(z) f ( z ) , the saddle point ρ n \rho_n ρ n is determined via the logarithmic derivative a f ( r ) : = r f ′ ( r ) / f ( r ) a_f(r):=rf'(r)/f(r) a f ( r ) := r f ′ ( r ) / f ( r ) by a f ( ρ n ) = n a_f(\rho_n)=n a f ( ρ n ) = n , while the second-order logarithmic derivative b f ( r ) : = r a f ′ ( r ) b_f(r):=ra_f'(r) b f ( r ) := r a f ′ ( r ) governs the width of the Gaussian-like peak around the saddle point. Once H \mathcal{H} H -admissibility is established, these quantities yield the standard Hayman coefficient asymptotics [26 ] based on the saddle-point method. We therefore first collect the corresponding data needed for B → ( t , 1 ) \overrightarrow{B}(t,1) B ( t , 1 ) , which will later also be used in the bivariate analysis for u u u near 1.
Lemma 2 (Hayman data). For simplicity, set g ( t ) : = E ( t ) − 1 g(t):=E(t)-1 g ( t ) := E ( t ) − 1 , with E ( t ) E(t) E ( t ) given in (26), and define for any function h ( z ) h(z) h ( z ) its first-order and second-order logarithmic derivatives by
a h ( z ) : = z h ′ ( z ) h ( z ) , b h ( z ) : = z a h ′ ( z ) . (28) a_h(z):=\frac{zh'(z)}{h(z)},\qquad b_h(z):=za_h'(z). \tag*{(28)} a h ( z ) := h ( z ) z h ′ ( z ) , b h ( z ) := z a h ′ ( z ) . (28) Then
a E ( z ) = 2 z 2 tanh ( 2 z ) , b E ( z ) = 2 z 4 tanh ( 2 z ) + z 2 sech 2 ( 2 z ) , a_E(z)=\frac{\sqrt{2z}}{2}\tanh(\sqrt{2z}),\qquad b_E(z)=\frac{\sqrt{2z}}{4}\tanh(\sqrt{2z})+\frac{z}{2}\operatorname{sech}^{2}(\sqrt{2z}), a E ( z ) = 2 2 z tanh ( 2 z ) , b E ( z ) = 4 2 z tanh ( 2 z ) + 2 z sech 2 ( 2 z ) , and
a g ( z ) = z 2 coth ( z 2 ) , b g ( z ) = 1 2 z 2 coth ( z 2 ) − z 4 csch 2 ( z 2 ) . a_g(z)=\sqrt{\frac{z}{2}}\coth\left(\sqrt{\frac{z}{2}}\right),\qquad b_g(z)=\frac{1}{2}\sqrt{\frac{z}{2}}\coth\left(\sqrt{\frac{z}{2}}\right)-\frac{z}{4}\operatorname{csch}^{2}\left(\sqrt{\frac{z}{2}}\right). a g ( z ) = 2 z coth ( 2 z ) , b g ( z ) = 2 1 2 z coth ( 2 z ) − 4 z csch 2 ( 2 z ) . Moreover, as z → ∞ z\to\infty z → ∞ , we have
E ( z ) ∼ g ( z ) ∼ 1 2 e 2 z , a E ( z ) ∼ a g ( z ) ∼ z 2 , b E ( z ) ∼ b g ( z ) ∼ z 8 . E(z)\sim g(z)\sim\frac{1}{2}e^{\sqrt{2z}},\qquad a_E(z)\sim a_g(z)\sim\sqrt{\frac{z}{2}},\qquad b_E(z)\sim b_g(z)\sim\sqrt{\frac{z}{8}}. E ( z ) ∼ g ( z ) ∼ 2 1 e 2 z , a E ( z ) ∼ a g ( z ) ∼ 2 z , b E ( z ) ∼ b g ( z ) ∼ 8 z . Proof. By (26) we have
E ′ ( z ) = sinh ( 2 z ) 2 z , E'(z)=\frac{\sinh(\sqrt{2z})}{\sqrt{2z}}, E ′ ( z ) = 2 z sinh ( 2 z ) , and therefore
a E ( z ) = 2 z 2 tanh ( 2 z ) . a_E(z)=\frac{\sqrt{2z}}{2}\tanh(\sqrt{2z}). a E ( z ) = 2 2 z tanh ( 2 z ) . Differentiating once more and using b E ( z ) = z a E ′ ( z ) b_E(z)=za_E'(z) b E ( z ) = z a E ′ ( z ) gives
b E ( z ) = 2 z 4 tanh ( 2 z ) + z 2 sech 2 ( 2 z ) . b_E(z)=\frac{\sqrt{2z}}{4}\tanh(\sqrt{2z})+\frac{z}{2}\operatorname{sech}^{2}(\sqrt{2z}). b E ( z ) = 4 2 z tanh ( 2 z ) + 2 z sech 2 ( 2 z ) .
The standard hyperbolic identities then give
a g ( z ) = z 2 coth ( z 2 ) a_g(z)=\sqrt{\frac{z}{2}}\coth\left(\sqrt{\frac{z}{2}}\right) a g ( z ) = 2 z coth ( 2 z )
and therefore
b g ( z ) = z a g ′ ( z ) = 1 2 z 2 coth ( z 2 ) − z 4 csch 2 ( z 2 ) . b_g(z)=za_g'(z)=\frac{1}{2}\sqrt{\frac{z}{2}}\coth\left(\sqrt{\frac{z}{2}}\right)-\frac{z}{4}\operatorname{csch}^{2}\left(\sqrt{\frac{z}{2}}\right). b g ( z ) = z a g ′ ( z ) = 2 1 2 z coth ( 2 z ) − 4 z csch 2 ( 2 z ) .
The stated asymptotic relations follow immediately from tanh x → 1 \tanh x\to1 tanh x → 1 , coth x → 1 \coth x\to1 coth x → 1 , sech x → 0 \operatorname{sech}x\to0 sech x → 0 , csch x → 0 \operatorname{csch}x\to0 csch x → 0 and cosh x ∼ 1 2 e x \cosh x\sim\frac{1}{2}e^x cosh x ∼ 2 1 e x , as x → ∞ x\to\infty x → ∞ . □
Theorem 3 (Asymptotic number of histories). The entire function t ↦ B ⃗ ( t , 1 ) t\mapsto\vec{B}(t,1) t ↦ B ( t , 1 ) given by (26) is H \mathcal{H} H -admissible in the sense of [26 ] in the whole complex plane. Let w n = W ( 2 n ) w_n=W(2n) w n = W ( 2 n ) , then, as n → ∞ n\to\infty n → ∞ ,
c n : = [ z n ] T ⃗ ( t , 1 ) ∼ 1 w n + 1 exp ( 2 n ( w n + 1 w n ) ) ( 2 e ) 2 n c_n:=[z^n]\vec{T}(t,1)\sim\frac{1}{\sqrt{w_n+1}}\frac{\exp\left(2n\left(w_n+\frac{1}{w_n}\right)\right)}{(2e)^{2n}} c n := [ z n ] T ( t , 1 ) ∼ w n + 1 1 ( 2 e ) 2 n exp ( 2 n ( w n + w n 1 ) )
Proof. With E ( t ) E(t) E ( t ) and g ( t ) g(t) g ( t ) as in Lemma 2, write
F ( t ) : = B ⃗ ( t , 1 ) = E ( g ( t ) ) . F(t):=\vec{B}(t,1)=E(g(t)). F ( t ) := B ( t , 1 ) = E ( g ( t )) .
Since E E E and g g g are entire and g ( r ) > 0 g(r)>0 g ( r ) > 0 for r > 0 r>0 r > 0 , the function F F F is entire and F ( r ) > 0 F(r)>0 F ( r ) > 0 for r > 0 r>0 r > 0 . We verify Hayman admissibility in the sense of [26 ] . To this end, first write a ( z ) : = a F ( z ) a(z):=a_F(z) a ( z ) := a F ( z ) and b ( z ) : = b F ( z ) b(z):=b_F(z) b ( z ) := b F ( z ) . We have to verify three conditions: First, the second-order logarithmic derivative b ( z ) b(z) b ( z ) must tend to infinity on the positive real axis. Second, F ( z ) F(z) F ( z ) has an asymptotic representation as ∣ z ∣ → ∞ |z|\to\infty ∣ z ∣ → ∞ involving the Hayman data and which is valid near the real axis. Precisely, there is a function δ \delta δ such that for z = r e i θ z=re^{i\theta} z = r e i θ with r → ∞ r\to\infty r → ∞ the asymptotic relation
F ( r e i θ ) ∼ F ( r ) e i a ( r ) θ − b ( r ) θ 2 / 2 F(re^{i\theta})\sim F(r)e^{ia(r)\theta-b(r)\theta^2/2} F ( r e i θ ) ∼ F ( r ) e ia ( r ) θ − b ( r ) θ 2 /2
holds uniformly for ∣ θ ∣ ≤ δ ( r ) |\theta|\le\delta(r) ∣ θ ∣ ≤ δ ( r ) , i.e. , the modulus of F ( z ) F(z) F ( z ) is Gaussian near the real axis. Third, farther away from the real axis the modulus of F ( z ) F(z) F ( z ) is small and there is an upper bound involving only the Hayman data. Precisely, we must have F ( z ) = o ( F ( r ) / b ( r ) ) F(z)=o(F(r)/\sqrt{b(r)}) F ( z ) = o ( F ( r ) / b ( r ) ) , as r → ∞ r\to\infty r → ∞ , uniformly for ∣ θ ∣ ≥ δ ( r ) |\theta|\ge\delta(r) ∣ θ ∣ ≥ δ ( r ) . By Lemma 2 and the chain rule, the Hayman data are
a ( r ) = a g ( r ) a E ( g ( r ) ) , b ( r ) = b g ( r ) a E ( g ( r ) ) + a g ( r ) 2 b E ( g ( r ) ) . (29) a(r)=a_g(r)a_E(g(r)),\qquad b(r)=b_g(r)a_E(g(r))+a_g(r)^2b_E(g(r)). \tag*{(29)} a ( r ) = a g ( r ) a E ( g ( r )) , b ( r ) = b g ( r ) a E ( g ( r )) + a g ( r ) 2 b E ( g ( r )) . (29)
For defining the region around the real axis, fix
δ ( r ) : = b ( r ) − 2 / 5 . \delta(r):=b(r)^{-2/5}. δ ( r ) := b ( r ) − 2/5 .
Condition [26 (2.6)] : divergence of b ( r ) b(r) b ( r ) . Using (28) and Lemma 2, we have
a g ( r ) ∼ r 2 , b g ( r ) ∼ r 8 , g ( r ) ∼ 1 2 e 2 r . a_g(r)\sim\sqrt{\frac{r}{2}},\qquad b_g(r)\sim\sqrt{\frac{r}{8}},\qquad g(r)\sim\frac{1}{2}e^{\sqrt{2r}}. a g ( r ) ∼ 2 r , b g ( r ) ∼ 8 r , g ( r ) ∼ 2 1 e 2 r .
Moreover,
a E ( z ) ∼ z 2 , b E ( z ) ∼ z 8 , a_E(z)\sim\sqrt{\frac{z}{2}},\qquad b_E(z)\sim\sqrt{\frac{z}{8}}, a E ( z ) ∼ 2 z , b E ( z ) ∼ 8 z ,
and hence
a E ( g ( r ) ) = Θ ( e r / 2 ) , b E ( g ( r ) ) = Θ ( e r / 2 ) . a_E(g(r))=\Theta\left(e^{\sqrt{r/2}}\right),\qquad b_E(g(r))=\Theta\left(e^{\sqrt{r/2}}\right). a E ( g ( r )) = Θ ( e r /2 ) , b E ( g ( r )) = Θ ( e r /2 ) .
Therefore the two terms in (29) satisfy
b g ( r ) a E ( g ( r ) ) = Θ ( r e r / 2 ) , b_g(r)a_E(g(r))=\Theta\left(\sqrt{r}e^{\sqrt{r/2}}\right), b g ( r ) a E ( g ( r )) = Θ ( r e r /2 ) ,
whereas
a g ( r ) 2 b E ( g ( r ) ) = Θ ( r e r / 2 ) . a_g(r)^2b_E(g(r))=\Theta\left(re^{\sqrt{r/2}}\right). a g ( r ) 2 b E ( g ( r )) = Θ ( r e r /2 ) .
Thus the second term dominates, and consequently
b ( r ) ∼ a g ( r ) 2 b E ( g ( r ) ) = Θ ( r e r / 2 ) → r → ∞ ∞ . b(r)\sim a_g(r)^2b_E(g(r))=\Theta\left(re^{\sqrt{r/2}}\right)\xrightarrow{r\to\infty}\infty. b ( r ) ∼ a g ( r ) 2 b E ( g ( r )) = Θ ( r e r /2 ) r → ∞ ∞.
In particular, δ ( r ) → 0 \delta(r)\to0 δ ( r ) → 0 .
Condition [26 (2.4)] : local expansion for ∣ θ ∣ ≤ δ ( r ) |\theta|\le\delta(r) ∣ θ ∣ ≤ δ ( r ) . Set
L r ( θ ) : = log F ( r e i θ ) . L_r(\theta):=\log F(re^{i\theta}). L r ( θ ) := log F ( r e i θ ) .
Writing y = r / 2 y=\sqrt{r/2} y = r /2 , we have
F ( r e i θ ) = cosh ( 2 sinh ( y e i θ / 2 ) ) . F(re^{i\theta})=\cosh\left(2\sinh\left(ye^{i\theta/2}\right)\right). F ( r e i θ ) = cosh ( 2 sinh ( y e i θ /2 ) ) .
Since y δ ( r ) → 0 y\delta(r)\to0 y δ ( r ) → 0 , uniformly for ∣ θ ∣ ≤ δ ( r ) |\theta|\le\delta(r) ∣ θ ∣ ≤ δ ( r ) ,
ℜ ( 2 sinh ( y e i θ / 2 ) ) = 2 sinh ( y cos ( θ / 2 ) ) cos ( y sin ( θ / 2 ) ) > 0 \Re\left(2\sinh\left(ye^{i\theta/2}\right)\right)=2\sinh(y\cos(\theta/2))\cos(y\sin(\theta/2))>0 ℜ ( 2 sinh ( y e i θ /2 ) ) = 2 sinh ( y cos ( θ /2 )) cos ( y sin ( θ /2 )) > 0
for all sufficiently large r r r . The zeros of cosh z \cosh z cosh z are purely imaginary, so F ( r e i θ ) ≠ 0 F(re^{i\theta})\ne0 F ( r e i θ ) = 0 throughout this arc. Hence L r ( θ ) = log F ( r e i θ ) L_r(\theta)=\log F(re^{i\theta}) L r ( θ ) = log F ( r e i θ ) can be chosen analytic on a neighbourhood of the arc. On this zero-free neighbourhood, let
a ( z ) : = z F ′ ( z ) F ( z ) , b ( z ) : = z a ′ ( z ) , a(z):=z\frac{F'(z)}{F(z)},\qquad b(z):=za'(z), a ( z ) := z F ( z ) F ′ ( z ) , b ( z ) := z a ′ ( z ) ,
so that these functions extend the quantities a ( r ) a(r) a ( r ) and b ( r ) b(r) b ( r ) defined above. Taylor’s theorem with remainder yields, uniformly for ∣ θ ∣ ≤ δ ( r ) |\theta|\le\delta(r) ∣ θ ∣ ≤ δ ( r ) ,
L r ( θ ) = L r ( 0 ) + i θ a ( r ) − θ 2 2 b ( r ) + O ( ∣ θ ∣ 3 sup ∣ φ ∣ ≤ ∣ θ ∣ ∣ r e i φ b ′ ( r e i φ ) ∣ ) . L_r(\theta)=L_r(0)+i\theta a(r)-\frac{\theta^2}{2}b(r)+O\left(|\theta|^3\sup_{|\varphi|\le|\theta|}\left|re^{i\varphi}b'(re^{i\varphi})\right|\right). L r ( θ ) = L r ( 0 ) + i θ a ( r ) − 2 θ 2 b ( r ) + O ( ∣ θ ∣ 3 ∣ φ ∣ ≤ ∣ θ ∣ sup r e i φ b ′ ( r e i φ ) ) .
Using the explicit expressions from Lemma 2, differentiation of b ( z ) b(z) b ( z ) from (29) gives, uniformly for ∣ φ ∣ ≤ δ ( r ) |\varphi|\le\delta(r) ∣ φ ∣ ≤ δ ( r ) ,
∣ r e i φ b ′ ( r e i φ ) ∣ = O ( r b ( r ) ) . \left|re^{i\varphi}b'(re^{i\varphi})\right|=O\left(\sqrt{r}b(r)\right). r e i φ b ′ ( r e i φ ) = O ( r b ( r ) ) .
Indeed, since y δ ( r ) = o ( 1 ) y\delta(r)=o(1) y δ ( r ) = o ( 1 ) , the standard hyperbolic estimates used in Lemma 2 hold uniformly on this shrinking arc, and hence
a g ( z ) , b g ( z ) , z b g ′ ( z ) = O ( r ) , a_g(z),\ b_g(z),\ zb'_g(z)=O(\sqrt{r}), a g ( z ) , b g ( z ) , z b g ′ ( z ) = O ( r ) ,
whereas
a E ( g ( z ) ) , b E ( g ( z ) ) , g ( z ) b E ′ ( g ( z ) ) = O ( e r / 2 ) . a_E(g(z)),\ b_E(g(z)),\ g(z)b'_E(g(z))=O\left(e^{\sqrt{r/2}}\right). a E ( g ( z )) , b E ( g ( z )) , g ( z ) b E ′ ( g ( z )) = O ( e r /2 ) .
Since b ( r ) = Θ ( r e r / 2 ) b(r)=\Theta\left(re^{\sqrt{r/2}}\right) b ( r ) = Θ ( r e r /2 ) , the Taylor remainder is therefore uniformly bounded by
O ( δ ( r ) 3 r b ( r ) ) = O ( r b ( r ) − 1 / 5 ) = o ( 1 ) . O\left(\delta(r)^3\sqrt{r}b(r)\right)=O\left(\sqrt{r}b(r)^{-1/5}\right)=o(1). O ( δ ( r ) 3 r b ( r ) ) = O ( r b ( r ) − 1/5 ) = o ( 1 ) .
This proves the local Gaussian approximation.
Condition [26 (2.5)] : tail bound for δ ( r ) ≤ ∣ θ ∣ ≤ π \delta(r) \leq|\theta| \leq\pi δ ( r ) ≤ ∣ θ ∣ ≤ π . Let z = r e i θ z = r e^{i\theta} z = r e i θ , with δ ( r ) ≤ ∣ θ ∣ ≤ π \delta(r) \leq|\theta| \leq\pi δ ( r ) ≤ ∣ θ ∣ ≤ π , and set
η ( z ) : = 2 ( cosh ( 2 z ) − 1 ) . (30) \eta(z) := \sqrt{2\left(\cosh\left(\sqrt{2z}\right)-1\right)}. \tag*{(30)} η ( z ) := 2 ( cosh ( 2 z ) − 1 ) . (30)
Since cosh is even, the value of cosh ( η ( z ) ) \cosh(\eta(z)) cosh ( η ( z )) is independent of the branch of the square root, and F ( z ) = cosh ( η ( z ) ) F(z)=\cosh(\eta(z)) F ( z ) = cosh ( η ( z )) .
Small angles: δ ( r ) ≤ ∣ θ ∣ ≤ 1 \delta(r) \leq|\theta| \leq1 δ ( r ) ≤ ∣ θ ∣ ≤ 1 . Here
ℜ ( 2 z ) = 2 r cos ( θ / 2 ) → ∞ , \Re\left(\sqrt{2z}\right)=\sqrt{2r}\cos(\theta/2)\to\infty, ℜ ( 2 z ) = 2 r cos ( θ /2 ) → ∞ ,
and therefore
cosh ( 2 z ) − 1 = 1 2 e 2 z ( 1 + O ( e − ℜ ( 2 z ) ) ) . \cosh\left(\sqrt{2z}\right)-1=\frac{1}{2}e^{\sqrt{2z}}\left(1+O\left(e^{-\Re(\sqrt{2z})}\right)\right). cosh ( 2 z ) − 1 = 2 1 e 2 z ( 1 + O ( e − ℜ ( 2 z ) ) ) .
Consequently,
∣ η ( z ) ∣ ∼ exp ( r / 2 cos ( θ / 2 ) ) . |\eta(z)|\sim\exp\left(\sqrt{r/2}\cos(\theta/2)\right). ∣ η ( z ) ∣ ∼ exp ( r /2 cos ( θ /2 ) ) .
Using ∣ cosh w ∣ ≤ e ∣ w ∣ |\cosh w|\leq e^{|w|} ∣ cosh w ∣ ≤ e ∣ w ∣ , we get
log ∣ F ( z ) ∣ ≤ ∣ η ( z ) ∣ ∼ exp ( r / 2 cos ( θ / 2 ) ) . \log|F(z)|\leq|\eta(z)|\sim\exp\left(\sqrt{r/2}\cos(\theta/2)\right). log ∣ F ( z ) ∣ ≤ ∣ η ( z ) ∣ ∼ exp ( r /2 cos ( θ /2 ) ) .
Since
log F ( r ) ∼ exp ( r / 2 ) \log F(r)\sim\exp\left(\sqrt{r/2}\right) log F ( r ) ∼ exp ( r /2 )
and 1 − cos ( θ / 2 ) ≥ θ 2 / 12 1-\cos(\theta/2)\geq\theta^2/12 1 − cos ( θ /2 ) ≥ θ 2 /12 for ∣ θ ∣ ≤ 1 |\theta|\leq1 ∣ θ ∣ ≤ 1 , we get the estimate
log ∣ F ( r e i θ ) ∣ − log F ( r ) ≤ e r / 2 ( exp ( − θ 2 12 r 2 ) − 1 ) ≤ e r / 2 ( exp ( − δ ( r ) 2 12 r 2 ) − 1 ) . \begin{aligned}
\log|F(re^{i\theta})|-\log F(r)\leq e^{\sqrt{r/2}}\left(\exp\left(-\frac{\theta^2}{12}\sqrt{\frac{r}{2}}\right)-1\right) \\
&\leq e^{\sqrt{r/2}}\left(\exp\left(-\frac{\delta(r)^2}{12}\sqrt{\frac{r}{2}}\right)-1\right).
\end{aligned} log ∣ F ( r e i θ ) ∣ − log F ( r ) ≤ e r /2 ( exp ( − 12 θ 2 2 r ) − 1 ) ≤ e r /2 ( exp ( − 12 δ ( r ) 2 2 r ) − 1 ) .
Now observe δ ( r ) 2 r ≻ r − 3 / 10 exp ( − ( 4 / 5 ) r / 2 ) → 0 \delta(r)^2\sqrt{r}\succ r^{-3/10}\exp\left(-(4/5)\sqrt{r/2}\right)\to0 δ ( r ) 2 r ≻ r − 3/10 exp ( − ( 4/5 ) r /2 ) → 0 , as r → ∞ r\to\infty r → ∞ , there exists a constant c > 0 c>0 c > 0 such that
log ∣ F ( r e i θ ) ∣ − log F ( r ) ≤ − c r − 3 / 10 exp ( r 5 2 ) = o ( log b ( r ) ) (31) \log|F(re^{i\theta})|-\log F(r)\leq-cr^{-3/10}\exp\left(\frac{\sqrt{r}}{5\sqrt{2}}\right)=o(\log b(r)) \tag*{(31)} log ∣ F ( r e i θ ) ∣ − log F ( r ) ≤ − c r − 3/10 exp ( 5 2 r ) = o ( log b ( r )) (31)
where we used b ( r ) ≍ r e r / 2 b(r)\asymp re^{\sqrt{r/2}} b ( r ) ≍ r e r /2 . Hence
∣ F ( r e i θ ) ∣ = o ( F ( r ) b ( r ) ) for δ ( r ) ≤ ∣ θ ∣ ≤ 1. |F(re^{i\theta})|=o\left(\frac{F(r)}{\sqrt{b(r)}}\right)\quad\text{for }\delta(r)\leq|\theta|\leq1. ∣ F ( r e i θ ) ∣ = o ( b ( r ) F ( r ) ) for δ ( r ) ≤ ∣ θ ∣ ≤ 1.
Large angles: 1 ≤ ∣ θ ∣ ≤ π 1\leq|\theta|\leq\pi 1 ≤ ∣ θ ∣ ≤ π . Then
ℜ ( 2 z ) = 2 r cos ( θ / 2 ) ≤ 2 r cos ( 1 / 2 ) , \Re\left(\sqrt{2z}\right)=\sqrt{2r}\cos(\theta/2)\leq\sqrt{2r}\cos(1/2), ℜ ( 2 z ) = 2 r cos ( θ /2 ) ≤ 2 r cos ( 1/2 ) ,
and therefore ∣ η ( z ) ∣ = O ( exp ( r / 2 cos ( 1 / 2 ) ) ) |\eta(z)|=O\left(\exp\left(\sqrt{r/2}\cos(1/2)\right)\right) ∣ η ( z ) ∣ = O ( exp ( r /2 cos ( 1/2 ) ) ) , which implies
log ∣ F ( z ) ∣ = O ( e r / 2 cos ( 1 / 2 ) ) . \log|F(z)|=O\left(e^{\sqrt{r/2}\cos(1/2)}\right). log ∣ F ( z ) ∣ = O ( e r /2 c o s ( 1/2 ) ) .
Since log F ( r ) ≍ e r / 2 \log F(r)\asymp e^{\sqrt{r/2}} log F ( r ) ≍ e r /2 , this gives log ∣ F ( z ) ∣ = o ( log F ( r ) ) \log|F(z)|=o(\log F(r)) log ∣ F ( z ) ∣ = o ( log F ( r )) and thus
log ( ∣ F ( z ) ∣ b ( r ) F ( r ) ) ≤ 1 2 log b ( r ) − log F ( r ) + o ( log F ( r ) ) ⟶ r → ∞ − ∞ . (32) \log\left(\frac{|F(z)|\sqrt{b(r)}}{F(r)}\right)\le\frac{1}{2}\log b(r)-\log F(r)+o(\log F(r))\longrightarrow_{r\to\infty}-\infty. \tag*{(32)} log ( F ( r ) ∣ F ( z ) ∣ b ( r ) ) ≤ 2 1 log b ( r ) − log F ( r ) + o ( log F ( r )) ⟶ r → ∞ − ∞. (32)
This proves the tail condition. Hence F ( t ) = B ⃗ ( t , 1 ) F(t)=\vec{B}(t,1) F ( t ) = B ( t , 1 ) is H \mathcal{H} H -admissible.
What remains to be done in order to derive the asymptotic value of c n c_n c n is to determine the asymptotic location of the saddle point ρ n \rho_n ρ n and of b ( ρ n ) b(\rho_n) b ( ρ n ) . Writing y = r / 2 y=\sqrt{r/2} y = r /2 , we have
a ( r ) = y cosh ( y ) tanh ( 2 sinh y ) . a(r)=y\cosh(y)\tanh(2\sinh y). a ( r ) = y cosh ( y ) tanh ( 2 sinh y ) .
The right-hand side is strictly increasing from 0 0 0 to + ∞ +\infty + ∞ for y > 0 y>0 y > 0 . Hence, for every n ≥ 1 n\ge1 n ≥ 1 , there is a unique ρ n > 0 \rho_n>0 ρ n > 0 satisfying a ( ρ n ) = n a(\rho_n)=n a ( ρ n ) = n .
By Hayman’s coefficient theorem [26 Corollary II, p. 69] , letting ρ n \rho_n ρ n be this unique solution, we have
[ t n ] F ( t ) ∼ F ( ρ n ) ρ n n 2 π b ( ρ n ) . [t^n]F(t)\sim\frac{F(\rho_n)}{\rho_n^n\sqrt{2\pi b(\rho_n)}}. [ t n ] F ( t ) ∼ ρ n n 2 π b ( ρ n ) F ( ρ n ) .
Using the coefficient relation (25), this gives
c n ∼ ( 2 n ) ! 2 n F ( ρ n ) ρ n n 2 π b ( ρ n ) . (33) c_n\sim\frac{(2n)!}{2^n}\frac{F(\rho_n)}{\rho_n^n\sqrt{2\pi b(\rho_n)}}. \tag*{(33)} c n ∼ 2 n ( 2 n )! ρ n n 2 π b ( ρ n ) F ( ρ n ) . (33)
It remains to evaluate the terms in (32). Write
y n : = ρ n 2 . y_n:=\sqrt{\frac{\rho_n}{2}}. y n := 2 ρ n .
Then
g ( ρ n ) = cosh ( 2 y n ) − 1 = 2 sinh 2 y n , g(\rho_n)=\cosh(2y_n)-1=2\sinh^2 y_n, g ( ρ n ) = cosh ( 2 y n ) − 1 = 2 sinh 2 y n ,
and hence
a g ( ρ n ) = y n coth y n , a E ( g ( ρ n ) ) = sinh y n tanh ( 2 sinh y n ) . a_g(\rho_n)=y_n\coth y_n,\qquad a_E(g(\rho_n))=\sinh y_n\tanh(2\sinh y_n). a g ( ρ n ) = y n coth y n , a E ( g ( ρ n )) = sinh y n tanh ( 2 sinh y n ) .
Therefore the saddle-point equation a ( ρ n ) = n a(\rho_n)=n a ( ρ n ) = n becomes
n = y n cosh ( y n ) tanh ( 2 sinh y n ) . n=y_n\cosh(y_n)\tanh(2\sinh y_n). n = y n cosh ( y n ) tanh ( 2 sinh y n ) .
Using
cosh y n = e y n 2 ( 1 + e − 2 y n ) \cosh y_n=\frac{e^{y_n}}{2}\left(1+e^{-2y_n}\right) cosh y n = 2 e y n ( 1 + e − 2 y n )
and
tanh ( 2 sinh y n ) = 1 + O ( e − 4 sinh y n ) , \tanh(2\sinh y_n)=1+O\left(e^{-4\sinh y_n}\right), tanh ( 2 sinh y n ) = 1 + O ( e − 4 s i n h y n ) ,
the saddle-point equation yields
2 n = y n e y n ( 1 + O ( e − 2 y n ) ) . 2n=y_ne^{y_n}\left(1+O\left(e^{-2y_n}\right)\right). 2 n = y n e y n ( 1 + O ( e − 2 y n ) ) .
Comparing the saddle-point equation with the defining relation for w n w_n w n , w n e w n = 2 n w_ne^{w_n}=2n w n e w n = 2 n , and using
∂ y ( y e y ) = ( 1 + y ) e y , \partial_y(ye^y)=(1+y)e^y, ∂ y ( y e y ) = ( 1 + y ) e y ,
the mean value theorem gives directly
y n = w n + O ( e − 2 w n ) . y_n=w_n+O\left(e^{-2w_n}\right). y n = w n + O ( e − 2 w n ) .
Consequently,
ρ n = 2 w n 2 ( 1 + O ( w n n 2 ) ) , \rho_n=2w_n^2\left(1+O\left(\frac{w_n}{n^2}\right)\right), ρ n = 2 w n 2 ( 1 + O ( n 2 w n ) ) ,
and in particular
ρ n n = ( 2 w n 2 ) n exp ( O ( w n n ) ) . \rho_n^n = (2w_n^2)^n \exp\left(\mathcal{O}\left(\frac{w_n}{n}\right)\right). ρ n n = ( 2 w n 2 ) n exp ( O ( n w n ) ) .
For the evaluation of F ( ρ n ) F(\rho_n) F ( ρ n ) , we use
F ( ρ n ) = cosh ( 2 sinh y n ) . F(\rho_n) = \cosh(2\sinh y_n). F ( ρ n ) = cosh ( 2 sinh y n ) .
The saddle-point equation implies
2 sinh y n = 2 n w n + o ( 1 ) , 2\sinh y_n = \frac{2n}{w_n} + o(1), 2 sinh y n = w n 2 n + o ( 1 ) ,
and therefore
F ( ρ n ) = 1 2 exp ( 2 n w n ) ( 1 + o ( 1 ) ) . (34) F(\rho_n) = \frac{1}{2}\exp\left(\frac{2n}{w_n}\right)(1+o(1)). \tag*{(34)} F ( ρ n ) = 2 1 exp ( w n 2 n ) ( 1 + o ( 1 )) . (34)
Next, using the Hayman data in (29) at r = ρ n = 2 y n 2 r=\rho_n=2y_n^2 r = ρ n = 2 y n 2 , we obtain
b ( ρ n ) = n 2 ( y n + 1 ) ( 1 + o ( 1 ) ) = n 2 ( w n + 1 ) ( 1 + o ( 1 ) ) . b(\rho_n) = \frac{n}{2}(y_n+1)(1+o(1)) = \frac{n}{2}(w_n+1)(1+o(1)). b ( ρ n ) = 2 n ( y n + 1 ) ( 1 + o ( 1 )) = 2 n ( w n + 1 ) ( 1 + o ( 1 )) .
Thus
2 π b ( ρ n ) = π n ( w n + 1 ) ( 1 + o ( 1 ) ) . (35) \sqrt{2\pi b(\rho_n)} = \sqrt{\pi n(w_n+1)}(1+o(1)). \tag*{(35)} 2 π b ( ρ n ) = π n ( w n + 1 ) ( 1 + o ( 1 )) . (35)
Finally, Stirling’s formula gives
( 2 n ) ! = 4 π n ( 2 n e ) 2 n ( 1 + o ( 1 ) ) . (2n)! = \sqrt{4\pi n}\left(\frac{2n}{e}\right)^{2n}(1+o(1)). ( 2 n )! = 4 π n ( e 2 n ) 2 n ( 1 + o ( 1 )) .
Together with the preceding estimate for ρ n n \rho_n^n ρ n n and w n e w n = 2 n w_n e^{w_n}=2n w n e w n = 2 n , we find
( 2 n ) ! 2 n ρ n n = 4 π n exp ( 2 n w n ) 2 2 n e 2 n ( 1 + o ( 1 ) ) . \frac{(2n)!}{2^n\rho_n^n} = \sqrt{4\pi n}\frac{\exp(2nw_n)}{2^{2n}e^{2n}}(1+o(1)). 2 n ρ n n ( 2 n )! = 4 π n 2 2 n e 2 n exp ( 2 n w n ) ( 1 + o ( 1 )) .
Combining this estimate with (34) and (35) in (33) , we obtain
c n ∼ 1 w n + 1 exp ( 2 n ( w n + 1 w n ) ) ( 2 e ) 2 n . c_n \sim\frac{1}{\sqrt{w_n+1}}\frac{\exp\left(2n\left(w_n+\frac{1}{w_n}\right)\right)}{(2e)^{2n}}. c n ∼ w n + 1 1 ( 2 e ) 2 n exp ( 2 n ( w n + w n 1 ) ) .
This proves the theorem. □
Remark 9. Since ( 2 e ) − 2 n e 2 n w n = 2 − 2 n e 2 n ( w n − 1 ) (2e)^{-2n}e^{2nw_n}=2^{-2n}e^{2n(w_n-1)} ( 2 e ) − 2 n e 2 n w n = 2 − 2 n e 2 n ( w n − 1 ) , the exponential growth in Theorems 1 and 3 has the same shape 2 − 2 n exp ( 2 n ( ω − 1 + 1 / ω ) ) 2^{-2n}\exp(2n(\omega-1+1/\omega)) 2 − 2 n exp ( 2 n ( ω − 1 + 1/ ω )) , with ω = W ( n 2 ) \omega=W(n\sqrt{2}) ω = W ( n 2 ) and ω = W ( 2 n ) \omega=W(2n) ω = W ( 2 n ) , respectively.
The number of vertices in the DIG-model
In this section we turn to the distribution of the number of vertices in a random history in the DIG-model that is generated in n n n steps. We will work with the (rescaled) Borel transform B ⃗ ( t , u ) \vec{B}(t,u) B ( t , u ) of the bivariate generating function and show that like in the UIG-model a central limit theorem holds in the DIG-model. Recall that we set c n : = [ t n ] T ⃗ ( t , 1 ) c_n:=[t^n]\vec{T}(t,1) c n := [ t n ] T ( t , 1 ) in Theorem 3, Moreover, let c n , m = [ t n u m ] T ⃗ ( t , u ) c_{n,m}=[t^nu^m]\vec{T}(t,u) c n , m = [ t n u m ] T ( t , u ) be the number of histories that are generated in n n n steps and yield a graph with m m m vertices. Our proof is based on the concept of e-admissibility, see [18 ] , which extends Hayman admissibility to functions in two variables and yields a normal limit law. For the sake of the paper being self-contained, we state the definition of e-admissibility. This is essentially [18 Def. 1] , but specialized to entire functions which are positive on the positive real axis.
Definition 2. Let f ( z , u ) f(z,u) f ( z , u ) be a function and let and let a ( z , u ) a(z,u) a ( z , u ) , b ( z , u ) b(z,u) b ( z , u ) be its first-order and second-order logarithmic derivative with respect to z z z , respectively, and a ˉ ( z , u ) \bar{a}(z,u) a ˉ ( z , u ) , b ˉ ( z , u ) \bar{b}(z,u) b ˉ ( z , u ) their analogues with respect to u u u and c ( z , u ) = u ( ∂ u a ) ( z , u ) c(z,u)=u(\partial_u a)(z,u) c ( z , u ) = u ( ∂ u a ) ( z , u ) its mixed second-order logarithmic derivative. Finally, let B ( z , u ) B(z,u) B ( z , u ) denote the logarithmic Hessian of f ( z , u ) f(z,u) f ( z , u ) .
The function f ( z , u ) f(z,u) f ( z , u ) is called e-admissible of the following ten conditions are satisfied:
(1) f ( z , u ) f(z,u) f ( z , u ) is entire and f ( r , 1 ) > 0 f(r,1)>0 f ( r , 1 ) > 0 for positive r r r
(2) For each K > 0 K>0 K > 0 , setting ε ( r ) = K b ( r , 1 ) / det B ( r , 1 ) = K ( b ˉ ( r , 1 ) − c ( r , 1 ) 2 / b ( r , 1 ) ) − 1 / 2 \varepsilon(r)=K\sqrt{b(r,1)/\det B(r,1)}=K(\bar{b}(r,1)-c(r,1)^2/b(r,1))^{-1/2} ε ( r ) = K b ( r , 1 ) / det B ( r , 1 ) = K ( b ˉ ( r , 1 ) − c ( r , 1 ) 2 / b ( r , 1 ) ) − 1/2 , there is a function δ : ( 0 , ∞ ) → ( 0 , π ) \delta:(0,\infty)\to(0,\pi) δ : ( 0 , ∞ ) → ( 0 , π ) such that, as r → ∞ r\to\infty r → ∞ , we have
f ( r e i θ , u ) ∼ f ( r , u ) exp ( i θ a ( r , u ) − θ 2 2 b ( r , u ) ) , f(re^{i\theta},u)\sim f(r,u)\exp\left(i\theta a(r,u)-\frac{\theta^2}{2}b(r,u)\right), f ( r e i θ , u ) ∼ f ( r , u ) exp ( i θ a ( r , u ) − 2 θ 2 b ( r , u ) ) , uniformly for ∣ θ ∣ ≤ δ ( r ) |\theta|\le\delta(r) ∣ θ ∣ ≤ δ ( r ) and u ∈ [ 1 − ε ( r ) , 1 + ε ( r ) ] u\in[1-\varepsilon(r),1+\varepsilon(r)] u ∈ [ 1 − ε ( r ) , 1 + ε ( r )] .
(3) The estimate
f ( r e i θ , u ) = o ( f ( r , u ) b ( r , u ) ) , as r → ∞ , f(re^{i\theta},u)=o\left(\frac{f(r,u)}{\sqrt{b(r,u)}}\right),\qquad\text{as }r\to\infty, f ( r e i θ , u ) = o ( b ( r , u ) f ( r , u ) ) , as r → ∞ , holds uniformly for δ ( r ) ≤ ∣ θ ∣ ≤ π \delta(r)\le|\theta|\le\pi δ ( r ) ≤ ∣ θ ∣ ≤ π and u ∈ [ 1 − ε ( r ) , 1 + ε ( r ) ] u\in[1-\varepsilon(r),1+\varepsilon(r)] u ∈ [ 1 − ε ( r ) , 1 + ε ( r )] .
(4) For r → ∞ r\to\infty r → ∞ we have b ( r , 1 ) → ∞ b(r,1)\to\infty b ( r , 1 ) → ∞ .
(5) b ( r , u ) ∼ b ( r , 1 ) b(r,u)\sim b(r,1) b ( r , u ) ∼ b ( r , 1 ) for r → ∞ r\to\infty r → ∞ , uniformly for u ∈ [ 1 − ε ( r ) , 1 + ε ( r ) ] u\in[1-\varepsilon(r),1+\varepsilon(r)] u ∈ [ 1 − ε ( r ) , 1 + ε ( r )] .
(6) a ( r , u ) = a ( r , 1 ) + c ( r , 1 ) ( u − 1 ) + O ( c ( r , 1 ) ( u − 1 ) 2 ) a(r,u)=a(r,1)+c(r,1)(u-1)+O(c(r,1)(u-1)^2) a ( r , u ) = a ( r , 1 ) + c ( r , 1 ) ( u − 1 ) + O ( c ( r , 1 ) ( u − 1 ) 2 ) for r > 0 r>0 r > 0 and u ∈ [ 1 − ε ( r ) , 1 + ε ( r ) ] u\in[1-\varepsilon(r),1+\varepsilon(r)] u ∈ [ 1 − ε ( r ) , 1 + ε ( r )] .
(7) a ˉ ( r , u ) = O ( a ˉ ( r , 1 ) ) \bar{a}(r,u)=O(\bar{a}(r,1)) a ˉ ( r , u ) = O ( a ˉ ( r , 1 )) and b ˉ ( r , u ) = O ( b ˉ ( r , 1 ) ) \bar{b}(r,u)=O(\bar{b}(r,1)) b ˉ ( r , u ) = O ( b ˉ ( r , 1 )) for all u u u in an arbitrary but fixed complex neighbourhood of 1 1 1 and all r > 0 r>0 r > 0 .
(8) ( det B ( r , 1 ) ) / b ( r , 1 ) → ∞ (\det B(r,1))/b(r,1)\to\infty ( det B ( r , 1 )) / b ( r , 1 ) → ∞ as r → ∞ r\to\infty r → ∞ .
(9) ε ( r ) 3 b ˉ ( r , 1 ) → 0 \varepsilon(r)^3\bar{b}(r,1)\to0 ε ( r ) 3 b ˉ ( r , 1 ) → 0 for r → ∞ r\to\infty r → ∞ .
(10) b ˉ ( r , 1 ) = O ( a ˉ ( r , 1 ) 2 ) \bar{b}(r,1)=O(\bar{a}(r,1)^2) b ˉ ( r , 1 ) = O ( a ˉ ( r , 1 ) 2 ) and a ˉ ( r , 1 ) = O ( f ( r , 1 ) η ) \bar{a}(r,1)=O(f(r,1)^\eta) a ˉ ( r , 1 ) = O ( f ( r , 1 ) η ) for every η > 0 \eta>0 η > 0 , as r → ∞ r\to\infty r → ∞ .
As shown in [18 ] , a sequence of random variables that is defined via the coefficients of an e-admissible function in the way as in Theorem 4 below is asymptotically normally distributed. Like in the UIG-model, the asymptotic expectation and variance can be expressed by means of the Hayman data of the function.
Now we are in the position to state and prove the central limit theorem for the number of vertices in a random history of given length in the directed model. We will prove it by showing that B ⃗ ( t , u ) \vec{B}(t,u) B ( t , u ) is e-admissible.
Theorem 4 (Number of vertices in the directed model). Let M n M_n M n be the number of vertices in a uniformly random history generated in n n n steps, i.e.,
P ( M n = m ) = c n , m c n ( m ≥ 0 ) . \mathbb{P}(M_n=m)=\frac{c_{n,m}}{c_n}\qquad(m\ge0). P ( M n = m ) = c n c n , m ( m ≥ 0 ) . Let w n = W ( 2 n ) w_n=W(2n) w n = W ( 2 n ) . Then
E [ M n ] ∼ n w n , V ( M n ) ∼ n 2 w n ( w n + 1 ) . \mathbb{E}[M_n]\sim\frac{n}{w_n},\qquad\mathbb{V}(M_n)\sim\frac{n}{2w_n(w_n+1)}. E [ M n ] ∼ w n n , V ( M n ) ∼ 2 w n ( w n + 1 ) n . Moreover,
M n − E [ M n ] V ( M n ) → n → ∞ d N ( 0 , 1 ) . \frac{M_n-\mathbb{E}[M_n]}{\sqrt{\mathbb{V}(M_n)}}\xrightarrow[n\to\infty]{d}N(0,1). V ( M n ) M n − E [ M n ] d n → ∞ N ( 0 , 1 ) .
Proof. We verify the e-admissibility conditions required by [18 Theorem 2] for B ⃗ ( t , u ) \vec{B}(t,u) B ( t , u ) and then apply this theorem to establish the distributional asymptotics. As noted by the authors, for [18 Theorem 2] it suffices to check conditions (1)–(6), (8), and (9) of Definition 2.
By (25), the probability generating function of M n M_n M n is
P n ( u ) = [ t n ] B ⃗ ( t , u ) [ t n ] B ⃗ ( t , 1 ) . P_n(u)=\frac{[t^n]\vec{B}(t,u)}{[t^n]\vec{B}(t,1)}. P n ( u ) = [ t n ] B ( t , 1 ) [ t n ] B ( t , u ) .
Thus the distribution of M n M_n M n can be studied directly through the coefficients of B ⃗ ( t , u ) \vec{B}(t,u) B ( t , u ) . In view of Definition 2, we extend the Hayman quantities a ( r ) a(r) a ( r ) and b ( r ) b(r) b ( r ) introduced in (28) by defining
a ( r , u ) : = r ∂ r log B ⃗ ( r , u ) , b ( r , u ) : = r ∂ r a ( r , u ) . a(r,u):=r\partial_r\log\vec{B}(r,u),\qquad b(r,u):=r\partial_r a(r,u). a ( r , u ) := r ∂ r log B ( r , u ) , b ( r , u ) := r ∂ r a ( r , u ) .
and additionally set
a ˉ ( r , u ) : = u ∂ u log B ⃗ ( r , u ) , b ˉ ( r , u ) : = u ∂ u a ˉ ( r , u ) , c ( r , u ) : = u ∂ u a ( r , u ) . \bar{a}(r,u):=u\partial_u\log\vec{B}(r,u),\qquad\bar{b}(r,u):=u\partial_u\bar{a}(r,u),\qquad c(r,u):=u\partial_u a(r,u). a ˉ ( r , u ) := u ∂ u log B ( r , u ) , b ˉ ( r , u ) := u ∂ u a ˉ ( r , u ) , c ( r , u ) := u ∂ u a ( r , u ) .
Using (26) and the chain rule, we obtain, with q = u g ( r ) q=ug(r) q = ug ( r ) ,
a ( r , u ) = a g ( r ) a E ( q ) , b ( r , u ) = b g ( r ) a E ( q ) + a g ( r ) 2 b E ( q ) , a ˉ ( r , u ) = a E ( q ) , b ˉ ( r , u ) = b E ( q ) , c ( r , u ) = a g ( r ) b E ( q ) . \begin{aligned}
a(r,u)&=a_g(r)a_E(q),\qquad b(r,u)=b_g(r)a_E(q)+a_g(r)^2b_E(q),\\
\bar{a}(r,u)&=a_E(q),\qquad\bar{b}(r,u)=b_E(q),\qquad c(r,u)=a_g(r)b_E(q).
\end{aligned} a ( r , u ) a ˉ ( r , u ) = a g ( r ) a E ( q ) , b ( r , u ) = b g ( r ) a E ( q ) + a g ( r ) 2 b E ( q ) , = a E ( q ) , b ˉ ( r , u ) = b E ( q ) , c ( r , u ) = a g ( r ) b E ( q ) .
The variance quantity appearing in Definition 2 is
V ( r ) : = det B ( r , 1 ) b ( r , 1 ) = b ˉ ( r , 1 ) − c ( r , 1 ) 2 b ( r , 1 ) . V(r):=\frac{\det B(r,1)}{b(r,1)}=\bar{b}(r,1)-\frac{c(r,1)^2}{b(r,1)}. V ( r ) := b ( r , 1 ) det B ( r , 1 ) = b ˉ ( r , 1 ) − b ( r , 1 ) c ( r , 1 ) 2 .
Substituting the preceding identities gives
V ( r ) = b g ( r ) a E ( g ( r ) ) b E ( g ( r ) ) b g ( r ) a E ( g ( r ) ) + a g ( r ) 2 b E ( g ( r ) ) . V(r)=\frac{b_g(r)a_E(g(r))b_E(g(r))}{b_g(r)a_E(g(r))+a_g(r)^2b_E(g(r))}. V ( r ) = b g ( r ) a E ( g ( r )) + a g ( r ) 2 b E ( g ( r )) b g ( r ) a E ( g ( r )) b E ( g ( r )) .
Put y = r / 2 y=\sqrt{r/2} y = r /2 . Using the asymptotics established in the proof of Theorem 3, the preceding identity gives
V ( r ) ∼ e y 4 ( y + 1 ) ⟶ ∞ , V(r)\sim\frac{e^y}{4(y+1)}\longrightarrow\infty, V ( r ) ∼ 4 ( y + 1 ) e y ⟶ ∞ ,
which establishes condition (8).
Condition (1) follows from (26): B ⃗ ( t , u ) \vec{B}(t,u) B ( t , u ) is entire in both variables, its coefficients are nonnegative, and B ⃗ ( r , 1 ) > 0 \vec{B}(r,1)>0 B ( r , 1 ) > 0 for r > 0 r>0 r > 0 .
Fix K > 0 K>0 K > 0 and set
ε ( r ) : = K V ( r ) − 1 / 2 . \varepsilon(r):=KV(r)^{-1/2}. ε ( r ) := K V ( r ) − 1/2 .
Hence,
ε ( r ) = O ( y e − y / 2 ) ⟶ 0. \varepsilon(r)=O\left(\sqrt{y}e^{-y/2}\right)\longrightarrow0. ε ( r ) = O ( y e − y /2 ) ⟶ 0.
Thus, for sufficiently large r r r , the interval [ 1 − ε ( r ) , 1 + ε ( r ) ] [1-\varepsilon(r),1+\varepsilon(r)] [ 1 − ε ( r ) , 1 + ε ( r )] is contained in U : = [ 1 / 2 , 3 / 2 ] U:=[1/2,3/2] U := [ 1/2 , 3/2 ] .
Condition (4) was already established in the proof of Theorem 3, since b ( r , 1 ) = b ( r ) b(r,1)=b(r) b ( r , 1 ) = b ( r ) . For condition (5), the asymptotics in Lemma 2 give, uniformly for u ∈ U u\in U u ∈ U ,
b ( r , u ) ∼ u 4 y ( y + 1 ) e y . b(r,u)\sim\frac{\sqrt{u}}{4}y(y+1)e^y. b ( r , u ) ∼ 4 u y ( y + 1 ) e y .
Hence
b ( r , u ) b ( r , 1 ) = u ( 1 + o ( 1 ) ) \frac{b(r,u)}{b(r,1)}=\sqrt{u}(1+o(1)) b ( r , 1 ) b ( r , u ) = u ( 1 + o ( 1 ))
uniformly for u ∈ U u \in U u ∈ U . Since ε ( r ) → 0 \varepsilon(r) \to0 ε ( r ) → 0 , we have u = 1 + o ( 1 ) \sqrt{u} = 1 + o(1) u = 1 + o ( 1 ) uniformly for ∣ u − 1 ∣ ≤ ε ( r ) |u - 1| \le\varepsilon(r) ∣ u − 1∣ ≤ ε ( r ) . Therefore
b ( r , u ) ∼ b ( r , 1 ) b(r,u) \sim b(r,1) b ( r , u ) ∼ b ( r , 1 )
uniformly on this interval, which proves condition (5).
Furthermore, the explicit expression for a ( r , u ) a(r,u) a ( r , u ) gives
sup u ∈ U ∣ ∂ u u a ( r , u ) ∣ = O ( y e y ) , c ( r , 1 ) ≍ y e y . \sup_{u \in U} |\partial_{uu}a(r,u)| = O\left(ye^y\right), \qquad c(r,1) \asymp ye^y. u ∈ U sup ∣ ∂ uu a ( r , u ) ∣ = O ( y e y ) , c ( r , 1 ) ≍ y e y .
Taylor’s theorem therefore yields
a ( r , u ) = a ( r , 1 ) + c ( r , 1 ) ( u − 1 ) + O ( c ( r , 1 ) ( u − 1 ) 2 ) , a(r,u) = a(r,1) + c(r,1)(u-1) + O\left(c(r,1)(u-1)^2\right), a ( r , u ) = a ( r , 1 ) + c ( r , 1 ) ( u − 1 ) + O ( c ( r , 1 ) ( u − 1 ) 2 ) ,
uniformly for ∣ u − 1 ∣ ≤ ε ( r ) |u - 1| \le\varepsilon(r) ∣ u − 1∣ ≤ ε ( r ) , proving condition (6).
Finally, since b ˉ ( r , 1 ) ≍ e y \bar{b}(r,1) \asymp e^y b ˉ ( r , 1 ) ≍ e y ,
ε ( r ) 3 b ˉ ( r , 1 ) = O ( y 3 / 2 e − y / 2 ) = o ( 1 ) , \varepsilon(r)^3\bar{b}(r,1) = O\left(y^{3/2}e^{-y/2}\right) = o(1), ε ( r ) 3 b ˉ ( r , 1 ) = O ( y 3/2 e − y /2 ) = o ( 1 ) ,
which establishes condition (9).
It remains to verify the parameter-uniform versions of the local Gaussian approximation and the tail bound established in Theorem 3.
For condition (2), we use the same cutoff
δ ( r ) = b ( r , 1 ) − 2 / 5 \delta(r) = b(r,1)^{-2/5} δ ( r ) = b ( r , 1 ) − 2/5
as in Theorem 3. The only additional point is uniformity in u u u . Writing
H θ = 2 u sinh ( y e i θ / 2 ) , H_\theta= 2\sqrt{u}\sinh\left(ye^{i\theta/2}\right), H θ = 2 u sinh ( y e i θ /2 ) ,
we have, uniformly for u ∈ U u \in U u ∈ U and ∣ θ ∣ ≤ δ ( r ) |\theta| \le\delta(r) ∣ θ ∣ ≤ δ ( r ) ,
ℜ H θ ≍ e y , ∂ θ 3 log B ⃗ ( r e i θ , u ) = O ( y 3 e y ) . \Re H_\theta\asymp e^y, \qquad\partial_\theta^3 \log\vec{B}(re^{i\theta},u) = O\left(y^3e^y\right). ℜ H θ ≍ e y , ∂ θ 3 log B ( r e i θ , u ) = O ( y 3 e y ) .
Since
δ ( r ) 3 y 3 e y = O ( y 3 / 5 e − y / 5 ) = o ( 1 ) , \delta(r)^3y^3e^y = O\left(y^{3/5}e^{-y/5}\right) = o(1), δ ( r ) 3 y 3 e y = O ( y 3/5 e − y /5 ) = o ( 1 ) ,
the Taylor argument from Theorem 3 applies uniformly in u u u , proving condition (2).
For the tail bound, condition (3), the argument leading to (30) in the proof of Theorem 3 is uniform for u ∈ U u \in U u ∈ U : indeed, the only difference is a factor u \sqrt{u} u in (29), which is bounded from above and away from zero in U U U . Thus the computations leading to (30) and (31) apply almost verbatim and yield the desired tail bound. We have therefore verified all conditions required by Theorem 2 of [18 ] . This implies so far that M n M_n M n converges to a normal limiting distribution.
What remains to do is to determine asymptotic values for expectation and variance. Let ρ n \rho_n ρ n and y n = ρ n / 2 y_n = \sqrt{\rho_n/2} y n = ρ n /2 be as in the proof of Theorem 3. There we showed that
y n = w n + O ( e − 2 w n ) . y_n = w_n + O\left(e^{-2w_n}\right). y n = w n + O ( e − 2 w n ) .
Using the saddle-point equation, we obtain
a ˉ ( ρ n , 1 ) = sinh y n tanh ( 2 sinh y n ) = n tanh y n y n ∼ n w n . \bar{a}(\rho_n,1) = \sinh y_n \tanh(2\sinh y_n) = \frac{n\tanh y_n}{y_n} \sim\frac{n}{w_n}. a ˉ ( ρ n , 1 ) = sinh y n tanh ( 2 sinh y n ) = y n n tanh y n ∼ w n n .
Moreover,
V ( ρ n ) ∼ n 2 y n ( y n + 1 ) ∼ n 2 w n ( w n + 1 ) . V(\rho_n) \sim\frac{n}{2y_n(y_n+1)} \sim\frac{n}{2w_n(w_n+1)}. V ( ρ n ) ∼ 2 y n ( y n + 1 ) n ∼ 2 w n ( w n + 1 ) n .
By Theorem 2 of [18 ] ,
E [ M n ] = a ˉ ( ρ n , 1 ) + o ( V ( ρ n ) ) , V ( M n ) ∼ V ( ρ n ) . \mathbb{E}[M_n]=\bar{a}(\rho_n,1)+o(V(\rho_n)),\qquad V(M_n)\sim V(\rho_n). E [ M n ] = a ˉ ( ρ n , 1 ) + o ( V ( ρ n )) , V ( M n ) ∼ V ( ρ n ) .
Hence, we finally obtain
E [ M n ] ∼ n w n , V ( M n ) ∼ n 2 w n ( w n + 1 ) . \mathbb{E}[M_n]\sim\frac{n}{w_n},\qquad\mathbb{V}(M_n)\sim\frac{n}{2w_n(w_n+1)}. E [ M n ] ∼ w n n , V ( M n ) ∼ 2 w n ( w n + 1 ) n .
and
M n − E [ M n ] V ( M n ) → d n → ∞ N ( 0 , 1 ) . \frac{M_n-\mathbb{E}[M_n]}{\sqrt{\mathbb{V}(M_n)}}\xrightarrow[d]{n\to\infty}\mathcal{N}(0,1). V ( M n ) M n − E [ M n ] n → ∞ d N ( 0 , 1 ) .
as claimed in the assertion.
Remark 10. In order to show asymptotic normality we relied on [18 Theorem 2] , for which only eight of the ten properties defining e-admissibility are needed. The other two are only important to prove the closure properties of the class of e-admissible functions. Therefore we confined ourselves with proving only those eight properties for our function. But it can be shown that B ⃗ ( t , u ) \vec{B}(t,u) B ( t , u ) satisfies the remaining two conditions as well and is therefore indeed e-admissible.
A correspondence between the DIG-model and set partitions
As already mentioned in this paper, the function B ⃗ ( t , u ) \vec{B}(t,u) B ( t , u ) has a striking similarity to the generating function of set partitions. We simply have to replace the standard exponential function e t e^t e t by E ( t ) E(t) E ( t ) . Thus, the coefficients of T ⃗ ( t , u ) \vec{T}(t,u) T ( t , u ) are closely related to partitions into blocks of even size.
Proposition 4. For n ≥ 1 n\geq1 n ≥ 1 , 1 ≤ k ≤ n 1\leq k\leq n 1 ≤ k ≤ n let p n , k p_{n,k} p n , k denote the number of partitions of the 2 n 2n 2 n -element set { 1 , 1 ′ , 2 , 2 ′ , … , n , n ′ } \{1,1',2,2',\ldots,n,n'\} { 1 , 1 ′ , 2 , 2 ′ , … , n , n ′ } into k k k blocks, each of even cardinality.
[ t n u k ] T ⃗ ( t , u ) = p n , k ( 2 k − 1 ) ! ! (36) [t^n u^k]\vec{T}(t,u)=\frac{p_{n,k}}{(2k-1)!!} \tag*{(36)} [ t n u k ] T ( t , u ) = ( 2 k − 1 )!! p n , k (36) where ( 2 k − 1 ) ! ! = ( 2 k − 1 ) ( 2 k − 3 ) ⋯ 3 ⋅ 1 (2k-1)!!=(2k-1)(2k-3)\cdots3\cdot1 ( 2 k − 1 )!! = ( 2 k − 1 ) ( 2 k − 3 ) ⋯ 3 ⋅ 1 .
Remark 11. This relation is recorded in OEIS A156289. For the sake of being self-contained, we present a proof here.
Proof. The exponential generating function of the numbers p n , k p_{n,k} p n , k is
∑ n ≥ 0 p n , k z 2 n ( 2 n ) ! = ( cosh z − 1 ) k k ! . \sum_{n\geq0}p_{n,k}\frac{z^{2n}}{(2n)!}=\frac{(\cosh z-1)^k}{k!}. n ≥ 0 ∑ p n , k ( 2 n )! z 2 n = k ! ( cosh z − 1 ) k .
Recall that g ( t ) = E ( t ) − 1 = cosh ( 2 t ) − 1 g(t)=E(t)-1=\cosh(\sqrt{2t})-1 g ( t ) = E ( t ) − 1 = cosh ( 2 t ) − 1 . If we set z = 2 t z=\sqrt{2t} z = 2 t , this becomes
∑ n ≥ 0 p n , k ( 2 t ) n ( 2 n ) ! = g ( t ) k k ! . \sum_{n\geq0}p_{n,k}\frac{(2t)^n}{(2n)!}=\frac{g(t)^k}{k!}. n ≥ 0 ∑ p n , k ( 2 n )! ( 2 t ) n = k ! g ( t ) k .
with the conventions
p 0 , 0 = 1 , p n , 0 = 0 ( n ≥ 1 ) . p_{0,0}=1,\qquad p_{n,0}=0\quad(n\geq1). p 0 , 0 = 1 , p n , 0 = 0 ( n ≥ 1 ) .
On the other hand, the closed form (26) for the rescaled Borel transform gives
[ u k ] B ⃗ ( t , u ) = 2 k ( 2 k ) ! g ( t ) k = 1 ( 2 k − 1 ) ! ! g ( t ) k k ! . [u^k]\vec{B}(t,u)=\frac{2^k}{(2k)!}g(t)^k=\frac{1}{(2k-1)!!}\frac{g(t)^k}{k!}. [ u k ] B ( t , u ) = ( 2 k )! 2 k g ( t ) k = ( 2 k − 1 )!! 1 k ! g ( t ) k .
Comparing coefficients with the definition of the rescaled Borel transform yields (35). □
The numbers p n , k p_{n,k} p n , k satisfy the recurrence relation [13 ]
p n , k = ( 2 k − 1 ) p n − 1 , k − 1 + k 2 p n − 1 , k . (37) p_{n,k}=(2k-1)p_{n-1,k-1}+k^2p_{n-1,k}. \tag*{(37)} p n , k = ( 2 k − 1 ) p n − 1 , k − 1 + k 2 p n − 1 , k . (37)
This also follows directly from the generating function. Indeed, if
P k ( z ) : = ( cosh z − 1 ) k k ! , P_k(z):=\frac{(\cosh z-1)^k}{k!}, P k ( z ) := k ! ( cosh z − 1 ) k ,
then
P k ′ ′ ( z ) = ( 2 k − 1 ) P k − 1 ( z ) + k 2 P k ( z ) , P_k''(z)=(2k-1)P_{k-1}(z)+k^2P_k(z), P k ′′ ( z ) = ( 2 k − 1 ) P k − 1 ( z ) + k 2 P k ( z ) ,
and extracting the coefficients gives (37) .
This recurrence admits a combinatorial interpretation based on the insertion of the new pair { n , n ′ } \{n,n'\} { n , n ′ } into a partition of a ( 2 n − 2 ) (2n-2) ( 2 n − 2 ) -element set. Throughout, we assume that the ground set is totally ordered by
1 ≺ 1 ′ ≺ 2 ≺ 2 ′ ≺ ⋯ ≺ n ≺ n ′ . 1\prec1'\prec2\prec2'\prec\cdots\prec n\prec n'. 1 ≺ 1 ′ ≺ 2 ≺ 2 ′ ≺ ⋯ ≺ n ≺ n ′ .
and that the blocks of a partition receive a time stamp when they are created.
Let π \pi π be a partition of { 1 , 1 ′ , … , n − 1 , ( n − 1 ) ′ } \{1,1',\ldots,n-1,(n-1)'\} { 1 , 1 ′ , … , n − 1 , ( n − 1 ) ′ } into even-sized blocks. The new pair is inserted by one of the following operations:
(N0) { n , n ′ } \{n,n'\} { n , n ′ } forms a new block.
(N1) Choose an existing block B B B from π \pi π and ε ∈ { n , n ′ } \varepsilon\in\{n,n'\} ε ∈ { n , n ′ } , put ε \varepsilon ε into B B B and the other element η \eta η of { n , n ′ } \{n,n'\} { n , n ′ } into a new block. Then move x : = max ≺ B x:=\max_{\prec}B x := max ≺ B (the maximum of the old elements of B B B ) to the new block. The result is the replacement of B B B by the two blocks { η , x } \{\eta,x\} { η , x } and ( B ∖ { x } ) ∪ { ε } (B\setminus\{x\})\cup\{\varepsilon\} ( B ∖ { x }) ∪ { ε } in π \pi π .
(L) Choose an existing block B B B and put both new elements n n n and n ′ n' n ′ into B B B .
(E) Choose an ordered pair ( B , B ′ ) (B,B') ( B , B ′ ) of distinct existing blocks and put n n n into B B B and n ′ n' n ′ into B ′ B' B ′ . Then move x : = max ≺ ( B ∪ B ′ ) x:=\max_{\prec}(B\cup B') x := max ≺ ( B ∪ B ′ ) (taken over the old elements) from the block containing it to the other one.
If π \pi π has k − 1 k-1 k − 1 blocks, then there are 1 + 2 ( k − 1 ) = 2 k − 1 1+2(k-1)=2k-1 1 + 2 ( k − 1 ) = 2 k − 1 possibilities to apply either of the operations (N0) and (N1), each resulting in a partition with k k k blocks. If π \pi π has k k k blocks, then there are k + k ( k − 1 ) = k 2 k+k(k-1)=k^2 k + k ( k − 1 ) = k 2 possibilities to apply either (L) or (E). All operations produce partitions into even-sized blocks.
After normalization by ( 2 k − 1 ) ! ! (2k-1)!! ( 2 k − 1 )!! , recurrence (37) becomes
p n , k ( 2 k − 1 ) ! ! = p n − 1 , k − 1 ( 2 k − 3 ) ! ! + k 2 p n − 1 , k ( 2 k − 1 ) ! ! . \frac{p_{n,k}}{(2k-1)!!}=\frac{p_{n-1,k-1}}{(2k-3)!!}+k^2\frac{p_{n-1,k}}{(2k-1)!!}. ( 2 k − 1 )!! p n , k = ( 2 k − 3 )!! p n − 1 , k − 1 + k 2 ( 2 k − 1 )!! p n − 1 , k .
Using (36) , this is precisely
[ t n u k ] T ⃗ ( t , u ) = [ t n − 1 u k − 1 ] T ⃗ ( t , u ) + k 2 [ t n − 1 u k ] T ⃗ ( t , u ) , [t^n u^k]\vec{T}(t,u)=[t^{n-1}u^{k-1}]\vec{T}(t,u)+k^2[t^{n-1}u^k]\vec{T}(t,u), [ t n u k ] T ( t , u ) = [ t n − 1 u k − 1 ] T ( t , u ) + k 2 [ t n − 1 u k ] T ( t , u ) ,
which exactly matches the recurrence for the DIG-model on the coefficient level. Thus, the factor ( 2 k − 1 ) ! ! (2k-1)!! ( 2 k − 1 )!! is the normalization that transforms the recurrence for even-block partitions into the recurrence for directed histories. In both cases, the two terms correspond, respectively, to the creation of a new vertex and to the k 2 k^2 k 2 possible directed edge or loop choices.
The operations of the insertion description above are reversible. From the resulting partition, one can uniquely recover the preceding partition and the operation that was applied. Iterating the construction therefore yields a correspondence with histories in the DIG-model, after all. At the j j j -th vertex-creation step, there are exactly 2 j − 1 2j-1 2 j − 1 possible partition insertions corresponding to the same vertex-creation step, whereas an edge or loop step determines its insertion uniquely.
Consequently, every history in the DIG-model with k k k vertices has exactly
∏ j = 1 k ( 2 j − 1 ) = ( 2 k − 1 ) ! ! \prod_{j=1}^{k}(2j-1)=(2k-1)!! j = 1 ∏ k ( 2 j − 1 ) = ( 2 k − 1 )!!
preimages among the even-sized set partitions.
Uniform sampling of graphs from the DIG-model
In order to sample histories in the DIG-model such that all histories generated in n n n steps are equally likely, we use the framework of Boltzmann samplers [19 ] . However, as the generating function T ⃗ ( z , 1 ) \vec{T}(z,1) T ( z , 1 ) is only a formal power series, this does not work directly. Likewise, the Borel transform B ⃗ ( t , 1 ) \vec{B}(t,1) B ( t , 1 ) cannot be used directly in the classical way of the symbolic method, as its building block E ( t ) E(t) E ( t ) does not correspond to any combinatorial construction presented in [24 ] .
A naive way of sampling histories in the DIG-model would be by uniformly generating set partitions into blocks of even size and then applying the above correspondence to obtain a graph. However, this procedure does not produce a uniform distribution over fixed length histories of the DIG-model. The reason is that every graph with k k k vertices originates from ( 2 k − 1 ) ! ! (2k-1)!! ( 2 k − 1 )!! partitions and k k k is not constant over all histories generating in n n n steps. To correct this bias, we present a biased sampler for set partitions into even-sized blocks with the probability of each partition being biased by a factor 1 / ( 2 k − 1 ) ! ! 1/(2k-1)!! 1/ ( 2 k − 1 )!! . When finally applying the correspondence, all histories generated in n n n steps are equally likely.
We start with two algorithms working with a data structure called History. Algorithm 1 extracts a history of graph-building instructions from a partition while applying the insertion operations (N0), (N1), (L), (E), which we introduced in Section 7, in reverse order and outputs the instructions to History. Algorithm 2 assembles the contents of History into a DIG-model graph. See Figure 1 for the a step-by-step execution of both algorithms on an example.
Figure 1. Step-by-step execution of Algorithms 1 and 2 on the partition in even subsets { { 1 , 2 ′ } , { 1 ′ , 2 , 4 , 5 } , { 3 , 3 ′ , 4 ′ , 5 ′ } } \{\{1, 2^{\prime}\}, \{1^{\prime}, 2, 4, 5\}, \{3, 3^{\prime}, 4^{\prime}, 5^{\prime}\}\} {{ 1 , 2 ′ } , { 1 ′ , 2 , 4 , 5 } , { 3 , 3 ′ , 4 ′ , 5 ′ }} , with the order 1 ≺ 1 ′ ≺ 2 ≺ 2 ′ ≺ ⋯ 1 \prec1^{\prime} \prec2 \prec2^{\prime} \prec\cdots 1 ≺ 1 ′ ≺ 2 ≺ 2 ′ ≺ ⋯ . The blocks are eliminated in the order B 3 , B 2 , B 1 B_{3}, B_{2}, B_{1} B 3 , B 2 , B 1 , so that B i B_{i} B i corresponds to vertex v i v_{i} v i .
This two-phased procedure exposes the origin of the many-to-one mapping. During deconstruction, every time a block is eliminated (a node-defining step), the information whether the step was the reverse of (N0) or of (N1) is discarded. Similarly, we discard information on the specific block and chosen element in the cases where we revert (L) or (E). As a graph with k k k nodes requires exactly k k k such node-defining steps, offering 1, 3, … \ldots … , 2 k − 1 2k-1 2 k − 1 choices for the first, second, … \ldots … , k k k -th step, respectively, there are exactly ( 2 k − 1 ) ! ! (2k-1)!! ( 2 k − 1 )!! distinct pairings that are forgotten during parsing. Conversely, the locations of the pairs during the k 2 k^2 k 2 edge and loop steps are preserved within the history, allowing the graph to be deterministically reconstructed. Therefore, any single reconstructed graph serves as the representative for exactly ( 2 k − 1 ) ! ! (2k-1)!! ( 2 k − 1 )!! distinct even-sized partitions.
Next, we turn to the needed bias. Note that the standard exponential generating function for set partitions into even-sized blocks is exp ( g ( t ) ) \exp(g(t)) exp ( g ( t )) , where the inner function g ( t ) = cosh ( 2 t ) − 1 g(t)=\cosh(\sqrt{2t})-1 g ( t ) = cosh ( 2 t ) − 1 is associated with the combinatorial class of blocks of even size. To inject the biasing factor 1 / ( 2 k − 1 ) ! ! 1/(2k-1)!! 1/ ( 2 k − 1 )!! , we replace the outer exponential series with the function E ( y ) = cosh ( 2 y ) E(y)=\cosh(\sqrt{2y}) E ( y ) = cosh ( 2 y ) , derived from the rescaled Borel transform.
The series expansion of E ( g ( t ) ) E(g(t)) E ( g ( t )) assigns the weight g ( t ) k / ( ( 2 k − 1 ) ! ! k ! ) g(t)^k/((2k-1)!!k!) g ( t ) k / (( 2 k − 1 )!! k !) to configurations containing k k k blocks. Based on this algebraic structure, we design a two-stage sampling procedure for any positive real parameter t t t , which can be chosen freely. In practice, it is set to tune the expected number n n n of steps used to generate the graph. First, we draw the integer
Algorithm 1 DeconstructPartition($\mathcal{P}$)
Require: A partition $\mathcal{P}$ of $\{1,1',\ldots,n,n'\}$ into $k$ blocks of even size; the elements are ordered by $1 \prec 1' \prec 2 \prec \cdots \prec n \prec n'$.
1: Initialize History as an empty stack and $L$ as an empty list.
2: {Blocks keep their time stamp when elements are removed or transferred.}
3: for $m=n$ down to 1 do
4: Let $C$ and $C'$ be the blocks containing $m$ and $m'$, respectively.
5: Remove $m$ and $m'$ from $\mathcal{P}$.
6: if $C=C'$ then
7: if $C$ is empty then
8: Instruction $\leftarrow$ NODE($C$); delete $C$ and append $C$ to $L$. {Case (N0)}
9: else
10: Instruction $\leftarrow$ LOOP($C$). {Case (L)}
11: end if
12: else
13: $x \leftarrow \max_{\prec}(C \cup C')$; let $D \in \{C,C'\}$ be the block containing $x$ and $\overline{D}$ the other one.
14: Transfer $x$ from $D$ to $\overline{D}$. {parity-restoring operation}
15: if $D$ is empty then
16: Instruction $\leftarrow$ NODE($D$); delete $D$ and append $D$ to $L$. {Case (N1)}
17: else
18: Instruction $\leftarrow$ EDGE($C \to C'$). {Case (E)}
19: end if
20: end if
21: Push Instruction to History.
22: end for
23: The $i$-th block of $L$ receives the vertex label $k+1-i$; replace every block occurring in History by its label.
24: return History
Algorithm 2 BuildGraph(History)
Require: The parsed History stack from DeconstructPartition.
1: Initialize directed graph $G$ with 0 vertices.
2: Initialize step counter $m \leftarrow 1$.
3: while History is not empty do
4: Pop Instruction.
5: if Instruction is NODE($i$) then
6: Create a new vertex $v_i$ in $G$ with time stamp $m$. {Cases (N0) and (N1)}
7: else if Instruction is LOOP($i$) then
8: Add a directed loop with time stamp $m$ at vertex $v_i$. {Case (L)}
9: else if Instruction is EDGE($i \to j$) then
10: Add a directed edge with time stamp $m$ from $v_i$ to $v_j$. {Case (E)}
11: end if
12: $m \leftarrow m+1$.
13: end while
14: return $G$
k k k from the discrete probability distribution proportional to the Taylor coefficients of E ( y ) E(y) E ( y ) evaluated at y = g ( t ) y = g(t) y = g ( t ) . Second, we determine the specific sizes of these k k k blocks. This is achieved by drawing k k k independent random variables from the distribution proportional to the coefficients of g ( t ) g(t) g ( t ) . By constructing a partition from these specific biased distributions and applying Algorithms 1 and 2 afterwards, the resulting distribution over histories of the DIG-model generated in a given number of steps becomes uniform.
Algorithm 3 Uniform Sampler for DIG-Model Graphs
Require: A parameter t > 0 t > 0 t > 0 .
{Phase 1: Biased sampling of the number of blocks K K K }
Draw K K K from a discrete distribution proportional to the coefficients of E ( y ) = cosh ( 2 y ) E(y) = \cosh(\sqrt{2}y) E ( y ) = cosh ( 2 y ) evaluated at g ( t ) g(t) g ( t ) :
P t ( K = k ) = 2 k ( 2 k ) ! g ( t ) k B ‾ ( t , 1 ) , for k ≥ 0. \mathbb{P}_{t}(K = k) = \frac{2^k}{(2k)!}\frac{g(t)^k}{\overline{B}(t,1)}, \qquad\text{for } k \ge0. P t ( K = k ) = ( 2 k )! 2 k B ( t , 1 ) g ( t ) k , for k ≥ 0.
{Phase 2: Sampling the sizes of the K K K even blocks}
for i = 1 i = 1 i = 1 to K K K do
Draw the size S i S_i S i of block i i i from a distribution proportional to the coefficients of g ( t ) = cosh ( 2 t ) − 1 g(t) = \cosh(\sqrt{2t}) - 1 g ( t ) = cosh ( 2 t ) − 1 :
P t ( S i = s i ) = 2 s i / 2 t s i / 2 s i ! g ( t ) , for even s i ≥ 2. \mathbb{P}_{t}(S_i = s_i) = \frac{2^{s_i/2}t^{s_i/2}}{s_i!g(t)}, \qquad\text{for even } s_i \ge2. P t ( S i = s i ) = s i ! g ( t ) 2 s i /2 t s i /2 , for even s i ≥ 2.
end for
2 n ← ∑ i = 1 K S i 2n \gets\sum_{i=1}^{K} S_i 2 n ← ∑ i = 1 K S i
{Phase 3: Partition construction and graph projection}
Draw a uniformly random permutation of { 1 , 1 ′ , … , n , n ′ } \{1,1',\ldots,n,n'\} { 1 , 1 ′ , … , n , n ′ } and cut it into consecutive blocks of sizes S 1 , … , S K S_1,\ldots,S_K S 1 , … , S K ; let P \mathcal{P} P be the resulting partition.
G ← BuildGraph ( DeconstructPartition ( P ) ) G \gets\operatorname{BuildGraph}(\operatorname{DeconstructPartition}(\mathcal{P})) G ← BuildGraph ( DeconstructPartition ( P ))
return G G G
Theorem 5. For any t > 0 t > 0 t > 0 , Algorithm 3 generates a random graph from the DIG-model graph. Conditioned on the generated graph having n n n time steps, the resulting probability distribution is uniform.
Proof. Let G G G be a history of the DIG-model that is generated in n n n time steps and has k k k vertices. Let Π ( G ) \Pi(G) Π ( G ) denote the equivalence class of even-sized set partitions that are deterministically mapped to G G G by Algorithms 1 and 2. By the correspondence established in § 7 , its cardinality is ∣ Π ( G ) ∣ = ( 2 k − 1 ) ! ! |\Pi(G)| = (2k - 1)!! ∣Π ( G ) ∣ = ( 2 k − 1 )!! .
Fix a partition P \mathcal{P} P of { 1 , 1 ′ , … , n , n ′ } \{1,1',\ldots,n,n'\} { 1 , 1 ′ , … , n , n ′ } into k k k even blocks of sizes s 1 , … , s k s_1,\ldots,s_k s 1 , … , s k (in some order). The algorithm produces P \mathcal{P} P if and only if K = k K = k K = k , the sequence ( S 1 , … , S k ) (S_1,\ldots,S_k) ( S 1 , … , S k ) is the sequence of the block sizes of P \mathcal{P} P in one of the k ! k! k ! orders of its blocks, and Phase 3 decomposes the 2 n 2n 2 n -element ground set into these blocks in this order. Since Phase 3 constructs the partition by cutting a uniformly random permutation of length 2 n 2n 2 n , generating exactly these specific blocks in this fixed order occurs if and only if the permutation groups the elements of each block together. There are exactly ∏ i s i ! \prod_i s_i! ∏ i s i ! such favorable permutations out of the ( 2 n ) ! (2n)! ( 2 n )! possible
::: ones, so this last event has probability ( ∏ i s i ! ) / ( 2 n ) ! \left(\prod_i s_i!\right)/(2n)! ( ∏ i s i ! ) / ( 2 n )! . Since ∑ i s i / 2 = n \sum_i s_i/2=n ∑ i s i /2 = n , we obtain
P t ( P ) = k ! ⋅ 2 k g ( t ) k ( 2 k ) ! B → ( t , 1 ) ⋅ ( 2 t ) n g ( t ) k ∏ i s i ! ⋅ ∏ i s i ! ( 2 n ) ! = 1 B → ( t , 1 ) ( 2 t ) n ( 2 n ) ! 1 ( 2 k − 1 ) ! ! . \mathbb{P}_t(\mathcal{P})=k!\cdot\frac{2^k g(t)^k}{(2k)!\overrightarrow{B}(t,1)}\cdot\frac{(2t)^n}{g(t)^k\prod_i s_i!}\cdot\frac{\prod_i s_i!}{(2n)!}=\frac{1}{\overrightarrow{B}(t,1)}\frac{(2t)^n}{(2n)!}\frac{1}{(2k-1)!!}. P t ( P ) = k ! ⋅ ( 2 k )! B ( t , 1 ) 2 k g ( t ) k ⋅ g ( t ) k ∏ i s i ! ( 2 t ) n ⋅ ( 2 n )! ∏ i s i ! = B ( t , 1 ) 1 ( 2 n )! ( 2 t ) n ( 2 k − 1 )!! 1 .
because k ! 2 k / ( 2 k ) ! = 1 / ( 2 k − 1 ) ! ! k!2^k/(2k)!=1/(2k-1)!! k ! 2 k / ( 2 k )! = 1/ ( 2 k − 1 )!! .
The overall probability of sampling the final graph G G G is the sum of the probabilities of generating any partition that is mapped to G G G :
P t ( G ) = ∑ P ∈ Π ( G ) P t ( P ) = ( 2 k − 1 ) ! ! ( 1 B → ( t , 1 ) ( 2 t ) n ( 2 n ) ! 1 ( 2 k − 1 ) ! ! ) = 1 B → ( t , 1 ) ( 2 t ) n ( 2 n ) ! . (38) \mathbb{P}_t(G)=\sum_{\mathcal{P}\in\Pi(G)}\mathbb{P}_t(\mathcal{P})=(2k-1)!!\left(\frac{1}{\overrightarrow{B}(t,1)}\frac{(2t)^n}{(2n)!}\frac{1}{(2k-1)!!}\right)=\frac{1}{\overrightarrow{B}(t,1)}\frac{(2t)^n}{(2n)!}. \tag*{(38)} P t ( G ) = P ∈ Π ( G ) ∑ P t ( P ) = ( 2 k − 1 )!! ( B ( t , 1 ) 1 ( 2 n )! ( 2 t ) n ( 2 k − 1 )!! 1 ) = B ( t , 1 ) 1 ( 2 n )! ( 2 t ) n . (38)
This probability P t ( G ) \mathbb{P}_t(G) P t ( G ) depends exclusively on n n n and the parameter t t t . It is entirely independent of the number of nodes k k k . Consequently, conditioning this generation process on the output being generated in n n n time steps guarantees a uniform distribution over all the DIG-model graphs with n n n time steps. □
Remark 12. Summing over all histories of length n n n gives
P t ( N = n ) = c n ( 2 t ) n ( 2 n ) ! B → ( t , 1 ) = t n [ n ] B → ( t , 1 ) B → ( t , 1 ) . \mathbb{P}_t(N=n)=\frac{c_n(2t)^n}{(2n)!\overrightarrow{B}(t,1)}=\frac{t^n[n]\overrightarrow{B}(t,1)}{\overrightarrow{B}(t,1)}. P t ( N = n ) = ( 2 n )! B ( t , 1 ) c n ( 2 t ) n = B ( t , 1 ) t n [ n ] B ( t , 1 ) .
To sample a history of exact length n n n by rejection, it is natural to choose t = ρ n t=\rho_n t = ρ n , the solution of a ( ρ n ) = n a(\rho_n)=n a ( ρ n ) = n from the proof of Theorem 3; then E t [ N ] = a ( t ) = n \mathbb{E}_t[N]=a(t)=n E t [ N ] = a ( t ) = n . By Hayman’s theorem and (35) ,
P ρ n ( N = n ) ∼ 1 2 π b ( ρ n ) ∼ 1 π n ( w n + 1 ) . \mathbb{P}_{\rho_n}(N=n)\sim\frac{1}{\sqrt{2\pi b(\rho_n)}}\sim\frac{1}{\sqrt{\pi n(w_n+1)}}. P ρ n ( N = n ) ∼ 2 π b ( ρ n ) 1 ∼ π n ( w n + 1 ) 1 .
so that the expected number of trials is of order n log n \sqrt{n\log n} n log n .
Conclusion
In this work we have proposed two random graph growth models where the growth is achieved by adding a new vertex or a new edge uniformly at random. With the UIG-model and the DIG-model, two natural models have been chosen for our investigation as prototypes for an undirected and a directed model. The two models are interesting in their own right, as they exhibit the need for a fairly different mathematical treatment. In both models, the number of objects of size n n n (where size is the length of the history) grows so rapidly that the generating functions that we encountered have a radius of convergence equal to zero. In the UIG-model, the expression as a sum together with the discrete Laplace method was the clue. The DIG-model required a rescaled Borel transform to make Hayman’s theory of saddle-point asymptotics and some of its extensions work. In both cases we see asymptotic expressions involving the Lambert W function.
Of course, two other obvious models are undirected graphs with loops allowed and directed graphs without loops. But we expect that one of the two approaches will work in either case. Other models in the framework of independent growth of the number of vertices and the number of edges can be obtained by imposing certain constraints of our model.
The most natural parameter in these models is of course the number of vertices of the graph generated by a history, for which we show a central limit theorem in both models. Other parameters are conceivable and in the extended abstract of this work [4] we treated some of them briefly. It is also worth investigating whether the correspondence between the DIG-model and set partitions can lead to interesting asymptotic results, either for the DIG-model graphs or for partitions. A natural line of future research would be the question whether a modification of the rules to generate a history, for instance looking at hypergraphs instead of graphs, will lead to structures that can be analyzed in a similar way and lead to similar asymptotics. Maybe such structures satisfy a correspondence to set partitions with different divisibility properties for their block sizes.
A brief discussion was done when introducing weights on vertex and edge creation. Unfortunately, the approach seems not to be well-suited for problems of that kind. So, it remains an open problem how to introduce weights in a proper way to allow for tuning the proportion of the number of edges and vertices in a history, such that the resulting graph class is amenable to a complete asymptotic analysis, including the description of possible phase transitions.
As the transformed generating function is nearly bivariate Hayman admissible it is worthwhile to investigate this further, In [4] we customized bivariate Hayman admissibility to our needs and were able to carry over the main theorem to our case. This gives a full bivariate normal limit law for the joint distribution of the number of vertices and the length of the history. A question is whether the slight extension of the concept developed in [25 ] mentioned above or a similar one allows for inclusion of further parameters, yielding multivariate normal limit laws based on multivariate Hayman admissibility.
Finally, we remark that this work serves as another example demonstrating that encountering combinatorial structures with rapidly growing counting sequences — whose generating functions are merely formal power series — is not the end of the story in analytic combinatorics. There are a lot of tools available to rigorously treat divergent series in a proper way to squeeze out precise asymptotic information from them.
References
Institute of Discrete Mathematics and Geometry, TU Wien, Austria Email address: nadja.azzouz@tuwien.ac.at
Institut Galilée, Univ. Paris Nord Email address: olivier.bodini@univ-paris13.fr
Institut Galilée, Univ. Paris Nord Email address: francis.durand@ens-paris-saclay.fr
Institute of Discrete Mathematics and Geometry, TU Wien, Austria Email address: gittenberger@dmg.tuwien.ac.at