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 r < 2.0 - 1e-9 || r > s.size as f64 + 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> {
145 validate(strata)?;
146 if !budget.is_finite() || budget <= 0.0 {
147 return Err("the budget must be positive".into());
148 }
149 let floor_cost: f64 = strata.iter().map(|s| s.cost * (s.size.min(2)) as f64).sum();
150 if floor_cost > budget + 1e-9 {
151 return Err(format!(
152 "the budget {budget} does not cover two units per stratum (cost {floor_cost})"
153 ));
154 }
155 let h = strata.len();
156 let a_all: f64 = strata
157 .iter()
158 .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
159 .sum();
160 if a_all <= 0.0 {
161 return Err("every stratum has zero standard deviation; nothing to allocate".into());
162 }
163 let mut full = vec![false; h];
166 let mut raw = vec![0.0; h];
167 loop {
168 let spent: f64 = (0..h)
169 .filter(|&i| full[i])
170 .map(|i| strata[i].cost * strata[i].size as f64)
171 .sum();
172 let left = budget - spent;
173 if left <= 0.0 {
174 return Err(
175 "the budget does not cover the strata that must be taken completely".into(),
176 );
177 }
178 let a: f64 = (0..h)
179 .filter(|&i| !full[i])
180 .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
181 .sum();
182 let mut new_full = false;
183 for i in 0..h {
184 if full[i] {
185 raw[i] = strata[i].size as f64;
186 continue;
187 }
188 raw[i] = if a > 0.0 {
189 left * strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() / a
190 } else {
191 2.0
192 };
193 if raw[i] >= strata[i].size as f64 {
194 full[i] = true;
195 new_full = true;
196 }
197 }
198 if !new_full {
199 break;
200 }
201 }
202 let mut a = finish(strata, &raw);
203 a.bounded = a.bounded || full.iter().any(|&f| f);
204 repair_budget(strata, budget, &mut a);
205 Ok(a)
206}
207
208fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
214 let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
215 let mut m = n.to_vec();
216 m[h] = (m[h] as i64 + delta) as usize;
217 variance_of(strata, &m)
218 };
219 while a.cost > budget + 1e-9 {
220 let mut best: Option<(usize, f64)> = None;
221 for (h, s) in strata.iter().enumerate() {
222 if a.n[h] > 2 {
223 let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
224 if best.map_or(true, |(_, r)| rate < r) {
225 best = Some((h, rate));
226 }
227 }
228 }
229 match best {
230 Some((h, _)) => {
231 a.n[h] -= 1;
232 a.cost -= strata[h].cost;
233 a.variance = variance_of(strata, &a.n);
234 }
235 None => break,
236 }
237 }
238 loop {
239 let mut best: Option<(usize, f64)> = None;
240 for (h, s) in strata.iter().enumerate() {
241 if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
242 let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
243 if best.map_or(true, |(_, r)| rate > r) {
244 best = Some((h, rate));
245 }
246 }
247 }
248 match best {
249 Some((h, _)) => {
250 a.n[h] += 1;
251 a.cost += strata[h].cost;
252 a.variance = variance_of(strata, &a.n);
253 }
254 None => break,
255 }
256 }
257}
258
259#[derive(Clone, Debug, PartialEq)]
269pub struct MultiAllocation {
270 pub n: Vec<usize>,
271 pub cost: f64,
272 pub attained: Vec<f64>,
274 pub bounded: bool,
276 pub multipliers: Vec<f64>,
278}
279
280pub fn allocate_multivariate(
281 sizes: &[usize],
282 costs: &[f64],
283 sd: &[f64],
284 targets: &[f64],
285) -> Result<MultiAllocation, String> {
286 let h = sizes.len();
287 let j = targets.len();
288 if h == 0 || j == 0 || costs.len() != h || sd.len() != h * j {
289 return Err("sizes and costs need one entry per stratum, sd one row per stratum and one column per target".into());
290 }
291 if sizes.iter().any(|&n| n < 2) {
292 return Err("every stratum needs at least two units".into());
293 }
294 if costs.iter().any(|c| !c.is_finite() || *c <= 0.0) {
295 return Err("costs must be positive".into());
296 }
297 if sd.iter().any(|s| !s.is_finite() || *s < 0.0) {
298 return Err("standard deviations must be finite and non-negative".into());
299 }
300 if targets.iter().any(|v| !v.is_finite() || *v <= 0.0) {
301 return Err("target variances must be positive".into());
302 }
303 let big_n: Vec<f64> = sizes.iter().map(|&n| n as f64).collect();
304 let a = |hh: usize, jj: usize| big_n[hh].powi(2) * sd[hh * j + jj].powi(2);
306 let b: Vec<f64> = (0..j)
307 .map(|jj| {
308 targets[jj]
309 + (0..h)
310 .map(|hh| big_n[hh] * sd[hh * j + jj].powi(2))
311 .sum::<f64>()
312 })
313 .collect();
314 let mut full = vec![false; h];
315 let mut raw = vec![0.0; h];
316 let mut mu = vec![1.0; j];
317 loop {
318 let b_left: Vec<f64> = (0..j)
320 .map(|jj| {
321 b[jj]
322 - (0..h)
323 .filter(|&hh| full[hh])
324 .map(|hh| a(hh, jj) / big_n[hh])
325 .sum::<f64>()
326 })
327 .collect();
328 if b_left.iter().any(|v| *v <= 0.0) {
329 return Err("a target variance cannot be met even by observing every unit".into());
330 }
331 let free: Vec<usize> = (0..h).filter(|&hh| !full[hh]).collect();
332 if free.is_empty() {
333 break;
334 }
335 for _ in 0..20_000 {
337 for &hh in &free {
338 let num: f64 = (0..j).map(|jj| mu[jj] * a(hh, jj)).sum();
339 raw[hh] = (num / costs[hh]).sqrt().max(1e-9);
340 }
341 let ratios: Vec<f64> = (0..j)
342 .map(|jj| free.iter().map(|&hh| a(hh, jj) / raw[hh]).sum::<f64>() / b_left[jj])
343 .collect();
344 let mut done = true;
345 for jj in 0..j {
346 let r = ratios[jj];
347 if r > 1.0 + 1e-9 || (mu[jj] > 1e-12 && r < 1.0 - 1e-9) {
348 done = false;
349 }
350 mu[jj] *= r.powf(0.5);
351 if mu[jj] < 1e-14 {
352 mu[jj] = 0.0;
353 }
354 }
355 if mu.iter().all(|v| *v == 0.0) {
356 mu = vec![1e-6; j];
357 }
358 if done {
359 break;
360 }
361 }
362 let worst = (0..j)
364 .map(|jj| free.iter().map(|&hh| a(hh, jj) / raw[hh]).sum::<f64>() / b_left[jj])
365 .fold(0.0, f64::max);
366 if worst > 1.0 {
367 for &hh in &free {
368 raw[hh] *= worst;
369 }
370 }
371 let mut new_full = false;
372 for &hh in &free {
373 if raw[hh] >= big_n[hh] - 1e-9 {
374 full[hh] = true;
375 raw[hh] = big_n[hh];
376 new_full = true;
377 }
378 }
379 if !new_full {
380 break;
381 }
382 }
383 let mut bounded = full.iter().any(|&f| f);
384 let n: Vec<usize> = (0..h)
385 .map(|hh| {
386 let up = (raw[hh] - 1e-9).ceil();
387 if up < 2.0 {
388 bounded = true;
389 }
390 (up.max(2.0).min(big_n[hh])) as usize
391 })
392 .collect();
393 let cost = (0..h).map(|hh| costs[hh] * n[hh] as f64).sum();
394 let attained: Vec<f64> = (0..j)
395 .map(|jj| {
396 (0..h)
397 .map(|hh| a(hh, jj) / n[hh] as f64 - big_n[hh] * sd[hh * j + jj].powi(2))
398 .sum()
399 })
400 .collect();
401 Ok(MultiAllocation {
402 n,
403 cost,
404 attained,
405 bounded,
406 multipliers: mu,
407 })
408}
409
410#[cfg(test)]
411mod tests {
412 use super::*;
413
414 #[test]
415 fn multivariate_allocation_meets_every_target_at_minimum_cost() {
416 let sizes = [1000usize, 500];
418 let costs = [10.0, 30.0];
419 let sd = [5.0, 2.0, 3.0, 9.0]; let s1 = [
422 Stratum {
423 size: 1000,
424 sd: 5.0,
425 cost: 10.0,
426 },
427 Stratum {
428 size: 500,
429 sd: 3.0,
430 cost: 30.0,
431 },
432 ];
433 let s2 = [
434 Stratum {
435 size: 1000,
436 sd: 2.0,
437 cost: 10.0,
438 },
439 Stratum {
440 size: 500,
441 sd: 9.0,
442 cost: 30.0,
443 },
444 ];
445 let v1 = allocate_for_budget(&s1, 2000.0).unwrap().variance;
446 let v2 = allocate_for_budget(&s2, 2000.0).unwrap().variance;
447 let m = allocate_multivariate(&sizes, &costs, &sd, &[v1, v2]).unwrap();
448 assert!(
449 m.attained[0] <= v1 * (1.0 + 1e-6),
450 "{} vs {v1}",
451 m.attained[0]
452 );
453 assert!(
454 m.attained[1] <= v2 * (1.0 + 1e-6),
455 "{} vs {v2}",
456 m.attained[1]
457 );
458 assert!(m.cost >= 2000.0 - costs[1]);
460 let var = |n1: usize, n2: usize, jj: usize| -> f64 {
462 let a = |hh: usize| (sizes[hh] as f64).powi(2) * sd[hh * 2 + jj].powi(2);
463 let c = |hh: usize| sizes[hh] as f64 * sd[hh * 2 + jj].powi(2);
464 a(0) / n1 as f64 + a(1) / n2 as f64 - c(0) - c(1)
465 };
466 for n1 in 2..400usize {
467 for n2 in 2..200usize {
468 let c = 10.0 * n1 as f64 + 30.0 * n2 as f64;
469 if c < m.cost - 1e-9 && var(n1, n2, 0) <= v1 && var(n1, n2, 1) <= v2 {
470 panic!(
471 "cheaper feasible allocation ({n1}, {n2}) at cost {c} < {}",
472 m.cost
473 );
474 }
475 }
476 }
477 let uni = allocate_for_variance(&s1, v1).unwrap();
479 let one = allocate_multivariate(&sizes, &costs, &[5.0, 3.0], &[v1]).unwrap();
480 assert_eq!(one.n, uni.n);
481 let all = allocate_multivariate(&sizes, &costs, &sd, &[1e-9, v2]).unwrap();
483 assert_eq!(all.n, vec![1000, 500]);
484 assert!(all.bounded);
485 assert!(allocate_multivariate(&sizes, &costs, &sd, &[v1]).is_err());
486 }
487
488 #[test]
489 fn budget_below_the_floor_is_refused_and_small_optima_are_flagged() {
490 let s = [Stratum {
491 size: 10,
492 sd: 1.0,
493 cost: 10.0,
494 }];
495 assert!(allocate_for_budget(&s, 5.0).is_err());
496 let a = allocate_for_budget(&s, 20.0).unwrap();
497 assert_eq!(a.n, vec![2]);
498 assert!(a.cost <= 20.0 + 1e-9);
499 let one = [Stratum {
501 size: 100,
502 sd: 1.0,
503 cost: 1.0,
504 }];
505 let v = 100.0f64.powi(2) / 1.5 * (1.0 - 1.5 / 100.0);
506 let a = allocate_for_variance(&one, v).unwrap();
507 assert_eq!(a.n, vec![2]);
508 assert!(a.bounded);
509 }
510
511 #[test]
512 fn neyman_with_cost() {
513 let strata = vec![
514 Stratum {
515 size: 1000,
516 sd: 10.0,
517 cost: 1.0,
518 },
519 Stratum {
520 size: 1000,
521 sd: 10.0,
522 cost: 4.0,
523 },
524 ];
525 let a = allocate_for_variance(&strata, 1e6).unwrap();
526 assert!(
528 (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
529 "{:?}",
530 a.n
531 );
532 assert!(a.variance <= 1e6 * 1.05);
533 let b = allocate_for_budget(&strata, a.cost).unwrap();
534 assert!((b.variance - a.variance).abs() / a.variance < 0.05);
535 assert!(
536 b.cost <= a.cost + 1e-9,
537 "cost {} exceeds budget {}",
538 b.cost,
539 a.cost
540 );
541 let c = allocate_for_budget(
542 &[
543 Stratum {
544 size: 2000,
545 sd: 12.0,
546 cost: 40.0,
547 },
548 Stratum {
549 size: 800,
550 sd: 30.0,
551 cost: 180.0,
552 },
553 ],
554 20000.0,
555 )
556 .unwrap();
557 assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
558 assert!(allocate_for_variance(&strata, -1.0).is_err());
559 assert!(allocate_for_variance(
560 &[Stratum {
561 size: 1,
562 sd: 1.0,
563 cost: 1.0
564 }],
565 1.0
566 )
567 .is_err());
568 }
569
570 #[test]
571 fn full_strata_keep_the_target() {
572 let strata = vec![
574 Stratum {
575 size: 680,
576 sd: 24.0,
577 cost: 103.0,
578 },
579 Stratum {
580 size: 100,
581 sd: 32.0,
582 cost: 45.0,
583 },
584 ];
585 let a = allocate_for_variance(&strata, 119_025.0).unwrap();
586 assert_eq!(a.n[1], 100);
587 assert!(
588 a.variance <= 119_025.0 * (1.0 + 1e-9),
589 "variance {}",
590 a.variance
591 );
592 assert!(a.bounded);
593 let b = allocate_for_budget(&strata, 20_000.0).unwrap();
594 assert!(b.cost <= 20_000.0 + 1e-9);
595 assert!(b.n[1] <= 100);
596 }
597
598 #[test]
599 fn bounds_are_reported() {
600 let strata = vec![Stratum {
601 size: 10,
602 sd: 100.0,
603 cost: 1.0,
604 }];
605 let a = allocate_for_variance(&strata, 1e9).unwrap();
607 assert_eq!(a.n[0], 2);
608 assert!(a.bounded);
609 let b = allocate_for_variance(&strata, 1e-6).unwrap();
611 assert_eq!(b.n[0], 10);
612 assert_eq!(b.variance, 0.0);
613 }
614}