An honest interval for a lake
An ecologist estimates the area of bodies of water from satellite images: throws n random points onto a frame of area A km² and counts how many of them, k, landed in water. The estimate of the area is A · k/n. A 95 per cent confidence interval is needed for it.
The textbook formula p̂ ± z√(p̂(1 − p̂)/n) does not suit the ecologist: if no point landed in a small pond, it claims there is certainly no water. So it was agreed to take as the interval all shares of water p from 0 to 1 at which the observed share p̂ = k/n differs from p by at most z standard deviations computed from p itself:
$$\left|\hat p - p\right| \le z\sqrt{\frac{p(1-p)}{n}}, \qquad z = 1.959963984540054.$$Print the estimate of the area and the ends of the interval in square kilometres (the share times A).
Input
The first line holds the number of bodies of water q (1 ≤ q ≤ 5000). Each of the next q lines holds a real A (0 < A ≤ 10⁶) and integers n, k (1 ≤ n ≤ 10⁹, 0 ≤ k ≤ n).
Output
For each body of water, three numbers separated by spaces: the estimate of the area, the lower and the upper end of the interval. Each number is accepted with an absolute or relative error of 10⁻⁶.
Examples
Example 1
3 3517.5 1000 312 12.5 30 0 2.0 10 10
1097.460000000 999.144770830 1200.836423408 0.000000000 0.000000000 1.418917415 2.000000000 1.444934400 2.000000000
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 5 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
An inequality with an absolute value and a root is awkward. Both its sides are non-negative: what happens if they are squared?
2Hint 2
After squaring you get (p̂ − p)² ≤ z²p(1 − p)/n, a quadratic inequality in p with a positive leading coefficient. Where does such an inequality hold?
3The idea
Expand the brackets and collect by powers of p: (1 + z²/n) p² − (2p̂ + z²/n) p + p̂² ≤ 0. The parabola opens upwards, so the inequality holds between its roots, and that is the interval. It is called the Wilson interval, after Edwin Wilson, who proposed it in 1927; more in the article on the Monte Carlo method.
4Walkthrough
The roots of the quadratic equation after simplification:
$$p_{\pm} = \frac{\hat p + \frac{z^2}{2n} \pm z\sqrt{\frac{\hat p(1-\hat p)}{n} + \frac{z^2}{4n^2}}}{1 + \frac{z^2}{n}}.$$The discriminant is always positive, so the root is taken without checks. With k = 0 the lower end is exactly 0 and the upper positive: even without catching a single point in water, we do not claim there is no water. With k = n the upper end is exactly 1. Rounding may push the ends slightly outside [0, 1]: clip them.
The second test has the counters from the article: points thrown onto the real water mask of the Kapchagay reservoir. Compare the intervals with those the program in the article prints.
4+Solution
5Complexity
O(1) per body of water: a few arithmetic operations and one square root.
6Common mistakes
- The textbook formula. With k = 0 it gives the interval [0, 0], with k = n [1, 1]. Already the second body of water in the first example catches it.
- Substituting p̂ under the root. If p on the right-hand side of the inequality is replaced by p̂, you get the same textbook formula; the whole point is that the spread is computed from the p being tested.
- Integer division. k/n in Go with integer k and n is zero. And n goes up to 10⁹: n² in the denominator does not fit in 32 bits, so compute in floating point.