Timeline for lower-bound for $Pr[X\geq EX]$
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 12, 2018 at 0:27 | review | Close votes | |||
| Apr 15, 2018 at 5:20 | |||||
| Apr 11, 2018 at 20:13 | answer | added | Michael | timeline score: 0 | |
| Jan 9, 2018 at 15:19 | comment | added | Iosif Pinelis | A recent result concerning this is in arxiv.org/abs/1712.00519 . | |
| Nov 25, 2014 at 22:48 | answer | added | fedja | timeline score: 12 | |
| Nov 25, 2014 at 20:20 | comment | added | Ryan O'Donnell | @fedja: I'm almost certain it's still open. I took a small try at it once. But besides agreeing with the fact (written in Feige's paper) that with enough painful work one could probably push his $c$ up a little bit beyond the $1/13$ (or whatever) he achieves, I had no ideas :) | |
| Nov 25, 2014 at 20:17 | comment | added | fedja | @Ryan O'Donnell. I've heard of it a couple of years ago but completely forgot it :-). Has it been solved by now? | |
| Nov 25, 2014 at 20:14 | comment | added | Ryan O'Donnell | I agree the question has issues, but while we're all here, I'm reminded of a beautiful problem of Uri Feige's, which at first glance seems like it cannot possibly be hard. (Warning: it is hard.) Let $X_1, \dots, X_n$ be independent and nonnegative, with $E[X_i] = 1$ for all $i$. Can one prove that $Pr[X_1 + \dots + X_n < n+1] \geq c$ for some universal constant $c > 0$? Can one achieve $c = 1/e$? | |
| Nov 25, 2014 at 19:37 | comment | added | Lucia | @fedja: Of course the example above, doesn't really have to do with numbers or primes. Suppose the $X_i$ are all $0$ with probability $1-\alpha$ and some value $a_i$ with probability $\alpha$. Then the expected value of $\sum X_i$ is $\alpha\sum a_i$. Estimate the probability that $\sum X_i$ is at least this expectation. A good bound for this would follow from the Manickam, Miklos, Singhi conjecture, and for certain ranges of $\alpha$ this would now follow from thework of Pokrovskiy arxiv.org/pdf/1308.2176.pdf . But perhaps I'm seeing more to this question than OP intended! | |
| Nov 25, 2014 at 19:23 | comment | added | Lucia | @fedja: Good point. Here's an example of what I have in mind. Factor a square-free number $N$ as a product of primes $p_1\cdots p_n$. Now take $a_i=\log p_i/\log N$, and $X_i=0$ with probability $1-\alpha$ and $a_i$ with probability $\alpha$. Then the expected value of $\sum X_j$ is $\alpha$, and the problem is to bound a weighted sum of divisors of $N$ that are at least $N^{\alpha}$. This problem was studied by Alladi, Erdos and Vaaler and Soundararajan, and when $\alpha$ is rational there is a lower bound depending only on $\alpha$ and not on $n$. | |
| Nov 25, 2014 at 19:10 | comment | added | fedja | @Lucia Well, even with the independence assumption, it is certainly not any good as posed. Take $X_1=1$ with probability $p>0$ and take $X_2=1-p$ with probability $1$. Then $EX=1$ but $P(X\ge 1)=p$. Can you pose the problem in some meaningful way? You seem to see something really interesting here, but the way the question is stated so far is just totally ridiculous even after all the comments. | |
| Nov 25, 2014 at 4:31 | comment | added | Lucia | So I had in mind the situation that the variables are all independent. It would be good for OP to clarify if that's to be assumed or not. The situation when the variables are independent is related to problems in combinatorial number theory (studied by Alladi, Erdos and Vaaler), and to the Manickam, Miklosh and Singhi conjecture in combinatorics (on which there has been interesting progress lately). | |
| Nov 25, 2014 at 1:16 | comment | added | fedja | Some extra assumption is certainly needed. Take arbitrarily small $p>0$ and put $X_1=X_2=1-p, X_3=0$ with probability $2p$ and $X_1=X_2=0, X_3=1-2p$ with probability $1-2p$. Then $EX=(2-2p)2p+(1-2p)^2=1$ but $P(X\ge 1)=2p$ | |
| Nov 24, 2014 at 17:20 | comment | added | Emil Jeřábek | If there is a lower bound, it certainly can’t be any better than $1/n$, unless you impose some independence condition: take $X_1=\cdots=X_n=1$ with probability $1/n$, and $X_1=\cdots=X_n=0$ otherwise. | |
| Nov 24, 2014 at 15:41 | comment | added | Lucia | This is actually a non-trivial and very interesting question. It should not be closed. I'll try to add an answer with references to related work if I get a chance. | |
| Nov 24, 2014 at 13:15 | review | Close votes | |||
| Nov 24, 2014 at 23:37 | |||||
| Nov 24, 2014 at 12:59 | comment | added | Joonas Ilmavirta | This does not look like a research level mathematical question. Please consult the StackExchange sites for mathematics (math.stackexchange.com) and statistics (stats.stackexchange.com) and decide which would be more suitable for your question. | |
| Nov 24, 2014 at 12:45 | review | First posts | |||
| Nov 24, 2014 at 12:50 | |||||
| Nov 24, 2014 at 12:44 | history | asked | LIU | CC BY-SA 3.0 |