Timeline for Shortest path through $\sqrt{n}$ points out of $n$
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 17, 2014 at 22:30 | comment | added | Douglas Zare | @John Gunnar Carlsson: It was from allocating the total distance $d$ into $m$ bins consisting of the $m-1$ steps and the unused distance. Equivalently, sum over the ways to allocate distances $0,1,2,...,d$ into $m-1$ bins. If $d=10$ then the path $(0,0)\to(1,1)\to(1,1)\to(3,4)$ would correspond to steps of $L^1$ sizes $2,0,5$ with $3$ unused. Allocating $d$ objects into $m$ bins is equivalent to choosing $m-1$ separators out of $d+m-1$ objects and separators. | |
| Jul 17, 2014 at 22:28 | comment | added | Christian Remling | @JohnGunnarCarlsson: I think I can answer this: it's the number of ways to partition the total distance $d$ into $m$ individual steps, where a step can be zero (this accounts for the extra $m-1$ on the top). This isn't the number of paths yet, it's the number of possible distance sequences we can encounter as we travel along a path of length $\le d$. | |
| Jul 17, 2014 at 21:30 | comment | added | John Gunnar Carlsson | @DouglasZare, can you explain where the term ${d+m-1 \choose m-1}$ comes from? I don't understand how this describes the number of paths. | |
| Jul 17, 2014 at 12:11 | comment | added | Douglas Zare | @Christian Remling: Yes, I meant the constant can be improved to be closer to the upper bound of $\sqrt{2}$. Using the $L^2$ norm directly improves the constant to $1/\sqrt{2\pi e}=0.24$. I'm not sure if avoiding the AM-GM inequality improves the constant more. | |
| Jul 17, 2014 at 7:50 | comment | added | Christian Remling | Thanks for the clarification. You can't be off by much with your method (the base of the $(\ldots)^{2m}$ can be off at most by a multiplicative constant) because an essentially stronger bound would prove the result also for paths of some length $L_n=o(\sqrt{n})$, which is false by John's argument. | |
| Jul 17, 2014 at 7:43 | comment | added | Douglas Zare | By the way, it looks nicer to do this analysis with integrals instead of sums, integrating over a simplex. The measure of a circle is still linear. I used a discrete sum to avoid worrying about the Jacobian. Also, the actual integral can be done instead of using the AM-GM inequality, but I think it is a little tricky and it would just affect the constant. One variation of that integral was on the Putnam exam. | |
| Jul 17, 2014 at 7:35 | comment | added | Douglas Zare | @Christian Remling: If you pick $n$ points IID uniform, then each of the roughly $n^{\sqrt{n}}$ possible paths is uniformly distributed, just as though you only picked those $\sqrt{n}$ points. They aren't independent, but the union bound/linearity of expectation does not depend on independence. We can count the expected number of paths of length less than $0.214$ and find it is asymptotically much less than $1$. Thus, the probability that the shortest path is shorter than $0.214$ is small. | |
| Jul 17, 2014 at 1:50 | comment | added | Christian Remling | This is a nice analysis, but the final step left me mildly confused. You seem to be assuming that the actual experiment (uniformly distributed points, then pick the shortest path) can be approximately described by instead imposing a uniform distribution on the paths. Is that clear? | |
| Jul 17, 2014 at 1:20 | history | answered | Douglas Zare | CC BY-SA 3.0 |