Algorithmic Solutions > LEDA > LEDA Guide > Graphs and Related Data Types > Markov Chains and Dynamic Markov Chains

## Markov Chains and Dynamic Markov Chains

A markov_chain is a graph in which each edge has an associated non-negative integer weight. For every node with at least one outgoing edge the total weight of the outgoing edges must be positive.

A random walk in a markov chain starts at some node `s` and then performs steps according to the following rule:

• Initially, `s` is the current node
• In the general step, suppose that node `v` is the current node.
• If `v` has no outgoing edge no further step can be taken.
• If `e`0, ..., `e`d - 1 are the edges out of `v` , the walk follows edge `e`i with probability proportional to `w`[`e`i] for all `i, 0 <= i < d`.
The target node of the chosen edge becomes the new current node.

Example for Markov Chains

In a dynamic_markov_chain edge weights can be changed after creation.

### Tips

Markov Chains and Dynamic Markov Chains are very special data types. Use them if the data type fits your needs.

Manual Entries:

Manual Page Markov Chains

Manual Page Dynamic Markov Chains