4 ms·
Reversible Markov Chains and Random Walks on Graphs (free ebook)
- carterschonwald 17y agoThis is a really great book, my randomized algorithms class last year reference it last year. The main way you want to use these techniques is to show that a simple algorithm fueled by some bit supply of randomness (at least at the first time step to initialize some protocol variable) will then at some point in time hit a ``good'' state with high probability, and then you want to show that this convergence happens very quickly. Off the top of my head, i can't think of any slick examples, but if you want to do clever algorithmic hacking, this is the sort of math to know!
- pageman 17y ago1.41 says the number of shuffles is is from 8-205 shuffles while this paper: http://www.dartmouth.edu/~chance/course/topics/winning_number.html http://www.dartmouth.edu/~chance/course/topics/winning_numbe... says it's 7 shuffles. Anybody have an explanation? Maybe its apples vs. oranges?