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.



Beyond union bound
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](https://en.wikipedia.org/wiki/Kolmogorov%27s_inequality#:%7E:text=In%20probability%20theory%2C%20Kolmogorov%27s%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.


