direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Module: Applications of Probabilistic Method (40978)


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.

Further Information

Module Components:
Two courses:

VL - Applications of Probabilistic Method
 (3 LP)
UE - 
Applications of Probabilistic Method (3 LP)  

Duration of Module:
One semester
This module is used in the following module lists:

Computer Engineering (Master of Science)
Computer Science (Informatik) (Master of Science)
Elektrotechnik (Master of Science)
Wirtschaftsinformatik / Information Systems Management (Master of Science)

Prerequisite for participation to courses are a mathematical background at the level of an early MSc student in Electrical Engineering and an undergraduate level background in probability theory.
LP = Leistungspunkte/Credits

Module Supporting Material

  • 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.

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe