Next: Programming in Java Up: Lent Term 2008: Part Previous: Lent Term 2008: Part   Contents

## Probability

This course is taken by Part IA (50% Option) students.

Lecturer: Dr F.H. King

No. of lectures: 12

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.

• 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