Timeline for Beyond union bound
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2020 at 10:56 | vote | accept | user2316602 | ||
| Dec 21, 2020 at 20:41 | answer | added | Yuval Peres | timeline score: 4 | |
| Dec 21, 2020 at 5:08 | comment | added | Mark Schultz-Wu | 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. | |
| Dec 20, 2020 at 21:13 | comment | added | jlewk | 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. | |
| Dec 20, 2020 at 18:16 | comment | added | user2316602 | Thanks! I know LLL but didn't realize it fits my description. Thanks for pointing out, this was helpful. | |
| Dec 20, 2020 at 17:56 | comment | added | Geva Yashfe | 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$. | |
| Dec 20, 2020 at 16:16 | history | asked | user2316602 | CC BY-SA 4.0 |