Timeline for Convex combination iid Bernoulli random variables
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 31, 2019 at 3:56 | comment | added | TOM | I cannot do the computation now, but I am reasonably sure it leads to a decent dependency on $p$. | |
| Oct 31, 2019 at 3:53 | comment | added | TOM | I see. One last thought in the situation with $p>\frac{1}{2}$. For all $h\in \mathbb{R}$ the moment generating function $\mathbb{E} \exp( a_{1}X_{1}+\cdots+a_{n}X_{n})$ is maximized when $a_{i}=\frac{1}{n}$ (for convex linear combinations, here $\mathbb{E}$ stands for expectation). Now $\mathbb{P}(S\geq \frac{1}{2})=1-\mathbb{P}(S< \frac{1}{2})\geq 1-\mathbb{E} \exp(h(S-\frac{1}{2}))$ for $h<0$ (standard Hoeffding's trick). Now using the fact that the worst case weights are all equal and optimizing with respect $h<0$ yields a bound dependent only on $p$. | |
| Oct 30, 2019 at 9:30 | comment | added | Ron P | TOM, please note that we are interested in the probability of the event that S>p rather than S>1/2. | |
| Oct 30, 2019 at 1:01 | comment | added | TOM | In case there still is confusion, here is the link to the paper (the result of interest is stated on the very first page): core.ac.uk/download/pdf/82145794.pdf | |
| Oct 29, 2019 at 12:28 | comment | added | TOM | I just did. It is the full result with $p\geq 0.5$. | |
| Oct 29, 2019 at 2:26 | comment | added | kodlu | since links are not permanent can you please write out your answer explicitly? | |
| Oct 29, 2019 at 2:17 | comment | added | TOM | I forgot to add that this is true only for $p\geq \frac{1}{2}$. | |
| Oct 28, 2019 at 14:02 | comment | added | TOM | The latter bound is sharp as equality is achieved by taking just one such random variable. | |
| Oct 28, 2019 at 14:02 | comment | added | TOM | Ligett proved that for independent Bernoulli random variables $X_1, X_2, \ldots, X_n$ with parameter p. Let S be a convex combination of these variables. Then $$\mathbb{P}(S\geq 1/2) \geq p.$$ | |
| Oct 27, 2019 at 11:33 | comment | added | Ron P | Can you elaborate, TOM? | |
| Oct 25, 2019 at 19:09 | history | answered | TOM | CC BY-SA 4.0 |