Skip to content
Technische Universität Berlin Deutsch
Course catalog and module transfer system

Applications of the Probabilistic MethodModule description #40978 / Version 1

← Module page Deutsche Fassung
This module description is not valid in the current semester (Winter semester 2026/27).
Module / Version#40978 / #1
ValiditySummer semester 2020 – Summer semester 2022
Available language(s)English
Credit points6
Person responsible for the moduleSchaefer, Rafael
GradingGraded
Exam formatOral exam
Language(s) of instructionEnglish

Affiliation

FacultyFakultät IV
InstituteInstitut für Telekommunikationssysteme
Academic chair34331900 FG Informationstheorie und deren Anwendungen

Contact

OfficeHFT 6
Contact personGünlü, Onur
E-mail addressrafael.schaefer@tu-berlin.de
Websitehttp://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)

Module components

Compulsory area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Applications of the Probabilistic MethodLecture34331900 L 003 Winter and summer semester[en]3 ISIS
Applications of the Probabilistic MethodExercise34331900 L 004 Winter and summer semester[en]1 ISIS

Workload and credit points

Applications of the Probabilistic Method (Lecture)

Workload descriptionMultiplierHoursTotal
Attendance153 h45 h
Pre/post processing154 h60 h
105 h

Applications of the Probabilistic Method (Exercise)

Workload descriptionMultiplierHoursTotal
Attendance151 h15 h
Pre/post processing154 h60 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

GradingGraded
Exam formatOral exam
LanguageEnglish, German
Duration/Extent30 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