April 19, 2018


Summer School in Applied Probability
to be held at Carleton University
May 11 – 21, 2009

Organizers: Zhicheng (Jason) Gao, Minyi Huang, Daniel Panario and Yiqiang Q. Zhao


Asymptotic and Probabilistic Properties of Combinatorial Structures
Part I: Analytic Combinatorics: A Primer
Lecturer: Conrado Martinez, Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya.

As the title suggests, this short course is an introduction to Analytic Combinatorics (AC). It has three parts. In the first one, we will introduce the basics of the symbolic method and concentrate in the combinatoric and algebraic properties of generating functions, the main tool of AC. In the second part, we will review some important results that follow when we deal with generating functions (also known as formal power series) as analytic functions in the complex plane. In particular we shall study singularity analysis and the saddle-point method. Last but not least, the third part will be devoted to applications, mainly enumerative combinatorics and analysis of algorithms, with practical examples.

Part II: Phase Changes in Random Structures and Algorithms
Lecturer: Hsien-Kuei Hwang, Institute of Statistical Science, Academia Sinica.

After an introduction to the area, this short course will include a lecture on each of the following topics:

1) method of moments and its refinements,
2) random search trees,
3) Quicksort and its variants,
4) the level profiles and related quantities,
5) differential equations with polynomial coefficients.

In each of these lectures, a corresponding theory of asymptotic transfer will also be presented.


Markov Chains: Intertwinings, Strong Stationary Times and Duality, Perfect Simulation, and Absorption Times
Speaker: Jim Fill, Department of Applied Mathematics and Statistics, The Johns Hopkins University.

The required background is elementary knowledge of Markov chains. I will explain what an intertwining of Markov semigroups is, and how intertwinings can be used to help
(a) analyze mixing times of ergodic Markov chains and absorption times of absorbing chains, and (b) for ergodic chains, construct and analyze randomized stopping times achieving perfect stationarity. The course will present theory and applications.

Here are some basic references:
  1. Aldous, D. and Diaconis, P. (1986). Shuffling cards and stopping times. American Mathematical Monthly 93, 333-348.
  2. Aldous, D. and Diaconis, P. (1987). Strong uniform times and finite random walks. Advances in Applied Mathematics 8, 69-97.
  3. Diaconis, P. and Fill, J. A. (1990). Strong stationary times via a new form of duality. Annals of Probability 18, 1483-1522.
  4. Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms 9, 223-252.
  5. Fill, J. A. (1998). An interruptible algorithm for perfect sampling via Markov chains. Annals of Applied Probability 8, 131-162.
  6. Fill, J. A. (2007). The passage time distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof. Journal of Theoretical Probability, to appear. [arXiv:0707.4042] [ ]
  7. Fill, J. A. (2007). On hitting times and fastest strong stationary times for skip-free chains. Journal of Theoretical Probability, to appear (after some extensions). [arXiv:0708.4258] []
  8. Diaconis, P. and Miclo, L. (2007). On times to quasi-stationarity for birth and death processes. Preprint. []
  9. Miclo, L. (2008). On absorbtion [sic] times and Dirichlet eigenvalues. Preprint. []

Queues, reflected random walks and the kernel method

Lecturer: Johan van Leeuwaarden, Department of Mathematics and Computer Science, Eindhoven University of Technology

The kernel method has a long tradition in queueing theory, random walk theory and combinatorics. It refers to a specific way in which multivariate generating functions can be derived from functional equations. We shall demonstrate the kernel method for one-dimensional reflected random walks and for two-dimensional random walks in the quarter plane. Along the way, we shall explore connections between queues and enumerative combinatorics, and we pay attention to asymptotic analysis, rare events and heavy-traffic regimes.

Selected Topics in Stochastic Approximation, Two-time-scale Systems, Switching Diffusions, and Applications

Speaker: G. George Yin, Department of Mathematics, Wayne State University.

In the series of lectures, we plan to cover several selected topics. Beginning with motivations from parameter estimation, we present the objectives and purposes of stochastic approximation (SA), the basic algorithms and their variants, and the main asymptotic properties of the algorithms. We will describe how correlated noise processes can be dealt with. Application examples from wireless communications, financial engineering, and image segmentation etc. will also be presented along with simulation, numerical experiment, and computation results using real data.

Next, we demonstrate how two-time-scale approaches can be used to reduce the computational complexity for Markov chains having large state spaces. The idea is based on the recent work on two-time-scale Markov chains. If time permits, we will also present some of our recent work on fundamental properties of switching diffusions.

Stemming from emerging applications in wireless communications and adaptive signal processing, the third lecture is devoted to tracking Markovian parameters. The algorithms use constant-step size to update the increments of a sequence of occupation measures or the increments from adaptive filtering type estimates. Limit regime-switching ordinary differential equations and limit regime-switching diffusions will be developed.

Outline of Tutorial on Markov Chain Monte Carlo
Neal Madras, York University (madras(at)

In the first part (about two thirds of the tutorial), I shall introduce the basic idea and definitions of Markov chain Monte Carlo (MCMC). Due to limited time, I shall only discuss discrete state spaces (although many things carry over directly to general state spaces). I shall include a very rapid review of some results about Markov chains, but I shall assume that students already have an elementary knowledge of Markov chains and their stationary distributions. Connections with random walks on graphs will be highlighted. I shall present some specific applications where MCMC has been important (e.g. Ising model, self-avoiding walk). I shall also present the Metropolis Algorithm, a versatile method for constructing MCMC chains.

In the second part of the course, I shall introduce issues concerning the speed of a Markov chain's convergence to equilibrium. This is a significant practical problem in MCMC: how long must one run a chain before we are "confident that it is in equilibrium" (and what exactly does this mean)? Finally, I shall describe some simple statistical approaches (batch means, simple time series) for coping with this problem in practical situations (i.e. what you can do if you are really running a simulation and you want an answer). For these problems, theory falls well short of practical needs, but the theory can still give us useful guidance.

Much of the material is based on Chapters 4 and 5 of:

Neal Madras, "Lectures on Monte Carlo Methods" (Fields Institute Monographs Series) (American Mathematical Society, Providence, 2002).

Back to Summer School Home page

For additional information inquiries may be directed to: