[math-fun] Random polyominoes
Suppose we tile the plane randomly with black and white unit square tiles in a grid pattern, black and white tiles occuring with equal probablity (sort of like the static you used to see on your old black and white TV). Consider the polyominoes formed by connecting like-colored tiles along their edges. Since every possible coloring of an nxn subsquare should occur, I'm thinking that every finite polyomino should occur in every orientation. What is the probability that a randomly chosen square is in a unomino (I find only one page on the web with that word!)? What is the probability that a randomly chosen polyomino is a unomino? What is the most frequent polyomino in both senses? I am thinking that if black squares occur with probability 1/2, the probability of an infinite polyomino is 0. Certainly if they occur with probability 1, the probability of an infinite polyomino is 1. What about choosing black squares with probability 3/4? Other probabilities? - David W. Wilson "Truth is just truth -- You can't have opinions about the truth." - Peter Schickele, from P.D.Q. Bach's oratorio "The Seasonings"
David Wilson wrote:
Suppose we tile the plane randomly with black and white unit square tiles in a grid pattern, black and white tiles occuring with equal probablity (sort of like the static you used to see on your old black and white TV).
This general setup is what's called a "percolation model" in the biz (where the biz in question is statistical mechanics). Well, not quite: they usually think of one of the two colors as "open" and the other as "closed", and only ask questions about the connectivity of open sites. Rearranging your mail a bit:
I am thinking that if black squares occur with probability 1/2, the probability of an infinite polyomino is 0. Certainly if they occur with probability 1, the probability of an infinite polyomino is 1. What about choosing black squares with probability 3/4? Other probabilities?
The standard big results here are: (1) there is a critical probability, usually denoted p_c, such that if you declare squares open with probability p < p_c, the probability of an infinite open component is zero, while with p > p_c it is 1. In dimension two, it's even known that p <= p_c is the probability zero condition; what happens at p_c exactly is known for some other lattices, but I don't know the full story.
What is the probability that a randomly chosen square is in a unomino (I find only one page on the web with that word!)? What is the probability that a randomly chosen polyomino is a unomino? What is the most frequent polyomino in both senses?
(I think people use "monomino.") That's just the probability that you're surrounded by squares whose color is not your own, so (1/2)^4 = 1/16, right? Likewise for a domino, there are four neighbors you could domin with (now *there's* a non-sactioned noun-to-verb conversion), and six border squares that would have to be of the opposite color. So the odds that a random square is in a domino is 4 * (1/2)^7 = 1/32. And picking random squares makes dominos twice as findable as monominos, so both come up one sixteeth of the time if you pick a random square and look at its connected component. Right? Unless I'm missing something, it would be easy to do this calculation for any specific polyomino. Eg, for an L-triomino, there are (I think) 12 ways for a square to lie in an L-triomino, and it needs the cooperation of two same-color and seven opposite-color squares, so 12*(1/2)^9 = 3/128 of all squares are in L's, and 9/128 of the time a random square's polyomino is an L. (That's bigger than 1/16, so it's the new record-holder.) I have to go do real work, so I'll let someone else (write the computer program to) expand this table (and tell me if I'm doing something dumb)... --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Oof: I wrote all of
The standard big results here are: (1) there is a critical probability, usually denoted p_c, such that if you declare squares open with probability p < p_c, the probability of an infinite open component is zero, while with p > p_c it is 1. In dimension two, it's even known that p <= p_c is the probability zero condition; what happens at p_c exactly is known for some other lattices, but I don't know the full story.
... but I neglected to mention that Robert Ziff's 1992 paper "Spanning probability in 2D percolation" (Phys. Rev. Lett. 69, 2670–2673 (1992)) calculated that p_c for the 2d square lattice is 0.5927460 ± 0.0000005 --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Double oof: Rich kindly tells me that a message I sent earlier today came through encoded, so some people couldn't read it. I meant to write the following...
Oof: I wrote all of
The standard big results here are: (1) there is a critical probability, usually denoted p_c, such that if you declare squares open with probability p < p_c, the probability of an infinite open component is zero, while with p > p_c it is 1. In dimension two, it's even known that p <= p_c is the probability zero condition; what happens at p_c exactly is known for some other lattices, but I don't know the full story.
... but I neglected to mention that Robert Ziff's 1992 paper "Spanning probability in 2D percolation" (Phys. Rev. Lett. 69, 2670–2673 (1992)) calculated that p_c for the 2d square lattice is 0.5927460 +/- 0.0000005
Sorry to everyone: those of you who saw garbage the first time, and those of you who now had to read it twice... --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
Ugh -- so I've sent mysteriously coded messages twice in one day. No more cut-and-paste for me. And if that wasn't enough, I earlier wrote:
That's just the probability that you're surrounded by squares whose color is not your own, so (1/2)^4 = 1/16, right?
Likewise for a domino, there are four neighbors you could domin with (now *there's* a non-sactioned noun-to-verb conversion), and six border squares that would have to be of the opposite color. So the odds that a random square is in a domino is 4 * (1/2)^7 = 1/32. And picking random squares makes dominos twice as findable as monominos, so both come up one sixteeth of the time if you pick a random square and look at its connected component. Right?
Wrong on the factor of two at the end. The probability that a random square is in a domino is indeed 1/32, so half the probability of a monomino. But if you pick random polyominos, instead of random squares therefrom, the domino becomes harder to pick, not easier -- you'll get a monomino four times as often as a domino in that case. J.D. Williams's _Compleat Strategyst_ introduced the notion of an "oddment" -- the number 4 in the statement "the ratio of monominos to dominos is 4:1", a numerator of a probability in which you do not yet know the denominator. For picking a random polyomino, we can easily get the oddments of any particular shape, but I don't see how to get the denominator (hence the probability) without doing all infinitely many of them. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
participants (2)
-
David Wilson -
Michael Kleber