MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
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

This looks like it might be related to reinforcement learning (in machine learning).

In the typical reinforcement learning problem an agent has a set of actions available to it and an unknown cost associated with each action. In your case the actions are to sample (and which element to sample), or to stop sampling and commit to the estimate. You could also view the action of committing to an estimate as having a cost depending on the quality of the resulting estimate.

Maybe you might find some useful literature there.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.