Timeline for How large can $\mathbf{P}[X_1 + X_2 + X_3 < 2 X_4]$ get?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7 at 13:19 | history | edited | Tobias Fritz | CC BY-SA 4.0 |
updated outdated statement
|
| Oct 7 at 6:05 | history | edited | Tobias Fritz | CC BY-SA 4.0 |
correction and tighter bound
|
| Jul 22 at 1:57 | history | edited | Tobias Fritz | CC BY-SA 4.0 |
typo
|
| Jul 21 at 17:04 | comment | added | Tobias Fritz | @WillSawin: I agree, I just haven't seen the added benefit in squeezing out another 1/60 :) | |
| Jul 21 at 14:28 | comment | added | Will Sawin | To get $N=29$ we know one of the three inequalities you stated must fail which means all the other inequalities must succeed. This gives $3$ sets of $29$ inequalities to check joint satisfiability for, which doesn't seem too hard to check by linear programming. | |
| Jul 21 at 5:40 | history | edited | Tobias Fritz | CC BY-SA 4.0 |
clarification
|
| Jul 21 at 5:34 | history | edited | Tobias Fritz | CC BY-SA 4.0 |
improved upper bound, mentioned Will Sawin's proof idea
|
| Jul 21 at 5:28 | history | edited | Tobias Fritz | CC BY-SA 4.0 |
improved bounds, mentioned Will Sawin's proof idea
|
| Jul 14 at 14:29 | history | edited | Tobias Fritz | CC BY-SA 4.0 |
deleted 14 characters in body
|
| Jul 14 at 14:07 | history | edited | Tobias Fritz | CC BY-SA 4.0 |
clarification
|
| Jul 14 at 13:26 | comment | added | Tobias Fritz | Right @WillSawin, good point! I was thinking that a compactness argument may be needed, but considering lower bounds at the same time is a clever way to avoid that. | |
| Jul 14 at 13:22 | comment | added | Will Sawin | I think the proof that the exchangeability upper bound is sharp is relatively easy: If there exist $n$ values $x_1,\dots,x_n$ such that $a$ of the $4 \binom{n}{4}$ possible versions of the inequality plugging in $4$ of the $n$ values are satisfied, then the probability distribution which takes each of the values $x_1,\dots,x_n$ with probability $1/n$ satisfies the inequality with probability at least $6 a /n^4$ which is asymptotic to the upper bound $a/ (4 \binom{n}{4})$ as $n\to\infty$. | |
| Jul 14 at 13:04 | comment | added | Tobias Fritz | Running some linear programs with the 30 inequalities that arise in the evaluation of the upper bound suggests that that system is actually infeasible, in which case we'd get an improved upper bound of $29/60$. It must be possible to turn this into a relatively concise human-readable proof, but I haven't done this yet. | |
| Jul 14 at 10:55 | history | answered | Tobias Fritz | CC BY-SA 4.0 |