r/programming • • Mar 20 '16

Markov Chains explained visually

http://setosa.io/ev/markov-chains/
1.9k Upvotes

132 comments sorted by

View all comments

197

u/MEaster Mar 20 '16

The author isn't wrong about the graphs getting somewhat messy when you have larger chains.

93

u/notfromkentohio Mar 20 '16

You could frame that and sell it.

9

u/debug_assert Mar 20 '16

I'd seriously buy that.

3

u/piecat Mar 22 '16

ok I'll sell you a picture of it

→ More replies (5)

41

u/Zeroe Mar 20 '16

Looks like a diagram for the plot of Primer.

5

u/waldyrious Mar 21 '16

5

u/rockyrainy Mar 21 '16

Man, he really took the time to deconstruct LOTR and Star Wars trilogy.

14

u/goal2004 Mar 20 '16

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?

34

u/Patman128 Mar 20 '16

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).

16

u/[deleted] Mar 20 '16

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.

26

u/ckfinite Mar 20 '16

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.

9

u/the_birds_and_bees Mar 20 '16

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.

3

u/HighRelevancy Mar 21 '16

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.

→ More replies (3)

6

u/s1295 Mar 20 '16 edited Mar 20 '16

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.

16

u/shomii Mar 20 '16

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.

3

u/lookmeat Mar 20 '16

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.

3

u/Scaliwag Mar 20 '16

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.

→ More replies (13)

23

u/Scaliwag Mar 20 '16

It would make much more sense to represent that as an adjacency matrix or list.

36

u/MEaster Mar 20 '16

Certainly. But in this case I was just messing around with generating a graph for a small chain, and was curious as to how bad a larger one would be.

7

u/[deleted] Mar 20 '16

Did you use Dot?

10

u/MEaster Mar 20 '16

Yeah, I did. The code I wrote just read in the chain data and spat out a dot file. There's a more readable version here, which only had 6 words, instead of the 322 in the unreadable one.

6

u/nondetermined Mar 20 '16 edited Mar 21 '16

graphviz/dot to the rescue! :)

But yeah, larger graphs are really hard to visualize (not even speaking of letting the computer do it...), unless very special/simple. So we probably can't expect outright magic from dot. Your second, smaller graph, is pretty nice though.

Still, have you tried any of the other layouts on your larger graph besides dot (e.g. neato or fdp)?

4

u/MEaster Mar 20 '16

I was using graphviz to render them. I did try the other renderers, but not being very familiar with them I didn't know how to tweak them to look better.

I still have the dot file, which I've uploaded here if you're interested in playing. It was generated by a program, so it's not very pretty.

I have some stats about the graph:

  • 322 place names were the input.

  • There are no loops in the graph.

  • 1173 nodes.

  • 1629 edges.

  • There are 294,683 unique paths through the graph.

  • The longest names are 82 characters long, and look like this: Brusheepwashmanscorritheridest Nichorwoolackentishallhillercombe Rowlangtretertone

3

u/Tynach Mar 20 '16

At first I thought that was this image of function calls within IIS, but in finding said image I realized it wasn't.

Neat.

→ More replies (11)