Hello and thanks in advance.
I'm trying to solve a problem I'm having with a pattern matching game.
The game's board consists of a 5x5 grid of numbers where column 1 (on the far left) contains 5 random numbers from a pool of numbers in the range 1-15, column 2 contains 5 random numbers in the range 16-30 etc. up to column 5 (on the far right) containing 5 random numbers from 61-75. We end up with a game board such as the following:
[5] [26] [43] [54] [75]
[13] [23] [39] [46] [72]
[12] [21] [33] [59] [71]
[10] [29] [34] [60] [67]
[8] [18] [40] [55] [65]
which is very similar to a traditional 75 ball bingo card but has a number in the centre square (usually replaced with a star in bingo but not relevant to this game).
The patterns to be matched are identical to the prize lines in 75 ball bingo. There are 12 possible patterns (prize lines) to match 5 horizontal lines (e.g. 5->26->43->54->75), 5 vertical lines (e.g. 43->39->33->34->40) and 2 diagonal lines (e.g. 5->23->33->60->65).
The game proceeds by the player having a number of turns, the specific count of turns being irrelevant to this question. Each turn consists of a draw of one number for each column (5 numbers drawn per turn) from number pools each dedicated to a specific column. The goal of the game is to complete as many of the patterns/prize lines as possible, with a higher count of completed patterns yielding a higher score.
What I'm trying to calculate is the expected increase in the prize line count from a single turn. I'd like to obtain a formula or series of steps for calculating this expectation from any given board state. For example, the player might be half way through their game and may have daubed (checked off) a random selection of half of their numbers on the board.
I asked a similar question elsewhere and some very smart members of the maths community (one in particular - thanks Timothy!) suggested that this question was better asked here but also showed that by iterating over the incomplete lines and calculating the probability of that line being completed on the next spin, I could then sum those probabilities to calculate the expected increase in the count of complete lines.
This worked perfectly for me where the pools of numbers contained only the numbers in the column's range. I could even unbalance their distribution within the column's pool and still get correct expectation values. However, if I introduce a wildcard symbol that will match any number in the column, the probabilities using the above method no longer sum to the expected test value.
Here are some examples of the solution first of all working with balanced number pools and then unbalanced number pools and then not working with a wildcard introduced.
Firstly, I'm scaling down the board size to make brute forcing the probabilities much simpler for an example and using the following board with only 4 squares:
[1] [3]
[x] [4]
The number pools are also simplified to contain only the numbers on the board.
Column 1 number pool: 1,2
Column 2 number pool: 3,4
So every turn either 1 or 2 will be drawn from column 1's number pool and either 3 or 4 will be drawn from column 2's number pool.
For the purposes of the example, we have pre-daubed the bottom left square (which previously held the number 2). Now there are no complete prize lines and 6 remaining incomplete prize lines (2 horizontal, 2 vertical, 2 diagonal). We calculate the probability in this simple example ahead of time by brute forcing every possible draw outcome, of which there are only 4, and manually counting the additional prize lines that will be completed as a result of each one:
1,3 = 3 additional prize lines completed
1,4 = 3 additional prize lines completed
2,3 = 1 additional prize line completed
2,4 = 1 additional prize line completed
On average therefore (8 prize lines / 4 possible draw combinations), we know ahead of time that the expected increase in the number of completed prize lines is 2.0 from a single turn. Now we apply our proposed solution to the same board state by calculating the probability of completing each incomplete prize line as follows:
Line 1->3 = ½ * ½ = 0.5 * 0.5 = 0.25
Line 2->4 = ½ = 0.5
Line 1->2 = ½ = 0.5
Line 3->4 = 0
Line 1->4 = ½ * ½ = 0.5 * 0.5 = 0.25
Line 2->3 = ½ = 0.5
The sum of these probabilities is equal to our ahead of time calculation (2.0) despite the fact that multiple combinations of these prize lines are mutually exclusive. This first example is a successful example of summing probabilities using the solution proposed above.
The second example is with an unbalanced number pool for one of the columns.
This time we increase the complexity by expanding the board and number pools as below. Now there are 9 numbers on the board and 8 prize lines. There are now 36 possible number draw combinations (3x3x4).
[1] [4] [7]
[2] [5] [8]
[3] [6] [9]
Number pools:
1 4 7
2 5 8
3 6 9
9
To start with, we’ve pre-daubed the middle vertical prize line as follows, leaving 7 incomplete prize lines.
[1] [x] [7]
[2] [x] [8]
[3] [x] [9]
We have to brute force all possible number pool draw combinations in order to list the increase in completed prize lines for each and calculate the expected overall increase. Below are those possible combinations and the additional complete prize lines they yield. Note there are 2 9s in column 3’s number pool so we have apparently repeated combinations including the second 9. In brackets are the additional number of completed prize lines resulting from each combination.
147(1),148(0),149(1),149(1),157(1),158(0),159(1),159(1),167(1),168(0),169(1),169(1)
247(0),248(1),249(0),249(0),257(0),258(1),259(0),259(0),267(0),268(1),269(0),269(0)
347(1),348(0),349(1),349(1),357(1),358(0),359(1),359(1),367(1),368(0),369(1),369(1)
21 additional prize lines / 36 draw combinations = expected increase in prize line count of 0.58333 (rounded to 5 dp)
If we now apply our proposed solution to each incomplete prize line (7 total) as we’ve done previously, the results are as follows:
Line 1->4->7 = ⅓ * ¼ = 0.33333 * 0.25 = 0.08332
Line 2->5->8 = ⅓ * ¼ = 0.33333 * 0.25 = 0.08332
Line 3->6->9 = ⅓ * ½ = 0.33333 * 0.5 = 0.16667
Line 1->2->3 = 0 (not possible to complete this line in a single draw)
Line 7->8->9 = 0 (not possible to complete this line in a single draw)
Line 1->5->9 = ⅓ * ½ = 0.33333 * 0.5 = 0.16667
Line 3->5->7 = ⅓ * ¼ = 0.33333 * 0.25 = 0.08332
Summation of the above probabilities = 0.5833 which ~= 0.58333 from our brute force example (more precision in these numbers will make them very close).
So far so good. Finally though, I add a wildcard '*' to the number pool for the 3rd column as follows:
[1] [4] [7]
[2] [5] [8]
[3] [6] [9]
Number pools:
1 4 7
2 5 8
3 6 9
*
The * symbol will match any number in that column. This time the brute forced combinations are as follows:
147(1),148(0),149(1),14*(1),157(1),158(0),159(1),15*(1),167(1),168(0),169(1),16*(1)
247(0),248(1),249(0),24*(1),257(0),258(1),259(0),25*(1),267(0),268(1),269(0),26*(1)
347(1),348(0),349(1),34*(1),357(1),358(0),359(1),35*(1),367(1),368(0),369(1),36*(1)
Predictably, this yields more complete prize lines. 24 / 36 = 0.66667 (rounded up to 5dp). However, if we now apply our solution, we see the following:
Line 1->4->7 = ⅓ * ½ = 0.33333 * 0.5 = 0.16667
Line 2->5->8 = ⅓ * ½ = 0.33333 * 0.5 = 0.16667
Line 3->6->9 = ⅓ * ½ = 0.33333 * 0.5 = 0.16667
Line 1->2->3 = 0 (not possible to complete this line in a single draw)
Line 7->8->9 = 0 (not possible to complete this line in a single draw)
Line 1->5->9 = ⅓ * ½ = 0.33333 * 0.5 = 0.16667
Line 3->5->7 = ⅓ * ½ = 0.33333 * 0.5 = 0.16667
The sum of these probabilities is 0.83335, which is wildly different from our predicted 0.66667.
Please could you help me understand why the wildcard is so different from additional, repeated numbers? I know it will match any of the numbers of course but why do the two calculations diverge?
If anyone can see an alternative or preferable method of calculating this expectancy without brute forcing on board states, I'm all ears!
Thank you for reading and thanks in advance for any input.
The reason is that in your first approach, you’re counting e.g. $14*$ as completing $1$ line, whereas in the second approach you count it once for each line it allows you to complete. The second approach overcounts because you can in fact only use the wildcard to complete one line, not two.
To make the two approaches agree, decide on a strategy: For every draw combination, specify what you intend to do with the wildcard if that combination is drawn, and then in the second approach only count it towards the lines that would be completed using that strategy. (You’re already doing that for the first approach, where the $1$s implicitly acknowledge that an optimal strategy would complete $1$ line using the wildcard.)
By the way, a technical term under which you can find more about why the two approaches agree is linearity of expectation.