Markov Model - Forest

A Markov model is a model of a sequence of unobserved states. Each state depends only on the previous state.

(define (transition state)
  (cond
   ((eq? state 'a) (multinomial '(a b c) '(0.7 0.2 0.1)))
   ((eq? state 'b) (multinomial '(a b c) '(0.3 0.3 0.4)))
   ((eq? state 'c) (multinomial '(a b c) '(0.3 0.65 0.05)))))

(define (markov state n)
  (if (= n 0)
      '()
      (pair state (markov (transition state) (- n 1)))))

(markov 'a 10)

We can put a prior on transition probabilities:

(define states '(a b c))

(define state->transition-model
  (mem (lambda (state) (dirichlet (make-list (length states) 1)))))

(define (transition state)
  (multinomial states (state->transition-model state)))

(define (markov state n)
  (if (= n 0)
      '()
      (pair state (markov (transition state) (- n 1)))))

(markov 'a 10)

The number of states can be infinite:

(define theta 0.7)

(define (transition state)
  (if (= state 3)
      (multinomial (list 3 4)
                   (list (- 1 (* 0.5 theta)) (* 0.5 theta)))
      (multinomial (list (- state 1) state (+ state 1))
                   (list 0.5 (- 0.5 (* 0.5 theta)) (* 0.5 theta)))))
  
(define (chain state n)
  (if (= n 0)
      state
      (chain (transition state) (- n 1))))

(hist (repeat 2000 (lambda () (chain 3 20))) "markov chain")