Skip to main content

dima_core/
entropy.rs

1//! Shannon entropy of the k-mer distribution at a position, and its bias-corrected estimators.
2//!
3//! All estimators work on the *counts of counts* of a position ([`CountProfile`]): how many
4//! distinct k-mers were seen once, twice, …. That is all they need, it is tiny, and it makes the
5//! cost independent of the k-mer length.
6//!
7//! * [`plug_in`]: the observed (maximum-likelihood) entropy H = −Σ pᵢ log₂ pᵢ (Shannon 1948),
8//!   biased downwards by about (D − 1)/(2N ln 2) bits (Miller 1955; Paninski 2003).
9//! * [`dima_corrected`]: the paper's correction (Tharanga et al. 2025, Fig. 2) — entropies of
10//!   subsamples of R % of the sequences are regressed on 1/n and the intercept (n → ∞) is the
11//!   estimate. The paper draws one random with-replacement subsample per R; because the OLS
12//!   intercept is linear in the responses, its expectation is the intercept fitted to the
13//!   *expected* subsample entropies, which are computed here exactly (no random numbers). It is
14//!   the conditional expectation of the random intercept given the data: the same mean and no
15//!   larger variance (Rao 1945; Blackwell 1947), the limit of averaging many random subsets as
16//!   DiMA's predecessors did (Khan et al. 2008, 2017; Miotto et al. 2008), and identical inputs
17//!   always give identical outputs. The expected intercept is never negative (see
18//!   [`dima_corrected`]), so the paper's negative-intercept rule never applies to it; DiMA v5.0.9
19//!   applies it to each random run instead, which raises its long-run average at near-conserved
20//!   positions.
21//!
22//! Every reported entropy is checked to be a finite number of at least 0 bits ([`estimate`]):
23//! the estimators guarantee it, so a violation is a bug and stops the run as an internal error
24//! instead of being replaced by another value (Wilson et al. 2014, Practice 5a; Hunter-Zinck et
25//! al. 2021, Rule 5).
26//! * [`miller_madow`]: H + (D − 1)/(2N ln 2) (Miller 1955).
27//! * [`chao_wang_jost`]: Chao et al. (2013), the least biased estimator in their
28//!   comparison.
29//! * [`sample_coverage`]: estimated sample coverage (Chao & Jost 2012), the probability that
30//!   the next sequence carries an already-seen k-mer.
31
32use std::f64::consts::LN_2;
33
34use crate::config::Estimator;
35use crate::error::{DimaError, Result};
36use crate::model::{EntropyFallback, EntropyMethod};
37use crate::numeric::{Neumaier, binomial_walk, digamma_difference, lerch_phi1, ols_intercept};
38
39/// Minimum number of rarefaction points for the regression: DiMA v5.0.9's (`calculate_entropy`);
40/// the paper states none.
41pub const RAREFACTION_MIN_POINTS: usize = 5;
42/// Lowest subsample percentage of the rarefaction grid (Tharanga et al. 2025, Fig. 2).
43pub const RAREFACTION_START: u64 = 50;
44/// Step of the rarefaction grid, in per cent: Fig. 2 ends "…, 90, 95, 100%"; DiMA v5.0.9 steps
45/// by 5 from the start.
46pub const RAREFACTION_STEP: u64 = 5;
47
48/// Counts of counts of the k-mers at one position.
49#[derive(Clone, Debug, PartialEq, Eq)]
50pub struct CountProfile {
51    support: u64,
52    distinct: u64,
53    /// `(count, number of distinct k-mers with that count)`, ascending by count.
54    frequencies: Vec<(u64, u64)>,
55}
56
57impl CountProfile {
58    /// Builds the profile from per-k-mer counts (zeros are ignored).
59    ///
60    /// # Errors
61    /// [`DimaError::Overflow`] if the counts sum beyond `u64::MAX`.
62    pub fn from_counts(counts: impl IntoIterator<Item = u64>) -> Result<Self> {
63        let mut v: Vec<u64> = counts.into_iter().filter(|&c| c > 0).collect();
64        v.sort_unstable();
65        let mut support = 0u64;
66        let mut frequencies: Vec<(u64, u64)> = Vec::new();
67        for c in &v {
68            support = support
69                .checked_add(*c)
70                .ok_or(DimaError::Overflow { what: "support" })?;
71            match frequencies.last_mut() {
72                Some((last, f)) if last == c => *f += 1,
73                _ => frequencies.push((*c, 1)),
74            }
75        }
76        Ok(Self {
77            support,
78            distinct: v.len() as u64,
79            frequencies,
80        })
81    }
82
83    /// Support *N*: the number of sequences with a valid k-mer.
84    #[must_use]
85    pub const fn support(&self) -> u64 {
86        self.support
87    }
88
89    /// Number of distinct k-mers *D*.
90    #[must_use]
91    pub const fn distinct(&self) -> u64 {
92        self.distinct
93    }
94
95    /// `(count, multiplicity)` pairs, ascending by count.
96    #[must_use]
97    pub fn frequencies(&self) -> &[(u64, u64)] {
98        &self.frequencies
99    }
100
101    /// Number of distinct k-mers seen exactly `count` times (f₁ for 1, f₂ for 2, …).
102    #[must_use]
103    pub fn with_count(&self, count: u64) -> u64 {
104        self.frequencies
105            .binary_search_by_key(&count, |&(c, _)| c)
106            .map_or(0, |i| self.frequencies[i].1)
107    }
108}
109
110/// The result of estimating the entropy of one position.
111#[derive(Clone, Copy, Debug, PartialEq)]
112pub struct Estimate {
113    /// The estimate in bits; `None` without support.
114    pub entropy: Option<f64>,
115    /// The observed (plug-in) entropy in bits; `None` without support.
116    pub observed: Option<f64>,
117    /// The method that produced `entropy`.
118    pub method: EntropyMethod,
119    /// Why the requested estimator was not used, if it was not.
120    pub fallback: Option<EntropyFallback>,
121}
122
123/// Estimates the entropy of a position with the requested estimator, applying the documented
124/// fallbacks (support ≤ T for `dima`; N = 1 for Miller–Madow and Chao–Wang–Jost).
125///
126/// # Errors
127/// [`DimaError::Internal`] if a reported value is not a finite number of at least 0 bits (it
128/// cannot be for valid counts; a violation is a bug).
129pub fn estimate(profile: &CountProfile, estimator: Estimator, threshold: u64) -> Result<Estimate> {
130    let Some(observed) = plug_in(profile) else {
131        return Ok(Estimate {
132            entropy: None,
133            observed: None,
134            method: EntropyMethod::NotEstimable,
135            fallback: None,
136        });
137    };
138    let plug = |fallback| Estimate {
139        entropy: Some(observed),
140        observed: Some(observed),
141        method: EntropyMethod::PlugIn,
142        fallback,
143    };
144    let corrected = |value: f64, method| Estimate {
145        entropy: Some(value),
146        observed: Some(observed),
147        method,
148        fallback: None,
149    };
150    let e = match estimator {
151        Estimator::Raw => plug(None),
152        Estimator::Dima => match dima_corrected(profile, threshold) {
153            Ok(v) => corrected(v, EntropyMethod::Dima),
154            Err(reason) => plug(Some(reason)),
155        },
156        Estimator::MillerMadow => match miller_madow(profile) {
157            Some(v) => corrected(v, EntropyMethod::MillerMadow),
158            None => plug(Some(EntropyFallback::SingleObservation)),
159        },
160        Estimator::ChaoWangJost => match chao_wang_jost(profile) {
161            Some(v) => corrected(v, EntropyMethod::ChaoWangJost),
162            None => plug(Some(EntropyFallback::SingleObservation)),
163        },
164    };
165    reportable(e, profile, threshold)
166}
167
168/// The postcondition of [`estimate`]: every reported entropy is a finite number of at least 0
169/// bits. The estimators guarantee it (see [`dima_corrected`] for the paper's correction), so a
170/// violation is a bug, never a property of the data.
171fn reportable(e: Estimate, profile: &CountProfile, threshold: u64) -> Result<Estimate> {
172    let valid = |v: Option<f64>| v.is_none_or(|x| (0.0..f64::INFINITY).contains(&x));
173    if valid(e.entropy) && valid(e.observed) {
174        Ok(e)
175    } else {
176        Err(DimaError::internal(format!(
177            "entropy {:?} (observed {:?}) from {:?} is not a finite number of at least 0 bits \
178             (support {}, threshold {threshold}, counts of counts {:?})",
179            e.entropy,
180            e.observed,
181            e.method,
182            profile.support(),
183            &profile.frequencies()[..profile.frequencies().len().min(8)],
184        )))
185    }
186}
187
188/// Plug-in Shannon entropy in bits, H = −Σ (c/N) log₂(c/N) (Shannon 1948); `None` when N = 0.
189#[must_use]
190pub fn plug_in(profile: &CountProfile) -> Option<f64> {
191    let n = profile.support;
192    if n == 0 {
193        return None;
194    }
195    let nf = n as f64;
196    let mut h = Neumaier::new();
197    for &(c, f) in &profile.frequencies {
198        if c != n {
199            let p = c as f64 / nf;
200            h.add(f as f64 * (-p * libm::log2(p)));
201        }
202    }
203    Some(h.total())
204}
205
206/// The paper's rarefaction grid for support `n` and threshold `t` (Fig. 2), with the step and
207/// start rounding of DiMA v5.0.9: R % from max(50, ⌈100·T/N⌉ rounded up to a multiple of 5) to
208/// 95 in steps of 5 (the 100% point is added separately). Empty when ⌈100·T/N⌉ > 95.
209#[must_use]
210pub fn rarefaction_grid(n: u64, t: u64) -> Vec<u64> {
211    if n == 0 {
212        return Vec::new();
213    }
214    // ⌈100·T/N⌉ in exact integer arithmetic (D55).
215    let x = (u128::from(t) * 100).div_ceil(u128::from(n));
216    let start = if x < u128::from(RAREFACTION_START) {
217        u128::from(RAREFACTION_START)
218    } else {
219        x.div_ceil(u128::from(RAREFACTION_STEP)) * u128::from(RAREFACTION_STEP)
220    };
221    #[allow(clippy::cast_possible_truncation)] // start ≤ 100 here or the range is empty.
222    let start = start.min(100) as u64;
223    (start..100).step_by(RAREFACTION_STEP as usize).collect()
224}
225
226/// Subsample size ⌈R·N/100⌉ for R % of `n` sequences (Fig. 2, "Upperbound").
227#[must_use]
228pub fn subsample_size(n: u64, percent: u64) -> u64 {
229    #[allow(clippy::cast_possible_truncation)] // ≤ n.
230    let size = (u128::from(n) * u128::from(percent)).div_ceil(100) as u64;
231    size
232}
233
234/// Expected plug-in entropy (bits) of a with-replacement subsample of `size` sequences drawn
235/// from the position's empirical k-mer distribution: `E[H(Multinomial(size, p̂))]`.
236///
237/// By linearity, `E[H] = Σ_k E[h(X_k)]` with `X_k ~ Binomial(size, c_k/N)` and
238/// h(x) = −(x/size) log₂(x/size); each binomial expectation is evaluated exactly (to 10⁻¹⁸ of
239/// the probability mass) by walking the pmf from its mode.
240#[must_use]
241pub fn expected_subsample_entropy(profile: &CountProfile, size: u64) -> f64 {
242    let n = profile.support;
243    if size <= 1 || n == 0 {
244        return 0.0;
245    }
246    let sf = size as f64;
247    let h = |x: u64| {
248        if x == 0 {
249            0.0
250        } else {
251            let q = x as f64 / sf;
252            -q * libm::log2(q)
253        }
254    };
255    let mut total = Neumaier::new();
256    for &(c, f) in &profile.frequencies {
257        if c == n {
258            continue; // p = 1: every subsample is pure, h = 0.
259        }
260        let p = c as f64 / n as f64;
261        let mut e = 0.0;
262        let w = binomial_walk(size, p, |x, w| e += w * h(x));
263        total.add(f as f64 * e / w);
264    }
265    total.total()
266}
267
268/// The `dima` estimate in bits: the exact expectation of the paper's procedure (Fig. 2).
269///
270/// The intercept is never negative: the expected subsample entropy never decreases with the
271/// subsample size n (the frequencies of n + 1 draws average those of their n + 1 subsets of n
272/// draws, and entropy is concave) and never exceeds the observed entropy (Jensen's inequality:
273/// a with-replacement subsample's expected frequencies are the observed ones), so the points
274/// never rise as 1/n grows, the least-squares slope is at most 0, and the intercept is at
275/// least the mean of the points, which is at least 0. The paper's fallback for a negative
276/// intercept therefore never applies; [`estimate`] checks the result like every other.
277///
278/// # Errors
279/// The reason the paper's procedure reports the observed entropy instead: support N ≤ T,
280/// fewer than five points, or a degenerate regression.
281pub fn dima_corrected(profile: &CountProfile, threshold: u64) -> Result<f64, EntropyFallback> {
282    let n = profile.support;
283    if n <= threshold {
284        return Err(EntropyFallback::SupportAtOrBelowThreshold);
285    }
286    let grid = rarefaction_grid(n, threshold);
287    if grid.len() + 1 < RAREFACTION_MIN_POINTS {
288        return Err(EntropyFallback::TooFewPoints);
289    }
290    let observed = plug_in(profile).ok_or(EntropyFallback::SupportAtOrBelowThreshold)?;
291    let mut xs = Vec::with_capacity(grid.len() + 1);
292    let mut ys = Vec::with_capacity(grid.len() + 1);
293    for r in grid {
294        let size = subsample_size(n, r);
295        xs.push(1.0 / size as f64);
296        ys.push(expected_subsample_entropy(profile, size));
297    }
298    // The 100% point is the full data set itself (not resampled), as in the paper.
299    xs.push(1.0 / n as f64);
300    ys.push(observed);
301    match ols_intercept(&xs, &ys) {
302        None => Err(EntropyFallback::DegenerateRegression),
303        Some(b0) => Ok(if b0 == 0.0 { 0.0 } else { b0 }),
304    }
305}
306
307/// Miller–Madow estimate in bits, H + (D − 1)/(2N ln 2) (Miller 1955); `None` when N < 2.
308#[must_use]
309pub fn miller_madow(profile: &CountProfile) -> Option<f64> {
310    let n = profile.support;
311    if n < 2 {
312        return None;
313    }
314    let h = plug_in(profile)?;
315    Some(h + (profile.distinct - 1) as f64 / (2.0 * n as f64 * LN_2))
316}
317
318/// The coverage-adjustment constant A of Chao et al. (2013), shared with
319/// [`sample_coverage`]: 2f₂/((N−1)f₁ + 2f₂) if f₂ > 0, else 2/((N−1)(f₁−1) + 2) if f₁ > 0, else 1.
320fn coverage_constant(n: u64, f1: u64, f2: u64) -> f64 {
321    let n1 = u128::from(n - 1);
322    if f2 > 0 {
323        (2 * u128::from(f2)) as f64 / (n1 * u128::from(f1) + 2 * u128::from(f2)) as f64
324    } else if f1 > 0 {
325        2.0 / (n1 * u128::from(f1 - 1) + 2) as f64
326    } else {
327        1.0
328    }
329}
330
331/// Chao–Wang–Jost (2013) entropy estimate in bits; `None` when N < 2.
332///
333/// Ĥ = Σ_{1≤c<N} f_c (c/N)(ψ(N) − ψ(c)) + (f₁/N)(1−A)^{1−N}(−ln A − Σ_{r=1}^{N−1}(1−A)^r/r).
334/// Because −ln A = Σ_{r≥1}(1−A)^r/r, the second term equals (f₁/N)(1−A)·Φ(1−A, 1, N), where
335/// Φ(1−A, 1, N) = Σ_{j≥0}(1−A)^j/(N+j) is the Lerch transcendent, evaluated exactly (up to
336/// rounding) in a time independent of N (`numeric::lerch_phi1`), so (1−A)^{1−N} is never formed.
337#[must_use]
338pub fn chao_wang_jost(profile: &CountProfile) -> Option<f64> {
339    let n = profile.support;
340    if n < 2 {
341        return None;
342    }
343    let nf = n as f64;
344    let mut part1 = Neumaier::new();
345    for &(c, f) in &profile.frequencies {
346        if c < n {
347            part1.add(f as f64 * (c as f64 / nf) * digamma_difference(n, c));
348        }
349    }
350    let f1 = profile.with_count(1);
351    let f2 = profile.with_count(2);
352    let a = coverage_constant(n, f1, f2);
353    let part2 = if f1 == 0 || a >= 1.0 {
354        0.0
355    } else {
356        f1 as f64 / nf * (1.0 - a) * lerch_phi1(n, a)
357    };
358    let h = (part1.total() + part2) / LN_2;
359    Some(if h == 0.0 { 0.0 } else { h })
360}
361
362/// Estimated sample coverage Ĉ = 1 − (f₁/N)·A' (Chao & Jost 2012, Eq. 4a), where
363/// A' = (N−1)f₁/((N−1)f₁ + 2f₂), or (N−1)(f₁−1)/((N−1)(f₁−1) + 2) when f₂ = 0; 1 when f₁ = 0.
364/// `None` when N < 2.
365#[must_use]
366pub fn sample_coverage(profile: &CountProfile) -> Option<f64> {
367    let n = profile.support;
368    if n < 2 {
369        return None;
370    }
371    let f1 = profile.with_count(1);
372    if f1 == 0 {
373        return Some(1.0);
374    }
375    let f2 = profile.with_count(2);
376    let n1 = u128::from(n - 1);
377    let ratio = if f2 > 0 {
378        (n1 * u128::from(f1)) as f64 / (n1 * u128::from(f1) + 2 * u128::from(f2)) as f64
379    } else {
380        (n1 * u128::from(f1 - 1)) as f64 / (n1 * u128::from(f1 - 1) + 2) as f64
381    };
382    Some(1.0 - f1 as f64 / n as f64 * ratio)
383}
384
385#[cfg(test)]
386mod tests {
387    use super::*;
388
389    fn profile(counts: &[u64]) -> CountProfile {
390        CountProfile::from_counts(counts.iter().copied()).unwrap()
391    }
392
393    /// MERS-CoV spike position 25 (Tharanga et al. 2025, Fig. 1C dataset).
394    const POS25: [u64; 10] = [129, 14, 9, 6, 4, 4, 1, 1, 1, 1];
395
396    /// Agreement with a reference value by the rule of the integration tests
397    /// (`tests/common/mod.rs`): within a relative 1e-13, so a zero must be exactly zero.
398    fn close(a: f64, b: f64) -> bool {
399        (a - b).abs() <= 1e-13 * b.abs()
400    }
401
402    #[test]
403    fn profile_basics() {
404        let p = profile(&[3, 0, 1, 1, 2, 3, 3]);
405        assert_eq!(p.support(), 13);
406        assert_eq!(p.distinct(), 6);
407        assert_eq!(p.frequencies(), &[(1, 2), (2, 1), (3, 3)]);
408        assert_eq!(p.with_count(1), 2);
409        assert_eq!(p.with_count(4), 0);
410        assert!(matches!(
411            CountProfile::from_counts([u64::MAX, 1]),
412            Err(DimaError::Overflow { .. })
413        ));
414    }
415
416    /// The estimators at position 25, against the reference implementation's values for
417    /// `positions[24]` of `dima_reference.py analyze -i samples/mers_spike_aa.fasta` (with `-s 30`
418    /// for T = 30; the same values as `MERS_AA_T30_POS25` and `MERS_AA_T100_POS25` in
419    /// `tests/paper_expected/mod.rs`). Each is also the exact value correctly rounded.
420    #[test]
421    fn golden_values_position_25() {
422        let p = profile(&POS25);
423        assert_eq!(p.support(), 170);
424        assert!(close(plug_in(&p).unwrap(), 1.422_388_672_162_913_5));
425        assert!(close(
426            dima_corrected(&p, 30).unwrap(),
427            1.445_053_291_028_629_3
428        ));
429        assert!(close(
430            dima_corrected(&p, 100).unwrap(),
431            1.461_701_237_532_242_2
432        ));
433        assert!(close(miller_madow(&p).unwrap(), 1.460_577_658_539_386_1));
434        assert!(close(chao_wang_jost(&p).unwrap(), 1.490_071_840_297_816));
435        // 1 − (4/170)·(507/509), exactly 42251/43265.
436        assert!(close(sample_coverage(&p).unwrap(), 42_251.0 / 43_265.0));
437    }
438
439    #[test]
440    fn grid_follows_figure_2() {
441        assert_eq!(
442            rarefaction_grid(170, 30),
443            vec![50, 55, 60, 65, 70, 75, 80, 85, 90, 95]
444        );
445        // ⌈100·100/170⌉ = 59 → 60.
446        assert_eq!(
447            rarefaction_grid(170, 100),
448            vec![60, 65, 70, 75, 80, 85, 90, 95]
449        );
450        // Exact integer ceiling: T = 55, N = 100 → 55 (a float computation gives 56 → 60).
451        assert_eq!(rarefaction_grid(100, 55)[0], 55);
452        // ⌈100·100/101⌉ = 100 → empty.
453        assert!(rarefaction_grid(101, 100).is_empty());
454        assert_eq!(rarefaction_grid(125, 100), vec![80, 85, 90, 95]);
455        assert_eq!(subsample_size(170, 50), 85);
456        assert_eq!(subsample_size(171, 50), 86);
457        assert_eq!(
458            subsample_size(u64::MAX, 95),
459            (u128::from(u64::MAX) * 95).div_ceil(100) as u64
460        );
461    }
462
463    #[test]
464    fn dima_fallbacks() {
465        let p = profile(&POS25);
466        assert_eq!(
467            dima_corrected(&p, 170),
468            Err(EntropyFallback::SupportAtOrBelowThreshold)
469        );
470        assert_eq!(
471            dima_corrected(&p, 500),
472            Err(EntropyFallback::SupportAtOrBelowThreshold)
473        );
474        // N = 125, T = 100: x = 80 → 4 grid points + 100% = 5 points: estimated.
475        let q = profile(&[100, 20, 5]);
476        assert!(dima_corrected(&q, 100).is_ok());
477        // N = 120, T = 100: x = 84 → 85, 90, 95 + 100% = 4 points: too few.
478        let q = profile(&[100, 15, 5]);
479        assert_eq!(dima_corrected(&q, 100), Err(EntropyFallback::TooFewPoints));
480        // A conserved position: every expected entropy is 0, intercept 0 (not negative).
481        assert_eq!(dima_corrected(&profile(&[500]), 100), Ok(0.0));
482        let e = estimate(&profile(&[500]), Estimator::Dima, 100).unwrap();
483        assert_eq!(e.entropy, Some(0.0));
484        assert!(e.entropy.unwrap().is_sign_positive());
485    }
486
487    #[test]
488    fn estimate_methods_and_fallbacks() {
489        let empty = profile(&[]);
490        let e = estimate(&empty, Estimator::Dima, 100).unwrap();
491        assert_eq!(e.entropy, None);
492        assert_eq!(e.observed, None);
493        assert_eq!(e.method, EntropyMethod::NotEstimable);
494        let one = profile(&[1]);
495        for est in [Estimator::MillerMadow, Estimator::ChaoWangJost] {
496            let e = estimate(&one, est, 100).unwrap();
497            assert_eq!(e.entropy, Some(0.0));
498            assert_eq!(e.method, EntropyMethod::PlugIn);
499            assert_eq!(e.fallback, Some(EntropyFallback::SingleObservation));
500        }
501        let e = estimate(&one, Estimator::Dima, 100).unwrap();
502        assert_eq!(e.fallback, Some(EntropyFallback::SupportAtOrBelowThreshold));
503        let p = profile(&POS25);
504        let e = estimate(&p, Estimator::Raw, 100).unwrap();
505        assert_eq!((e.method, e.fallback), (EntropyMethod::PlugIn, None));
506        assert_eq!(e.entropy, e.observed);
507        let e = estimate(&p, Estimator::Dima, 30).unwrap();
508        assert_eq!(e.method, EntropyMethod::Dima);
509        assert!(e.entropy.unwrap() > e.observed.unwrap());
510    }
511
512    /// E[H_n] equals brute-force enumeration over all multinomial outcomes.
513    #[test]
514    fn expected_subsample_entropy_matches_enumeration() {
515        fn enumerate(probs: &[f64], n: u64) -> f64 {
516            // Recursive enumeration of all count vectors summing to n.
517            fn rec(probs: &[f64], n: u64, left: u64, counts: &mut Vec<u64>, acc: &mut f64) {
518                if counts.len() + 1 == probs.len() {
519                    counts.push(left);
520                    let mut logp = libm::lgamma(n as f64 + 1.0);
521                    let mut h = 0.0;
522                    for (&c, &p) in counts.iter().zip(probs) {
523                        logp += c as f64 * p.ln() - libm::lgamma(c as f64 + 1.0);
524                        if c > 0 {
525                            let q = c as f64 / n as f64;
526                            h -= q * q.log2();
527                        }
528                    }
529                    *acc += logp.exp() * h;
530                    counts.pop();
531                    return;
532                }
533                for c in 0..=left {
534                    counts.push(c);
535                    rec(probs, n, left - c, counts, acc);
536                    counts.pop();
537                }
538            }
539            let mut acc = 0.0;
540            rec(probs, n, n, &mut Vec::new(), &mut acc);
541            acc
542        }
543        for counts in [
544            &[3u64, 1][..],
545            &[2, 2, 1],
546            &[5, 3, 2, 1, 1],
547            &[1, 1, 1, 1],
548            &[7, 4],
549        ] {
550            let p = profile(counts);
551            let total: u64 = counts.iter().sum();
552            let probs: Vec<f64> = counts.iter().map(|&c| c as f64 / total as f64).collect();
553            for size in 1..=12 {
554                let got = expected_subsample_entropy(&p, size);
555                let want = enumerate(&probs, size);
556                assert!(
557                    (got - want).abs() < 1e-12,
558                    "{counts:?} n={size}: {got} vs {want}"
559                );
560            }
561        }
562        // E[H_1] = 0 and a pure position stays 0.
563        assert_eq!(expected_subsample_entropy(&profile(&POS25), 1), 0.0);
564        assert_eq!(expected_subsample_entropy(&profile(&[50]), 30), 0.0);
565    }
566
567    #[test]
568    fn miller_madow_and_cwj_edge_cases() {
569        // All identical: every estimator gives 0.
570        let p = profile(&[40]);
571        assert_eq!(miller_madow(&p), Some(0.0));
572        assert_eq!(chao_wang_jost(&p), Some(0.0));
573        assert_eq!(sample_coverage(&p), Some(1.0));
574        // f1 = 1, f2 = 0: A = 1, part 2 vanishes.
575        let p = profile(&[10, 1]);
576        let part1 = (10.0 / 11.0 * digamma_difference(11, 10)
577            + 1.0 / 11.0 * digamma_difference(11, 1))
578            / LN_2;
579        assert!(close(chao_wang_jost(&p).unwrap(), part1));
580        // All singletons (f1 = N): defined and above the plug-in value log2(N).
581        let p = profile(&[1; 50]);
582        assert!(chao_wang_jost(&p).unwrap() > 50f64.log2());
583        assert!(sample_coverage(&p).unwrap() < 0.05);
584        // Profiles around A·N ≈ 9 are finite and positive.
585        for (f1, f2) in [(30u64, 3u64), (20, 1), (200, 50), (3, 1)] {
586            let mut counts = vec![1; f1 as usize];
587            counts.extend(std::iter::repeat_n(2, f2 as usize));
588            counts.push(1000);
589            let v = chao_wang_jost(&profile(&counts)).unwrap();
590            assert!(v.is_finite() && v > 0.0);
591        }
592        // N = 17.5 million with A·N ≈ 8.9, where summing the term as written loses 8 digits; the
593        // value (mpmath at 50 digits, and the reference implementation) is 0.014173273093526109.
594        let mut counts = vec![17_490_100u64];
595        counts.extend(std::iter::repeat_n(1, 1000));
596        counts.extend(std::iter::repeat_n(2, 4450));
597        let v = chao_wang_jost(&profile(&counts)).unwrap();
598        assert!(
599            (v - 0.014_173_273_093_526_109).abs() <= 2.0 * f64::EPSILON * v,
600            "{v}"
601        );
602        // Large N is stable and fast.
603        let mut big = vec![1_000_000u64, 50_000, 3, 2, 2];
604        big.extend(std::iter::repeat_n(1, 1000));
605        let p = profile(&big);
606        let c = chao_wang_jost(&p).unwrap();
607        let h = plug_in(&p).unwrap();
608        assert!(c > h && c.is_finite());
609    }
610
611    #[test]
612    fn coverage_cases() {
613        assert_eq!(sample_coverage(&profile(&[1])), None);
614        assert_eq!(sample_coverage(&profile(&[])), None);
615        // f2 = 0 branch: N = 4, f1 = 1 → A' = 0 → Ĉ = 1.
616        assert_eq!(
617            sample_coverage(&profile(&[3, 1])).map(|c| c.to_bits()),
618            Some(1.0f64.to_bits())
619        );
620        let c = sample_coverage(&profile(&[3, 1, 1])).unwrap();
621        // N = 5, f1 = 2, f2 = 0: 1 − (2/5)·(4·1/(4·1+2)) = 1 − 0.4·(2/3).
622        assert!(close(c, 1.0 - 0.4 * (2.0 / 3.0)));
623    }
624
625    /// The regression points of [`dima_corrected`] (resampled points, then the 100% point).
626    fn points(p: &CountProfile, threshold: u64) -> Vec<(f64, f64)> {
627        let n = p.support;
628        let mut out: Vec<(f64, f64)> = rarefaction_grid(n, threshold)
629            .into_iter()
630            .map(|r| {
631                let size = subsample_size(n, r);
632                (1.0 / size as f64, expected_subsample_entropy(p, size))
633            })
634            .collect();
635        out.push((1.0 / n as f64, plug_in(p).unwrap()));
636        out
637    }
638
639    /// The proof that the expected intercept is never negative, step by step: the expected
640    /// subsample entropy never falls as n grows, never exceeds the observed entropy, and the
641    /// intercept is at least the mean of the points.
642    fn intercept_bounds_hold(counts: &[u64], threshold: u64) {
643        let p = profile(counts);
644        let observed = plug_in(&p).unwrap();
645        let tol = |x: f64| 1e-12 * x.abs().max(1e-300) + 1e-15;
646        let mut pts = points(&p, threshold);
647        pts.sort_by(|a, b| b.0.total_cmp(&a.0)); // by n, ascending
648        for w in pts.windows(2) {
649            assert!(
650                w[1].1 >= w[0].1 - tol(w[1].1),
651                "{counts:?}: E[H_n] fell: {w:?}"
652            );
653        }
654        for &(_, y) in &pts {
655            assert!(
656                y <= observed + tol(observed),
657                "{counts:?}: {y} > {observed}"
658            );
659        }
660        let mean = pts.iter().map(|&(_, y)| y).sum::<f64>() / pts.len() as f64;
661        if let Ok(h) = dima_corrected(&p, threshold) {
662            assert!(
663                h >= mean - tol(mean) && h >= 0.0,
664                "{counts:?}: {h} < {mean}"
665            );
666        }
667    }
668
669    #[test]
670    fn a_degenerate_regression_falls_back() {
671        // N = 3, T = 2: the grid is 70..95% and every subsample size rounds up to 3 = N, so all
672        // the points share one x and no line is defined.
673        assert_eq!(
674            dima_corrected(&profile(&[2, 1]), 2),
675            Err(EntropyFallback::DegenerateRegression)
676        );
677    }
678
679    #[test]
680    fn reported_entropies_are_finite_and_not_negative() {
681        let p = profile(&[3, 1]);
682        let e = |entropy, observed| Estimate {
683            entropy,
684            observed,
685            method: EntropyMethod::Dima,
686            fallback: None,
687        };
688        for ok in [Some(0.0), Some(-0.0), Some(1.5), None] {
689            assert!(reportable(e(ok, ok), &p, 1).is_ok());
690        }
691        for bad in [-1e-300, -0.1, f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
692            for (a, b) in [(Some(bad), Some(0.5)), (Some(0.5), Some(bad))] {
693                let err = reportable(e(a, b), &p, 1).unwrap_err();
694                assert!(matches!(err, DimaError::Internal { .. }), "{err}");
695            }
696        }
697    }
698
699    #[test]
700    fn the_expected_intercept_is_never_negative_near_conservation() {
701        // One to five sequences differing from the Index, where single random runs of the paper's
702        // procedure most often give a negative intercept; T near N gives the shortest grids.
703        for n in [101, 110, 125, 130, 171, 500, 1_000, 10_000, 1_000_000] {
704            for minor in [vec![1], vec![1, 1], vec![2], vec![1, 1, 1, 1, 1], vec![5]] {
705                let mut counts = vec![n - minor.iter().sum::<u64>()];
706                counts.extend(&minor);
707                for t in [1, 30, 100, n / 2, n - 1] {
708                    intercept_bounds_hold(&counts, t);
709                }
710            }
711        }
712    }
713
714    proptest::proptest! {
715        #[test]
716        fn the_expected_intercept_is_never_negative(
717            counts in proptest::collection::vec(1u64..400, 1..12),
718            t_fraction in 0.0f64..1.0,
719        ) {
720            let n: u64 = counts.iter().sum();
721            #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
722            let threshold = ((n as f64 * t_fraction) as u64).max(1);
723            intercept_bounds_hold(&counts, threshold);
724        }
725    }
726}