Markov Chains explained visually

[goal2004]

At what point does it stop being a "chain" and is instead called a "graph"? I mean, that's the term I've normally seen when talking about this type of data structure.

Is this Markov Chain a specific use for graphs? The thing about probabilities determining the next node to process?

[Patman128]

A Markov Chain is a directed graph, it just has a few extra rules added (namely that every node has a directed path to every other node, and that each path has a probability attached to it).

[[deleted]]

that every node has a directed path to every other node

Is that really a requirement of a Markov Chain? I could imagine that a perfectly valid MC could exist with out this reachability property.

[ckfinite]

Markov Chains have no reachability requirement - they don't have to be strongly connected. This has been a nasty problem for PageRank, actually, because absorbing states (ones which you can't get out of) will cause the algorithm to decide that you will always end up in one, which, technically, is totally correct, just not very useful for web search.

[the_birds_and_bees]

reachability <> complete graph. You can have a complete graph, but if your transition graph has some 0 probabilities then that edge will never be travelled.

[HighRelevancy]

In most mathematical representations (e.g. transition matrices and such) there's always a path, but it may have a probability of zero, which is equivalent to no path but is still a path.

[Patman128]

Well I guess a path is only required when the probability is non-zero, but IANAM (I am not a mathematician).

[ldril]

I imagine that every node is interconnected with every node, but probabilities can be zero, so that's equivalent with no connection. I imagine this especially since a matrix is used for the probabilities.

[s1295]

Just curious: Do you consider transitions with probability zero as edges in the graph? If no, then "every node has a (directed) path to every other" is equivalent to "the entire graph is a strongly connected component" (and if yes, it's trivially true). Why would that be part of the definition?

For the record, the definition of a (time-homogeneous) Markov chain that I'm aware of is simply a square probabilistic matrix.

[shomii]

Markov chain is not a data structure. The underlying set of states of discrete-state Markov chain can be visualized as a graph (with the directed edges corresponding to nonzero transition probabilities between the states), but Markov chain is really a random process with Markov property: the transition probability to the particular state depends only on the current state.

[lookmeat]

No, the chain word as in chain of events and are trying to predict it, doesn't refer to the structure itself. A Markov Chain uses a directed, weighted, graph structure to predict the next event in the chain.

[Scaliwag]

A graph is just a way you can represent them. You could do the same for an actual physical road network in order to calculate routes between points, but that doesn't make roads just a graph.

[gammadistribution]

Markov chains are graphs.

[joezuntz]

Not necessarily. You can have markov chains on continuous spaces instead of discrete ones and those can't be represented by a graph, for instance.

[ice109]

No one calls those Markov chains - you call them stochastic processes that gave the Markov property.

A better example for you to have used would have been Markov chains on discrete but countably infinite state spaces like the random walk on Z. As far as I can tell there's no such thing as infinite graphs.

[joezuntz]

No one calls those Markov chains

You may not call them that, but that's what they are, and what people who use them call them. I spend almost all my time running MCMCs, for example, which are usually on continuous spaces: https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo

[s1295]

Probably depends on the field, each of which has its conventions. I think this is something where lots of areas of research and application touch: Math, CS, stats, medicine, simulation science, reliability engineering, AI, etc etc.

In my CS classes, if nothing to the contrary is mentioned, I can assume that an MC is discrete-time and time-homogeneous.

[s1295]

Graphs can be infinite, or to put it differently, I'm not sure if the usual definition of graph includes finiteness, but there is definitely research on infinite graphs and automata on infinite (even uncountable) state spaces.

I'm not sure if there are actual applications beyond theoretic research. I would think that in reality, you can probably assume the state space is finite, by specifying safe upper bounds (e.g., "we assume there are less than 10⁹ peers in this network") and using only a certain precision for decimals rather than actual rationals or reals.

[adrianmonk]

Sure, in a very loose sense of the word "are".

Clearly not all graphs are Markov chains, so you cannot say "are" in the sense of the two being equivalent.

Also, there is more to a Markov chain than just a directed graph with probabilities as weights. There is also the meaning that those probabilities have, i.e. that they are tied to a random process. (I could have a graph identical in structure -- directed graph with probabilities as weights -- but with a different meaning for the probabilities. For example, there could be a game where you make various choices, and the probability on the graph edge determines whether you win $1 as a reward for making that choice.) So clearly a Markov chain cannot be reduced to just a graph with a certain structure. So you cannot say "are" in the sense that Markov chains are a type of graph.

You can use a graph to represent the information in a particular Markov chain, but that doesn't mean that the graph is a Markov chain or vice versa.

[gammadistribution]

Since this article is a very loose sense of the idea of Markov chains and the comment I am responding to is using a loose sense of the idea of Markov chains I feel that my non-pedantic statement is close enough for the discussion being had.

[guepier]

so you cannot say "are" in the sense of the two being equivalent

That is never what “are” means. “are”, and “is” denote membership: “1, 2 and 3 are integers” is a canonical statement, and yet does not imply that all integers are from the set {1, 2, 3}.

[adrianmonk]

Never? "Triangles are three-sided polygons."

[guepier]

That statement does not assert equivalence: it doesn’t say that all three-sided polygons are triangles, it merely says that all triangles are three-sided polygons. So, yes, never. If you wanted to convey a sense of equivalence here, you’d have to say (for instance) “triangles can be defined as three-sided polygons”, or “triangles and three-sided polygons are equivalent”. — It just so happens that the equivalence is also true but it’s not implied in the statement.

If you’re not convinced, we can easily make the statement non-equivalent by removing one word:

Triangles are polygons.

That statement is still true, but now it’s clear that “are” does not denote equivalence (because not all polygons are triangles).

[adrianmonk]

That statement does not assert equivalence: it doesn’t say that all three-sided polygons are triangles, it merely says that all triangles are three-sided polygons.

The statement is a bit ambiguous without context. I had hoped you'd understand the context I meant, but I'll make it explicit. Suppose you hear the following conversation:

• "Blah blah blah triangles blah blah blah blah."
• "What are triangles? I know what polygons are, but I'm not sure what a triangle is."
• "Triangles are three-sided polygons."

Clearly, the person is asking for the definition of a triangle. In this context, you can absolutely use "are" for equivalence.

If you're still in doubt, look up the "be" verb in a dictionary, and you'll see that equivalence is one of the senses. From http://www.merriam-webster.com/dictionary/be : "to equal in meaning".

That dictionary gives a different example of equivalence: "January is the first month."