So, I have a small question.
I'm currently designing a randomized algorithm. In each round, the algorithm samples $k$ i.i.d. 0-1-RVs, and I want to estimate the expected value of those RVs up to a multiplicative error of $1 + \varepsilon$, say.
AFAIK, the usual way to go about this is to use Chernoff bounds to determine the number of samples needed.
However, to do this, I need a lower bound on the expected value, which I do not have (or rather: I could give a very crude estimation which would not suffice to derive the result I need)
So my idea is: For any such RV $X$ we have $\E(X) = \Pr(X = 1)$ and $\Pr(X = 1) = 1 - \Pr(X = 0)$, and for my purposes it suffices to estimate either $\Pr(X = 1)$ or $\Pr(X= 0)$ well enough (rather than both).
I know that at least one of these probabilities is bounded from below by $1 / 2$, but I do not know which one of them.
Hence, I simply choose the one which the algorithm empirically found to have value $\geq 1 / 2$.
This, of course, could be wrong, and I need to account for this.
So I thought of the following: Suppose that the relative frequency of $i \in \{0, 1\}$ was at least $1 / 2$. If, say, $\Pr(X = i) < 1 / 4$, then the probability of choosing $i$ is very low, and since we see an absolute difference of $\geq 1 / 4$ we can apply Hoeffding's inequality to bound the probability of choosing $i$ in this case.
This, hopefully, yields that $\Pr(X = i) \geq 1 / 4$ with high probability if we chose it.
But this kind of feels wrong?
Also, I think I might be running into correlation issues if I use the same samples to both choose $i$ and estimate $\Pr(X = i)$.
But this could be fixed by taking independent samples for both tasks, I guess?