Случайное блуждание с поглощением: быстрый алгоритм

[alexey007]

Всем привет! Помогите найти быстрое решение задачи:

Частица стартует из $x_0 > 0$ и делает случайные прыжки в $x=0$ поглощение:

$$X_{n+1} = \begin{cases} X_n + \xi_n, & X_n > 0 \\ 0, & X_n \leq 0 \end{cases}$$

где $\xi$ имеет дискретное распределение с $k = 4$ точками $(u_i, p_i)$, $\mu = \mathbb{E}[\xi] < 0$.

Нужно вычислить $\mathbb{E}[X_N]$ при произвольном $N$ (от 1 до $10^6$).

Без поглощающей границы $N$-кратная свёртка считается через БПФ . С поглощением этот трюк не работает напрямую.

Вопрос: существует ли быстрый алгоритм, дающий $\mathbb{E}[X_N]$ с заданной точностью?

[mihaild]

Про величины шагов что-то известно? Более точно - у нас количество возможных итогов $O(n)$ (если, например, шаги бывают 1,2,3,4) или $O(n^4)$ (если шаги линейно независимы над $\mathbb Q$)?

[alexey007]

mihaild в сообщении #1727572 писал(а):

Про величины шагов что-то известно?

Да, структура шагов следующая.

Все шаги кратны фиксированному $h > 0$ (шаг сетки), то есть $u_i \in\mathbb{Z}$. Распределение имеет $k = 4$ точки вида:

$$\xi \in {-h,; h,; u_3,; u_4}$$

где $u_3, u_4 \gg h$ — редкие большие прыжки. Вероятности убывают с ростом шага:

$$p_1 \gg p_2 \gg p_4 \gg p_3$$

Например: $\xi = (-1, 1, 10, 100)$ с вероятностями $(0.5, 0.25, 0.2, 0.05)$.

[mihaild]

Вроде бы можно просто сказать, что вероятность после $n$ шагов сдвинуться на величину, отличающуюся от $n \mathbb E \xi$ больше чем на $c \sqrt n$ мала, соответственно можно просто считать вероятности попасть в каждую точку отрезка длины $O(\sqrt N)$, и сложность получается $O(N^{3/2})$.

[Евгений Машеров]

Для приведенных значений вероятностей и длин шагов я бы тупо считал свёртку в лоб, безо всякий фурьеризмов, для первой сотни (ну, пусть тысячи) значений N, а потом заметил бы, что среднее уползло вправо (для сотни - на 495, для тысячи - на 4950, это оценка без учёта поглощений, там ещё больше будет), при этом вероятность, что из сотни шагов не будет "большого скачка" на сотню, равна 5$.92052922\cdot 10^{-3}$, а для тысячи $5.,918227477\cdot 10^{-23}$
И затем, имея верно (с учётом всех поглощений) рассчитанное значение матожидания, я бы пренебрёг для больших значений поглощениями, и просто прбавлял бы 4.95 при каждом увеличении N.

[Zahar Kartashov]

А есть какой-то общий подход для решения задачи на собственные значения для случая цепей Маркова с бесконечным (счетным) числом состояний?