Computing product/sum of scores on a matrix game

Question

I am thinking of a matrix game, and I have some questions about it. I do not know which topic will this fit into, so any ideas/direcitons in this direction are welcome.

Let me explain the matrix game. Consider the following grid. \begin{equation} \begin{array}{||c|c|c|c||} \hline\hline a_{11}&a_{12}&\cdots&a_{1n}\\ \hline a_{21}&a_{22}&\cdots&a_{2n}\\ \hline \vdots&\vdots&\ddots&\vdots\\ \hline a_{m1}&a_{m2}&\cdots&a_{mn}\\ \hline\hline \end{array}\nonumber \end{equation} Here, $a_{ij}$'s are real numbers. I will walk from the top-left cell to the right-bottom cell by moving either left or below. Clearly, there are $\binom{(m-1)+(n-1)}{(m-1)}$ possible ways. At the end of the walk, my score is the product of the $a_{ij}$'s that I have stepped on.

1. What is the product of scores over all possible ways?
2. What is the sum of scores over all possible ways?

Answer 1

We run into this situation in computer science a lot. It's called dynamic programming. A few things to note:

1.) if the values of $a_{i,j}$ are basically random or arbitrary numbers, then I happen to know that the best you can do about calculating the product of scores over all possible paths is to simply say that the product of scores over all possible paths is:

$$ \prod_{k}^{M} (\prod_{i,j}^N a_{i,j})_k$$

where $k$ is an indexes over path number. I'm sure someone else can calculate the total number of possible paths. I'm almost certain that you'll have a computer work through all possible paths to determine each product. A similar formula can be derived if you want the sum of all scores over all possible paths. Simply put, this is a computer calculation problem - I'm pretty sure there is no way to create a formula that generalizes the outcome (other than the self-defining formula I wrote above).

2.) If you have some function that will return the value of $a_{i,j}$ then just stick it in the formula above.

Lastly, a couple of ways you might improve your game:

a.) Have someone try to calculate the maximum possible score, or the minimum possible score, or some path to get a predetermined score etc.

b.) have a probability distribution for determining if the next square is to the right or down, and try to create games based on that.

Answer 2

The expression for the sum doesn't look nice for small $m,n$, so there's probably no clean formula. For the product, however, we can simplify things a bit.

Let's renumber the grid as $a_{00}$ through $a_{mn}$, just so that there are $\binom{m+n}{m}$ possible paths instead and all our formulas are a bit nicer (fewer $-1$'s).

For the product of scores over all possible paths, it's enough to figure out how many paths contain $a_{ij}$. There are $\binom{i+j}{i}$ ways to get from $a_{00}$ to $a_{ij}$, nd then $\binom{m+n-i-j}{m-i}$ ways to get from $a_{ij}$ to $a_{mn}$. Since every path into $a_{ij}$ can be paired with every path out of $a_{ij}$, there are $\binom{i+j}{i} \binom{m+n-i-j}{m-i}$ paths through $a_{ij}$ altogether. Therefore the product is $$ \prod_{i=0}^m \prod_{j=0}^n a_{ij}^{\binom{i+j}{i} \binom{m+n-i-j}{m-i}}. $$