15
$\begingroup$

Inspired by a Putnam problem, I came up with the following question:

A point in randomly chosen in the unit cube, a sphere is then created using the random point as the center such that the sphere must be contained inside the cube (In other words, the largest sphere that fits). What is the probability that the center of the cube is contained inside the sphere created?

No real idea how to approach this one but thought some of you might find this interesting.

$\endgroup$
  • $\begingroup$ How is the radius of the sphere chosen? Is it the largest that fits or randomly from $0$ to that? $\endgroup$ – Ross Millikan Feb 28 at 16:39
  • $\begingroup$ @RossMillikan The largest that fits $\endgroup$ – Gabriel Feb 28 at 16:40
  • 1
    $\begingroup$ @joriki thanks for the reminder, I've edited the post $\endgroup$ – Gabriel Feb 28 at 18:51
  • 1
    $\begingroup$ One has to compute the volume of intersection of several paraboloids... Should be not too hard. $\endgroup$ – zhoraster Feb 28 at 19:49
  • 1
    $\begingroup$ In dimension 2, the answer is $(4\sqrt{2}-5)/3$. In dimension 3, I'm too lazy to compute this. $\endgroup$ – zhoraster Feb 28 at 20:45
8
$\begingroup$

As the probability is the same in all cubes, we can calculate it in the cube $[-1,1]^3$.

We can limit ourselves to the sixth of the cube where $z$ is positive and has the greatest absolute value of the three coordinates. Then the radius of the sphere is $1-z$, and the centre of the cube is in the sphere if $x^2+y^2+z^2\le(1-z)^2$. Thus the admissible area of $(x,y)$ is the intersection of the square $[-z,z]^2$ with the circle $x^2+y^2=1-2z$. A corner of the square lies on the circle if $3z^2=(1-z)^2$, that is, $z=\frac{\sqrt3-1}2$, and a midpoint of the square lies on the circle if $2z^2=(1-z)^2$, that is, $z=\sqrt2-1$.

Thus, for $0\le z\le\frac{\sqrt3-1}2$, the entire square lies within the circle, so the area is $4z^2$.

For $\frac{\sqrt3-1}2\le z\le\sqrt2-1$ the circle and square intersect. The four segments of the circle that extend beyond the square each have area $(1-2z)\arccos\frac z{\sqrt{1-2z}}-z\sqrt{1-2z-z^2}$, so the area is $\pi(1-2z)-4\left((1-2z)\arccos\frac z{\sqrt{1-2z}}-z\sqrt{1-2z-z^2}\right)$.

For $\sqrt2-1\le z\le\frac12$ the entire circle lies within the square, so the area is $\pi(1-2z)$; and for $z\gt\frac12$ the area is $0$.

Thus the desired probability is

$$ \frac68\left(\int_0^\frac{\sqrt3-1}24z^2\mathrm dz+\int_\frac{\sqrt3-1}2^{\sqrt2-1}\left((1-2z)\left(\pi-4\arccos\frac z{\sqrt{1-2z}}\right)+4z\sqrt{1-2z-z^2}\right)\mathrm dz+\int_{\sqrt2-1}^\frac12\pi(1-2z)\mathrm dz\right)\;. $$

The first and last integral evaluate to $\frac43\left(\frac{\sqrt3-1}2\right)^3=\sqrt3-\frac53$ and $\frac\pi4\left(1-2\left(\sqrt2-1\right)\right)^2=\pi\left(\frac{17}4-3\sqrt2\right)$, respectively. Wolfram|Alpha evaluates the indefinite form of the second integral to

$$ -\pi z^2+\pi z+4\sqrt{1-2z-z^2}\left(\frac{z^2}3+\frac z6-\frac56\right)+(6-z)\sqrt{1-2z-z^2}+\frac{15}2\arctan{\frac{1+z}{\sqrt{1-2z-z^2}}}+\frac12\arctan\frac{1-3z}{\sqrt{1-2z-z^2}}-4\arcsin\frac{1+z}{\sqrt2}+4(z-1)z\arccos\frac z{\sqrt{1-2z}} $$

but refuses to evaluate it with limits. Substituting the limits by hand yields

$$ -\pi\left(3-2\sqrt2\right)+\pi\left(\sqrt2-1\right)+\frac{15}2\cdot\frac\pi2-\frac12\cdot\frac\pi2-4\cdot\frac\pi2=\left(3\sqrt2-\frac52\right)\pi $$

at the upper limit and

$$ -\pi\left(1-\frac{\sqrt3}2\right)+\pi\cdot\frac{\sqrt3-1}2+\frac23-\sqrt3+\frac72\sqrt3-4+\frac{15}2\cdot\frac{5\pi}{12}+\frac12\left(-\frac\pi{12}\right)-4\cdot\frac{5\pi}{12}+4\cdot\frac{\sqrt3-3}2\cdot\frac{\sqrt3-1}2\cdot\frac\pi4=-\frac{10}3+\frac52\sqrt3+\frac{17}{12}\pi $$

at the lower limit, so the second integral evaluates to

