Discrete Probability Theory for Computer Science
Overview
The course ends by continuing the introduction to discrete probability theory that was started in Computer Science 251. Results that are useful for the average-case analysis of algorithms, and the analysis of randomized algorithms, will be emphasized — and examples from computer science will be given.
This material will be covered in lectures on November 3 – 26 and in tutorials on November 16 – December 3.
Supplemental Material
You should not need any reference material, for this, that is not provided on the course web site. However, the following book is an excellent reference for the material on discrete probability theory that is included in this course.
- D. Stirzaker, Probability and Random Variables:
A Beginner’s Guide
Cambridge University Press, 1999
It is freely available to students at the University of Calgary, as an ebook, through the university library. This sentence is a link to the ebook.
Lecture #19: Reintroduction to Discrete Probability Theory (Tuesday, November 3)
Why This is Included
Once again, you have to start somewhere! This lecture introduces sample spaces and probability distributions, which will be used to model and analyze experiments, for the rest of this course.
Almost everything in this lecture should be a review of material that was introduced in a prerequisite for this course — but an example from computer science, and a small number of technical results, will likely be material that students have not seen already.
Preparatory Viewing and Reading
- Reintroduction to Discrete Probability Theory [ Video: 25:12 ] [ PDF Slides ]
- Reintroduction to Discrete Probability Theory — Key Concepts [ PDF ]
Lecture Presentation
Tutorial #14: Reintroduction to Discrete Probability Theory (Monday, November 16 and Tuesday, November 17)
This exercise concerns material from Lecture #19. Please read and try to solve the problems on this exercise before attending the tutorial where it is discussed.
Lecture #20: Random Variables and Expectation (Thursday, November 5)
Why This is Included
There is often a numerical value, associated with an experiment, whose value we wish to know. Indeed, computing (or estimating, or bounding) this value may be the main reason to consider the experiment at all. This lecture introduces notation and some results that are needed for this.
While random variables were introduced in a prerequisite course, the expected value of a random variable, and its properties, might be new.
Preparatory Viewing and Reading
- Random Variables and Expectation [ Video: 15:32 ] [ PDF Slides ]
- Random Variables and Expectation — Key Concepts [ PDF ]
Supplemental Material
- What about Countably Infinite Sample Spaces? [ PDF ]
Lecture Presentation
Tutorial #15: Random Variables and Expectation (Wednesday, November 18 and Thursday, November 19
This exercise concerns material from Lecture #20. Please read and try to solve the problems on this exercise before attending the tutorial where it is discussed.
Lecture #21: Tail Bounds (Tuesday, November 17)
Why This is Included
As noted above, there is often a numerical value, associated with an experiment, whose value we wish to know about. This can be modelled using a random variable whose expected value can be computed or bounded.
We might also be interested in the probability that this random variable’s value is far away from its expected value — or is above (or below) a given threshold. This lecture includes notation and results that can often be used to compute or bound this kind of probability.
Preparatory Viewing and Reading
- Tail Bounds [ Video: 26:31 ] [ PDF Slides ]
Supplemental Material
- Proofs of Claims [ PDF ]
Lecture #22: Application — The Analysis of Algorithms (Thursday, November 19)
Why This is Included
While the worst-case analysis of an algorithm is often important, this might not describe how the algorithm behaves “most of the time“ — and this might be what someone is most interested in, when they want to make a choice between algorithms.
It is sometimes possible to produce algorithms that are simpler or (at least slightly) faster, than would otherwise be the case, if these algorithms are allowed to make random choices.
This lecture describes how probability theory can be applied to perform an average-case analysis of an algorithm, to understand how it behaves in practice. It also introduces several kinds of randomized algorithms, including algorithms that can fail (in limited ways) that have been studied and used.
Lecture Presentation
- Application: The Analysis of Algorithms [ Video:22:39 ] [ PDF Slides ]
Lecture #23: Classical Probability Distributions (Tuesday, November 24)
Why This is Included
“Classical” probability distributions arise when probability theory is being used to solve problems, over and over again. However, the language used in an application area might not be the language used in a textbook on probability and statistics, so these distributions might appear in a somewhat “disguised” form. If you are already familiar with these classical probability distributions then you will, ideally, recognize them — so that you can look for and make use of helpful material about these classical distributions in the “probability theory” literature.
Note: For the purposes of this course, this is “for interest only:” students will not be examined on this material in CPSC 351.
Preparatory Viewing and Reading
- Classical Probability Distributions [ Video: 14:27 ] [ PDF Slides ]
