Exploring mazes at random

Abstract

We consider a probabilistic version of the depth-first search on mazes with two exits, and show that this algorithm has equal probability of finding either exit. The proof is combinatorial and uses an explicit involution.

This paper is intended for a general audience. 5 pages, 10 figures