Skip to main content

solow_cv/
bootstrap.rs

1//! Bootstrap resampling for confidence intervals on any scalar statistic.
2//!
3//! The [`bootstrap_ci`] entry point takes a sample size `n`, a `statistic`
4//! callback that computes a scalar from a resampled index list, the number
5//! of bootstrap replicates, a confidence level, and a bootstrap method, and
6//! returns the point estimate together with a two-sided confidence
7//! interval. Passing indices instead of raw data keeps the callback typed
8//! independently of the underlying container — the caller closes over
9//! whatever data structure they use.
10//!
11//! Three interval kinds are supported:
12//!
13//! * [`BootstrapMethod::Percentile`] — the classical `[Q_{α/2}, Q_{1−α/2}]`
14//!   percentile of the bootstrap distribution.
15//! * [`BootstrapMethod::Basic`] — the "reverse-percentile" `[2θ̂ - Q_{1−α/2},
16//!   2θ̂ - Q_{α/2}]` interval, which corrects for asymmetric bias.
17//! * [`BootstrapMethod::Bca`] — Efron's bias-corrected and accelerated
18//!   interval, using a jackknife estimate of the acceleration constant.
19//!   BCa requires `n ≥ 2` and adjusts the percentile levels for bias `z₀`
20//!   and skewness `â`; it is the recommended default for asymmetric or
21//!   biased statistics.
22//!
23//! Resampling uses the same deterministic MMIX-LCG as the other splitters,
24//! so a fixed seed produces byte-identical bootstrap replicates on every
25//! run and platform.
26
27use solow_core::{Error, Result};
28
29/// Bootstrap confidence-interval method.
30#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
31#[derive(Copy, Clone, Debug, PartialEq, Eq)]
32pub enum BootstrapMethod {
33    /// Classical percentile interval.
34    Percentile,
35    /// Reverse-percentile ("basic") interval.
36    Basic,
37    /// Efron's bias-corrected and accelerated interval.
38    Bca,
39}
40
41/// A point estimate together with its bootstrap confidence interval.
42#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
43#[derive(Clone, Debug)]
44pub struct BootstrapCi {
45    /// The statistic evaluated on the original sample.
46    pub point: f64,
47    /// Two-sided confidence-interval lower bound.
48    pub low: f64,
49    /// Two-sided confidence-interval upper bound.
50    pub high: f64,
51    /// Confidence level `1 - α` this interval was computed at.
52    pub confidence: f64,
53    /// The method that produced this interval.
54    pub method: BootstrapMethod,
55    /// Sorted bootstrap replicates of the statistic.
56    pub replicates: Vec<f64>,
57}
58
59impl BootstrapCi {
60    /// Standard error of the statistic: standard deviation of the bootstrap
61    /// replicates.
62    pub fn standard_error(&self) -> f64 {
63        let n = self.replicates.len() as f64;
64        if n <= 1.0 {
65            return 0.0;
66        }
67        let mean: f64 = self.replicates.iter().sum::<f64>() / n;
68        let s2: f64 = self
69            .replicates
70            .iter()
71            .map(|v| (v - mean).powi(2))
72            .sum::<f64>()
73            / (n - 1.0);
74        s2.sqrt()
75    }
76}
77
78// ---------------------------------------------------------------------------
79// Deterministic PRNG (MMIX 64-bit LCG) — same constants as splitters.rs
80// ---------------------------------------------------------------------------
81
82fn lcg_next(state: &mut u64) -> u64 {
83    *state = state
84        .wrapping_mul(6_364_136_223_846_793_005)
85        .wrapping_add(1_442_695_040_888_963_407);
86    *state
87}
88
89fn uniform_index(state: &mut u64, n: u64) -> usize {
90    let max = u64::MAX - (u64::MAX % n);
91    loop {
92        let r = lcg_next(state);
93        if r < max {
94            return (r % n) as usize;
95        }
96    }
97}
98
99// ---------------------------------------------------------------------------
100// bootstrap_ci
101// ---------------------------------------------------------------------------
102
103/// Compute a bootstrap confidence interval for `statistic(indices)` on a
104/// sample of size `n`.
105///
106/// `statistic` is called once on the identity indices to produce the point
107/// estimate, then `n_boot` times on `n`-of-`n` resamples-with-replacement.
108/// Any error from the callback is propagated. `n_boot` should be `≥ 999`
109/// for tight quantile estimates (a typical default is 1000-2000).
110pub fn bootstrap_ci<F>(
111    n: usize,
112    statistic: F,
113    n_boot: usize,
114    confidence: f64,
115    method: BootstrapMethod,
116    seed: u64,
117) -> Result<BootstrapCi>
118where
119    F: Fn(&[usize]) -> Result<f64>,
120{
121    if n == 0 {
122        return Err(Error::Value("bootstrap_ci: n must be positive".into()));
123    }
124    if n_boot == 0 {
125        return Err(Error::Value("bootstrap_ci: n_boot must be ≥ 1".into()));
126    }
127    if !(0.0 < confidence && confidence < 1.0) {
128        return Err(Error::Value(format!(
129            "bootstrap_ci: confidence must be in (0, 1), got {confidence}"
130        )));
131    }
132    let identity: Vec<usize> = (0..n).collect();
133    let point = statistic(&identity)?;
134    if !point.is_finite() {
135        return Err(Error::Value(
136            "bootstrap_ci: statistic returned a non-finite value on the full sample".into(),
137        ));
138    }
139
140    let mut state = seed.wrapping_add(0x9E37_79B9_7F4A_7C15);
141    let mut replicates = Vec::with_capacity(n_boot);
142    let mut sample = vec![0usize; n];
143    for _ in 0..n_boot {
144        for slot in sample.iter_mut() {
145            *slot = uniform_index(&mut state, n as u64);
146        }
147        let s = statistic(&sample)?;
148        if s.is_finite() {
149            replicates.push(s);
150        }
151    }
152    if replicates.is_empty() {
153        return Err(Error::Value(
154            "bootstrap_ci: every bootstrap replicate produced a non-finite value".into(),
155        ));
156    }
157    replicates.sort_by(|a, b| a.partial_cmp(b).unwrap());
158
159    let alpha = 1.0 - confidence;
160    let (lo_q, hi_q) = match method {
161        BootstrapMethod::Percentile => (alpha / 2.0, 1.0 - alpha / 2.0),
162        BootstrapMethod::Basic => (alpha / 2.0, 1.0 - alpha / 2.0),
163        BootstrapMethod::Bca => bca_quantiles(&replicates, point, &statistic, n, alpha)?,
164    };
165    let q_low = quantile_sorted(&replicates, lo_q);
166    let q_high = quantile_sorted(&replicates, hi_q);
167    let (low, high) = match method {
168        BootstrapMethod::Percentile | BootstrapMethod::Bca => (q_low, q_high),
169        BootstrapMethod::Basic => (2.0 * point - q_high, 2.0 * point - q_low),
170    };
171    Ok(BootstrapCi {
172        point,
173        low,
174        high,
175        confidence,
176        method,
177        replicates,
178    })
179}
180
181fn quantile_sorted(sorted: &[f64], q: f64) -> f64 {
182    let n = sorted.len();
183    if n == 0 {
184        return f64::NAN;
185    }
186    // Type-7 linear interpolation (R's default; matches numpy.quantile).
187    let h = (n as f64 - 1.0) * q;
188    let lo = h.floor() as usize;
189    let hi = (lo + 1).min(n - 1);
190    let frac = h - lo as f64;
191    (1.0 - frac) * sorted[lo] + frac * sorted[hi]
192}
193
194fn bca_quantiles<F>(
195    sorted: &[f64],
196    point: f64,
197    statistic: &F,
198    n: usize,
199    alpha: f64,
200) -> Result<(f64, f64)>
201where
202    F: Fn(&[usize]) -> Result<f64>,
203{
204    if n < 2 {
205        return Err(Error::Value(
206            "bootstrap_ci: BCa requires n ≥ 2 for a jackknife acceleration estimate".into(),
207        ));
208    }
209    // Bias-correction z0 from the fraction of replicates below the point estimate.
210    let below = sorted.iter().filter(|&&v| v < point).count() as f64;
211    let mut prop = below / sorted.len() as f64;
212    // Clip to avoid ±∞ from the inverse-normal at the ends.
213    let eps = 1.0 / (2.0 * sorted.len() as f64);
214    prop = prop.clamp(eps, 1.0 - eps);
215    let z0 = normal_inverse_cdf(prop);
216
217    // Jackknife acceleration: replace each index by every other row once.
218    let mut jack = Vec::with_capacity(n);
219    let mut leave_one: Vec<usize> = Vec::with_capacity(n - 1);
220    for i in 0..n {
221        leave_one.clear();
222        for j in 0..n {
223            if j != i {
224                leave_one.push(j);
225            }
226        }
227        let s = statistic(&leave_one)?;
228        if s.is_finite() {
229            jack.push(s);
230        }
231    }
232    if jack.is_empty() {
233        return Err(Error::Value(
234            "bootstrap_ci: jackknife produced no finite values".into(),
235        ));
236    }
237    let jm: f64 = jack.iter().sum::<f64>() / jack.len() as f64;
238    let num: f64 = jack.iter().map(|v| (jm - v).powi(3)).sum();
239    let den: f64 = jack.iter().map(|v| (jm - v).powi(2)).sum();
240    let a = if den > 0.0 {
241        num / (6.0 * den.powf(1.5))
242    } else {
243        0.0
244    };
245
246    let z_alpha_lo = normal_inverse_cdf(alpha / 2.0);
247    let z_alpha_hi = normal_inverse_cdf(1.0 - alpha / 2.0);
248    let adj = |z: f64| {
249        let denom = 1.0 - a * (z0 + z);
250        // Guard against a degenerate acceleration that would flip the sign.
251        if denom == 0.0 {
252            return normal_cdf(z0 + z);
253        }
254        normal_cdf(z0 + (z0 + z) / denom)
255    };
256    let lo_q = adj(z_alpha_lo).clamp(1e-6, 1.0 - 1e-6);
257    let hi_q = adj(z_alpha_hi).clamp(1e-6, 1.0 - 1e-6);
258    Ok((lo_q, hi_q))
259}
260
261// ---------------------------------------------------------------------------
262// Normal CDF / inverse CDF (Acklam's rational approximation)
263// ---------------------------------------------------------------------------
264
265fn normal_cdf(x: f64) -> f64 {
266    0.5 * (1.0 + erf(x / std::f64::consts::SQRT_2))
267}
268
269fn erf(x: f64) -> f64 {
270    // Abramowitz & Stegun 7.1.26 — accurate to ~1.5e-7, which is plenty for
271    // the BCa quantile adjustment (whose input error dominates the erf
272    // approximation error at these confidence levels).
273    let a1 = 0.254_829_592;
274    let a2 = -0.284_496_736;
275    let a3 = 1.421_413_741;
276    let a4 = -1.453_152_027;
277    let a5 = 1.061_405_429;
278    let p = 0.327_591_1;
279    let sign = if x < 0.0 { -1.0 } else { 1.0 };
280    let x = x.abs();
281    let t = 1.0 / (1.0 + p * x);
282    let y = 1.0 - (((((a5 * t + a4) * t) + a3) * t + a2) * t + a1) * t * (-(x * x)).exp();
283    sign * y
284}
285
286fn normal_inverse_cdf(p: f64) -> f64 {
287    // Peter Acklam's rational approximation for the standard-normal inverse
288    // CDF (max relative error ~1.15e-9 in central region; ~1e-6 in tails).
289    let p_low = 0.02425;
290    let p_high = 1.0 - p_low;
291    if p <= 0.0 {
292        return f64::NEG_INFINITY;
293    }
294    if p >= 1.0 {
295        return f64::INFINITY;
296    }
297    let a = [
298        -3.969_683_028_665_376e1,
299        2.209_460_984_245_205e2,
300        -2.759_285_104_469_687e2,
301        1.383_577_518_672_690e2,
302        -3.066_479_806_614_716e1,
303        2.506_628_277_459_239,
304    ];
305    let b = [
306        -5.447_609_879_822_406e1,
307        1.615_858_368_580_409e2,
308        -1.556_989_798_598_866e2,
309        6.680_131_188_771_972e1,
310        -1.328_068_155_288_572e1,
311    ];
312    let c = [
313        -7.784_894_002_430_293e-3,
314        -3.223_964_580_411_365e-1,
315        -2.400_758_277_161_838,
316        -2.549_732_539_343_734,
317        4.374_664_141_464_968,
318        2.938_163_982_698_783,
319    ];
320    let d = [
321        7.784_695_709_041_462e-3,
322        3.224_671_290_700_398e-1,
323        2.445_134_137_142_996,
324        3.754_408_661_907_416,
325    ];
326    if p < p_low {
327        let q = (-2.0 * p.ln()).sqrt();
328        (((((c[0] * q + c[1]) * q + c[2]) * q + c[3]) * q + c[4]) * q + c[5])
329            / ((((d[0] * q + d[1]) * q + d[2]) * q + d[3]) * q + 1.0)
330    } else if p <= p_high {
331        let q = p - 0.5;
332        let r = q * q;
333        (((((a[0] * r + a[1]) * r + a[2]) * r + a[3]) * r + a[4]) * r + a[5]) * q
334            / (((((b[0] * r + b[1]) * r + b[2]) * r + b[3]) * r + b[4]) * r + 1.0)
335    } else {
336        let q = (-2.0 * (1.0 - p).ln()).sqrt();
337        -(((((c[0] * q + c[1]) * q + c[2]) * q + c[3]) * q + c[4]) * q + c[5])
338            / ((((d[0] * q + d[1]) * q + d[2]) * q + d[3]) * q + 1.0)
339    }
340}