Timeline for Subgaussian norm of a symmetric $\{-1,0,1\}$ random variable
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 1, 2023 at 16:11 | comment | added | Iosif Pinelis | @ClementC. : "to bound the expectation of the maximum of $n$ such things with a $\sqrt{\log n}$ dependence" ... With what scaling? (Without scaling, it is obviously bounded by $1$.) Anyhow, because of the mentioned heavy tails for small $p$, I don't think you can get a Gaussian-like $\sqrt{\log n}$ rate of growth. On the other hand, if you are only interested in the best rate up to universal constant factor that you can get from the sub-Gaussianity, then my answer (and apparently fedja's too) should do, even for small $p$, because it gives you $\kappa(p)$ up to the factor $2$. | |
| Aug 1, 2023 at 12:09 | comment | added | Clement C. | @IosifPinelis Thank you! My end goal was to bound the expectation of the maximum of $n$ such things with a $\sqrt{\log n}$ dependence, hence the use of subgaussianity. I'll have a look at the second reference you linked. | |
| Jul 31, 2023 at 15:53 | comment | added | Iosif Pinelis | Previous comment continued: Cf. e.g. the Bennett--Hoeffding bound (formula (2.9)) and its refinements, such as this one, involving a "balanced" convolution of a Gaussian distribution and a Poisson distribution, thus covering well, in your case, all values of $p$. | |
| Jul 31, 2023 at 15:53 | comment | added | Iosif Pinelis | @ClementC. : It is not a good idea to use a Gaussian bound here for small $p$. Then the distribution (say $\mu_\xi$) of $\xi$ has rather heavy tails (say in the sense that the moments of $\xi$ grow relatively fast), and $\mu_\xi$ is much better approximated by a symmetrized Poisson distribution. | |
| Jul 30, 2023 at 22:58 | answer | added | fedja | timeline score: 8 | |
| Jul 30, 2023 at 14:54 | answer | added | Iosif Pinelis | timeline score: 8 | |
| Jul 30, 2023 at 10:09 | comment | added | Aryeh Kontorovich | you can even replace the 1/2 by 1/4, and that appears to be tight. | |
| Jul 30, 2023 at 10:02 | comment | added | Aryeh Kontorovich | Numerically, it appears that the subgaussian constant behaves something like $1/(2\log(1/p))$ -- which is qualitatively similar to what you get in Kearns-Saul for small p. | |
| Jul 30, 2023 at 10:00 | comment | added | Clement C. | Whoops. Not anymore, thanks! | |
| Jul 30, 2023 at 10:00 | history | edited | Clement C. | CC BY-SA 4.0 |
added 6 characters in body
|
| Jul 30, 2023 at 9:56 | comment | added | Aryeh Kontorovich | Isn't there a missing log in the numerator? | |
| Jul 30, 2023 at 9:09 | history | edited | Clement C. | CC BY-SA 4.0 |
edited title
|
| Jul 30, 2023 at 9:02 | history | asked | Clement C. | CC BY-SA 4.0 |