Applications of the Probabilistic MethodModule description #40978 / Version 1
- 6 CP
- Oral exam
- Graded
- Winter and summer semester
- English
This module description is not valid in the current semester (Winter semester 2026/27).
| Module / Version | #40978 / #1 |
|---|---|
| Validity | Summer semester 2020 – Summer semester 2022 |
| Available language(s) | English |
| Credit points | 6 |
| Person responsible for the module | Schaefer, Rafael |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | English |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Telekommunikationssysteme |
| Academic chair | 34331900 FG Informationstheorie und deren Anwendungen |
Contact
| Office | HFT 6 |
|---|---|
| Contact person | Günlü, Onur |
| E-mail address | rafael.schaefer@tu-berlin.de |
| Website | http://www.commit.tu-berlin.de/menue/lehre/parameter/en/ |
Learning outcomes
After completing the module the students will have a solid understanding of the probabilistic method and its applications in various information systems including analyzing randomized algorithms used in information theory, coding theory, information and differential privacy, machine learning, wireless communications, gambling, and data systems. They will get familiar with the current literature in the field and will be able to analyze, apply, and develop probabilistic inequalities as a proof technique to show the existence (and sometimes construction) of randomized algorithms that achieve a claimed performance in various network topologies.
Content
This course aims to expose students to powerful tools and ideas from probability theory that are not commonly covered in undergraduate probability courses or graduate courses on stochastic processes. The focus of the lecture will not be on randomized algorithms, but on the most recent applications of probabilistic methods in hot topics!
The course begins by a number of examples to motivate probabilistic thinking. We then discuss probability inequalities with an emphasis on advanced versions of Chernoff bounds (both the additive and multiplicative forms). Applications of these bounds in Information Theory, Information Security, and Machine Learning will be extensively discussed. Then, we introduce martingales that allow us to obtain more powerful concentration inequalities than Chernoff bounds. Applications of martingales in Gambling, (Polar) Coding Theory used in 5G, Hypothesis Testing, and DNA Pattern Matching will be given as examples. Next, we talk about “Balls into bins” and the Poisson approximation method. Finally, we plan to go into the details of the probabilistic method such as the basic counting argument, the expectation argument, the second moment method, and the Lovász local lemma.
Previous knowledge expected
- A course on probability theory (although a brief recap will be given at the beginning)
The course begins by a number of examples to motivate probabilistic thinking. We then discuss probability inequalities with an emphasis on advanced versions of Chernoff bounds (both the additive and multiplicative forms). Applications of these bounds in Information Theory, Information Security, and Machine Learning will be extensively discussed. Then, we introduce martingales that allow us to obtain more powerful concentration inequalities than Chernoff bounds. Applications of martingales in Gambling, (Polar) Coding Theory used in 5G, Hypothesis Testing, and DNA Pattern Matching will be given as examples. Next, we talk about “Balls into bins” and the Poisson approximation method. Finally, we plan to go into the details of the probabilistic method such as the basic counting argument, the expectation argument, the second moment method, and the Lovász local lemma.
Previous knowledge expected
- A course on probability theory (although a brief recap will be given at the beginning)
Module components
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Applications of the Probabilistic Method (Lecture)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 3 h | 45 h |
| Pre/post processing | 15 | 4 h | 60 h |
| 105 h | |||
Applications of the Probabilistic Method (Exercise)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Attendance | 15 | 1 h | 15 h |
| Pre/post processing | 15 | 4 h | 60 h |
| 75 h | |||
The workload of the module adds up to 180 hours. The module therefore comprises 6 credit points.
Description of teaching and learning methods
The module consists of conventional frontal teaching in class using slides and blackboard, developing theoretical and mathematical concepts and an oral examination.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Prerequisite for participation to courses are a mathematical background at the level of beginning MS students in Electrical Engineering and an undergraduate level background in probability theory.
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | English, German |
| Duration/Extent | 30 minutes |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Winter and summer semester.
Maximum number of participants
The maximum capacity of participants is 40.
Registration procedures
Course teaching and organization is supported by an ISIS course. Module examination enrollment is done via QISPOS.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
- M. Mitzenmacher, E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
- N. Alon, J. H. Spencer, The probabilistic method. John Wiley & Sons, 2004.
- R. Motwani, P. Raghavan, Randomized algorithms. Cambridge University Press, 1995.
Assigned programs
This module is not used in any program.
Miscellaneous
Verwendbarkeit: Studiengebiete:
Kommunikationssysteme und Informationssysteme
WiIng
Kommunikationssysteme und Informationssysteme
WiIng