4
$\begingroup$

Consider a collection of $n$ i.i.d. Bernoulli random variables $\{ X_i \}_{i=1}^{n}$ with $\mathbb{E}[X_i] = \mu$.

Then, if $\hat{\mu}$ is the mean of the $n$ random variables, i.e. if, $$\hat{\mu} = \frac{1}{n} \sum_{i=1}^{n} X_i,$$ then, by Hoeffding's inequality we have the following concentration result,

$$\mathbb{P} (\hat{\mu} - \mu \geq \Delta) \leq \exp(-2n\Delta^{2}).$$

If instead of a concentration result on the mean $\hat{\mu}$, we were interested in a concentration result on its inverse, $\frac{1}{\hat{\mu}}$, what approach can we take?

That is, how can we obtain a Hoeffding like exponential decay bound on the probability,

$$\mathbb{P} \left( \frac{1}{\hat{\mu}} \geq a \right),$$

for some suitably chosen form of constant $a$.

Since $\frac{1}{\hat{\mu}}$ does not involve a mean over the direct samples of any random variable, I am not sure how to proceed.

$\endgroup$

1 Answer 1

4
$\begingroup$

It is possible to come up with something like this. Here is an example.

The first thing to note is that,

$$\hat{\mu}^{-1}=n/S_n$$

Where $S_n = X_1 + \dots + X_n$. Now under the assumption that the $X_i \sim Bern(p_i)$ we have the following Multiplicative Chernoff bound,

$$\Pr[S_n\geq(1+\delta)\mu]\leq 2\exp(-\mu\delta^2/3)$$

where $\mu = \mathbb{E} [X]$ and $\delta \in (0,1)$. Then notice that $f(x)=1/x$ is one-to-one and is decreasing on $\mathbb{R}_+$. Note that $S_n \in [0,\infty)$. Let us assume that $S_n \neq 0$. Then we have, $$\Pr[S_n\geq(1+\delta)\mu]=\Pr[S_n^{-1}\leq\frac{1}{(1+\delta)\mu}]=\Pr[nS_n^{-1}\leq\frac{n}{(1+\delta)\mu}]=\Pr[\hat{\mu}^{-1}\leq\frac{n}{(1+\delta)\mu}]$$

So,

$$\Pr[\frac{1}{\hat{\mu}}\leq\frac{n}{(1+\delta)\mu}]=1-Pr[\frac{1}{\hat{\mu}}\geq\frac{n}{(1+\delta)\mu}]$$

Or,

$$Pr[\frac{1}{\hat{\mu}}\geq\frac{n}{(1+\delta)\mu}] \geq 1-2\exp(-\mu\delta^2/3)$$

Which I guess in some sense is more of an anti-concentration result. I imagine using this approach you can come up with other bounds depending on your desired outcome.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer, I had seen the multiplicative chernoff bound in a HW problem once but its applicability here slipped me. I'll keep the answer open for another week before accepting the answer in case anyone else has a different idea. $\endgroup$
    – ijuneja
    Jun 16, 2021 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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