We all know that Markov Chains can be used for generating real-looking text (or real-sounding music). I've also heard that Markov Chains has some applications in the image processing, is that true? What are some other uses of MCs in CS?
$\begingroup$
$\endgroup$
13
-
4$\begingroup$ apparently too many to list $\endgroup$– Pratik DeoghareMar 22, 2012 at 16:41
-
2$\begingroup$ This might be better as a CW question since, as @PratikDeoghare points out, there are too many to list. $\endgroup$– SureshMar 22, 2012 at 16:48
-
2$\begingroup$ You mean besides their use to model a rich class of discrete probability distributions? Or do you expect more concrete answers? $\endgroup$– RaphaelMar 22, 2012 at 16:49
-
4$\begingroup$ @Suresh: I'd rather the OP focused the question more. $\endgroup$– RaphaelMar 22, 2012 at 16:49
-
1$\begingroup$ @PratikDeoghare: Yes but people realize it only when they're understanding like you. =) $\endgroup$– GigiliMar 22, 2012 at 16:59
|
Show 8 more comments
4 Answers
$\begingroup$
$\endgroup$
4
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.
-
-
$\begingroup$ Depends on the chain. that's the tricky part. $\endgroup$– SureshMar 22, 2012 at 19:34
-
$\begingroup$ Ya, can't always get small mixing time. Some probability distributions really do take exponential time to sample from... $\endgroup$– AaronMar 22, 2012 at 20:22
-
$\begingroup$ The mixing time is well behaved under suitable regularity conditions. For most non-pathological cases, including those one would typically use in practice, the mixing time is not a big issue. Also, the use of the term random walk in this context is not really merited. It would be better just to say the stationary distribution of the chain is the distribution you want. $\endgroup$ Jan 14, 2013 at 20:21
$\begingroup$
$\endgroup$
1
An important application are Hidden Markov Models which essentially assume the underlying random distribution follows a Markov chain. One exiting application of HMMs is gene prediction in bioinformatics. The task is to consume a long (as in millions of symbols) DNA sequence and predict where important parts (genes) are located. One approach is using a Hidden Markov Model that is trained to model a certain distribution.
A related, but more concise problem is detecting when an unfair die is used in a casino. Assume that the game master switches between fair and unfair dice with a certain probability $p$ after every roll. This can be modelled like this:
[source]
States fair and unfair have emission probabilities for die rolls; in state fair, every number between $1$ and $6$ is emitted with probability $\frac{1}{6}$, in state unfair something different happens. All these probabilities can be trained , either using observed relative counts if we have access to some roll histories (and when which die was used) or using for instance forward-backward algorithm if we have not.
For a given sequence of die rolls, Viterbi algorithm can be used to obtain the most likely underlying path that emits this sequence; from this path, we can read off when the unfair die was (most likely used). If we do this online, we can guess when the unfair die is used and exploit this knowledge.
-
$\begingroup$ Hidden Markov models are also very important for speech recognition. $\endgroup$ Mar 24, 2012 at 20:41
$\begingroup$
$\endgroup$
Markov chains appear everywhere. Why? Because the model is so general: You are interested in a large set of objects, and you can handle local manipulations on these objects, eg. modifying an object slightly to get a new one. You want to study global properties of this set of objects, such as its approximate size. This very natural problem, which is an abstraction of problems in many fields, can be modeled by a random walk on a graph, the nodes of which are the objects of interest. Starting from an arbitrary node, an elementary step is to move to a neighboring node with a certain (say uniform over all neighbors) probability. This very simple elementary step applied many times, results in a wonderful phenomenon- the distribution over the nodes converges to a limiting distribution depending only on the structure of the graph, and not on the arbitrary node we started with. This limiting distribution can tell us a lot about the global properties of the set of objects of interest, such as the size or structure of the graph. The time it takes for convergence, or the "mixing time" is thus of crucial importance for algorithmic and modeling applications. One of the more active fields in probability and theoretical computer science is the analysis of Markov chains for various applications. Many clever and beautiful mathematical tools have been developed to analyze the mixing time in the various cases.
Source: http://www.cs.huji.ac.il/~doria/markovchains.huji2002.html
$\begingroup$
$\endgroup$
In a nutshell, Markov chains are used to model correlated stochastic processes; a broad class of signals. If the value of the signal at any moment can be well approximated by a function of the signal values at a limited number of the the preceding moments, then a Markov model is appropriate.