$$ \frac{10}3-\frac52\sqrt3+\left(3\sqrt2-\frac{47}{12}\right)\pi\;. $$

Thus, the desired probability is

$$ \frac34\left(\sqrt3-\frac53+\frac{10}3-\frac52\sqrt3+\left(3\sqrt2-\frac{47}{12}\right)\pi+\pi\left(\frac{17}4-3\sqrt2\right)\right)\\=\boxed{\frac\pi4+\frac54-\frac98\sqrt3\approx0.086841}\;, $$

in agreement with Aaron’s calculation and simulation.

$\endgroup$
  • 3
    $\begingroup$ Well done as always, and thank you joriki! $\endgroup$ – Aaron Montgomery Feb 29 at 4:09
  • $\begingroup$ LOL. I guess I'm going to have to try to follow through with my slightly stronger use of symmetry and see what happens. This calculation reminds me of the "wrong" way of finding the volume inside the three cylinders $x^2+y^2=x^2+z^2=y^2+z^2=1$. With maximal use of symmetry, that problem is easy. $\endgroup$ – Ted Shifrin Feb 29 at 20:43
  • $\begingroup$ @TedShifrin: You mean this one? :-) But that has a rather simple result (in three dimensions). You may well be able to do better than I did here, but it's bound to be at least slightly complicated if the result is $\frac\pi4+\frac54-\frac98\sqrt3$... $\endgroup$ – joriki Feb 29 at 21:16
  • $\begingroup$ Yikes, no, just in $\Bbb R^3$. I can do it with no calculus at all, of course, but it's a one-line integral in polar coordinates if one takes full advantage of symmetry. I'll let you know if I get anywhere with this :P $\endgroup$ – Ted Shifrin Feb 29 at 21:24
  • 1
    $\begingroup$ @TedShifrin: Very nice! :-) The difference isn't so much the symmetry, I think we both made use of the same symmetries -- the difference is that I thought it would be easier to integrate over $z$ last, and that turned out to be quite wrong -- you're integrating over $z$ first and your outermost integral comes out much easier than mine. $\endgroup$ – joriki Mar 1 at 0:31
5
$\begingroup$

I'll try an approach using order statistics. Suppose the coordinates of the chosen random point are $(X_1, X_2, X_3)$. We can assume that the coordinates of the chosen point are all positive. (If they are not, we can reflect the point into the first octant.) Hence, $X_1, X_2, X_3$ are independent uniform random variables on $(0, 1)$.

Now, we define the order statistics $Y_1, Y_2, Y_3$ so that $Y_1$ is the smallest of the $X_i$ values, $Y_2$ is the middle value, and $Y_3$ is the largest value. Note that the $Y_i$ variables are neither uniform on $(0, 1)$ nor independent of one another.

There are two variables of interest: $R$, the radius of the sphere, and $D$, the distance from the chosen point to the origin. Note that $R = \min\{1 - X_1, 1 - X_2, 1 - X_3\} = 1 - Y_3 $ and that $D = \sqrt{X_1^2 + X_2^2 + X_3^2} = \sqrt{Y_1^2 + Y_2^2 + Y_3^2}$. The operative question is: what is $\mathbb P(D < R)$? That is, what is $$\mathbb P \left(\sqrt{Y_1^2 + Y_2^2 + Y_3^2} < 1 - Y_3 \right)?$$

First, a bit of algebra to clean this up: \begin{align*} \mathbb P \left(\sqrt{Y_1^2 + Y_2^2 + Y_3^2} < 1 - Y_3 \right) &= \mathbb P \left( Y_1^2 + Y_2^2 + Y_3^2 < (1 - Y_3)^2 \right) \\ &= \mathbb P \left(Y_1^2 + Y_2^2<1-2 Y_3 \right) \end{align*} We know the joint pdf of these order statistics to be $$f(y_1, y_2, y_3) = \begin{cases} 3!, & 0 < y_1 < y_2 < y_3 < 1 \\ 0, & \text{otherwise} \end{cases}$$ so we just need to integrate that density over the set $\{y_1^2 + y_2^2 < 1 - 2 y_3\}$ in the cube $[0, 1]^3$. Note that this requires in particular that $y_3 \leq 1/2$. I claim that this triple integral can be expressed as \begin{align*} \int_0^{1/2} \int_0^{\min\{y_3, \sqrt{1 - 2 y_3}\}} \int_0^{\min\{y_2, \sqrt{1 - 2y_3 - y_2^2}\}} 6 \, \textrm d y_1 \, \textrm d y_2 \, \textrm d y_3. \end{align*}

I don't know the analytic value of that integral (I haven't tried very hard yet), but Wolfram Alpha estimates it to be $\fbox{0.0868}$.


When I do a really long probability computation like this, I always assume I screwed up somewhere and verify my work with a Monte Carlo simulation. Here's that work in R:

spherecube <- function(){
  center <- runif(3, min=-1, max=1)
  radius <- min(abs(1 - center), abs(1 + center))
  sum(center * center) < radius^2
}

mean(replicate(100000, spherecube()))
# 0.08674

