Задачка про туристов (теория вероятностей, вычисления)

[MetaMorphy]

Всем привет. Вслед за этой темой вспомнилась такая задача (вернее, две).

Имеются две остановки (отправления и прибытия), через которые проходят $n$ (скажем, автобусных) маршрутов. Пусть для $1\leqslant k\leqslant n$ пассажиру, появившемуся на остановке отправления, требуется $W_k$ времени (с момента появления!) для ожидания автобуса номер $k$, и сверх того, $T_k$ времени, чтобы доехать на нём до остановки прибытия. Здесь $W_k$ и $T_k$ ($1\leqslant k\leqslant n$) — случайные величины, причём $W_k$ независимы в совокупности и (не будем выпендриваться) имеют равномерные распределения в $(0,w_k)$, а величины $T_k$ имеют математические ожидания $t_k$ (остальное для дальнейшего неважно).

Турист поглупее появляется на остановке отправления и добирается до остановки прибытия первым прибывшим автобусом. Требуется найти математическое ожидание времени, которое ему на это понадобится.

(Оффтоп)

Моё решение тут таково. Время ожидания $W=\min_{1\leqslant k\leqslant n}W_k$ имеет функцию распределения

$$F(w)=\Bbb{P}(W<w)=1-\Bbb{P}\Big(\bigwedge_{1\leqslant k\leqslant n}(W_k>w)\Big)=1-\prod_{k=1}^{n}\Big(1-\frac{w}{w_k}\Big),\qquad 0<w<w_0:=\min_{1\leqslant k\leqslant n}w_k$$

и, соответственно, математическое ожидание $\overline{W}=\displaystyle\int_{0}^{w_0}w\,dF(w)=\int_{0}^{w_0}(1-F(w))\,dw$. Математическое ожидание времени поездки равно $\overline{T}=\displaystyle\sum_{k=1}^{n}p_k t_k$, где

$$p_k=\Bbb{P}\Big(\bigwedge_{\substack{1\leqslant j\leqslant n\\j\neq k}}(W_j>W_k)\Big)=\int_{0}^{w_0}\Bbb{P}\Big(\bigwedge_{j\neq k}(W_j>w)\Big)\,d\Bbb{P}(W_k<w)=\frac{1}{w_k}\int_{0}^{w_0}\prod_{j\neq k}\Big(1-\frac{w}{w_j}\Big)\,dw$$

есть вероятность того, что автобус номер $k$ придёт первым. Собирая вместе, получаем ответ

$$\overline{W}+\overline{T}=\int_{0}^{w_0}\left(1+\sum_{k=1}^{n}\frac{t_k}{w_k-w}\right)\prod_{k=1}^{n}\Big(1-\frac{w}{w_k}\Big)\,dw.$$

(А теперь - вторая скорость.) Турист поумнее в момент прибытия любого из автобусов принимает решение, использовать его или нет. Причём оптимальным образом (зная то, что уже произошло, и распределения вместе с параметрами). Будем считать, что автобус с любым выбранным номером прибывает лишь однажды (т.е. что его второго прибытия дожидаться нет смысла). Задача та же — найти математическое ожидание времени, потраченного на ожидание и поездку.

(Оффтоп)

Тут у меня решение получается таким.

Для вектора $\mathbf{x}=(x_1,\ldots,x_n)$ положим $\min\mathbf{x}=\min_{1\leqslant k\leqslant n}x_k$; для скаляра $x$ обозначим $\mathbf{x}-x=(x_1-x,\ldots,x_n-x)$; для $1\leqslant k\leqslant n$ через $\mathbf{x}_k'=(\ldots,x_{k-1},x_{k+1},\ldots)$ обозначим вектор $\mathbf{x}$ без его $k$-й компоненты.

Пусть $\mathbf{w}=(w_1,\ldots,w_n)$, $\mathbf{t}=(t_1,\ldots,t_n)$ и $T_n(\mathbf{w},\mathbf{t})$ — ответ к задаче. Очевидно, $T_1(\mathbf{w},\mathbf{t})=t_1+w_1/2$.

Теперь если $K$ — (случайный, событиями нулевой вероятности пренебрегаем) номер первого прибывшего автобуса и $W=W_K$ — (как и раньше) время его ожидания, то

$$\Bbb{P}(K=k\wedge W<t)=\Bbb{P}\Big((W_k<t)\wedge\bigwedge_{j\neq k}(W_j>W_k)\Big)=\frac{1}{w_k}\int_{0}^{t}\prod_{j\neq k}\Big(1-\frac{w}{w_j}\Big)\,dw\qquad(1\leqslant k\leqslant n,\ 0<t<\min\mathbf{w})$$

При условии $K=k\wedge W=w$, величины $W_j$ ($j\neq k$) остаются независимыми в совокупности, с равномерными распределениями в $(w,w_j)$. Условное математическое ожидание требуемого итогового времени $T$ при этом условии получается равным $w + \min\{t_k,T_{n-1}(\mathbf{w}_k'-w,\mathbf{t}_k')\}$ (взятие минимума соответствует принятию решения, садиться или ждать дальше). Собирая в кучу все эти наблюдения, получаем (такое вот громоздковатое) соотношение

$$T_n(\mathbf{w},\mathbf{t})=\int_{0}^{\min\mathbf{w}}\left(1+\sum_{k=1}^{n}\frac{\min\{t_k,T_{n-1}(\mathbf{w}_k'-w,\mathbf{t}_k')\}}{w_k-w}\right)\prod_{k=1}^{n}\Big(1-\frac{w}{w_k}\Big)\,dw$$

(из которого можно получить и $T_1$, если в качестве базы индукции принять $T_0\equiv\infty$).

Внимание — вопрос. В "задаче поглупее" всё действительно "поглупее" — и интеграл берётся от многочлена, и вычисления можно уложить в $\mathcal{O}(n^2)$ операций (причём численно устойчивым путём). В задаче "поумнее" интеграл брать не хочется уже при $n=3$, не говоря о больших значениях $n$ (когда это, скорее всего, аналитически уже просто-напросто не сделать), а что касается вычислений — я вижу только алгоритмы экспоненциальной сложности по $n$ (если говорить о фиксированной точности). Можно ли быстрее? (И вообще, правильно ли моё решение в этом случае?..)