Ожидание максимальной последовательной суммы подпоследовательности случайной последовательности

Question

Вот проблема из Programming Pearls 2-е издание (глава 8.7):

Рассматривая последовательность действительных чисел, элементы которой нарисованы равномерно из диапазона [-1, 1], какова ожидаемая максимальная сумма последовательной подпоследовательности? (Если все элементы отрицательные, максимальная сумма 0.)

Предполагая, что длина последовательности N, есть ли замкнутая форма для ожидаемой максимальной суммы подпоследовательности f(N)? Я пытаюсь сделать какую-то симуляцию, но не смог найти никакой подсказки.

Спасибо за помощь.

Answer 1

Это похоже на броуновское движение в 1D, но с необычным распределением по размерам шагов. для больших N он приближается к винеровскому процессу.

(не уверен, что все это очень полезно, но если вы не знаете о связях, это может дать дополнительные места для поиска).

Answer 2

Выполните ряд симуляций и сохраните все результаты. Поместите их в гистограмму, и вы увидите, что некоторые значения имеют свойство появляться чаще. Из-за случайности вы должны выполнить большее количество тестов, чтобы ваша гистограмма стала более надежной (даже тогда я не уверен в справедливости результата).

Answer 3

Эта проблема также представлена ​​в Quora. Ссылка здесь

Один из ответов о симуляции:

Вот точные ответы на несколько небольших случаев, предоставленных Mathematica. К сожалению, после этого вычисления становятся очень медленными.

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}