Return to Question

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, polyominos may have holes.

(Update: these are sometimes also called two-dimensional lattice animals. For another model of random lattice animal, see this earlier MO question and discussion and references there.)

I would like to be able to sample a uniform random polyomino with $n$ squares, where $n$ is of the order $100$ or $1000$.

I am thinking of fixed polyominos, where two polyominos are considered equivalent only if they agree after a translation, but where rotations and reflections are in general distinct. But I might also be okay with sampling one-sided or fixed polyominos if that is for some reason easier or more natural.

The point is that I don't want to have to enumerate all the polyominos of this size. For $n=100$, enumerating all the polyominoes would already be far beyond the reach of modern computing. I am hoping that there is a random construction, or else a Markov chain that converges to the uniform distribution (i.e. every polyomino having equal probability). I would be interested in such a Markov chain, if it could be proved to converge to the uniform distribution, even without guarantees on the mixing time.

My first attempt at a random construction was to apply a randomized version of Redelmeier's method, or at least Wikipedia's description of this algorithm. But I am not sure if Wikipedia's description is correct. I copy it here, for the sake of completeness.

The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n-omino n times, once from starting from each of its n squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When n squares have been created, an n-omino has been created.

This method ensures that each fixed polyomino is counted exactly n times, once for each starting square.

I was hoping that by making a uniform random legal choice at each step, I could generate a large random polyomino, but unfortunately the description of the algorithm above seems to sometimes get stuck. See, for example, the figure below. We have consructed a polyomino with 16 tiles, but no further moves are possible.

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, polyominos may have holes.

(Update: these are sometimes also called two-dimensional lattice animals. For another model of random lattice animal, see this earlier MO question and discussion and references there.)

I would like to be able to sample a uniform random polyomino with $n$ squares, where $n$ is of the order $100$ or $1000$.

I am thinking of fixed polyominos, where two polyominos are considered equivalent only if they agree after a translation, but where rotations and reflections are in general distinct. But I might also be okay with sampling one-sided or fixed polyominos if that is for some reason easier or more natural.

The point is that I don't want to have to enumerate all the polyominos of this size. For $n=100$, enumerating all the polyominoes would already be far beyond the reach of modern computing. I am hoping that there is a random construction, or else a Markov chain that converges to the uniform distribution (i.e. every polyomino having equal probability). I would be interested in such a Markov chain, if it could be proved to converge to the uniform distribution, even without guarantees on the mixing time.

My first attempt at a random construction was to apply a randomized version of Redelmeier's method, or at least Wikipedia's description of this algorithm. But I am not sure if Wikipedia's description is correct. I copy it here, for the sake of completeness.

The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n-omino n times, once from starting from each of its n squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When n squares have been created, an n-omino has been created.

This method ensures that each fixed polyomino is counted exactly n times, once for each starting square.

I was hoping that by making a uniform random legal choice at each step, I could generate a large random polyomino, but unfortunately the description of the algorithm above seems to sometimes get stuck. See, for example, the figure below. We have consructed a polyomino with 16 tiles, but no further moves are possible.

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, polyominos may have holes.

(Update: these are sometimes also called two-dimensional lattice animals. For another model of random lattice animal, see this earlier MO question and discussion and references there.)

I would like to be able to sample a uniform random polyomino with $n$ squares, where $n$ is of the order $100$ or $1000$.

I am thinking of fixed polyominos, where two polyominos are considered equivalent only if they agree after a translation, but where rotations and reflections are in general distinct. But I might also be okay with sampling one-sided or fixed polyominos if that is for some reason easier or more natural.

The point is that I don't want to have to enumerate all the polyominos of this size. For $n=1000$ this is far beyond. I am hoping that there is a random construction, or else a Markov chain that converges to the uniform distribution (i.e. every polyomino having equal probability). I would be interested in such a Markov chain, if it could be proved to converge to the uniform distribution, even without guarantees on the mixing time.

My first attempt at a random construction was to apply a randomized version of Redelmeier's method, or at least Wikipedia's description of this algorithm. But I am not sure if Wikipedia's description is correct. I copy it here, for the sake of completeness.

The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n-omino n times, once from starting from each of its n squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When n squares have been created, an n-omino has been created.

This method ensures that each fixed polyomino is counted exactly n times, once for each starting square.

I was hoping that by making a uniform random legal choice at each step, I could generate a large random polyomino, but unfortunately the description of the algorithm above seems to sometimes get stuck. See, for example, the figure below. We have consructed a polyomino with 16 tiles, but no further moves are possible.

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, polyominos may have holes.

(Update: these are sometimes also called two-dimensional lattice animals. For another model of random lattice animal, see this earlier MO question and discussion and references there.)

I would like to be able to sample a uniform random polyomino with $n$ squares, where $n$ is of the order $100$ or $1000$.

