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/