(9)–(10), p. 1463 — under (8) with x₀ = 1, x_{j+1}ⁿ⁻¹ = ((n − 1)/n)xⱼⁿ + x₁ⁿ⁻¹ − (n − 1)/n
ProvedCorreaThreshold.Adaptive.recursion_closed_formiidp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-inequalityrecursion
Let and let be real numbers with satisfying
for , where . Then
With this is (9), , raised to the power ; for it is (10).
It identifies the recursion with that of Hill and Kertz.
Formalization Note The statement is the -st power of (9), so no real roots appear and it holds for all real .
Preamble
import Mathlib import Definitions.Def_CorreaThreshold_Adaptive_Setting
Formal statement
namespace CorreaThreshold.Adaptive
open MeasureTheory ProbabilityTheory
theorem recursion_closed_form {n : ℕ} (hn : 2 ≤ n) (x : ℕ → ℝ) (hx0 : x 0 = 1)
(j : ℕ) (hj : 1 ≤ j)
(h8 : ∀ i ∈ Finset.Icc 1 j,
x (i - 1) ^ n / n - x i ^ n / n =
x i ^ (n - 1) / ((n : ℝ) - 1) - x (i + 1) ^ (n - 1) / ((n : ℝ) - 1)) :
x (j + 1) ^ (n - 1) = ((n : ℝ) - 1) / n * x j ^ n + x 1 ^ (n - 1) - ((n : ℝ) - 1) / n := by sorry
end CorreaThreshold.Adaptive
Source
Correa, Foncea, Hoeksma, Oosterwijk, Vredeveld, Posted price mechanisms and optimal threshold strategies for random arrivals, Math. Oper. Res. 46 (2021), p. 1463, (9), (10) and the induction following (10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.