2
$\begingroup$

I am very curious whether there are some interesting techniques to deal with cases where union bound is not strong enough to give the desired result. I am only aware of the Bonferroni inequalities (take inclusion-exclusion and cut the expansion short. Based on whether you cut it after the negative or positive sign, you get one or the other inequality).

Are there any other things that might be helpful? References to papers where such a thing is used would be very useful, too.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ The Lovasz local lemma is one such tool. If $X_1,...,X_n$ is a collection of random variables with values in $\{0,1\}$, it gives a bound on $p_0 = P(X_1 = \ldots = X_n = 0)$ when each variable only depends on a few of the others. Specifically, if $P(X_i = 1) \le p$ for each $i$, each variable $X_i$ only depends on at most $d$ other variables among $X_1,\ldots,X_n$, and $4dp<1$, then $p_0>0$. $\endgroup$
    – Geva Yashfe
    Commented Dec 20, 2020 at 17:56
  • $\begingroup$ Thanks! I know LLL but didn't realize it fits my description. Thanks for pointing out, this was helpful. $\endgroup$
    – user2316602
    Commented Dec 20, 2020 at 18:16
  • 1
    $\begingroup$ If you take a subset $T$ of the sphere in $R^n$ and $z\sim N(0,I_n)$ then the union bound tells you that $\sup_{t\in T} t^Tz$ is at most of order $\sqrt{2\log|T|}$. However, this is far from being sharp: the order of magnitude of $\sup_{t\in T} t^Tz$ is instead given by Talagrand's generic chaining functional, which gives in a sense the best possible multi-scale approximation of the set $T$ for this problem. $\endgroup$
    – jlewk
    Commented Dec 20, 2020 at 21:13
  • $\begingroup$ A very common technique when the union bound is not strong enough is to first apply a Chernoff bound, and then the union bound. Of course this still uses the union bound, but it suffices to get results where "just" the union bound does not. $\endgroup$
    – Mark Schultz-Wu
    Commented Dec 21, 2020 at 5:08

1 Answer 1

Reset to default
4
$\begingroup$

The subject of maximal inequalities exactly concerns bounds that improve upon the union bound. These started with Hardy-Littlewood in analysis. Perhaps the earliest example in probability theory is Kolmogorov's inequality [1] (which improves on Chebyshev's inequality followed by a union bound. ) Later came Doob's martingale maximal inequalities (see e.g. [2], [3]). Another example is the Maximal_ergodic_theorem [4] which is a different improvement on Markov inequality followed by a union bound. One of my favorites is Starr's inequality [5], see the appendix of [6] for a short proof. A novel direction in discrete spaces is [7].

[1]https://en.wikipedia.org/wiki/Kolmogorov%27s_inequality#:~:text=In%20probability%20theory%2C%20Kolmogorov's%20inequality,the%20Russian%20mathematician%20Andrey%20Kolmogorov.

[2] https://en.wikipedia.org/wiki/Doob%27s_martingale_inequality

[3] http://bass.math.uconn.edu/math5160f14/post4b.pdf

[4] https://en.wikipedia.org/wiki/Maximal_ergodic_theorem

[5] Norton Starr. Operator limit theorems. Transactions of the American Mathematical Society, pages 90–115, 1966.

[6] Basu, Riddhipratim, Jonathan Hermon, and Yuval Peres. "Characterization of cutoff for reversible Markov chains." The Annals of Probability 45, no. 3 (2017): 1448-1487. https://arxiv.org/pdf/1409.3250.pdf

[7] Harrow, A.W., Kolla, A. and Schulman, L.J., 2014. Dimension-Free L2 Maximal Inequality for Spherical Means in the Hypercube. Theory of Computing, 10(3), pp.55-75.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .