Оптимальный маршрут

[arseniiv]

ozheredov
podih
Ну серьёзно, нормально он сформулировал. Есть элементарные исходы. В каждом из них клад находится в какой-то точке. Есть функция, по стратегии и положению клада выдающая длину пути, пока мы не наткнулись на него. Значит, есть функция, дающая длину пути по стратегии и элементарному исходу. Значит, если стратегия фиксирована, есть функция из элементарного исхода в длину пути. Это случайная величина, раз мы имеем вероятностное распределение на исходах, и мы можем поинтересоваться её матожиданием. Это совершенно механическое жонглирование основными определениями теорвера.

-- Вс июл 14, 2019 17:53:32 --

Видимо, непонятно, что такое стратегия. Будем считать, что это последовательность чисел $a_i$ и реализуется стратегия так: сначала мы идём вправо, пока не попадём в $a_0$, потом влево до $a_1$, потом снова вправо до $a_2$ и так далее. То, что стратегией должно считать именно такое, очевидно если иметь в виду, что мы ничего не знаем — как только мы нашли клад, мы уже победили, а пока не нашли, мы не получаем дополнительной информации, и потому весь маршрут можем спланировать заранее, ровно один.

-- Вс июл 14, 2019 17:54:10 --

Гораздо интереснее говорить о решении.

[ozheredov]

arseniiv
А, вон оно как... ну тогда сорян, виной всему моё стереотипное мышление )) Я думал, что мы втыкаем лопату и... то есть, победа -- это накрытие точки клада хотя бы одним из звеньев маршрута. Понял. Sicker, смиренно прошу простить меня

-- 14.07.2019, 17:12 --

Ок. Пусть распределение -- дельта-функция с центром на правом конце (исходно я в левом). Now what?
А не, автор вводит какие то ограничения на плотность. Но хорошо бы поставить эту задачу как минимакс: что делать, чтобы в наихудших условиях особо не обделаться

[Sicker]

ozheredov в сообщении #1405049 писал(а):

А не, автор вводит какие то ограничения на плотность

Никаких ограничений нет, есть заданная функция распределения

ozheredov в сообщении #1405049 писал(а):

Но хорошо бы поставить эту задачу как минимакс: что делать, чтобы в наихудших условиях особо не обделаться

Грубо говоря минимакс тут равен бесконечности, ибо клад может быть сколько угодно удаленным от нуля (т.к. гауссиана не затухает)
Минимакс вроде можно понимать так. Вот у нас есть функция плотности вероятности получить какую-то суммарную длину пути, т.е. по оси абцисс суммарный путь до клада, а по оси ординат плотность вероятности. Тогда сама функция плотности вероятности будет иметь примерно такой вид - на характерном расстоянии $L$ будет максимальная плотность вероятности (по идее $L$ будет совпадать или лежать близко к математическому ожиданию), которая будет спадать по мере удаления в обе стороны от $L$, и можно условно ввести характерную ширину этого холма - $\Delta L$. Я так понимаю, вы собрались минимизировать не $L$, а $L+\Delta L$? Мне кажется это немного бессмысленно от нечеткой определенности этого самого $\Delta L$

[Geen]

arseniiv в сообщении #1405036 писал(а):

сначала мы идём вправо, пока не попадём в $a_0$,

А почему $a_0$ конечно?

[ozheredov]

Geen в сообщении #1405055 писал(а):

А почему $a_0$ конечно?

Разве не для любого расположения клада и точки старта существует маршрут

arseniiv в сообщении #1405036 писал(а):

сначала мы идём вправо, пока не попадём в $a_0$, потом влево до $a_1$, потом снова вправо до $a_2$ и так далее.

с конечным $a_0$, такой, что хотя бы одно звено накрывает точку клада? Можете плииз привести контрпример?

А, кажется понял. По-видимому, с какой-то исчезающей вероятностью мы вообще не найдем клад

[EUgeneUS]

Geen в сообщении #1405055 писал(а):

А почему $a_0$ конечно?

