; a Markov process is a discrete random process in which the
; probability of the next outcome depends on one (or more) past
; outcomes. The easiest way to understand the linkage between past and
; future outcomes is to imagine a 'transition table' where each row in
; the table is the probability distribution of future outcomes for a
; given past outcome. In a first order Markov process then, each row
; is a transtion "rule" connecting one past outcome to the (next)
; possible outcomes. In a second order process each row would
; determine the next outcome given the two previous outcomes. The
; (degenerate) case of no past outcomes is called zero order Markov
; and it is equivalent to weighted random selection.

; Our first example shows a zero order Markov process that implements
; a fair coin toss. One two outcomes are possible: A (heads) and B
; (tails), each one of which has an equal probability of being
; selected.

; Probability table of fair coin toss:
;
;        A       B
;        0.50    0.50

; Here are 20 representative outcomes from this table:
;
;    B A B B A A A B B B A A B A A A B A B

; We now convert the preceding example into a (first order) transition
; table that exibits the exact same behavior.

; Transition table of a fair coin toss:

;        A       B
; A  ->  0.50    0.50
; B  ->  0.50    0.50


; This table says that IF our last event was an A then our next event
; is either an A or a B with equal probability, and if our last event
; was a B then our next event is either an A or a B with equal
; probablity. Thus, each row in the trasition table acts as a kind of
; 'feedback' loop: past outcomes are "matched" against the transition
; row, and the row whose past matches the last outcome is used to
; generate the next outcome. Note that EVERY outcome must match some
; row. Another way of sayinf this is there must 100 proability that
; the next outcome  --whatever it is -- will occur.

; Transition tables can implement random patterns that are impossible
; to generate using just probability tables. Different patterns are
; established by altering the weights of table cells in the transition
; rows. For example, this next table produces a 'biased' coin toss
; that favors heads, particularly if the last value chosen was tails:

; Transition table for a biased coin toss:
;
;        A       B
; A  ->  0.75    0.25
; B  ->  1.00    0.00

; Here are representative outcomes from this table:
;
;    B A B A A A A A B A A B A A A A A B A A

;
; The Markov pattern
;

; To create a markov process, specify a transition table to the
; <markov> pattern.  The transision table is a list of lists where
; each sublist is a 'row' that contains one (or more) past outcomes
; followed by a 'trasition marker' :-> followed by all the future
; outcomes with their associated probabilities. For example, the fair
; coin toss would look like this:

variable faircoin = 
  make-markov({{a  ->  {a 1} {b 1}} 
               {b  ->  {a 1} {b 1}}
               })

next(faircoin, 20)

; Note that outcomes with the (default) weighting of 1 do not have to
; be specified with the weight. So an equivannt notation is:

variable faircoin = 
  make-markov({{a  ->  a  b} 
               {b  ->  a  b}
               })

next(faircoin, 20)

; the biased coin toss looks like this:

variable biascoin = 
  make-markov({{a  ->  {a .75} {b .25}} 
               {b  ->  a}
               })

next(biascoin, 20)