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
e0, ..., ed - 1
are the edges out of v , the walk follows edge ei
with probability proportional to w[ei]
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. |
See also:
Graphs and Related Data Types
Graph
Algorithms
Manual Entries:
Manual Page Markov Chains
Manual Page Dynamic Markov Chains
|