Asymptotics of Multivariate Sequences

The aim of this project is to systematize (asymptotic) coefficient extraction from a wide class of naturally occurring multivariate generating functions (mvGFs). We aim to take a genuinely multivariate approach, and to improve over previous work in the areas of generality, ease of use, and suitability for effective computation.

The topic is inherently interdisciplinary and in particular uses complex analysis in one and several variables, asymptotics of integrals, symbolic computation. The application areas are many: we are particularly motivated by specific naturally occurring problems arising from areas such as multivariable recurrence relations, random tilings, queueing theory, and analysis of algorithms and data structures. If you are interested in working on these problems, please let us know.

Our methods have been based on using complex analysis and oscillatory integrals to analyse singularities of explicitly known GFs. So far, attention has been limited to meromorphic, non-entire GFs (``small singularities" in the terminology of Odlyzko). We deal with GFs of the form F(z₁ , ..., z_d) = ∑ a_{r₁ ,
... , r_d} z₁^r₁ ... z_d^r_d which have locally the form G/H with G and H analytic functions, and the singular variety V (zero-set of H) plays a big role.

Publications in this project

Papers are listed generally in reverse chronological order of production. Papers applying results of this project to other areas are listed below this section. Versions linked here are usually not the official published versions, but they are usually the latest prepublication versions held by the authors.

Publications concerning core theory of the project

