Skip to main content

hpr_analysis/
statistics.rs

1//! Summaries of a sample of numbers: the spread of a Monte Carlo run's apogees, say.
2//!
3//! A [`Distribution`] keeps every value, sorted, and the number of samples that were tried, so a
4//! sample that failed or never gave a value (a flight with no apogee) is counted, not dropped:
5//! its share is [`Distribution::missing`] of [`Distribution::attempted`], and a probability is
6//! reported as the bounds those unknowns allow ([`Distribution::share_at_least`]).
7//!
8//! - **Mean and standard deviation** are taken on the values shifted by the smallest one, the
9//!   standard deviation by the two-pass formula with `n − 1` (T. F. Chan, G. H. Golub and R. J.
10//!   LeVeque, "Algorithms for computing the sample variance: analysis and recommendations", *The
11//!   American Statistician* 37(3), 242–247, 1983, <https://doi.org/10.2307/2683386>). Shifting
12//!   by a value of the sample keeps the sums small, and makes a sample of equal values give that
13//!   value and a deviation of exactly zero.
14//! - **Quantiles** are Hyndman and Fan's definition 7, linear between order statistics, the
15//!   default of R and NumPy: with the values sorted `x₀ ≤ … ≤ xₙ₋₁` and `h = (n − 1) p`,
16//!   `Q(p) = x⌊h⌋ + (h − ⌊h⌋)(x⌊h⌋₊₁ − x⌊h⌋)` (R. J. Hyndman and Y. Fan, "Sample quantiles in
17//!   statistical packages", *The American Statistician* 50(4), 361–365, 1996,
18//!   <https://doi.org/10.2307/2684934>).
19//! - **Quantiles counting the missing runs** ([`Distribution::quantile_counting_missing`]) take
20//!   the same definition over every run tried, `h = (N − 1) p` with `N` the runs tried, each run
21//!   with no value placed past one end of the values (as `+∞` above the largest, or `−∞` below
22//!   the smallest). That is the worst case the missing runs allow: if they all lie beyond that
23//!   end, the quantile of every run tried is this one. Where the interpolation puts weight on a
24//!   missing run the quantile is [`CountedQuantile::Unbounded`]: the runs that gave a value can't bound it.
25//!
26//! Every sum runs over the sorted values in order, so a summary is bit-for-bit the same however
27//! the values were computed, in parallel or not.
28
29use serde::{Deserialize, Serialize};
30
31use crate::error::AnalysisError;
32
33/// The values a sample of runs gave, sorted, and how many runs were tried. It serializes as
34/// those two, and reads back through [`Distribution::new`]'s checks.
35#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
36#[serde(try_from = "DistributionData")]
37pub struct Distribution {
38    attempted: usize,
39    sorted: Vec<f64>,
40}
41
42/// The serialized form of a [`Distribution`].
43#[derive(Deserialize)]
44#[serde(deny_unknown_fields)]
45struct DistributionData {
46    attempted: usize,
47    sorted: Vec<f64>,
48}
49
50impl TryFrom<DistributionData> for Distribution {
51    type Error = AnalysisError;
52
53    fn try_from(data: DistributionData) -> Result<Self, AnalysisError> {
54        Self::new(data.sorted, data.attempted)
55    }
56}
57
58/// The usual numbers of a [`Distribution`], for a report.
59#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
60pub struct Summary {
61    /// The runs tried.
62    pub attempted: usize,
63    /// The runs that gave a value.
64    pub count: usize,
65    /// The mean, `None` with no values.
66    pub mean: Option<f64>,
67    /// The sample standard deviation (`n − 1`), `None` with fewer than two values.
68    pub standard_deviation: Option<f64>,
69    /// The smallest value.
70    pub min: Option<f64>,
71    /// The 5th percentile ([`Distribution::quantile`]).
72    pub p05: Option<f64>,
73    /// The median.
74    pub p50: Option<f64>,
75    /// The 95th percentile.
76    pub p95: Option<f64>,
77    /// The largest value.
78    pub max: Option<f64>,
79    /// The 5th percentile with every run that gave no value placed below the smallest value
80    /// ([`Distribution::quantile_counting_missing`]); `None` when every run gave a value, as the
81    /// 5th percentile is then `p05`.
82    pub p05_counting_missing: Option<CountedQuantile>,
83    /// The 95th percentile with every run that gave no value placed above the largest value;
84    /// `None` when every run gave a value.
85    pub p95_counting_missing: Option<CountedQuantile>,
86}
87
88/// Which end of the values [`Distribution::quantile_counting_missing`] places the runs that gave
89/// no value past.
90#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
91#[serde(rename_all = "snake_case")]
92pub enum MissingEnd {
93    /// Below the smallest value: the worst case for a low quantile, such as the 5th percentile.
94    Below,
95    /// Above the largest value: the worst case for a high quantile, such as the 95th percentile.
96    Above,
97}
98
99/// A quantile that counts the runs that gave no value ([`Distribution::quantile_counting_missing`]).
100#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
101#[serde(rename_all = "snake_case")]
102pub enum CountedQuantile {
103    /// The quantile, a value the runs gave or one between two of them.
104    Value(f64),
105    /// Too many runs gave no value for the rest to bound the quantile: its interpolation puts
106    /// weight on a missing run.
107    Unbounded,
108}
109
110/// Bounds on the share of all the runs tried whose value passed a test: `low` counts a run with
111/// no value as failing it, `high` as passing.
112#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
113pub struct Share {
114    /// The runs with a value that passed, over every run tried.
115    pub low: f64,
116    /// The same, with every run that gave no value counted as passing.
117    pub high: f64,
118}
119
120impl Distribution {
121    /// The distribution of `values`, from `attempted` runs (those that gave no value make up the
122    /// difference).
123    ///
124    /// # Errors
125    ///
126    /// - [`AnalysisError::Domain`] for a value that isn't finite.
127    /// - [`AnalysisError::Count`] for more values than runs.
128    pub fn new(values: Vec<f64>, attempted: usize) -> Result<Self, AnalysisError> {
129        if values.len() > attempted {
130            return Err(AnalysisError::Count {
131                what: "values in a distribution, against the runs tried",
132                count: values.len(),
133                limit: attempted,
134            });
135        }
136        if let Some(&bad) = values.iter().find(|v| !v.is_finite()) {
137            return Err(AnalysisError::Domain {
138                what: "value in a distribution",
139                value: bad,
140            });
141        }
142        let mut sorted = values;
143        sorted.sort_by(f64::total_cmp);
144        Ok(Self { attempted, sorted })
145    }
146
147    /// The runs tried.
148    pub fn attempted(&self) -> usize {
149        self.attempted
150    }
151
152    /// The runs that gave a value.
153    pub fn count(&self) -> usize {
154        self.sorted.len()
155    }
156
157    /// The runs that gave no value: failed, or without the quantity asked for.
158    pub fn missing(&self) -> usize {
159        self.attempted - self.sorted.len()
160    }
161
162    /// The values, smallest first.
163    pub fn sorted(&self) -> &[f64] {
164        &self.sorted
165    }
166
167    /// The smallest value, `None` with no values.
168    pub fn min(&self) -> Option<f64> {
169        self.sorted.first().copied()
170    }
171
172    /// The largest value, `None` with no values.
173    pub fn max(&self) -> Option<f64> {
174        self.sorted.last().copied()
175    }
176
177    /// The mean, `x₀ + Σ(xᵢ − x₀)/n` with `x₀` the smallest value; `None` with no values.
178    pub fn mean(&self) -> Option<f64> {
179        let shift = self.min()?;
180        Some(shift + self.shifted_mean(shift))
181    }
182
183    /// The sample standard deviation, `√(Σ(dᵢ − d̄)²/(n − 1))` with `dᵢ = xᵢ − x₀`; `None` with
184    /// fewer than two values.
185    pub fn standard_deviation(&self) -> Option<f64> {
186        if self.sorted.len() < 2 {
187            return None;
188        }
189        let shift = self.min()?;
190        let mean = self.shifted_mean(shift);
191        let sum_squares: f64 = self
192            .sorted
193            .iter()
194            .map(|&x| {
195                let d = (x - shift) - mean;
196                d * d
197            })
198            .sum();
199        // Cast: a count of values is far below 2⁵³.
200        Some((sum_squares / (self.sorted.len() - 1) as f64).sqrt())
201    }
202
203    /// The mean of the values less `shift`.
204    fn shifted_mean(&self, shift: f64) -> f64 {
205        let sum: f64 = self.sorted.iter().map(|&x| x - shift).sum();
206        // Cast: a count of values is far below 2⁵³.
207        sum / self.sorted.len() as f64
208    }
209
210    /// The `p` quantile by Hyndman and Fan's definition 7 (the module's docs); `None` with no
211    /// values.
212    ///
213    /// # Errors
214    ///
215    /// [`AnalysisError::Domain`] for `p` outside `[0, 1]`.
216    pub fn quantile(&self, p: f64) -> Result<Option<f64>, AnalysisError> {
217        if !(0.0..=1.0).contains(&p) {
218            return Err(AnalysisError::Domain {
219                what: "quantile probability",
220                value: p,
221            });
222        }
223        let Some(&last) = self.sorted.last() else {
224            return Ok(None);
225        };
226        // Cast: a count of values is far below 2⁵³, and `h` lies in `[0, n − 1]`.
227        let h = (self.sorted.len() - 1) as f64 * p;
228        let below = h.floor();
229        let index = below as usize;
230        let Some(&above) = self.sorted.get(index + 1) else {
231            return Ok(Some(last));
232        };
233        let low = self.sorted[index];
234        Ok(Some(low + (h - below) * (above - low)))
235    }
236
237    /// The `p` quantile of every run tried, each run that gave no value placed past `end` of the
238    /// values (the module's docs); `None` with no runs tried. With no missing run it is
239    /// [`Distribution::quantile`]'s value, bit for bit.
240    ///
241    /// The missing runs' worst case: a 95% value read over the runs that gave one alone sits
242    /// below the 95% of every run tried if the missing runs lie above it, so the high quantile
243    /// counts them [`MissingEnd::Above`] and the low one [`MissingEnd::Below`].
244    ///
245    /// # Errors
246    ///
247    /// [`AnalysisError::Domain`] for `p` outside `[0, 1]`.
248    pub fn quantile_counting_missing(
249        &self,
250        p: f64,
251        end: MissingEnd,
252    ) -> Result<Option<CountedQuantile>, AnalysisError> {
253        if !(0.0..=1.0).contains(&p) {
254            return Err(AnalysisError::Domain {
255                what: "quantile probability",
256                value: p,
257            });
258        }
259        if self.attempted == 0 {
260            return Ok(None);
261        }
262        let missing = self.missing();
263        // The `j`th of every run tried, smallest first: `None` for a missing run.
264        let value = |j: usize| match end {
265            MissingEnd::Above => self.sorted.get(j).copied(),
266            MissingEnd::Below => j
267                .checked_sub(missing)
268                .and_then(|i| self.sorted.get(i).copied()),
269        };
270        // Cast: a count of runs is far below 2⁵³, and `h` lies in `[0, N − 1]`.
271        let h = (self.attempted - 1) as f64 * p;
272        let below = h.floor();
273        let index = below as usize;
274        let Some(low) = value(index) else {
275            return Ok(Some(CountedQuantile::Unbounded));
276        };
277        if index + 1 == self.attempted {
278            return Ok(Some(CountedQuantile::Value(low)));
279        }
280        match value(index + 1) {
281            Some(above) => Ok(Some(CountedQuantile::Value(
282                low + (h - below) * (above - low),
283            ))),
284            // `h` on a value: the missing run next to it carries no weight.
285            None if h == below => Ok(Some(CountedQuantile::Value(low))),
286            None => Ok(Some(CountedQuantile::Unbounded)),
287        }
288    }
289
290    /// Bounds on the share of the runs tried whose value is at least `threshold` ([`Share`]);
291    /// `None` with no runs tried, when there is no share to bound. An infinite threshold is
292    /// allowed.
293    ///
294    /// # Errors
295    ///
296    /// [`AnalysisError::Domain`] for a threshold that is not a number.
297    pub fn share_at_least(&self, threshold: f64) -> Result<Option<Share>, AnalysisError> {
298        if threshold.is_nan() {
299            return Err(AnalysisError::Domain {
300                what: "threshold of a share",
301                value: threshold,
302            });
303        }
304        if self.attempted == 0 {
305            return Ok(None);
306        }
307        let passed = self.sorted.len() - self.sorted.partition_point(|&x| x < threshold);
308        // Cast: counts far below 2⁵³.
309        let attempted = self.attempted as f64;
310        Ok(Some(Share {
311            low: passed as f64 / attempted,
312            high: (passed + self.missing()) as f64 / attempted,
313        }))
314    }
315
316    /// The usual numbers, for a report: [`Summary`].
317    pub fn summary(&self) -> Summary {
318        // The probabilities are in [0, 1].
319        let quantile = |p: f64| self.quantile(p).ok().flatten();
320        let counting_missing = |p: f64, end: MissingEnd| {
321            if self.missing() == 0 {
322                None
323            } else {
324                self.quantile_counting_missing(p, end).ok().flatten()
325            }
326        };
327        Summary {
328            attempted: self.attempted,
329            count: self.count(),
330            mean: self.mean(),
331            standard_deviation: self.standard_deviation(),
332            min: self.min(),
333            p05: quantile(0.05),
334            p50: quantile(0.5),
335            p95: quantile(0.95),
336            max: self.max(),
337            p05_counting_missing: counting_missing(0.05, MissingEnd::Below),
338            p95_counting_missing: counting_missing(0.95, MissingEnd::Above),
339        }
340    }
341}
342
343#[cfg(test)]
344mod tests {
345    use super::*;
346
347    #[test]
348    fn equal_values_give_their_value_and_no_spread() {
349        // A sum of 0.1s divided by their count isn't 0.1 in floating point; shifted by the
350        // smallest value, it is.
351        let d = Distribution::new(vec![0.1; 7], 7).unwrap();
352        assert_eq!(d.mean(), Some(0.1));
353        assert_eq!(d.standard_deviation(), Some(0.0));
354        assert_eq!(d.quantile(0.37).unwrap(), Some(0.1));
355    }
356
357    #[test]
358    fn moments_and_quantiles_by_hand() {
359        let d = Distribution::new(vec![4.0, 1.0, 3.0, 2.0], 6).unwrap();
360        assert_eq!(d.sorted(), &[1.0, 2.0, 3.0, 4.0]);
361        assert_eq!((d.count(), d.missing(), d.attempted()), (4, 2, 6));
362        assert_eq!(d.mean(), Some(2.5));
363        // Σ(x − 2.5)² = 5, over n − 1 = 3.
364        assert_eq!(d.standard_deviation(), Some((5.0_f64 / 3.0).sqrt()));
365        // h = 3p: p = 0.5 is halfway from 2 to 3; p = 0.9 is 0.7 of the way from 3 to 4. NumPy's
366        // `np.quantile([1, 2, 3, 4], [0, 0.5, 0.9, 1])` gives the same: 1, 2.5, 3.7, 4.
367        assert_eq!(d.quantile(0.0).unwrap(), Some(1.0));
368        assert_eq!(d.quantile(0.5).unwrap(), Some(2.5));
369        assert!((d.quantile(0.9).unwrap().unwrap() - 3.7).abs() < 1e-15);
370        assert_eq!(d.quantile(1.0).unwrap(), Some(4.0));
371        let summary = d.summary();
372        assert_eq!((summary.min, summary.max), (Some(1.0), Some(4.0)));
373        assert_eq!(summary.p50, Some(2.5));
374    }
375
376    #[test]
377    fn a_share_is_bounded_by_the_runs_with_no_value() {
378        // Two of six runs gave nothing: at least 2/6 and at most 4/6 reached 3.
379        let d = Distribution::new(vec![1.0, 2.0, 3.0, 4.0], 6).unwrap();
380        let share = d.share_at_least(3.0).unwrap().unwrap();
381        assert_eq!((share.low, share.high), (2.0 / 6.0, 4.0 / 6.0));
382        let all = Distribution::new(vec![1.0, 2.0], 2).unwrap();
383        let share = all.share_at_least(1.0).unwrap().unwrap();
384        assert_eq!((share.low, share.high), (1.0, 1.0));
385        let share = all.share_at_least(f64::INFINITY).unwrap().unwrap();
386        assert_eq!((share.low, share.high), (0.0, 0.0));
387        let share = all.share_at_least(f64::NEG_INFINITY).unwrap().unwrap();
388        assert_eq!((share.low, share.high), (1.0, 1.0));
389        // No runs, no share; a threshold that isn't a number is refused.
390        let none = Distribution::new(vec![], 0).unwrap();
391        assert_eq!(none.share_at_least(1.0).unwrap(), None);
392        assert!(matches!(
393            all.share_at_least(f64::NAN),
394            Err(AnalysisError::Domain {
395                what: "threshold of a share",
396                ..
397            })
398        ));
399    }
400
401    #[test]
402    fn a_quantile_counting_the_missing_runs_by_hand() {
403        // Four values of six runs. Above: the runs are 1, 2, 3, 4, +∞, +∞, and `h = 5p`.
404        let d = Distribution::new(vec![4.0, 1.0, 3.0, 2.0], 6).unwrap();
405        let above = |p| d.quantile_counting_missing(p, MissingEnd::Above).unwrap();
406        let below = |p| d.quantile_counting_missing(p, MissingEnd::Below).unwrap();
407        assert_eq!(above(0.0), Some(CountedQuantile::Value(1.0)));
408        assert_eq!(above(0.5), Some(CountedQuantile::Value(3.5)));
409        // h = 3.0 sits on the 4, the last value: the missing run after it has no weight.
410        assert_eq!(above(0.6), Some(CountedQuantile::Value(4.0)));
411        assert_eq!(above(0.65), Some(CountedQuantile::Unbounded));
412        assert_eq!(above(0.95), Some(CountedQuantile::Unbounded));
413        // Below: −∞, −∞, 1, 2, 3, 4.
414        assert_eq!(below(0.5), Some(CountedQuantile::Value(1.5)));
415        assert_eq!(below(0.4), Some(CountedQuantile::Value(1.0)));
416        assert_eq!(below(0.35), Some(CountedQuantile::Unbounded));
417        assert_eq!(below(0.05), Some(CountedQuantile::Unbounded));
418        assert_eq!(below(1.0), Some(CountedQuantile::Value(4.0)));
419        // Nothing tried, nothing to bound; every run missing, nothing bounded.
420        let none = Distribution::new(vec![], 0).unwrap();
421        assert_eq!(
422            none.quantile_counting_missing(0.5, MissingEnd::Above)
423                .unwrap(),
424            None
425        );
426        let empty = Distribution::new(vec![], 3).unwrap();
427        for end in [MissingEnd::Above, MissingEnd::Below] {
428            assert_eq!(
429                empty.quantile_counting_missing(0.0, end).unwrap(),
430                Some(CountedQuantile::Unbounded)
431            );
432        }
433        for p in [-0.1, 1.1, f64::NAN] {
434            assert!(matches!(
435                d.quantile_counting_missing(p, MissingEnd::Above),
436                Err(AnalysisError::Domain { what: "quantile probability", value })
437                    if value.to_bits() == p.to_bits()
438            ));
439        }
440    }
441
442    #[test]
443    fn with_no_missing_run_it_is_the_quantile_bit_for_bit() {
444        let values: Vec<f64> = (0..37)
445            .map(|i| f64::from(i).mul_add(0.37, 1.0).sin())
446            .collect();
447        let d = Distribution::new(values, 37).unwrap();
448        for step in 0..=200 {
449            let p = f64::from(step) / 200.0;
450            let plain = d.quantile(p).unwrap().unwrap();
451            for end in [MissingEnd::Above, MissingEnd::Below] {
452                assert_eq!(
453                    d.quantile_counting_missing(p, end).unwrap(),
454                    Some(CountedQuantile::Value(plain)),
455                    "p = {p}"
456                );
457            }
458        }
459        // The summary leaves the counting quantiles out when nothing is missing.
460        let summary = d.summary();
461        assert_eq!(summary.p05_counting_missing, None);
462        assert_eq!(summary.p95_counting_missing, None);
463    }
464
465    #[test]
466    fn the_missing_runs_widen_each_tail_toward_its_own_end() {
467        // 1 to 20 from 21 runs. Over the 20 values the 95th percentile is 19.05 and the 5th
468        // 1.95. Counting the missing run past each end gives the worst case: higher at the top
469        // (h = 20 × 0.95 = 19, the 20), lower at the bottom (h = 1, the 1).
470        let d = Distribution::new((1..=20).map(f64::from).collect(), 21).unwrap();
471        let summary = d.summary();
472        assert!((summary.p95.unwrap() - 19.05).abs() < 1e-12);
473        assert!((summary.p05.unwrap() - 1.95).abs() < 1e-12);
474        assert_eq!(
475            summary.p95_counting_missing,
476            Some(CountedQuantile::Value(20.0))
477        );
478        assert_eq!(
479            summary.p05_counting_missing,
480            Some(CountedQuantile::Value(1.0))
481        );
482        // Two missing of 21: the top's interpolation reaches a missing run, and so does the
483        // bottom's.
484        let d = Distribution::new((1..=19).map(f64::from).collect(), 21).unwrap();
485        let summary = d.summary();
486        assert_eq!(
487            summary.p95_counting_missing,
488            Some(CountedQuantile::Unbounded)
489        );
490        assert_eq!(
491            summary.p05_counting_missing,
492            Some(CountedQuantile::Unbounded)
493        );
494    }
495
496    #[test]
497    fn a_bound_serializes_as_a_value_or_unbounded() {
498        assert_eq!(
499            serde_json::to_string(&CountedQuantile::Value(2.5)).unwrap(),
500            r#"{"value":2.5}"#
501        );
502        assert_eq!(
503            serde_json::to_string(&CountedQuantile::Unbounded).unwrap(),
504            r#""unbounded""#
505        );
506    }
507
508    #[test]
509    fn empty_and_single_samples() {
510        let empty = Distribution::new(vec![], 3).unwrap();
511        assert_eq!(empty.mean(), None);
512        assert_eq!(empty.quantile(0.5).unwrap(), None);
513        assert_eq!(empty.missing(), 3);
514        let one = Distribution::new(vec![2.0], 1).unwrap();
515        assert_eq!(one.mean(), Some(2.0));
516        assert_eq!(one.standard_deviation(), None);
517        assert_eq!(one.quantile(0.3).unwrap(), Some(2.0));
518    }
519
520    #[test]
521    fn a_distribution_reads_back_through_its_checks() {
522        let d = Distribution::new(vec![3.0, 1.0, 2.0], 4).unwrap();
523        let json = serde_json::to_string(&d).unwrap();
524        assert_eq!(json, r#"{"attempted":4,"sorted":[1.0,2.0,3.0]}"#);
525        assert_eq!(serde_json::from_str::<Distribution>(&json).unwrap(), d);
526        // Unsorted values are sorted on the way in; more values than runs are refused.
527        let unsorted: Distribution =
528            serde_json::from_str(r#"{"attempted":3,"sorted":[3.0,1.0,2.0]}"#).unwrap();
529        assert_eq!(unsorted.sorted(), &[1.0, 2.0, 3.0]);
530        let error = serde_json::from_str::<Distribution>(r#"{"attempted":1,"sorted":[3.0,1.0]}"#)
531            .unwrap_err();
532        assert!(error.to_string().contains("more than 1"), "{error}");
533    }
534
535    #[test]
536    fn bad_inputs_are_refused() {
537        assert!(matches!(
538            Distribution::new(vec![1.0, f64::NAN], 2),
539            Err(AnalysisError::Domain { what: "value in a distribution", value }) if value.is_nan()
540        ));
541        assert!(matches!(
542            Distribution::new(vec![1.0, 2.0], 1),
543            Err(AnalysisError::Count {
544                count: 2,
545                limit: 1,
546                ..
547            })
548        ));
549        let d = Distribution::new(vec![1.0], 1).unwrap();
550        for p in [-0.1, 1.1, f64::NAN] {
551            assert!(matches!(
552                d.quantile(p),
553                Err(AnalysisError::Domain { what: "quantile probability", value })
554                    if value.to_bits() == p.to_bits()
555            ));
556        }
557    }
558}