Skip to main content

tpt_math_prob_markov/
lib.rs

1//! Markov chain and hidden-Markov-model primitives.
2//!
3//! Two small, dependency-light building blocks sit on top of the [`Rng`] and
4//! [`Distribution`] traits from [`tpt_math_prob_core`]:
5//!
6//! * [`MarkovChain`] — a finite, time-homogeneous chain: build a transition
7//!   matrix, normalize it, find its stationary distribution by power
8//!   iteration, and simulate trajectories from any [`Rng`].
9//! * [`Hmm`] (alias [`HiddenMarkovModel`]) — a discrete hidden Markov model
10//!   with Viterbi decoding, a scaled forward pass for filtering and
11//!   likelihoods, and generative sampling.
12//!
13//! Matrices are plain `Vec<Vec<f64>>` — row `i` is the outgoing distribution of
14//! state `i` — so models can be written out literally, and nothing here needs a
15//! linear-algebra backend. Every sampling entry point is generic over [`Rng`],
16//! so seeding with [`SplitMix64`] makes a whole simulation reproducible.
17//!
18//! # Examples
19//!
20//! A two-state chain, its stationary distribution, and a simulated walk:
21//!
22//! ```
23//! use tpt_math_prob_core::SplitMix64;
24//! use tpt_math_prob_markov::MarkovChain;
25//!
26//! let mut chain = MarkovChain::new(2);
27//! chain.set_transition(0, 0, 0.9);
28//! chain.set_transition(0, 1, 0.1);
29//! chain.set_transition(1, 0, 0.5);
30//! chain.set_transition(1, 1, 0.5);
31//!
32//! let pi = chain.stationary();
33//! assert!((pi[0] - 5.0 / 6.0).abs() < 1e-9);
34//!
35//! let mut rng = SplitMix64::seed_from_u64(42);
36//! let path = chain.run(&mut rng, 0, 1_000);
37//! assert_eq!(path.len(), 1_000);
38//! ```
39//!
40//! Decoding a hidden sequence with Viterbi:
41//!
42//! ```
43//! use tpt_math_prob_markov::Hmm;
44//!
45//! // Hidden: 0 = healthy, 1 = fever. Observed: 0 = normal, 1 = cold, 2 = dizzy.
46//! let model = Hmm::from_parts(
47//!     vec![0.6, 0.4],
48//!     vec![vec![0.7, 0.3], vec![0.4, 0.6]],
49//!     vec![vec![0.5, 0.4, 0.1], vec![0.1, 0.3, 0.6]],
50//! )
51//! .unwrap();
52//!
53//! assert_eq!(model.viterbi(&[0, 1, 2]), vec![0, 0, 1]);
54//! ```
55//!
56//! # Conventions
57//!
58//! * States are `usize` indices into `0..states`; observation symbols are
59//!   `usize` indices into `0..observations`.
60//! * Reading a probability out of range yields `0.0` instead of panicking, so
61//!   partially built models stay inspectable.
62//! * Every operation that can fail on malformed input has a checked `try_*`
63//!   (or `validate`) form returning [`MarkovError`]; the plain form either
64//!   falls back to a documented default or panics on a caller mistake such as
65//!   an out-of-range index.
66
67#![forbid(unsafe_code)]
68#![warn(missing_docs, missing_debug_implementations)]
69
70pub mod chain;
71pub mod error;
72pub mod hmm;
73
74pub use chain::{MarkovChain, DEFAULT_STATIONARY_MAX_ITER, DEFAULT_STATIONARY_TOLERANCE};
75pub use error::MarkovError;
76pub use hmm::{HiddenMarkovModel, Hmm};
77
78pub use tpt_math_prob_core;
79pub use tpt_math_prob_core::{Distribution, Rng, Sampler, SplitMix64, Standard};
80
81/// How far a row sum may drift from `1` before `validate` calls it an error.
82pub const PROBABILITY_TOLERANCE: f64 = 1e-9;
83
84/// Draw an index from `weights`, treated as relative (not necessarily
85/// normalized) probabilities.
86///
87/// This is the inverse-CDF draw used by [`MarkovChain::step`] and
88/// [`Hmm::sample`]: it consumes exactly one [`Standard`] uniform from `rng` and
89/// scans the weights in order, so a seeded generator yields a reproducible
90/// sequence. Negative, infinite, and `NaN` weights are skipped.
91///
92/// Returns `None` if `weights` is empty or carries no positive, finite mass.
93///
94/// # Examples
95///
96/// ```
97/// use tpt_math_prob_core::SplitMix64;
98/// use tpt_math_prob_markov::sample_categorical;
99///
100/// let mut rng = SplitMix64::seed_from_u64(3);
101///
102/// // Only index 1 can be drawn.
103/// assert_eq!(sample_categorical(&mut rng, &[0.0, 2.0, 0.0]), Some(1));
104///
105/// // Weights need not sum to one.
106/// let i = sample_categorical(&mut rng, &[3.0, 1.0]).unwrap();
107/// assert!(i < 2);
108///
109/// assert_eq!(sample_categorical(&mut rng, &[]), None);
110/// assert_eq!(sample_categorical(&mut rng, &[0.0, 0.0]), None);
111/// ```
112pub fn sample_categorical<R: Rng + ?Sized>(rng: &mut R, weights: &[f64]) -> Option<usize> {
113    let total: f64 = weights.iter().filter(|w| w.is_finite() && **w > 0.0).sum();
114    if !total.is_finite() || total <= 0.0 {
115        return None;
116    }
117
118    let uniform: f64 = Standard.sample(rng);
119    let target = uniform * total;
120    let mut cumulative = 0.0;
121    let mut last = None;
122    for (i, &w) in weights.iter().enumerate() {
123        if !w.is_finite() || w <= 0.0 {
124            continue;
125        }
126        cumulative += w;
127        last = Some(i);
128        if target < cumulative {
129            return Some(i);
130        }
131    }
132    // Only reachable through floating-point drift in the final comparison.
133    last
134}
135
136#[cfg(test)]
137mod tests {
138    use super::*;
139
140    #[test]
141    fn sample_categorical_respects_zero_weights() {
142        let mut rng = SplitMix64::seed_from_u64(17);
143        for _ in 0..1_000 {
144            assert_eq!(
145                sample_categorical(&mut rng, &[0.0, 1.0, 0.0, 2.0]).map(|i| i % 2),
146                Some(1)
147            );
148        }
149    }
150
151    #[test]
152    fn sample_categorical_is_none_without_usable_mass() {
153        let mut rng = SplitMix64::seed_from_u64(18);
154        assert_eq!(sample_categorical(&mut rng, &[]), None);
155        assert_eq!(sample_categorical(&mut rng, &[0.0, 0.0]), None);
156        assert_eq!(sample_categorical(&mut rng, &[-1.0, f64::NAN]), None);
157        assert_eq!(sample_categorical(&mut rng, &[f64::NAN, 1.0]), Some(1));
158    }
159
160    #[test]
161    fn sample_categorical_frequencies_track_the_weights() {
162        let weights = [0.5, 0.3, 0.2];
163        let mut counts = [0.0; 3];
164        let mut rng = SplitMix64::seed_from_u64(2026);
165        let draws = 200_000;
166        for _ in 0..draws {
167            counts[sample_categorical(&mut rng, &weights).unwrap()] += 1.0;
168        }
169        for (count, weight) in counts.iter().zip(weights.iter()) {
170            assert!(
171                (count / draws as f64 - weight).abs() < 5e-3,
172                "counts = {counts:?}"
173            );
174        }
175    }
176
177    #[test]
178    fn sample_categorical_accepts_unnormalized_weights() {
179        let mut rng = SplitMix64::seed_from_u64(19);
180        let mut counts = [0.0_f64; 2];
181        for _ in 0..100_000 {
182            counts[sample_categorical(&mut rng, &[30.0, 10.0]).unwrap()] += 1.0;
183        }
184        assert!((counts[0] / 100_000.0 - 0.75).abs() < 5e-3);
185    }
186}