# Grid-constrained probability question

A little rusty on my combinatorics/probability, and looking for some pointers on figuring out some probabilities in a game setup.

Given a 2-dimensional grid that is divided into 2x2 tiles, with each tile having a specific feature in exactly one of it's four squares, I'm trying to figure out the probability of an overlaid square tile (2x2 minimum, but the interesting cases are larger) having a certain number of feature squares within it. I can brute-force the small cases, but the non-uniform distribution of features (i.e. conditional probabilities based on neighboring squares and grid constraints) as well as the different possible alignments quickly make larger cases a counting nightmare.

By way of a little better example, a 2x2 overlay, if aligned to the underlying grid, obviously will have just one feature square. If it's misaligned either horizontally or vertically, it can have 0, 1, or 2 squares, and if it's misaligned in both directions, it could have anywhere between 0 and 4 squares. The probabilities (calculated by just counting the possible combinations) come out to about 20.4% chance of 0 tiles, 60.6% chance of 1, 17.8% for 2, 1.8% for 3, and about 0.1% for all 4.

A 3x3 overlay, calculated similarly, has a minimum of 1 square (18.75%), but can have 2, 3, or 4 (maximum) with respective probabilities of 43.75%, 31.25% and 6.25%.

Is this a well defined problem that has a (preferably closed-form) formula as a solution? Or is tabulating the possibilities the best that can be done for the higher-order parameters?

-

There are closed forms (though you need to split into cases based on the parity of the side length.)

Let's say you want to calculate the probability there are $k$ features in a $m\times m$ square.

Case 1: $m$ is odd. Then there will be exactly $\frac{(m-1)^2}{4}$ full tiles in it, exactly $m-1$ half-tiles, and exactly $1$ quarter-tile. This is true no matter how the $m\times m$ square is arranged.

No matter what there will be at least $\frac{(m-1)^2}{4}$ features in it, and at most $\frac{(m-1)^2}{4}+m.$ Let $k = \frac{(m-1)^2}{4} + k'.$ If $k'$ is not in $[0,m]$ the probability will be 0. So for the rest of the discussion, we will assume $k'$ is in this range.

There are two ways we could get $k'$ features from the half-tiles and quarter-tile: We could get $k'$ features from the half-tiles and 0 from the quarter-tile, or we could get $k'-1$ features from the half-tiles and $1$ feature from the quarter-tile.

In the first case, each half tile has a one-half probability of having a feature, and the quarter-tile will have a three-forth probability of not having a feature. The number of ways to get $k'$ features is $m-1\choose k',$ so the probability of this case is $\frac{3{m-1\choose k'}}{4\cdot 2^{m-1}}.$ Similarly, the probability of the second case is $\frac{m-1\choose k'-1}{4\cdot 2^{m-1}},$ so adding, when $m$ is odd, the probability will be $$\frac{3{m-1\choose k'} + {m-1\choose k'-1}}{4\cdot 2^{m-1}} = \frac{3{m-1\choose k'} + {m-1\choose k'-1}}{2^{m+1}}$$ where $k' = k-\frac{(m-1)^2}{4}. Case 2:$m$is even. Sadly, in this case, the arrangements of tiles do matter. One possible arrangement is so that the$m\times m$square contains$\frac{m^2}{4}$full tiles. This is a nice case; here, the number of features will always be$\frac{m^2}{4}.$Another possible arrangement is where there are$\frac{m(m-2)}{4}$full tiles and$m$half tiles. Here, let$k'' = k-\frac{m(m-2)}{4}.$We need$k''$of the half-tiles to have a feature, so the probability here is$\frac{m \choose k''}{2^m}.$The final possible arrangement is where there are$\frac{(m-2)^2}{4}$full tiles,$2(m-2)$half-tiles, and$4$quarter-tiles. The$4$quarter-tiles have probabilities$\frac{81}{256}, \frac{108}{256}, \frac{54}{256}, \frac{12}{256}, \frac{1}{256}$of giving$0,1,2,3,4$features respectively. Let$k''' = k - \frac{(m-2)^2}{4}.$Then, similarly to case 1, the answer will be $$\frac{81{2m-4\choose k'''}+108{2m-4\choose k'''-1}+54{2m-4\choose k'''-2}+12{2m-4\choose k'''-3}+{2m-4\choose k'''-4}}{2^{2m+4}}$$ To calculate the final answer to this case, we need to average these (but we need a weighted average, since the second subcase is twice as likely as the first and third.) The probability of having exactly k features is: $$\frac{81{2m-4\choose k'''}+108{2m-4\choose k'''-1}+54{2m-4\choose k'''-2}+12{2m-4\choose k'''-3}+{2m-4\choose k'''-4}+2^{m+5}{m \choose k''}}{2^{2m+6}}+\frac{1}{4}(\text{if } k = \frac{m^2}{4})$$ Where$k'' = k-\frac{m(m-2)}{4}$and$k''' = k - \frac{(m-2)^2}{4}.\$

-
It's very possible that I made some mistakes in the computation, so tell me if anything seems wrong. – only Aug 30 '12 at 4:03
Thanks for the detailed analysis - wasn't expecting quite that extensive an answer. That's essentially the method I was following for the small cases (m = 2,3,4) and was hoping maybe there was something simpler that I was missing that I could just plug into a spreadsheet. Not horribly surprised there isn't one simple answer, but thought it worth asking, anyway. I don't see any obvious mistakes, but I'll probably be transforming this into a program soon, that should help uncover any... – twalberg Aug 30 '12 at 14:53