algorithmprogramming-pearls

Expectation of the maximum consecutive subsequence sum of a random sequence

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.

Solution

  • 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).