Expectation of the maximum consecutive subsequence sum of a random sequence

Question

Here is a problem from Programming Pearls 2nd edition (Chapter 8.7):

Considering a real number sequence, whose elements are drawn uniformly from the range [-1, 1], what is the expected maximum consecutive subsequence sum? (If all the elements are negative, the maximum sum is 0.)

Assuming the length of the sequence is N, is there a closed form for the expected maximum subsequence sum f(N)? I try to do some simulation, but failed to find any clue.

Thanks for help.

Answer 1

this is similar to Brownian motion in 1D, but with an unusual distribution for step sizes. for large N it approximates a Wiener process.

(not sure any of that is very helpful, but if you're not aware of the connections it may give additional places to look).

Answer 2

Perform a number of simulation and save all the results. Put them into a Histogram and you will see that some values have the property to appear more frequently. Because of the randomness you have to perform a larger number of tests so your histogram to become more reliable( even then I am not sure of the fairness of the result).

Answer 3

This problem is also submitted in Quora. The link is here

One of the replies is about simulation:

Here are exact answers for a few small cases, courtesy of Mathematica. Unfortunately the computation becomes very slow after these.

In[1]:= f[n_] := Expectation[Max[0, Max[Table[Sum[x[k], {k, i, j}], {i, n}, {j, i, n}]]], Distributed[Table[x[i], {i, n}], UniformDistribution[Table[{-1, 1}, {n}]]]]

In[2]:= Table[f[n], {n, 5}]

Out[2]= {1/4, 1/2, 23/32, 291/320, 4141/3840}