Category Archives: 2000-2004

Some old talks

Here are slides for recent talks, in reverse chronological order of delivery. If the date is incomplete, then the slides are not yet available, probably because the talk has not yet been given. Slides for several earlier talks seem no longer to be available. I will be putting up any newer talks as individual blog posts.

Asymptotics of coefficients of multivariate generating functions Workshop in Asymptotic Enumeration, ANU, Canberra, 2007-09-{10-14}.

Polytope computations in social choice theory Auckland Discrete Mathematics and Social Sciences Seminar 2007-04-23.

The diameter of random Cayley graphs 12th AofA workshop Alden Biesen 2006-07-06

Asymptotics of generalized Riordan arrays 11th AofA workshop Barcelona 2005-06-08

Multivariate generating functions II CDMTCS seminar Auckland 2005-04-26

Multivariate generating functions I CDMTCS seminar Auckland 2005-04-12

Sattolo’s algorithm INRIA Rocquencourt 2004-06-28

Towards a theory of multivariate generating functions INRIA Rocquencourt 2004-06-28

Asymptotics of multivariate generating functions Melbourne FPSAC conference 2002-07-

Superalgebras and their uses Missoula 1999-03-09

Primitive ideals in Hopf algebra extensions San Antonio 1999-01-14

Algebras of my acquaintance Auckland 1998-04-29

Probability generating functions for Sattolo’s algorithm

Mark C. Wilson, Journal of the Iranian Statistical Society 3 (2004), 297-308 (special issue on probabilistic analysis of algorithms).

Download author version

Abstract: In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. Recently H. Prodinger analysed two important random variables associated with the algorithm, and found their mean and variance. H. Mahmoud extended Prodinger’s analysis by finding limit laws for the same two random variables.

The present article, starting from the definition of the algorithm, is completely self-contained. After giving a simple new proof of correctness, we generalize the abovementioned probabilistic results results by determining the “grand” probability generating functions of the random variables.

The focus throughout is on using standard methods that give a unified approach, and open the door to further study.

Asymptotics of multivariate sequences, part II: multiple points of the singular variety

Robin Pemantle and Mark C. Wilson, Combinatorics, Probability and Computing 13 (2004), 735-761.

Download author version

Abstract: Let $latex F(mathbf{z})=sum_mathbf{r} a_mathbf{r}mathbf{z^r}$ be a multivariate generating function which is meromorphic in some neighborhood of the origin of $latex mathbb{C}^d$, and let $latex mathcal{V}$ be its set of singularities. Effective asymptotic expansions for the coefficients can be obtained by complex contour integration near points of $latex mathcal{V}$.

In the first article in this series, we treated the case of smooth points of $latex mathcal{V}$. In this article we deal with multiple points of $latex mathcal{V}$.

Asymptotics of multivariate sequences, part I: smooth points of the singular variety

Robin Pemantle and Mark C. Wilson, Journal of Combinatorial Theory Series A 97 (2002), 129-161.

Download author version

Abstract: Given a multivariate generating function $latex F(z_1 , ldots , z_d) = sum a_{r_1 , ldots , r_d} z_1^{r_1} cdots z_d^{r_d}$, we determine asymptotics for the coefficients. Our approach is to use Cauchy’s integral formula near singular points of $latex F$, resulting in a tractable oscillating integral. This paper treats the case where the singular point of $latex F$ is a smooth point of a surface of poles. Companion papers will treat singular points of $latex F$ where the local geometry is more complicated, and for which other methods of analysis are not known.