I am thinking of fixed polyominos, where two polyominos are considered equivalent only if they agree after a translation, but where rotations and reflections are in general distinct. But I might also be okay with sampling one-sided or fixed polyominos if that is for some reason easier or more natural.

The point is that I don't want to have to enumerate all the polyominos of this size. For $n=100$, enumerating all the polyominoes would already be far beyond the reach of modern computing. I am hoping that there is a random construction, or else a Markov chain that converges to the uniform distribution (i.e. every polyomino having equal probability). I would be interested in such a Markov chain, if it could be proved to converge to the uniform distribution, even without guarantees on the mixing time.

My first attempt at a random construction was to apply a randomized version of Redelmeier's method, or at least Wikipedia's description of this algorithm. But I am not sure if Wikipedia's description is correct. I copy it here, for the sake of completeness.

The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n-omino n times, once from starting from each of its n squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When n squares have been created, an n-omino has been created.

This method ensures that each fixed polyomino is counted exactly n times, once for each starting square.

I was hoping that by making a uniform random legal choice at each step, I could generate a large random polyomino, but unfortunately the description of the algorithm above seems to sometimes get stuck. See, for example, the figure below. We have consructed a polyomino with 16 tiles, but no further moves are possible.

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, polyominos may have holes.

I would like to be able to sample a uniform random polyomino with $n$ squares, where $n$ is of the order $100$ or $1000$.

I am thinking of fixed polyominos, where two polyominos are considered equivalent only if they agree after a translation, but where rotations and reflections are in general distinct. But I might also be okay with sampling one-sided or fixed polyominos if that is for some reason easier or more natural.

The point is that I don't want to have to enumerate all the polyominos of this size. For $n=1000$ this is far beyond. I am hoping that there is a random construction, or else a Markov chain that converges to the uniform distribution (i.e. every polyomino having equal probability). I would be interested in such a Markov chain, if it could be proved to converge to the uniform distribution, even without guarantees on the mixing time.

My first attempt at a random construction was to apply a randomized version of Redelmeier's method, or at least Wikipedia's description of this algorithm. But I am not sure if Wikipedia's description is correct. I copy it here, for the sake of completeness.

The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n-omino n times, once from starting from each of its n squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When n squares have been created, an n-omino has been created.

This method ensures that each fixed polyomino is counted exactly n times, once for each starting square.

I was hoping that by making a uniform random legal choice at each step, I could generate a large random polyomino, but unfortunately the description of the algorithm above seems to sometimes get stuck. See, for example, the figure below. We have consructed a polyomino with 16 tiles, but no further moves are possible.

A polyomino is formed by joining finitely many unit squares edge to edge. It may be regarded as a finite subset of the regular square tiling with a connected interior. In particular, for us, polyominos may have holes.

(Update: these are sometimes also called two-dimensional lattice animals. For another model of random lattice animal, see this earlier MO question and discussion and references there.)

I would like to be able to sample a uniform random polyomino with $n$ squares, where $n$ is of the order $100$ or $1000$.

I am thinking of fixed polyominos, where two polyominos are considered equivalent only if they agree after a translation, but where rotations and reflections are in general distinct. But I might also be okay with sampling one-sided or fixed polyominos if that is for some reason easier or more natural.

The point is that I don't want to have to enumerate all the polyominos of this size. For $n=1000$ this is far beyond. I am hoping that there is a random construction, or else a Markov chain that converges to the uniform distribution (i.e. every polyomino having equal probability). I would be interested in such a Markov chain, if it could be proved to converge to the uniform distribution, even without guarantees on the mixing time.

My first attempt at a random construction was to apply a randomized version of Redelmeier's method, or at least Wikipedia's description of this algorithm. But I am not sure if Wikipedia's description is correct. I copy it here, for the sake of completeness.

The basic idea is that we begin with a single square, and from there, recursively add squares. Depending on the details, it may count each n-omino n times, once from starting from each of its n squares, or may be arranged to count each once only.

The simplest implementation involves adding one square at a time. Beginning with an initial square, number the adjacent squares, clockwise from the top, 1, 2, 3, and 4. Now pick a number between 1 and 4, and add a square at that location. Number the unnumbered adjacent squares, starting with 5. Then, pick a number larger than the previously picked number, and add that square. Continue picking a number larger than the number of the current square, adding that square, and then numbering the new adjacent squares. When n squares have been created, an n-omino has been created.

This method ensures that each fixed polyomino is counted exactly n times, once for each starting square.

I was hoping that by making a uniform random legal choice at each step, I could generate a large random polyomino, but unfortunately the description of the algorithm above seems to sometimes get stuck. See, for example, the figure below. We have consructed a polyomino with 16 tiles, but no further moves are possible.