## Course notes

Here are notes. I aim to make each lecture a self-contained unit on a topic, with notes of four A4 pages. These notes are from the 2014 course and I may make some small changes as the course progresses. An initial outline appears at the end of this page.
The notes contain hyperlinks. If you click on an entry in the table of contents, or on a page number in the Index, you be taken to the appropriate page. Read on page i my thoughts on Printed notes, good or bad?

If you think you find a mistake in the notes, check that you have the most recent copy (in case a correction has already been made). Otherwise, please let me know and I will make the correction.

## Course Blog

In the course blog I will be writing a few comments after each lecture: to emphasize an idea, answer an interesting question (that perhaps a student sends to me in email or asks in lecture), or include something such as an annimation like this.
Click below for an interactive *Mathematica* demo. (You must have the free Wolfram CDF Player installed in your browser.)

**Random walk simulated by 100 fair coin tosses **

## Examples sheets

You should receive a supervision on each of the 4 examples sheets (which you can download from links at the right). Each contains about 12 fairly straightforward Exercises, 2-4 more challenging and/or lengthy Problems, and also a few Puzzles. Please work on all the Exercises and Problems. The Puzzles are for enthusiasts, and might be fun to talk about in supervision if you have done everything else. Some of the Problems and Puzzles are a bit off the well-beaten path of questions that are typical for an introductory Probability course.

## Feedback

The course finishes on 11 March 2015. The feedback questionnaire has been completed by 118 students. If you have not yet given feedback you can do so using my equivalent on-line form. This will be sent to my email anonymously. After reading the responses, I will forward them to the Faculty Office.

## Past exam questions

Here is single fille of all the tripos examination questions on Probability from 2001 to last June.

## Recommended books and notes

You can find these books in libraries around Cambridge. Clicking on the title link will show you where the book can be found. [*However, there is presently something weird about the LibrarySearch site - sometimes, using Chrome browser you will be taken to the LibrarySearch home page, not the specific book information page. If that happens, try refreshing your browser.*]

**Feller, W.**, An Introduction to Probability Theory and its Applications, Vol. I. Wiley 1968. (Useful for all parts of the course.) ISBN 0471257087. This is the book I bought and used when I was a IA student in 1971.

**† Grimmett, G. and Welsh, D.**, Probability: An Introduction, Oxford 1986. ISBN 0198532644. This has everything that is in the course.

**† Ross, S.**, A First Course in Probability. Prentice Hall, 2009. ISBN 0136079091. This is popular and clearly written book (used for many courses in the U.S.)

**Stirzaker, D. R.**, Elementary Probability. CUP, 1994/2003. ISBN 0521421837.

See also these nice notes

- Frank Kelly's 1996 course (notes taken by Paul Metcalfe, a student) These do contain a few typos.

- Doug Kennedy's course notes

There are also some very good Wikipedia pages on many of the topics we study. For example, you could read more about Pascal's solution to the Problem of points, mentioned in Lecture 1.

The lecturer for Probability IA when I did the course in 1971 was Geoff Eagleson. He made the subject fun and this set the direction for my primary mathematical focus. You can see from his current web page that a knowledge of Probability is a good preparation for management consulting. We have been in touch by email recently and he offered the following as a motiviation to you for studying this year's course:

My background in probability theory has helped in management consulting. A training in mathematics prepares one to be precise with language, accurate in arguments and able to see structure in chaos. These skills are incredibly useful to the consultant working with organisations where loose language, sloppy arguments and chaos reign supreme.

## Other resources and further reading

Charles Grinstead and Laurie Snell Introduction to Probability Second edition, 1997 (freely available to download). This book is also easy to read. The authors have good insight and you will find some gems in this book.

David Spiegelhalter is Cambridge's *Winton Professor for the Public Understanding of Risk*. He has a web site called Understanding Uncertainty. It is about chance, risk, luck, uncertainty and probability --- it aims to educate the public about things like coincidences.

Frederick Mosteller, 50 Challenging Problems in Probability, with Solutions, 1987. This is a classic book which anyone who is interested in probability will enjoy. ISBN 0486653552.

Peter Winkler, Mathematical Mind Benders, 2007. This is book of high quality mathematical puzzles, many of which are based on probability. It includes the "Evening out the Gumdrops" puzzle that I discuss in my Markov Chains lectures, and lots of other great problems. He has an earlier book also, Mathematical Puzzles: a Connoisseur's Collection, 2003.

David Aldous has an interesting page of his reviews of many non-technical books related to probability. You might enjoy reading his posting: Presenting probability via math puzzles is harmful.

## Schedules

**Basic concepts**

Classical probability, equally likely outcomes. Combinatorial analysis, permutations and combinations.
Stirling’s formula (asymptotics for log n! proved). [3]

**Axiomatic approach**

Axioms (countable case). Probability spaces. Inclusion-exclusion formula. Continuity and subadditivity of probability measures. Independence. Binomial, Poisson and geometric distributions. Relation between Poisson and binomial distributions. Conditional probability, Bayes's formula. Examples, including Simpson’s paradox. [5]

**Discrete random variables**

Expectation. Functions of a random variable, indicator function, variance, standard deviation. Covariance, independence of random variables. Generating functions: sums of independent random variables, random sum formula, moments. Conditional expectation. Random walks: gambler's ruin, recurrence relations. Diﬀerence equations and their solution. Mean time to absorption. Branching processes: generating functions and extinction probability. Combinatorial applications of generating functions. [7]

**Continuous random variables**

