Loading...
Please wait, while we are loading the content...
CS265/CME309: Randomized Algorithms and Probabilistic Analysis Lecture #13: Introduction to Markov Chains, and a Randomized Algorithms for 2-SAT
| Content Provider | Semantic Scholar |
|---|---|
| Author | Valiant, Gregory |
| Copyright Year | 2019 |
| Abstract | The formal development of the theory of Markov chains was initially motivated by Markov’s observation that sequences of dependent events often exhibited similar sorts of concentration in their long-term behavior, as sequences of independent events. Specifically, Markov examined the statistics of word frequencies (and vowel/consonant frequencies) in Pushkin’s novel Eugene Onegin, and found that, for example, the statistics of these frequencies in different parts of the novel were all very similar. This would be expected if words were chosen independently; however, language has extremely strong dependencies—the next word is very dependent on the previous words. How can we model such dependencies, and how can we understand the long-term behavior of these processes? |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://theory.stanford.edu/~valiant/teaching/CS265/lectureNotes/l13.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
