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

Lecture

Von Neumann Extractor: Extensions

In course

COM-622: Topics in information-theoretic cryptography

Information-theoretic methods and their application to secrecy & privacy. Perfect information-theoretic secrecy. Randomness extraction & privacy amplification. Secret key generation from common randomness. Measures of information leakage incl. differential ...

Description

This lecture covers the von Neumann Extractor, its extensions, and the analysis of asymptotically optimal extractors for binary i.i.d. sequences. It introduces the concept of extraction rules and proves uniformity for random variables. The lecture also discusses exchangeability of sequences and the law of total probability. Examples are provided to illustrate the concepts presented.

Instructor

Yanina Yurina Shkel

Official source

Ontological neighbourhood

Statistics

Statistical inference: Mathematical statistics

Related concepts (32)

Exchangeable random variables

In statistics, an exchangeable sequence of random variables (also sometimes interchangeable) is a sequence X1, X2, X3, ... (which may be finitely or infinitely long) whose joint probability distribution does not change when the positions in the sequence in which finitely many of them appear are altered. Thus, for example the sequences both have the same joint probability distribution. It is closely related to the use of independent and identically distributed random variables in statistical models.

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.

Distribution of the product of two random variables

A product distribution is a probability distribution constructed as the distribution of the product of random variables having two other known distributions. Given two statistically independent random variables X and Y, the distribution of the random variable Z that is formed as the product is a product distribution. The product distribution is the PDF of the product of sample values. This is not the same as the product of their PDF's yet the concepts are often ambiguously termed as "product of Gaussians".

Complex random variable

In probability theory and statistics, complex random variables are a generalization of real-valued random variables to complex numbers, i.e. the possible values a complex random variable may take are complex numbers. Complex random variables can always be considered as pairs of real random variables: their real and imaginary parts. Therefore, the distribution of one complex random variable may be interpreted as the joint distribution of two real random variables.

Independent and identically distributed random variables

In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is usually abbreviated as i.i.d., iid, or IID. IID was first defined in statistics and finds application in different fields such as data mining and signal processing. Statistics commonly deals with random samples. A random sample can be thought of as a set of objects that are chosen randomly.

Related lectures (38)

Probability and Statistics: Fundamental Theorems

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

Convergence in Law: Theorem and Proof

Explores convergence in law for random variables, including Kolmogorov's theorem and proofs based on probability lemmas.

Probability and Statistics

Delves into probability, statistics, paradoxes, and random variables, showcasing their real-world applications and properties.

Probability and Statistics: Independence and Conditional Probability

Explores independence and conditional probability in probability and statistics, with examples illustrating the concepts and practical applications.

Continuous Random Variables