4
$\begingroup$

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?

1 Answers 1

3

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}\left(\text{if } k = \frac{m^2}{4}\right)$$

Where $k'' = k-\frac{m(m-2)}{4}$ and $k''' = k - \frac{(m-2)^2}{4}.$

  • 0
    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...2012-08-30