ЛОР, выручай.
Есть выборка значений в дискретном времени (x_1 при t_1=1, ..., x_50 при t_50=50, например). Работаем с ней по следующему правилу: берём первое значение, а любое последующее с равной вероятностью либо так же берём, либо нет и пропускаем. Задача: посчитать матожидание суммы при таких вот случайных действиях.
Пример: пусть есть выборка {x_1,x_2,x_3,x_4,x_5}. Матожидание после второго шага: 0.5(x_1+0)+0.5(x_1+x_2). После третьего: 0.25(x_1+0+0)+0.25(x_1+0+x_3)+0.25(x_1+x_2+0)+0.25(x_1+x_2+x_3). И так далее.
Проблема в том, что для нахождения матожидания суммы после n шагов нужно предварительно вычислить 2^{n-1} слагаемых (потому что со второго по n-й шаги у нас два возможных ветвления каждый раз: берём или пропускаем), что представляется затруднительным уже для n=50 или n=100.
Внимание, знатоки, как составить применимый на практике алгоритм?
