18
$\begingroup$

I recently read the following "open problem" titled "Pennies on a carpet" in "An Introduction To Probability and Random Processes" by Baclawski and Rota (page viii of book, page 10 of following pdf), found here: http://www.ellerman.org/Davids-Stuff/Maths/Rota-Baclawski-Prob-Theory-79.pdf

"We have a rectangular carpet and an indefinite supply of perfect pennies. What is the probability that if we drop the pennies on the carpet at random no two of them will overlap? This problem is one of the most important problems in statistical mechanics. If we could answer it we would know, for example, why water boils at 100C, on the basis of purely atomic computations. Nothing is known about this problem.”

I was wondering if this problem goes by a more popular name and whether or not some form of progress has been made on it. In particular, references would be highly appreciated!

$\endgroup$
3
  • $\begingroup$ The authors phrased this badly: 'indefinite supply' is misleading. What they mean is 'n perfect pennies'. $\endgroup$
    – TonyK
    Sep 1, 2010 at 23:22
  • 3
    $\begingroup$ Perhaps "indefinite supply" stands for "unknown number". $\endgroup$ Sep 2, 2010 at 5:48
  • $\begingroup$ The model as described above is somewhat related to what's known as "random sequential adsorption", see e.g. the references in my answer here mathoverflow.net/a/63092. In RSA one discards pennies that overlap and then keeps adding more until it is impossible. In the hard disks model as described by Matthew Kahle below, one is studying the properties of a uniformly random configuration of nonoverlapping disks. $\endgroup$
    – j.c.
    Feb 11, 2016 at 13:36

4 Answers 4

10
$\begingroup$

This is the two-dimensional hard spheres model, sometimes called hard discs in a box.

See Section 4 of Persi Diaconis's recent survey article, The Markov Chain Monte Carlo Revolution. The point here is that even though it very hard to sample a random configuration of nonoverlapping discs by dropping them on the carpet (because the probability of success is far too small for any reasonable number of discs), but it is nevertheless possible to sample a random configuration via Monte Carlo.

$\endgroup$
10
$\begingroup$

One variation that was solved by Baxter is the hard hexagon model, a discrete version where the pennies are hexagons and they are constrained to have their centers on the vertices of a triangular lattice. This example is rather famous because the solution involves the Rogers-Ramanujan identities. See Baxter's book for more details. As far as I know, the analogous "hard square model" has not been solved.

$\endgroup$
6
$\begingroup$

Rota (on page $viii$ of his introduction, page 10 of the pdf file) is talking about the difficulty of having an analytic solution for statistical mechanics in the 2-dimensional and 3-dimensional cases, while it is possible to attack the problem somewhat in the one-dimensional case.

He also mentions how stochastic methods and simulation can be used to come up with a quick-and-dirty approximation of the answers by modeling the physical sysyem and using Monte Carlo methods: iterating the system with random steps.

Topics to research would be Monte Carlo methods, stochastic models, random walks, etc. Can you say a little more about exactly what it is that you wish to study or examine?

$\endgroup$
5
$\begingroup$

I suppose one could phrase the question this way: given $r$, $s$, $n$, and $\epsilon$, what is the probability that of $n$ points, selected uniformly and independently at random from a rectangle of dimensions $r$ by $s$, no two will be within $\epsilon$ of each other.

In the theory of uniform distribution modulo one, there is a concept of discrepancy which can be brought to bear on this problem. I hope that gives you a few keywords to look for.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.