Andy Latto <andy.latto@pobox.com> wrote:

While I think this is likely, I think more argument is needed to actually prove it. The duality argument shows that if there is a phase transition at probability p, there is also a phase transition at 1-p. But how does it show there is a phase transition at p = .5? Maybe there are two phase transitions, one at .37 and one at .63. Maybe there are no phase transitions at all, and the chance that most locations are accessible increases gradually with p, with no sudden jumps.

I'm sure it does increase gradually with p -- for small mazes. But as you repeatedly assemble four random mazes of a given size into a maze of twice the height and twice the width, it should become more and more unlikely that any p significantly less than 0.5 allows a solution or that any p significantly more than 0.5 doesn't allow a solution. By "solution," I'm thinking mostly about a west-to-east traversal of the maze. Consider two mazes in parallel, i.e. one north of the other. If p is such that the odds of a solution in each maze is 0.8, then the odds of a non-solution with them in parallel is 0.2^2 = 0.04. Actually, less, since there could be a solution partly through one maze and partly through the other. But call it 0.04. Now put two more mazes in parallel in series with the original two. Another 0.04. Since the two new ones are in series with the original two, we have to square 0.96 to get the odds of a solution. 0.9216. Actually, less, since it's possible that none of the solution exits from the first two line up with any solution entrances on the second two, but probably not much less. Of course by symmetry the odds are the same for a north-to-south traversal. Roughly speaking, if the maze size is infinite, if p exceeds 0.5 there will certainly be a single infinite connected set which most of the small squares are in, and will certainly not be any such set for the maze's dual. And if p is less than 0.5, it will be the other way around. I'm reminded of the Apollo Lunar Module ascent stage. It had to work, since otherwise the astronauts would be stranded on the moon. It used hypergolic fuel, so there were no worries about ignition. What was needed is a very reliable valve. It had to open when desired, and had to remain closed at all other times. (It would have been embarrassing had it spontaneously taken off while the astronauts weren't aboard.) Also, since the fuel was very corrosive, the engine couldn't be tested ahead of time. Every lunar module ascent engine was "tested" for the very first time only when it was taking off from the moon. So what they did was have four identical valves in series-parallel. That way any one valve could be open when it should have been closed, and any one valve could be closed when it should have been open, but the engine would still work perfectly. This amplified the odds both of the thing not taking off when it shouldn't and of the thing taking off when it should. Now imagine that the four valves themselves each consisted of four valves in series-parallel. And that each of those four valves consisted of four valves in series-parallel. *Those* valves could be very unreliable, with perhaps only a 2/3 probability of being open when they're supposed to be open, and only a 2/3 probability of being closed when they're supposed to be closed, and yet the overall system would still be highly reliable. That's how I envision these arbitrarily large random mazes. Large assemblages tend to have abrupt phase changes. A macroscopic amount of water (at reasonable pressures) is always either a gas, a liquid, or a solid, never a jelly. Similarly with all other simple substances. The sun has an sharp edge even though it's just a ball of gas. An avalanche on a large mountain always consists of a large amount of snow. You can hammer a rock hundreds of times and have no visible change. Then suddenly when a sufficient proportion of tiny internal cracks link up, the rock shatters into gravel in response to a hammer blow no larger than any of the previous hundred. Learning is often just as abrupt, when lots of small useless disconnected networks of related concepts, skills, facts, and therbligs in your mind link up and create a path between problem and solution. As for the possibility of there being two phase changes, what would the other one be? But there's no substitute for numerical simulation. I should actually construct connection matrices with the appropriate kinds of randomness, and measure the distribution of connected regions as a function of both p and the maze size. Of course this will require multiplication of large matrices, which is CPU intensive and memory intensive. It helps that I only care about zero and non-zero, so I can store 32 values in each 32-bit integer. Also, the matrix is symmetric, so I need only store half of it. Slightly less than half since the diagonal elements are always all non-zero.

Keith F. Lynch <kfl@keithlynch.net> wrote:

...

I haven't yet figured out how to generalize my dual insight to three-dimensional graphs.

I'm pretty sure that unless p is very close to 0 or very close to 1, both the 3D graph and the 3D graph's dual will almost certainly be well connected, letting you get from any face to any other face. That's because I'm thinking of a zero-dimensional explorer, i.e. a one-dimensional path. A better generalization to 3D should assume a one-dimensional explorer, i.e. a two-dimensional path. Hold a piece of string in your hands, and drag it through a 3D maze from north to south while keeping one end of the string to the west of the maze and the other end to the east of the maze. (You may need a helper with tweezers to keep the string on the right path.) Again, either the maze has such a solution between two opposite faces, or the maze's dual has such a solution between two different opposite faces, never both and never neither. One complication is that any such solvable maze would fall apart into two or more disconnected pieces. So would a placemat maze except that the lines are attached to the placemat. Clearly what's needed for a 3D maze is for all its parts to be firmly glued to a 3D block through a 4th dimension. I wonder if anyone has ever researched such paths. Or 3D paths through 4D mazes. (Drag a rubber sheet through a 4D maze.)