1
$\begingroup$

I have a graph structure and want to say it is a Markov Chain. But I am wondering what necessary assumptions or properties that my graph structure need to meet to be called a Markov Chain?

$\endgroup$
1
$\begingroup$

The formal definition of a Markov Chain is a:

discrete-time stochastic process satisfying the Markov property

From my understanding this means that any finite graph could be considered a Markov Chain, with the vertices being the states and the edges representing the probability of transitioning from one state to another.

The only assumption that you need to be aware of is that of the Markov property, which says that transitions to future states depend only in the present and not in past states. When traversing your graph (i.e. through a random walk), if your jumps from one node to the other depend solely on the edge weights (which usually is the case), then the assumption holds. However, if during your traversal you also consider the previous steps, then the Markov Chain won't give a proper representation of the graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.