Если при каких-то расположениях клада на множестве ненулевой меры стратегия дает бесконечный путь, то и МО длины пути будет бесконечным. Нет?
А если так, то должен быть какой-то критерий, чтобы "перестать искать под фонарем" и вернуться к жирным россыпям

-- 14.07.2019, 18:17 --

ozheredov в сообщении #1405056 писал(а):

По-видимому, с какой-то исчезающей вероятностью мы вообще не найдем клад

В условиях задачи если не вернёмся, то не найдем клад с вероятностью одна вторая, которая никуда не исчезает.

[ozheredov]

EUgeneUS в сообщении #1405059 писал(а):

Если при каких-то расположениях клада на множестве ненулевой меры стратегия дает бесконечный путь, то и МО длины пути будет бесконечным.

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

[arseniiv]

Geen в сообщении #1405055 писал(а):

А почему $a_0$ конечно?

Ну можно расширить определение, да, это вы хорошую дырку нашли — сделаем последовательности не обязательно бесконечными, и тогда, когда числа кончаются, мы идём в текущем направлении в бескрайнюю даль (и назад нам уже возвращаться не понадобится).

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

ozheredov в сообщении #1405056 писал(а):

А, кажется понял. По-видимому, с какой-то исчезающей вероятностью мы вообще не найдем клад

Нам важно не просто найти клад, нам важно найти его поскорее. А так да, если $[0; a_0]\subsetneq [a_1; a_0]\subsetneq [a_1; a_2]\subsetneq [a_3; a_2]\subsetneq \ldots$, то мы найдём клад обязательно, и наоборот, если это неверно, то клад мы найдём не достоверно.

[worm2]

Я в сообщении #1404831 писал(а):

Первое метание — на $\sqrt{2\pi}\sigma$?

Напишу, как я дошёл до жизни такой.
Во-первых, вычислений немало, где-то я мог наврать, так что следите за руками!
Во-вторых, я сразу принял $\sigma=1$, потому что понятно, что результат потом можно просто умножить на правильное $\sigma$.
В-третьих, у меня немного другие обозначения, чем у arseniiv.
Идём вправо до точки $x_0$. Потом влево до точки $-x_1$. Потом опять вправо до $x_2 > x_0$ и опять влево до $-x_3 < -x_1$. И т.д. Таким образом, все $x_i>0$.
Интересующее нас матожидание складывается из кусков, вычисляемых только на тех участках, на которые мы вступили впервые. Вычисляется стандартным образом: текущее значение пройденного пути умножается на плотность вероятности в текущей точке и интегрируется. Вспомним для начала плотность вероятности нормального распределения с нулевым средним и единичной дисперсией:

$$p(x)=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}.$$

Поехали! На нулевом участке получается:

$$M_0=\frac{1}{\sqrt{2\pi}}\int\limits_0^{x_0} xe^{-x^2/2}dx=\frac{1-e^{-x_0^2/2}}{\sqrt{2\pi}}.$$

На первом уже возникает не берущийся в элементарных функциях интеграл. Введём для него стандартное обозначение:

$$E(x)=\mathrm{erf}(x)=\frac{2}{\sqrt{\pi}}\int\limits_0^t e^{-t^2}\,dt.$$

Кусок матожидания получается:

$$M_1=\frac{1}{\sqrt{2\pi}}\int\limits_0^{x_1} (x+2x_0)e^{-x^2/2}dx=\frac{1-e^{-x_1^2/2}}{\sqrt{2\pi}}+x_0 E\left(\frac{x_1}{\sqrt{2}}\right).$$

(тут мы пользуемся симметричностью распределения). Подынтегральная добавка $2x_0$ означает, что мы бесплодно дошли до $x_0$ и обратно. На втором шаге, когда мы пойдём опять вправо, эта добавка будет уже $2x_0+2x_1$ (хотя на самом деле мы бесплодно пройдём ещё больше: $4x_0+2x_1$, но $2x_0$ из этого пути будет уже учтено в $x$). И т.д. На $n$-м шаге ($n>1$) получается такой кусок матожидания:

