General information

Instructor: Nicolas Broutin
room 310, McConnell Engineering Building
(514) 398 5485.
Office hours: Mon--Wed 1:30pm to 2:20 pm
Time and Location: Mon and Wed, from 2:35 to 3:55pm in Burnside 1120.

Course description and contents

We intend to go through the core stochastic processes. If time permits, we will talk about more advanced topics. We will try to emphasize the intuition that is underlying the main ideas: the topics will roughly cover:

  • Random walks: evolution, ballot theorems, fluctuations.
  • Discrete time Markov chains: evolution, convergence, hitting time, cover time.
  • Continous time Markov chains.
  • Poisson process and the exponential distribution.
  • Branching processes: the Galton--Watson process, age-dependent processes.
  • Concentration: exponential concentration, martingale methods.
  • Renewal theory.

Textbook

Most of the material can be found in Grimmett and Stirzaker, Probability and Random Processes, OUP, 2001. I will sometimes provide additional hand outs for what is not covered.

Evaluation

About 4 homework assignments (80%) and a final exam (20%).

Lectures

  • Wed. sept 3: Simple random walk I -- Counting methods: Reflection principle, ballot theorem, paths not returning to zero, eventual return to zero and expected number of returns.
  • Mon. sept. 8: Simple random walk II: Arcsine law for last return, arcsine law for sojourn times, probability generating function, moments as derivatives.
  • Wed. sept. 10: Simple random walk III: returns to zero and first return to zero, expected time for first return. Branching processes I: Galton--Watson process, generating function for the number of individuals.
  • Mon. sept. 15: Branching processes II: convergence of the probability generating function, probability of extinction, growth of the number of individuals, connection with random walks (size of the tree/hitting time of -1, expected size of critical trees on the example of binary trees), geometric branching case, expected size of the nth generation given it's positive.
  • Wed. sept. 17: Convergence in distribution, characteristic functions, a bit of complex analysis to compute them, continuity theorem, central limit theorem for i.i.d. random variables.
  • Mon. sept. 22: Strong law of large numbers I. Borel--Cantelli lemmas, zero-th, first and second moment method. (Louigi's lecture)
  • Wed. sept. 24: Strong law of large numbers II. Proof following T. Tao (Louigi's lecture).
  • Mon. sept. 29: Markov chains I. Discrete time Markov chains, transitions, period, irreducibility, stationary distribution.
  • Wed. oct. 1: Markov chains II. Existence/uniqueness of a stationary distribution, total variation distance, coupling, convergence, reversibility, random walks on graphs (hitting time, cover time, mixing time).
  • Mon. oct. 6: Bounds on the mixing time I. Upper and lower bound using hitting times. Random ceneration I. Approximation using a Markov chain, Hardcore model, Markov chain Monte Carlo, Metropolis chain.
  • Wed. oct. 8: Random generation II. Propp--Wilson's coupling from the past, sandwiching technique, Wilson's read-once algorithm.
  • Mon. oct. 13: No class, turkey cooking instead.
  • Wed. oct. 15: Bounds on the mixing time II. reversible Markov chains and electrical networks, bounds using the conductance.
  • Mon. oct. 20: Martingales I. Definition, examples, concentration, Azuma--Hoeffding inequality.
  • Wed. oct. 22: Martingales II. Upcrossing inequality, convergence theorem.
  • Mon. oct. 27: Martingales III. Subadditive lemma, exposure martingales, concentration of bin packing and traveling salesman.
  • Wed. oct. 29: Martingales IV. Stopping times, stopped martingales, Doob's optional stopping theorem, Wald's identity, maximal inequality.
  • Mon. nov. 3: Birth processes I. Poisson process, exponential distribution, birth processes, forward and backward systems of differential equations.
  • Wed. nov. 5: Birth processes II. Explosion of birth processes, memoryless property of the exponential, superposition, characterizations of Poisson processes: arrival times of i.i.d. exponentials, independent increments.
  • Mon. nov. 10: Ergodic theory I. Measure preserving maps, invariant events, Birkhoff's theorem, Kolmogorov's 0-1 law.
  • Wed. nov. 12: Ergodic theory II. Kingman's subadditive ergodic theorem, longest increasing subsequence, bin packing, traveling salesman.
  • Mon. nov. 17: Poisson point process, Poissonization, depoissonization for increasing subsequences.
  • Wed. nov. 19: Branching random walk. Large deviations upper bound, Holder's inequality, Cramer's theorem, maxima in branching random walks.
  • Mon. nov. 24: Large deviations lower bound, statements about more general results.
  • Wed. nov. 27: Balls and bins, load balancing, Poisson limit, power of two choices.

References

  1. R. Durrett. Essentials of Stochastic Processes. Springer, New York, 1999.
  2. W. Feller. An Introduction to Probability Theory and its applications. Third edition. Wiley, New York, 1968.
  3. P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, Cambridge, 2008.
  4. G.R. Grimmett. Percolation. Second edition. Springer, Berlin, 1999.
  5. G.R. Grimmett and D.R. Stirzaker. Probability and Random Processes. Second edition. Oxford University Press, Oxford, 2001.
  6. O. Häggström. Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002.
  7. S. Karlin and H.M. Taylor. A First Course in Stochastic Processes. Second edition. Academic Press, New York, 1975.
  8. S. Karlin and H.M. Taylor. A Second Course in Stochastic Processes. Academic Press, New York, 1981.
  9. A. Klenke. Probability Theory: A Comprehensive Course. Springer, London, 2008.
  10. J.R. Norris. Markov Chains. Cambridge University Press, Cambridge, 1998.
  11. D. Williams. Probability with Martingales. Cambridge University Press, Cambridge, 1991.