“Higher order asymptotics from multivariate generating functions” was presented at University of Pennsylvania, Rutgers University, University of California Berkeley and University of California Davis.
“Measuring manipulability of voting rules” was presented at University of Rochester and Union College.
These and others can be found on my archive of talks.
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.
Reyhaneh Reyhani, Geoffrey Pritchard and I have just submitted this to a special issue of Journal of Autonomous Agents and Multi-Agent Systems concerning computational social choice.
Abstract: We introduce new measures of manipulability of anonymous voting rules
and argue for their superiority over some commonly used measures. We give a sim-
ple common framework that describes these measures and connects them to recent
literature. We discuss their computation and present numerical results that allow for
comparison of various common voting rules.
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.
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.
Geoffrey Pritchard and Mark C. Wilson, submitted to Journal of Economic Theory, February 2007 (20 pages).
Abstract: We consider the problem of manipulation of elections using positional voting rules under Impartial Culture voter behaviour. We consider both the logical possibility of coalitional manipulation, and the number of voters that must be recruited to form a manipulating coalition. It is shown that the manipulation problem may be well approximated by a very simple linear program in two variables. This permits a comparative analysis of the asymptotic (large-population) manipulability of the various rules. It is seen that the manipulation resistance of positional rules with 5 or 6 (or more) candidates is quite different from the more commonly analyzed 3- and 4-candidate cases.
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}$.
to appear in Annals of Combinatorics (10 pages).
Abstract: In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. This algorithm is very similar to the standard method for generating a random permutation, but is less well known.
We consider both methods in a unified way, and discuss their relation with exhaustive generation methods. We analyse several random variables associated with the algorithms and find their grand probability generating functions, which gives easy access to moments and limit laws.
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.
Mark C. Wilson and Geoffrey Pritchard, Mathematical Social Sciences 54 (2007), 244-256.
Abstract: We show how powerful algorithms recently developed for counting lattice points and computing volumes of convex polyhedra can be used to compute probabilities of a wide variety of events of interest in social choice theory. Several illustrative examples are given.