$$M_n=\frac{1}{\sqrt{2\pi}}\int\limits_{x_{n-2}}^{x_n} \left(x+2\sum\limits_{i=0}^{n-1} x_i\right)e^{-x^2/2}dx=\frac{e^{-x_{n-2}^2/2}-e^{-x_n^2/2}}{\sqrt{2\pi}}+\left(\sum\limits_{i=0}^{n-1} x_i\right) \left(E\left(\frac{x_n}{\sqrt{2}}\right)-E\left(\frac{x_{n-2}}{\sqrt{2}}\right)\right).$$

Искомое матожидание:

$$M=\sum\limits_{n=0}^{\infty}M_n=\sqrt\frac{2}{\pi}+x_0 E\left(\frac{x_1}{\sqrt{2}}\right)+\sum\limits_{n=2}^\infty\left(\sum\limits_{i=0}^{n-1} x_i\right) \left(E\left(\frac{x_n}{\sqrt{2}}\right)-E\left(\frac{x_{n-2}}{\sqrt{2}}\right)\right)$$

Первую часть суммы я сразу выписал, потому что она "сворачивается" легко: в ней осталось только две единицы из числителей дробей $M_0$ и $M_1$, которые мы складываем и делим на знаменатель, остальные слагаемые взаимно уничтожаются.
С остатком сложнее. Снизим его громоздкость, введя обозначение $E_k=E\left(\frac{x_k}{\sqrt{2}}\right)$:

$$x_0E_1+\sum\limits_{n=2}^\infty\left(\sum\limits_{i=0}^{n-1} x_i\right) \left(E_n-E_{n-2}\right)$$

Соберём вместе коэффициенты перед $x_i$:

\begin{align*} &x_0\left(E_1+E_2-E_0+E_3-E_1+E_4-E_2+E_5-E_3+\dots\right)+\\ +&x_1\left(E_2-E_0+E_3-E_1+E_4-E_2+E_5-E_3+\dots\right)+\\ +&x_2\left(E_3-E_1+E_4-E_2+E_5-E_3+\dots\right)+\\ +&\dots \end{align*}

Видим, что почти всё уничтожается и остаётся

$$x_0\left(2E_\infty-E_0\right)+x_1\left(2E_\infty-E_0-E_1\right)+x_2\left(2E_\infty-E_1-E_2\right)+\dots$$

Учитывая, что $E_\infty=\mathrm{erf}(\infty)=1$, имеем:

$$M=\sqrt\frac{2}{\pi}+\sum\limits_{n=0}^{\infty}x_n\left(2-E_{n-1}-E_n\right),$$

где для пущей компактности доопределено $x_{-1}=0$, соответственно, $E_{-1}=E(0)=0$.
Вот эту вещь нам и предстоит минимизировать.
Давайте-ка для ещё большей компактности определим $F(x_i)=F_i=1-E_i=1-\mathrm{erf}(x_i/\sqrt{2})$ (напоминаю, что $F_{-1}=1$ — константа):

$$M(x_0,x_1,\dots)=\sqrt\frac{2}{\pi}+\sum\limits_{n=0}^{\infty}x_n\left(F(x_{n-1})+F(x_n)\right) \to\min$$

Функция $F$ — гладкая, поэтому со спокойной душой (и тяжёлым сердцем, ибо $M$, как функция счётного числа аргументов, по-хорошему, требует к себе отдельного уважения) дифференцируем по каждой переменной:

$$\frac{\partial M}{\partial x_n}=F(x_{n-1})+F(x_n)+F'(x_n)(x_n+x_{n+1})=0.$$

Отсюда следует рекуррентная формула:

