# markov-realization: Realizations of Markov chains.

[ bsd3, library, statistics ] [ Propose Tags ]
This version is deprecated.

## Modules

• Markov
• Markov.Example
• Markov.Extra
• Markov.Generic

#### Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0, 0.2.1, 0.3.0, 0.3.1, 0.3.2, 0.3.3, 0.4 (info) ChangeLog.md base (>=4.7 && <5), comonad, configuration-tools, matrix, MonadRandom [details] BSD-3-Clause 2019 Alex Loomis Alex Loomis atloomis@math.arizona.edu Statistics https://github.com/alexloomis/markov https://github.com/alexloomis/markov/issues head: git clone git://github.com/alexloomis/markov.git by alexloomis at 2019-08-21T04:18:02Z NixOS:0.4 2034 total (3 in the last 30 days) (no votes yet) [estimated by Bayesian average] λ λ λ Docs not available All reported builds failed as of 2019-08-21

## Readme for markov-realization-0.3.1

[back to package description]

# Markov Tutorial

Let Xₙ denote the nth state of a Markov chain with state space ℕ. For x ≠ 0 define transition probabilities

p(x,0) = q,

p(x,x) = r, and

p(x,x+1) = s.

When x = 0, let p(x,0) = q+r, p(x,x+1) = s. Let p(x,y) = 0 in all other cases. Suppose we wanted to find P[Xₙ = j ∩ d = k], where d denotes the number of transitions from a positive integer to zero. There are three values we need to track — extinctions, probability, and state. Extinctions add a value to a counter each time they happen and the counter takes integral values, so they can be represented by Sum Int. Probabilities are multiplied each step, and added when duplicate steps are combined. We want decimal probabilities, so we can represent this with Product Rational. We will make a new type for the state.

newtype Extinction = Extinction Int
deriving Generic
deriving newtype (Eq, Num, Show)
deriving anyclass Grouping


Combining identical states should not change the state, so we make an instance of Combine as follows.

instance Combine Extinction where combine = const


All that remains is to make an instance of Markov.

instance Markov ((,) (Sum Int, Product Rational)) Extinction where
transition = \case
0 -> [ 0 >*< (q+r) >*< id
, 0 >*< s >*< (+1) ]
_ -> [ 1 >*< q >*< const 0
, 0 >*< r >*< id
, 0 >*< s >*< (+1) ]
where q = 0.1; r = 0.3; s = 0.6


We can now easily see a list of states, deaths, and the probabilities.

> chain [pure 0 :: Sum Int :* Product Rational :* Extinction] !! 3

[ ((0,8 % 125),0)
, ((0,111 % 500),1)
, ((1,51 % 500),0)
, ((0,9 % 25),2)
, ((1,9 % 250),1)
, ((0,27 % 125),3) ]


This means that starting from a state of zero, after three time steps there is a 51/500 chance that the state is zero and there has been one death.