{'fraction_non_alphanumeric': 0.05784366406422859, 'fraction_numerical': 0.025666150393526568, 'mean_word_length': 3.99968394437421, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Analysis of an exhaustive search algorithm in random graphs and the n^{c\log n} -asymptotics

We analyze the cost used by a naive exhaustive search algorithm for finding a maximum independent set in random graphs under the usual G_{n,p} -model where each possible edge appears independently with the same probability p. The expected cost turns out to be of the less common asymptotic order n^{c\log n}, which we explore from several different perspectives. Also we collect many instances where such an order appears, from algorithmics to analysis, from probability to algebra. The limiting distribution of the cost required by the algorithm under a purely idealized random model is proved to be normal. The approach we develop is of some generality and is amenable for other graph algorithms.


Introduction
An independent set or stable set of a graph G is a subset of vertices in G no two of which are adjacent. The Maximum Independent Set (MIS) Problem consists in finding an independent set with the largest cardinality; it is among the first known NP-hard problems and has become a fundamental, representative, prototype instance of combinatorial optimization and computational complexity; see Garey and Johnson (1979). A large number of algorithms (exact or approximate, deterministic or randomized), as well as many applications, have been studied in the literature; see Bomze et al. (1999); Fomin and Kratsch (2010); Woeginger (2003) and the references therein for more information.
The fact that there exist several problems that are essentially equivalent (including maximum clique and minimum node cover) adds particularly further dimensions to the algorithmic aspects and structural richness of the problem. Also worthy of special mention is the following interesting polynomial formulation (see Abello et al. (2001); Harant (2000)) where α(G) denotes the cardinality of an MIS of G (or the stability number) and E is the set of edges of G. Such an expression is easily coded, albeit with an exponential complexity. The algorithmic, theoretical and practical connections of many other formulations similar to this one have also been widely discussed; see Abello et al. (2001). One simple means to find an MIS of a graph G is the following exhaustive (or branching or enumerative) algorithm. Start with any node, say v in G. Then either v is in an MIS or it is not. This leads to the recursive decomposition (1.1) where MIS(G) denotes an MIS of G and N * (v) denotes the union of v and all its neighbors. Such a simple procedure leads to many refined algorithms in the literature, including alternative formulations such as backtracking (see Wilf (2002)) or branch and bound (see Fomin and Kratsch (2010)). Tarjan and Trojanowski Tarjan and Trojanowski (1977) proposed an improved exhaustive algorithm with worst-case time complexity O(2 n/3 ). Their paper was followed and refined by many since then; see Bomze et al. (1999); Woeginger (2003) and Fomin and Kratsch (2010) for more information and references. In particular, Chvátal Chvátal (1977) generalized Tarjan and Trojanowski's algorithm and showed inter alia that for almost all graphs with n nodes, a special class of algorithms (which he called order-driven) has time bound O(n c 0 log n+2 ), where c 0 := 2/ log 2. He also characterized exponential algorithms and conjectured that a similar bound of the form O(n c log n ) holds for a wider class of recursive algorithms for some c > 0. Pittel Pittel (1982) then refined Chvátal's bounds by showing that, under the usual G n,p -model (namely, each pair of nodes has the same probability p ∈ (0, 1) of being connected by an edge, and one independent of the others), the cost of Chvátal's algorithms (called f-driven, more general than order-driven) is bounded between n ( 1 4 −ε) log κ n and n ( 1 2 +ε) log κ n with high probability, for any ε > 0, where q := 1 − p and κ := 1/q.
The infrequent scale n c log n = e c(log n) 2 is central to our study here and can be seen through several different angles that will be examined in the following paragraphs. The simplest algorithmic connection to MIS problem is via the following argument. It is well-known that for any random graph G (under the G n,p -model), the value of α(G) is highly concentrated for fixed p ∈ (0, 1), namely, there exists a sequence m n such that α(G) = m n or α(G) = m n + 1 with high probability; see Bollobás (2001). Asymptotically (κ := 1/q), m n = 2 log κ n − 2 log κ log κ n + O(1).
For more information on this and related estimates, see Bollobás (2001) and the references therein. Thus a simple randomized (approximate) MIS-finding algorithm consists in examining all possible n m n + n m n + 1 = O n 2 log κ n subsets and determining if at least one of them is independent; otherwise (which happens with very small probability; see Bollobás (2001)), we resort to exhaustive algorithms such as that discussed in this paper. From a different algorithmic viewpoint, Jerrum Jerrum (1992) studied the following Metropolis algorithm for maximum clique. Sequentially increase the clique, say K by (i) choose a vertex v uniformly at random; (ii) if v ∈ K and v is connected to every vertex of K, then add v to K; (iii) if v ∈ K, then v is subtracted from K with probability Λ −1 . He proved that for all Λ 1, there exists an initial state from which the expected time for the Metropolis process to reach a clique of size at least (1 + ε) log κ (pn) exceeds n Ω(log pn) . See Coja-Oghlan and Efthymiou (2011) for an account of more recent developments on the complexity of the MIS problem.
We aim in this paper at a more precise analysis of the cost used by the simple recursive, exhaustive algorithm implied by (1.1). The exact details of the algorithm matter less and the overall cost is dominated by the total number of recursive calls, denoted by X n , which is a random variable under the same G n,p -model. Then the mean value µ n := E(X n ) satisfies (1.2) for n 2, with the initial conditions µ 0 = 0 and µ 1 = 1, where π n,k := P(v has n − 1 − k neighbors) = n − 1 k p n−1−k q k .
How fast does µ n grow as a function of n? (i) If p is close to 1, then the graph is very dense and thus the sum in (1.2) is small (many nodes being removed), so we expect a polynomial time bound by simple iteration; (ii) If p is sufficiently small, then the second term is large, and we expect an exponential time bound; (iii) What happens for p in between? In this case the asymptotics of µ n turns out to be nontrivial and we will show that log µ n = log n log κ n 2 2 log κ + 1 2 + 1 log κ log n − log log n + P 0 log κ n log κ n + o(1), where P 0 (t) is a bounded, periodic function of period 1. We will give a precise expression for P 0 . Note that µ n n 1 2 log κ n (log n) 1 2 log κ log n−1− log log κ log κ n log κ log n− 1 for any K > 0, where the symbol a n b n means that a n and b n are asymptotically of the same order. Thus µ n = o n 1 2 log κ n−K . On the other hand, the asymptotic pattern (1.3) is to some extent generic, as we will see below.
An intuitive way to see why we have the asymptotic form (1.3) for log µ n is to look at the simpler functional equation (1.5) since the binomial distribution is highly concentrated around its mean value pn, and we expect that µ n ≈ ν(n) (under suitable initial conditions). This functional equation and the like (such as ν n = ν n−1 + ν qn ) has a rich literature. Most of them are connected to special integer partitions; important pointers are provided in Encyclopedia of Integer Sequences; see for example A000123, A002577, A005704, A005705, and A005706. In particular, it is connected to partitions of integers into powers of κ = 1/q 2 when κ is a positive integer; see de Bruijn (1948); Fredman and Knuth (1974); Mahler (1940). It is known that (under suitable initial conditions) for large x, where P 1 (t) is a bounded 1-periodic function; see de Bruijn (1948); Dumas and Flajolet (1996). Thus We see that approximating the binomial distribution in (1.2) by its mean value E(µ n−1−Binom(n−1;p) ) ≈ µ n−1−E(Binom(n−1;p)) ≈ µ qn gives a very precise estimate, where Binom(n − 1; p) denotes a binomial distribution with parameters n − 1 and p.
An even simpler way to see the dominant order x c log x is to approximate (1.5) by the delay differential equation which is a special case of the so-called "pantograph equations" originally arising from the study of current collection systems for electric locomotives; see Iserles (1993); Kato and McLeod (1971); Ockendon and Tayler (1971). Since the usual polynomial or exponential functions fail to satisfy (1.7), we try instead a solution of the form ω(x) = x c log x ; then c should be chosen to satisfy the equation So we should take c = 1/(2 log κ) + O(x −1 log x). This gives the dominant term (log x) 2 2 log κ for log ω(x). More precise asymptotic solutions are thoroughly discussed in de Bruijn (1953); Kato and McLeod (1971). In particular, all solutions of the equation ω (x) = aω(qx) with a > 0 satisfies log ω(x) = log x log κ x 2 2 log κ + 1 2 + 1 log κ + log a log κ log x − 1 + log a log κ log log x for large x, where P 2 (t) is a bounded 1-periodic function. We see once again the generality of the asymptotic pattern (1.3).
On the other hand, the function and is a fundamental factor in the asymptotic theory of q-difference equations; see the two survey papers Adams (1931); Di Vizio et al. (2003) and the references therein. This equation will also play an important role in our analysis. From yet another angle, one easily checks that the series satisfies the equation (1.7). The largest term occurs, by simple calculus, at and, by the analytic approach we use in this paper, we can deduce that the logarithm of the series is, up to an error of O(1), of the same asymptotic order as log ν(x); see (1.6) and Section 6. The function M (x) arises sporadically in many different contexts and plays an important rôle in the corresponding asymptotic estimates; see below for a list of some representative references. A closely related sum arises in the average-case analysis of a simple backtracking algorithm (see Wilf (2002)), which corresponds to the expected number of independent sets in a random graph (or, equivalently, the expected number of cliques by interchanging q and p) J n := 1 j n n j q j(j−1)/2 , (1.8) see Matula (1970); Wilf (2002). Wilf Wilf (2002) showed that J n = O(n log n ) when p = 1/2. While such a crude bound is easily obtained, the more precise asymptotics of J n is more involved. First, it is straightforward to check that J n ∼ M (n) for large n. Second, the approach we develop in this paper can be used to show that J n has an asymptotic expansion similar to (1.3). Indeed, it is readily checked that J n + 1 satisfies the same recurrence relation as µ n with MIS-finding algorithms Exhaustive algorithms a n − a n−1 = 0 k<n π n,k a k Mahler's partitions a n − a n−1 = a qn Pantograph equations Figure 1: The connection between MIS-finding algorithms and the scale n c log n (discrete) or x c log x (continuous). The circles on the right-hand side are more algorithmic in nature, while those on the left-hand side more analytic in nature. different initial conditions. So the asymptotics of J n follows the same pattern (1.3) as that of µ n ; see Section 6 for more details.
Thus examining all independent sets one after another in the backtracking style of Wilf Wilf (2002) and identifying the one with the maximum cardinality also leads to an expected n c log n -complexity.
The diverse aspects we discussed of algorithms or equations leading to the scale n c log n are summarized in Figure 1. The bridge connecting the algorithms and the analysis is the binomial recurrence (1.2) as explained above.
This paper is organized as follows. We derive in the next section an asymptotic expansion for µ n using a purely analytic approach. The interest of deriving such a precise asymptotic approximation is at least fourfold.
Asymptotics: It goes much beyond the crude description n c log n and provides a more precise description; see particularly (1.4) and its implication mentioned there. Indeed, few papers in the literature address such an aspect; see de Bruijn (1948Bruijn ( , 1953; Dumas and Flajolet (1996); Kato and McLeod (1971); Pennington (1953); Richmond (1976).
Numerics: All scales involved in problems of similar nature here are expressed either in log or in log log, making them more subtle to be identified by numerical simulations. The inherent periodic functions and the slow convergence further add to the complications.
Methodology: Our approach, different from previous ones that rely on explicit generating functions in product forms, is based on the underlying functional equation and is of some generality; it is akin to some extent to Mahler's analysis in Mahler (1940).
Generality: The asymptotic pattern (1.3) is of some generality, an aspect already examined in details in several papers; see for example de Bruijn (1953); Dumas and Flajolet (1996); Kato and McLeod (1971). See also the last section for a list of diverse contexts where the order n c log n appears.
Alternative approaches leading to different asymptotic expansions are discussed in Section 3.
The next curiosity after the expected value is the variance. But due to strong dependence of the subproblems, the variance is quite challenging at this stage. We consider instead an idealized independent version of X n (the total cost of the exhaustive algorithm implied by (1.1)), namely with Y 1 := 1 and Y 0 := 0, where " d =" stands for equality in distribution, Y * n is an identical copy of Y n and the two terms on the right-hand side are independent. The original random variable X n satisfies the same distributional recurrence but with the two terms (X n−1 and X * n−1−Binom(n−1;p) ) on the right-hand side dependent. We expect that Y n would provide an insight of the possible stochastic behavior of X n although we were unable to evaluate their difference. We show, by a method of moments, that Y n is asymptotically normally distributed in addition to deriving an asymptotic estimate for the variance. Monte Carlo simulations for n up to a few hundreds show that the limiting distribution of X n seems likely to be normal, although the ratio between its variance and that of Y n grows like a concave function. But the sample size n is not large enough to provide more convincing conclusions from simulations.
Once the asymptotic normality of Y n is clarified, a natural question then is the limit law of the random variables (by changing the underlying binomial to uniform distribution) with Z 0 = 0 and Z 1 = 1. In this case, we prove that the mean is asymptotic to cn −1/4 e 2 √ n and the limit law is no more normal. We conclude this paper with a few remarks and a list of many instances where n c log n arises, further clarifications and connections being given elsewhere.

Expected cost
We derive asymptotic approximations to µ n in this section by an analytic approach, which is briefly sketched in Figure 2.1.

Preliminaries and main result
Recall that X n denotes the cost used by the exhaustive search algorithm (implied by (1.1)) for finding an MIS in a random graph, and it satisfies the recurrence with X 0 = 0 and X 1 = 1, where X * n d = X n , and the two terms on the right-hand side are dependent.
From (2.1), we see that the expected value µ n of X n satisfies the recurrence (1.2). Our analytic approach then proceeds along the line depicted in Figure 2.1. While the approach appears standard (see Flajolet and Sedgewick (2009) ;Jacquet and Szpankowski (1998);Szpankowski (2001)), the major difference is that instead of Mellin transform, we need Laplace transform since the quantity in question is not polynomially bounded. Also the diverse functional equations are crucial in our analysis, notably for the purpose of justifying the de-Poissonization, which differs from previous ones; see Jacquet and Szpankowski (1998); Szpankowski (2001).
Recurrence relation Figure 2: Our analytic approach to the asymptotics of µ n . Here π n,k := n−1 k q k p n−1−k .
By iteration, we then obtain the closed-form expressioñ Since f (z) = e zf (z), we then have This expression is, although exact, less useful for large n; also its asymptotic behavior remains opaque. See also (3.4) for another closed-form expression for µ n .
Asymptotic approximations. Our aim in this section is to derive the following asymptotic approximation.
Theorem 2.1. The expected cost µ n of the exhaustive search on a random graph satisfies (see (2.8)) and is a bounded, 1-periodic function of u.
Our approach leads indeed to an asymptotic expansion, but we content ourselves with the statement of (2.4); see (2.18), (2.23) and (3.3). The function f (and thusf ) is an entire function. It follows immediately that we have the identity (see Hwang et al. (2010)) (referred to as the Poisson-Charlier expansion in Hwang et al. (2010)) where the τ j (n)'s are polynomials of n of degree n/2 ; see (2.24). See also Jacquet and Szpankowski (1998) for different representations. However, the hard part is often to justify the asymptotic nature of the expansion, namely, for J = 2, 3, . . . . In particular, the first-order asymptotic equivalent "µ n ∼f (n)" is often called the Poisson heuristic. Thus the asymptotics of µ n is reduced to that off (x) once we justify the asymptotic nature of the expansion. Of special mention is that, unlike almost all papers in the literature, we need only the asymptotic behavior off (x) for real values of x, all analysis involving complex parameters being carefully handled by the corresponding functional equation.
We will derive an asymptotic expansion forf (x) for large real x by Laplace transform techniques and suitable manipulation of the saddle-point method, and then bridge the asymptotics of µ n andf (n) by a variant of the saddle-point method (or de-Poissonization procedure; see Jacquet and Szpankowski (1998)); see Figure 2.1 for a sketch of our proof.

Asymptotics off (x)
We derive an asymptotic expansion forf (x) in this subsection.
Modified Laplace transform. For technical convenience, consider the modified Laplace transformf Note that this use of the Laplace transform differs from the usual one by a factor 1/s and by a change of variables s → 1/s. Also the use of the exponential GF coupling with this Laplace transform is equivalent to considering the ordinary GF of µ n ; see Section 3.2 for more information.
Then the functional-differential equation (2.2) translates into the following functional equation forf q j(j+1)/2 1 + q j s s j+1 . (2.6) We will approximatef (s) for large s by means of the function because adding terms of the form s −j , j 0, does not alter the asymptotic order of both functions.
is a continuous, positive, periodic function with period 1.
Proof. One can easily check that F (s) satisfies a functional equation similar to that of Jacobi's theta functions F (s) = sF (qs) (s ∈ C). (2.9) Iterating N times this functional equation, we obtain which, together with the functional equation F (1/q) = F (1)/q (or G(u + 1) = G(u)), proves the lemma.
Asymptotic expansion off (x): saddle-point method By the inversion formula, we havẽ where r > 0 is a small number whose value will be specified later. We now derive a few estimates forf (s).
On the other hand if (s) 0, then It is easily checked that ϑ(x) satisfies the same functional equation (2.9) as F (x), namely, Thus, by the same arguments used for F (x), we have, for x > 1, where g(x) is a continuous, bounded, periodic function. Comparing this expression with (2.7) for F (x), we conclude that ϑ(x) = O(F (x)) for x 1. Let c m := q −2m − 1, m > 1. Then, for 0 < r < 1, This proves (2.14) and the lemma.
By splitting the integral in (2.11) into three ranges |t| c m r, c m r < |t| 1, and |t| > 1, and then applying the estimates (2.12) and (2.14), we deduce that It remains to evaluate more precisely the integral I r (x) by the saddle-point method.
To derive a more explicit expansion, we first observe that e xr F (1/r) = r −1/ log κ−1/2 e (log(1/r)) 2 /(2 log κ) G(log κ (1/r)), by (2.7) and (2.16). Then what remains is standard (see Flajolet and Sedgewick (2009)): evaluating the integral in (2.15) by Laplace's method (a change of variable t → t/ √ xr followed by an asymptotic expansion of H(t/ √ xr) for large xr and then an integration term by term), and we obtain the following expansion.
In particular, By using (2.17), the leading term in (2.18) can be expressed completely in terms of log x as follows.
(2.19) This is nothing but (2.1) with n there replaced by x.
As another consequence, we see, by (2.2) and (2.19), that More generally, we have the following asymptotic relations forf (j) (x) andf (q j x).
Corollary 2.6. For j 1f (2.21) Note that (2.20) also follows easily from the integral representatioñ and exactly the same arguments used above.

Asymptotics of µ n
We first derive a simple lemma for the ratio f (x + y)/f (x) when y is not too large by using (2.20).
Theorem 2.8. The expected cost used by the exhaustive search algorithm satisfies the asymptotic expansion
Proof. For simplicity, we prove only the following estimate (2.25) The same method of proof easily extends to the proof of (2.23). We start with the Taylor expansion off (z) at z = n to the fourth order By applying successively the equation (2.2), we get f (4) (z) = −e −z + q 3 e −qz − q 5 e −q 2 z + q 6 e −q 3 z + q 6f (q 4 z).
It follows that By the estimate (2.27) for R(z), we have

Alternative expansions and approaches
We discuss in this section other possible approaches to the asymptotic expansions we derived above.

An alternative expansion forf (x)
We begin with an alternative asymptotic expansion forf (x), starting from the integral representation (2.11), which, as showed above, can be approximated bỹ For simplicity, we will write this as Now we use the same N = log κ (1/r) = log κ (1/r) − η and Now instead of expanding F (q N /(r + it)) at t = 0, we expand F (q N /s) at s = r, giving where Q := q N /r = q −{log κ (1/r)} and F j denotes F (j) (Q). Substituting this expansion into the integral representation (3.1) and then integrating term-by-term, we obtaiñ where, by the integral representation for Gamma function (see Flajolet and Sedgewick (2009)), For computational purposes, it is preferable to use the recurrence The value of r is arbitrary up to now. If we take r = N/x, then Note that |T m (N )| N − m/2 . In particular, , · · · .
Since q N /r remains bounded, we can regroup the terms and get an asymptotic expansion in terms of increasing powers of N −1 , the first few terms being given as follows On the other hand, if we choose r = (N + 1)/x, then T 1 (N ) = 0 and While |T m (N )| N − m/2 for m 2 as in the case of r = N/x, this is a better expansion because the first term incorporates more information.
The more transparent expansion (3.2) is a priori a formal one whose asymptotic nature can be easily justified by the same local analysis as above, details being omitted here. We summarize the analysis in the following theorem.

Exponential GFs vs ordinary GFs
The different forms of the GFs of the sequence µ n have several interesting features which we now briefly explore. Instead off (s), we start with considering the usual Laplace transform off (z) which, by (2.6), satisfies .
By inverting this series, we obtaiñ From this exact expression, we deduce not only the exact expression (2.3) but also the following one (by multiplying both sides by e z and then expanding) where all terms are now positive; compare (2.3). But this expression and (2.3) are less useful for numerical purposes for large n.
On the other hand, the consideration of ourf (s) bridges essentially EGF and OGF of µ n . Indeed,f which is essentially the Euler transform of the OGF; see Flajolet and Richmond (1992).
Our proofs given above rely strongly on the use of EGF, but the use of OGF works equally well for some of them. We consider the general recurrence (4.6). Then the OGF A(z) := n 1 a n z n satisfies which after iteration gives Thus (3.5) Closed-form expressions can be derived from this; we omit the details here.

Variance of Y n
We derive in this section the asymptotics of the variance Y n (see (1.9)), which can be regarded as a very rough independent approximation to X n . We use an elementary approach (no complex analysis being needed) here based on the recurrences of the central moments and suitable tools of "asymptotic transfer" for the underlying recurrence. The approach is, up to the development of asymptotic tools, by now standard; see Hwang (2003); Hwang and Neininger (2002). The same analysis provided here is also applicable to higher central moments, which will be analyzed in the next section.

Asymptotic transfer
We now develop an asymptotic transfer result, which will be used to compute the asymptotics of higher central moments of Y n (in particular the variance). More generally, we consider a sequence {a n } n 0 satisfying the recurrence relation a n = a n−1 + 0 j<n π n,j a j + b n (n 1), (4.6) where a 0 is finite (whose value is immaterial) and {b n } n 1 is a given sequence.
This proves the lemma.
Proof. We start with obtaining upper and lower bounds for a n . Since b n > 0 for sufficiently large n, say n n 0 . We may, without loss of generality, assume that b n 0 for n n 0 (for, otherwise, we consider b n := b n + max j n 0 |b j | and then show the difference between the corresponding a n and a n is of orderf (n)). Then a n 0 and, by (4.6), we have the lower bound a n a n−1 + b n 0 j n b j . Now consider the sequence C n := a n 0 j n b j 1 (n 1), and the increasing sequence C * n := max Then we have the upper bound for all k n.
In view of the recurrence relation (4.6), we have a n C * By Lemma 4.1 and Corollary 2.6, we see that there exist an absolute constant K > 0 such that It follows that a n C * n−1 1 + Kn −α (log n) α 0 j n b j .
By our definition of C n , we then have Since the finite product on the right-hand side is convergent, we conclude that the sequence C * n is bounded, or more precisely, Thus we obtain the upper bound a n C where C > 0 is an absolute constant depending only on p, α, β and ξ.
With this bound and definingã n := 0 j<n π n,j a j , we can rewrite the recurrence relation (4.6) as a n = a n−1 +ã n + b n = 0 j n b j + 0 k nã k . (4.9) Now by the estimate (4.8), we see that Thus 0 j nã The proof of the Proposition is complete by substituting this estimate into (4.9).
Denote by [z n ]A(z) for the coefficient of z n in the Taylor expansion of A(z). Then, in terms of ordinary GFs, the asymptotic transfer (4.7) can be stated alternatively as (when b n satisfies the assumption of Proposition 4.2), which means that the contribution from terms in the sum in (3.5) with j 1 is asymptotically negligible. Roughly, since we see that b n,j = O(q j b q j n ). We can then give an alternative proof of (4.7) by using (3.5). By (4.5) and a direct application of Proposition 4.2, we obtain an asymptotic approximation to the variance.
Monte Carlo simulations (with n a few hundred) suggest that the ratio V(X n )/V(Y n ) grows concavely, so that one would expect an order of the form n β (log n) ξ for some 0 < β < 1. But due to the complexity of the problem, we could not run simulations of larger samples to draw more convincing conclusions. Asymptotics of V(X n ) remains open.

Asymptotic normality
We prove in this section that Y n is asymptotically normally distributed by the method of moments. Our approach is to start from the recurrence (4.2) for the central moments and the asymptotic estimate (4.10) and then to apply inductively the asymptotic transfer result (Proposition 4.2), similar to that used in our previous papers Hwang (2003); Hwang and Neininger (2002).
Theorem 5.1. The distribution of Y n is asymptotically normal, namely, where d → denotes convergence in distribution.
We will indeed prove convergence of all moments.
Proof. By standard moment convergence theorem, it suffices to show that The cases when m 2 having been proved above, we assume m 3. By induction hypothesis, we have It follows (see (4.3)) that, for 0 < m, 0 j<n π n,j M j, ∆ m− n,j = O n − /2−3m/2 (log n) /2+2mf (n) m ; and, for 2 k m − 2 and 0 m − k, Thus the main contribution to the asymptotics of T n,m will come from the terms in the second group of sums in (4.3) with k = m − 2 and = 0. More precisely T n,m = m 2 M n−1,m−2 T n,2 + O n −3/2−m (log n) 3(m+1)/2f (n) m .
Note that T n,2 ∼ 2n(log κ n) −1 σ 2 n ; see (4.5). Thus if m is even, then, by (4.5) and induction hypothesis, Applying the asymptotic transfer result (Proposition 4.2) with α = m, we obtain In a similar manner, we can prove that if m is odd, then M n,m = o(σ m n ). This concludes the proof of (5.1) and the asymptotic normality of Y n .

The random variables Z n
We briefly consider the random variables defined recursively in (1.10). The major interest is in understanding the robustness of the asymptotic normality when changing the underlying probability distribution from binomial to uniform.
Theorem 6.1. The mean value of Z n satisfies E(Z n ) = Cn −1/4 e 2 √ n 1 + 9 16 √ n + 11 1536n The limit law of the normalized random variables Z n /E(Z n ) is not normal where the distribution of Z is uniquely characterized by its moment sequence and the GF ζ(y) := m 1 E(Z m )y m /(m · m!) satisfies the nonlinear differential equation with ζ(0) = ζ (0) = 1.
Proof. (Sketch) The proof the theorem is simpler and we sketch only the major steps.
Mean value. First, ν n := E(Z n ) satisfies the recurrence ν n = ν n−1 + 1 n 0 j<n ν j (n 2), with ν 0 = 0, and ν 1 = 1. The GF f (z) of E(Z n ) satisfies the differential equation with the initial condition f (0) = 0. Surprisingly, this same equation (and the same sequence {ν n n!} n , which is A005189 in Encyclopedia of Integer sequences) occurs in the study of twosided generalized Fibonacci sequences; see Fishburn et al. (1988Fishburn et al. ( , 1989). The first-order differential equation is easily solved and we obtain the closed-form expression From this, the asymptotic approximation (6.1) results from a direct application of the saddlepoint method (see Flajolet and Sedgewick's book (Flajolet and Sedgewick, 2009, Ch. VIII)); see also Fishburn et al. (1989).
Asymptotic transfer. For higher moments and the limit law, we are led to consider the following recurrence. a n = a n−1 + 1 n 0 j<n a j + b n (n 2), (6.3) with a 0 and a 1 given. For simplicity, we assume a 0 = b 0 = 0.
Unique determination of the distribution. First, by a simple induction we can show, by (6.5), that ζ m cm!K m for a sufficiently large K > 0. This is enough for justifying the unique determination. Instead of giving the details, it is more interesting to note that the nonlinear differential equation (6.2) represents another typical case for which the asymptotic behavior of its coefficients (E(Z m ) for large m) necessitates the use of the psi-series method recently developed in Chern et al. (2012). We can show, by the approach used there, that where ρ > 0 is an effectively computable constant. Note that there is no term of the form m −1 in the expansion, a typical situation when psi-series method applies; see Chern et al. (2012).
This list is not aimed to be complete but to show to some extent the generality of the seemingly uncommon scale n c log n ; also it suggests the possibly nontrivial connections between instances in various areas, whose clarification in turn may lead to further development of more useful tools such as those in this paper.