This course is a prerequisite for Mathematical Methods for Computer Science, and the following Part II courses: Artificial Intelligence II, Computer Systems Modelling, Information Theory and Coding, Computer Vision, Digital Signal Processing.

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.

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.