$$x_{n+1}=-\left(x_n+\frac{F(x_{n-1})+F(x_n)}{F'(x_n)}\right).$$

К сожалению, этого недостаточно для определения $x_0$
Но если мы обнаглеем и продлим эту формулу на $n=-1$ (для этого ещё понадобится доопределить $x_{-2}=0$), то получим:

$$x_0=0-\frac{1+1}{F'(0)},$$

откуда, вспоминая, что такое $F$, получаем: $x_0=\sqrt{2\pi}$.
Что можно сказать в оправдание такой наглости? Ну, например, вот что: допустим, нулевому шагу вправо предшествовал "минус первый" шаг влево на неизвестную величину, а потом будем уменьшать эту величину до нуля. На итоговое поведение это не повлияет. Так себе оправдание, но я смутно чувствую, что в нём что-то есть.

[Geen]

Похоже меня не поняли - почему первый шаг не бесконечно малый?

[podih]

arseniiv в сообщении #1405073 писал(а):

нам важно найти его поскорее

Т.е. надо максимилизировать МО.
Тогда да. Возможно, поворотов будет бесконечно много. Интуиция здесь не работает. Считать надо...
Путь растёт линейно, а прибыль с объеденного куска обратно-экспонентуально. А на недоеденном куске сравнительно жирнее. Но надо возвращаться...
Плюнуть на теорию и зарубиться в численном эксперименте?
Почитал worm2. Да, мне здесь делать нечего.

[arseniiv]

Geen
Ну пусть он бесконечно малый, погоды-то он не сделает и в вещественных числах не выразится. Какая ему стать быть бесконечно малым?

podih в сообщении #1405085 писал(а):

Т.е. надо максимилизировать МО.

Минимизировать МО, как написано притом в первом посте.

podih в сообщении #1405085 писал(а):

Да, мне здесь делать нечего.

Спасибо, наконец-то.

[Geen]

arseniiv в сообщении #1405086 писал(а):

Какая ему стать быть бесконечно малым?

В терминах поста worm2 я уверен лишь в том, что $x_{-\infty}=0$...

[arseniiv]

Мы не можем ходить много на мелкие шаги — так мы слишком много раз пройдём уже проверенные места зазря.

Кстати если бы распределение было экспоненциальным, нам было бы полезнее всего идти не останавливаясь вправо. Но если бы оно было сдвинутым левее, то (сейчас будет от балды) скорее всего нам будет полезнее идти сначала влево до точки скачка плотности, а потом поворачивать вправо и не останавливаться.

-- Вс июл 14, 2019 22:38:46 --

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

-- Вс июл 14, 2019 22:42:48 --

А вот можно наоборот выдать бедолаге одну канистру воды и отправить на поиски фонтана молодости (где заодно стоит телепортер домой), то есть искать стратегию, максимизирующую вероятность успеха найти клад (как кому-то и хотелось) при возможности протопать только данное заранее расстояние. Ещё можно искать лучшую из стратегий, дающих неединичную фиксированную заранее вероятность успеха. Вот теперь у нас будет большое пространство, где возможно (или нет) всё связать. Кто хочет попытаться?

[iancaple]

worm2 в сообщении #1405082 писал(а):

Отсюда следует рекуррентная формула:

$$x_{n+1}=-\left(x_n+\frac{F(x_{n-1})+F(x_n)}{F'(x_n)}\right).$$

Извините, у меня немножко другая формула получается
$x_{n+1}=x_n+\frac{(-1)^{n}+F(x_{n-1})-F(x_n)}{F'(x_n)}$
Вот ее обоснование. $x_n$ при n четном точка поворота влево. точка $x_n+dx_n$ даст меньшее итоговое матожидание, если клад на отрезке между ними, что будет с вероятностью $\sim F'(x_n)dx_n$ ,причем меньше на величину $2|x_n-x_{n+1}|$ , то есть не при следующем проходе за точку $x_n$, а сразу.В остальных случаях даст большее матожидание на величину $2dx_n$, с вероятностью, эквивалентной при $dx_n\to 0$ той, что клад не был найден ранее, $1-|F(x_n)-F(x_{n-1})|$. Если $x_n$ оптимальная точка поворота, получаем равенство
$|x_n-x_{n+1}|F'(x_n)+|F(x_n)-F(x_{n-1})|=1$ Под модулями оба положительные, если точка поворота влево, и оба отрицательные, если n было нечетное и точка поворота вправо.
Поэтому раскрываются $(x_n-x_{n+1})F'(x_n)+F(x_n)-F(x_{n-1})=(-1)^n$. При $n=0$ $F(x_{-1}):=\frac 12$
Получаются $x_0=\sqrt{2\pi},x_1=-84,14753$