#[derive(Clone, Copy, Debug)]
pub struct Stratum {
pub size: usize,
pub sd: f64,
pub cost: f64,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Allocation {
pub n: Vec<usize>,
pub cost: f64,
pub variance: f64,
pub bounded: bool,
}
fn validate(strata: &[Stratum]) -> Result<(), String> {
if strata.is_empty() {
return Err("at least one stratum is needed".into());
}
for (h, s) in strata.iter().enumerate() {
if s.size < 2 {
return Err(format!("stratum {h} has fewer than two units"));
}
if !s.sd.is_finite() || s.sd < 0.0 {
return Err(format!("stratum {h} has an invalid standard deviation"));
}
if !s.cost.is_finite() || s.cost <= 0.0 {
return Err(format!("stratum {h} must have a positive cost"));
}
}
Ok(())
}
fn variance_of(strata: &[Stratum], n: &[usize]) -> f64 {
strata
.iter()
.zip(n)
.map(|(s, &nh)| {
let big_n = s.size as f64;
big_n * big_n * s.sd * s.sd / nh as f64 * (1.0 - nh as f64 / big_n)
})
.sum()
}
fn finish(strata: &[Stratum], raw: &[f64]) -> Allocation {
let mut bounded = false;
let n: Vec<usize> = strata
.iter()
.zip(raw)
.map(|(s, &r)| {
let up = (r - 1e-9).ceil();
let v = up.max(2.0).min(s.size as f64);
if (v - up).abs() > 1e-9 {
bounded = true;
}
v as usize
})
.collect();
let cost = strata
.iter()
.zip(&n)
.map(|(s, &nh)| s.cost * nh as f64)
.sum();
Allocation {
variance: variance_of(strata, &n),
cost,
n,
bounded,
}
}
pub fn allocate_for_variance(
strata: &[Stratum],
target_variance: f64,
) -> Result<Allocation, String> {
validate(strata)?;
if !target_variance.is_finite() || target_variance <= 0.0 {
return Err("the target variance must be positive".into());
}
let h = strata.len();
let mut full = vec![false; h];
let mut raw = vec![0.0; h];
loop {
let a: f64 = (0..h)
.filter(|&i| !full[i])
.map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
.sum();
let b: f64 = (0..h)
.filter(|&i| !full[i])
.map(|i| strata[i].size as f64 * strata[i].sd * strata[i].sd)
.sum();
let denom = target_variance + b;
let mut new_full = false;
for i in 0..h {
if full[i] {
raw[i] = strata[i].size as f64;
continue;
}
raw[i] = strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() * a / denom;
if raw[i] >= strata[i].size as f64 {
full[i] = true;
new_full = true;
}
}
if !new_full {
break;
}
}
let mut out = finish(strata, &raw);
out.bounded = out.bounded || full.iter().any(|&f| f);
Ok(out)
}
pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
validate(strata)?;
if !budget.is_finite() || budget <= 0.0 {
return Err("the budget must be positive".into());
}
let h = strata.len();
let a_all: f64 = strata
.iter()
.map(|s| s.size as f64 * s.sd * s.cost.sqrt())
.sum();
if a_all <= 0.0 {
return Err("every stratum has zero standard deviation; nothing to allocate".into());
}
let mut full = vec![false; h];
let mut raw = vec![0.0; h];
loop {
let spent: f64 = (0..h)
.filter(|&i| full[i])
.map(|i| strata[i].cost * strata[i].size as f64)
.sum();
let left = budget - spent;
if left <= 0.0 {
return Err(
"the budget does not cover the strata that must be taken completely".into(),
);
}
let a: f64 = (0..h)
.filter(|&i| !full[i])
.map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
.sum();
let mut new_full = false;
for i in 0..h {
if full[i] {
raw[i] = strata[i].size as f64;
continue;
}
raw[i] = if a > 0.0 {
left * strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() / a
} else {
2.0
};
if raw[i] >= strata[i].size as f64 {
full[i] = true;
new_full = true;
}
}
if !new_full {
break;
}
}
let mut a = finish(strata, &raw);
a.bounded = a.bounded || full.iter().any(|&f| f);
repair_budget(strata, budget, &mut a);
Ok(a)
}
fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
let mut m = n.to_vec();
m[h] = (m[h] as i64 + delta) as usize;
variance_of(strata, &m)
};
while a.cost > budget + 1e-9 {
let mut best: Option<(usize, f64)> = None;
for (h, s) in strata.iter().enumerate() {
if a.n[h] > 2 {
let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
if best.map_or(true, |(_, r)| rate < r) {
best = Some((h, rate));
}
}
}
match best {
Some((h, _)) => {
a.n[h] -= 1;
a.cost -= strata[h].cost;
a.variance = variance_of(strata, &a.n);
}
None => break,
}
}
loop {
let mut best: Option<(usize, f64)> = None;
for (h, s) in strata.iter().enumerate() {
if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
if best.map_or(true, |(_, r)| rate > r) {
best = Some((h, rate));
}
}
}
match best {
Some((h, _)) => {
a.n[h] += 1;
a.cost += strata[h].cost;
a.variance = variance_of(strata, &a.n);
}
None => break,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn neyman_with_cost() {
let strata = vec![
Stratum {
size: 1000,
sd: 10.0,
cost: 1.0,
},
Stratum {
size: 1000,
sd: 10.0,
cost: 4.0,
},
];
let a = allocate_for_variance(&strata, 1e6).unwrap();
assert!(
(a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
"{:?}",
a.n
);
assert!(a.variance <= 1e6 * 1.05);
let b = allocate_for_budget(&strata, a.cost).unwrap();
assert!((b.variance - a.variance).abs() / a.variance < 0.05);
assert!(
b.cost <= a.cost + 1e-9,
"cost {} exceeds budget {}",
b.cost,
a.cost
);
let c = allocate_for_budget(
&[
Stratum {
size: 2000,
sd: 12.0,
cost: 40.0,
},
Stratum {
size: 800,
sd: 30.0,
cost: 180.0,
},
],
20000.0,
)
.unwrap();
assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
assert!(allocate_for_variance(&strata, -1.0).is_err());
assert!(allocate_for_variance(
&[Stratum {
size: 1,
sd: 1.0,
cost: 1.0
}],
1.0
)
.is_err());
}
#[test]
fn full_strata_keep_the_target() {
let strata = vec![
Stratum {
size: 680,
sd: 24.0,
cost: 103.0,
},
Stratum {
size: 100,
sd: 32.0,
cost: 45.0,
},
];
let a = allocate_for_variance(&strata, 119_025.0).unwrap();
assert_eq!(a.n[1], 100);
assert!(
a.variance <= 119_025.0 * (1.0 + 1e-9),
"variance {}",
a.variance
);
assert!(a.bounded);
let b = allocate_for_budget(&strata, 20_000.0).unwrap();
assert!(b.cost <= 20_000.0 + 1e-9);
assert!(b.n[1] <= 100);
}
#[test]
fn bounds_are_reported() {
let strata = vec![Stratum {
size: 10,
sd: 100.0,
cost: 1.0,
}];
let a = allocate_for_variance(&strata, 1e9).unwrap();
assert_eq!(a.n[0], 2);
assert!(a.bounded);
let b = allocate_for_variance(&strata, 1e-6).unwrap();
assert_eq!(b.n[0], 10);
assert_eq!(b.variance, 0.0);
}
}