Probability that five random unit disks fit in a disk of radius 3

Question

In Ten Digit Problems (in An Invitation to Mathematics: From Competitions to Research, Springer, 2011, pages 119–136), Lloyd Trefethen considers putting disks of unit radius randomly inside a disk of radius 3, subject only to the constraint that they not overlap any previous disk. He observes that at least three disks will always fit.

enter image description here

He then asks for the probability $p$ that five disks will fit, and estimates $p\approx 0.053$.

Question: What is $p$ to ten decimal places?

You might ask for the motivation. Trefethen notes that this is an instance of a "Tanemura parking problem," which is of interest in chemistry and physics. But Trefethen is a numerical analyst, and his primary interest is in efficient algorithms. He is not claiming that knowing this particular value of $p$ to ten digits is of particular mathematical importance. Rather, the point is that our apparent inability to compute more than 3 decimal places highlights a gap in our algorithmic toolkit. Trefethen writes, "There must be a way to solve it to high accuracy! ... I think a slick solution is still waiting to be found." Although Trefethen worked on the problem himself for a while with some students, it seems that it hasn't been seriously attacked by others, so maybe some MO readers can solve it?

• Iosif Pinelis: This is a problem of high-precision numerical integration over a domain of a rather high dimension; here the dimension is 9ドル$ and the domain seems rather complicated. So, here Trefethen seems to use the attention-catching title "Tanemura parking problem" to attract more attention to this kind of problems. Clearly, naive approaches will not work here: if, in each dimension, the range is divided in just 10ドル^2$ intervals, then we will already get about 10ドル^{18}$ grid points.
• Iosif Pinelis: Previous comment continued: So, one can try to use cubature formulas, but their theory seems to be focused on domains such as "a cube, a simplex, and other polyhedra". So, one would also have to transform the complicated domain in this 5ドル$-disk case to a combination of simpler polyhedral domains. One may note here that a coauthor of the linked book is Sobolev (as in Sobolev spaces), who spent latter decades of his life working mostly on cubature formulas.
• Iosif Pinelis: Previous comment continued: One can also try to use an Euler--Maclaurin formula with remainder for polytopes. However, one can be pretty sure that Trefethen was well aware of these approaches.
• Timothy Chow: @IosifPinelis I don't think Trefethen can be accused of using the attention-catching title "Tanemura parking problem." The title of his article, as I said, is "Ten Digit Problems." In his book, An Applied Mathematician's Apology, he lamented that this article, or some version of it, was even rejected by the arXiv for being too insubstantial. Trefethen has long used ten-digit problems as a device to engage students, but mentioning the "Tanemura parking problem" is, if anything, a device that I used to try to draw attention (or at least prevent the question from being instantly closed).
• Steven Stadnicki: Having thought about this more, I think my initial assessment was off; you can pretty straightforwardly randomize over the first two coins, and then probably the third with some measure of rejection sampling, but the last coin especially is a search problem (or as noted above, a question of the non-emptiness of a quadratic semialgebraic set) and I don't really see any good way of doing that other than 'the hard way'.

Answer 1

Note: As pointed out by Matthew Bolan in the comments, this argument is incorrect. I'm leaving it for now in the hope it could be fix, or that it would inspire another solution.

---

(削除) The probability seems to be 0ドル.057508 \pm 0.000007$. Note that a few arguments here are intuitive, so there's a possibility I've made a mistake somewhere. There's also some chance that my code has bugs. (削除ここまで)

My code is available here, and you can play around with the GeoGebra figures in the answer here.

By symmetry, all possible orders of the disks are equally likely (note: this is wrong, see the comments). We will therefore assume that they are sampled in the following order, then multiply the result by 12 (as we restrict to 10 possible permutations out of 120):

five disks in larger disk, 1 and 2 adjacent, 3 not adjacent to either.

We will now transition to the equivalent problem of placing points in a radius 2 circle such that no point is contained in a radius 2 disk centered in another point. This is exactly the requirement on the centers of the disks. All circles in the following diagrams have radius 2.

Using symmetry again for convenience, we may assume that the first point has $x$ coordinate 0ドル$. We will start by sampling it. Now let us consider the possible positions for the second point. The "best case" scenario has the other disks positioned in D, E, H:

Possible placements of 4 circles

So the second circle has to be in the area bounded by F, L, K.

Therefore we can multiply the success probability by the ratio of the area of FLK to the area of the disk minus the disk centered at C and then sample a point $G$ from that area (this is importance sampling):

Possible placement of second disk

For the third disk to be OK, it should be in the area bounded by NOE. Additionally, we can see that once we place a disk there we will necessarily obtain 5 disks: the two remaining disks have valid placements in I and D, and they can't block each other.

Therefore, we can simply compute the ratio of the areas NOE and IMD.

• Matthew Bolan: I don't see why all orders are equally likely. To give a 1 dimensional example, if we are trying to fit 3 intervals of length 1 in an interval of width 3.1, there is a 1/42 chance of succeeding with an order where we place the middle interval first, followed by the left and then the right, but the chance of placing the disks from left to right seems bounded above by 1/21 * 1/11 . I think a similar phenomena makes placing disks in your order much more likely than placing the disks in the order they appear around the circle.
• Daniel Weber: @MatthewBolan Ah, you're right - I confused the scenario with one where we restart if we place a disk intersecting an existing one, where all results are equally likely, but of course this isn't the case here. Do you think it might be possible to fix this in any way, maybe bounding the likelihood of other orders such that weaker estimates for them suffice?
• Matthew Bolan: I think you should be able to do a similar computation for the other possible orders. I think the main term will come from the permutations you have already handled and those which begin by placing disk 1 (blue) and then disk 3 (red) in your diagram. For 10 digits of precision as in the original question I think my estimates suggest you'll need to do all orders though.
• Daniel Weber: What permutations need handling? Numbering the disks 1 to 5 clockwise: we have 124 twice (because 153 is a mirror so it does have the same probability). Do all of 12345,12354,12534,12543,15234,15243,15432,15423 have the same probability? It feels so, as after the $i$th disk we should have uniform $i$ disks conditioned on being a continuous segment in a placement of five, but I'm hesitant to guess that without a proof now. There is also 13 which is equivalent to 14, and I think that's it?