Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Concentration Inequalities: Hoeffding's Inequality

In course

COM-417: Advanced probability and applications

In this course, various aspects of probability theory are considered. The first part covers the main theorems in the field (law of large numbers, central limit theorem), while the second part focuses on the theory of martingales and concentration inequalit ...

Description

This lecture covers concentration inequalities, focusing on Hoeffding's inequality. It explains the concept using sequences of independent and integrable random variables, discussing how the probability tends to zero as the sample size increases. The lecture also delves into the proof of Hoeffding's inequality and its consequences, such as the strong law of large numbers and Chebyshev's inequality.

Instructors (2)

Olivier Lévêque

Olivier Lévêque was born in Switzerland in 1971. He received the physics diploma from EPFL in 1995 and completed his PhD in mathematics at EPFL in 2001. Since then, he has been with the Laboratory of Information Theory at EPFL. He spent the academical year 2005-2006 at the Electrical Engineering Department of Stanford University, where he was appointed as lecturer. His research interests include stochastic analysis, random matrices, wireless communications and information theory.

Yanina Yurina Shkel

Official source

Ontological neighbourhood

Statistics

Statistical inference: Mathematical statistics

Related concepts (32)

Economic inequality

Economic inequality is an umbrella term for a) income inequality or distribution of income (how the total sum of money paid to people is distributed among them), b) wealth inequality or distribution of wealth (how the total sum of wealth owned by people is distributed among the owners), and c) consumption inequality (how the total sum of money spent by people is distributed among the spenders).

Random variable

A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. The term 'random variable' can be misleading as it is not actually random nor a variable, but rather it is a function from possible outcomes (e.g., the possible upper sides of a flipped coin such as heads and tails ) in a sample space (e.g., the set ) to a measurable space (e.g., in which 1 corresponding to and −1 corresponding to ), often to the real numbers.

Convergence of random variables

In probability theory, there exist several different notions of convergence of random variables. The convergence of sequences of random variables to some limit random variable is an important concept in probability theory, and its applications to statistics and stochastic processes. The same concepts are known in more general mathematics as stochastic convergence and they formalize the idea that a sequence of essentially random or unpredictable events can sometimes be expected to settle down into a behavior that is essentially unchanging when items far enough into the sequence are studied.

Concentration inequality

In probability theory, concentration inequalities provide bounds on how a random variable deviates from some value (typically, its expected value). The law of large numbers of classical probability theory states that sums of independent random variables are, under very mild conditions, close to their expectation with a large probability. Such sums are the most basic examples of random variables concentrated around their mean. Recent results show that such behavior is shared by other functions of independent random variables.

International inequality

International inequality refers to inequality between countries, as compared to global inequality, which is inequality between people across countries. International inequality research has primarily been concentrated on the rise of international income inequality, but other aspects include educational and health inequality, as well as differences in medical access. Reducing inequality within and among countries is the 10th goal of the UN Sustainable Development Goals and ensuring that no one is left behind is central to achieving them.

Related lectures (29)

McDiarmid's Inequality: Proof and Applications

Covers McDiarmid's inequality, providing concentration bounds for functions of independent random variables.

Uniform Integrability and Convergence

Explores uniform integrability, convergence theorems, and the importance of bounded sequences in understanding the convergence of random variables.

Probability and Statistics: Fundamental Theorems

Explores fundamental theorems in probability and statistics, joint probability laws, and marginal distributions.

Continuous Random Variables

Explores continuous random variables, density functions, joint variables, independence, and conditional densities.

Convergence in Law: Theorem and Proof