skip to primary navigationskip to content

Department of Computer Science and Technology

Part IA CST

 

Course pages 2022–23

Introduction to Probability

Principal lecturers: Prof Mateja Jamnik, Dr Thomas Sauerwald
Taken by: Part IA CST
Term: Easter
Hours: 12
Format: In-person lectures
Suggested hours of supervisions: 3
Prerequisites: Discrete Mathematics
This course is a prerequisite for: Computer Systems Modelling, Randomised Algorithms
Exam: Paper 1 Question 5, 6, 5, 6
Past exam questions, Moodle, timetable

Aims

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.

Lectures

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

Objectives

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. and Tsitsiklis, J.N. (2008). Introduction to probability. Athena Scientific.

Grimmett, G. and 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.