6
$\begingroup$

Similar to Mean minimum distance for N random points on a one-dimensional line, but instead of only N random points, choose N and M random points and find the mean minimum distance between points of N and M, but NOT M and M or N and N.

So, given $x_1,x_2,...,x_N \in [0,1]$ and $y_1,y_2,...,y_M \in [0,1]$ (uniformly random), find the mean distance: $min(abs(x_i - y_j))$ with $i\in[1,N]$ and $j\in[1,M]$.

Ideally, the answer would include the probability of the points being a minimum of $d$ distance apart, like in the referenced question.

$\endgroup$
  • 1
    $\begingroup$ For $M=N=2$, I get $$24 \int_0^1 \int_0^a \int_0^b \int_0^c \frac{(b-c)+\min(a-b,c-d)+\min(a-b,b-c,c-d)}{3}dd\ dc\ db\ da = \frac{11}{90}$$ $\endgroup$ – Matt F. Nov 9 '17 at 16:36
  • 1
    $\begingroup$ This looks right according to my simulation: https://repl.it/OCGt/1 With 100,000 trials, I get 0.12270902036396046, which is close to 11/90 (0.1222...). Now it just needs to be generalized :) $\endgroup$ – J. Smitherson Nov 9 '17 at 17:02
  • 1
    $\begingroup$ For $M=N=2$ I did a numerical integration (not stochastic simulation) NIntegrate[ Min[Abs[x1 - y1], Abs[x1 - y2], Abs[x2 - y1], Abs[x2 - y2]], {x1, 0, 1}, {x2, 0, 1}, {y1, 0, 1}, {y2, 0, 1}] and got $0.122377$, a bit closer to the theoretical result than the stochastic simulation was. $\endgroup$ – David G. Stork Nov 10 '17 at 1:01
  • 1
    $\begingroup$ 4 Integrate[ Min[Abs[x1 - y1], Abs[x1 - y2], Abs[x2 - y1], Abs[x2 - y2]], {x1, 0, 1}, {x2, 0, x1}, {y1, 0, 1}, {y2, 0, y1}] $= 11/90$. $\endgroup$ – David G. Stork Nov 10 '17 at 1:26
  • $\begingroup$ @DavidG.Stork, I’m glad the straightforward integral works — I used the one I gave mostly because I could break it up into pieces small enough for WolframAlpha, using the three terms of the integrand, which correspond to k=1, k=2, k=3 in the answer. $\endgroup$ – Matt F. Nov 10 '17 at 21:26
4
$\begingroup$

Let $D_1$ be the answer conditioned on the leftmost point being at 0 and the rightmost point at 1 (colors irrelevant). Let $0 = x_1 \leq \ldots \leq x_{n + m} = 1$ be the ordered coordinates of points. We can see that $s_i = x_{i + 1} - x_i$ are equidistributed subject to $s_1 + \ldots + s_{n + m - 1} = 1$, and coloring is independent of $s_i$. The probability that there are exactly $k$ adjacent color changes in the sequence is $$\frac{{n - 1 \choose \lceil \frac{k - 1}{2} \rceil}{m - 1 \choose \lfloor \frac{k - 1}{2} \rfloor} + {m - 1 \choose \lceil \frac{k - 1}{2} \rceil}{n - 1 \choose \lfloor \frac{k - 1}{2} \rfloor}}{n + m \choose n},$$ since the sequence either starts with a white group, and has $\lceil (k + 1) / 2 \rceil$ white groups and $\lfloor (k + 1) / 2 \rfloor$ black groups, or vice versa.

Conditioned on the colouring, the smallest distance is equal to the minimum of $k$ instances of $s_i$ (it is irrelevant which ones due to symmetry). For $0 \leq t \leq 1 / k$, the probability of $\min(s_1, \ldots, s_k) \leq t$ is $1 - (1 - tk)^{n + m - 2}$. Integrating with density, we have $$E\min(s_1, \ldots, s_k) = \int_0^{1 / k} k(n + m - 2)(1 - tk)^{n + m - 3} tdt =$$ $$(n + m - 2) \int_0^1 z^{n + m - 3}\frac{1 - z}{k} dz = \frac{1}{k(n + m - 1)}$$ (note that the answer is correct in the special case $k = n = m = 1$ where some transformations were illegal). Hence $$D_1 = \frac{1}{(n + m - 1){n + m \choose n}}\sum_{k = 1}^{\infty}\frac{{n - 1 \choose \lceil \frac{k - 1}{2} \rceil}{m - 1 \choose \lfloor \frac{k - 1}{2} \rfloor} + {m - 1 \choose \lceil \frac{k - 1}{2} \rceil}{n - 1 \choose \lfloor \frac{k - 1}{2} \rfloor}}{k}$$

Finally, integrating by the span $s$ between extreme points we obtain the complete answer $$D = \int_0^1 (n + m)(n + m - 1)(1 - s)s^{n + m - 2} \cdot sD_1 ds = \frac{n + m - 1}{n + m + 1}D_1 =$$ $$\frac{1}{(n + m + 1){n + m \choose n}}\sum_{k = 1}^{\infty}\frac{{n - 1 \choose \lceil \frac{k - 1}{2} \rceil}{m - 1 \choose \lfloor \frac{k - 1}{2} \rfloor} + {m - 1 \choose \lceil \frac{k - 1}{2} \rceil}{n - 1 \choose \lfloor \frac{k - 1}{2} \rfloor}}{k}$$

When $n = m = 2$, we have $D = \frac{1}{5 \cdot 6}(\frac{2}{1} + \frac{2}{2} + \frac{2}{3}) = \frac{1}{30} \cdot \frac{11}{3} = \frac{11}{90}$, which matches the computations in the comments. Not sure if the sum can be simplified further, still the answer is feasible to compute.

The probability of the smallest distance being at least $d$ can be found along the same lines by computing $$\frac{(n + m)(n + m - 1)}{n + m \choose n}\sum_{k = 1}^{\infty}\left({n - 1 \choose \lceil \frac{k - 1}{2} \rceil}{m - 1 \choose \lfloor \frac{k - 1}{2} \rfloor} + {m - 1 \choose \lceil \frac{k - 1}{2} \rceil}{n - 1 \choose \lfloor \frac{k - 1}{2} \rfloor}\right) \times \\ \int_0^1 (1 - s)s^{n + m - 2} \cdot \max(0, 1 - \frac{kd}{s})^{n + m - 2}ds$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Absolutely fantastic! When m = n = 4, D = 1427/44100. Any other values can be checked with this python snippet. I'm still having trouble making the probability of the smallest distance computable. Any extra help would be greatly appreciated! $\endgroup$ – J. Smitherson Nov 10 '17 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.