úÎ!iÃa¿t      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrs6Realization of Markov processes with known parameters.atloomis@math.arizona.edu ExperimentalNone;>@AME markov-realizationgValues which are multiplied each step, and combined additively for equal states. E.g., probabilities.markov-realization–Values which are added each step, where different values mean states should not be combined. E.g., number of times a red ball is picked from an urn.markov-realizationValues from a tž which have the respective binary operation applied each step, where different values mean states should not be combined. E.g., strings with concatenation.markov-realizationWithin equivalence classes, combineT should be associative, commutative, and idempotent (up to equivalence). I.e. if  x == y == z,9(x `combine` y) `combine` z = x `combine` (y `combine` z)x `combine` y = y `combine` xx `combine` x == x markov-realization#An implementation of Markov chains. markov-realization(A basic implementation of Markov chains.markov-realization+Iterated steps, with equal states combined.markov-realization1Iterated steps, with equal states combined using  operation.markov-realizationWARNING! Defined  _ == _ = True!markov-realizationWARNING! Defined compare _ _ = EQ!   atloomis@math.arizona.eduNone>UV"1markov-realization$Easier way to write nested 2-tuples.umarkov-realization+Randomly choose from a list by probability.2markov-realization/Returns a single realization of a Markov chain.3markov-realizationKCreate a transition function from a transition matrix. Inputs should obey: Iall (== length matrix) (map length matrix) length matrix == length states4markov-realizationJEasier way to write nested 2-tuples. Left associative, binds weaker than + but stronger than ==.12343214456Realization of Markov processes with known parameters.atloomis@math.arizona.edu ExperimentalSafe@A%ò5markov-realization<An implementation of Markov chains with non-list containers.0Markov.Markov t s = Markov.Generic.Markov [] t s57685768,Examples of Markov chains implemented using Markov.atloomis@math.arizona.edu ExperimentalNone ;=>?@AMUV_`Ô9markov-realizationÿ#A collection of bins with gaps between them. At each step an empty space is chosen form a bin or from a gap. If it is in a bin, the space is filled. If it is in a gap, it is assigned to an adjacent bin, which expands to contain it and any intervening spaces, and then the space filled.vmarkov-realization4Represents space between bins where they can expand.wmarkov-realization*Represents bins with free slots and items.:markov-realizationA hidden Markov model.4:{ filter (\((_,Merge xs),_) -> xs == "aaa") $ chainN [1 >*< Merge "" >*< 1 :: Product Rational :* Merge String :* Room] !! 3 :} [ ((3243 % 200000,"aaa"),Room 1) , ((9729 % 500000,"aaa"),Room 2)", ((4501 % 250000,"aaa"),Room 3) ]*Given that all three tokens recieved were "a"+, there is a probability of approximately 0.34 that the current room is Room 3.<markov-realizationA time inhomogenous random walk that vaguely models tides by periodically switching directions and falling back from a shore at the origin.@markov-realization"This is the chain from the README.Bmarkov-realizationAn urn contains balls of two colors. At each step, a ball is chosen uniformly at random from the urn and a ball of the same color is added.BrandomPath (mkStdGen 70) (Urn (2,5)) !! 8 :: (Product Double, Urn) (0.1648351648351649, Urn (2,13))Dmarkov-realizationBA simple random walk. Possible outcomes of the first three steps:take 3 $ chain0 [Simple 0][ [0], [-1,1] , [-2,0,2] ]Probability of each outcome:3take 3 $ chain [pure 0 :: (Product Double, Simple)] [ [(1.0,0)], [(0.5,-1),(0.5,1)] , [(0.25,-2),(0.5,0),(0.25,2)] ]'Number of ways to achieve each outcome:0take 3 $ chain [pure 0 :: (Product Int, Simple)] [ [(1,0)], [(1,-1),(1,1)], [(1,-2),(2,0),(1,2)] ]Number of times pred( was applied, allowing steps in place (id) for more interesting output:(chain [pure 0 :: (Sum Int, Simple)] !! 2.[ (2,-2), (1,-1), (1,0), (0,0), (0,1), (0,2) ]Fmarkov-realization!An example defined from a matrix.Dchain [pure (FromMatrix 't') :: (Product Double, FromMatrix)] !! 100[ (0.5060975609756099,'a'), (0.201219512195122,'t'), (0.29268292682926833,'l') ]xmarkov-realization*fBFromLists [1,3,5,10] [(3,5),(9,9),(8,3)] 1 (3,5) 3 (9,9) 5 (8,3) 10Hmarkov-realization+Create state where all bins start as (0,0).initial [5,7,0]5 (0,0) 7 (0,0) 0ymarkov-realizationThe number of bins.zmarkov-realizationThe bins of a state.{markov-realizationThe open values of a state.|markov-realizationThe open value of the Nth bin.}markov-realizationThe full values of a state.~markov-realizationThe full value of the Nth bin.markov-realizationThe gap values of a state.€markov-realizationWarning! Indexed from zero!markov-realization The command  iApply i f s is analagous to take i s ++ f (drop i s).‚markov-realizationAdd an item to the ith bin.ƒmarkov-realization@Expand the ith bin to the left by j. The Markov chain will use addItem i . growLeft j i.„markov-realization+The sum of all open slots in bins and gaps.…markov-realization/The probability that a state returns to itself.†markov-realization/The probability that the ith bin gains an item.‡markov-realization5The probability that the ith bin expands to the left.ˆmarkov-realization6The probability that the ith bin expands to the right.‰markov-realizationThe l^2M distance between a finished state and a state with perfectly balanced bins.Imarkov-realization$Expected loss of a set of states of [9]. Loss is the l^2M distance between a finished state and a state with perfectly balanced bins.BexpectedLoss [pure $ initial [1,0,3] :: (Product Double, FillBin)]2.09:;<=>?@ABCDEFGHIFGDEBC@A<=>?:;9HISafeašŠ‹ŒŽ‘’      !"#$%&'()*+,-./0123456  78899:;<<==>>??@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹Œ-markov-realization-0.4-4vrsocu7nZUCfVxGqeaT8uMarkov Markov.ExtraMarkov.GenericMarkov.ExamplePaths_markov_realizationProductSumMergeCombinecombine summarize transitionstep sequentialMarkov0 transition0step0chain0chain $fCombine(,,) $fCombine(,)$fCombineMerge $fMonoidSum$fSemigroupSum $fCombineSum$fMonoidProduct$fSemigroupProduct$fCombineProduct $fEqProduct $fOrdProduct $fEqMerge$fSemigroupMerge $fMonoidMerge $fEnumMerge $fNumMerge $fOrdMerge$fFractionalMerge $fShowMerge$fEqSum $fEnumSum$fNumSum$fOrdSum$fFractionalSum $fShowSum $fEnumProduct$fFractionalProduct$fIntegralProduct $fNumProduct $fRealProduct $fShowProduct:* randomPath fromLists>*<FillBinRoomTidaltimeposition ExtinctionUrnSimple FromListsinitial expectedLoss$fMarkov(,)FromLists$fCombineFromLists$fMarkov(,)Simple$fMarkov(,)Simple0$fMarkov(,)Simple1$fMarkov0Simple$fCombineSimple$fMarkov[](,)Urn$fMarkov(,)Urn $fCombineUrn$fMarkov(,)Extinction$fCombineExtinction$fMarkov(,)Tidal$fCombineTidal$fMarkov(,)Room $fCombineRoom$fMarkov(,)FillBin$fCombineFillBin $fShowFillBin $fEqFromLists$fOrdFromLists$fShowFromLists $fNumSimple $fEnumSimple $fEqSimple $fOrdSimple $fShowSimple$fEqUrn$fOrdUrn $fShowUrn$fEqExtinction$fNumExtinction$fShowExtinction $fEqTidal $fOrdTidal $fShowTidal $fShowRoom$fEqRoom $fNumRoom $fOrdRoom $fEqFillBin $fOrdFillBinbaseGHC.BaseMonoid randomProductGapBin fBFromListssizegetBinsgetOpenopenNgetFullfullNgetGapgapNiApplyaddItemgrowLeftslotsprobIdprobAdd probGrowL probGrowRindividualLossversion getBinDir getLibDir getDynLibDir getDataDir getLibexecDir getSysconfDirgetDataFileName