If two points on a lattice are connected with probability p (Thane, I'm replacing your p with 1-p), then you can start to write a power series for expected cluster sizes based on counting polyominoes. If p=0, the cluster size is always 1, so the constant term in this series is 1. One needs to be careful with definitions. You can ask, "what is the expected size of the cluster to which a randomly-selected point belongs?" Or you can ask about a randomly-selected *cluster*; this is a smidge harder to define. (The usual cludge is that this is the limit, as d increases, of the expected size of all clusters impinging on a randomly-selected d-by-d square of points.) The point model is way easier. The probability that a point belongs to a cluster of size 1 is q^4 (using the usual convention that q = 1-p). Larger cluster sizes require at least one bond, so larger clusters contribute nothing to the constant term of our power series. This confirms that the constant term is 1. The one-point cluster also contributes -4p to the linear term, 6p^2 to the quadratic term, and -4p^3 to the cubic term. The chance that a point belongs to a cluster of size 2 is 4 p^1 q^6. Larger cluster sizes require more than one bond, so they never contribute anything to the linear term of the power series for the expected cluster size; we now know enough to say that the linear coefficient is 4. (It got -4 from the one-point cluster, and +8 from the two-point cluster.) The two-point cluster also contributes -48p^2 to the quadratic term, and 120p^3 to the cubic term. Three-point clusters look like one of the two trominoes. The straight tromino contributes 18 p^2 q^8 to the expected cluster size; the L tromino contributes 36 p^2 q^8; the total is 54 p^2 q^8. Now we know that the quadratic coefficient is 6 - 48 + 54 = 12. The trominos also contribute -432p^3 to the cubic term. To finish computing the cubic term is tedious. There are contributions corresponding to each of the five tetrominoes: 32 from the straight tromino, 128 from the L, 64 each for the T, skew, and square. The total is 352. So the sum of all the contributions to the cubic coefficient is -4 + 120 - 432 + 352 = 36. Having said all of that, I suspect I made a mistake. Although OEIS has lots of sequences starting 1, 4, 12, 36, none of them seem to have anything to do with bond percolation. On Tue, Feb 11, 2014 at 5:25 PM, Richard E. Howard <rich@richardehoward.com>wrote:
The most fun paper in this field (in my opinion) is by Last and Thouless in 1971.
In this era of Higgs Boson-sized experimental budget, it is a study in elegance. They punched carefully randomized holes in carbon paper (2D conducting sheet) and measured the resistivity as a function of hole density.
The experiment trumped the theory at the time and the apparatus (for once) actually cost less than the pencil/paper theory...
--R
Physical Review Letters, Vol 27, Number 25, 20 December 1971, pp1719-1722.
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, February 10, 2014 10:16 PM To: math-fun Subject: Re: [math-fun] Connected components in random Cartesian mazes
It is percolation theory; there is an enormous literature on it. Start with the Wikipedia article. I hope you have a spare lifetime to spend.
On Mon, Feb 10, 2014 at 10:00 PM, Thane Plambeck <tplambeck@gmail.com
wrote:
Draw a maze on a two-dimensional n x n grid by erecting a wall between each pair of adjacent (ie, distance one) lattice points independently with probability p.
Eyeballing these things in Mathematica, it looks to me like if p < 1/2, there tends to be one "large component" that connects almost all the cells that are not walled off into "locally small" (say 1x1 or 1x2) walled gardens.
I'm sure I can't be the first to have considered something like this.
I'd welcome information about prior work.
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun