<p>Well what do you know -- in a recent paper of ours, <a href="https://arxiv.org/abs/1910.05270" rel="nofollow noreferrer">https://arxiv.org/abs/1910.05270</a>, the inequalities leading to (12) invoke Hoeffding where the <span class="math-container">$(b_i-a_i)^2=p_i^2$</span>, and further the <span class="math-container">$0\le p_i\le c$</span> satisfy <span class="math-container">$\sum_i p_i\le 1$</span>, which implies <span class="math-container">$\sum_i p_i^2\le c$</span> -- precisely the sort of heterogeneous Hoeffding bound I had in mind. BTW, the argument we use in (11) is actually unnecessary, as Hölder's inequality yields
<span class="math-container">$$ \sum_i p_i^2 \le ||p||_1 \cdot ||p||_\infty \le c.$$</span></p>

CC BY-SA 4.0
2019-11-02T20:14:04.373Z
2019-11-04T18:42:37.593Z
2019-11-04T18:42:37.593Z
Aryeh
<p>Yes. See for example the stronger concentration for the occupancy problem in the following note:</p>

<p><a href="http://sarielhp.org/teach/17/b/lec/10_martin_II.pdf" rel="noreferrer">http://sarielhp.org/teach/17/b/lec/10_martin_II.pdf</a></p>

<p>Theorems 10.3.1 and 10.3.2.
(This is also covered in the Randomized Algorithm book by Motwani and Raghavan).</p>

<p>The version stated here is the martingale version, but it is the same thing...</p>

CC BY-SA 4.0
2018-06-01T05:22:51.253Z
Very nice, I think I’ll put this on an exam!
Aryeh
CC BY-SA 4.0
2018-06-01T04:52:51.840Z
2018-06-01T04:52:51.840Z
Sariel Har-Peled
<p>Hoeffding's inequality for independent random variables <span class="math-container">$a_i\le X_i\le b_i$</span> states that their sum has sub-Gaussian tails, decaying as <span class="math-container">$\exp(-2t^2/\sum_i (b_i-a_i)^2)$</span>. Question: Are there any interesting applications exploiting the heterogeneous ranges? In all of the applications I'm aware of, either the <span class="math-container">$X_i$</span> all have the same range, or else Hoeffding/McDiarmid (and for that matter, Bernstein/Bennett) are simply too crude, and a sharper tool such as Kearns-Saul is called for (see, e.g., Theorem 1(i) in <a href="http://jmlr.org/papers/v16/berend15a.html" rel="nofollow noreferrer">http://jmlr.org/papers/v16/berend15a.html</a>, or Theorem 2.1 in <a href="https://projecteuclid.org/euclid.ecp/1465315542;" rel="nofollow noreferrer">https://projecteuclid.org/euclid.ecp/1465315542;</a> Talagrand's inequality also comes to mind of course). So again: is heterogenous Hoeffding actually ever used?</p>

<pr.probability>
Heterogeneous Hoeffding/McDiarmid
Aryeh
# Heterogeneous Hoeffding/McDiarmid

(Asked by: username_0 on 2018-05-31)

Hoeffding's inequality for independent random variables $a\_i\le X\_i\le b\_i$ states that their sum has sub-Gaussian tails, decaying as $\exp(-2t^2/\sum\_i (b\_i-a\_i)^2)$. Question: Are there any interesting applications exploiting the heterogeneous ranges? In all of the applications I'm aware of, either the $X\_i$ all have the same range, or else Hoeffding/McDiarmid (and for that matter, Bernstein/Bennett) are simply too crude, and a sharper tool such as Kearns-Saul is called for (see, e.g., Theorem 1(i) in <http://jmlr.org/papers/v16/berend15a.html>, or Theorem 2.1 in <https://projecteuclid.org/euclid.ecp/1465315542;> Talagrand's inequality also comes to mind of course). So again: is heterogenous Hoeffding actually ever used?

**Tags:** pr.probability

---

## 2 answers

### Answer by username_1 on 2018-06-01. Score: 9 | Accepted answer

Yes. See for example the stronger concentration for the occupancy problem in the following note:

<http://sarielhp.org/teach/17/b/lec/10_martin_II.pdf>

Theorems 10.3.1 and 10.3.2.
(This is also covered in the Randomized Algorithm book by Motwani and Raghavan).

The version stated here is the martingale version, but it is the same thing...

> **Comments:**
> **username_0**: Very nice, I think I’ll put this on an exam!  

---

### Answer by username_0 on 2019-11-02. Score: 1

Well what do you know -- in a recent paper of ours, <https://arxiv.org/abs/1910.05270>, the inequalities leading to (12) invoke Hoeffding where the $(b\_i-a\_i)^2=p\_i^2$, and further the $0\le p\_i\le c$ satisfy $\sum\_i p\_i\le 1$, which implies $\sum\_i p\_i^2\le c$ -- precisely the sort of heterogeneous Hoeffding bound I had in mind. BTW, the argument we use in (11) is actually unnecessary, as Hölder's inequality yields
$$ \sum\_i p\_i^2 \le ||p||\_1 \cdot ||p||\_\infty \le c.$$


---

