I have a question about the problem of coming up with a random distribution of non-overlapping coins in a given two dimensional space. I don't understand why using the random sequential adsorption technique (picking an initial random position for one coin, then do the same for the next; if it overlaps, keep trying until you find a non-overlapping position for it and so on) is not equivalent to using Markov chains to solve the same problem.
Thanks!
The reason is that the successive picking process doesn't produce a uniform distribution on the possible center positions. Some positions are much more likely to be found by successive picking than others. For an obvious example, consider a near-packed configuration like oranges piled in a crate: in this case you will never make any such configuration by successive picks, you will just fail to fit that many oranges in the crate. But Monte-Carlo will eventually lead the oranges to settle into the right pattern, either by cooling and shrinking from a hot state in a big box, or by adiabatically raising the repulsion strength to infinity. The many-steps of the Monte-Carlo guaratee tha the distribution becomes uniform, because Markov chains converge to a unique stationary distribution generically.
To see specifically what's wrong with successive picks, go to one dimension, and consider putting two intevals of length 1 inside a region of length 3. If you plot the allowed positions of the two left most points you see that the distribution of the position of either one is far from uniform. Note that in this case, sequential picking will always succeed, but it will produce two intervals that are much closer than they have to be.
This is a problem studied in Gravitational Waves (GW) data analysis for example, where you need to sample the surfaces of possible (GW) signals to obtain a finite subset of the signals to compare (see matched-filtering) to the output of your detector. See for example this paper and references there.
The algorithms for non overlapping "coins" go under the name of "stochastic algorithms" in the GW literature, and they can be show to be more efficient than pure random sampling, but less efficient that regular lattice distributions (only true for the low dimensional case).
The point is that at least in 2 dimension it's possible to start from a stochastic distribution and start moving the "coins" around until they crystallize and reproduce an hexagonal lattice (which is know to be the optimal placement). The subject is still open because: optimal placement are not know for higher dimensional spaces, the (hyper)-surface my be curved, the metric tensor might be difficult to obtain or difficult to diagonalize... etc.
So in general the problem is still open and the answer will change from case to case, but in 2d for a flat surface given in coordinates where the metric tensor is the identity the problem is basically solved.
Regarding your question in particular the efficiency of your algorithm can be estimated and it's worse then an hexagonal lattice. Since with a Markov chain you can get closer to a lattice the two algorithm have clearly different performances.
Notice that I don't know up to which dimension things have been actually tested. "Weird" things can happen in higher dimensions: if you allow the coins (hyper-spheres) to overlap the random distribution becomes very efficient, but boundary effects become also determinant.
