Timeline for Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2020 at 19:51 | comment | added | Penelope Benenati | Of course, but the case $n$ finite is important in the underlying research work I am doing. Thank you. | |
| Nov 14, 2020 at 19:48 | comment | added | ofer zeitouni | What I wrote is that the formula I gave should also be an (asymptotic) upper bound, that is, I believe that $\lim_{n\to\infty} m_n$. equals the formula I wrote. If you want a finite $n$ result then yes, by all means, start another question. I have no idea how to compute a finite $n$ upper bound. | |
| Nov 14, 2020 at 19:29 | vote | accept | Penelope Benenati | ||
| Nov 14, 2020 at 19:29 | comment | added | Penelope Benenati | Thank you once again @ofer. I also would need an upper bound, asking help for a rigorous proof showing that $m(n)$ is smaller than a certain constant I can obtain via numerical simulations, when $n$ is large enough (still finite). Do you suggest me to create another similar post for the upper bound? I hope this does not go against the rules of the community. | |
| Nov 14, 2020 at 18:25 | comment | added | ofer zeitouni | Asymptotically, 0 distance. Replace $1_{x<p<y}$ by $g_\epsilon(p,x,y)$ continuous, so that $g_\epsilon(p,x,y)=1$ if $x<p-\epsilon$ and $y>p+\epsilon$ and $g_\epsilon(p,x,y)=0$ if $x> p-\epsilon/2$ and $y>x+\epsilon/2$. Now you get a bound (that depends at $\epsilon$) and then at the end take $\epsilon\to 0$. | |
| Nov 14, 2020 at 17:28 | history | bounty ended | Penelope Benenati | ||
| Nov 14, 2020 at 17:27 | comment | added | Penelope Benenati | Thank you, interesting. By "tight", in my last question here, I meant the same. Could you please provide more information about how to quantify how far from the optimum one can go by mollification? | |
| Nov 14, 2020 at 16:49 | comment | added | ofer zeitouni | The only places where you need care (in writing a formal proof) is that $1_{x<p<y}$ is not a continuous function of $(x,y)$. But you can get around that by mollification, since $p$ has a smooth law. | |
| Nov 14, 2020 at 16:47 | comment | added | ofer zeitouni | By tight I mean that I expect it to give the correct asymptotics for the maximum (in spite of the fact that it is only a lower bound, which is what you asked about). The reasoning (which I have not tried to transform into a formal proof) goes as follows: suppose you have a near optimal $S=S_n$ (that nearly achieves the maximum). Consider the empirical measure. It has a converging subsequence (as $n\to\infty$) to some measure $\mu$. Now apply the argument I wrote with that $\mu$. | |
| Nov 14, 2020 at 12:01 | comment | added | Penelope Benenati | Thanks @ofer. Why do you say that you "expect [your approach] to be tight"? | |
| Nov 14, 2020 at 10:26 | comment | added | ofer zeitouni | @Penelope Benenati You are right, I misread. Corrected. | |
| Nov 14, 2020 at 10:25 | history | edited | ofer zeitouni | CC BY-SA 4.0 |
Corrected expression
|
| Nov 13, 2020 at 18:00 | comment | added | Penelope Benenati | Thank you for your answer @ofer. I am sorry, I think that I am missing why you wrote $x<p<y$ whereas I am interested in the case we have either $\max(x,y)\le p$ or $\min(x,y)\ge p$. | |
| Nov 11, 2020 at 8:50 | history | answered | ofer zeitouni | CC BY-SA 4.0 |