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 h = strata.len();
105 let mut full = vec![false; h];
106 let mut raw = vec![0.0; h];
107 loop {
108 let a: f64 = (0..h)
109 .filter(|&i| !full[i])
110 .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
111 .sum();
112 let b: f64 = (0..h)
113 .filter(|&i| !full[i])
114 .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].sd)
115 .sum();
116 let denom = target_variance + b;
117 let mut new_full = false;
118 for i in 0..h {
119 if full[i] {
120 raw[i] = strata[i].size as f64;
121 continue;
122 }
123 raw[i] = strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() * a / denom;
124 if raw[i] >= strata[i].size as f64 {
125 full[i] = true;
126 new_full = true;
127 }
128 }
129 if !new_full {
130 break;
131 }
132 }
133 let mut out = finish(strata, &raw);
134 out.bounded = out.bounded || full.iter().any(|&f| f);
135 Ok(out)
136}
137
138pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
139 validate(strata)?;
140 if !budget.is_finite() || budget <= 0.0 {
141 return Err("the budget must be positive".into());
142 }
143 let h = strata.len();
144 let a_all: f64 = strata
145 .iter()
146 .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
147 .sum();
148 if a_all <= 0.0 {
149 return Err("every stratum has zero standard deviation; nothing to allocate".into());
150 }
151 let mut full = vec![false; h];
154 let mut raw = vec![0.0; h];
155 loop {
156 let spent: f64 = (0..h)
157 .filter(|&i| full[i])
158 .map(|i| strata[i].cost * strata[i].size as f64)
159 .sum();
160 let left = budget - spent;
161 if left <= 0.0 {
162 return Err(
163 "the budget does not cover the strata that must be taken completely".into(),
164 );
165 }
166 let a: f64 = (0..h)
167 .filter(|&i| !full[i])
168 .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
169 .sum();
170 let mut new_full = false;
171 for i in 0..h {
172 if full[i] {
173 raw[i] = strata[i].size as f64;
174 continue;
175 }
176 raw[i] = if a > 0.0 {
177 left * strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() / a
178 } else {
179 2.0
180 };
181 if raw[i] >= strata[i].size as f64 {
182 full[i] = true;
183 new_full = true;
184 }
185 }
186 if !new_full {
187 break;
188 }
189 }
190 let mut a = finish(strata, &raw);
191 a.bounded = a.bounded || full.iter().any(|&f| f);
192 repair_budget(strata, budget, &mut a);
193 Ok(a)
194}
195
196fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
202 let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
203 let mut m = n.to_vec();
204 m[h] = (m[h] as i64 + delta) as usize;
205 variance_of(strata, &m)
206 };
207 while a.cost > budget + 1e-9 {
208 let mut best: Option<(usize, f64)> = None;
209 for (h, s) in strata.iter().enumerate() {
210 if a.n[h] > 2 {
211 let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
212 if best.map_or(true, |(_, r)| rate < r) {
213 best = Some((h, rate));
214 }
215 }
216 }
217 match best {
218 Some((h, _)) => {
219 a.n[h] -= 1;
220 a.cost -= strata[h].cost;
221 a.variance = variance_of(strata, &a.n);
222 }
223 None => break,
224 }
225 }
226 loop {
227 let mut best: Option<(usize, f64)> = None;
228 for (h, s) in strata.iter().enumerate() {
229 if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
230 let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
231 if best.map_or(true, |(_, r)| rate > r) {
232 best = Some((h, rate));
233 }
234 }
235 }
236 match best {
237 Some((h, _)) => {
238 a.n[h] += 1;
239 a.cost += strata[h].cost;
240 a.variance = variance_of(strata, &a.n);
241 }
242 None => break,
243 }
244 }
245}
246
247#[cfg(test)]
248mod tests {
249 use super::*;
250
251 #[test]
252 fn neyman_with_cost() {
253 let strata = vec![
254 Stratum {
255 size: 1000,
256 sd: 10.0,
257 cost: 1.0,
258 },
259 Stratum {
260 size: 1000,
261 sd: 10.0,
262 cost: 4.0,
263 },
264 ];
265 let a = allocate_for_variance(&strata, 1e6).unwrap();
266 assert!(
268 (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
269 "{:?}",
270 a.n
271 );
272 assert!(a.variance <= 1e6 * 1.05);
273 let b = allocate_for_budget(&strata, a.cost).unwrap();
274 assert!((b.variance - a.variance).abs() / a.variance < 0.05);
275 assert!(
276 b.cost <= a.cost + 1e-9,
277 "cost {} exceeds budget {}",
278 b.cost,
279 a.cost
280 );
281 let c = allocate_for_budget(
282 &[
283 Stratum {
284 size: 2000,
285 sd: 12.0,
286 cost: 40.0,
287 },
288 Stratum {
289 size: 800,
290 sd: 30.0,
291 cost: 180.0,
292 },
293 ],
294 20000.0,
295 )
296 .unwrap();
297 assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
298 assert!(allocate_for_variance(&strata, -1.0).is_err());
299 assert!(allocate_for_variance(
300 &[Stratum {
301 size: 1,
302 sd: 1.0,
303 cost: 1.0
304 }],
305 1.0
306 )
307 .is_err());
308 }
309
310 #[test]
311 fn full_strata_keep_the_target() {
312 let strata = vec![
314 Stratum {
315 size: 680,
316 sd: 24.0,
317 cost: 103.0,
318 },
319 Stratum {
320 size: 100,
321 sd: 32.0,
322 cost: 45.0,
323 },
324 ];
325 let a = allocate_for_variance(&strata, 119_025.0).unwrap();
326 assert_eq!(a.n[1], 100);
327 assert!(
328 a.variance <= 119_025.0 * (1.0 + 1e-9),
329 "variance {}",
330 a.variance
331 );
332 assert!(a.bounded);
333 let b = allocate_for_budget(&strata, 20_000.0).unwrap();
334 assert!(b.cost <= 20_000.0 + 1e-9);
335 assert!(b.n[1] <= 100);
336 }
337
338 #[test]
339 fn bounds_are_reported() {
340 let strata = vec![Stratum {
341 size: 10,
342 sd: 100.0,
343 cost: 1.0,
344 }];
345 let a = allocate_for_variance(&strata, 1e9).unwrap();
347 assert_eq!(a.n[0], 2);
348 assert!(a.bounded);
349 let b = allocate_for_variance(&strata, 1e-6).unwrap();
351 assert_eq!(b.n[0], 10);
352 assert_eq!(b.variance, 0.0);
353 }
354}