Distributions and density functions. Expectations; expectation of a function of a random variable.
Uniform, normal and exponential random variables. Memoryless property of exponential distribution.
Joint distributions: transformation of random variables (including Jacobians), examples. Simulation: generating continuous random variables, independent normal random variables. Geometrical probability: Bertrand's paradox, Buffon's needle. Correlation coeﬃcient, bivariate normal random variables. [6]

**Inequalities and limits**

Markov’s inequality, Chebyshev’s inequality. Weak law of large numbers. Convexity: Jensen's inequality for general random variables, AM/GM inequality. Moment generating functions and statement (no proof) of continuity theorem. Statement of central limit theorem and sketch of proof. Examples, including sampling. [3]

## Contents

About these notes.

Schedules

Learning outcomes

1 **Classical probability**

1.1 Diverse notions of `probability'

1.2 Classical probability

1.3 Sample space and events

1.4 Equalizations in random walk

2 **Combinatorial analysis**

2.1 Counting

2.2 Sampling with or without replacement

2.2.0.1 Remarks.

2.3 Sampling with or without regard to ordering

2.4 Four cases of enumerative combinatorics

3 **Stirling's formula**

3.1 Multinomial coefficient

3.2 Stirling's formula

3.3 Improved Stirling's formula

4 **Axiomatic approach**

4.1 Axioms of probability

4.2 Boole's inequality

4.3 Inclusion-exclusion formula

**5 Independence**

5.1 Bonferroni's inequalities

5.2 Independence of two events

5.2.0.1 Independent experiments.

5.3 Independence of multiple events

5.4 Important distributions

5.5 Poisson approximation to the binomial

**6 Conditional probability**

6.1 Conditional probability

6.2 Properties of conditional probability

6.3 Law of total probability

6.4 Bayes' formula

6.5 Simpson's paradox

6.5.0.1 Remark.

**7 Discrete random variables**

7.1 Continuity of $P$

7.2 Discrete random variables

7.3 Expectation

7.4 Function of a random variable

7.5 Properties of expectation

**8 Further functions of random variables**

8.1 Expectation of sum is sum of expectations

8.2 Variance

8.2.0.1 Binomial.

8.2.0.2 Poisson.

8.2.0.3 Geometric.

8.3 Indicator random variables

8.4 Reproof of inclusion-exclusion formula

8.5 Zipf's law

**9 Independent random variables**

9.1 Independent random variables

9.2 Variance of a sum

9.3 Efron's dice

9.4 Cycle lengths in a random permutation

9.4.0.1 Names in boxes problem.

**10 Inequalities**

10.1 Jensen's inequality

10.2 AM--GM inequality

10.3 Cauchy-Schwarz inequality

10.4 Covariance and correlation

10.5 Information entropy

**11 Weak law of large numbers**

11.1 Markov inequality

11.2 Chebyshev inequality

11.3 Weak law of large numbers

11.3.0.1 Remark.

11.3.0.2 Strong law of large numbers

11.4 Probabilistic proof of Weierstrass approximation theorem

11.5 Probabilistic proof of Weierstrass approximation theorem

11.6 Benford's law

**12 Probability generating functions**

12.1 Probability generating function

12.2 Combinatorial applications

12.2.0.1 Dyck words.

**13 Conditional expectation**

13.1 Conditional distribution and expectation

13.2 Properties of conditional expectation

13.3 Sums with a random number of terms

13.4 Aggregate loss distribution and VaR

13.5 Conditional entropy

**14 Branching processes**

14.1 Branching processes

14.2 Generating function of a branching process

14.3 Probability of extinction

**15 Random walk and gambler's ruin**

15.1 Random walks

15.2 Gambler's ruin

15.3 Duration of the game

15.4 Use of generating functions in random walk

**16 Continuous random variables**

16.1 Continuous random variables

16.1.0.1 Remark.

16.2 Uniform distribution

16.3 Exponential distribution

16.4 Hazard rate

16.5 Relationships among probability distributions

**17 Functions of a continuous random variable**

17.1 Distribution of a function of a random variable

17.1.0.1 Remarks.

17.2 Expectation

17.3 Stochastic ordering of random variables

17.4 Variance

17.5 Inspection paradox

**18 Jointly distributed random variables**

18.1 Jointly distributed random variables

18.2 Independence of continuous random variables

18.3 Geometric probability

18.4 Bertrand's paradox

18.5 Last arrivals problem

**19 Normal distribution**

19.1 Normal distribution

19.2 Calculations with the normal distribution

19.3 Mode, median and sample mean

19.4 Distribution of order statistics

19.5 Stochastic bin packing

**20 Transformations of random variables**

20.1 Convolution

20.2 Cauchy distribution

**21 Moment generating functions**

21.1 What happens if the mapping is not 1--1?

21.2 Minimum of exponentials is exponential

21.3 Moment generating functions

21.4 Gamma distribution

21.5 Beta distribution

**22 Multivariate normal distribution**

22.1 Moment generating function of normal distribution

22.2 Functions of normal random variables

22.3 Multivariate normal distribution

22.4 Bivariate normal

22.5 Multivariate moment generating function

22.6 Buffon's needle

**23 Central limit theorem
**23.1 Central limit theorem

23.1.0.1 Remarks.

23.2 Normal approximation to the binomial

23.3 Estimating $\pi$ with Buffon's needle

**24 Continuing studies in probability**

24.1 Large deviations

24.2 Chernoff bound

24.3 Random matrices

24.4 Concluding remarks

**Appendices**

A Problem solving strategies

B Fast Fourier transform and p.g.fs

C The Jacobian

D Beta distribution

E Kelly criterion

F Ballot theorem

G Allais paradox

H IB courses in applicable mathematics