Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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}.$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.