Aside from being an interesting problem, it's a great advertisement for the power of Monte Carlo simulations!

$\endgroup$
  • 1
    $\begingroup$ I've made some progress on analyzing that integral geometrically to eliminate the $\min$ functions in the limits, but it's quite obnoxious -- and even after that obnoxious work, I'm still faced with some rather annoying integrals. I suspect that there's some clever other way of viewing this problem that will more quickly yield a pretty closed-form answer, and I look forward to seeing someone post it! $\endgroup$ – Aaron Montgomery Feb 28 at 21:44
  • 1
    $\begingroup$ I hope to be doing so soon. (Whether it's pretty will be for you to judge :-). $\endgroup$ – joriki Feb 28 at 23:00
  • $\begingroup$ I believe that you can get around all this yucky min stuff by using symmetry to chop into a smaller region, as I suggested in my comment above. $\endgroup$ – Ted Shifrin Feb 28 at 23:04
  • $\begingroup$ @TedShifrin That sounds right, though I wonder how tractable the integrals that await are. I'm excited to see it done! $\endgroup$ – Aaron Montgomery Feb 28 at 23:07
  • $\begingroup$ It's not too bad, methinks. We just have to find the volume of that portion of the paraboloid $2x_1\le 1-\sum\limits_{i\ge 2} x_i^2$ inside that pyramid. $\endgroup$ – Ted Shifrin Feb 28 at 23:23
4
$\begingroup$

Here's the solution, confirming the previous answers, using symmetry as I suggested. I'll reorder my variables to conform with previous discussions. So we're going to consider the cube $[-1,1]^3$ and restrict to centers of the sphere in the pyramid $0\le x\le y\le z\le 1$. This means that the face $z=1$ will be the closest. The origin will be (on or) inside such a sphere if and only if $x^2+y^2+z^2\le (1-z)^2$, i.e., $2z\le 1-(x^2+y^2)$.

Over what region in the $xy$-plane does our region project? Since $x\le y\le z$, we must have $2y\le 2z\le 1-(x^2+y^2)$, which means $x^2+y^2+2y\le 1$, or $x^2+(y+1)^2\le 2$. This results in the portion of $0\le x\le y$ lying inside the circle $x^2+(y+1)^2\le 2$. Note that $0\le x\le \dfrac{\sqrt3-1}2$.

Setting up the triple integral, the volume we desire is $$\int_0^{\frac{\sqrt3-1}2}\int_x^{\sqrt{2-x^2}-1}\int_y^{\frac12(1-x^2-y^2)} dz\,dy\,dx,$$ and since we're comparing to the volume of the full pyramid, which is $1/6$, we take $6$ times this answer.

(We can also set this up nicely in polar coordinates: $$\int_0^{\pi/4}\int_0^{\sqrt{\cos^2\theta+1}-\cos\theta}\int_{r\sin\theta}^{\frac12(1-r^2)}\,r\,dz\,dr\,d\theta.)$$

The integral, multiplied by $6$, turns into \begin{align*} \int_0&^{\frac{\sqrt3-1}2} \big({-}5+4\sqrt{2-x^2}+3x^2-2x^2\sqrt{2-x^2}-(3x-3x^2-4x^3)\big)dx\\ &= \int_0^{\frac{\sqrt3-1}2} \big({-}5-3x+4x^3+4\sqrt{2-x^2}+6x^2-2x^2\sqrt{2-x^2}\big)dx \\ &= \frac54-\frac98\sqrt3+\frac{\pi}4. \end{align*}

$\endgroup$
  • $\begingroup$ This is nice. I agree with @joriki -- I don't think the main insight was the symmetry, but rather the coordinate order / polar coordinates. (If I chase the $\min$ stuff through in my solution, all that happens is that the same algebraic bounds like $0 \leq x \leq \frac{\sqrt 3 -1}{2}$, etc. fall out. Your suggestion on the main post to order the variables is morally the same as considering the order statistics, which is why we both had a 6 lying around in our integrals.) At any rate, nicely done! $\endgroup$ – Aaron Montgomery Mar 1 at 2:17
  • $\begingroup$ @Aaron: Yes, I noticed you'd made the same symmetry reduction. But I was puzzled by all the min's ... But you're right, of course, that, even having made the symmetry reduction, the wrong order of integration can still result in having to split into several integrals. $\endgroup$ – Ted Shifrin Mar 1 at 2:19
  • $\begingroup$ @TedShifrin Could you explain the rationale to restrict to centers of the sphere in the pyramid $0\leq x\leq y\leq z \leq 1$? $\endgroup$ – Gabriel Mar 5 at 16:00
  • $\begingroup$ @Gabriel: By restricting to $x,y\le z$ I know that the closest face is at $z=1$. If we project the region onto the $xy$-plane, we get a region whose boundary curve is $x^2+(y+1)^2=2$ when $x\le y$ and $(x+1)^2+y^2=2$ when $y\le x$. Restricting (and then using symmetry) allows us to do one iterated integral rather than two. $\endgroup$ – Ted Shifrin Mar 5 at 17:42

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.