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

Lecture

Markov Chains and Algorithm Applications

In course

COM-516: Markov chains and algorithmic applications

The study of random walks finds many applications in computer science and communications. The goal of the course is to get familiar with the theory of random walks, and to get an overview of some applications of this theory to problems of interest in commu ...

Description

This lecture covers the application of Markov chains in algorithms, focusing on formal algorithms by Propp & Wilson. It explains the generation of chains, starting times, and checking for coalescence. The lecture also discusses theorems by Propp & Wilson guaranteeing good representations.

Official source

Related concepts (16)

Markov chain

A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happens next depends only on the state of affairs now." A countably infinite sequence, in which the chain moves state at discrete time steps, gives a discrete-time Markov chain (DTMC). A continuous-time process is called a continuous-time Markov chain (CTMC).

Generation

A generation refers to all of the people born and living at about the same time, regarded collectively. It can also be described as, "the average period, generally considered to be about 20–⁠30 years, during which children are born and grow up, become adults, and begin to have children." In kinship terminology, it is a structural term designating the parent-child relationship. It is known as biogenesis, reproduction, or procreation in the biological sciences.

Greatest Generation

The Greatest Generation, also known as the G.I. Generation and the World War II generation, is the Western demographic cohort following the Lost Generation and preceding the Silent Generation. The generation is generally defined as people born from 1901 to 1927. They were shaped by the Great Depression and were the primary generation composing the enlisted forces in World War II. Most people of the Greatest Generation are the parents of the Silent Generation and Baby Boomers, and, in turn, were the children of the Lost Generation.

Hidden Markov model

A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it — with unobservable ("hidden") states. As part of the definition, HMM requires that there be an observable process whose outcomes are "influenced" by the outcomes of in a known way.

Silent Generation

The Silent Generation, also known as the Traditionalist Generation, is the Western demographic cohort following the Greatest Generation and preceding the baby boomers. The generation is generally defined as people born from 1928 to 1945. By this definition and U.S. Census data, there were 23 million Silents in the United States as of 2019. In the United States, the Great Depression of the 1930s and World War II in the early-to-mid 1940s caused people to have fewer children and as a result, the generation is comparatively small.

Related lectures (35)

Markov Chains and Algorithm Applications

Covers the application of Markov chains and algorithms for function optimization and graph colorings.

Markov Chains and Applications

Explores Markov chains, their properties, and algorithmic applications, emphasizing information quantification and state monotonicity.

Generation and Recombination

Explores the fundamental concepts of generation and recombination in semiconductors for photovoltaic devices.

Hidden Markov Models: Primer

Introduces Hidden Markov Models, explaining the basic problems and algorithms like Forward-Backward, Viterbi, and Baum-Welch, with a focus on Expectation-Maximization.