MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please consider two processes:

Process 1 - I simulate random sequential adsorption of discs on the unit square in the continuum limit, randomly selecting real number coordinates and rejecting the point if placing a disc at this point leads to any disc-disc overlaps. I continue this process until I reach a disc surface density of $P$.

Process 2 - I perform process 1 until I reach a disc surface density $Q > P$. I then randomly select and prune discs from the surface until the disc surface density is $P$.

Provided a sufficiently large number of discs to achieve a surface density of $P$ and/or a sufficient gap between $P$ and $Q$, is it possible to detect when Process 2 has occurred? More specifically, say I present you with a simulation result and ask you to tell me if Process 2 occurred. To what extent, if any, is it possible for you to discern this?

An explicit statement (which may be nonsense): "It is inherently unfair to simulate RSA to a surface density of discs $Q$, randomly select and remove discs reducing the disc surface density to $P < Q$, and then claim that the probability distribution of discs on the surface if fundamentally the same as if I had originally simulated RSA to a density of only $P < Q$."

share|cite|improve this question
up vote 1 down vote accepted

These distributions on sets of discs with density $P$ will differ.

Here is a big simplification: Instead of a surface, let's pack line segments on $\mathbb{R/Z}$. Let's place $3$ segments of length $1/10$, and then delete one, and consider the distribution on the distances between the intervals. Without loss of generality, assume the first is placed at $[0,1/10]$. The start of the second is uniformly distributed from $1/10$ to $9/10$. Then there might be one or two intervals, of total lengths between $6/10$ and $7/10$ where we can place the third interval. If we delete the last interval, we get the same distribution as if we only placed two, a constant density of $5/2 = 2.5$ on distances between $0$ and $4/10$. Otherwise, we might as well delete the second. Then the density at $0$ is $5/2 + 5/2 \log 7/6 \approx 2.885$, a little higher than between $2/10$ and $4/10$, where the density is $5/3 + 5 \log 7/6 \approx 2.437$. The $2/3:1/3$ weighted average of this with the uniform distribution on $[0,4/10]$ is also not uniform. When you take $2$ segments out of $3$, it is a little more likely that they are close together than if you only chose $2$, since there are more possibilities so that the first and third intervals are close.

The same should be true in two or more dimensions. If you place three discs, and then delete one, the remaining two should tend to be slightly closer than if you simply place two discs. Closer locations of the third disc overlap and rule out fewer possibilities for the second disc given that the second doesn't overlap the first.

share|cite|improve this answer

Some realizations of surface density $P$ have a sufficiently regular arrangement of discs that there is no space left to reach the larger density $Q$, without overlapping discs. For these realizations the occurrence of Process 2 can therefore be excluded. I would think that this is the only conclusion you can reach with certainty, but it is reasonable to assume that if you see a highly irregular arrangement of discs, with closely packed regions separated by large voids, then this was produced by Process 2 and not directly by Process 1.

So indeed, these two procedures are not statistically equivalent.

share|cite|improve this answer
@Carlo Beenakker Maybe we could handle what you're talking about by conditioning my presentation of a simulation result on having been able to achieve a density $Q$? I suppose what I'm attempting to address is the notion that in the "pre-jammed" state during Process 1, the probability of placing a disc at a certain location depends on the local geometry of previously placed discs, which will look different as we increase the disc surface density. However, going backwards, we uniformly select and remove discs, possibly generating a different surface patterning. – A.T. Apr 18 '13 at 13:18
@Carlo Beenakker Then again, this could be nonsense since discs are placed randomly, and if we remove a disc, we could just as well have not placed it there in the first place. – A.T. Apr 18 '13 at 13:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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