Without appealing to a guess-and-check approach, how might I select a pair of random points inside of a sphere of radius $R$ s.t. the points always a distance $d \leq R$ apart? Can the selected points be 'random' in the sense that a large number of such pairs can be split into two equal-sized populations that independently appear uniformly distributed within the sphere's volume? If it simplifies matters, and I'm not sure it would, I would also be interested in the case of a cube of edge-length $R$.
So that I can better understand the distribution of point pairs: Imagine I select a pair of points meeting the above separation distance criterion. If I randomly select another such pair, what is the probability that the distance between the first points in either pair is $\leq \delta_1$, and the distance between the second points in either pair is $\leq \delta_2$ for some $\delta_1,\delta_2 \leq R$?
Best Answer
From an algorithmic point of view, a very simple and computationally effective way to produce points is exactly the guess and check that you say you don't want. [ You don't say, but I'm assuming you're working in 3 dimensions? As the dimensionality increases, so the methods that I'm talking about become progressively worse ]
Let $X$ be a randomly chosen point in the ball of radius $R$; let $Z$ be a randomly chosen point in the ball of radius 1. Then set $Y=X+dZ/|Z|$. If $Y$ lies in the sphere of radius $R$, then keep the pair $(X,Y)$; otherwise generate a new pair.
This is efficient because it's simple to generate points in a ball and the expected number of attempts you have to make to get a valid pair is small (if you take a spherical shell of radius $d$ centred at a point on the boundary of a ball of radius $R$, a lower bound for the probability of success is the proportion of the shell lying inside the ball. I haven't done the calculation, but this must be large, even for $d=R$.) Since the success probability is high, you don't have to repeat too often to get a valid pair.
Next notice that each pair of valid points has the same chance of being selected so that you are truly picking from the distribution you want.
To answer your question about uniform distribution, you can see from the construction that the first coordinate (and hence the second coordinate also since the distribution is symmetric) is not uniformly distributed in the sphere. For example if $d$ is a lot smaller than $R$, then if you pick $X$ near the boundary of the sphere, the probability of the pair being rejected is about 50%, whereas if you pick $X$ far from the boundary then the probability of rejection is 0.
This means that if you take the marginal distribution of either coordinate, it is biased towards being at the centre of the ball.