Indeterministic/Propabilistic Machine

Machine.sc

// Indeterministic chooses all possible states, maintaining probabilities
// Probabilistic chooses one of possible states on every transition.
object Probabilistic {
 
	class Machine[T : Ordering] (transitions: Map[T, Set[T]]) { // TODO: probabilistic transitions
		
		def step(history: List[T]) = {
			val p2 = transitions(history.head)
			val picked = (Math.random() * p2.size).toInt
			p2.toList(picked) :: history
		}
		def evolve(state: List[T], steps: Int): List[T] = steps match {
			case 0 => state
			case _ => evolve(step(state), steps-1)
		}//for {_ <- (1 to steps)} step(state)*/
	}
	
	def compileTransitions[T](map: Tuple2[T, T]*): Map[T, Set[T]] = {
		map.foldLeft(Map[T,Set[T]]()) {case (map, (src, dst)) =>
			val set2 = map.get(src).getOrElse(Set()) + dst
			map + (src -> set2)
		}
	}                                         //> compileTransitions: [T](map: (T, T)*)Map[T,Set[T]]
	
	def cycle[T](linearSeq: List[T]): List[Tuple2[T,T]] = {
		for {
			(letter, i) <- linearSeq.zipWithIndex
		} yield linearSeq(i) -> linearSeq((i+1) % linearSeq.length)
		
	}                                         //> cycle: [T](linearSeq: List[T])List[(T, T)]
	val fwd_cycle = cycle("abcde".toList)     //> fwd_cycle  : List[(Char, Char)] = List((a,b), (b,c), (c,d), (d,e), (e,a))
	val bicycle = fwd_cycle.foldLeft(fwd_cycle) {case (acc, (src, dst)) => dst -> src :: acc }
                                                  //> bicycle  : List[(Char, Char)] = List((a,e), (e,d), (d,c), (c,b), (b,a), (a,
                                                  //| b), (b,c), (c,d), (d,e), (e,a))
	compileTransitions(bicycle : _*)          //> res0: Map[Char,Set[Char]] = Map(e -> Set(d, a), a -> Set(e, b), b -> Set(a,
                                                  //|  c), c -> Set(b, d), d -> Set(c, e))
	(1 to 20) foreach {_ =>
		println (new Machine(compileTransitions(bicycle: _ *)).evolve(List('a'), 5).reverse)
                                                  //> List(a, b, a, b, a, b)
                                                  //| List(a, e, a, b, a, b)
                                                  //| List(a, b, c, d, c, d)
                                                  //| List(a, b, c, d, e, d)
                                                  //| List(a, e, a, e, d, e)
                                                  //| List(a, b, c, d, e, a)
                                                  //| List(a, e, a, b, c, b)
                                                  //| List(a, b, c, d, c, b)
                                                  //| List(a, b, c, b, a, e)
                                                  //| List(a, e, a, e, a, e)
                                                  //| List(a, b, c, d, c, b)
                                                  //| List(a, e, a, b, a, e)
                                                  //| List(a, e, d, c, d, c)
                                                  //| List(a, e, d, e, a, e)
                                                  //| List(a, b, a, e, a, b)
                                                  //| List(a, e, a, b, c, b)
                                                  //| List(a, e, d, c, b, c)
                                                  //| List(a, e, a, b, c, b)
                                                  //| List(a, e, a, b, a, e)
                                                  //| List(a, b, a, b, c, d)
                                                  
		// Note that probability of 'a' is very low after 5 steps. Indeterminist
		// simulation computes the real probability below.
	}
	
	
	// Curiously, indetermenist machine may be reversible -- you can get into reset state from any other state.
	// But, we evolve from one initial state. After n steps we are in some distribution. It is different distri
	// bution when started from a different state and reverting won't recover previous state.
	
	type State[T] = Map[T, Double] // value with some probability
	
	class Indet[T : Ordering] (val initial: T, val transitions: Map[T, Set[T]]) { // TODO: probabilistic transitions
		
		var state: State[T] = Map(initial -> 1) // collapse into initial state
		
		def step = {
			var st2: State[T] = Map()
			state foreach {case (curState, curWeight) =>
				transitions(curState) foreach {nextState =>
					val newWeight = st2.get(nextState).getOrElse(0.0) + curWeight
					//println ("adding " + nextState -> newWeight)
					st2 += nextState -> newWeight
				}
			}
 
			val total = st2.values.sum
			state = st2
				.map {case (key, w) => (key, w/total)} // normalize prob to 0..1
			println ("entered " + state.toList.sortBy(_._1))
		}
		
		def evolve(steps: Int) = (1 to steps).foreach (_ => step)
	}
 
	new Indet('a', compileTransitions(bicycle: _ *)).evolve(100)
                                                  //> entered List((b,0.5), (e,0.5))
                                                  //| entered List((a,0.5), (c,0.25), (d,0.25))
                                                  //| entered List((b,0.375), (c,0.125), (d,0.125), (e,0.375))
                                                  //| entered List((a,0.375), (b,0.0625), (c,0.25), (d,0.25), (e,0.0625))

// Fifth step: probability of 'a' is very low:    //| entered List((a,0.0625), (b,0.3125), (c,0.15625), (d,0.15625), (e,0.3125))

                                                  //| entered List((a,0.3125), (b,0.109375), (c,0.234375), (d,0.234375), (e,0.109
                                                  //| 375))
                                                  //| entered List((a,0.109375), (b,0.2734375), (c,0.171875), (d,0.171875), (e,0.
                                                  //| 2734375))
                                                  //| entered List((a,0.2734375), (b,0.140625), (c,0.22265625), (d,0.22265625), (
                                                  //| e,0.140625))
                                                  //| entered List((a,0.140625), (b,0.248046875), (c,0.181640625), (d,0.181640625
                                                  //| ), (e,0.248046875))
                                                  //| entered List((a,0.248046875), (b,0.1611328125), (c,0.21484375), (d,0.214843
                                                  //| 75), (e,0.1611328125))
                                                  //| entered List((a,0.1611328125), (b,0.2314453125), (c,0.18798828125), (d,0.18
                                                  //| 798828125), (e,0.2314453125))
                                                  //| entered List((a,0.2314453125), (b,0.174560546875), (c,0.209716
                                                  //| Output exceeds cutoff limit.
                                                  
	
	
}