Skip to main content

statistical_comparison/
statistical_comparison.rs

1//! Statistical comparison of consistent-permutation constructions
2//! against `ConsistentChooseKHasher` (the gold-standard reference).
3//!
4//! Each generator is asked to produce a uniformly-random ordering of
5//! `0..n` and we run four chi-squared tests at alpha = 0.001:
6//!
7//! 1. Marginal at position 0 (first emitted element should be uniform).
8//! 2. Marginal at position `k-1` (last sampled element should be uniform).
9//! 3. Choose-2 unordered-pair uniformity over the `(n choose 2)` pairs.
10//! 4. Per-position bit balance (each bit should be 1 ~half the time).
11//!
12//! Run with:  cargo run --release --example statistical_comparison
13
14use std::hash::{DefaultHasher, Hash};
15
16use consistent_choose_k::{ConsistentChooseKHasher, ConsistentPermutation};
17
18const SAMPLES: usize = 200_000;
19
20/// 99.9% upper-tail critical value for chi-squared with `df` degrees of
21/// freedom, computed by Wilson-Hilferty:
22///   `chi2_{df, 1-alpha} ≈ df * (1 - 2/(9 df) + z * sqrt(2/(9 df)))^3`
23/// where `z = Phi^{-1}(1 - alpha)`. For alpha=0.001, z ≈ 3.0902.
24fn chi2_critical_999(df: usize) -> f64 {
25    let df = df as f64;
26    let a = 2.0 / (9.0 * df);
27    df * (1.0 - a + 3.0902 * a.sqrt()).powi(3)
28}
29
30/// Pearson chi-squared statistic for `observed` against the uniform
31/// distribution; returns `(chi2, df)`.
32fn chi2_uniform(observed: &[u64]) -> (f64, usize) {
33    let total: u64 = observed.iter().sum();
34    let cells = observed.len();
35    let expected = total as f64 / cells as f64;
36    let mut chi2 = 0.0;
37    for &c in observed {
38        let d = c as f64 - expected;
39        chi2 += d * d / expected;
40    }
41    (chi2, cells - 1)
42}
43
44// ---------- Generators ----------
45
46fn chooseh_take(key: u64, n: usize, k: usize) -> Vec<u32> {
47    let mut h = DefaultHasher::default();
48    key.hash(&mut h);
49    ConsistentChooseKHasher::new(h, n)
50        .map(|v| v as u32)
51        .take(k)
52        .collect()
53}
54
55fn perm_take(key: u64, n: usize, k: usize) -> Vec<u32> {
56    ConsistentPermutation::new(n as u32, key).take(k).collect()
57}
58
59// ---------- Per-method accumulator ----------
60
61struct Acc {
62    name: String,
63    first: Vec<u64>,
64    kth: Vec<u64>,
65    pair: Vec<u64>,      // n*n, indexed by lo*n + hi (lo <= hi)
66    bits: Vec<Vec<u64>>, // bits[pos][bit]
67}
68
69impl Acc {
70    fn new(name: &str, n: usize, kk: usize, n_bits: usize) -> Self {
71        Self {
72            name: name.to_string(),
73            first: vec![0u64; n],
74            kth: vec![0u64; n],
75            pair: vec![0u64; n * n],
76            bits: vec![vec![0u64; n_bits]; kk],
77        }
78    }
79
80    fn record(&mut self, v: &[u32], n: usize, n_bits: usize) {
81        let kk = self.bits.len();
82        self.first[v[0] as usize] += 1;
83        self.kth[v[kk - 1] as usize] += 1;
84        let (lo, hi) = if v[0] <= v[1] {
85            (v[0], v[1])
86        } else {
87            (v[1], v[0])
88        };
89        self.pair[(lo as usize) * n + hi as usize] += 1;
90        for (pos, &val) in v.iter().enumerate().take(kk) {
91            for b in 0..n_bits {
92                if (val >> b) & 1 == 1 {
93                    self.bits[pos][b] += 1;
94                }
95            }
96        }
97    }
98}
99
100fn run_for_n(n: usize) {
101    let kk = 2usize.min(n - 1).max(1);
102    let n_bits = ((n - 1).next_power_of_two().trailing_zeros() as usize).max(1);
103
104    type GenFn = Box<dyn Fn(u64, usize, usize) -> Vec<u32>>;
105
106    // Build the list of methods to test.
107    let methods: Vec<(&'static str, GenFn)> = vec![
108        ("ChooseKHasher    ", Box::new(chooseh_take)),
109        ("Permutation      ", Box::new(perm_take)),
110    ];
111
112    let mut accs: Vec<Acc> = methods
113        .iter()
114        .map(|(name, _)| Acc::new(name, n, kk, n_bits))
115        .collect();
116
117    for seed in 0..SAMPLES as u64 {
118        // Avalanche each sample's seed so we don't pass small
119        // sequential integers into the (single-pass) hashers, which
120        // would correlate strongly. `ConsistentPermutation::new`
121        // does not avalanche its key argument, so we have to do it
122        // here.
123        let mut z = seed.wrapping_add(0x9E37_79B9_7F4A_7C15);
124        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
125        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
126        let key = z ^ (z >> 31);
127        for ((_, gen), acc) in methods.iter().zip(accs.iter_mut()) {
128            let v = gen(key, n, kk);
129            assert_eq!(v.len(), kk);
130            acc.record(&v, n, n_bits);
131        }
132    }
133
134    println!("\n=== n = {n}  (samples = {SAMPLES}) ===");
135    println!(
136        "{:<46} {:>14} {:>6} {:>14} {:>7}",
137        "test", "chi2", "df", "crit(0.001)", "verdict"
138    );
139
140    let print_row = |label: &str, chi2: f64, df: usize| {
141        let crit = chi2_critical_999(df);
142        let verdict = if chi2 <= crit { "PASS" } else { "FAIL" };
143        println!("{label:<46} {chi2:>14.2} {df:>6} {crit:>14.2} {verdict:>7}");
144    };
145
146    // 1) Marginal @ pos 0.
147    for acc in &accs {
148        let (c, d) = chi2_uniform(&acc.first);
149        print_row(&format!("{}: marginal @ pos 0", acc.name), c, d);
150    }
151    // 2) Marginal @ pos kk-1.
152    for acc in &accs {
153        let (c, d) = chi2_uniform(&acc.kth);
154        print_row(&format!("{}: marginal @ pos {}", acc.name, kk - 1), c, d);
155    }
156    // 3) Choose-2 set uniformity over the (n choose 2) cells with i<j.
157    for acc in &accs {
158        let mut cells = Vec::with_capacity(n * (n - 1) / 2);
159        for i in 0..n {
160            for j in (i + 1)..n {
161                cells.push(acc.pair[i * n + j]);
162            }
163        }
164        let (c, d) = chi2_uniform(&cells);
165        print_row(&format!("{}: choose-2 set uniformity", acc.name), c, d);
166    }
167    // 4) Per-(pos, bit) balance against the expected per-bit fraction.
168    for acc in &accs {
169        let mut chi2 = 0.0;
170        let mut df = 0;
171        for b in 0..n_bits {
172            let pi = (0..n).filter(|v| (v >> b) & 1 == 1).count() as f64 / n as f64;
173            if pi == 0.0 || pi == 1.0 {
174                continue;
175            }
176            let exp_set = SAMPLES as f64 * pi;
177            let exp_unset = SAMPLES as f64 * (1.0 - pi);
178            for pos in 0..kk {
179                let set = acc.bits[pos][b] as f64;
180                let unset = SAMPLES as f64 - set;
181                chi2 += (set - exp_set).powi(2) / exp_set + (unset - exp_unset).powi(2) / exp_unset;
182                df += 1;
183            }
184        }
185        print_row(&format!("{}: per-(pos,bit) balance", acc.name), chi2, df);
186    }
187}
188
189fn main() {
190    println!("Statistical comparison of consistent-permutation generators");
191    println!("(Chi-squared tests, alpha = 0.001 — PASS means we cannot reject uniformity.)");
192    for n in [8usize, 16, 32, 64, 128, 256, 1024] {
193        run_for_n(n);
194    }
195}