Syllabus
Basic notions and methods
- events, expected value and its linearity
- conditional probability, Bayes' rule
Basic inequalities and estimates
- Markov's a Chebyshev's inequality
- Chernoff-type estimates
Probabilistic method
- basic method and alteration method
- Lovász local lemma
Advanced techniques
- balls and bins model, basic estimates and applications
- Markov chains, stationary distribution
- basic continuous distributions as limits of discrete ones, properties and applications
Annotation
Probabilistic techniques are a major tool of discrete mathematics, they are also frequently used in design and analysis of algorithms and other areas of computer science. The lecture introduces basic notions, methods, and estimates and illustrates them on examples from computer science and discrete mathematics.