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.
