2 Module behavior/markov-chain

This module provides an implementation for (discrete-time, classic) Markov chains, these can be used to create the underlying event stream, with specific distributions, for higher-level behaviors, or for direct simulation. It also separates the definition of a mkchain from an execution instance so that the definition may be reused across multiple executions. Individual states are represented as symbols, the chain is represented as a matrix, with a row representing transition sources and columns representing the transition target. Probabilities are represented as real numbers from 0.0 to 1.0 and all probabilities in a row must add up to either 0.0 or 1.0.

As defined by Wikipedia; A Markov chain is "a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event".

Examples:

> (define a-chain (make-chain 'example
                   (==> 'a (--> 'a 0.5) (--> 'b 0.25) (--> 'c 0.25))
                   (==> 'b (--> 'a 0.5) (--> 'c 0.5))
                   (==> 'c (--> 'a 0.25) (--> 'b 0.25) (--> 'c 0.5))))
> (define an-exec (make-chain-execution a-chain 'b))
> (execute an-exec 10)
execute: undefined;
cannot reference an identifier before its definition
  in module: top-level
> (displayln (execution-trace an-exec))
execution-trace: undefined;
cannot reference an identifier before its definition
  in module: top-level
> (displayln (mkchain->graph-string a-chain))
digraph markov_chain {
    rankdir = LR;
    size = "8,5";
    node [shape = circle];
    c -> c [label = "0.5"];
    c -> b [label = "0.25"];
    c -> a [label = "0.25"];
    b -> c [label = "0.5"];
    b -> a [label = "0.5"];
    a -> c [label = "0.25"];
    a -> b [label = "0.25"];
    a -> a [label = "0.5"];
}

The execution-trace function returns the history of the execution as a list of states the execution has been in. The list is ordered from most recent to last; this trace is not a memory, the implementation is still a classic Markov chain.

2.1 Types and Predicates

struct
(struct mkchain (name))
name : symbol?

struct
(struct chain-execution (model state complete?))
  model : symbol?
  state : symbol?
  complete? : boolean?

struct
(struct chain-history-event history-event (current-execution state))
current-execution : chain-execution?
state : symbol?

contract
mkchain-row? : contract?

Determines whether a contract parameter is a Markov chain row.

procedure
(-->? chain from-state to-state) → boolean?
  chain : mkchain?
  from-state : symbol?
  to-state : symbol?

Does a transition exist between from-state and to-state?.

procedure
(<-->? chain state1 state2) → boolean?
  chain : mkchain?
  state1 : symbol?
  state2 : symbol?

Do the two states state1 and state2 communicate? Wikipedia: "A state i is said to communicate with state j (written i ↔ j) if both i → j and j → i".

procedure
(>--<? chain state) → boolean
chain : mkchain?
state : symbol?

Is the state state an absorbing state? Wikipedia: "A state i is called absorbing if it is impossible to leave this state". This implies either no transitions exit this state, or the only transition from this state is to itself.

2.2 Construction

procedure
(==> from-state pair ...+) → pair?
from-state : symbol?
pair : pair?

Construct a pair that represents a row in the transition matrix. The pair c consists of a symbol naming a state and one or more transition pairs (see --> below).

procedure
(==>! from-state) → pair?
from-state : symbol?

Construct a pair that represents an absorbing state in the transition matrix.

procedure
(--> to-state probability) → pair?
to-state : symbol
probability : real?

Construct a transition pair that represents the target of a transition and it’s associated probability.

procedure
(make-chain name pair ...+) → (or/c #f mkchain?)
name : symbol?
pair : (pairof symbol? mkchain-row?)

Make a new mkchain structure from the list of symbol and row pairs. Each pair represents a source state and it’s set of target state probabilities. These pairs can be constructed using the ==> and ==> functions.

Example:

> (make-chain 'example
              (==> 'a (--> 'a 0.3) (--> 'b 0.7))
              (==> 'b (--> 'b 0.7) (--> 'c 0.3))
              (==>! 'c))
#<mkchain>

This function will return #f if any of the provided pairs are invalid.

procedure
(make-diagonal-chain name state ...+) → mkchain?
name : symbol?
state : symbol?

Make a new mkchain where the only transitions are the self-transitions for each state. The name of this function comes from visualizing the transition matrix as having only cells for the diagonal relationships where the from state and to state are the same.

procedure
(row-ref chain from-state) → mkchain-row?
chain : mkchain?
from-state : symbol?

Return a row from the transition matrix corresponding to the state from-state.

procedure
(row-set chain state row) → (or/c #f mkchain?)
  chain : mkchain?
  state : symbol?
  row : mkchain-row?

Set a row in the transition matrix corresponding to the state from-state, returning the new chain. If the row itself is invalid in any way the response is #f and the chain is unchanged.

procedure
(mkchain-states chain) → (listof string?)
chain : mkchain?

Return the list of symbols representing the states of this chain.

2.3 Execution

An execution takes place according to discrete steps. At each step the set of transitions from the current state (see execution-state) and chooses a single transition based on the probabilities for each. Once chosen the to state is made current and the step is complete.

If the current state is an absorbing state (see >--<?) then the execution is said to be complete (see execution-complete?) and any further calls to either execute or execute-next will have no effect.

procedure
(make-chain-execution from-chain
start-state
[ reporter]) → (or/c #f execution?)
  from-chain : mkchain?
  start-state : symbol?
  reporter : mkchain-reporter? = #f

Create an execution structure from the given chain, and given starting state. The behavior of the execution depends on whether the execution itself keeps track of the execution history or whether the caller does by providing a reporter function.

When reporter is specified the provided function is called with the new state each time one is selected. As the execution is not responsible for tracking the history of the chosen states, the value of the function execution-trace is simply the current state.
Otherwise, all states are recorded and can be retrieved by the execution-trace function.

This function will return #f if start-state is not a state within the chain from-chain.

procedure
(make-chain-execution-generator from-chain
start-state)
→ (or/c #f generator?)
from-chain : mkchain?
start-state : symbol?

Create an execution generator from the given chain, and given starting state. The most common usage is in conjunction with in-producer and use a stop-value of #f, as shown below.

Examples:

> (define d-chain (make-chain
                   (==> 'a (--> 'b 1.0))
                   (==> 'b (--> 'c 1.0))
                   (==>! 'c)))
make-chain: contract violation
  expected: symbol?
  given: '(a . #hash((b . 1.0)))
  in: the 1st argument of
      (->*
       (symbol?)
       #:rest
       (listof pair?)
       (or/c #f mkchain?))
  contract from:
      <pkgs>/behavior/behavior/markov-chain.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/behavior/behavior/markov-chain.rkt:20.3
> (define next (make-chain-execution-generator d-chain 'a))
d-chain: undefined;
cannot reference an identifier before its definition
  in module: top-level
> (for ([state (in-producer next #f)])
    (displayln state))
next: undefined;
cannot reference an identifier before its definition
  in module: top-level

This function will return #f if start-state is not a state within the chain from-chain.

procedure
(execute-chain exec steps) → execution?
exec : execution?
steps : exact-positive-integer?

This function will perform a number of steps, effectively calling the execute-next for each step. The response is the new state of the execution.

procedure
(execute-chain-step exec) → execution?
exec : execution?

Calculate the next state, store it in the execution trace, and return an updated copy of the execution.

procedure
(execution-chain-state exec) → symbol?
exec : execution?

Return the current state the chain is in.

procedure
(execution-chain-complete? exec) → boolean?
exec : execution?

Return #t if the execution has reached an absorbing state (see >--<?).

2.4 GraphViz

It can be very useful to view a Markov chain as a state transition diagram and the following functions provide this capability by writing the DOT file format used by Graphviz for visualization.

Given the example in this module’s introduction, running the resulting DOT text through dot -T png a-chain.dot > a-chain-graph.png results in the following image.

procedure
(mkchain->graph chain out) → void?
chain : mkchain?
out : port?

Write a Graphviz representation of the provided chain to the provided output port.

procedure
(mkchain->graph-string chain) → string?
chain : mkchain?

Return a Graphviz representation of the provided chain as a string.

top ← prev up next →

1	Module behavior/ fsm
2	Module behavior/ markov-chain
3	Module behavior/ petri-net
4	Module behavior/ reporter

2.1	Types and Predicates
2.2	Construction
2.3	Execution
2.4	Graph Viz