



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
Recommended reading
* Grimmett, G. & Welsh, D. (1986). Probability: an introduction. Oxford University Press.




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