# Introduction to Probability

**Principal lecturers:** Prof Mateja Jamnik, Dr Thomas Sauerwald

**Taken by:** Part IA CST

**Term:** Easter

**Hours:** 12

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

**Past exam questions, 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.