如何从U(a,b)抽取n个间距≥d的样本？求高效非确定性算法

Great question—this is a classic problem where naive rejection sampling (generate n samples, check spacing, retry if invalid) becomes horribly inefficient when n is large relative to the interval [a,b] (i.e., when the required minimum spacing d eats up most of the interval length). Here's a clean, efficient non-deterministic approach that guarantees uniformly distributed valid samples:

Key Feasibility Check First #

First, confirm a solution exists: if (n-1)*d > b - a, it's impossible to fit n points with pairwise spacing ≥d into [a,b], so handle this case upfront (throw an error, return a warning, etc.).

The Efficient Algorithm #

Here's the step-by-step method that produces uniformly distributed samples meeting the spacing requirement:

1. Calculate the "free" space we have after accounting for the mandatory minimum spacing between n points:

   free_space = (b - a) - (n - 1)*d
   

   (This value must be ≥0 for a solution to exist.)

2. Generate n independent samples from the uniform distribution U(0, free_space)—let's call these x_1, x_2, ..., x_n.

3. Sort these n samples in non-decreasing order to get x_(1) ≤ x_(2) ≤ ... ≤ x_(n) (these sorted values act as our "offset" allocations in the free space).

4. Construct the final valid samples by adding the mandatory spacing offsets and the base interval start:

   y_k = a + x_(k) + (k-1)*d  # for k from 1 to n
   

Why This Works #

• Spacing Guarantee: For any consecutive samples y_k and y_{k+1}, the difference is (x_(k+1) - x_(k)) + d. Since x_(k+1) ≥ x_(k), this difference is at least d—exactly what we need.
• Uniform Distribution: This method leverages the properties of order statistics of uniform variables. The joint distribution of the y_k is identical to what you'd get if you uniformly sampled a set of n points in [a,b] that satisfy the spacing constraint. No bias is introduced here.

Example Code (Python) #

import numpy as np

def sample_with_min_spacing(a, b, n, d):
    # Feasibility check
    if (n - 1)*d > b - a:
        raise ValueError("Cannot fit n points with spacing d in [a,b]")
    
    free_space = (b - a) - (n - 1)*d
    # Generate n uniform samples in free space
    x = np.random.uniform(0, free_space, size=n)
    # Sort the samples
    x_sorted = np.sort(x)
    # Build the final samples
    y = a + x_sorted + np.arange(n)*d
    return y

Performance Note #

This runs in O(n log n) time (dominated by the sort step), which is vastly more efficient than rejection sampling—especially when the interval is nearly filled with the mandatory spacing (i.e., free_space is small relative to b-a). Rejection sampling would have an extremely low acceptance probability in that scenario, leading to potentially infinite retries.

内容的提问来源于stack exchange，提问作者Henrik4