*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.