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

Lecture

Markov Chain Monte Carlo: Sampling High-Dimensional Distributions

In course

MGT-484: Applied probability & stochastic processes

This course focuses on dynamic models of random phenomena, and in particular, the most popular classes of such models: Markov chains and Markov decision processes. We will also study applications in queuing theory, finance, project management, etc. ...

Description

This lecture introduces the concept of Markov Chain Monte Carlo (MCMC) as a powerful algorithm for sampling high-dimensional probability distributions. It covers the Metropolis-Hastings algorithm, detailed balance equations, and practical implementation strategies. The lecture discusses the challenges of sampling from high-dimensional distributions, the advantages of MCMC methods, and their applications in solving optimization problems like the Knapsack Problem and cryptography. Examples include the Ising model and decoding ciphers using MCMC. The instructor emphasizes the importance of understanding the power and pitfalls of MCMC algorithms.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Negar Kiyavash

Official source

Related concepts (32)

Probability distribution

In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon in terms of its sample space and the probabilities of events (subsets of the sample space). For instance, if X is used to denote the outcome of a coin toss ("the experiment"), then the probability distribution of X would take the value 0.5 (1 in 2 or 1/2) for X = heads, and 0.

Combinatorial optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

Cipher

In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. To encipher or encode is to convert information into cipher or code. In common parlance, "cipher" is synonymous with "code", as they are both a set of steps that encrypt a message; however, the concepts are distinct in cryptography, especially classical cryptography.

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.

Markov chain Monte Carlo

In statistics, Markov chain Monte Carlo (MCMC) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as its equilibrium distribution, one can obtain a sample of the desired distribution by recording states from the chain. The more steps that are included, the more closely the distribution of the sample matches the actual desired distribution. Various algorithms exist for constructing chains, including the Metropolis–Hastings algorithm.

Related lectures (51)

Max Entropy and Monte Carlo

Explores max entropy, Shannon's entropy, Lagrange multipliers, and Monte Carlo sampling techniques.

Introduction to Maximum Entropy Inference

Introduces maximum entropy inference for finding optimal probability distributions with minimal extra structure.

Optimization and Simulation: Bayesian Inference

Explores Bayesian inference, knapsack problem, and prediction using Markov Chain Monte Carlo methods.

Probability and Statistics

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

Maximum Likelihood Inference