Probability (50% option only)

Lecturer: Dr F.H. King (fhk1@cl.cam.ac.uk)

No. of lectures: 12

This course is a prerequisite for Introduction to Security (Part IB), Information Theory and Coding (Part II) and Neural Computing (Part II).

Aims

The principal aim of this course is to provide a foundation course in Probability with particular emphasis on discrete distributions. A secondary aim is to provide a somewhat formal approach to the subject but one which is accessible to those with single subject A-level Mathematics.

Lectures

• Single random variable. Chance phenomena, discrete versus continuous. Probability in Computer Science. Experiments. Need for a probability calculus. Random variables. P(X = r) notation. Probability models. Elementary events. Sample space. Relationship to set theory. Probability axioms. Addition theorem. Conditional probability.

• Two or more random variables. Independence. Distinguishability. Multiplication theorem. Uniform distribution. Array diagrams. Event trees. Bayes's theorem. Combinatorial numbers. Pascal's triangle. Binomial theorem.

• Discrete distributions. Uniform distribution. Triangular distribution. Binomial distribution. Trinomial distribution. Multinomial distribution. Expectation or mean.

• Means and variances. Derived random variables. Variance and standard deviation. Geometric distribution. Poisson distribution. Revision of summation (double-sigma sign). Mean and variance when there are two or more random variables. Independence and covariance.

• Correlation. Correlation coefficient. Complete positive correlation. Complete negative correlation. Means and variances of particular distributions. A polynomial with probabilities as coefficients.

• Probability generating functions. Generating functions. Means and variances of distributions revisited. Application of generating functions to P(X + Y = t).

• Difference equations. General introduction to linear, second-order difference equations with constant coefficients. How these equations are found in Probability. How to solve both homogeneous and inhomogeneous difference equations.

• Stochastic processes. Random walks, recurrent versus transient. Gambler's ruin, absorbing barriers, probability of winning and losing, expected length of a game.

• Continuous distributions. Continuous probability models. Probability density functions. Expectation and variance. Uniform distribution. Poisson distribution. Negative exponential distribution.

• Bivariate distributions. Normal distribution. The central limit theorem. Bivariate distributions. Illustrations.

• Transforming probability density functions. Revision of integration by substitution. Application to probability density functions. Transforming a uniform distribution. Illustrations.

• Transforming bivariate probability density functions. Transforming a Uniform distribution into a Normal distribution using Excel. Revision of integration with two independent variables. Jacobians. Application to bivariate probability density functions. The Box-Muller transformation.

Objectives

At the end of the course students should

• have some feeling for Probability to the extent that they can recognise which of the techniques that have been covered in the course might be appropriate in given circumstances

• have some appreciation of the assumptions that need to be made when a particular technique is used or when a particular distribution may apply

Recommended books

Grimmett, G. & Welsh, D. (1986). Probability: an Introduction. Oxford University Press.