Loading...
Please wait, while we are loading the content...
CS265/CME309: Randomized Algorithms and Probabilistic Analysis Lecture #15: Mixing Times, Strong Stationary Times, and Coupling
| Content Provider | Semantic Scholar |
|---|---|
| Author | Valiant, Gregory |
| Copyright Year | 2019 |
| Abstract | Last lecture we discussed stationary distributions, and also saw the Metropolis Algorithm for constructing a Markov chain that has a desired stationary distribution. This prompts the following fundamental question: How long must we run a Markov chain until the state of the chain is close to being drawn from the stationary distribution? The answer corresponds to the notion of mixing time. Before defining the mixing time, we begin by giving a few different definitions of total-variation distance, which will be a natural metric for measuring the distance between distributions. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~valiant/teaching/CS265/lectureNotes/l15.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
