 |
|
|
|
|
|
Fields-MITACS
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
|
Minicourses
-----
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.
Summary:
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.
Summary:
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.
Summary:
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:
- Aldous, D. and Diaconis, P. (1986). Shuffling cards and stopping
times. American Mathematical Monthly 93, 333-348.
- Aldous, D. and Diaconis, P. (1987). Strong uniform times and
finite random walks. Advances in Applied Mathematics 8, 69-97.
- Diaconis, P. and Fill, J. A. (1990). Strong stationary times
via a new form of duality. Annals of Probability 18, 1483-1522.
- 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.
- Fill, J. A. (1998). An interruptible algorithm for perfect
sampling via Markov chains. Annals of Applied Probability 8,
131-162.
- 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]
[ http://front.math.ucdavis.edu/0707.4042
]
- 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] [http://front.math.ucdavis.edu/0708.4258]
- Diaconis, P. and Miclo, L. (2007). On times to quasi-stationarity
for birth and death processes. Preprint. [ http://hal.archives-ouvertes.fr/hal-00164690/en/]
- Miclo, L. (2008). On absorbtion [sic] times and Dirichlet
eigenvalues. Preprint. [
http://hal.archives-ouvertes.fr/hal-00270958/fr/]
-----
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.
Summary:
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)mathstat.yorku.ca)
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: summer_school@math.carleton.ca
|
|
