Probability that randomly chosen points on a line segment each has distance > 1 with its adjacent point

Question

Suppose we have chosen $n$ random points in a line segment $[0, t]$, $n\leq t+1$. What is the probability that distance between each pair of adjacent points is > 1? Or more formally, let $U_1, U_2, ..., U_n \stackrel{iid}{\sim} U(0,t), n\leq t+1$, let $U_{(i)}$ denotes $i^{th}$ ordered statistic. Find $P(\cap_{i=1}^{n-1} U_{(i+1)} - U_{(i)} > 1)$?

Answer 1

Answer: $\mathbb{P}(\bigcap_{i=1}^{n-1} U_{(i+1)} - U_{(i)} > 1) = \frac{(t-(n-1))^n}{t^n}$.

1. $\mathbb{P}(\bigcap_{i=1}^{n-1} U_{(i+1)} - U_{(i)} > 1) = n! \cdot \mathbb{P} (\forall 1 \leq i \leq n-1 \colon U_i + 1 < U_{i+1})$:

First, note that $\mathbb{P}(\exists i,j \in \{1, \dots, n\}, i \neq j\colon U_i = U_j ) = 0$. ("Almost surely, all values are unique.")

Hence, $\mathbb{P}\left(\exists \pi \in S_n\colon U_{\pi(1)} < U_{\pi(2)} < \dots < U_{\pi(n)} \right) = \sum_{\pi \in S_n} \mathbb{P}\left(U_{\pi(1)} < U_{\pi(2)} < \dots < U_{\pi(n)} \right) = 1$, where $S_n$ denotes the symmetric group.

Since the $U_i$'s are i.i.d., every one of the orderings should have equal probability, i.e.

$\mathbb{P}\left(U_{\pi(1)} < U_{\pi(2)} < \dots < U_{\pi(n)} \right) = \frac{1}{n!}$ for all $\pi \in S_n$.

Furthermore, $$\mathbb{P}\left(\left\{ \bigcap_{i=1}^{n-1} U_{(i+1)} - U_{(i)} > 1 \right\} \cap \left\{U_{\pi(1)} < U_{\pi(2)} < \dots < U_{\pi(n)} \right\}\right) = \mathbb{P} \left(\forall 1 \leq i \leq n-1 \colon U_{\pi (i)} + 1 < U_{\pi(i+1)}\right)$$ for all $\pi \in S_n$.

Again, since each the $U_i$'s are i.i.d., each of the "spaced orderings" should be equally likely.

All in all, we have

\begin{align} \mathbb{P}\left(\bigcap_{i=1}^{n-1} U_{(i+1)} - U_{(i)} > 1\right) &= \sum_{\pi \in S_n} \mathbb{P}\left(\left\{ \bigcap_{i=1}^{n-1} U_{(i+1)} - U_{(i)} > 1 \right\} \cap \left\{U_{\pi(1)} < U_{\pi(2)} < \dots < U_{\pi(n)} \right\}\right) \\ &= \sum_{\pi \in S_n} \mathbb{P} \left(\forall 1 \leq i \leq n-1 \colon U_{\pi (i)} + 1 < U_{\pi(i+1)}\right) \\ &= \sum_{\pi \in S_n} \mathbb{P} \left(\forall 1 \leq i \leq n-1 \colon U_{i} + 1 < U_{i+1}\right) \\ &= n! \cdot \mathbb{P} \left(\forall 1 \leq i \leq n-1 \colon U_{i} + 1 < U_{i+1}\right). \end{align}

2. $\mathbb{P} (\forall 1 \leq i \leq n-1 \colon U_i + 1 < U_{i+1}) = \frac{(t-(n-1))^n}{n! \cdot t^n}$

Now that we have concrete ordering, we can calculate the probability using integrals:

Clearly, since the $U_i$'s are i.i.d., their joint probability density function is $$f(u_1, \dots, u_n) = \frac{1_{\{u_1, \dots, u_n \in [0,t]\}}}{t^n}.$$

Also, it should be clear that from $U_{n-1} + 1 < U_{n} \leq t$ we must have $U_{n-1} < t - 1$.

Inductively, we get $U_i < t - (n - i)$ (given that $ \forall 1 \leq i \leq n-1 \colon U_i + 1 < U_{i+1}$ occurs).

