Sampling with non-uniform costs Suppose that I have a population, each represented by a bit $b_i$ for $i \in \{1,\ldots, n\}$. I would like to compute an estimate $\hat{B}$ of the parameter $B = \sum_{i=1}^nb_i$ so that with high probability, the error $|\hat{B}-B| \leq k$ for some fixed $k$. However, I have to pay a cost $c_i$ to sample bit $b_i$, and this cost may be different for each $i$. I want to find the minimum-cost sample that satisfies my accuracy constraint. Clearly, uniform sampling is not necessarily optimal. 
Has this been studied? Is there a known optimal solution specifying the probability $p_i$ that I should sample each bit $b_i$ to compute $\hat{B}$?  
 A: Methods to find a solution are well known, but this is a messy problem.  A tiny example reveals much, so consider the case $n = 2$.  Let the cost of sampling bit 1 be $c_1 = 1$ and the cost of sampling bit 2 be $c_2 = c$.  Without any loss of generality assume this is the expensive bit: $c \ge 1$.
Either we sample both bits at a cost of $1 + c$ because we have to in order to keep the error low, or else we will sample bit 2 with probability $\pi$ and bit 1 with probability $1 - \pi$.  Let's assume the value of $k$ is large enough that we won't be compelled to sample both bits.
An unbiased estimator is $\hat{B} = b_1 / (1 - \pi)$ if we sample bit 1 and $\hat{B} = b_2 / \pi$ if we sample bit 2.  (This is the Horvitz-Thompson estimator.)
The error rate depends on the state of the population.  I interpret the problem to require that the expected error size be assured of not exceeding the limit $k$ *no matter what the state of the population may be.*  We cannot remove the word "expected" here, because (except for nearly exhaustive samples), the maximum error size can be arbitrarily close to 1 for large populations.
There are $2^2 = 4$ possible states, which can be fully enumerated in this small problem:
$$\eqalign{
\text{Prob.} &b_1 &b_2 &B &\text{Observation} &\hat{B} &\text{Error} \cr
1 - \pi      &0   &0   &0 &0                  &0       &0\cr
\pi          &0   &0   &0 &0                  &0       &0\cr
1 - \pi      &0   &1   &1 &0                  &0       &-1\cr
\pi          &0   &1   &1 &1                  &1/\pi   &1/\pi - 1\cr
1 - \pi      &1   &0   &1 &1                  &1/(1-\pi) &1/(1-\pi) - 1\cr
\pi          &1   &0   &1 &0                  &0       &-1\cr
1 - \pi      &1   &1   &2 &1                  &1/(1-\pi) &1/(1-\pi) - 2\cr
\pi          &1   &1   &2 &1                  &1/\pi   &1/\pi - 2
}$$
Taking expectations for each possible state $(b_1, b_2)$ condenses this into the following:
$$\eqalign{
 b_1 &b_2 &\text{Error distribution} &\mathbb{E}[|\text{Error}|]\cr
 0   &0   &(0, 0)                    &0\cr
 0   &1   &(-1, 1/\pi-1)             &2(1 - \pi)\cr
 1   &0   &(1/(1-\pi)-1, -1)         &2\pi \cr
 1   &1   &(1/(1-\pi) - 2, 1/\pi - 2) &2 - 4\pi
}$$
In computing the expected absolute error I have assumed $\pi \le 1/2$: we will favor sampling the cheaper bit whenever possible.
Suppose, for example, $k = 3/2$.  That is, we aim to find a sampling scheme that keeps the absolute error to $3/2$ or less with "high probability" while minimizing the expected cost.  (I realize this choice of $k$ is artificial because we might attempt to improve the estimator--at risk of biasing it slightly--by constraining its estimates to 0, 1, or 2; but the purpose here is to look ahead to a situation with large $n$, where such improvements will be unlikely.  The mathematical patterns are important in this example, not its (lack of) realism.)  Evidently we would like to minimize the chance of paying for the expensive bit; that is, to make $\pi$ as small as possible.  The final column in the previous table constrains $\pi$; it implies that 
$$2(1-\pi) \le k,\quad 2\pi \le k,\quad 2 - 4\pi \le k.$$
For $k \ge 1$ all constraints can be satisfied provided
$$\max(1-k/2, 1/2 - k/4) \le \pi \le k/2.$$
Because the expected cost is
$$\mathbb{E}[\text{Cost}] = 1 + (c-1)\pi,$$
the unique cost-minimizing solution for $k=3/2$ is $\pi = 1/4$: regardless of the differences in expenses, we should sample the cheap bit with probability $3/4$ and the expensive bit with probability $1/4$, for an expected cost of $1 + (c-1)/4$.
This example reveals many things, including


*

*There can be solutions cheaper than simple random sampling (which in this case would select each bit with probability $1/2$ for an expected cost of $1 + (c-1)/2$).

*Finding a solution involves an optimization with an exponential number of (increasingly complicated) constraints in $n$.

*The selection probabilities will depend on the value of $k$.

*We cannot guarantee a fixed cost; all we can hope for--because randomization is essential--is an optimal expected cost.

*As always, the optimal sample size will depend on $k$ (the limit on the amount of error).
As a practical matter, I think most people would have more information than contained in this abstract problem.  Even if they didn't, if $n$ were large and a substantial sample size were contemplated, it would make sense to devote part of the sampling budget to the purpose of modeling a relationship between the costs and the values (the $c_i$ and the $b_i$).  With such a model in hand one could greatly simplify the analysis and identify an optimal or near-optimal program to spend the remaining sampling budget (or even, in some cases, to establish that the targeted error rate is unlikely to be achieved).  For this reason, and because the exponential growth in the constraints is troublesome, I am reluctant to pursue a more detailed analysis of this problem.
A: Despite promising not to, I have thought about this problem further.  This approach differs enough from the previous one I outlined that it seems worthwhile posting it as a separate reply.