Analytic combinatorics in d variables: An overview by Robin Pemantle. AMS Contemporary Mathematics 520.
A case study in bivariate singularity analysis by Timothy Devries. AMS Contemporary Mathematics 520.
The first detailed treatment of an example in which asymptotics in the scale of $n^{1/4}$ occur rather than the usual $n^{1/2}$. A degenerate saddle point occurs in a natural counting problem whose answer is expressed as the diagonal sequence of a bivariate rational generating function. Results from previous papers do not cover this case. Performing the analysis in this example represents a first step towards understanding general cases of this geometric type.
Asymptotic expansions of oscillatory integrals with complex phase by Robin Pemantle and Mark C. Wilson. AMS Contemporary Mathematics 520.
We consider saddle point integrals in d variables whose phase function is neither real nor purely imaginary. Results analogous to those for Laplace (real phase) and Fourier (imaginary phase) integrals hold whenever the phase function is analytic and nondegenerate. These results generalize what is well known for integrals of Laplace and Fourier type. The method is via contour shifting in complex d-space. This work is motivated by applications to asymptotic enumeration, and fulfils a promised citation made in an earlier paper by these authors.
Tilings, groves and multiset permutations: asymptotics of rational generating functions whose pole set includes a cone by Yuliy Baryshnikov and Robin Pemantle.
We consider a number of combinatorial problems in which rational generating functions may be obtained, whose denominators have factors with certain singularities. Specifically, there exist cone points, near which one of the factors is asymptotic to a nondegenerate quadratic. We compute the asymptotics of the coeﬃcients of such a generating function. The computation requires some topological deformations as well as Fourier-Laplace transforms of generalized functions. We apply the results of the theory to speciﬁc combinatorial problems. This deals with another case in the original taxonomy outlined in the first paper of Pemantle and Wilson.
Asymptotics of coefficients of multivariate generating functions: improvements for smooth points by Alexander Raichev and Mark C. Wilson. Electron. J. Combin. 15 (2008), no. 1, Research Paper 89, 17 pp.
We improve over the first paper by Pemantle and Wilson, and derive explicit formulae for the entire asymptotic series obtained by analysis near a smooth point of the singular variety. The numerical results obtained show how well these approximations work in practice.
A new method for computing asymptotics of diagonal coefficients of multivariate generating functions by Alexander Raichev and Mark C. Wilson. Proceedings of International Conference on Analysis of Algorithms, Juan-les-Pins, 2007.
Let $\sum_{\nvec\in\nats^d} f_\nvec \xvec^\nvec$ be a multivariate generating function that converges in a neighborhood of the origin of $\comps^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $f_{a_1n,\ldots,a_dn}$ and show its superiority over the standard, univariate diagonal method.
Mixed powers of generating functions by Manuel Lladser. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Discrete Mathematics and Theoretical Computer Science Proceedings, AG, 171-182, 2006.
This paper derives uniform asymptotics for a multivariate generalization of Riordan arrays, namely a GF of the form $\prod_j (1 - w_j f_j(z))^{-1}$. In other words we seek the asymptotics of $[z^{n_0}] \prod_j f_j(z)^{n_j}$ as at least one of the exponents $n_j$ tends to infinity. This generalizes several results in the literature. Once again reduction to Fourier-Laplace integral is the key step.
Uniform formulae for coefficients of meromorphic functions in two variables. Part I By Manuel Lladser, to appear in SIAM Journal on Discrete Mathematics.
This paper derives uniform asymptotics in the smooth bivariate case when the directions in question are such that there is no phase change in the underlying Fourier-Laplace integral. This generalizes results in "Asymptotics of multivariate sequences. I." below.
Twenty combinatorial examples of asymptotics derived from multivariate generating functions by Robin Pemantle and Mark C. Wilson, preprint (2005), 89 pages. SIAM Review 50 (2008), 199-272.
We illustrate the use of the techniques of some of the papers below, on a variety of problems of combinatorial interest. The survey begins by summarizing previous work on the asymptotics of univariate and multivariate generating functions. Next we describe the Morse-theoretic underpinnings of some new asymptotic techniques. We then quote and summarize these results in such a way that only elementary analyses are needed to check hypotheses and carry out computations. The remainder of the survey focuses on combinatorial applications, such as enumeration of words with forbidden substrings, edges and cycles in graphs, polyominoes, and descents in permutations. After the individual examples, we discuss three broad classes of examples, namely functions derived via the transfer matrix method, those derived via the kernel method, and those derived via the method of Lagrange inversion. These methods have the property that generating functions derived from them are amenable to our asymptotic analyses, and we describe further machinery that facilitates computations for these classes of examples.
Asymptotics for generalized Riordan arrays by Mark C. Wilson, Discrete Mathematics and Theoretical Computer Science, volume AD (2005), 323-334 (Proceedings of the 2005 International Conference on Analysis of Algorithms, Barcelona).
This applies the results of papers below to derive bivariate asymptotics for the special case $F(x, y) = \phi(x)/(1 - yv(x))$, which arises frequently in applications.
Convolutions of inverse linear functions via multivariate residues by Yuliy Baryshnikov and Robin Pemantle, preprint (2004), 42 pages.
This uses stratified Morse theory to derive complete expansions when $V$ is a union of hyperplanes ($H$ is a product of linear factors). Such GFs occur often in queueing theory. It does not handle directions on the boundary of the cones mentioned below (Asymptotics of Multivariate Sequences, II). At present, each of these articles does something the other cannot.
Asymptotics of multivariate sequences II: multiple points of the singular variety by Robin Pemantle and Mark C. Wilson, Combinatorics, Probability and Computing 13 (2004), 735-761.
In this article we deal with multiple points of $V$. Our results show that the central limit (Ornstein-Zernike) behavior typical of the smooth case does not hold in the multiple point case. For example, when $\sing$ has a multiple point singularity at $(1 , \ldots , 1)$, rather than $a_\b{r}$ decaying as $|\b{r}|^{-1/2}$ as $|\b{r}| \to \infty$, $a_\b{r}$ is very nearly polynomial in a cone of directions.
Asymptotic enumeration via singularity analysis by Manuel Lladser. PhD thesis, Ohio State University 2003.
Asymptotics for smooth points are computed in the above articles by Fourier-Laplace integrals, and are usually uniform for most sets of directions. However there can be directions where the asymptotic behaviour changes (for example, in "Airy phenomena" where $r^{-1/2}$ becomes $r^{-1/3}$) and uniformity breaks down. The thesis studies such situations in detail in the two-dimensional case. It relies on the asymptotic analysis of a certain type of "parameter-varying" F-L integral of the form $\int exp(-s P(d,x)) A(d,x) \, dx$. The cases of interest are when either the phase term $P(d,x)$ or the amplitude term $A(d,x)$ exhibits a change of degree as $d$ approaches a degenerate direction. These are handled by a generalized version of the stationary phase and the coalescing saddle point method. Uniform expansions and local limit results are obtained.
Asymptotics of multivariate sequences I: smooth points of the singular variety by Robin Pemantle and Mark C. Wilson, Journal of Combinatorial Theory A 97 (2002), 129-161.
This article treats the case of smooth points of $V$. It includes a detailed introduction to the project, discusses previous work on the topic and lays the groundwork for further papers by devising a taxonomy. Then it treats the most commonly occurring case, smooth points. Companion papers will treat points of $V$ where the local geometry is more complicated, and for which other methods of analysis are not known.
Note: the published version (reprints are available) contains many errors, several the fault of the publisher. In particular, in Thm 3.5 there should be a minus sign in the denominator of the expression for the constant C_0.
Generating functions with high-order poles are nearly polynomial by Robin Pemantle, Mathematics and computer science (Versailles, 2000), 305--321. Trends in Mathematics, Birkhauser, Basel, 2000.
Explains why our multivariate asymptotic expansions sometimes have only finitely many terms, and hence are effectively computable.

