# Expectation of the maximum consecutive subsequence sum of a random sequence

There is a problem from Programming Pearls 2nd edition (Problem 4 in Chapter 8.7):

If the input elements in the input array are random real numbers chosen uniformly from [-1,1], what is the expected value of the maximum subvector?

If all the elements are negative, the maximum sum is 0.

Thanks for help.

-
It's a bad idea to make the problem look quoted when you haven't actually quoted it. Problem 4 in Chapter 8.7 of the second edition reads: "If the elements in the input array are random real numbers chosen uniformly from $[-1,1]$, what is the expected value of the maximum subvector?". Note that it talks about an array, not a sequence. A sequence wouldn't have an expected maximum consecutive subsequence sum, since the consecutive subsequence sums are unbounded with probability $1$. –  joriki Jul 1 '12 at 16:12
There's a hint for this problem on p. 203: "Plot the cumulative sum as a random walk." –  joriki Jul 1 '12 at 16:34
@joriki Thanks for your remind. I have edited the quoted sentence. –  Kun Huang Jul 2 '12 at 1:19
@joriki I have few knowledge about random walk. From limited materials, I still could not solve it, though I know the original problem is equivalent to compute the expect value of the maximum rise up in a n-step 1D random walk which starts from $x=0$ and whose each step is chosen uniformly from [-1,1]. –  Kun Huang Jul 2 '12 at 1:23