Markov Chain that learns by observing data.

MarkovChain.fs

/// Markov chain that learns by observing data.
/// Let it observe a sequence of states.
/// Then you can ask it, given a state,
/// what are the probabilities of the next states occuring?
/// This chain can remember history to make better predictions.
type MarkovChain (numStates : int, memory : int) =

    let numPrevious = 1 + memory

    let matrixSize = int (System.Math.Pow (float numStates, float numPrevious))

    let mutable matrix = Array2D.create matrixSize matrixSize (0, 0)

    let previousStatesToIndex ps = ps |> Seq.take numPrevious |> Seq.fold (fun i x -> i*numStates + x) 0

    let approx (n : int, d : int) =
        if d > 0 then float n / float d
        else 0.0

    member this.TransitionProbabilities = matrix |> Array2D.map approx

    member this.PredictNextState (previousStates : int seq) =
        let prevIndex = previousStatesToIndex previousStates
        let s = previousStates |> Seq.nth (numPrevious - 1)
        Array.init numStates (fun i -> approx matrix.[prevIndex, s*numStates + i])

    member this.Learn (states : int seq) =
        let rec learn s =
            let pIndex = previousStatesToIndex s
            let nIndex = previousStatesToIndex (s |> Seq.skip 1)
            for i = 0 to (matrixSize - 1) do                
                let s, c = matrix.[pIndex, i]
                let a = if i = nIndex then 1 else 0
                matrix.[pIndex, i] <- (s + a, c + 1)
            if Seq.length s > numPrevious + 1 then
                learn (s |> Seq.skip 1)
        learn states

Example:

let t = MarkovChain (3, 1) // 3 states, 1 historical reference
t.Learn ([0; 1; 2; 0; 2; 2; 2; 1; 0; 0; 1; 1; 0; 1; 2; 1; 0; 2; 2; 1; 1; 0])

> t.PredictNextState [0; 1];;
val it : float [] = [|0.0; 0.3333333333; 0.6666666667|]

> t.PredictNextState [1; 0];;
val it : float [] = [|0.3333333333; 0.3333333333; 0.3333333333|]

> t.TransitionProbabilities;;
val it : float [,] =
  [[0.0; 1.0; 0.0; 0.0; 0.0; 0.0; 0.0; 0.0; 0.0]
   [0.0; 0.0; 0.0; 0.0; 0.3333333333; 0.6666666667; 0.0; 0.0; 0.0]
   [0.0; 0.0; 0.0; 0.0; 0.0; 0.0; 0.0; 0.0; 1.0]
   [0.3333333333; 0.3333333333; 0.3333333333; 0.0; 0.0; 0.0; 0.0; 0.0; 0.0]
   [0.0; 0.0; 0.0; 1.0; 0.0; 0.0; 0.0; 0.0; 0.0]
   [0.0; 0.0; 0.0; 0.0; 0.0; 0.0; 0.5; 0.5; 0.0]
   [0.0; 0.0; 1.0; 0.0; 0.0; 0.0; 0.0; 0.0; 0.0]
   [0.0; 0.0; 0.0; 0.6666666667; 0.3333333333; 0.0; 0.0; 0.0; 0.0]
   [0.0; 0.0; 0.0; 0.0; 0.0; 0.0; 0.0; 0.6666666667; 0.3333333333]]