Crate markovian

Simulation of (sub-)stochastic processes.

Goal

Serve as an extension of the rand crate for sub-stochastic processes.

Examples

Discrete time

Construction of a random walk in the integers.

let init_state: i32 = 0;
let transition = |state: &i32| raw_dist![(0.5, state + 1), (0.5, state - 1)];
let rng = thread_rng();
let mut mc = markovian::MarkovChain::new(init_state, transition, rng);

Branching process

Construction using density p(0) = 0.3, p(1) = 0.4, p(2) = 0.3.

let init_state: u32 = 1;
let base_distribution = raw_dist![(0.3, 0), (0.4, 1), (0.3, 2)];
let rng = thread_rng();
let mut branching_process = markovian::BranchingProcess::new(init_state, base_distribution, rng);

Continuous time

Construction of a random walk in the integers, with expponential time for each transition.

let init_state: i32 = 0;
struct MyTransition;
impl markovian::Transition<i32, (f64, i32)> for MyTransition {
    fn sample_from<R: ?Sized>(&self, state: &i32, rng: &mut R) -> (f64, i32)
    where
        R: Rng
    {
        let time = Exp::new(2.0).unwrap().sample(rng);
        let step = Uniform::from(0..=1).sample(rng) * 2 - 1;
        (time, state + step)
    }
}
let transition = MyTransition;
let rng = thread_rng();
let mut mc = markovian::TimedMarkovChain::new(init_state, transition, rng);

Remarks

All methods are inline, by design.

Non-trivial ways to use the crate are described below, including time dependence, continuous space and non-markovian processes.

Time dependence

Include the time as part of the state of the process.

Examples

A random walk on the integers that tends to move more to the right as time goes by.

let init_state: (usize, i32) = (0, 0);
let transition = |(time, state): &(usize, i32)| raw_dist![
    (0.6 - 1.0 / (time + 2) as f64, (time + 1, state + 1)),
    (0.4 + 1.0 / (time + 2) as f64, (time + 1, state - 1))
];
let rng = thread_rng();
let mut mc = markovian::MarkovChain::new(init_state, &transition, rng);
 
// Take a sample of 10 elements 
mc.take(10).map(|(_, state)| state).collect::<Vec<i32>>();

Continuous space

Randomize the transition: return a random element together with a probability one

Examples

A random walk on the real line with variable step size.

let init_state: f64 = 0.0;
struct MyTransition;
impl markovian::Transition<f64, f64> for MyTransition {
    fn sample_from<R: ?Sized>(&self, state: &f64, rng: &mut R) -> f64
    where
        R: Rng
    {
        let step = Exp::new(2.0).unwrap().sample(rng);
        state + step
    }
}
let transition = MyTransition;
let rng = thread_rng();
let mut mc = markovian::MarkovChain::new(init_state, transition, rng);
mc.next();
  
// current_state is positive 
assert!(mc.state().unwrap() > &0.0);

Non markovian

Include history in the state. For example, instead of i32, use Vec<i32>.

Examples

A random walk on the integers that is atracted to zero in a non markovian fashion.

let init_state: Vec<i32> = vec![0];
let transition = |state: &Vec<i32>| {
    // New possible states
    let mut right = state.clone();
    right.push(state[state.len() - 1] + 1);
    let mut left = state.clone();
    left.push(state[state.len() - 1] - 1);
 
    // Some non markovian transtion
    let path_stadistic: i32 = state.iter().sum();
    if path_stadistic.is_positive() {
        raw_dist![
            (1.0 / (path_stadistic.abs() + 1) as f64, right), 
            (1.0 - 1.0 / (path_stadistic.abs() + 1) as f64, left)
        ]
    } else {
        raw_dist![
            (1.0 - 1.0 / (path_stadistic.abs() + 1) as f64, right), 
            (1.0 / (path_stadistic.abs() + 1) as f64, left)
        ]
    }
};
let rng = thread_rng();
let mut mc = markovian::MarkovChain::new(init_state, transition, rng);
  
// state has history
mc.next();
assert_eq!(mc.state().unwrap().len(), 2);

Modules

distributions

Ease interoperability with rand_distr crate.

errors

Errors of this crate.

prelude

Ease of use of this crate in general.

Macros

raw_dist

Creates a Raw struct by first allocating a Vec and passing it to Raw::new.

Structs

BranchingProcess

Branching process in the natural numbers NN = {0, 1, 2, …}.

ContFiniteMarkovChain

Finite state Markov Chain in continuous time.

FiniteMarkovChain

Finite state Markov Chain in discrete time.

MarkovChain

Markov Chain in discrete time, with arbitrary space.

TimedMarkovChain

Markov Chain in continuous time, with arbitrary space.

Traits

State

Possible public state.

StateIterator

Iterator with an internal state that is thought as the “zero” element.

Transition

Abstraction over transition matrix.