4
$\begingroup$

The construction quoted in the question "How to sample a uniform random polyomino?" claims to produce a "uniform random polyomino". But apart from the mentioned possibility of getting stuck, it also seems to me that the polyominoes obtained by this construction tend to contain less $2\times2$ squares than average. This is because if three cells of such a square are already selected during the construction, there seem to be fairly high chances that the fourth cell already has a number smaller than the last picked one (and thus can never be picked). E.g. after having chosen 1 and 3 in the given example, the only chance to obtain a $2\times2$ square here is to pick 4 and then 8. And there are only quite few other $2\times2$ squares at all which might be obtained similarly at some stage of this (admittedly very particular) construction.

My impression may be wrong, but in any case, without clinging to the quoted construction, it makes me wondering about the following:

  • For a uniformly sampled $n$-polyomino, what is in fact the expected number of $2\times2$ squares it contains? Or at least, what about its asymptotics as $n$ grows?
  • Is the distribution of the number of $2\times2$ squares essentially similar if we restrict it all to $n$-polyominoes without holes? Or do the latter contain significantly more $2\times2$ squares?

Note that whether or not rotations and reflections are considered as different should not make a notable difference for this distribution.

$\endgroup$
  • $\begingroup$ I think the only problem with the quoted construction is that the algorithm sometimes gets stuck. But as someone else pointed out, this does not mean that it is not sampling correctly––you just have to start over whenever you get stuck. All one needs to check is that every $n$-omino gets counted exactly $n$ times, which seems straightforward unless I am missing something. Still, this does not answer your questions about the expected number of $2 \times 2$ squares as $ n \to \infty$. $\endgroup$ – Matthew Kahle Jul 18 '16 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.