Expected Value Of a Random Grid That Contains Multipliers

Question

I am a software developer and recently came across this problem when working on a hobby project, and my knowledge of probability is too small to solve this.

I have a bag that contains 5 negative ones, 5 zeros, 10 ones, 5 twos, 5 threes. The tiles are set randomly on a 5 by 5 grid with 5 tiles left in the bag. The threes in the bag also multiply all 8 of the adjacent squares by 2 (A number is multiplied by $2^n$ adjacent 3's). What is the best way to calculate the expected value of the grid for any known bag that can contain a random amount of any numbers? Bonus points if it can handle any size (and rectangular shape) of grid.

Eg. Bag ( 2 1 3 3 3 ), Grid Value: 27

$$\begin{array}{c|c|c|c|c} 3&2&1&-1&1\\ \hline 1&1&0&0&-1\\ \hline 1&0&3&2&2\\ \hline -1&0&-1&2&1\\ \hline 1&-1&1&1&0 \end{array}$$

Without the multiplier, the solution is quite simple:

The number of values in the grid (25) × The sum of all of the numbers in the bag / the number of numbers in the bag. Or $(n * s) / a$

Since they do not interact, the fact they are in a grid does not even matter. For the same reason, it's not that useful for solving this problem, but I thought I would mention it as a start.

A kinda related question of mine

Answer 1

The simplest approach--in the sense of requiring the least mathematics--is via simulation. You would program random permutations and compute the value of the grid for each one; with sufficiently large samples, the expectation would be reasonably close to the exact value, and you can also get an estimate of the standard deviation of the value.

My code in Mathematica:

b = Sort[Flatten[Join[Table[Range[4] - 1, 5], Table[1, 10]]]];
t[m_] := Take[m, {Max[1, #[[1]] - 1], Min[5, #[[1]] + 1]}, {Max[1, #[[2]] - 1], 
         Min[5, #[[2]] + 1]}] & /@ Position[m, 3]
s[m_] := Total[Flatten[t[m]]] + Total[Flatten[m]] - 3 Count[Flatten[m], 3]
d = ParallelTable[s[Partition[RandomSample[b, 25], 5]], 10^6];
{Mean[d], Variance[d]}

This produces $10^6$ simulations and computes the overall mean and variance. Note the following:

• My algorithm shows that the correct score for the grid in your question is $38$, not $39$.
• My instance of running this code produced a mean of $63.9687$.

An exact calculation would be problematic, since the number of such grids is quite large, even after accounting for symmetries and repeated elements.

The conditional means and variances for each base total ranging from $25$ to $40$ are approximately:

$$\begin{array}{c|cc} \text{base} & \text{mean} & \text{variance} \\ \hline 25 & 25. & 0. \\ 26 & 31.4203 & 4.60442 \\ 27 & 36.0449 & 18.0836 \\ 28 & 40.4705 & 19.7906 \\ 29 & 44.906 & 31.9896 \\ 30 & 49.4376 & 36.9694 \\ 31 & 53.8249 & 47.2579 \\ 32 & 58.3649 & 55.2471 \\ 33 & 62.7921 & 61.3061 \\ 34 & 67.0464 & 69.8355 \\ 35 & 71.4379 & 73.5359 \\ 36 & 75.1243 & 69.9286 \\ 37 & 77.7472 & 68.0978 \\ 38 & 79.9451 & 67.8064 \\ 39 & 82.2345 & 66.5388 \\ 40 & 85.338 & 70.5698 \\ \end{array}$$ This is based on $10^7$ simulations.

Answer 2

Edit: this does NOT solve the problem stated. I implicitly assume that if a value is next to $n$ threes, it is multiplied by $n + 1$. However, OP clarified in the comments that the value is multiplied by $2^n$ if it is next to $n$ threes. I'm not sure how to fix this.

This is actually a rather simple problem (or rather, the complexity is deceptive). The problem boils down to calculating the expected value of the sum of elements adjacent to each three.

By linearity of expectation, it suffices to calculate the expected sum of elements adjacent to a given 3, then multiply by the number of 3s.

Now the expected sum of the neighbors of a given 3 is equal to the expected number of neighbors, times the expected value of each given neighbor. This is because no matter how many neighbors a 3 has, the expected value of a given neighbor is constant.

Let's take the case of an $m \times m$ grid with $n$ copies of 3 and a total number of bag elements $M \geq m \geq 2$. Then the expected value of a neighbor of 3 will be $\frac{S - 3}{M - 1}$, where $S$ is the sum of all elements in the bag.

Now for calculating the expected number of neighbors of a given 3. To do this, note that there is a $\frac{4}{M}$ chance of the 3 being in a corner, a $\frac{4(m - 2)}{M}$ chance of $m$ being on an edge, and a $\frac{(m - 2)^2}{M}$ chance of the 3 being in the middle. If the 3 is in a corner, it has only 3 neighbours. On an edge, the 3 will have 5 neighbours. There is also a chance the 3 won't make it onto the board of $\frac{M - m^2}{M}$, in which case the 3 will have zero neighbors. This gives us an expected value of $3 \frac{4}{M} + 5 \frac{4(m - 2)}{M} + 8 \frac{(m - 2)^2}{M}$.

So the expected sum of the neighbours of all threes will be $n \cdot \frac{S - 3}{M} \cdot (3 \frac{4}{M} + 5 \frac{4(m - 2)}{M} + 8 \frac{(m - 2)^2}{M})$.

To answer the original problem, we must add the expected sum of the (unadjusted by 3-doubling) grid back in, which is $\frac{S m^2}{M}$.

So the final answer is

$$ \frac{S m^2}{M} + n \cdot \frac{S - 3}{M} \cdot (3 \frac{4}{M} + 5 \frac{4(m - 2)}{M} + 8 \frac{(m - 2)^2}{M}) $$