What is the probability that two objects will intersect in a large volume? Let's say we have N (10,000 for simplicity) small objects (cubes with edge of size 1, or if easier to calculate, spheres with diameter 1), randomly scattered in a large volume, say a cube of dimensions 10,000x10,000x10,000 (or a sphere of diameter 10,000 if easier to calculate).
What is the easiest way to estimate the higher bound of probability that 2 of them will intersect?
I'm interested in simplicity rather than accuracy, e.g. overestimating the higher bound of that probability by 100 or 1000 times is fine. I'm more interested in EASY methodology of estimation.
 A: Let's consider a simpler case - with two objects. 
Suppose we have two intervals $I_1$ and $I_2$ of unit length and centers $X_1$ and $X_2$ that we independently and randomly place on a line of length 10. (For ease, I'll pretend that we "drop" an $X$ value and then generate the surrounding interval $I$. I'll also say the larger interval lies on [0,10].)
You can place $X_1$ wherever, except for anywhere in [0,0.5) or (9.5,10] of the interval. (If you place $X_1$ any closer to either edge, the interval will extend beyond the boundary.) Then when you place $X_2$, you need only concern yourself with making sure that a) it does not overlap with $X_1$ and b) it is a "valid placement." (Meaning that it doesn't extend beyond the boundary.)
Place $X_1$ somewhere on the line. Based on the placement of $X_1$, what are the remaining areas where $X_2$ cannot be placed? If $X_1$ is placed somewhere in [1,9], then we can say that $X_2$ can be placed anywhere on [0,10] as long as it doesn't fall in $I_1$. Since $I_1$ is of length 1 and the entire interval is of length 10, the probability that $I_2$ does not overlap with $I_1$ is 90%.
This gets trickier in the case where $X_1$ is placed in (0.5,1) or (9,9.5). This is because, in order for $X_2$ to be a valid placement, it cannot be placed near the boundaries of the larger interval, nor can $I_2$ overlap with $I_1$. It's certainly possible to derive this (and not necessarily difficult!) but depending on how rudimentary this can be and how this generalizes to higher dimensions with different shapes and more objects, you may just want to suppose a conservative case here as calculations for more objects will likely get computationally intensive pretty quickly.
Ultimately, the probability of no overlap is going to be $P(\text{no overlap}) = P(\text{shape 2 doesn't overlap with shape 1})*P(\text{shape 3 doesn't overlap with shape 2 or shape 1})\cdots$. If you disregard any issues with the boundary (i.e. assume that if a shape overlaps with the boundary, it's fine), then you can estimate that the probability that shape $a_i$ does not overlap with shapes $a_1, \ldots, a_{i-1}$ is the ratio of the volume of shape $a_i$ to the remaining volume in the container after filling the container with shapes $a_1, \ldots, a_{i-1}$. Taking the boundary into account makes this more complex. If you assume no boundary issues, then your estimate of no overlap will be conservative, meaning that your estimate of overlap will be anti-conservative.
Per your post, in order to make your estimate of overlapping to be conservative and your estimate of not overlapping to be anti-conservative, you can assume that the center of any object cannot be sufficiently close to the boundary such that part of the object extends beyond the boundary. That is, you are basically making the container smaller because you don't want to risk any object being placed improperly. You can estimate that the probability that shape $a_i$ does not overlap with shapes $a_1, \ldots, a_{i-1}$ is the ratio of the volume of shape $a_i$ to the remaining volume in the smaller container after filling the smaller container with shapes $a_1, \ldots, a_{i-1}$.
Once you estimate the probability of no overlap, you can easily estimate the probability of an overlap by using $P(\text{overlap}) = 1 - P(\text{no overlap}) = 1 - P(a_n \text{does not overlap with} a_{n-1}, \ldots, a_1)•P(a_{n-1} \text{does not overlap with} a_{n-2}, \ldots, a_1) • \cdots$.
Assuming spheres (or that you place each object in a minimal-volume sphere - see comments below) with radii $r$ and the container is a sphere with radius $R$, we have:
$\begin{eqnarray*}
P(\text{overlap}) &=& 1 - P(\text{no overlap}) \\
&=& 1 - P(a_n \text{does not overlap with} a_{n-1}, \ldots, a_1)•P(a_{n-1} \text{does not overlap with} a_{n-2}, \ldots, a_1) • \cdots \\
&=& 1 - \frac{2\pi r^2}{2\pi R^2-2(n-1)\pi r^2}•\frac{2\pi r^2}{2\pi R^2-2(n-2)\pi r^2}•\cdots \\
&=& 1 - \frac{(2\pi r^2)^n}{\prod_{i=1}^n(2\pi R^2-2i\pi r^2)}
\end{eqnarray*}$
If your container isn't a sphere, then replace sphere volume $\pi R^2$ with container volume $V$ and calculate from there.
Hope this helps!
