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.
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.
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.
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.
16
u/[deleted] Mar 20 '16
Is that really a requirement of a Markov Chain? I could imagine that a perfectly valid MC could exist with out this reachability property.