Условие
Каждый день я получаю случайный заработок, равномерно распределённый на [0, 1]. Заработки независимы. Получив деньги, я решаю, работать ли дальше или навсегда выйти на заслуженный отдых. Если я ухожу, мой последний заработок удваивается, но дальше я не получаю ничего.
Общее благосостояние считается с дисконт-фактором δ: R = δu1 + δ2u2 + δ3u3 + …, где uk — деньги, полученные в день k.
Как выглядит стратегия, максимизирующая E(R), и чему равен максимальный E(R)?
Решение источника
Оптимальная стратегия пороговая: если зарплата большая, «бери и беги», иначе работай дальше. Если порог равен c, то R = 2u1 при u1 ≥ c и R = u1 + δE(R) иначе. Беря ожидание (аккуратно, через условные ожидания), получаем
E(R) = (1 − c) · 2 · (1 + c)/2 + c · (c/2 + δE(R)).
Второе уравнение — безразличие при u1 = c: 2c = c + δE(R). Решая систему, получаем квадратное уравнение и берём корень, стремящийся к нулю при δ → 0:
c(δ) = (1 − √(1 − 2δ2))/δ.
Редакционное объяснение
Порог равен максимальному E(R). Пусть V — максимальное E(R) в постановке задачи, где уже первый день дисконтируется множителем δ. В день 1 при заработке w уход даёт δ · 2w, а продолжение — δw плюс та же игра, начатая на день позже, которая в среднем стоит δV. Уходить выгодно, когда 2w ≥ w + V, то есть при w ≥ V. Значит, оптимальный порог c совпадает с V. Источник записывает рекурсию без множителя δ у первого дня, поэтому его E(R) в 1/δ раз больше, но порог от этого не меняется: c = δ · Eист(R) = V.
Уравнение. V = δ · E max(2w, w + V) = δ · (E w + E max(w, V)). При V < 1 имеем E max(w, V) = V2 + (1 − V2)/2, откуда V = δ(1 + V2/2), то есть δV2 − 2V + 2δ = 0 и V = (1 − √(1 − 2δ2))/δ. Второй корень больше 1/δ > 1 и противоречит предположению V < 1.
Чего не хватает в источнике. Формула верна, только пока порог не превышает 1, то есть пока (1 − √(1 − 2δ2))/δ ≤ 1. Это равносильно δ ≤ 2/3. При δ = 2/3 порог равен ровно 1. При δ > 2/3 уходить не выгодно никогда: даже максимальная зарплата 1 не перевешивает ценность продолжения. Тогда V = δ(1/2 + V), и
при δ ≥ 2/3 оптимально работать всегда, E(R) = δ/(2(1 − δ)); при δ ≤ 2/3 — уходить, как только заработок не меньше c = (1 − √(1 − 2δ2))/δ, и E(R) = c.
При 2/3 < δ ≤ 1/√2 ≈ 0,707 формула источника молча даёт порог больше 1, а при δ > 1/√2 корень становится комплексным — это и есть сигнал, что пороговое решение с c < 1 перестало существовать.
Числа. δ = 0,5: c = E(R) = 2 − √2 ≈ 0,586. δ = 0,6: c ≈ 0,785. δ = 2/3: c = E(R) = 1. δ = 0,9: уходить не нужно, E(R) = 4,5. Обе ветви склеиваются непрерывно: при δ = 2/3 формула δ/(2(1 − δ)) тоже даёт 1.
Проверки. При малом δ порог близок к δ: почти любой заработок выгодно удвоить сразу, и E(R) ≈ δ · E(2w) = δ. Итерация уравнения Беллмана, перебор порогов по сетке и моделирование 200 000 траекторий при δ = 0,5 (среднее 0,586) совпали с формулами.
Типичные ошибки: считать E(2u1) вместо условного ожидания E(2u1 | u1 ≥ c) = 1 + c; брать не тот корень квадратного уравнения; применять формулу при δ > 2/3.
Что не следует из ответа
Ответ максимизирует средний дисконтированный доход и ничего не говорит о риске: человек, которому важна гарантированная сумма, может уходить раньше.
Порог не зависит от номера дня только потому, что горизонт бесконечен и все дни устроены одинаково. При конечном сроке работы порог менялся бы день ото дня и в последний день был бы равен нулю.
Борис Демешев и участники · probability_pro, задача «Уход на заслуженный отдых» · Исходное задание и решение · CC BY 4.0. Адаптация: условие сохранено, вывод источника пересказан; уточнение про дисконт первого дня, разбор случая δ ≥ 2/3, численные примеры и проверки добавлены редакцией.