1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ This sounds like it could be homework. Can you tell us why you care? $\endgroup$
    – Warren Schudy
    Commented Nov 18, 2010 at 22:57
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Nov 19, 2010 at 0:15

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am imagining that we know the $c_i$ ahead of time, so there is no learning involved. $\endgroup$
    – Jack
    Commented Nov 18, 2010 at 21:32
  • $\begingroup$ 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.) $\endgroup$
    – trutheality
    Commented Nov 19, 2010 at 3:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .