Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  konjac 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]. –  konjac Jul 2 '12 at 1:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.