ICTS:31829

Video URL

Using Markov Chains before they mix.

Using Markov Chains before they mix.

(2025). Using Markov Chains before they mix.. SciVideos. https://youtube.com/live/L-L6QTDCE8k

Using Markov Chains before they mix.. SciVideos, May. 12, 2025, https://youtube.com/live/L-L6QTDCE8k 

          @misc{ scivideos_ICTS:31829,
            doi = {},
            url = {https://youtube.com/live/L-L6QTDCE8k},
            author = {},
            keywords = {},
            language = {en},
            title = {Using Markov Chains before they mix.},
            publisher = {},
            year = {2025},
            month = {may},
            note = {ICTS:31829 see, \url{https://scivideos.org/icts-tifr/31829}}
          }
Prasad Raghavendra
Talk numberICTS:31829
Source RepositoryICTS-TIFR

Abstract

Markov chains are among the most popular sampling algorithms both in theory and practice. There is a vast theory on understanding the mixing times of Markov chains. But what if the Markov chain does not mix fast? Can we still use such Markov chains in down-stream applications of sampling, and what theoretical guarantees can we show about these chains? In this talk, we will define a notion of "locally stationary measure" -- which is an analogue of local optima in convex optimization. We will see some generic methods to analyze the structure of distributions that non-mixing Markov chains sample from, along with applications to finding large independent sets in graphs, and finding planted cuts in random graphs. Finally, we will conclude the talk with a set of open questions on locally stationary measures. Based on joint work with Kuikui Liu, Prasad Raghavendra, Amit Rajaraman and David X Wu.