Probability

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.

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]

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