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}