Suppose we are interested in the mean $\mu$ of a random variable $X$ but the only way to sample it is from known biased distributions $p_{\lambda}(x)$, such that $\left<{X}\right>_{\lambda} =\mu_{\lambda} \neq \mu$. However, the total average of all biased distributions is unbiased, i.e. $\left<\left<{X}\right>_{\lambda} \right> = \mu$. Suppose also that each biased distribution comes with an equal initial cost $C_0$ (expensive) and an extra cost for each subsample $C_1$ (cheap). Given an allotment of a total cost $C$, what is the optimal way to partition the resources between different distributions and within each of them to get the most precise estimate for this cost?

A simple discrete example of this problem would be having access to $N$ unfair coins, half of which only give tails and half of which only give heads, meaning that they are fair on average. If we have access to \$100 and the initial toss costs \$10, while subsequent tosses cost \$0.1, clearly the best strategy is to buy 10 coins and toss each one of them once. On the other hand, if we know that all coins are fair, the best strategy would be to toss a single coin as many times as we can. How can we formalise this problem mathematically in less obvious cases and in the continuous case? Is this possible?

  • $\begingroup$ In your example you know the distribution of the coins, I guess the general question you ask doesn't assume this? What do you know about the distribution? $\endgroup$ – Tim Jul 10 '20 at 12:55
  • $\begingroup$ I suppose that it would be asking too much to do that without any information. Let's suppose that one can get a reliable esimate of the lower moments of the distributions, e.g. one knows $\mu_{\lambda}$ and ${\sigma}^2_{\lambda}$ for each $\lambda$. $\endgroup$ – Godzilla Jul 10 '20 at 12:56
  • 1
    $\begingroup$ Do you know the distribution of $\lambda$'s? If yes, maybe this can be thought as a Gaussian mixture? $\endgroup$ – Tim Jul 10 '20 at 12:57
  • $\begingroup$ I don't necessarily know the distribution of the $\lambda$'s but I can sample from it, if this makes sense $\endgroup$ – Godzilla Jul 10 '20 at 13:00

I think I finally figured it out. First we define the parametric estimator:

$$\hat{\mu}_{M,N} = \frac{1}{M}\sum_i^M \hat{\mu}_{i;N}$$

Where $M$ is the total number of samplers we use and $N$ is the number of samples we draw from each one of them. Then we are interested in the variance of this parametric estimator:

$$\text{Var}(\hat{\mu}_{M,N}) = \frac{1}{M}\text{Var}(\mu_N) \equiv \frac{1}{M} \left(\left<\left<\mu^2\right>_{\lambda;N}\right> - \left<\left<\mu\right>_{\lambda;N}\right>^2\right)\\ = \frac{1}{M} \left(\left<\left<\mu^2\right>_{\lambda;N}\right> - \left<\left<\mu\right>^2_{\lambda;N}\right> + \left<\left<\mu\right>^2_{\lambda;N}\right> - \left<\left<\mu\right>_{\lambda;N}\right>^2\right)\\ =\frac{1}{M}\left( \left<\frac{\text{Var}_{\lambda}(X)^2}{N}\right> + \text{Var}(\mu_{\lambda})\right)$$

where $\left<\text{Var}_{\lambda}(X)^2\right>$ is the intra-sampler variance (which I am going to call $\sigma^2_{intra}$) and $\text{Var}(\mu_{\lambda})$ is the inter-sampler variance (which I am going to call $\sigma^2_{inter}$).

The cost function was defined as (note that here we include the first draw into the second term, unlike in the original question): $$C = C_0 M + C_1 M N$$

Now we do constrained minimisation of the variance so that the cost is constant and $M$ and $N$ are bigger than one. I will skip the steps, but finally one obtains:

$$N_{opt} = 1 \vee \left( \left\lfloor\sqrt{\frac{\sigma^2_{intra} C_0}{\sigma^2_{inter} C_1}}\right\rfloor \wedge \left\lfloor\frac{C-C_0}{C_1}\right\rfloor \right)$$

In our coin example, if all coins are double sided, such that $\sigma^2_{intra}=0$, then the above equation reduces to $N_{opt}=1$, and in the other example $\sigma^2_{inter}=0$, which means that $N_{opt}$ obtains its maximum possible value given the constraint, as expected.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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