Both @Aniko and @shabbychef are right: you need to "almost exhaust the population" with "greedy sampling."  But there's a twist--on occasion you can get away with a small sample.
Let's first change the notation (only slightly) to provide a clear interpretation of the constraint in the question.  Assume that a (small) threshold error probability $p$ and a maximum error size $\epsilon$ (in place of $k$, which will have uses elsewhere) have been specified, so that we require
$$\Pr[|\hat{B}-B| \leq \epsilon] \ge 1 - p$$ 
regardless of the (unknown) values of the $b_i$ (the "state" of the population).
Let $c_i$ be the cost of sampling element $i$ in the population.  Suppose $A$ is a subset of the population that is sampled with probability $\pi_A$, at a cost of $c(A) = \sum_{i \in A}{c_i}$.  Let $m$ be the number of elements of $A$ (written $m = |A|$) and let $k$ be the number of them that are 1's.  This information tells us that $B$ surely lies between $k$ and $k + n - m$ no matter what the state of the population may be.  Provided only that 
$$k + n - m - \epsilon \le \hat{B} \le k + \epsilon,$$
we are assured that the error associated with the sample $A$ cannot exceed $\epsilon$. This is not possible whenever $m \lt n - 2 \epsilon$.  Let's say that such a subset is "small" (with respect to $\epsilon$ and $n$) and otherwise is "large."
Here is perhaps the only subtlety: when a sample is small we still have a chance of not making an error, provided we use a randomized estimator.  An example of the best ones I can find is 
$$\hat{B} = k + (2j-1)\epsilon \text{ with probability } \frac{1}{l},\ j=1,2,\ldots, l$$
where $l = \lceil{\frac{n-m}{2 \epsilon}\rceil}$.  No matter what the values of the unsampled data are, this procedure has at least a chance of $2/l$ of being within $\epsilon$ of the correct total $B$.  Using such an estimator, the probability of an unacceptable error is bounded by the expected chance that the randomized estimate will have too great an error:
$$\Pr[|\hat{B}-B| \gt \epsilon] \le \sum_{A}{\pi_A(1 - \frac{1}{\lceil{\frac{n-|A|}{2 \epsilon}\rceil}})}.$$
(The coefficient when $|A| = n$ appears to be undefined but actually is zero; the sum really needs to extend only over the small subsets where randomization is actually needed.)
We have obtained a linear program for the sample probabilities $\pi_A$; to wit,
Minimize the expected cost $\sum_{A}{\pi_A c(A)}$
subject to


*

*$\sum_{A}{\pi_A(1 - \frac{1}{\lceil{(n-|A|)/(2 \epsilon)\rceil}})} \le p,$

*$\sum_{A}{\pi_A} = 1,$

*$\pi_A \ge 0$ for all subsets $A$.
This is a simple linear program (but with $2^n$ variables), easy to set up and easy to solve provided the population has about 16 or fewer bits.  When some of the costs are the same, the number of variables can be substantially reduced.  With larger populations, approximate methods would be needed to obtain a solution.   Generally, the solution cannot include any small samples with appreciable probability: most of the probability must be concentrated on large samples.  Among those, it will select the cheapest (which can be found with the greedy algorithm).  These heuristics allow for simple, rapid approximations to good solutions.

The solutions can be interesting.  Here are some examples.  As an abbreviation, let $f(c, \epsilon, p)$ indicate a solution for cost vector $c = (c_1, c_2, \ldots, c_n)$ and problem constraints $\epsilon$ and $p$.


*

*$f((1,1), 1/2, 1/20)$ samples each element with probability 9/20 and obtains no data with probability 1/10.  The expected cost is 0.9.
Why is this?  If we sample element 1 we observe $b_1$ and estimate $\hat{B}$ = $b_1 + 1/2$.  This is certainly within $1/2$ of the correct value.  When we take no sample we estimate that $B$ equals $1/2$ with 50% probability and otherwise estimate that $B$ equals $3/2$.  No matter what the population is, this guessing will return the correct answer (within an error of $1/2$) 50% of the time.  Thus we make an error greater than $1/2$ only 50% of $1/10$ of the time, which meets the targeted error rate of $1/20$.

*$f((1,1,5,5), 1/2, 1/20)$ elects to sample both cheap bits no matter what.  In addition, there is a 45% chance it will also include bit 3 (but not bit 4) and a 45% chance it will also include bit 4 (but not bit 3).  The reasoning is similar to the previous situation.

*$f((1,1,5,5), 1/4, 1/20)$ samples the entire population with a $33/35$ probability and otherwise obtains no data with $2/35$ probability.

*$f((1,2,3,4), 1/2, 1/20)$ samples bits 1, 2, and 3 with $14/15$ probability and otherwise obtains no data.  The expected cost equals $84/15$ = 5.6.
A: If the costs $c_i$ are known a priori, it seems like a greedy sampling would give you some guarantees. That is, sample the $n-2k$ bits in order of increasing cost. This gives a $k$-error guarantee on $B$ with probability $1$ in the obvious way. I am curious if this strategy is the limit strategy of some sane sequence of strategies that provide a guarantee with probability $1-\epsilon$.
If the algorithm is to be deterministic, and the $c_i$ are set by an adversary, I do not think you can do better than this.
