Probability

Course information (under construction)

This is the very beginnings of a home page of information that will be provided for Richard Weber's course of 24 lectures to first year Cambridge mathematics students, starting January 17, 2014. This material is provided for students, supervisors (and others) to freely use in connection with this course.

Random walk simulated by 100 coin tosses

Click above for an interactive demo.

Course notes

The course closely follows the schedules.

These notes are under construction and will be available later. An initial outline appears at the end of this page. The notes will include:

Table of Contents
Schedules and learning outcomes
Lectures 1 – 24
Appendices
Index

The notes have 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.

If you think you find a mistake in these notes, check that you have the most recent copy (as I may have already made a correction.) Otherwise, please let me know and I will incorporate that correction into the notes.

Here also are the overhead slides that I sometimes used in lectures.

Course Blog

There is a course blog in which I am writing a few comments after each lecture: to emphasize an idea, give a sidebar, correction (!), or answer an interesting question (that perhaps a student sends to me in email).

Comments, Discussion and Questions

You can comment or ask questions on the discussion page, and also at the end of each of the blog posts. I expect some good contributions. I will endeavour to answer questions. When you comment, you can do this anonymously if you wish. Just give any name and leave the email address box blank.

You can also send me email with questions, suggestions or if you think you have discovered a mistake in the notes.

Examples sheets

There are 4 examples sheets, each containing about X questions, as well as 3 or 4 "extra" optional questions. The extra questions are interesting and off the well-beaten path of questions that are typical for an introductory Probability course. You should receive a supervision on each examples sheet.

I will be revising the sheets with new questions for 2014. These are the 2013 sheets:

Example sheet 1 (for Lectures 1 – 6)
Example sheet 2 (for Lectures 7 – 12)
Example sheet 3 (for Lectures 11 – 18)
Example sheet 4 (for Lectures 19 – 24)

Feedback

This year's course will finish on day 12 March 2014. The written feedback questionnaire has been completed by __ students, and a further __ have completed the electronic form. 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 should be able these books in libraries around Cambridge. Clicking on the title link will show you where the book can be found.

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.

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 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 Basics
1.1 What is probability?
1.2 Classical probability
1.3 Sample space and events
1.4 Equalizations in random walk
1.4.0.1 The arcsine law.
2 Counting
2.1 Combinatorial analysis
2.2 Sampling with or without replacement
2.3 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
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.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
7 Discrete random variables
7.1 Continuity of $P$
7.2 Discrete random variables
7.3 Expectation
7.3.0.1 Poisson.
7.3.0.2 Binomial.
7.4 Function of a random variable
8 Further functions of random variables
8.1 Expectation of sum is sum of expectations
8.2 Variance
8.2.0.1 Poisson.
8.2.0.2 Binomial.
8.2.0.3 Geometric.
8.3 Indicator functions
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
10 Inequalities
10.1 Jensen's inequality
10.2 AM-GM inequality
10.3 Cauchy-Schwarz inequality
10.4 Covariance and correlation
10.5 Markov inequality
10.6 Surprise and entropy
11 Weak law of large numbers
11.1 Chebyshev inequality
11.2 Weak law of large numbers
11.2.0.2 Strong law of large numbers
11.3 Probabilistic proof of Weierstrass approximation theorem
12 Probability generating functions
12.1 Probability generating function
12.2 Combinatorial applications
12.2.0.1 Tilings.
12.2.0.2 Dyke words.
12.2.0.3 Random matrices.
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
14.3.1 Alternative derivation
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
15.5 Ballot theorem
16 Continuous random variables
16.1 Continuous random variables
16.2 Uniform distribution
16.3 Exponential distribution
16.4 Distribution of a function of a random variable
17 Functions of a continuous random variable
17.1 Expectation
17.2 Stochastic ordering of random variables
17.3 Variance
17.4 Benford's law
18 Jointly distributed random variables
18.1 Jointly distributed random variables
18.2 Geometric probability
18.3 Bertrand's paradox
19 Normal distribution
19.1 Normal distribution
19.2 Mode, median and sample mean
19.3 Order statistics, distribution of maximum of minimum
20 Transformations of random variables
20.1 Transformation of Random Variables
20.2 Convolution
20.3 Cauchy distribution
21 More on transformations of random variables
21.1 What happens if the mapping is not 1-1?
22 Moment generating functions
22.1 Moment generating functions
22.2 Gamma distribution
22.3 Moment generating function of normal distribution
23 Multivariate normal distribution
23.1 Multivariate normal distribution
23.2 Bivariate normal
23.3 Multivariate moment generating function
24 The central limit theorem
24.1 Central limit theorem
24.2 Buffon's needle

Index

A Problem solving strategies

B Entertainments (to eventually be inserted above)
B.0.1 Kelly criterion
B.0.2 Beta distribution
B.0.3 Allais paradox
B.0.4 Two envelopes problem
B.0.5 Parrondo's paradox
B.0.6 Brazil nut effect
B.0.7 Inspection paradox

C Credits (sources of some of the material in these notes)

Probability (under construction)