Random Mazes

The picture below shows a random maze. You can use your mouse to find the path from the bottom left corner to the top right corner. Clicking the ENTER button will draw a new maze, with new parameters if you wish to set them. The program was modified with permission from an original created by Mike Bostock using the algorithm of David Wilson. The maze has the property that it is possible to get to any white square within the boundary and there is only one solution that does not backtrack. In a grid this size (40x40), there are about 10^800 (one googol to the eighth power) such mazes. The maze chosen is equally likely to be any of these!

There are many interesting properties of such mazes. First, if the outer black boundary square is considered to be a single vertex, then the resulting black graph is a tree. It is actually a spanning tree in the sense that it includes every vertex in the black square grid within the boundary. Second, if the possible paths to all white squares through the maze are drawn, one again obtains a spanning tree (spanning all the white squares).

The solution path, which is part of this white tree and is drawn here in red, can be randomly generated by itself (without randomly generating the rest of the maze/tree) by using what is called loop-erased random walk. Namely, start at the starting point and choose one of the 2 white squares that neighbors it in the square grid, all such squares having equal probability. Then choose similarly a neighbor of this square in the grid (there are either 3 of them), and so on (most squares will have 4 neighbors to choose from) until reaching the ending point. This is a simple random walk from the starting point to the ending point in the square grid. It may, and very likely will, contain cycles (loops). If so, erase the cycles in the order in which they were created. The final path has the same probabilistic distribution as the solution path!

For more details and information on the mathematics related to this, see How to Get a Perfectly Random Sample From a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph by James G. Propp and David B. Wilson or A bird's-eye view of uniform spanning trees and forests, in Microsurveys in Discrete Probability, D. Aldous and J. Propp (eds.), Amer. Math. Soc., Providence, RI, 1998, pp. 135--162 by me. The wiggliness of the solution path was analyzed by Richard Kenyon in The asymptotic determinant of the discrete Laplacian, Acta Math. 185 no. 2 (2000), 239--286. The scaling limit of the solution path as the mesh size of the grid tends to 0 was found by Greg Lawler, Oded Schramm, and Wendelin Werner in Conformal invariance of planar loop-erased random walks and uniform spanning trees, Ann. Probab. vol. 32, no. 1B (2004), 939--995, part of the work that earned Werner a 2006 Fields Medal. For information on how to count the number of mazes, see Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005), 491--522 and Identities and inequalities for tree entropy, Combin. Probab. Comput. 19 (2010), 303--313 by me and references there.