# 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}$ to the statistic $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}$, as a function of the costs $c_i$?

• This sounds like it could be homework. Can you tell us why you care? – Warren Schudy Nov 18 '10 at 22:57
• Your problem might be too hard as stated. Suppose I have an instance where all $c_i = 1$ except for $c_1 = n$. Now my bit vector has $b_1 = 1$ and $b_n = 1$, with all other bits being zero. OPT can obtain a factor 2 approximation (or k=1) by querying that bit, but it will be difficult to find $b_n$ by random sampling in less than $\Theta(n)$ cost. – Suresh Venkat Nov 19 '10 at 0:15

• I am imagining that we know the $c_i$ ahead of time, so there is no learning involved. – Jack Nov 18 '10 at 21:32
• Then it depends on what you know about how $b_i$ and $c_i$ are related. If they are independent then the estimate using $k$ lowest cost samples is as good as an estimate using a uniform sample. Otherwise you have to learn the relationship between $c_i$s and $b_i$s anyway. (There's also the case when the relationship is known, but then you can get an estimate of your statistic without sampling at all.) – trutheality Nov 19 '10 at 3:42