Papers using the basic theory in application areas

Quantum random walks on the integer lattice via generating functions by Andrew Bressler. PhD thesis, U. Penn., 2009.
This thesis contains several early results from the papers below. It also includes exact asymptotics for a three-chirality walk on the line and the 2-D Hadamard walk, as well as a proof of Airy phenomena for the two-chirality walk. It concludes with a preliminary discussion of higher dimensions.
Random walk on the integer lattice: examples and phenomena by Andrew Bressler, Torin Greenwood, Robin Pemantle, and Marko Petkovsek.
We apply results from the previous 2-D QRW paper to compute limiting probability profiles for various quantum random walks in one and two dimensions. Using analytic machinery we show some features of the limit distribution that are not evident in an empirical intensity plot of the time 10,000 distribution. Some conjectures are stated and computational techniques are discussed as well.
Two-dimensional quantum random walk by Yuliy Baryshnikov, Wil Brady, Andrew Bressler, and Robin Pemantle.
We analyze several families of two-dimensional quantum random walks. The feasible region (the region where probabilities do not decay exponentially with time) grows linearly with time, as is the case with one-dimensional QRW. The limiting shape of the feasible region is, however, quite different. The limit region turns out to be an algebraic set, which we characterize as the rational image of a compact algebraic variety. We also compute the probability profile within the limit region, which is essentially a negative power of the Gaussian curvature of the same algebraic variety. Our methods are based on analysis of the space-time generating function, following the methods of the first paper of Pemantle and Wilson. Some extensions to toral singularities are required.
Quantum random walks in one dimension via generating functions by Andrew Bressler and Robin Pemantle. Proceedings of International Conference on Analysis of Algorithms, Juan-les-Pins, 2007.
Extended abstract (full version to appear sometime).
Quantum random walks on $\mathbb{Z}^2$ by Wil Brady. MS thesis, U. Penn., 2007.
This thesis computes the asymptotic probability profile for nearest-neighbor quantum random walks in the two-dimensional integer lattice with various quantum coins (4x4 unitary matrices). A shape theorem is proved for the Hadamard coin (the standard choice). Analogous results for other coins, exhibiting an unexpectedly wide range of visual phenomena, are verified numerically but not proved. The numeric finite-time profiles are compared to pictures of the theoretically computed range of non-exponential decay. The shapes are indeed the same. Furthermore, plots of the normalized probabilities in the non-exponential region turn out to have internal structure that is mirrored in the rendering of the theoretically predicted non-exponential decay region via point plotting. This has led to followup work showing why both of these are essentially the same as a plot of the push-forward via the Gauss map of the surface measure on the toral part of the pole variety.

Citations and applications of this project by others

