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

[DeBill]

iancaple
Ну, с учетом разницы в обозначениях, это как раз и есть то...

[worm2]

DeBill, iancaple, да, так и есть, формулы совпадают.
У меня просто с самого начала повелось, что все иксы положительны, а знаки я уже в самом конце расставляю.
Т.е. если истинные координаты поворотов кладоискателя взять за $a_n$, то мои $x_n=(-1)^na_n$, и формула преобразуется к такой:

$$a_{n+1}=a_n+\frac{2(-1)^n+F(a_{n-1})-F(a_n)}{F'(a_n)}.\eqno{(1)}$$

Тут у меня вместо $(-1)^n$ стоит $2(-1)^n$. Вероятно, вы, iancaple, за $F$ обозначаете половину той функции $F$, которая у меня, тогда совпадение будет полным. Это также объясняет вашу формулу $F(x_{-1})=\frac 1 2$ (у меня $F(x_{-1})=F(0)=1$). Поэтому тут я должен расписать свою $F$ подробно:

$$F(x)=\mathrm{erfc}\left(\frac{x}{\sqrt{2}}\right)=1-\mathrm{erf}\left(\frac{x}{\sqrt{2}}\right)=\sqrt\frac{2}{\pi}\int\limits_{x}^{+\infty}e^{-t^2/2}\,dt \quad \Rightarrow\quad \frac{1}{F'(a_n)}=-\sqrt\frac{\pi}{2}e^{a_n^2/2}.$$

(определения $\mathrm{erf}$ и $\mathrm{erfc}$ взяты, как они приняты в Wolfram).
Далее, рассмотрим дробь в (1). Функция $F$ на $\mathbb{R}$ убывает от 2 до 0, знак $a_n$ совпадает со знаком $(-1)^n$, поэтому знак $F(a_{n-1})-F(a_n)$ противоположен знаку $2(-1)^n$, а по модулю всегда меньше модуля этой величины (двойки). Поэтому знак числителя в (1) совпадает со знаком $(-1)^n$, и можно переписать (1) как:

$$a_{n+1}=a_n-(-1)^n e^{a_n^2/2}\left(\sqrt{2\pi}-\left|\int\limits_{a_{n-1}}^{a_n}e^{-t^2/2}\,dt\right|\right).$$

По крайней мере, эта формула не страдает от неоднозначностей. По ней получается $a_1\approx -26.8494$.

[DeBill]

Пусть $F(x)$ - некий функционал, и мы ищем его экстремум, прравнивая производную к нулю.
Пусть у нас нашлось целое семейство $x_t$ решений: $F'(x_t) =0$.
Посчитаем значения функционала $f(t)=F(x_t) $ в энтих точках.
Тогда: $\dot{f}=F'(x_t)\dot{x_t}=0$. Значит, $f$ - константа....

Так что для нашей задачи, $x_0$ можно выбирать произвольно - значения экстремума не зависит...(ну, если, конечно, работают все оговоркиworm2, связанные с бесконечномерномерностью, и еще такие же добавить...)

[iancaple]

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

По крайней мере, эта формула не страдает от неоднозначностей. По ней получается $a_1\approx -26.8494$.

Да у меня тоже теперь $a_1\sim -26.84944$, была ошибка.
$F$ у меня была интегральная функция распределения места клада, для общности, обязательно непрерывная.
А вот начинать поиски с $x_{-1}=0$ неоптимально, но это уже другая задача, так? И ответ я не знаю

[Sicker]

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

Кстати а нельзя ли тут стратегию с бесконечными поворотами получить как-то из стратегий с конечным числом поворотов (и их друг из друга)?

Т.к. гауссиана никогда не затухает до нуля то нет, нельзя. Т.е. при любой стратегии с конечным числом поворотов у нас есть ненулевая вероятность никогда не наткнуться на клад. В принципе стратегия с конечным числом поворотов сработала бы в случае если распределение угасает ровно в ноль вне какого-то отрезка.
Я короче распишу случай для предельной функции распределения зеркальных плотностей $f(x)=\frac{1-|x+L|}{2}$ на $[-L-1;-L+1]$ и $f(x)=\frac{1-|x-L|}{2}$ на $[L-1;L+1]$ при $L\rightarrow \infty$. Там тогда можно радиусы метаний разложить как $L+1+a_0 d+a_1 d^2+...$, где $d=\frac{1}{L}$

[arseniiv]

Sicker в сообщении #1405187 писал(а):

Т.е. при любой стратегии с конечным числом поворотов у нас есть ненулевая вероятность никогда не наткнуться на клад.

Это да, это бы было бы как-то учтено.

[worm2]

Я тут, попробовал численно посчитать, подставляя различные значения $a_0$ и $a_1$ (в моей терминологии $x_0$ и $x_1$), и считая дальше по рекуррентной формуле.
И у меня, знаете ли, фигня получается.
Ситуацию осложняет то, что по рекуррентной формуле абсолютные значения абсцисс очень быстро растут, буквально, как "степенная башня". И в процессе вычислений очень быстро наступает переполнение, хотя я ещё не уверен, что остаток ряда мал, и его можно отбросить.
Но это ещё не самое странное.
По рекуррентной формуле запросто может получиться, что $|a_n| < |a_{n-2}|$, т.е. мы должны поворачивать раньше, чем достигаем границы, которую посетили в прошлый раз.
Отсюда можно сделать неутешительный вывод: то, что я там дифференцирую функцию бесконечного числа аргументов и приравниваю производные к нулю — это ведь только необходимое условие глобального минимума. Нужно ещё, чтобы матрица вторых производных была положительно определена (что бы это ни значило в бесконечномерном случае), а она, похоже, не всегда.
Могу лишь поделиться странным результатом: минимум матожидания, который я получил, равен примерно 2.91 и достигается примерно при $a_0=+1.4$, $a_1=-2.6$ (получен на сетке с шагом 0.1). Причём этот минимум лежит на границе "допустимой области": рядом с ним наблюдается фигня ($|a_n| < |a_{n-2}|$).
Значение при $a_0=0$, $a_1=-\sqrt{2\pi}$, которое я считал минимальным, даёт матожидание примерно 3.66233, т.е. существенно большее.

[worm2]

На предыдущем допросе я искал решение среди различных $a_0$ и $a_1$, совершенно забыв, что $a_1$ однозначно определяется через $a_0$ (ведь $a_{-1}=0$ и $F_{-1}=1$).
Поэтому достаточно произвести одномерный поиск $a_0$. После того, как я это осознал, дела пошли гораздо веселее.
Увеличивая точность, у меня слетела шляпа от удивления. Чем ближе я подходил к оптимальной точке, тем менее полученная последовательность проявляла склонность к взрывному росту: она неторопливо гуляла туда-сюда, и всё позже, как бы нехотя говорила: мол, засиделась я тут, пора и честь знать, и наконец резко взмывала в свою "степенную башню".
Причём шаг влево от оптимальной точки приводил к бесполезному "замыканию в себе" ($|a_{n+2}|<|a_n|$), а шаг вправо — к гораздо более раннему старту в космос.
К двенадцатому знаку после запятой до меня этот намёк начал доходить. Оптимальная последовательность вообще никуда не улетает, а территорию захватывает потихоньку!
Вот ряд, рассчитанный для точности $a_0$ в 15 значащих цифр (стандартная двойная точность компьютерных чисел):
+1.44085409998362
-2.6275801141085
+3.63220011457
-4.5203424258
+5.32668133
-6.0715776
+6.76811
-7.425
+8.0
Уменьшение числа знаков после запятой означает уменьшение соответствующей точности. Точность рассчитывалась исходя из примерного совпадения членов последовательности для начальных значений $a_0$ и $a_0+10^{-14}$. Помимо "естественного" падения точности, обусловленного чрезвычайной чувствительностью к начальному значению $a_0$, есть ещё и вычислительные сложности. Напомню расчётную формулу:

$$a_{n+1}=a_n-(-1)^n e^{a_n^2/2}\left(\sqrt{2\pi}-\left|\int\limits_{a_{n-1}}^{a_n}e^{-t^2/2}\,dt\right|\right).$$

Её можно переписать так (пользуясь симметрией плотности распределения):

$$a_{n+1}=a_n-(-1)^n e^{a_n^2/2}\left(\int\limits_{|a_{n-1}|}^{+\infty}e^{-t^2/2}\,dt+\int\limits_{|a_n|}^{+\infty}e^{-t^2/2}\,dt\right).$$

С ростом $|a_n|$ коэффициент перед интегралами $e^{a_n^2/2}$ очень быстро растёт, в то время как сами интегралы очень быстро убывают, но насколько быстро? Используемая библиотечная функция для расчёта $\mathrm{erfc}(x)$ имеет сомнительную относительную погрешность для больших значений агрумента, и не совсем понятно, что с этим можно сделать. Да, есть асимптотическая формула, но спасает ли она в данном случае?
Тем не менее, несмотря на все эти сложности, тенденция ощущается. Видно, что разность между соседними точками не растёт, а даже уменьшается, что, согласитесь, более соответствует интуитивному представлению о том, как должно быть.
Итак, численный эксперимент подсказывает нам, что начальное значение оптимальной последовательности — замечательное число. Оно, с одной стороны, является минимальным числом, для которого выполняется необходимое условие $D_n=|a_{n+2}|-|a_n|>0$, а, с другой стороны — максимальным числом, для которого эта последовательность разностей $D_n$ ограничена сверху.
Попытка засунуть оптимальное начальное значение 1.44085409998362 (как и минимальное значение математического ожидания времени поиска 2.903665477166) в Inverse Symbolic Calculator успеха не дала: эта база данных математических констант ничего о них не знает.
Да, ещё хорошая новость: та часть "бесконечной матрицы" вторых производных, которую удалось рассчитать, имеет совершенно явное и сильное диагональное преобладание, что даёт "положительную определённость", а значит, и основание считать, что найденный экстремум — именно минимум.

[worm2]

Похоже, всё уже придумано и решено до нас
https://math.stackexchange.com/question ... d-solution
Там есть и ссылки на статьи, например:
https://link.springer.com/article/10.1007%2FBF02786568

[worm2]

Оптимальное значение первого прыжка 1.440854... близко к корню уравнения

$$1+\mathrm{erfc}\left(\frac{x}{\sqrt{2}}\right)=\sqrt{\frac{2}{\pi}}x.$$

Это уравнение получается, если попробовать продлить последовательность в другую сторону, полагая $a_{-1}=0$, и вычисляя $a_{-2}=1.44084546...$. К сожалению, получившееся $a_{-2}$ не равно в точности $a_0$ Причина такого близкого совпадения неизвестна. Разность составляет примерно 0.00000863, что, в свою очередь, недалеко от $\mathrm{erfc(\pi)}\approx0.00000888$. Возможно, существует какой-то быстро сходящийся алгоритм, с помощью которого можно эффективно вычислить оптимальное $a_0$. Но вряд ли его можно получить таким нумерологическим способом, подбирая подходящие константы