Timeline for Mean maximum distance for N random points on a unit square
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 12, 2018 at 17:55 | comment | added | Silvia | @N.T. precisely. I think that is a more rigorous way of proceeding but it is true that, in the limit, the approximation works either way (and indeed agrees with Matt's answer). An interesting challenge would be to find accurate results for $n$ small. | |
| Dec 12, 2018 at 17:19 | comment | added | user114668 | @Silvia Oh, I think I see now where you are coming from! The probability of finding no point in the area $h$ is given by $\Pr[X <= 0]$ for $X$ following a Bernoulli distribution of $n$ trials with probability $h$, which is $(1-h^2)^n$, so $\Pr[D > \sqrt{2}-2h] \approx 1 - (1 - h^2)^n$ which has the expansion $n h^2$ for small $h$. | |
| Dec 12, 2018 at 13:51 | comment | added | user114668 | @MattF. That's a good point, actually, and I would not have added an answer had I noticed. I was blindsided by the fact that the linear approximation gives a coefficient that ends up being much closer. | |
| Dec 12, 2018 at 13:36 | comment | added | user44143 | Worth noting: you and I have converged on essentially the same argument in different language. Your “in the corner triangle with height $h$” corresponds to my “max x > u” with the change of variables $h=\sqrt 2-u/\sqrt 2$; and then your pdf is the linear approximation to mine, which makes your integral easier. | |
| Dec 12, 2018 at 13:32 | comment | added | Silvia | Thanks, nice intuition. However, there are some steps which I do not follow. $n h^{2}$ cannot be a probability (choose $h=2/\sqrt{n}$ and you get a probability equal to 4). Indeed, $n h^{2}$ is only the expected value of the number of points in the corner triangle. The number of points in such a triangle follow a Bernoulli distribution with probability $p=h^{2}$. It follows that $P(D > \sqrt{2} - 2h)$ is approximately $(1-e^{-h^{2}n})^{2}$... | |
| Dec 12, 2018 at 11:34 | history | edited | user114668 | CC BY-SA 4.0 |
added explanation
|
| Dec 12, 2018 at 8:13 | history | edited | user114668 | CC BY-SA 4.0 |
more samples in simulation
|
| Dec 12, 2018 at 7:56 | history | edited | user114668 | CC BY-SA 4.0 |
added 22 characters in body
|
| Dec 12, 2018 at 0:56 | history | edited | user114668 | CC BY-SA 4.0 |
added 9 characters in body
|
| Dec 12, 2018 at 0:21 | history | edited | user114668 | CC BY-SA 4.0 |
added 135 characters in body; edited body
|
| Dec 12, 2018 at 0:12 | history | answered | user114668 | CC BY-SA 4.0 |