In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all possible simple cycles.
One way to do this would be to use a Markov chain whose states are sets of squares whose boundaries are simple cycles and whose transitions consist of choosing a random square to flip and keeping the flip when the modified set of squares still has a simple cycle as its boundary. One can get from any simple cycle to any other one in this way (using standard results about existence of shellings) so this eventually converges to a uniform distribution, but how quickly?
Alternatively, is there a better Markov chain, or a direct method for selecting simple cycles?
ETA: See this blog post for code to calculate the number of cycles I'm looking for, and pointers to OEIS for some of these numbers. As we know, counting is almost the same thing as random generation, and I infer from the lack of any obvious pattern in the factorizations of these numbers and the lack of a formula in the OEIS entry that there unlikely to be a known simple direct method. But that still leaves the questions of how quickly this chain converges and whether there's a better chain wide open.