1#[derive(Clone, Copy, Debug)]
14pub struct Stratum {
15 pub size: usize,
17 pub sd: f64,
19 pub cost: f64,
21}
22
23#[derive(Clone, Debug, PartialEq)]
25pub struct Allocation {
26 pub n: Vec<usize>,
28 pub cost: f64,
30 pub variance: f64,
32 pub bounded: bool,
34}
35
36fn validate(strata: &[Stratum]) -> Result<(), String> {
37 if strata.is_empty() {
38 return Err("at least one stratum is needed".into());
39 }
40 for (h, s) in strata.iter().enumerate() {
41 if s.size < 2 {
42 return Err(format!("stratum {h} has fewer than two units"));
43 }
44 if !s.sd.is_finite() || s.sd < 0.0 {
45 return Err(format!("stratum {h} has an invalid standard deviation"));
46 }
47 if !s.cost.is_finite() || s.cost <= 0.0 {
48 return Err(format!("stratum {h} must have a positive cost"));
49 }
50 }
51 Ok(())
52}
53
54fn variance_of(strata: &[Stratum], n: &[usize]) -> f64 {
55 strata
56 .iter()
57 .zip(n)
58 .map(|(s, &nh)| {
59 let big_n = s.size as f64;
60 big_n * big_n * s.sd * s.sd / nh as f64 * (1.0 - nh as f64 / big_n)
61 })
62 .sum()
63}
64
65fn finish(strata: &[Stratum], raw: &[f64]) -> Allocation {
66 let mut bounded = false;
67 let n: Vec<usize> = strata
68 .iter()
69 .zip(raw)
70 .map(|(s, &r)| {
71 let up = (r - 1e-9).ceil();
72 let v = up.max(2.0).min(s.size as f64);
73 if (v - up).abs() > 1e-9 {
74 bounded = true;
75 }
76 v as usize
77 })
78 .collect();
79 let cost = strata
80 .iter()
81 .zip(&n)
82 .map(|(s, &nh)| s.cost * nh as f64)
83 .sum();
84 Allocation {
85 variance: variance_of(strata, &n),
86 cost,
87 n,
88 bounded,
89 }
90}
91
92pub fn allocate_for_variance(
94 strata: &[Stratum],
95 target_variance: f64,
96) -> Result<Allocation, String> {
97 validate(strata)?;
98 if !target_variance.is_finite() || target_variance <= 0.0 {
99 return Err("the target variance must be positive".into());
100 }
101 let a: f64 = strata
102 .iter()
103 .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
104 .sum();
105 let b: f64 = strata.iter().map(|s| s.size as f64 * s.sd * s.sd).sum();
106 let denom = target_variance + b;
107 let raw: Vec<f64> = strata
108 .iter()
109 .map(|s| s.size as f64 * s.sd / s.cost.sqrt() * a / denom)
110 .collect();
111 Ok(finish(strata, &raw))
112}
113
114pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
116 validate(strata)?;
117 if !budget.is_finite() || budget <= 0.0 {
118 return Err("the budget must be positive".into());
119 }
120 let a: f64 = strata
121 .iter()
122 .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
123 .sum();
124 if a <= 0.0 {
125 return Err("every stratum has zero standard deviation; nothing to allocate".into());
126 }
127 let raw: Vec<f64> = strata
128 .iter()
129 .map(|s| budget * s.size as f64 * s.sd / s.cost.sqrt() / a)
130 .collect();
131 let mut a = finish(strata, &raw);
132 repair_budget(strata, budget, &mut a);
133 Ok(a)
134}
135
136fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
142 let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
143 let mut m = n.to_vec();
144 m[h] = (m[h] as i64 + delta) as usize;
145 variance_of(strata, &m)
146 };
147 while a.cost > budget + 1e-9 {
148 let mut best: Option<(usize, f64)> = None;
149 for (h, s) in strata.iter().enumerate() {
150 if a.n[h] > 2 {
151 let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
152 if best.map_or(true, |(_, r)| rate < r) {
153 best = Some((h, rate));
154 }
155 }
156 }
157 match best {
158 Some((h, _)) => {
159 a.n[h] -= 1;
160 a.cost -= strata[h].cost;
161 a.variance = variance_of(strata, &a.n);
162 }
163 None => break,
164 }
165 }
166 loop {
167 let mut best: Option<(usize, f64)> = None;
168 for (h, s) in strata.iter().enumerate() {
169 if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
170 let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
171 if best.map_or(true, |(_, r)| rate > r) {
172 best = Some((h, rate));
173 }
174 }
175 }
176 match best {
177 Some((h, _)) => {
178 a.n[h] += 1;
179 a.cost += strata[h].cost;
180 a.variance = variance_of(strata, &a.n);
181 }
182 None => break,
183 }
184 }
185}
186
187#[cfg(test)]
188mod tests {
189 use super::*;
190
191 #[test]
192 fn neyman_with_cost() {
193 let strata = vec![
194 Stratum {
195 size: 1000,
196 sd: 10.0,
197 cost: 1.0,
198 },
199 Stratum {
200 size: 1000,
201 sd: 10.0,
202 cost: 4.0,
203 },
204 ];
205 let a = allocate_for_variance(&strata, 1e6).unwrap();
206 assert!(
208 (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
209 "{:?}",
210 a.n
211 );
212 assert!(a.variance <= 1e6 * 1.05);
213 let b = allocate_for_budget(&strata, a.cost).unwrap();
214 assert!((b.variance - a.variance).abs() / a.variance < 0.05);
215 assert!(
216 b.cost <= a.cost + 1e-9,
217 "cost {} exceeds budget {}",
218 b.cost,
219 a.cost
220 );
221 let c = allocate_for_budget(
222 &[
223 Stratum {
224 size: 2000,
225 sd: 12.0,
226 cost: 40.0,
227 },
228 Stratum {
229 size: 800,
230 sd: 30.0,
231 cost: 180.0,
232 },
233 ],
234 20000.0,
235 )
236 .unwrap();
237 assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
238 assert!(allocate_for_variance(&strata, -1.0).is_err());
239 assert!(allocate_for_variance(
240 &[Stratum {
241 size: 1,
242 sd: 1.0,
243 cost: 1.0
244 }],
245 1.0
246 )
247 .is_err());
248 }
249
250 #[test]
251 fn bounds_are_reported() {
252 let strata = vec![Stratum {
253 size: 10,
254 sd: 100.0,
255 cost: 1.0,
256 }];
257 let a = allocate_for_variance(&strata, 1e9).unwrap();
259 assert_eq!(a.n[0], 2);
260 assert!(a.bounded);
261 let b = allocate_for_variance(&strata, 1e-6).unwrap();
263 assert_eq!(b.n[0], 10);
264 assert_eq!(b.variance, 0.0);
265 }
266}