[math-fun] Connected components in random Cartesian mazes
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/
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
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
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
Perhaps it would be difficult to reproduce this experiment today. Is it even possible to purchase carbon paper anymore? I heard a program on NPR (Planet Money, perhaps?) where they said that the last bastion of carbon paper was India, where the govt still records lots of official stuff typed on paper with carbon duplicates/triplicates/... At 02:25 PM 2/11/2014, Richard E. Howard 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...
< http://www.amazon.com/s/ref=nb_sb_noss?url=search-alias%3Daps&field-keywords... >. On Feb 12, 2014, at 6:55 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Perhaps it would be difficult to reproduce this experiment today.
Is it even possible to purchase carbon paper anymore?
I heard a program on NPR (Planet Money, perhaps?) where they said that the last bastion of carbon paper was India, where the govt still records lots of official stuff typed on paper with carbon duplicates/triplicates/...
At 02:25 PM 2/11/2014, Richard E. Howard 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...
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
When I sailed to Cuba a few years ago the Harbor Master came aboard to fill out paper work. He needed three copies but he only had one (used) piece of carbon paper so he had to fill out two by hand. Brent On 2/12/2014 6:55 AM, Henry Baker wrote:
Perhaps it would be difficult to reproduce this experiment today.
Is it even possible to purchase carbon paper anymore?
I heard a program on NPR (Planet Money, perhaps?) where they said that the last bastion of carbon paper was India, where the govt still records lots of official stuff typed on paper with carbon duplicates/triplicates/...
At 02:25 PM 2/11/2014, Richard E. Howard 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...
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Real 20th century engineers used Teledeltos paper, not carbon paper. See this article, and the comments about Bob Widlar, probably the best analog electrical engineer ever (well, maybe Faraday…). Google still thinks you can buy it in the UK. http://electronicdesign.com/analog/whats-all-teledeltos-stuff-anyway On Feb 12, 2014, at 4:34 PM, meekerdb <meekerdb@verizon.net> wrote:
When I sailed to Cuba a few years ago the Harbor Master came aboard to fill out paper work. He needed three copies but he only had one (used) piece of carbon paper so he had to fill out two by hand.
Brent
On 2/12/2014 6:55 AM, Henry Baker wrote:
Perhaps it would be difficult to reproduce this experiment today.
Is it even possible to purchase carbon paper anymore?
I heard a program on NPR (Planet Money, perhaps?) where they said that the last bastion of carbon paper was India, where the govt still records lots of official stuff typed on paper with carbon duplicates/triplicates/...
At 02:25 PM 2/11/2014, Richard E. Howard 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...
_______________________________________________ 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
I have not been understanding the discussion of solving percolation problems by punching holes in conductive paper. My problem is this: One is typically looking for the critical probability, a phase boundary at which (among other things) the modeled material changes from a conductor to an insulator. But on the insulator side of this transition, the paper will physically fall into separate pieces! Rather than go to the trouble of acquiring conducting paper and putting a voltage across it, why not just pull gently on opposite edges and see if it comes apart? I don't see how insulation can be achieved without physically disconnecting the material. Perhaps a more perspicacious funster can resolve my difficulty. On Wed, Feb 12, 2014 at 4:45 PM, Tom Knight <tk@ginkgobioworks.com> wrote:
Real 20th century engineers used Teledeltos paper, not carbon paper. See this article, and the comments about Bob Widlar, probably the best analog electrical engineer ever (well, maybe Faraday...). Google still thinks you can buy it in the UK. http://electronicdesign.com/analog/whats-all-teledeltos-stuff-anyway
On Feb 12, 2014, at 4:34 PM, meekerdb <meekerdb@verizon.net> wrote:
When I sailed to Cuba a few years ago the Harbor Master came aboard to fill out paper work. He needed three copies but he only had one (used) piece of carbon paper so he had to fill out two by hand.
Brent
On 2/12/2014 6:55 AM, Henry Baker wrote:
Perhaps it would be difficult to reproduce this experiment today.
Is it even possible to purchase carbon paper anymore?
I heard a program on NPR (Planet Money, perhaps?) where they said that the last bastion of carbon paper was India, where the govt still records lots of official stuff typed on paper with carbon duplicates/triplicates/...
At 02:25 PM 2/11/2014, Richard E. Howard 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...
_______________________________________________ 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
one could also perform a biological version of this experiment with swiss cheese... in three dimensions, both the holes and the cheese can form a connected set. Cris On Feb 12, 2014, at 6:13 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I have not been understanding the discussion of solving percolation problems by punching holes in conductive paper. My problem is this: One is typically looking for the critical probability, a phase boundary at which (among other things) the modeled material changes from a conductor to an insulator. But on the insulator side of this transition, the paper will physically fall into separate pieces! Rather than go to the trouble of acquiring conducting paper and putting a voltage across it, why not just pull gently on opposite edges and see if it comes apart? I don't see how insulation can be achieved without physically disconnecting the material. Perhaps a more perspicacious funster can resolve my difficulty.
On Wed, Feb 12, 2014 at 4:45 PM, Tom Knight <tk@ginkgobioworks.com> wrote:
Real 20th century engineers used Teledeltos paper, not carbon paper. See this article, and the comments about Bob Widlar, probably the best analog electrical engineer ever (well, maybe Faraday...). Google still thinks you can buy it in the UK. http://electronicdesign.com/analog/whats-all-teledeltos-stuff-anyway
On Feb 12, 2014, at 4:34 PM, meekerdb <meekerdb@verizon.net> wrote:
When I sailed to Cuba a few years ago the Harbor Master came aboard to fill out paper work. He needed three copies but he only had one (used) piece of carbon paper so he had to fill out two by hand.
Brent
On 2/12/2014 6:55 AM, Henry Baker wrote:
Perhaps it would be difficult to reproduce this experiment today.
Is it even possible to purchase carbon paper anymore?
I heard a program on NPR (Planet Money, perhaps?) where they said that the last bastion of carbon paper was India, where the govt still records lots of official stuff typed on paper with carbon duplicates/triplicates/...
At 02:25 PM 2/11/2014, Richard E. Howard 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...
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This reminds me of an old puzzle: You have an infinite square grid of 1 ohm resistors. What is the resistance between two adjacent nodes in the grid? More precisely, you have an infinte square grid of nodes. Each horizontally adjacent pair of nodes is joined by a 1 ohm resistor, and each vertically adjacent pair of nodes is joined by a 1 ohm resistor. What is the resistance between two adjacent nodes (either horizontal or vertical)? Tom Richard E. Howard writes:
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
Spoiler and references available at https://oeis.org/A211074 Charles Greathouse Analyst/Programmer Case Western Reserve University On Wed, Feb 12, 2014 at 3:43 PM, Tom Karzes <karzes@sonic.net> wrote:
This reminds me of an old puzzle:
You have an infinite square grid of 1 ohm resistors. What is the resistance between two adjacent nodes in the grid?
More precisely, you have an infinte square grid of nodes. Each horizontally adjacent pair of nodes is joined by a 1 ohm resistor, and each vertically adjacent pair of nodes is joined by a 1 ohm resistor. What is the resistance between two adjacent nodes (either horizontal or vertical)?
Tom
Richard E. Howard writes:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This problem was aired previously by Steve Witham just before Christmas 2007; or rather, its rather tougher relation where the nodes are one knight's move apart. I think the subject line might have been "xkcd points out dangers of math fun" ? I shan't spoil it for newcomers; but possess a record of the thread for anyone requiring a crib! WFL On 2/12/14, Tom Karzes <karzes@sonic.net> wrote:
This reminds me of an old puzzle:
You have an infinite square grid of 1 ohm resistors. What is the resistance between two adjacent nodes in the grid?
More precisely, you have an infinte square grid of nodes. Each horizontally adjacent pair of nodes is joined by a 1 ohm resistor, and each vertically adjacent pair of nodes is joined by a 1 ohm resistor. What is the resistance between two adjacent nodes (either horizontal or vertical)?
Tom
Richard E. Howard writes:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Consider the dual lattice, and prove that the critical probability is exactly p=1/2... Then consider placing hexagonal lily pads on the surface of a pond, and show that the critical probability for being able to cross the pond is again p=1/2. Hint: there are no draws in Hex. Cris On Feb 10, 2014, at 8: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
Yes, the standard question is, If you did that on an infinite grid, what is the probability that one of the connected components is infinite? It's proven that there always exists a critical probability p_0 in this and related situations where p > p_0 implies an infinite component, with probability 1; and p < p_0 implies no infinite component, with probability 1. This covers questions asked on a wide variety of infinite graphs where you can think of the "edges" in your example as the nodes, with the edges of the graph connecting any two adjacent "edges". There is also "site" percolation, which is just another way of looking at the same phenomenon: Here the chosen items are not the "edges" of an infinite graph, but the nodes. (So the corresponding graph is the same as the original grid.) Maybe the nicest case is the nodes of the triangular lattice. (Which correspond to starting with the hexagonal tessellation of the plane and coloring each tile red with probability = p, and asking what's the chance of there being a red connected component that's infinite. Here it's known that the critical probability is p_0 = 1/2 (and also that if p = 1/2, there will also be a infinite red component with probability = 1). As far as I know, most of these calculations of p_0 in various cases are *extremely* hard and require many lemmas and theorems. The pioneers in this field were Geoffrey Grimmett and Harry Kesten; a lot more information can be found in their books and papers. --Dan On 2014-02-10, at 7:00 PM, Thane Plambeck 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/
participants (11)
-
Allan Wechsler -
Charles Greathouse -
Cris Moore -
Dan Asimov -
Fred Lunnon -
Henry Baker -
meekerdb -
Richard E. Howard -
Thane Plambeck -
Tom Karzes -
Tom Knight