With that, we get for $p := \mathbb{P} (\forall 1 \leq i \leq n-1 \colon U_i + 1 < U_{i+1})$ (using Fubini)

$$p = \int_0^{t-(n-1)} \int_{u_1 + 1}^{t-(n-2)} \dots \int_{u_{n-2} + 1}^{t-1} \int_{u_{n-1} + 1}^{t} f(u_1, \dots, u_n) d u_n d u_{n-1} \dots d u_2 d u_1.$$

On that domain, $f(u_1, \dots, u_n) \equiv \frac{1}{t^n}$. Iteratively, we get

\begin{align} p &= \int_0^{t-(n-1)} \int_{u_1 + 1}^{t-(n-2)} \dots \int_{u_{n-2} + 1}^{t-1} \int_{u_{n-1} + 1}^{t} \frac{1}{t^n} d u_n d u_{n-1} \dots d u_2 d u_1 \\ &= \frac{1}{t^n} \cdot \int_0^{t-(n-1)} \int_{u_1 + 1}^{t-(n-2)} \dots \int_{u_{n-2} + 1}^{t-1} \int_{u_{n-1} + 1}^{t} d u_n d u_{n-1} \dots d u_2 d u_1 \\ &= \frac{1}{t^n} \cdot \int_0^{t-(n-1)} \int_{u_1 + 1}^{t-(n-2)} \dots \int_{u_{n-2} + 1}^{t-1} (t -1 - u_{n-1}) d u_{n-1} \dots d u_2 d u_1 \\ &= \frac{1}{t^n} \cdot \int_0^{t-(n-1)} \int_{u_1 + 1}^{t-(n-2)} \dots \int_{u_{n-3} + 1}^{t-2} \left[ \frac{-(t -1 - u_{n-1})^2}{2} \right]_{u_{n-2} + 1}^{t-1} d u_{n-2} \dots d u_2 d u_1 \\ &= \frac{1}{t^n} \cdot \int_0^{t-(n-1)} \int_{u_1 + 1}^{t-(n-2)} \dots \int_{u_{n-4} + 1}^{t-3} \int_{u_{n-3} + 1}^{t-2} \frac{(t -2 - u_{n-2})^2}{2} d u_{n-2} d u_{n-3} \dots d u_2 d u_1 \\ &= \frac{1}{t^n} \cdot \int_0^{t-(n-1)} \int_{u_1 + 1}^{t-(n-2)} \dots \int_{u_{n-4} + 1}^{t-3} \left[ \frac{-(t -2 - u_{n-2})^3}{3 \cdot 2} \right]_{u_{n-3} + 1}^{t-2} d u_{n-3} \dots d u_2 d u_1 \\ &= \frac{1}{t^n} \cdot \int_0^{t-(n-1)} \int_{u_1 + 1}^{t-(n-2)} \dots \int_{u_{n-4} + 1}^{t-3} \frac{(t -3 - u_{n-3})^3}{3 \cdot 2} d u_{n-3} \dots d u_2 d u_1 \\ &\vdots \\ &= \frac{1}{t^n} \cdot \int_0^{t-(n-1)} \frac{(t - (n-1) - u_{1})^{n-1}}{(n-1)!} d u_1 \\ &= \frac{1}{t^n} \cdot \left[ \frac{- (t - (n-1) - u_{1})^{n}}{n!} \right]_0^{t-(n-1)} \\ &= \frac{(t-(n-1))^n}{n! \cdot t^n} \end{align}

Thus,

$$\mathbb{P}\left(\bigcap_{i=1}^{n-1} U_{(i+1)} - U_{(i)} > 1\right) = \frac{(t-(n-1))^n}{t^n}.$$

Answer 2

@MXXZ answer is toooo beautiful to be the only solution :)

The denominator

Our $n$ points are distributed uniformly on $[0;t]$, so the denominator is $t^n$.

The nominator

Imagine a favorable arrangement of points. Favorable means all points have the distance at least 1 between them. Now cut a segment of length one to the right of points $1$, $2$, ..., $n-1$. You will be left with a segment of lenght $t-(n-1)$ and $n$ points uniformly distributed on it. So the nominator is $(t-(n-1))^n$.

And the probability is $$ \frac{(t-(n-1))^n}{t^n} $$

Sketch for $n=4$