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 v = r.ceil().max(2.0).min(s.size as f64);
72 if (v - r.ceil()).abs() > 1e-9 {
73 bounded = true;
74 }
75 v as usize
76 })
77 .collect();
78 let cost = strata
79 .iter()
80 .zip(&n)
81 .map(|(s, &nh)| s.cost * nh as f64)
82 .sum();
83 Allocation {
84 variance: variance_of(strata, &n),
85 cost,
86 n,
87 bounded,
88 }
89}
90
91pub fn allocate_for_variance(
93 strata: &[Stratum],
94 target_variance: f64,
95) -> Result<Allocation, String> {
96 validate(strata)?;
97 if !target_variance.is_finite() || target_variance <= 0.0 {
98 return Err("the target variance must be positive".into());
99 }
100 let a: f64 = strata
101 .iter()
102 .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
103 .sum();
104 let b: f64 = strata.iter().map(|s| s.size as f64 * s.sd * s.sd).sum();
105 let denom = target_variance + b;
106 let raw: Vec<f64> = strata
107 .iter()
108 .map(|s| s.size as f64 * s.sd / s.cost.sqrt() * a / denom)
109 .collect();
110 Ok(finish(strata, &raw))
111}
112
113pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
115 validate(strata)?;
116 if !budget.is_finite() || budget <= 0.0 {
117 return Err("the budget must be positive".into());
118 }
119 let a: f64 = strata
120 .iter()
121 .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
122 .sum();
123 if a <= 0.0 {
124 return Err("every stratum has zero standard deviation; nothing to allocate".into());
125 }
126 let raw: Vec<f64> = strata
127 .iter()
128 .map(|s| budget * s.size as f64 * s.sd / s.cost.sqrt() / a)
129 .collect();
130 let mut a = finish(strata, &raw);
131 repair_budget(strata, budget, &mut a);
132 Ok(a)
133}
134
135fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
140 let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
141 let mut m = n.to_vec();
142 m[h] = (m[h] as i64 + delta) as usize;
143 variance_of(strata, &m)
144 };
145 while a.cost > budget + 1e-9 {
146 let mut best: Option<(usize, f64)> = None;
147 for (h, s) in strata.iter().enumerate() {
148 if a.n[h] > 2 {
149 let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
150 if best.map_or(true, |(_, r)| rate < r) {
151 best = Some((h, rate));
152 }
153 }
154 }
155 match best {
156 Some((h, _)) => {
157 a.n[h] -= 1;
158 a.cost -= strata[h].cost;
159 a.variance = variance_of(strata, &a.n);
160 a.bounded = true;
161 }
162 None => break,
163 }
164 }
165 loop {
166 let mut best: Option<(usize, f64)> = None;
167 for (h, s) in strata.iter().enumerate() {
168 if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
169 let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
170 if best.map_or(true, |(_, r)| rate > r) {
171 best = Some((h, rate));
172 }
173 }
174 }
175 match best {
176 Some((h, _)) => {
177 a.n[h] += 1;
178 a.cost += strata[h].cost;
179 a.variance = variance_of(strata, &a.n);
180 }
181 None => break,
182 }
183 }
184}
185
186#[cfg(test)]
187mod tests {
188 use super::*;
189
190 #[test]
191 fn neyman_with_cost() {
192 let strata = vec![
193 Stratum {
194 size: 1000,
195 sd: 10.0,
196 cost: 1.0,
197 },
198 Stratum {
199 size: 1000,
200 sd: 10.0,
201 cost: 4.0,
202 },
203 ];
204 let a = allocate_for_variance(&strata, 1e6).unwrap();
205 assert!(
207 (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
208 "{:?}",
209 a.n
210 );
211 assert!(a.variance <= 1e6 * 1.05);
212 let b = allocate_for_budget(&strata, a.cost).unwrap();
213 assert!((b.variance - a.variance).abs() / a.variance < 0.05);
214 assert!(
215 b.cost <= a.cost + 1e-9,
216 "cost {} exceeds budget {}",
217 b.cost,
218 a.cost
219 );
220 let c = allocate_for_budget(
221 &[
222 Stratum {
223 size: 2000,
224 sd: 12.0,
225 cost: 40.0,
226 },
227 Stratum {
228 size: 800,
229 sd: 30.0,
230 cost: 180.0,
231 },
232 ],
233 20000.0,
234 )
235 .unwrap();
236 assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
237 assert!(allocate_for_variance(&strata, -1.0).is_err());
238 assert!(allocate_for_variance(
239 &[Stratum {
240 size: 1,
241 sd: 1.0,
242 cost: 1.0
243 }],
244 1.0
245 )
246 .is_err());
247 }
248
249 #[test]
250 fn bounds_are_reported() {
251 let strata = vec![Stratum {
252 size: 10,
253 sd: 100.0,
254 cost: 1.0,
255 }];
256 let a = allocate_for_variance(&strata, 1e9).unwrap();
258 assert_eq!(a.n[0], 2);
259 assert!(a.bounded);
260 let b = allocate_for_variance(&strata, 1e-6).unwrap();
262 assert_eq!(b.n[0], 10);
263 assert_eq!(b.variance, 0.0);
264 }
265}