What are the uses of Markov Chains in CS?
Markov Chain Monte-Carlo is a technique for efficiently sampling from a complicated probability distribution. No matter what your (discrete) probability distribution, you can set up a markov chain so that the steady-state distribution of a random walk is the distribution you wish to sample from. You can then approximate this distribution by simulating the random walk on the markov chain. If the markov-chain happens to have small mixing time, then the empirical distribution of your simulation will quickly converge to the steady state distribution, giving you an efficient algorithm for sampling from it.