Timeline for Proof of a statement from Steele's "Probability theory and combinatorial optimization"
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 25, 2013 at 18:39 | comment | added | ofer zeitouni | In fact, see mathoverflow.net/questions/124579/… which shows that there is nothing new under the sun... | |
| Aug 24, 2013 at 22:46 | comment | added | ofer zeitouni | One can actually prove this by the second moment method: Set $Z_n=\sum_{i\neq j=1}^n 1_{\|X_i-X_j\|<c/n}$. Then as in Igor's solution, $EZ_n\sim c^2$ while simple estimates show that $EZ_n^2$ is proportional to $c^2+c^4$ for $n$ large. By Cauchy-Schwartz, this shows that the probability to have $Z_n\geq 1$ remains bounded away from $0$ as $n$ increases, and taking $c$ large shows that this probability goes to $1$; a complimentary bound on $EZ_n$ with $c$ small shows that the right order is indeed $O(1/n)$. | |
| Aug 22, 2013 at 1:28 | history | edited | Igor Rivin | CC BY-SA 3.0 |
added a comment.
|
| Aug 22, 2013 at 1:26 | comment | added | Anthony Quas | I think it's $n^{-2/d}$ (which captures both of these) | |
| Aug 22, 2013 at 0:20 | comment | added | Igor Rivin | Yes, but in one dimension it is $1/n^2,$ I believe. | |
| Aug 22, 2013 at 0:12 | comment | added | Anthony Quas | so it sounds like you're agreeing with the OP, that the minimum distance between a pair of points should be $1/n$ not $1/\sqrt n$? | |
| Aug 22, 2013 at 0:07 | comment | added | Igor Rivin | That's because there was a typo :( | |
| Aug 22, 2013 at 0:07 | history | edited | Igor Rivin | CC BY-SA 3.0 |
fixed typo
|
| Aug 21, 2013 at 23:55 | comment | added | Anthony Quas | I don't understand this. If I read it right, you're saying the expected minimum distance is $\Omega(1)$ irrespective of the number of points. Of course, this violates the pigeonhole principle. | |
| Aug 21, 2013 at 23:50 | history | answered | Igor Rivin | CC BY-SA 3.0 |