Moses - Applications of the Probabilistic Method

Display language

To modulepage Generate PDF

Diese Modulbeschreibung gilt nicht im aktuellen Semester.

Die Modulbeschreibung gilt nur für den Zeitraum SoSe 2020 - SoSe 2022.

Module / Version:
#40978 / #1

Validity:
SoSe 2020 - SoSe 2022

Default display language:
English

Module title:
Applications of the Probabilistic Method

Credits:
6

Responsible person:
Schaefer, Rafael

Grading:
benotet

Type of exam:
Mündliche Prüfung

Zugehörigkeit

Faculty:
Fakultät IV

Institute:
Institut für Telekommunikationssysteme

Area of expertise:
34331900 FG Informationstheorie und deren Anwendungen

Prüfungsausschuss:
No information

Kontakt

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)

Module Components

Pflichtgruppe:

All Courses are mandatory.

Course Name	Type	Number	Cycle	Language	SWS	VZ
Applications of the Probabilistic Method	VL	34331900 L 003	WiSe/SoSe	English	3
Applications of the Probabilistic Method	UE	34331900 L 004	WiSe/SoSe	English	1

Workload and Credit Points

Applications of the Probabilistic Method (VL):

Workload description	Multiplier	Hours	Total
Attendance	15.0	3.0h	45.0h
Pre/post processing	15.0	4.0h	60.0h
			105.0h(~4 LP)

Applications of the Probabilistic Method (UE):

Workload description	Multiplier	Hours	Total
Attendance	15.0	1.0h	15.0h
Pre/post processing	15.0	4.0h	60.0h
			75.0h(~3 LP)

The Workload of the module sums up to 180.0 Hours. Therefore the module contains 6 Credits.

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 test application:

This module has no requirements.

Module completion

Grading

graded

Type of exam

Oral exam

Language

German/English

Duration/Extent

30 minutes

Duration of the Module

The following number of semesters is estimated for taking and completing the module:
1 Semester.

This module may be commenced in the following semesters:
Winter- und Sommersemester.

Maximum Number of Participants

The maximum capacity of students is 40.

Registration Procedures

Course teaching and organization is supported by an ISIS course. Module examination enrollment is done via QISPOS.

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 Degree Programs

Semester:

Zeige auch ausgelaufene Studiengänge und StuPOs

This module is used in the following Degree Programs (new System):

	Studiengang / StuPO	StuPOs	Verwendungen	Erste Verwendung	Letzte Verwendung
This module is not used in any degree program.

Miscellaneous

Verwendbarkeit: Studiengebiete: Kommunikationssysteme und Informationssysteme WiIng

Applications of the Probabilistic Method