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), Computer Systems Modelling (Part II), 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 book

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