What is the expected value of this process?

Question

There are $n$ piles each containing $a_i$ stones. In a sequence of moves, Alex chooses two neighbouring piles randomly (containing, say, $A$ and $B$ stones) and combines them to create a single pile with $A + B$ stones at the same place. Such a move also yields him $A + B$ points. He does this repeatedly until there is one pile. Alex's score is the sum of all points after all $ n-1$ moves. What is the expected value of Alex's score?

I am stuck at this. I found there are $(n-1)!$ possible move sequences, but I couldn't find how many points we get in all possible ways.

Answer 1

This is difficult -- parts of the solution are related to obscure combinatorial properties of the Symmetric groups -- and I don't think there's a simple closed-form solution. But we can still make substantial progress.

Step 1: Simplification

The key is that the total point value is a linear function of the $a_i.$

That is, let there be a sequence of pile "values" (which can be any numbers whatsoever, not just counts) $A = (a_1, a_2, \ldots, a_n).$ The choices in the procedure are a sequence of random integers $\Sigma = (\sigma_1, \sigma_2, \ldots, \sigma_{n-1})$ where for each index $i$ $\sigma_i$ is chosen uniformly and independently from the numbers $1,2,\ldots, n-i$ to indicate that the values at positions $\sigma_i$ and $\sigma_i + 1$ will be combined (and earned). Let

$$f(A;\Sigma)$$

be the total points earned. Given any two sequences $A$ and $B$ of length $n,$ it is straightforward to check that

$$f(A+B;\Sigma) = f(A;\Sigma) + f(B;\Sigma).$$

The problem asks for a formula for the expectation $E[f(A;\Sigma)]$ in terms of $A.$ By linearity of expectation, it will suffice to find a formula for any set of vectors that generate all such $A.$ A convenient set is the basis $(e_j)_{j=1,2,\ldots, n}$ where

$$e_j = (0,0,\ldots,0,1,0,0,\ldots,0)$$

has a $1$ in location $j$ and zeros everwhere else. Clearly

$$A = a_1 e_1 + a_2 e_2 + \cdots + a_n e_n$$

and therefore

$$E[f(A;\Sigma)] = a_1 E[f(e_1;\Sigma)] + a_2 E[f(e_2;\Sigma)] + \cdots + a_n E[f(e_n;\Sigma)].\tag{*}$$

Step 2: Recursive solution

In this solution we will play the game one step at a time and need to keep track of $n.$ To this end, let $e_{j;n}$ be the basis element with $n$ components and a $1$ in position $j,$ where $1 \le j \le n.$ Similarly let $\Sigma_n$ refer to the random variable corresponding to $n-1$ steps in the game.

There are two cases to consider.

1. Starting with $e_{1;n},$ there is a $1/(n-1)$ chance that the first two places will be chosen and combined. This yields $1+0=1$ point for Alex and changes the piles to the configuration $e_{1;n-1}.$ Therefore $$E[f(e_{1;n};\Sigma_n)] = \frac{1}{n-1} + E[f(e_{1;n-1};\Sigma_{n-1})].$$ By symmetry (reversing the sequence of pile values) a similar relation holds for $e_{n;n}.$

2. Otherwise, starting with $A= e_{j;n}$ where $1\lt j \lt n,$

   • There is a $2/(n-1)$ chance position $j$ will be combined with one of its neighbors $j\pm 1$ to give Alex one point.

   • There is a $(j-1)/(n-1)$ chance any combination will involve positions preceding $j$ and a $(n-j)/(n-1)$ chance positions following $j$ will be combined. This gives two possible new configurations $e_{j-1;n-1}$ and $e_{j;n-1}.$

Thus, $$E[f(e_{j;n};\Sigma_n)] = \frac{1}{n-1}\left(2 + (j-1)E[f(e_{j-1;n-1};\Sigma_{n-1})] + (n-j+1)E[f(e_{j;n-1};\Sigma_{n-1})]\right).$$

This yields an infinite triangular matrix of expectations. The rows are indexed by $n=1,2,3,\ldots$ and the columns by $j.$ Here is the array $((n-1)!E[f(e_{j;n};\Sigma(n)])$ for $n=1, 2, \ldots, 8,$ where the expectations are multiplied by $(n-1)!$ to give integer values:

$$\begin{array}{r|llllllllll} \text{n} & & & & & & & & & &\\ 1&0& & & & & & & & & \\ 2&1&1& & & & & & & & \\ 3&3&4&3& & & & & & & \\ 4&11&15&15&11& & & & & & \\ 5&50&68&72&68&50& & & & & \\ 6&274&370&400&400&370&274& & & & \\ 7&1764&2364&2580&2640&2580&2364&1764& & & \\ 8&13068&17388&19068&19740&19740&19068&17388&13068& & \\ \vdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\ddots& \end{array}$$

The rows of this matrix (each divided by $(n-1)!$) give the coefficients of the $a_j$ to use in the formula $(*).$

Step 3: Verification

Here are the results of playing this game with $n=20$ piles for each of the starting positions $j=1,2,\ldots, 20,$ 5000 times each. The dotted line plots the recursive solution for reference. The deviations between the simulated results and the recursive solution can be attributed to random variation.

Having some confidence the recursive solution is correct, we may study it for larger $n,$ as in this plot for $n=10,000:$

The values at the endpoints $j=1,n$ grow exponentially (in $n$) close to $\log(n) + \gamma$ (Euler's $\gamma \approx 0.5772157$). The curve peaks in the middle near $2\log n$ and is (obviously) symmetric under $j \to n+1-j$ (corresponding to reversing the order of the piles).

The code to compute these solutions using the recursion is efficient, requiring $O(N^2)$ calculations to obtain all solutions for $n=1,2,\ldots, N.$ This version takes one second for $n=10,000$ (but to save space, outputs only the solution for $N$ itself in the array X).

N <- 1e4
X <- c(0, rep(NA, N-1))
for (n in 2:N) {
  j <- seq_len(n-1)[-1]
  X[c(1,j,n)] <- c(1+(n-1)*X[1], 2+(j-1)*X[j-1] + (n-j)*X[j], 1+(n-1)*X[n-1]) / (n-1)
}

Incidentally, the first column of the solutions, $1,3,11,50,274,\ldots,$ counts many things, such as the total number of cycles in all permutations of $n$ things. The second column is also a known sequence, but subsequent columns do not appear to have been noticed.

Answer 2

For a closed-form solution, notice that the number of times $a_i$ is summed in all $\Gamma(n)$ possible move sequences is

$(H_{i-1}+H_{n-i})\Gamma(n)$

where $H_i$ is the $i^{\text{th}}$ harmonic number, with $H_0\equiv0$.

So Alex's expected score is

$\sum_i{a_i(H_{i-1}+H_{n-i})}$

This result matches the matrix provided by @whuber (with R):

f <- function(n) {
  h <- c(0, cumsum(1/seq_len(n - 1L)))
  (h + rev(h))*gamma(n)
}
m <- matrix(0, 8, 8)
m[upper.tri(m, TRUE)] <- unlist(lapply(1:8, f))
t(m)
#>       [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]
#> [1,]     0     0     0     0     0     0     0     0
#> [2,]     1     1     0     0     0     0     0     0
#> [3,]     3     4     3     0     0     0     0     0
#> [4,]    11    15    15    11     0     0     0     0
#> [5,]    50    68    72    68    50     0     0     0
#> [6,]   274   370   400   400   370   274     0     0
#> [7,]  1764  2364  2580  2640  2580  2364  1764     0
#> [8,] 13068 17388 19068 19740 19740 19068 17388 13068