Department of Computer Science and Technology

Course pages 2020–21 (these pages are still being updated)

Introduction to Probability

Principal lecturers: Prof Mateja Jamnik, Dr Thomas Sauerwald
Taken by: Part IA CST
Past exam questions

No. of lectures: 12
Suggested hours of supervisions: 3
This course is a prerequisite for Probability and Computation (Part II).


This course provides an elementary introduction to probability and statistics with applications. Probability theory and the related field of statistical inference provide the foundations for analysing and making sense of data. The focus of this course is to introduce the language and core concepts of probability theory. The course will also cover some applications of statistical inference and algorithms in order to equip students with the ability to represent problems using these concepts and analyse the data within these principles.


Part 1 - Introduction to Probability

  • Introduction. Counting/Combinatorics (revision), Probability Space, Axioms, Union Bound.

  • Conditional probability. Conditional Probabilities and Independence, Bayes’Theorem, Partition Theorem

Part 2 - Discrete Random Variables

  • Random variables. Definition of a Random Variable, Probability Mass Function, Cumulative Distribution, Expectation.

  • Probability distributions. Definition and Properties of Expectation, Variance, different ways of computing them, Examples of important Distributions (Bernoulli, Binomial, Geometric, Poisson), Primer on Continuous Distributions including Normal and Exponential Distributions.

  • Multivariate distributions. Multiple Random Variables, Joint and Marginal Distributions, Independence of Random Variables, Covariance.

Part 3 - Moments and Limit Theorems

  • Introduction. Law of Average, Useful inequalities (Markov and Chebyshef), Weak Law of Large Numbers (including Proof using Chebyshef’s inequality), Examples.

  • Moments and Central Limit Theorem. Introduction to Moments of Random Variables, Central Limit Theorem (Proof using Moment Generating functions), Example.

Part 4 - Applications/Statistics

  • Statistics. Classical Parameter Estimation (Maximum-Likelihood-Estimation), bias, sample mean, sample variance), Examples (Collision-Sampling, Estimating Population Size).

  • Algorithms. Online Algorithms (Secretary Problem, Odd’s Algorithm).


At the end of the course students should

  • understand the basic principles of probability spaces and random variables

  • be able to formulate problems using concepts from probability theory and compute or estimate probabilities

  • be familiar with more advanced concepts such as moments, limit theorems and applications such as parameter estimation

Recommended reading

* Ross, S.M. (2014). A First course in probability. Pearson (9th ed.).

Bertsekas, D.P. & Tsitsiklis, J.N. (2008). Introduction to probability. Athena Scientific.

Grimmett, G. & Welsh, D. (2014). Probability: an Introduction. Oxford University Press (2nd ed.).

Dekking, F.M., et. al. (2005) A modern introduction to probability and statistics. Springer.