# Hoeffding type concentration result for the inverse of a sum of iid random variables

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.

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.

• 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. Jun 16, 2021 at 7:06