Papers directly using the results of this project
- M. Erickson, S. Fernando, K. Tran, Enumerating Rook and Queen Paths, Bulletin of the Institute for Combinatorics and Its Applications 60 (2010), 37--48.
- Noble, R. Asymptotics of a family of binomial sums. Journal of Number Theory 130 (2010), 2561-2585.
- Sahlmann, H. Entropy calculation for a toy black hole. Classical and Quantum Gravity, 200825 (5), art. no. 055004.
- Kong, Y. Asymptotics of the monomer-dimer model on two-dimensional semi-infinite lattices, Physical Review E 75, 051123 (2007) (13 pages).
- Kong, Y. Monomer-dimer model in two-dimensional rectangular lattices with fixed dimer density. Physical Review E 74, 061102 (2006) (15 pages).
- Corteel, S., Louchard, G., Pemantle, R. Common intervals in permutations. Discrete Mathematics and Theoretical Computer Science 8 (2006), pp. 189-214.
- Wormald, N. Tournaments with many Hamilton cycles. Preprint, 2001.
Papers/books citing publications of this project
- Kauers, M., Zeilberger, D. The computational challenge of enumerating high-dimensional rook walks. Advances in Applied Mathematics, 47 (2011), 813-819.
- Guillemin, F.F., Leeuwaarden, J.S.H. Rare event asymptotics for a random walk in the quarter plane. Queueing Syst. 67 (2011), 1-32
- Antal, T., Krapivsky, P.L. Exact solution of a two-type branching process: Clone size distribution in cell division kinetics. Journal of Statistical Mechanics: Theory and Experiment, 2010 (7), art. no. P07028.
- Chang, H., Fuchs, M. Limit theorems for phylogenetic trees. Journal of Mathematical Biology 60 (2010), 481-512.
- Flajolet, P., Sedgewick, R. Analytic Combinatorics. Cambridge, 2009.
- Richard, C. Limit distributions and scaling functions. Lecture Notes in Physics, 775 (2009), 247-299.
- Egorychev, G.P., Zima, E.V. Integral Representation and Algorithms for Closed Form Summation (2008) Handbook of Algebra, 5, pp. 459-529.
- Stanley, R.P. Longest alternating subsequences of permutations (2008) Michigan Mathematical Journal, 57 (1), pp. 675-687.
- Grosskinsky, S. Equivalence of ensembles for two-species zero-range invariant measures. Stochastic Processes and their Applications 118 (2008), 1322-1350.
- Tamm, M. V., Nechaev, S. K. Necklace-cloverleaf transition in associating RNA-like diblock copolymers. Phys. Rev. E 75 (2007), 031904.
- Lladser, M. Uniqueness of polynomial cannonical representations (extended abstract) 2007 Conference on Analysis of Algorithms, Discrete Mathematics and Theoretical Computer Science Proceedings, AH, 463-470, 2007.
- Flajolet, P. Analytic combinatorics: a calculus of discrete structures. Proceedings of the eighteenth annual ACM-SIAM Symposium on Discrete algorithms (2007), 137-148.
- Lichtin, B. Uniform bounds for two variable real oscillatory integrals and singularities of mappings. Journal fur die Reine und Angewandte Mathematik, 611 (2007), 1-73.
- Dantas, W.G., De Oliveira, M.J., Stilck, J.F. Asymptotic behavior of the entropy of chains placed on cylinders. Physical Review E 76 (3), 031133.
- Firro, G., Mansour, T., Wilson, M. C. Longest alternating subsequences in pattern-restricted permutations. Electronic Journal of Combinatorics 14 (2007), R34.
- Berenhaut, K.S., Foley, J.D. Explicit bounds for multidimensional linear recurrences with restricted coefficients. Journal of Mathematical Analysis and Applications 322 (2006), pp. 1159-1167.
- Gao, Z., Panario, D. Degree distribution of the greatest common divisor of polynomials over F_q. Random Structures and Algorithms 29 (2006), pp. 26-37.
- Petersen, T.K., Speyer, D. An arctic circle theorem for Groves. Journal of Combinatorial Theory. Series A 111 (2005), pp. 137-164.
- De Loera, J.A., Hemmecke, R., Tauzer, J., Yoshida, R. Effective lattice point counting in rational convex polytopes. Journal of Symbolic Computation 38 (2004), pp. 1273-1302.
- Baryshnikov, Y., Coffman Jr., E.G., Jelenkovic, P. Space filling and depletion. Journal of Applied Probability 41 (2004), pp. 691-702.
- Banderier, C., Flajolet, P., Schaeffer, G., Soria, M. Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Structures and Algorithms 19 (2001), pp 194-246.

Software

Maple worksheets and other scripts automating some of the computations in these papers are available from Alex Raichev's research page, and from Robin Pemantle's site.

A much more comprehensive package is under development. Please contact us to discuss.

People

This is a list of people who have published in this project so far.

Last updated: 2011-10-03

Asymptotics of multivariate sequences