Stephen Melczer and I have just posted a paper to arXiv.org:
Asymptotics of lattice walks via analytic combinatorics in several variables.
In my humble opinion this is a nontrivial advance in the area. It is a nice application of smooth and multiple point asymptotics in the framework developed by Robin Pemantle and me.
Last week I made a flying visit to Canada for this annual meeting (it’s hard to imagine any other type given the distance, but it was particularly short – less than 72 hours in the country). I was invited by Steve Melczer, an impressive PhD student who seems to have read my coauthored book better than anyone alive, and with whom I hope to collaborate this year. Despite the arduous travel, it was a worthwhile experience and should lead to some nice joint publications.
I noticed that many of the buildings at the beautiful campus of the University of Saskatchewan are connected underground, giving a clue to the winter weather. Even though it was early June, the weather was not particularly warm. On my return via Calgary Airport, I noticed that it was 12 degrees and raining at 4pm (in summer, or close enough). The next morning in Auckland at 4am, it was 13 degrees and raining (in winter).
Robin Pemantle and I have written a book summarizing over a decade of research. The first draft sent to the publisher is available from the book website. We expect publication in 2013 and welcome feedback on this draft version.
Robin Pemantle and I have just submitted this paper, which fills in some gaps from our previous work. There is still more to be done along these lines – asymptotics of integrals whose stationary points are not isolated or are at a vertex of a simplex, for example, requires more work.
Abstract: 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.
I went to this conference in Dunedin just for the first two days – it ends on 20 June.
A lot of good generating functions arise from the enumeration of permutations avoiding certain patterns. The plenary talk by Mireille Bousquet-Melou (whose talks are always a model of clarity) discussed the systematic solution of various functional equations arising from fairly straightforward recursive decompositions of these combinatorial classes. As well as the by now traditional kernel method, she discussed the “algebraic kernel method” which uses symmetries of the kernel function to derive a system of equations that is amenable to simplification.
I have been thinking for a long time about the need for a better presentation of the kernel method in these contexts. Perhaps this will finally inspire me to write something.
Alex Raichev and I have just submitted a journal article on this topic (read it on arXiv). The associated Maple 11 worksheets can be found on Alex’s site. We improve over previous work by Robin Pemantle and me, and derive explicit formulae for the entire asymptotic series obtained by approximating the coefficients of a generating function near a smooth point of the singular variety. The numerical results obtained show how well these approximations work in practice.
I heard a talk by Wojtek Szpankowski a few years ago where he quoted Ziv as saying that second order asymptotics were needed in information theory. Persi Diaconis told me years ago that the work with Robin is all very nice, but what about looking at approximations that work for moderately small values, not just asymptotic approximations. I hope that this paper will satisfy both needs.
On the occasion (today in the USA) of Don Knuth’s 70th birthday, several bloggers have posted tributes (see Jeffrey Shallit’s list). His list of achievements is really impressive, and he has had a big influence on me. To name a few areas, somewhat facetiously: his founding of the field of analysis of algorithms (AofA) led to the development of a community of people who are heavy users of generating function methodology and therefore may be interested in my research in that area, and it gave me something nice to teach as a mathematician moving into a CS department! More seriously, I can’t conceive of computer science as a real science without proper analysis of algorithms, and I would hate to have to write papers without using TeX.
Since unalloyed praise can get a bit cloying, I will mention that it might have been better for the world if Knuth (or someone else) had been able to build a school of AofA in the USA. The algorithms community in the USA is heavily dominated by “worst-case” analysis and indeed by analysis of problem complexity, which is a very weak form of analysis of algorithms, concentrating as it does on lower bounds and rather weak (many would say useless) upper bounds.
The main development of AofA along Knuthian lines has been in Europe, in France (Philippe Flajolet and others) and Austria particularly. In recent years Bob Sedgewick and others have tried to bridge the gap between these communities through meetings such as ANALCO, but at least to my eyes they have not yet had great success.
Of course some may say that the sort of very detailed analysis by Knuth is unnecessary for a working computer scientist. And even if his analyses made sense in the days of flat memory, the prevalence of such things as caching makes it impossible to make such detailed predictions nowadays. But perhaps we just need some better mathematics.
Manuel Lladser, Primoz Potocnik, Jana Siagova, Jozef Siran and Mark C. Wilson, submitted to Random Structures and Algorithms, June 2006 (12 pages)
Abstract: We consider random Cayley digraphs of order $latex n$ with uniformly distributed generating set of size $latex k$. Specifically, we are interested in the asymptotics of the probability such a Cayley digraph has diameter two as $latex ntoinfty$ and $latex k=f(n)$. We find a sharp phase transition from 0 to 1 as the order of growth of $latex f(n)$ increases past $latex sqrt{n log n}$. In particular, if $latex f(n)$ is asymptotically linear in $latex n$, the probability converges exponentially fast to 1.
Alexander Raichev and Mark C. Wilson, to appear in Proceedings of the International Conference on Analysis of Algorithms (Juan-les-Pins, June 2007).
Let $latex sum_{mathbf{n}inmathbb{N}^d} f_{mathbf{n}} mathbf{x}^mathbf{n}$ be a multivariate generating function that converges in a neighborhood of the origin of $latex mathbb{C}^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $latex f_{a_1n,ldots,a_dn}$ and show its superiority over the standard, univariate diagonal method.
Note: there is a typo: in Example 3.6, we should have $latex c = ( (L-b)/a, (L-a)/b )$ where $latex L = sqrt{a^2 + b^2}$.
Ghassan Firro, Toufik Mansour and Mark C. Wilson, Electronic Journal of Combinatorics 14 (2007), R34 (11 pages).
Abstract: Inspired by the results of Stanley and Widom concerning the limiting distribution of the lengths of longest alternating subsequences in random permutations, and results of Deutsch, Hildebrand and Wilf on the limiting distribution of the longest increasing subsequence for pattern-restricted permutations, we find the limiting distribution of the longest alternating subsequence for pattern-restricted permutations in which the pattern is any one of the six patterns of length three. Our methodology uses recurrences, generating functions, and complex analysis, and also yields more detailed information. Several ideas for future research are listed.