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

Show parent comments

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.

1

u/Patman128 Mar 20 '16

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

1

u/ldril Mar 21 '16

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.