MA3B4 Probability: Structures and Examples

Introductory description

This is a new second year module that is intended as a bridge between first year 'introduction to probability' type modules and third year probability modules. It emphasises the practical application of probabilistic theorems in particular examples.

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

1. Recap of basic probability (independence, expectations, variance, correlation and correlation inequalities) and motivating examples

2. The weak law of large numbers

3. Notions of convergence in probability

4. Borel—Cantelli lemma and strong law of large numbers

5. Simple large deviations estimates

6. Shannon entropy and some applications to combinatorics and coding theory

7. The central limit theorem (CLT): proof of the de Moivre-Laplace CLT via by-hand computation and Stirling formula and introduction to the Lindeberg exchange principle

8. Poisson random variables and convergence

9. Examples. This will constitute a large part of the module, to demonstrate both the applications of the above theoretical principles and to develop computational skills. Examples will be drawn from combinatorial probability (random graphs, random permutations), stochastic processes (e.g. random walks, Gambler’s ruin) statistical mechanics, information theory

Learning outcomes

By the end of the module, students should be able to:

• Familiarise with the notions of probabilistic convergence
• Main probabilistic inequalities and their applications to functions of long strings of i.i.d. random variables, giving proofs of the weak law of large numbers under various hypothesis and also associated large-deviations inequalities
• Apply those results to concrete models in combinatorics, coding theory, statistical mechanics, simple cases of random walks and possibly examples from other fields of pure maths (permutations and groups or analysis) where randomness is present or probabilistic tools become handy.
• State the central limit theorem, and understand the main ideas in one of its proofs for finite-valued random variables.
• State Poisson convergence and highlight the dichotomy between central limit behaviour vs Poisson.

Subject specific skills

Understand the basic methods of rigorous probability such as the weak law of large numbers and the central limit theorem, and be able to apply these techniques in examples.

Transferable skills

Understand some of the applications of the techniques in this module to coding theory, combinatorics and statistical mechanics.