# 21 Lectures on Probability and Random Processes

In the second semester of the academic year 2011-2012 and for reasons unknown, I was asked to teach a course on Probability and Random Processes to second-year Informatics students. (I have been asked why it is that for a second year running, a mathematical physicist is teaching this course. I have no answer.)

At any rate, as this was the last time that the course was given, it was my first and for the foreseeable future also my last time teaching it. Nevertheless it is a topic I find fascinating and very enjoyable and I spent quite a bit of time preparing the lectures, and not wanting this effort to go to waste, I am making the lectures available here to anyone interested.

The files are the very same presentation slides I used in class. They were created with LaTeX's beamer class, with many of the diagrams drawn with PGF/TiKZ or generated with Mathematica. Most photos and some graphics I did borrow (with thanks) from the world wide web — mostly from wikipedia.

The handout mode slides are printed "4 on 1" and with flattened transitions. They are more convenient for printing and to see at a glance the contents of the lecture.

I have tried to give an impression of the topics and examples covered in each lecture, without attempting to generate a proper table of contents.

Enjoy (or endure)!

## Schedule of lectures

1. 18 January 2012 (handout mode)
Introduction and basic notions; outcomes, events; the langugage of set theory: distributivity, De Morgan's; σ-fields
2. 20 January 2012 (handout mode)
Probability as relative frequency; probability measure; Bernoulli trials: fair coins and dice; uniform probability measure; inclusion-exclusion; Boole's inequality; continuity
Birthday problem
3. 25 January 2012 (handout mode)
Conditional probability; multiplication rule; independence
4. 27 January 2012 (handout mode)
Partition rules; conditional partition rule; Bayes's rule
Mendelian genetics
5. 1 February 2012 (handout mode)
Conditional independence; discrete probability distributions; distribution function
Uniform distribution; binomial distribution; the problem of the points; Benford's distribution;
6. 3 February 2012 (handout mode)
Discrete random variables; probability mass function; expectation
Waiting and the geometric distribution; Poisson distribution
7. 8 February 2012 (handout mode)
Functions of a discrete random variable; moment generating function; variance and standard deviation; Approximations: from binomial to Poisson
Bortkiewicz and the Prussian cavalry fatalities
8. 10 February 2012 (handout mode)
Several random variables; joint probability mass functions; marginals; independence; functions of several random variables; linearity of expectation
Bernoulli trials with a random parameter; randomised hats; coupon collector problem
9. 15 February 2012 (handout mode)
Expectation of a product; covariance; correlation; Markov and Chebyshev inequalities; the law of large numbers
10. 17 February 2012 (handout mode)
Continuous random variables; probability density functions; cumulative distribution functions; Borel sets; exponential distribution and lack of memory; expectation
Uniform distribution; normal distribution; exponential distribution;
11. 29 February 2012 (handout mode)
Functions of a continuous random variable; expectation; variance; moment generating functions; standardising the normal distribution; maximum entropy
Gamma distribution; log-normal distributions; standard error
12. 2 March 2012 (handout mode)
Jointly distributed continuous random variables; joint densities; marginals; joint distributions; independence; geometric probability; sums of random variables
Buffon's needle
13. 7 March 2012 (handout mode)
Convolution; independent random variables; Markov, Chebyshev and Chernoff; waiting times and the exponential distribution
14. 9 March 2012 (handout mode)
More approximations; normal limit of binomial and Poisson distributions; sum of i.i.d. random variables; central limit theorem
Rounding errors; astronomical measurements
15. 14 March 2012 (handout mode)
Stochasticity and non-determinism; Markov chains; transition matrix
Gambler's ruin
16. 16 March 2012 (handout mode)
n-step transition matrix; Chapman–Kolmogorov formula; steady state and stationary distributions; regular Markov chains
17. 21 March 2012 (handout mode)
Random walks; probability generating function; conditional expectation; branching processes; hitting times for random walks
Random sums; more Gambler's ruin; Galton–Watson process and extinction of family surnames
18. 23 March 2012 (handout mode)
Random walks on graphs; hitting times; mean return times; independent random walks
19. 28 March 2012 (handout mode)
Continuous-time Markov processes; Counting process; Poisson process; inter-arrival and waiting times; uniqueness of the exponential distribution
20. 30 March 2012 (handout mode)
Further properties of the exponential distribution; birth and death processes; transition rates; steady-state distribution
Single server (M/M/1) queue
21. 4 April 2012 (handout mode)