Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates
arXiv:2607.02150v1 [cs.DS] 2 Jul 2026
Jiawei Zhang Department of Technologies, Operations, and Statistics Stern School of Business, New York University [email protected] July 3, 2026
Abstract This paper studies additive regret in the multi-secretary problem, defined as the gap between the expected offline prophet reward and the reward of the best online policy. Prior work established O(log T ) regret for bounded-density distributions with connected support and O((log T )2 ) upper bounds for bounded-density distributions with support gaps. It was unknown whether the extra logarithmic factor is necessary even in the one-resource model. We prove that it is necessary. For a mixture of two separated uniform distributions at the critical capacity, the optimal regret grows at least on the order of (log T )2 . Thus the existing O((log T )2 ) upper bounds for boundeddensity gapped instances, including those implied by network revenue management models with continuous rewards, are tight in this simplest specialization. The same framework also yields a matching lower bound for gapped distributions whose gap-facing densities vanish near the support edges; this companion result is given in the appendix. The proofs use Bellman certificates: feasible solutions to a relaxation of the exact Bellman recursion. This framework converts lower bounds into explicit certificate constructions and identifies why support gaps permit larger regret.
1
Introduction
In the multi-secretary problem, a decision maker observes independent values V1 , . . . , VT ∼ F sequentially and may accept at most k of them. The objective is to maximize the expected total accepted value. We measure performance by additive regret against the offline, or prophet, benchmark: the expected reward of a decision maker who observes all T realized values before selecting. Because all values are nonnegative and the offline decision maker has only the cardinality constraint, the offline optimum is obtained by selecting the largest k realized values. Thus the prophet benchmark is the expected sum of the largest k order statistics, and the regret is this benchmark minus the expected reward of the optimal online policy. The order of this regret depends sharply on the local structure of the distribution F . Arlotto and Gurvich (2019) show that, when F has finite support, the regret is uniformly bounded in the horizon. For continuous distributions with connected support and density bounded above and away from zero on the relevant interval, such as a uniform distribution, Lueker (1998) and Bray (2024) show that the tight order is logarithmic. Besbes et al. (2024) show that substantially larger regret can arise when the distribution places little probability mass near the relevant selection threshold. They organize such instances by a local mass-accumulation exponent β. The case β = 0 means that the density remains bounded away 1
from zero near that threshold, and includes the uniform distribution. The case β > 0 means that the local probability mass in an interval of length ε is of order εβ+1 , equivalently that the density behaves like distanceβ when a density exists. For connected support and β > 0, their upper bound has a leading polynomial factor T β/(2(β+1)) , and they prove a matching lower bound. They also study distributions with separated support intervals. On each side of the gap, the mass near the endpoint adjacent to the gap may again follow the exponent β. When β = 0, the gap-facing densities are bounded above and away from zero, as in a mixture of two separated uniform distributions. This bounded-density gapped class is also a single-resource special case of the network revenue management model with continuous reward distributions studied by Jiang et al. (2025a). In this regime, Besbes et al. (2024) and Jiang et al. (2025a) give log-squared upper bounds. For β > 0, Besbes et al. (2024) give an upper bound with the same polynomial term as in the connected-support case, but multiplied by an additional logarithmic factor; their lower bound has the polynomial term but lacks this logarithmic factor. Our main results resolve the remaining lower-bound questions for the gapped regimes considered here. First, for the bounded-density gapped case β = 0, we prove an Ω((log T )2 ) lower bound for the simplest such instance: a mixture of two separated uniform distributions. The lower bound holds at the critical capacity kT = ⌊qT ⌋, where q is the probability mass of the upper support. Therefore the log-squared upper bound is tight already in the single-resource multi-secretary problem, and consequently the log-squared bound of Jiang et al. (2025a) for bounded-density continuous-reward network revenue management cannot in general be improved. Second, for gapped distributions with β > 0, we prove a lower bound with the additional logarithmic factor appearing in the upper bound of Besbes et al. (2024). This positive-β gapped lower bound is proved for √ capacities shifted from the critical capacity: kT is of the form qT plus a fixed positive multiple of T log T , where qT is the expected number of observations from the upper support. Unlike the two-uniform bounded-density case, where the sharp lower bound is obtained at ⌊qT ⌋, the positive-β gapped theorem is stated for this moderate-deviation shifted-capacity region. Table 1 summarizes the known results and the new lower bounds. For compactness, the table writes Rβ (T ) := T β/(2(β+1)) ,
Gβ (T ) := Rβ (T )(log T )(β+2)/(2(β+1)) .
Table 1: Known and new lower bounds in the four distributional regimes. Case
Known upper bound
Known lower bound
New lower bound
No gap, β = 0
O(log T ) (Bray 2024)
–
Gap, β = 0
O((log T )2 ) (Besbes et al. 2024, Jiang et al. 2025a) O(Rβ (T )) (Besbes et al. 2024) O(Gβ (T )) (Besbes et al. 2024)
Ω(log T ) (Lueker 1998, Bray 2024) Ω(log T ) (Lueker 1998, Bray 2024) Ω(Rβ (T )) (Besbes et al. 2024) Ω(Rβ (T )) (Besbes et al. 2024)
No gap, β > 0 Gap, β > 0
1.1
Ω((log T )2 ), Theorem 4.8 – Ω(Gβ (T )), Theorem D.10 (Appendix D)
Lower bounds by Bellman certificates
We prove these tight lower bounds by a unified Bellman-certificate method. Besbes et al. (2024) prove their lower bounds through direct hard-instance constructions and indistinguishability arguments over arbitrary candidate online policies. Our method is structurally different: we do not analyze any specific online policy, but instead construct explicit Bellman certificates, feasible solutions to relaxations of the exact Bellman recursion for for the gap between the offline benchmark and the optimal online value. 2
The online multi-secretary problem has a standard dynamic-programming formulation. The offline prophet benchmark also admits a recursion based on order statistics: after separating one current observation from the future observations, the current observation improves the offline top-c sum exactly when it exceeds the future marginal order statistic. Subtracting the online and offline recursions yields a Bellman equation for the prophet-online regret. We denote a candidate regret certificate by B = (Bs (c)), where s is the number of remaining observations and c is the remaining capacity. The target capacity is typically close to qs, where q is the probability mass of the upper support in the gapped model. In the gapped two-uniform case, q is the probability mass of the upper support, so qs is the expected number of future observations from that upper support. Let Hs,c be the c-th largest value among those s − 1 future observations. Let τs (c) = EHs,c and let Ds (c) = Bs−1 (c) − Bs−1 (c − 1) be the one-step capacity first difference of the certificate. The Bellman residual can be written as (1 − q)Bs−1 (c) + qBs−1 (c − 1) − Bs (c) + {E∆(Hs,c ) − ∆(τs (c))} + {∆(τs (c)) − ∆(τs (c) − Ds (c))} ≥ 0. | {z } | {z } {z } | Ms (c): deterministic drift term
order-statistic Jensen term
finite-difference perturbation
(1) Here ∆ is the convex residual; its curvature depends on the local shape of the distribution F . When F has density bounded away from zero near the operating threshold, ∆ is strongly convex locally. When F has a support gap, ∆ is flat on the empty interval. The optimal prophet-online regret satisfies the corresponding Bellman equation with equality. We prove that, in order to derive a regret lower bound, it is enough to construct a nonnegative candidate B satisfying the boundary and base conditions, together with the one-sided Bellman certificate inequality (1) for all states in the finite-horizon grid, with the boundary cases c = 0 and c ≥ s treated by the imposed zero boundary values. The resulting comparison principle is the main lower-bound tool. The certificate construction has the following interpretation. A candidate lower bound can be made large at the target state, where c is close to qs, only if it can be propagated through the Bellman inequality at every nearby state. The term Ms (c) measures the resulting drift cost: it records how much the proposed certificate decreases, after the natural affine transport of capacity, when one moves from time s − 1 to time s. A taller certificate creates a larger drift burden, governed by how quickly the profile changes across both capacity and time. Feasibility requires this cost to be paid for by the remaining terms in (1). The first remaining term is the order-statistic Jense term. It is independent of the certificate B and depends only on the distribution of the prophet’s offline marginal item (Hs,c ) and on the shape of ∆. The final term is the finite-difference perturbation. It depends on the spatial first difference Ds (c) of the certificate and can be negative. Thus, in constructing a certificate, one must balance three effects: deterministic drift, positive order-statistic slack, and possible loss from the finite difference. This decomposition isolates the support-gap mechanism. The operating threshold lies in the empty interval between two support components. In the moderate band where c − qs is of order √ s log s, the certificate is constructed so that both the mean prophet threshold τs (c) and the shifted threshold τs (c) − Ds (c) remain inside this empty interval. Consequently the finite-difference perturbation in (1) is zero there. Randomness still matters, however: on sample paths with slightly too many or slightly too few observations from the upper support, the prophet’s marginal item can fall near one of the two support boundaries adjacent to the gap. At those boundaries ∆ starts to bend, and the order-statistic Jensen term is positive. The support gap therefore separates where slack is generated from where the certificate is transported. Fluctuations of the offline marginal into the support edges generate positive slack, while the flat gap suppresses the local finite-difference 3
penalty. This separation permits a larger feasible certificate and yields the order (log T )2 lower bound at kT = ⌊qT ⌋ for the two-uniform bounded-density gapped case.
1.2
Additional related literature
The multi-secretary problem is a single-resource special case of broader online resource allocation, network revenue management, and online linear programming models; see Balseiro et al. (2024). Classical fluid and deterministic-linear-program approaches to network revenue management date back at least to Gallego and van Ryzin (1994) and Talluri √ and van Ryzin (1998), and static fluid or bid-price controls generally incur regret of order O( T ); much of the subsequent literature asks when this baseline can be improved. When rewards and resource consumptions have finite support, Jasin and Kumar (2012) show that resolving the fluid relaxation obtains constant regret under standard nondegeneracy assumptions. Recent works obtain constant regret without the standard nondegeneracy assumption, including Arlotto and Gurvich (2019), Bumpensanti and Wang (2020), Vera and Banerjee (2021), Vera et al. (2021), Freund and Zhao (2022), and Banerjee and Freund (2024). These algorithms typically require repeatedly resolving the fluid relaxation, with the number of resolves ranging from O(T ) to O(log log T ). More recently, Gupta (2024) and He et al. (2025) present algorithms that solve the fluid relaxation only once; they prove constant-regret bounds under conditions equivalent to existing nondegeneracy assumptions. Several recent papers present constant-regret algorithms without assuming known probability distributions; see (Chen et al. 2024, Wei et al. 2023, Xie et al. 2025) for nondegenerate problems and Li et al. (2024) for degenerate problems. When rewards or consumptions are continuously distributed, constant regret is generally no longer attainable. For online linear programming √ with continuous valuations, Gao et al. (2025) show that first-order algorithms can achieve o( T ) regret. Li and Ye (2022) prove polylogarithmic regret under local strong-convexity and smoothness conditions, and Bray (2024) sharpens this to a tight logarithmic bound with a different set of assumptions. Jiang and Zhang (2020) extend the result of Arlotto and Xie (2020) to obtain logarithmic regret under regularity conditions. Chen and Wang (2025) study general continuous reward distributions without the standard primal-stability, strict-complementarity, or second-order growth assumptions, though their conditions still imply uniqueness of the fluid dual. Most directly related to our work, Jiang et al. (2025a) study network revenue management with finitely many resource-consumption vectors but continuous, bounded-density reward distributions, obtaining O((log T )2 ) regret without any additional assumptions. Their model contains our boundeddensity gapped multi-secretary instances as a single-resource special case, and our lower bound shows the log-squared rate is already tight there. Relative to these works, our contribution is a lower-bound method for additive regret. The Bellman-certificate framework turns the lower-bound problem into the construction of explicit feasible solutions to relaxations of the exact Bellman recursion. This Bellman-inequality structure is closest in spirit to Vera et al. (2021), who use Bellman inequalities to prove constant-regret guarantees for tractable online allocation and pricing policies. Their inequalities certify that a particular online policy is close to the offline benchmark, yielding an upper bound on regret. Here the certificate has the opposite role: the certificates are feasible solutions to relaxations of the exact Bellman recursion, and the comparison principle converts them into lower bounds on the gap incurred by every online policy. The same framework applies to bounded-density support gaps and gap-facing vanishing densities. The paper is also related to the prophet-inequality literature, which studies multiplicative competitive ratios. Classical single-unit prophet inequalities compare an online stopping rule with 4
the maximum realized value; see Hill and Kertz (1982), Samuel-Cahn (1984), and Correa et al. (2017). A large subsequent literature studies prophet inequalities under cardinality, matroid, and other feasibility constraints; see Chawla et al. (2010), Alaei (2014), Jiang et al. (2024), and Jiang et al. (2025b), and the survey of Correa et al. (2019).
1.3
Organization
Section 2 defines the model, the gapped support structure, and the affine-reference residual function. Section 3 formulates the Bellman-certificate optimization problem and proves the comparison principle. Section 4 proves the two-uniform bounded-density lower bound using the certificate in (22), with the moderate-scale finite-difference expansions deferred to Appendix E. Appendices A–C collect the reusable binomial, order-statistic, and finite-difference estimates. Appendix D proves the gapped vanishing-density lower bound for β > 0 using the framework of Section 3.
2
Model setup
This section introduce the basic model and the gapped distributional structure used in the main body of the paper. The main text focuses on bounded-density gapped distributions, with the two-uniform mixture as the sharp lower-bound instance. Gapped distributions whose gap-facing densities vanish, as in Besbes et al. (2024), are treated in Appendix D. Let V1 , V2 , . . . be i.i.d. draws from a distribution F on [0, ∞). Throughout the paper F is atomless and has compact support. The compactness assumption is used only to avoid irrelevant integrability issues and to keep all value functions finite. A policy with horizon T and capacity k observes Vt before deciding whether to accept it. Formally, a policy is a sequence At ∈ {0, 1} such PTthat At is measurable with respect to the history generated by (V1 , . . . , Vt , A1 , . . . , At−1 ), and t=1 At ≤ k almost surely. The online reward is P ALGπT (k) := Tt=1 At Vt . The offline prophet reward is the sum of the largest k realized values, Pk ↓ ↓ ↓ OPTT (k) := i=1 Vi:T , where V1:T ≥ · · · ≥ VT :T are the descending order statistics, and the convention is that the sum is over i ≤ min{k, T }. Since the support is nonnegative, the at-most-k offline benchmark agrees with the sum of the largest k observations. In this paper, we focus on the gapped model, i.e., F has two separated support intervals I− := [a1 , b1 ] and I+ := [a2 , b2 ], where 0 ≤ a1 < b1 < a2 < b2 , with gap width G := a2 − b1 > 0. The distribution is a mixture F = pF− + qF+ , where p := 1 − q, F− is supported on I− , and F+ is supported on I+ . Equivalently, q = P(V ∈ I+ ) is the upper-support mass. The main body focuses on bounded-density gapped distributions, and the lower bound is proved for the two-uniform mixture, where F− and F+ are uniform on their respective support intervals. The vanishing-density case, where the gap-facing mass grows at a higher-order power, is discussed in the appendix. P Pmin{c,s} ↓ For s ≥ 0 and integer c, let Js (c) := supπ E[ st=1 At Vt ] and Φs (c) := E[ i=1 Vi:s ] be the optimal online and expected prophet values, respectively, with s periods remaining and capacity c. We use the boundary convention Js (0) = Φs (0) = 0,
Js (c) = Φs (c) = sEV
The prophet-online gap is Bs⋆ (c) := Φs (c) − Js (c). The optimal additive regret for horizon T and capacity k is Regret(T, k; F ) := BT⋆ (k). 5
for c ≥ s.
(2)
Throughout the paper, constants denoted by c, C, C1 , . . . may depend on the fixed distributional primitives, on q, and on fixed parameters in the constructed certificates, but never on s, T, c, k. Constants in the appendix may also depend on the local edge exponent introduced there. We write As ≲ Bs if As ≤ CBs for a constant C < ∞, and As ≍ Bs if both As ≲ Bs and Bs ≲ As . All statements involving “sufficiently large” s or T are uniform over the state ranges explicitly specified in the corresponding lemma.
3
Common Bellman-certificate framework
This section contains the dynamic-programming identities and the comparison principle used in all lower-bound constructions. The arguments are independent of the particular certificate constructed later.
3.1
Online and offline dynamic recursions
We first present the Bellman recursion for the online problem. The boundary conditions are those in (2). Define the tail-integral function Z ∞ + h(τ ) := E[(V − τ ) ] = (1 − F (v)) dv. τ
This function will be used throughout the paper. Since F is atomless, h is continuously differentiable and h′ (τ ) = −(1 − F (τ )) = F (τ ) − 1. In particular, h is convex because h′ is nondecreasing. The following result is well-known in the literature. We include a proof for completeness. Proposition 3.1 (Online Bellman recursion). For s ≥ 1 and 1 ≤ c < s, Js (c) = Js−1 (c) + h(Js−1 (c) − Js−1 (c − 1)) .
(3)
The optimal online action at state (s, c) is a threshold rule: accept the current value V if and only if V ≥ Js−1 (c) − Js−1 (c − 1).
(4)
Proof. At state (s, c), after observing V , rejection yields continuation value Js−1 (c), while acceptance yields V + Js−1 (c − 1). Therefore Js (c) = E max{Js−1 (c), V + Js−1 (c − 1)}. Using max{a, V + b} = a + (V − (a − b))+ with a = Js−1 (c), b = Js−1 (c − 1), and the definition of h gives (3). The same maximization gives the threshold rule (4). The state space is finite for each horizon, so the dynamic program attains the optimum. For the prophet recursion we separate one observation, called the current observation, from the remaining s − 1 future observations. Let Hs,c be the c-th largest value among those s − 1 future observations for s ≥ 2 and 1 ≤ c < s. We also refer to Hs,c as the offline marginal. Equivalently, if Sr denotes the sum of the largest r among the future observations, with S0 = 0, then Hs,c = Sc − Sc−1 . Since F is atomless, ties occur with probability zero; we use the standard order-statistic convention. For s ≥ 2 and 1 ≤ c < s, define τs (c) := Φs−1 (c) − Φs−1 (c − 1).
6
Proposition 3.2 (Offline marginal and prophet recursion). It holds that τs (c) = EHs,c
and
Φs (c) = Φs−1 (c) + Eh(Hs,c ).
(5)
Proof. The first equality follows from Hs,c = Sc − Sc−1 : by definition ESc = Φs−1 (c) and ESc−1 = Φs−1 (c − 1), hence EHs,c = E(Sc − Sc−1 ) = Φs−1 (c) − Φs−1 (c − 1). Now add an independent current observation V to the future multiset. The sum of the top c values among all s observations is Sc + (V − Hs,c )+ . The current value improves the previous top-c block exactly when it exceeds the smallest value in that block, namely Hs,c ; the improvement is then V − Hs,c . Taking expectations and conditioning on Hs,c gives Φs (c) = ESc + E[(V − Hs,c )+ ] = Φs−1 (c) + Eh(Hs,c ), which proves the second equality of (5). For any s ≥ 2 and 1 ≤ c < s, define the prophet’s one-step slack by δs (c) := Φs (c) − Φs−1 (c) − h τs (c) . On the gap [b1 , a2 ] we have F (τ ) = p, hence h′ (τ ) = F (τ ) − 1 = −q for τ ∈ (b1 , a2 ). Thus h is affine on the gap. Let h0 denote its affine continuation from the gap to all of R: h0 (τ ) := h(b1 ) − q(τ − b1 ). Thus h0 (τ ′ ) − h0 (τ ) = −q(τ ′ − τ ),
τ, τ ′ ∈ R.
(6)
Define ∆(τ ) := h(τ ) − h0 (τ ).
(7)
Then ∆(τ ) = 0 for τ ∈ [b1 , a2 ]. Since h is convex and h0 is affine, ∆ is convex. Moreover, h0 agrees with a supporting affine segment of h on the gap, so ∆ is nonnegative on the support interval. Lemma 3.3 (Offline slack identity). For s ≥ 2 and 1 ≤ c < s, δs (c) = E∆(Hs,c ) − ∆ τs (c) ≥ 0.
(8)
Proof. By Proposition 3.2, δs (c) = Eh(Hs,c ) − h(EHs,c ). Write h = h0 + ∆. Since h0 is affine, Eh0 (Hs,c ) = h0 (EHs,c ). The affine contribution therefore cancels, leaving (8). Since ∆ is convex, Jensen’s inequality gives E∆(Hs,c ) ≥ ∆(EHs,c ) = ∆(τs (c)).
7
3.2
Bellman certificate
For any candidate function B = (Bs (c)), s ≥ 2, and 1 ≤ c < s, define the one-step difference Ds (c), affine transport drift Ms (c), and support-source term Ss (c, D) by Ds (c) := Bs−1 (c) − Bs−1 (c − 1),
(9)
Ms (c) := (1 − q)Bs−1 (c) + qBs−1 (c − 1) − Bs (c), Ss (c, D) := E∆(Hs,c ) − ∆ τs (c) − D .
(10) (11)
By Lemma 3.3, Ss (c, 0) = δs (c). With this notation, we now formulate a finite-dimensional optimization problem whose feasible solutions provide certified lower bounds on the prophet-online regret. Such feasible solutions are called Bellman certificates. Fix a horizon T , a target capacity k ∈ {0, . . . , T }, and a base time s0 ≥ 2. Consider the following maximization problem: maximizeB BT (k) subject to
Bs (c) ≥ 0,
s0 ≤ s ≤ T, 0 ≤ c ≤ min{s, k},
Bs (c) = 0,
s0 ≤ s ≤ T,
Bs0 (c) ≤ Bs⋆0 (c),
c = 0 or c = s ≤ k,
(P(T, k, s0 ))
0 ≤ c ≤ min{s0 , k},
Ms (c) + Ss (c, Ds (c)) ≥ 0,
s0 < s ≤ T,
1 ≤ c ≤ min{s − 1, k},
where Ds , Ms , and Ss are defined by (9)–(11). We call the final constraint the Bellman certificate inequality; in pointwise form it is Ms (c) + Ss (c, Ds (c)) ≥ 0.
(13)
A collection B satisfying all constraints in (P(T, k, s0 )) is called a feasible Bellman certificate on [s0 , T ]: it is a feasible solution to a relaxation of the exact Bellman recursion. The program (P(T, k, s0 )) is not an algorithm for computing the regret. Its role is dual: any feasible value is a certified regret lower bound. The next proposition gives the exact Bellman-residual equation for the true gap and the resulting comparison principle. It also shows that the optimal value of (P(T, k, s0 )) is exactly the true regret gap, because B ⋆ itself is feasible with equality in the Bellman certificate constraints. Proposition 3.4 (Comparison principle). Every feasible solution of (P(T, k, s0 )) satisfies BT (k) ≤ Regret(T, k; F ).
(14)
The optimal value of (P(T, k, s0 )) is BT⋆ (k). Proof. We first record the exact residual identity satisfied by B ⋆ : Ms⋆ (c) + Ss c, Ds⋆ (c) = 0. Using the online recursion (3), the prophet recursion (5), and the definition of δs (c), Bs⋆ (c) = Φs (c) − Js (c) = Φs−1 (c) + h(τs (c)) + δs (c) − Js−1 (c) − h(Js−1 (c) − Js−1 (c − 1)) . ⋆ , we have Since Js−1 = Φs−1 − Bs−1
Js−1 (c) − Js−1 (c − 1) = τs (c) − Ds⋆ (c). 8
(15)
Thus ⋆ Bs⋆ (c) = Bs−1 (c) + δs (c) + h(τs (c)) − h τs (c) − Ds⋆ (c) .
(16)
By (6), for any τ and D, h(τ ) − h(τ − D) = −qD + ∆(τ ) − ∆(τ − D).
(17)
Combining (16), (17), and (8) gives ⋆ Bs⋆ (c) = Bs−1 (c) − qDs⋆ (c) + E∆(Hs,c ) − ∆ τs (c) − Ds⋆ (c) ⋆ ⋆ = (1 − q)Bs−1 (c) + qBs−1 (c − 1) + Ss c, Ds⋆ (c) . Rearranging gives (15). We next prove the comparison inequality by induction on s. The base case s = s0 is the base constraint in (P(T, k, s0 )). The boundary states c = 0 and c ≥ s are immediate because both the online and prophet values agree there, and the program imposes the same zero boundary values on B. ⋆ (·). Let 1 ≤ c < s, and define, for real x, y, Fix s > s0 and assume Bs−1 (·) ≤ Bs−1 Ψs,c (x, y) := (1 − q)x + qy + Ss (c, x − y). By (15), ⋆ ⋆ Bs⋆ (c) = Ψs,c Bs−1 (c), Bs−1 (c − 1) . The Bellman certificate constraint in (P(T, k, s0 )) is exactly Bs (c) ≤ Ψs,c Bs−1 (c), Bs−1 (c − 1) . It remains to use monotonicity. Set τ := τs (c) and δ := δs (c). The map Ψs,c admits the representation Ψs,c (x, y) = Φs (c) − E max {Φs−1 (c) − x, V + Φs−1 (c − 1) − y} .
(18)
Apply E max{A, V + B} = A + h(A − B) with A = Φs−1 (c) − x and B = Φs−1 (c − 1) − y, and use Φs (c) = Φs−1 (c) + h(τ ) + δ. Increasing either x or y decreases one argument of the maximum in (18); hence Ψs,c is nondecreasing in each coordinate. Therefore ⋆ ⋆ Bs (c) ≤ Ψs,c Bs−1 (c), Bs−1 (c − 1) ≤ Ψs,c Bs−1 (c), Bs−1 (c − 1) = Bs⋆ (c), where the middle inequality uses the induction hypothesis. Inequality (14) follows from BT⋆ (k) = Regret(T, k; F ). Finally, B ⋆ itself is feasible: nonnegativity follows because the prophet dominates any online policy, the boundary and base constraints hold with equality, and the Bellman certificate constraints hold with equality by (15). Hence the objective value BT⋆ (k) is attainable in (P(T, k, s0 )). Together with the comparison part, this proves that the program value is exactly BT⋆ (k).
3.3
The finite base condition
The explicit certificates used later are asymptotic constructions valid for all sufficiently large s. The comparison principle starts at a finite base time s0 , so we need a simple way to verify the base condition after fixing s0 . Lemma 3.5 (Strict finite-time prophet advantage). Assume F is atomless and nondegenerate. Then, for every s ≥ 2 and every 1 ≤ c < s, it holds that Bs⋆ (c) > 0. 9
Proof. Let π be any nonanticipating policy with capacity c, and let s c X X ↓ ALGπ := At V t , OPT := Vi:s . t=1
i=1 π
Pathwise, every feasible online policy satisfies ALG ≤ OPT. It therefore suffices to show that no nonanticipating policy can satisfy ALGπ = OPT almost surely. Suppose, toward a contradiction, that some policy satisfies ALGπ = OPT almost surely. Since F is atomless, the s realized values are almost surely distinct. On this event, the unique subset attaining OPT is the set of the c largest observations. Thus the policy must select exactly this top-c subset almost surely. In particular, A1 = 1{V1 belongs to the top-c observations among V1 , . . . , Vs }
a.s.
(19)
Choose an interval I with positive F -mass such that 0 < inf P(V > v) ≤ sup P(V > v) < 1; v∈I
v∈I
such an interval exists because F is atomless and nondegenerate. Conditional on V1 ∈ I, the future observations remain independent of the first decision and have a positive probability of producing at least c values above V1 , and also a positive probability of producing fewer than c values above V1 . Equivalently, by the regular conditional distribution of V1 , for F -almost every v ∈ I the binomial variable Nv := #{2 ≤ t ≤ s : Vt > v} ∼ Bin(s − 1, P(V > v)) satisfies P(Nv ≥ c) > 0.
P(Nv < c) > 0,
For such v, the event that V1 belongs to the top-c block is exactly {Nv < c}, up to a null tie event. The first decision A1 is measurable with respect to the information available at time one, together with any policy randomization independent of the future; hence, under the regular conditional law given V1 = v, it is independent of Nv . Let a(v) := P(A1 = 1 | V1 = v). If (19) held almost surely, then for F -almost every such v we would have A1 = 1{Nv < c} almost surely under the conditional law. Therefore 0 = P(A1 = 1, Nv ≥ c | V1 = v) = a(v)P(Nv ≥ c), which forces a(v) = 0, and also 0 = P(A1 = 0, Nv < c | V1 = v) = (1 − a(v))P(Nv < c), which forces a(v) = 1. This contradiction proves that every online policy loses to the prophet with positive probability. Since an optimal online policy is attained by Proposition 3.1, the expected gap Bs⋆ (c) is strictly positive. es (c) = η B̄s (c) be a nonnegative Corollary 3.6 (Choosing the base scale). Fix s0 ≥ 2. Let B candidate family depending linearly on a scale parameter η > 0, and suppose B̄s0 (c) < ∞ for every 0 ≤ c ≤ s0 . If the Bellman certificate inequality is verified for all s > s0 whenever 0 < η ≤ η0 , then, es (c) ≤ B ⋆ (c) holds for 0 ≤ c ≤ s0 . after possibly shrinking η ∈ (0, η0 ], the base condition B s0 0 es (0) = B es (s0 ) = B ⋆ (0) = B ⋆ (s0 ) = 0 in the constructions Proof. The boundary states satisfy B s0 s0 0 0 below. On the finite set of interior states, Lemma 3.5 gives m0 := min Bs⋆0 (c) > 0. 1≤c<s0
Let K0 := max1≤c<s0 B̄s0 (c) < ∞. If K0 = 0 there is nothing to prove; otherwise choose η ≤ m0 /K0 , in addition to η ≤ η0 . 10
4
Mixture of Two Uniform Distributions
This section treats the bounded-density case in the gapped model, which corresponds to the case β = 0 in the more general distribution introduced in Appendix B. We focus on the two-uniform mixture, which gives the sharp bounded-density lower bound. Throughout this section we assume F− = Unif[a1 , b1 ],
F+ = Unif[a2 , b2 ].
(20)
Denote L− := b1 − a1 and L+ := b2 − a2 . We now prove the main lower bound of the paper: the bounded-density gapped case has regret of order (log T )2 . √ The proof builds a certificate on the moderate-deviation scale s log s, with height (log s)2 at the critical capacity. The verification has four regimes, summarized below: the near-critical range, the bounded moderate-deviation range, the large moderate-deviation range, and the outer cutoff range. A direct calculation for the two-uniform mixture gives ∆(τ ) =
p q (τ − a2 )2+ + (b1 − τ )2+ , 2L+ 2L−
τ ∈ [a1 , b2 ].
(21)
This follows by integrating h′ (τ ) + q = F (τ ) − p on the lower and upper support intervals and using ∆ = 0 on [b1 , a2 ].
4.1
Candidate Certificate
In this section, we construct a candidate certificate B as follows. For s ≥ s0 and 1 ≤ c < s, define Bs (c) := η(log s)2 Ω(c/s)φs (zs (c)),
(22)
and set Bs (0) = 0 and Bs (c) = 0 for c ≥ s. Here η, Ω, and φs are constructed below. We choose constants in the following order. First choose 1 0 < α0 < α1 < α2 < α3 < α4 < α5 < . 2
(23)
Choose ρ > 0 such that ρ < min{p/4, q/4}. Choose constants f0 > 0, κ > 8f0 , and φ⋆ > f0 + κα22 . Finally choose λ > 0 so large that 11 1 − λα5 > 3. (24) 16 2 This lower bound on λ is imposed for the large-deviation verification in Proposition 4.7. The small multiplicative parameter η > 0 and the base time s0 are chosen last. Let Ω ∈ C 2 ([0, 1]) be a cutoff satisfying 0 ≤ Ω ≤ 1,
Ω(x) = 1 if |x − q| ≤ ρ,
Ω(x) = 0 if |x − q| ≥ 2ρ.
(25)
Let ψ : R → [0, 1] be a C ∞ transition function such that ψ = 0 on (−∞, 0], ψ = 1 on [1, ∞),
ψ ′ ≥ 0, and all derivatives vanish at 0 and 1. Define ψ1 (z) := ψ
z − α1 α2 − α 1
,
ψ2 (z) := ψ
11
z − α3 α4 − α3
.
Define For all sufficiently large s, define φs : [0, ∞) → (0, ∞) by f0 + κz 2 , 0 ≤ z ≤ α1 , 2 α 1 ≤ z ≤ α2 , (1 − ψ1 (z))(f0 + κz ) + ψ1 (z)φ⋆ , α2 ≤ z ≤ α3 , φs (z) := φ⋆ , (1 − ψ2 (z))φ⋆ + ψ2 (z)Ts (z), α3 ≤ z ≤ α4 , n o α +α λ 3 4 Ts (z) := φ⋆ exp − , z ≥ α4 . log s z − 2
(26)
The flatness of ψ at the joining points makes φs a C 3 function. Lemma 4.1 (Profile bounds). Uniformly in all sufficiently large s, the functions φs defined in (26) satisfy: (j)
(P1) For z ∈ [α1 , α2 ], φ′s (z) ≥ 0 and |φs (z)| ≤ Cλ for j = 1, 2, 3. (j)
s (z) (P2) For z ∈ [α3 , α4 ], φs (z) ≍ φ⋆ and |φs (z)| ≤ Cλ φlog s ,
j = 1, 2, 3.
(P3) For every fixed C0 < ∞, uniformly over α3 ≤ z ≤ C0 |φs−1 (z) − φs (z)| ≤ Cλ
p s/(log s),
(1 + z)φs (z) . s(log s)2
(27)
For every fixed R < ∞, uniformly over 0 ≤ z ≤ R and j = 1, 2, (j)
|φs−1 (z) − φ(j) s (z)| ≤ Proof. On [α1 , α2 ],
Cλ,R . s(log s)2
(28)
φ′s (z) = ψ1′ (z) φ⋆ − f0 − κz 2 + (1 − ψ1 (z))2κz.
Since φ⋆ > f0 + κα22 , both terms are nonnegative; the derivative bounds on this fixed compact interval are immediate. On [α3 , α4 ], the exponent in Ts is Oλ (1/ log s), so Ts = φ⋆ (1 + Oλ (1/ log s)). More explicitly, Ts − φ⋆ = Oλ (φ⋆ / log s),
Ts(m) = (−λ/ log s)m Ts ,
m ≥ 1.
Because φs = φ⋆ + ψ2 (Ts − φ⋆ )
(α3 ≤ z ≤ α4 ),
the first two derivatives are φ′s = ψ2′ (Ts − φ⋆ ) + ψ2 Ts′ , φ′′s = ψ2′′ (Ts − φ⋆ ) + 2ψ2′ Ts′ + ψ2 Ts′′ . Each displayed term is Oλ (φ⋆ / log s), and φs ≍ φ⋆ on [α3 , α4 ]. The third derivative is identical in form, with one more product-rule term, and is also Oλ (φs / log s). This proves (P2). It remains to prove the time-variation bounds. On [0, α3 ], the construction is independent of s. On [α3 , ∞), view φs (z) as F (z, u) evaluated at u = 1/ log s. On z ≥ α4 , α3 + α4 ∂u F (z, u) = −λ z − F (z, u), 2 12
and on [α3 , α4 ] the same expression is multiplied by the fixed cutoff ψ2 (z). Thus, uniformly for z ≥ α3 , |∂u F (z, u)| ≤ Cλ (1 + z)F (z, u). Moreover, 1 1 1 − = +O log(s − 1) log s s(log s)2
1 s(log s)3
.
p For z ≤ C0 s/(log s) and u between 1/ log s and 1/ log(s − 1), the ratio F (z, u)/F (z, 1/ log s) is bounded by a constant depending only on C0 and λ, because u−
1 1+z = o(1). (1 + z) ≤ C log s s(log s)2
The mean-value theorem therefore gives (27). For the derivative bounds on bounded intervals, differentiate F first. For instance, on z ≥ α4 , α3 + α4 2 F, ∂u ∂z F = −λF + λ u z − 2 and similarly |∂u ∂z2 F | ≤ Cλ,R F on z ≤ R. The interval [α3 , α4 ] has only additional fixed cutoff factors. Applying the mean-value theorem to ∂z F and ∂z2 F gives (28). In order to verify the feasibility of the constructed function B, notice that Bellman certificate inequality (13) is equivalent to (1 − q)Bs−1 (c) + qBs−1 (c − 1) − Bs (c) + {E∆(Hs,c ) − ∆(τs (c))} + {∆(τs (c)) − ∆(τs (c) − Ds (c))} ≥ 0. | {z } | {z } {z } | Ms (c): deterministic drift
Jensen/order-statistic source
finite-difference perturbation
We decompose the Bellman residual into three contributions: the deterministic drift, the Jensen/orderstatistic slack, and the finite-difference perturbation. In the verification, the drift Ms (c) is bounded separately. The remaining two contributions are controlled either separately, when the perturbation is zero or negligible, or together through Ss (c, D) := E∆(Hs,c ) − ∆(τs (c) − D), when the perturbation is comparable to the Jensen/order-statistic slack. Recall that Ds (c) := Bs−1 (c) − Bs−1 (c − 1). Although the constructed certificates are verified on a broad state space, the most interesting cases are when c is close to critical capacity qs, where q is the upper-support mass introduced earlier. Write σ 2 := q(1−q). For any (s, c), define the centered capacity imbalance and its standard-deviation normalization by ds (c) ds (c) := c − qs, xs (c) := √ . (29) σ s The proofs also use the moderate-deviation coordinate |ds (c)| |xs (c)| zs (c) := √ =√ . σ s log s log s We begin with bounding Ms (c), the deterministic drift in the next subsection.
13
(30)
4.2
Deterministic finite differences
The following lemma bounds Ms (c) and Ds (c) in four regions, using the moderate-deviation coordinate zs (c). Lemma 4.2 (Bounded-density finite differences). After increasing s0 if necessary, the following estimates hold for all s > s0 and all 1 ≤ c < s. (D1) If zs (c) ≤ α0 and |c/s − q| ≤ ρ/2, then Ms (c) ≥ 0,
|Ds (c)| ≤ Cη
(log s)3/2 √ . s
(31)
(D2) If α0 ≤ zs (c) ≤ α5 and |c/s − q| ≤ ρ/2, then Ms (c) ≥ −Cλ η
log s , s
|Ds (c)| ≤ Cλ η
(log s)3/2 √ . s
(32)
(D3) If zp s (c) ≥ α5 and |c/s − q| ≤ ρ/2, then ds (c)Ds (c) < 0. Moreover, uniformly for α5 ≤ zs (c) ≤ Cρ s/(log s), which is the range implied by |c/s − q| ≤ ρ/2, r log s ηλ |Ds (c)| = (1 + o(1)) φs (zs (c)) , (33) σ s λzs (c) log s Ms (c) = −ηφs (zs (c)) 2 + + rs (zs (c)) . (34) 2 s Here the remainder satisfies |rs (z)| −→ 0. 1 + λz s/(log s)
sup √
α5 ≤z≤Cρ
(D4) If |c/s − q| ≥ ρ/2 and at least one of Bs (c), Bs−1 (c), Bs−1 (c − 1) is nonzero, then |Ms (c)| + |Ds (c)| = o(1/s).
(35)
Proof. When |c/s − q| ≤ ρ/2, the cutoff factors in Bs (c), Bs−1 (c), and Bs−1 (c − 1) are all equal to one for large s. Write d = ds (c). The predecessor deviations are ds−1 (c) = d + q,
ds−1 (c − 1) = d − (1 − q).
Whenever |d| → ∞ and the two predecessor deviations have the same sign as d, let ξ be the two-point random variable taking values q sgn(d) with probability 1 − q and −(1 − q) sgn(d) with probability q. Then Eξ = 0 and Eξ 2 = σ 2 . With this notation, Lemma E.2 gives the useful identity Ms (c) = η (log(s − 1))2 Eφs−1 (Zs ) − (log s)2 φs (z) , z = zs (c), (36) where Zs = √ σ
|d|+ξ . On the same sign-stable range, (s−1) log(s−1)
Ds (c) = η(log(s − 1))2 [φs−1 (zs−1 (c)) − φs−1 (zs−1 (c − 1))] .
14
(37)
The range zs (c) ≤ α0 is the only near-critical range where d may be bounded; there we use the quadratic formula directly instead of (36). Regime 1. If zs (c) ≤ α0 , then for large s both predecessor coordinates lie in the interval [0, α1 ]. Therefore (d + q)2 φs−1 (zs−1 (c)) = f0 + κ 2 , σ (s − 1) log(s − 1) φs−1 (zs−1 (c − 1)) = f0 + κ
(d − (1 − q))2 . σ 2 (s − 1) log(s − 1)
Using (1 − q)(d + q)2 + q(d − (1 − q))2 = d2 + σ 2 , we obtain
(38)
Ms (c) = ηf0 ((log(s − 1))2 − (log s)2 ) d2 + σ 2 d2 2 2 + ηκ (log(s − 1)) 2 . − (log s) 2 σ (s − 1) log(s − 1) σ s log s
Since the square of the moderate-deviation normalizer is σ 2 s log s, this becomes d2 + σ 2 d2 2 2 Ms (c) = ηf0 ((log(s − 1)) − (log s) ) + ηκ log(s − 1) 2 − log s 2 . σ (s − 1) σ s The d2 part is d2 σ2
log(s − 1) log s − s−1 s
.
It is nonnegative for large s because x 7→ (log x)/x is decreasing on (e, ∞), so log(s − 1) log s ≥ . s−1 s The remaining positive contribution from the σ 2 term is ηκ
log(s − 1) log s ≥ ηκ s−1 2s
for all large s. Finally, 2 log s +O (log(s − 1)) − (log s) = − s 2
2
log s s2
,
so the negative part contributed by the constant term f0 is at most 3ηf0 log s/s for large s. Therefore log s κ Ms (c) ≥ η −3f0 + ≥0 s 2 for large s, because κ > 8f0 . The bound on Ds (c) follows from the mean-value theorem and the global Lipschitz estimate (log s)2 (log s)3/2 |∂c Bs−1 (c)| ≤ Cη √ = Cη √ . s σ s log s
(39)
The estimate (39) follows by differentiating (log(s − 1))2 Ω(c/(s − 1))φs−1 (zs−1 (c)). The cutoff √ derivative contributes O(η(log s)2 /s), while the profile derivative contributes O(η(log s)2 /(σ s log s)), which dominates. 15
Regime 2. Suppose α0 ≤ zs (c) ≤ α5 . Then the predecessor deviations have the same sign as d for large s, and with the above definition of ξ, ! |d| + ξ p . (1 − q)φs−1 (zs−1 (c)) + qφs−1 (zs−1 (c − 1)) = Eφs−1 σ (s − 1) log(s − 1) Let z = zs (c). The random argument has expansion |d| + ξ ξ z p =z+ √ + +O 2s σ s log s σ (s − 1) log(s − 1)
1+z s log s
,
so its first two centered moments around z are 1 z 1+z 1 + z2 1+z . , E(Z − z)2 = E(Z − z) = +O +O + 2s s log s s log s s2 (s log s)3/2 Decompose the drift using (36): Ms (c)/η = (log(s − 1))2 E[φs−1 (Zs ) − φs−1 (z)] | {z } coordinate transport
+ (log(s − 1))2 φs−1 (z) − (log s)2 φs (z) . | {z }
(40)
height/time change
The second term in (40) is (log(s − 1))2 φs−1 (z) − (log s)2 φs (z) = ((log(s − 1))2 − (log s)2 )φs (z) + (log(s − 1))2 (φs−1 (z) − φs (z)) log s 1 = −2φs (z) + Oλ . s s Here the first equality is exact, the scalar expansion (log(s − 1))2 − (log s)2 = −2 log s/s + O(log s/s2 ) gives the main term. Up to α3 the profile is independent of s, while on [α3 , α5 ] the time-variation estimate (27) contributes only Oλ (1/s) on this bounded range. The coordinate-transport term is the Taylor increment recorded in Appendix Lemma E.4. Combining the two terms gives (log s)2 z ′ log s 1 ′′ log s φ (z) + η φ (z) − 2φs (z) + Oλ η . Ms (c) = η s 2 s s 2 s s On [α0 , α3 ] one has φ′s (z) ≥ 0, so the first term is nonnegative. On [α3 , α5 ], the derivative bounds from Lemma 4.1 and the exponential formula in (26) give |φ′s (z)| ≤ Cλ / log s, so the first term is bounded below by −Cλ η log s/s. The remaining terms are also bounded below by −Cλ η log s/s. This proves the drift bound in (32); the bound on Ds (c) again follows from (39). Regime 3. Suppose zs (c) ≥ α5 . Because α5 > α4 , all relevant predecessor arguments lie in the interval z ≥ α4 for large s. We give the calculation for d < 0; the case d > 0 is identical after reversing signs. When d < 0, |d| − q zs−1 (c) = p , σ (s − 1) log(s − 1)
|d| + 1 − q zs−1 (c − 1) = p . σ (s − 1) log(s − 1)
Thus zs−1 (c) < zs−1 (c − 1). Since φs is decreasing on z ≥ α4 , Bs−1 (c) > Bs−1 (c − 1) and hence Ds (c) > 0. Since d < 0, this proves dDs (c) < 0 in this case. For the magnitude of the first difference, the identity φ′s−1 (w) = −
λ φs−1 (w) log(s − 1) 16
and the mean-value theorem give Ds (c) = η(log(s − 1))2 {φs−1 (zs−1 (c)) − φs−1 (zs−1 (c − 1))} λ 1 = η(log(s − 1))2 φs−1 (e z) p log(s − 1) σ (s − 1) log(s − 1) for some ze√ between the two predecessor coordinates. The two predecessor coordinates differ from z by O(1/(σ s log s)) + O(z/s). Thus, for the intermediate point ze in the mean-value theorem, z 1 . + |e z − z| ≤ C √ s log s s p In the range z ≤ Cρ s/(log s), λ|e z − z| z 1 + = o(1), ≤ Cλ √ log s s(log s)3/2 s log s uniformly. Since the slope on z ≥ α4 is −λ/ log s, this gives φs−1 (e z )/φs (z) = 1 + o(1) uniformly. Therefore r ηλ log s |Ds (c)| = (1 + o(1)) φs (z) , σ s which is (33). For the drift, let Z = √ |d|+ξ with the sign-stable two-point increment from Lemma E.2. σ
(s−1) log(s−1)
Then
Ms (c) (log(s − 1))2 φs−1 (Z) = E − 1. η(log s)2 φs (z) (log s)2 φs (z) Appendix Lemma E.5 gives λz 1+z 1 φs−1 (Z) =1− + Oλ + , E φs (z) 2s log s s(log s)2 s(log s)3 while Lemma E.1 gives (log(s − 1))2 2 =1− +O 2 (log s) s log s
1 2 s log s
.
Multiplying the two displays yields φs−1 (Z) 2 + λz/2 + rs (z) (log(s − 1))2 E −1=− , (log s)2 φs (z) s log s where
|rs (z)| → 0. 1 + λz s/(log s)
sup √
α5 ≤z≤Cρ
Multiplying by η(log s)2 φs (z) proves (34). Regime 4. If |c/s − q| ≥ ρ/2 but some neighboring certificate value is nonzero, then by the support of Ω all relevant ratios are within 2ρ + O(1/s) of q. In particular p zs (c) ≥ cρ s/(log s). The exponential formula in (26) then gives √ φs (zs (c)) ≤ C exp{−c s/(log s)3/2 }, and the same bound holds at neighboring states. Since B and its first differences are polynomial factors times this super-polynomially small quantity, (35) follows. 17
4.3
Source and perturbation estimates
The next estimate controls the Jensen/order-statistic term E∆(Hs,c ) − ∆(τs (c)). It is the bounded-density specialization of the estimate in Appendix B. We record the form used below. The later estimate in this subsection controls the combined term Ss (c, D), where the finite-difference perturbation is included. Lemma 4.3 (Quadratic bounded-density source on the moderate√band). There are constants cI > 0 and sI < ∞ such that, for all s ≥ sI and all c with |xs (c)| ≤ α5 log s + 1, E∆(Hs,c ) ≥ cI
(1 + |xs (c)|)2 . s
(41)
log s . s
(42)
In particular, if zs (c) ≥ α0 , then E∆(Hs,c ) ≥ cI α02
Proof. Apply Lemma B.9 with A = α5 < 1 and L = 1. The two-uniform model has bounded positive densities at the two support edges adjacent √ to the gap, √ and the appendix estimate reduces exactly to (41). If zs (c) ≥ α0 , then |xs (c)| = zs (c) log s ≥ α0 log s, proving (42). The range zs (c) ≥ α5 requires a bound on the combined term Ss (c, D) that uses the sign condition ds (c)D ≤ 0. This is the only such estimate in this section not already contained in the appendix estimates for the vanishing-density case. The following elementary comparison explains the constants used in the large- and small-overshoot alternatives. Lemma 4.4 (Deterministic bounded-density comparisons). Let R, A > 0, 0 ≤ D ≤ RA/8, x ≥ 0, and m2 ≥ 0.99R2 A2 . Then there is an absolute constant cdet > 0 such that: (i) if x ≤ 3RA/4, then m2 − ((x − D)+ )2 ≥ cdet R2 A2 ; (ii) if x > 3RA/4, then x2 − ((x − D)+ )2 ≥ 11 8 RAD. Proof. If x ≤ 3RA/4, then (x − D)+ ≤ x + D ≤ 7RA/8. Hence 2 ! 7 m2 − ((x − D)+ )2 ≥ 0.99 − R 2 A2 , 8 and the parenthetical constant is positive. If x > 3RA/4, then u2+ ≤ u2 gives x2 − ((x − D)+ )2 ≥ x2 − (x − D)2 = 2xD − D2 . Using x > 3RA/4 and D ≤ RA/8 yields 3 1 11 2xD − D2 ≥ RAD − RAD = RAD. 2 8 8
18
Lemma 4.5 (Uniform bounded-density bound for Ss (c, D)). There exist constants K = 11/16 > 1/2, c0 > 0, and ε0 > 0, depending only on the two-uniform distribution and on ρ, with the following property. Fix α > 0. For all sufficiently large s, suppose ασ
p s log s ≤ |ds (c)| ≤ 2ρs,
as (c) :=
|ds (c)| , s
and |D| ≤ ε0 as (c),
ds (c)D ≤ 0.
Define ( (w, R) :=
(τs (c) − a2 )+ , L+ /q , (b1 − τs (c))+ , L− /p ,
ds (c) < 0, ds (c) > 0.
Then, if w > 43 Ras (c), E∆(Hs,c ) − ∆(τs (c) − D) ≥ Kas (c)|D|, while, if w ≤ 34 Ras (c),
E∆(Hs,c ) − ∆(τs (c) − D) ≥ c0 as (c)2 .
Proof. We prove the lemma when ds (c) < 0; the other side is symmetric. Put a := as (c), τ = τs (c), τb = τ − D, X = (Hs,c − a2 )+ , and w = (τ − a2 )+ . We choose ε0 below fixed distributional constants; in particular, G R+ R− , , . ε0 ≤ min 4ρ 8 8 Since D ≥ 0 and |D| ≤ ε0 a ≤ 2ρε0 , this gives D < G/2 throughout the stated range. We first check that τb ∈ [b1 , b2 ] for all large s. The upper bound τb ≤ b2 is immediate from τ ≤ b2 and D ≥ 0. For the lower bound, if τ ≥ a2 , then τb ≥ a2 − D > b1 + G/2. Suppose instead that τ < a2 . Since Hs,c ≥ a2 on {N ≥ c} and Hs,c ≥ a1 always, τ = EHs,c ≥ a2 P(N ≥ c) + a1 P(N < c) = a2 − (a2 − a1 )P(N < c). Because ds (c) < 0 and a = |ds (c)|/s, µs − c = a s − q. For large s, a s → ∞, and hence 1 a s − q + 1 ≥ a s. 2 Bernstein’s inequality for the binomial variable N gives c′ a2 s2 P(N < c) ≤ P{µs − N ≥ a s − q + 1} ≤ exp − B s + as
.
Since a ≤ 2ρ in the stated range, the denominator is at most a constant multiple of s, and therefore p 2 P(N < c) ≤ exp{−cB a2 s} ≤ s−cB α , a ∈ [ασ (log s)/s, 2ρ], where cB > 0 depends only on q and ρ. The constant α is fixed before s → ∞, so the probability is o(1) uniformly over this range; at the lower end of the range it is polynomially small in s, which is sufficient here. Hence τ ≥ a2 − G/4 = b1 + 3G/4 for all large s. Since D < G/2, this gives τb ≥ b1 + G/4. Thus τb ∈ [b1 , b2 ].
19
Using the exact convex-residual formula (21), and because τb ∈ [b1 , b2 ], ∆(b τ) =
2 q (w − D)+ , 2L+
while E∆(Hs,c ) ≥ Therefore E∆(Hs,c ) − ∆(b τ) ≥
(43)
q EX 2 . 2L+
(44)
q EX 2 − ((w − D)+ )2 . 2L+
(45)
We need a lower bound on EX 2 . Conditional on N = n ≥ c, X is the order statistic of rank n − c + 1 among n iid uniform variables on [0, L+ ]. Hence E[X 2 | N = n] = L2+
(n − c + 1)(n − c + 2) . (n + 1)(n + 2)
Because ds (c) < 0 and a = |ds (c)|/s, one has µs − c = a s − q. Fix δ ∈ (0, q/4). Let Gs := N − c ≥ (1 − δ)a s ∩ |N − µs | ≤ δs . The first event in Gs fails only if µs − N > δa s − q. p Since a s → ∞ uniformly over a ∈ [ασ (log s)/s, 2ρ], the right side is at least (δ/2)a s for all large s. Bernstein’s inequality then gives P N − c < (1 − δ)a s ≤ exp{−cB,δ a2 s} = o(1) uniformly over the same range of a. The second event fails with probability at most exp{−cδ s}. Hence P(Gs ) = 1 − o(1) uniformly. On Gs , for all large s, N − c + 1 ≥ (1 − 32 δ)a s,
N − c + 2 ≥ (1 − 32 δ)a s,
N + 1, N + 2 ≤ (q + 2δ)s.
Substituting these deterministic bounds into the conditional second-moment formula gives, on Gs , E[X
2
3 2 2 2 2 (1 − 2 δ) a s | N ] ≥ L+ . 2 2
(q + 2δ) s
Using the tower property and X 2 ≥ 0 on the complement of Gs yields EX 2 = E E[X 2 | N ] ≥ E E[X 2 | N ]1Gs (1 − 32 δ)2 a2 s2 P(Gs ) (q + 2δ)2 s2 (1 − 32 δ)2 2 ≥ L2+ a (1 − o(1)). (q + 2δ)2 ≥ L2+
p This estimate is uniform on a ∈ [ασ (log s)/s, 2ρ]: at the lower end of the range the deviations are 2 only logarithmic, but a2 s ≍ log s still forces P(Gs ) → 1. Since the prefactor tends to (L+ /q)2 = R+ as δ ↓ 0, we may choose δ and then s large enough so that, for any prescribed ε > 0, 2 2 EX 2 ≥ (1 − ε)R+ a .
20
(46)
Take ε = 0.01. By the choice of ε0 , D ≤ R+ a/8. If w ≤ 34 R+ a, apply Lemma 4.4 with R = R+ and m2 = EX 2 . Together with (45), this gives E∆(Hs,c ) − ∆(b τ ) ≥ c0 a2 for a positive constant c0 . If w > 34 R+ a, then w = τ − a2 > 0. The pointwise inequality X = (Hs,c − a2 )+ ≥ Hs,c − a2 holds also on the off-event {N < c}, where X = 0 and Hs,c − a2 < 0. Therefore EX ≥ E(Hs,c − a2 ) = w, and Jensen’s inequality gives EX 2 ≥ w2 . Lemma 4.4, again with R = R+ , gives w2 − ((w − D)+ )2 ≥
11 R+ aD. 8
Substituting into (45) and using qR+ /(2L+ ) = 1/2 yields E∆(Hs,c ) − ∆(b τ) ≥
11 aD. 16
This proves the case ds (c) < 0 with K = 11/16. For the case ds (c) > 0, set Y = (b1 − Hs,c )+ and w = (b1 − τ )+ . Now D ≤ 0, so |D| = −D. The same gap-margin argument shows τb ∈ [a1 , a2 ] for all large s. On this side the exact convex-residual formula gives 2 p p ∆(b τ) = (w − |D|)+ , E∆(Hs,c ) ≥ EY 2 . 2L− 2L− Conditional on N = n < c, the distance Y has the same uniform-order-statistic second-moment formula as above, with L− and p replacing L+ and q and rank c − n. Repeating the preceding 2 a2 , uniformly on the stated range. Applying tower-property argument gives EY 2 ≥ (1 − ε)R− Lemma 4.4 with R = R− and D replaced by |D| proves the stated linear and quadratic alternatives for the case ds (c) > 0. For states outside the central range, the proof uses the prophet Jensen slack rather than the signed first-difference source. Lemma 4.6 (Jensen slack in the outer cutoff range). There are constants κρ > 0 and sρ < ∞ such that, for all s ≥ sρ and all interior c satisfying ρ/2 ≤ |c/s − q| ≤ 2ρ + 1/s, one has δs (c) := E∆(Hs,c ) − ∆(τs (c)) ≥
(47) κρ . s
(48)
Proof. We prove the high-deficit case ρ/2 ≤ q − c/s ≤ 2ρ + 1/s; the other side is symmetric. Let Es := {|N − µs | ≤ (ρ/4)s}. By Bernstein’s inequality, P(Esc ) ≤ e−cρ s . On Es , for large s, N −c≥
ρ s, 8
N ≤ (q + ρ/4)s,
q c ≥ (q − 2ρ)s − 1 ≥ s. 2
Thus Hs,c lies in the upper support on Es , and conditional on N it is a uniform order statistic with rank rN = N − c + 1. The variance formula for uniform order statistics gives Var(Hs,c | N ) = L2+
rN (N − rN + 1) κ1 ≥ 2 (N + 1) (N + 2) s
21
on Es .
On the upper interval, ∆(τ ) = q(τ − a2 )2 /(2L+ ), so the conditional Jensen gap equals E[∆(Hs,c ) | N ] − ∆(E[Hs,c | N ]) =
κ2 q Var(Hs,c | N ) ≥ 2L+ s
on Es . Decomposing the unconditional Jensen gap into the expectation of conditional Jensen gaps plus the Jensen gap of the conditional mean, the second term is nonnegative by convexity. Hence δs (c) ≥
κ2 κ2 P(Es ) ≥ s 2s
for large s.
4.4
Certificate verificatioin
We now verify the Bellman certificate inequality (13) for the certificate (22). Recall that Ss (c, D) = E∆(Hs,c ) − ∆(τs (c) − D). The proof separates four regimes. In the central range zs (c) ≤ α0 , the drift is nonnegative and the perturbation remains inside the gap. For α0 ≤ zs (c) ≤ α5 , the Jensen/order-statistic source dominates the bounded negative drift. For zs (c) ≥ α5 near q, Lemma 4.5 controls the combined term Ss (c, Ds (c)). Outside the central range, the certificate terms are o(1/s) and are dominated by the prophet Jensen slack. Proposition 4.7 (Feasibility of the bounded-density certificate). There exist η0 > 0 and s0 < ∞ such that, for every η ∈ (0, η0 ], the certificate (22) satisfies Ms (c) + Ss (c, Ds (c)) ≥ 0
(49)
for every s > s0 and every interior state 1 ≤ c < s. Proof. We choose η0 small enough for the applications of Lemma 4.5 and for the comparisons below, and then choose s0 large enough so that all asymptotic estimates hold uniformly for η ≤ η0 . Fix such s and c. Regime 1: zs (c) ≤ α0 and |c/s − q| ≤ ρ/2. Lemma 4.2 gives Ms (c) ≥ 0 and |Ds (c)| ≤ √ Cη(log s)3/2 / s. The bounded-density case of the common gap-margin Lemma D.5, used with any A ∈ (α5 , 1), gives 2 dist(τs (c), {b1 , a2 }) ≥ cs−A /2 (log s)−1/2 throughout zs (c) ≤ α5 . Since A < 1, √ (log s)3/2 / s 2 = s−(1−A )/2 (log s)2 → 0. s−A2 /2 (log s)−1/2 Thus τs (c) − Ds (c) lies in the gap for all large s, so ∆(τs (c) − Ds (c)) = 0 and Ss (c, Ds (c)) = E∆(Hs,c ) ≥ 0. Hence (49) holds. Regime 2: α0 ≤ zs (c) ≤ α5 and |c/s−q| ≤ ρ/2. As in Regime 1, the perturbation Ds (c) is smaller than the gap margin, hence Ss (c, Ds (c)) = E∆(Hs,c ). Lemma 4.3 gives Ss (c, Ds (c)) ≥ c1 log s/s, while Lemma 4.2 gives Ms (c) ≥ −Cλ η log s/s. Choosing η0 ≤ c/(2Cλ ) yields (49) in this regime. p Regime 3: zs (c) ≥ α5 and |c/s − q| ≤ ρ/2. Put z = zs (c) and as (c) = |ds (c)|/s = σz log s/s. By Lemma 4.2, ds (c)Ds (c) < 0 and as (c)|Ds (c)| = (1 + o(1))ηλzφs (z) 22
log s . s
We apply Lemma 4.5 with the fixed lower-tail parameter α = α5 . Also, |Ds (c)| ηλφs (z) = (1 + o(1)) ≤ Cηλ, as (c) σ2z because φs is bounded and z ≥ α5 . Reducing η0 ensures |Ds (c)| ≤ ε0 as (c), so Lemma 4.5 applies. In Lemma 4.5, if w > 34 Ras (c), then Ss (c, Ds (c)) ≥ Kas (c)|Ds (c)| with K = 11/16. Combining with (34), log s [(K − 1/2)λz − 2 − rs (z)] . Ms (c) + Ss (c, Ds (c)) ≥ ηφs (z) s By (24), the deterministic part of the bracket satisfies (K − 1/2)λz − 2 ≥ (K − 1/2)λα5 − 2 > 1
(z ≥ α5 ).
The uniform bound on rs (z) in Lemma 4.2 implies that rs (z) = o(1) p on bounded subranges and rs (z) = o(λz) on growing subranges, uniformly over α5 ≤ z ≤ Cρ s/(log s). Therefore the lower bound for Ss (c, Ds (c)) dominates the error for all sufficiently large s, and the bracket is positive uniformly. If w ≤ 34 Ras (c), Lemma 4.5 gives Ss (c, Ds (c)) ≥ c0 as (c)2 = c0 σ 2 z 2
log s . s
On z ≥ α5 , φs (z) is bounded and decreasing. Hence, for z ∈ [α5 , 1], the ratio φs (z)(1 + λz)/z 2 is bounded by a constant depending only on λ, α5 and φ⋆ . For z ≥ 1, 1 + λz ≤ (1 + λ)z 2 , and φs (z) ≤ φs (α5 ) ≤ Cφ⋆ . Therefore, for all z ≥ α5 , φs (z)(1 + λz) ≤ Cλ,α5 z 2 . Using (34), log s log s ≤ C ′ ηz 2 . s s Reducing η0 once more gives (49) in the small-overshoot subcase. Regime 4: |c/s − q| ≥ ρ/2. If all three values Bs (c), Bs−1 (c), and Bs−1 (c − 1) vanish, then Ms (c) = Ds (c) = 0, and −Ms (c) ≤ Cηφs (z)(1 + λz)
Ss (c, 0) = E∆(Hs,c ) − ∆(τs (c)) = δs (c) ≥ 0 by the Jensen-slack identity. If at least one neighboring certificate value is nonzero, then the support of Ω implies |c/s − q| ≤ 2ρ + 1/s for large s, so (47) holds. Lemma 4.2 gives |Ms (c)| + |Ds (c)| = o(1/s), while Lemma 4.6 gives δs (c) ≥ κρ /s. Since h is globally Lipschitz for a compactly supported distribution and h0 is affine, ∆ = h − h0 is globally Lipschitz. Therefore the following comparison is valid even if the o(1/s) perturbation moves τs (c) − Ds (c) slightly outside [a1 , b2 ]: Ss (c, Ds (c)) = δs (c) + ∆(τs (c)) − ∆(τs (c) − Ds (c)) ≥
κρ κρ − C∆ |Ds (c)| = − o(1/s). s s
Together with Ms (c) = o(1/s), this proves (49). The four regimes exhaust all interior states, so the proposition follows.
23
4.5
The lower bound
Theorem 4.8 (Two-uniform mixture). Assume (20). Let kT = ⌊qT ⌋. There is a constant c > 0, depending only on the two-uniform distribution, such that for all sufficiently large T , BT⋆ (kT ) = ΦT (kT ) − JT (kT ) ≥ c(log T )2 .
(50)
Proof. Let η0 and s0 be as in Proposition 4.7. By Corollary 3.6, after possibly reducing η ∈ (0, η0 ], the certificate satisfies the base condition at time s0 . Proposition 4.7 verifies the Bellman certificate inequality for all later times, so B is feasible for P(T, kT , s0 ) for all sufficiently large T . By Proposition 3.4, Regret(T, kT ; F ) ≥ BT (kT ). Now |kT − qT | ≤ 1, hence zT (kT ) = O((T log T )−1/2 ). For large T , Ω(kT /T ) = 1 and zT (kT ) ≤ α1 , so (26) gives BT (kT ) = η(log T )2 f0 + κzT (kT )2 = ηf0 (log T )2 + o(1). Therefore Regret(T, kT ; F ) ≥ (ηf0 /2)(log T )2 for all sufficiently large T .
5
Conclusion
This paper proves a tight lower bound for the additive prophet-online regret in the bounded-density gapped case of the multi-secretary problem: for a mixture of two separated uniform distributions, the regret at the critical capacity is Ω((log T )2 ). This shows that the additional logarithmic factor in prior upper bounds for gapped bounded-density instances is not an artifact of the analysis, but is already unavoidable in the one-resource multi-secretary specialization. The same Bellman-certificate framework also yields a matching lower bound for gapped distributions with gap-facing vanishing densities in the shifted-capacity regime; this companion result is proved in Appendix D. The proof approach is based on explicit feasible Bellman certificates for the exact Bellman recursion of the prophet-online regret. The certificates make visible the mechanism behind the regret order of the gapped support case. With a support gap, the reward curve is locally affine at the operating threshold and curvature appears only near the adjacent support edges; the certificate must therefore exploit moderate-deviation fluctuations of the prophet’s marginal order statistic. This separation between where slack is generated and where the certificate is transported is what permits the log-squared lower bound in the bounded-density gapped case. The Bellman-certificate method therefore works directly with the regret recursion rather than through policy-level indistinguishability arguments.
References Alaei S (2014) Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers. SIAM Journal on Computing 43(2):930–972. Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260. Arlotto A, Xie X (2020) Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards. Stochastic Systems 10(2):170–191. Banerjee S, Freund D (2024) Good prophets know when the end is near. Management Science 71(6):4877–4894. 24
Balseiro SR, Besbes O, Pizarro D (2024) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Operations Research 72(5):2168–2189. Besbes O, Kanoria Y, Kumar A (2024) Dynamic resource allocation: Algorithmic design principles and spectrum of achievable performances. Operations Research 73(3):1273–1288. Boucheron S, Lugosi G, Massart P (2013) Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press. Bray RL (2024) Logarithmic regret in multisecretary and online linear programs with continuous valuations. Operations Research 73(4):2188–2203. Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science 66(7):2993–3009. Chawla S, Hartline JD, Malec DL, Sivan B (2010) Multi-parameter mechanism design and sequential posted pricing. Proceedings of the 42nd ACM Symposium on Theory of Computing, 311–320. Chen G, Li X, Ye Y (2024) An improved analysis of LP-based control for revenue management. Operations Research 72(3):1124–1138. Chen Y, Wang W (2025) Beyond non-degeneracy: Revisiting certainty equivalent heuristic for online linear programming. arXiv preprint arXiv:2501.01716. Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2017) Posted price mechanisms for a random stream of customers. Proceedings of the 2017 ACM Conference on Economics and Computation, 169–186. Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019) Recent developments in prophet inequalities. ACM SIGecom Exchanges 17(1):61–70. Feller W (1971) An Introduction to Probability Theory and Its Applications, Vol. II, 2nd ed. Wiley. Freund D, Zhao J (2022) Overbooking with bounded loss. Mathematics of Operations Research 48(3):1344–1363. Gallego G, van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Science 40(8):999–1020. √ Gao W, Ge D, Xue C, Sun C, Ye Y (2025) Beyond O( T ) regret: Decoupling learning and decision-making in online linear programming. arXiv preprint arXiv:2501.02761. Gupta V (2024) Greedy algorithm for multiway matching with bounded regret. Operations Research 72(3):1139–1155. He S, Wei Y, Xu J, Yu SH (2025) Online resource allocation without re-solving: The effectiveness of primal-dual policies. Working paper, SSRN 5133857. Hill TP, Kertz RP (1982) Comparisons of stop rule and supremum expectations of i.i.d. random variables. The Annals of Probability 10(2):336–345. Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research 37(2):313–345.
25
Jiang J, Zhang J (2020) Online resource allocation with stochastic resource consumption. arXiv preprint arXiv:2012.07933. Jiang J, Ma W, Zhang J (2024) Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack. Operations Research 73(3):1703–1721. Jiang J, Ma W, Zhang J (2025a) Degeneracy is OK: Logarithmic regret for network revenue management with indiscrete distributions. Operations Research 73(6):3405–3420. Jiang J, Ma W, Zhang J (2025b) Tightness without counterexamples: A new approach and new results for prophet inequalities. Mathematics of Operations Research 51(2):956–987. Li G, Wang Z, Zhang J (2024) Infrequent resolving algorithm for online linear programming. arXiv preprint arXiv:2408.00465. Li X, Ye Y (2022) Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research 70(5):2948–2966. Lueker GS (1998) Average-case analysis of off-line and on-line knapsack problems. Journal of Algorithms 29(2):277–305. Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. The Annals of Probability 12(4):1213–1216. Talluri K, van Ryzin G (1998) An analysis of bid-price controls for network revenue management. Management Science 44(11):1577–1593. Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Science 67(3):1368–1391. Vera A, Banerjee S, Gurvich I (2021) Online allocation and pricing: Constant regret via Bellman inequalities. Operations Research 69(3):821–840. Wei Y, Xu J, Yu SH (2023) Constant regret primal-dual policy for multi-way dynamic matching. Working paper, SSRN 4357216. Xie Y, Ma W, Xin L (2025) The benefits of delay to online decision making. Management Science, forthcoming.
A
Binomial estimates
This section collects the binomial estimates used throughout the proof, stated uniformly over the central and moderate-deviation ranges that arise in the certificates. The estimates are elementary consequences of Bernstein’s inequality, Berry–Esseen, Mills’ ratio, and moment bounds for sums of bounded independent random variables; see, for example, Boucheron et al. (2013) for Bernstein-type concentration inequalities and Feller (1971) for classical normal approximation and tail estimates. Throughout this section fix q ∈ (0, 1) and write σ 2 := q(1 − q). For each horizon s ≥ 2, let N = Ns ∼ Bin(s − 1, q),
m := s − 1,
µs := q(s − 1).
For an integer capacity c ∈ {0, . . . , s}, use the coordinate xs (c) from (29) and set us (c) := |xs (c)|. When no confusion is possible we write x = xs (c) and u = |x|. Notice that the binomial mean is 26
µs = qs − q, whereas the state coordinate is centered at qs. This distinction creates only O(s−1/2 ) shifts. More precisely, for any integer c, r s c − µs q √ = xs (c) (51) + √ , m σ m σ m r c − 1 − µs s 1−q √ = xs (c) − √ . (52) m σ m σ m √ Thus, uniformly in the moderate-deviation range |xs (c)| ≤ A log s + L, c − µs 1 + |xs (c)| 1 √ = xs (c) + O (53) +√ , s σ m s and the same estimate holds with c replaced by c − 1.
A.1
Concentration and central moments
We begin with a nonasymptotic concentration estimate. It is useful both for tail truncations and for proving uniform moment bounds. Lemma A.1 (Bernstein bound for the binomial). For every s ≥ 2 and every t ≥ 0, t2 P(N − µs ≥ t) ≤ exp − 2 , 2σ (s − 1) + 2t/3 t2 . P(µs − N ≥ t) ≤ exp − 2 2σ (s − 1) + 2t/3
(54) (55)
Consequently, for every b > 0 there is Cb < ∞ such that E|N − µs |b ≤ Cb sb/2
for all s ≥ 2.
(56)
Ps−1
Proof. Write N − µs = i=1 (Zi − q), where Zi are iid Bernoulli(q). The summands are mean zero, bounded by 1 in absolute value, and have total variance (s − 1)σ 2 . Bernstein’s inequality gives (54); applying the same inequality to −(N − µs ) gives (55). For the moment bound, use the tail-integral identity Z ∞ E|N − µs |b = b tb−1 P(|N − µs | ≥ t) dt. 0
Split the integral at t = s. On 0 ≤ t ≤ s, Bernstein gives a sub-Gaussian bound after increasing constants: t2 P(|N − µs | ≥ t) ≤ 2 exp −c s for a constant c = c(q) > 0. Integrating this bound gives O(sb/2 ). On t > s, the probability is zero because |N − µs | ≤ s − 1. This proves (56). A useful corollary is the following square-root logarithmic concentration estimate. Corollary A.2 (Square-root logarithmic concentration). For every a > 0 there are constants Ca < ∞ and sa < ∞ such that, for all s ≥ sa , p P |N − µs | ≥ Ca s log s ≤ s−a . (57) √ Proof. Apply Lemma A.1 with t = C s log s. For fixed C, the denominator in Bernstein’s exponent is 2σ 2 s + o(s), hence the exponent is −(C 2 /(2σ 2 ) + o(1)) log s. Choosing C sufficiently large gives (57). 27
A.2
Moderate-deviation tail lower bounds
The next lemma gives the lower-tail estimates needed to keep the offline marginal Hs,c inside the gap. Lemma A.3 (Moderate-deviation tail lower bound). Fix constants A ∈ (0, 1) and L < ∞. There are constants aA > 0 and sA √ < ∞, depending only on q, A, L, such that for all s ≥ sA and all integers c with u = |xs (c)| ≤ A log s + L, 2
min{P(N < c), P(N ≥ c)} ≥ aA
e−u /2 . 1+u
(58)
Proof. Let ΦN denote the standard normal distribution function. The Berry–Esseen theorem for Bernoulli sums gives a constant CBE = CBE (q) such that, for all real t, N − µs CBE √ P ≤ t − ΦN (t) ≤ √ . (59) σ m m We first lower-bound P(N < c) when xs (c) ≤ 0. Let u = |xs (c)|. By (52), c − 1 − µs 1 1+u √ +√ . = −u + εs , |εs | ≤ C s σ m s √ In the range u ≤ A log s + L, one has |εs | = o(1) and (1 + u)|εs | = o(1). The mean-value theorem applied to v 7→ log ΦN (−v) gives log
ΦN (−u + εs ) ≤ C(1 + u)|εs | = o(1), ΦN (−u)
where the derivative bound uses Mills’ ratio. Hence the small shift changes the normal tail by a factor 1 + o(1) uniformly over this range. Applying Mills’ ratio once more gives 2
ΦN (−u + εs ) ≥ c1 ΦN (−u) ≥ c2
e−u /2 1+u
(60)
for constants c1 , c2 > 0. Since A < 1, √ 2 2 e−u /2 s−A /2 exp(−AL log s) √ ≥ c3 , 1+u 1 + log s and this quantity dominates s−1/2 . Therefore the Berry–Esseen error in (59) is at most one half of the right-hand side of (60) for all sufficiently large s. Since P(N < c) = P(N ≤ c − 1), this gives the required lower bound on P(N < c) when xs (c) ≤ 0. The corresponding lower bound on P(N ≥ c) when xs (c) ≥ 0 is identical. In that case, c − µs √ = u + o(1), σ m and applying Berry–Esseen to the upper tail, with the same Mills-ratio comparison, gives 2
e−u /2 P(N ≥ c) ≥ c4 1+u 28
for a constant c4 > 0. Finally, (58) follows by combining the preceding estimates with the trivial observation that the non-rare side has probability bounded below by a positive constant. For example, if xs (c) ≤ 0, then the preceding lower bound controls P(N < c), while P(N ≥ c) is at least a positive constant for all large s by Berry–Esseen and (51). The case xs (c) ≥ 0 is symmetric. Reducing aA if necessary gives (58). The form most often used later is the following direct consequence. √ Corollary A.4 (Tail lower bound on the s log s scale). Fix√A ∈ (0, 1). There are constants bA > 0 and sA < ∞ such that, whenever s ≥ sA and |c − qs| ≤ Aσ s log s, one has 2
min{P(N < c), P(N ≥ c)} ≥ bA s−A /2 (log s)−1/2 . √ Proof. Apply Lemma A.3 with L = 0. Since u ≤ A log s, 2
(61)
2
s−A /2 e−u /2 2 √ ≥ ≥ bA s−A /2 (log s)−1/2 1+u 1 + A log s for all large s. √ When a bound has the form |xs (c)| ≤ A0 log s + O(1), we will apply Corollary A.4 with any fixed A > A0 ; this absorbs the O(1) buffer for all sufficiently large s.
A.3
Positive-part binomial moments
The source estimates in the vanishing-density sections require moments of the random rank by which the future high count exceeds, or falls short of, the capacity. The next lemma gives both upper bounds and truncated lower bounds. The truncation in the lower bound will later ensure √ that the relevant order-statistic ranks are at most a constant multiple of (1 + u) s. Lemma A.5 (Positive-part binomial moments). Fix a > 0 and constants A, L < ∞. There are constants 0 < ba < Ba < ∞ and sa√< ∞, depending only on q, a, A, L, such that for all s ≥ sa and all integers c with u = |xs (c)| ≤ A log s + L, one has E[(N − c + 1)a+ ] ≤ Ba sa/2 (1 + u)a ,
(62)
E[(c − N )a+ ] ≤ Ba sa/2 (1 + u)a .
(63)
Moreover, if xs (c) ≤ 0, then E (N − c + 1)a+ 1{1≤N −c+1≤Ba (1+u)√s} ≥ ba sa/2 (1 + u)a ,
(64)
and if xs (c) ≥ 0, then E (c − N )a+ 1{1≤c−N ≤Ba (1+u)√s} ≥ ba sa/2 (1 + u)a .
(65)
Proof. We prove (62) and (64); the estimates involving (c − N )+ follow by the same argument applied to µs − N . For the upper bound, use (N − c + 1)+ ≤ |N − µs | + |µs − c + 1|. 29
In the stated range,
√ |µs − c + 1| ≤ C(1 + u) s.
Therefore, by (r + t)a ≤ Ca (ra + ta ) and Lemma A.1, E[(N − c + 1)a+ ] ≤ Ca E|N − µs |a + Ca (1 + u)a sa/2 ≤ Ba sa/2 (1 + u)a . Now assume xs (c) ≤ 0. Then √ µs − c + 1 = σ s u + (1 − q).
(66)
We split into two cases. First suppose u ≥ u0 , where u0 is a fixed constant chosen large enough below. Let 1 √ Eu := |N − µs | ≤ σ s u . 2 Chebyshev’s inequality gives 4 Var(N ) 4 ≤ 2. 2 2 σ su u Choose u0 so large that this probability is at most 1/2. On Eu , (66) implies P(Euc ) ≤
1 √ N − c + 1 ≥ σ su 2 for all sufficiently large s, and also √ √ N − c + 1 ≤ C s u ≤ C(1 + u) s. Thus 1 E (N − c + 1)a+ 1{1≤N −c+1≤C(1+u)√s} ≥ 2
a 1 √ σ s u ≥ csa/2 (1 + u)a , 2
after reducing c and using u ≥ u0 . It remains to consider 0 ≤ u ≤ u0 . Let I = [2, 3]. Berry–Esseen gives N − µs √ ∈ I ≥ c0 > 0 P σ s for all large s, uniformly in c because the interval is fixed and does not depend on c. On this event, √ √ √ √ N − c + 1 = (N − µs ) + (µs − c + 1) ≥ 2σ s + σ s u + (1 − q) ≥ 2σ s ≥ c1 s, where the last inequality holds for all sufficiently large s and uses u ≥ 0. Moreover, using u ≤ u0 , √ √ N − c + 1 ≤ C1 s ≤ C1 (1 + u) s. √ Therefore the truncated expectation is at least c0 (c1 s)a , which is comparable to sa/2 (1 + u)a because u is bounded. Enlarging Ba and reducing ba completes the proof of (64). √ The truncation in (64) and (65) ensures that the relevant conditional rank is at most O((1+u) s), which is o(s) in the moderate-deviation ranges used later.
30
B
Edge quantiles and order statistics
This section introduces the local assumptions at the support edges adjacent to the gap, which we call gap-facing edges, and turns them into estimates for the offline marginal order statistic. The results are deliberately stated in a reusable one-sided form and are applied at the two gap-facing support edges a2 and b1 . Fix a local mass exponent β ≥ 0 and define θ :=
1 , β+1
γ :=
β 1−θ = . 2(β + 1) 2
(67)
Assumption B.1 (Gap-facing edge exponent). There exist constants 0 < mg < Mg < ∞ and εg > 0 such that, for every 0 < u ≤ εg , mg uβ+1 ≤ F+ (a2 + u) ≤ Mg uβ+1 ,
(68)
mg uβ+1 ≤ 1 − F− (b1 − u) ≤ Mg uβ+1 .
(69)
If densities exist, the gap-facing densities are ≍ distanceβ . The case β = 0 corresponds to bounded positive densities at the two gap-facing edges, while β > 0 is the vanishing-density case used in Appendix D. Lemma B.2 (Gapped convex residual shape). Under Assumption B.1, there are constants 0 < c < C < ∞ such that, for all sufficiently small u > 0, cuβ+2 ≤ ∆(a2 + u) ≤ Cuβ+2 ,
cuβ+2 ≤ ∆(b1 − u) ≤ Cuβ+2 .
Proof. For u > 0 small, ∆′ (a2 + u) = qF+ (a2 + u),
∆′ (b1 − u) = −p 1 − F− (b1 − u) .
Because ∆ vanishes at both gap boundaries, integration gives Z u Z u ∆(a2 + u) = q F+ (a2 + v) dv, ∆(b1 − u) = p 1 − F− (b1 − v) dv. 0
0
The two estimates then follow from (68)–(69). We use the following elementary convention. A right-edge coordinate is denoted by x ≥ 0 and corresponds to values e + x to the right of an edge e. A left-edge coordinate is also denoted by x ≥ 0 and corresponds to values e − x to the left of an edge e.
B.1
One-sided quantile conversion
Let A : [0, L] → [0, 1] be a continuous strictly increasing distribution function in edge-distance coordinates, with A(0) = 0 and A(L) = 1. Its generalized inverse is QA (u) := inf{x ∈ [0, L] : A(x) ≥ u}, In applications, A(x) is either F+ (a2 + x) or 1 − F− (b1 − x).
31
0 < u ≤ 1.
Lemma B.3 (Edge quantile bounds). Suppose that there are constants m, M, ρ > 0 such that mxβ+1 ≤ A(x) ≤ M xβ+1 ,
0 ≤ x ≤ ρ.
(70)
Then there exist constants 0 < cQ < CQ < ∞ and u0 ∈ (0, 1) such that cQ uθ ≤ QA (u) ≤ CQ uθ ,
0 < u ≤ u0 .
(71)
Moreover, after increasing CQ if necessary, one has the global upper bound QA (u) ≤ CQ uθ ,
0 < u ≤ 1.
(72)
Proof. Choose u0 := min{mρβ+1 , M ρβ+1 , 1/2}. If 0 < u ≤ u0 , then both (u/m)θ and (u/M )θ are at most ρ. The upper bound follows because β+1 A (u/m)θ ≥ m (u/m)θ = u, so QA (u) ≤ m−θ uθ . The lower bound follows because if x < (u/M )θ , then A(x) ≤ M xβ+1 < u, hence the inverse cannot be smaller than (u/M )θ . This gives (71) with cQ = M −θ and CQ = m−θ . θ For u ≥ u0 , compactness gives QA (u) ≤ L ≤ Lu−θ 0 u . Enlarging CQ to dominate both constants yields (72). The next lemma is the main conversion used in all source estimates. It says that an edge-rank fraction u produces convex residual cost of order at least u1+θ . Lemma B.4 (Edge quantile-to-residual conversion). Let A satisfy the assumptions of Lemma B.3. Let ∆A : [0, L] → [0, ∞) be continuous with ∆A (0) = 0 and ∆A (x) > 0 for x > 0. Suppose that for some m∆ , M∆ , ρ∆ > 0, m∆ xβ+2 ≤ ∆A (x) ≤ M∆ xβ+2 ,
0 ≤ x ≤ ρ∆ .
(73)
Then there are constants 0 < c∆ < C∆ < ∞ such that, for all 0 < u ≤ 1, c∆ u1+θ ≤ ∆A (QA (u)) ≤ C∆ u1+θ .
(74)
The same conclusion applies at a left edge after writing x = e − v for the distance from the edge. Proof. Let u1 > 0 be small enough that QA (u) ≤ ρ∆ for every 0 < u ≤ u1 , which is possible by Lemma B.3. For 0 < u ≤ u1 , Lemma B.3 and (73) give θ(β+2) ∆A (QA (u)) ≥ m∆ (cQ uθ )β+2 = m∆ cβ+2 . Q u
Since θ(β + 2) = 1 + θ, this is the desired lower bound for small u. For u ∈ [u1 , 1], the function u 7→ ∆A (QA (u)) is positive. More explicitly, QA (u) ≥ QA (u1 ) > 0, and by the assumption ∆A (x) > 0 for x > 0 and compactness of [QA (u1 ), L], m1 :=
inf x∈[QA (u1 ),L]
∆A (x) > 0.
Because u1+θ ≤ 1, the same lower bound holds on [u1 , 1] with constant m1 . Taking the smaller of the two constants proves the lower bound in (74). For the upper bound, use the local upper bounds for u ≤ u1 and boundedness of ∆A for u ≥ u1 , enlarging the constant if necessary by the same compactness argument. Remark B.5 (How the abstract conversion is used). For the upper gap edge a2 , take A(x) = F+ (a2 +x) and ∆A (x) = ∆(a2 + x). For the lower edge adjacent to the gap, b1 , take A(x) = 1 − F− (b1 − x) and ∆A (x) = ∆(b1 − x). Assumption B.1 and Lemma B.2 imply the local power hypotheses. The positivity condition ∆A (x) > 0 for x > 0 follows because h0 is a supporting affine function and ∆ vanishes on the gap but is strictly increasing into either support edge for small positive edge distance. 32
B.2
Uniform order-statistic moments
The conditional distribution of an edge order statistic is obtained by applying an edge quantile to a uniform order statistic. We record the moment estimates needed for that conversion. Lemma B.6 (Gamma-ratio bound). For every fixed a > 0 there are constants 0 < ca < Ca < ∞ such that Γ(x + a) ca xa ≤ ≤ Ca xa , x ≥ 1. (75) Γ(x) Proof. The function Ra (x) :=
Γ(x + a) Γ(x)xa
is continuous and positive on [1, ∞). By Stirling’s formula, Ra (x) → 1 as x → ∞. Therefore Ra is bounded above and below by positive finite constants on [1, ∞). Lemma B.7 (Uniform order-statistic moment). Let Uj:n be the j-th smallest order statistic among n independent uniform [0, 1] random variables. For every fixed a > 0 there are constants 0 < ca < Ca < ∞ such that, uniformly over 1 ≤ j ≤ n, a a j j a ca ≤ E[Uj:n ] ≤ Ca . (76) n+1 n+1 Proof. The density of Uj:n is beta with parameters (j, n − j + 1). Hence a E[Uj:n ]=
Γ(j + a) Γ(n + 1) . Γ(j) Γ(n + 1 + a)
(77)
Applying Lemma B.6 first at x = j and then at x = n + 1 gives a E[Uj:n ] ≍a
ja , (n + 1)a
which is (76). Corollary B.8 (Convex residual moment of an edge order statistic). Under the hypotheses of Lemma B.4, if Uj:n is the j-th smallest uniform order statistic, then E ∆A (QA (Uj:n )) ≥ c
j n+1
1+θ ,
1 ≤ j ≤ n,
(78)
where c > 0 depends only on the edge constants and on θ. The upper bound follows from the upper bound in (74). Proof. By Lemma B.4, 1+θ ∆A (QA (Uj:n )) ≥ c∆ Uj:n .
Taking expectations and applying Lemma B.7 with a = 1 + θ proves the claim. The upper estimate is identical.
33
B.3
Source estimates at a support gap
We now combine the edge conversion with the binomial moment estimates from Section A. These estimates control the positive Jensen/order-statistic term for the gapped β > 0 certificate. Assume the two-support model of Assumption B.1. Let N ∼ Bin(s − 1, q) be the number of future arrivals in the upper support. Conditional on N = n, the upper-support observations are independent draws from F+ and the lower-support observations are independent draws from F− . Since every upper-support value exceeds every lower-support value, the offline marginal Hs,c has the following conditional descriptions: • If n ≥ c, then Hs,c lies in the upper support and is the upper-support order statistic of rank n − c + 1. • If n < c, then Hs,c lies in the lower support and is the lower-support order statistic of upper-tail rank c − n, equivalently the distance from the lower right edge b1 has rank c − n from the left. Lemma B.9 (Gapped source estimate). Assume Assumption B.1. Fix constants A, L < ∞ with A < 1. There exist constants 0 < c < C < ∞ and s0 < ∞ such that, for all s ≥ s0 and all integers c satisfying p u = |xs (c)| ≤ A log s + L, one has csγ−1 (1 + u)1+θ ≤ E∆(Hs,c ) ≤ Csγ−1 (1 + u)1+θ + C P |N − µs | > C
p s log s .
(79)
The constant inside the probability can be chosen large enough to make that probability O(s−r ) for any fixed r < ∞. Proof. We first prove the lower bound when xs (c) ≤ 0; the case xs (c) ≥ 0 is the same with the roles of the two support intervals interchanged. Assume xs (c) ≤ 0. Conditional on N = n ≥ c, set j = n − c + 1. Then Hs,c = a2 + Q+ (Uj:n ), where Q+ is the lower-edge distance quantile of F+ at a2 and Uj:n is the j-th smallest uniform order statistic among n points. Corollary B.8 gives E [∆(Hs,c ) | N = n] ≥ c1
n−c+1 n+1
1+θ ,
n ≥ c.
(80)
Since n + 1 ≤ s, the right side is at least c1 ((n − c + 1)/s)1+θ . Therefore # " N − c + 1 1+θ 1{N ≥c} . E ∆(Hs,c )1{N ≥c} ≥ c1 E s Dividing the truncated lower bound in Lemma A.5 by s1+θ , with a = 1 + θ, gives E ∆(Hs,c )1{N ≥c} ≥ c2 s−(1+θ)/2 (1 + u)1+θ . Because 1 + θ = 2(1 − γ), s−(1+θ)/2 = sγ−1 . This gives the lower bound in (79) when xs (c) ≤ 0. For the upper bound, split according to N ≥ c and N < c. On the event p EC := {|N − µs | ≤ C s log s},
34
√ with C fixed large enough, the displayed range for c implies c = qs + O( s log s). Hence, on EC and for all large s, the relevant conditional sample sizes satisfy n + 1 ≥ (q/2)s on {N ≥ c} and s − n ≥ (p/2)s on {N < c}. The corresponding ranks are j+ (n) = n − c + 1, j− (n) = c − n, √ √ and both are bounded by C ′ (1 + u + log s) s on EC . Using the upper half of Lemma B.4 and Lemma B.7 conditionally on N = n gives E[∆(Hs,c ) | N = n] ≤ C E[∆(Hs,c ) | N = n] ≤ C
j+ (n) s
1+θ
j− (n) s
1+θ
,
n ≥ c,
,
n < c.
Taking expectations and applying Lemma A.5 to (N − c + 1)+ and (c − N )+ gives the term Cs−(1+θ)/2 (1 + u)1+θ = Csγ−1 (1 + u)1+θ . On ECc , the convex residual is bounded because the value support is compact; this gives the probability term in (79).
C
A standard-scale finite-difference expansion
For a candidate certificate Bs (c) = ηas Gs (xs (c)), recall the affine-transport drift Ms (c) = (1 − q)Bs−1 (c) + qBs−1 (c − 1) − Bs (c). √ We use the standard coordinate xs (c) = (c − qs)/(σ s) and allow the profile Gs to depend on s.
C.1
Predecessor-coordinate expansion
Throughout this subsection, let ξ be the two-point random variable ( q, with probability 1 − q, ξ= −(1 − q), with probability q. Then Eξ = 0, Eξ 2 = σ 2 , and |ξ| ≤ 1. √ Lemma C.1 (Predecessor coordinates). Fix Rs ≥ 1 with Rs = O( log s). Uniformly over states with |xs (c)| ≤ Rs , writing x = xs (c), define √ σ sx + ξ Xs := √ . σ s−1 Then Xs = xs−1 (c) with probability 1 − q and Xs = xs−1 (c − 1) with probability q. Moreover, ξ x Xs = x + √ + + Rs (x, ξ), σ s 2s
35
|Rs (x, ξ)| ≤ C
1 + |x| . s3/2
(81)
Proof. By definition,
√ c − q(s − 1) σ sx + q √ xs−1 (c) = = √ , σ s−1 σ s−1
and similarly
Since
√ σ s x − (1 − q) √ xs−1 (c − 1) = . σ s−1 r
s 1 =1+ + O(s−2 ), s−1 2s
√
1 1 = √ 1 + O(s−1 ) , s s−1
Substitution gives the stated representation of Xs and the error bound. The identities for the two predecessor coordinates follow from taking ξ = q and ξ = −(1 − q), respectively.
C.2
Taylor expansion of the affine transport
For an interval I ⊂ R write
∥f ∥j,I := sup |f (j) (y)|. y∈I
For a state (s, c) and a local radius ρloc > 0, define Is,c (ρloc ) := [xs (c) − ρloc , xs (c) + ρloc ]. Lemma C.2 (Standard-scale Bellman drift expansion). Let Bs (c) = ηas Gs (xs (c))
(82)
√ for positive numbers as and functions Gs ∈ C 3 (R). Fix Rs = O( log s) and suppose |xs (c)| ≤ Rs . Let x = xs (c) and let I = Is,c (1). Then, for all sufficiently large s, Ms (c) = (1 − q)Bs−1 (c) + qBs−1 (c − 1) − Bs (c) ′′ Gs (x) xG′s (x) + + η(as−1 − as )Gs (x) + ηas Gs−1 (x) − Gs (x) + Errs,c , = ηas 2s 2s
(83)
where the error satisfies " 1 + x2 ′′ 1 1 + |x| ′ ∥Gs ∥0,I |Errs,c | ≤ Cηas ∥Gs ∥0,I + 3/2 ∥G′′′ s ∥0,I + 2 s s s3/2 1 1 + |x| ′ + ∥G′′s−1 − G′′s ∥0,I + ∥Gs−1 − G′s ∥0,I s s # as−1 as−1 |x| ′ as−1 1 ′′ + − 1 ∥Gs−1 − Gs ∥0,I + −1 ∥Gs ∥0,I + − 1 ∥Gs ∥0,I . as as s as s (84) √ The constant C depends only on q and on the implicit constant in Rs = O( log s). Proof. Let ξ and Xs be as in Lemma C.1. Then (1 − q)Gs−1 (xs−1 (c)) + qGs−1 (xs−1 (c − 1)) = EGs−1 (Xs ).
36
(85)
√ By (81), |Xs − x| ≤ C(1 + Rs )/ s = o(1) uniformly on the active range; hence Xs ∈ I for all sufficiently large s. In the Taylor expansions below, the Lagrange intermediate point lies between x and Xs and therefore also lies in I. First expand Gs around x. Taylor’s theorem with remainder gives 1 EGs (Xs ) = Gs (x) + G′s (x)E(Xs − x) + G′′s (x)E(Xs − x)2 + R3 , 2 where 3 |R3 | ≤ C∥G′′′ s ∥0,I E|Xs − x| .
From Lemma C.1, x 1 + |x| E(Xs − x) = , +O 2s s3/2 1 1 + x2 2 E(Xs − x) = + O , s s2 E|Xs − x|3 ≤ Cs−3/2 .
(86) (87) (88)
Here the cross terms involving the remainder Rs (x, ξ) are not zero in general, because Rs depends on ξ; they are bounded directly by E|Rs (x, ξ)| ≤ C(1 + |x|)s−3/2 and E|ξRs (x, ξ)| ≤ C(1 + |x|)s−3/2 , which is precisely the size absorbed in (86)–(87). Therefore EGs (Xs ) = Gs (x) + with
xG′s (x) G′′s (x) + + Rs(1) , 2s 2s
(89)
1 + x2 ′′ 1 + |x| ′ 1 ′′′ ∥G ∥ + ∥G ∥ ∥G ∥ + (90) 0,I . s 0,I s 0,I s2 s3/2 s3/2 s Next compare Gs−1 with Gs . By Taylor expanding the difference Gs−1 − Gs to second order and using (86)–(87), 1 + |x| ′ 1 ′′ ′ ′′ E (Gs−1 − Gs )(Xs ) − (Gs−1 − Gs )(x) ≤ C ∥Gs−1 − Gs ∥0,I + ∥Gs−1 − Gs ∥0,I . (91) s s |Rs(1) | ≤ C
Combining (85), (89), and (91), EGs−1 (Xs ) = Gs (x) +
xG′s (x) G′′s (x) + + (Gs−1 (x) − Gs (x)) + Rs(2) , 2s 2s
(92)
(2)
where Rs is bounded by the first five terms in (84) without the factor ηas . Finally, Ms (c) = ηas−1 EGs−1 (Xs ) − ηas Gs (x). Insert (92), write as−1 = as + (as−1 − as ), and keep the leading contribution of (as−1 − as )Gs (x). The product of (as−1 − as ) with the time-change term Gs−1 (x) − Gs (x) is the cross term η(as−1 − as ) Gs−1 (x) − Gs (x) , which is bounded by the new term Cηas
as−1 − 1 ∥Gs−1 − Gs ∥0,I as
in (84). The multiplication of (as−1 /as − 1) against the transport derivative terms gives the final two terms in (84). This proves (83)–(84). 37
C.3
Useful corollaries
The following two consequences are the forms used later in the proof. Corollary C.3 (Power-height drift). Let as = sγ with fixed γ ∈ [0, 1/2). Assume that on the active √ range |xs (c)| ≤ Rs = O( log s) the profile sequence satisfies mj |G(j) s (y)| ≤ As Ks (1 + |y|) , As Ks (j) |Gs−1 (y) − G(j) (1 + |y|)mj , s (y)| ≤ s log s
j = 0, 1, 2, 3, j = 0, 1, 2,
for deterministic scales As , Ks growing at most polynomially in log s. Then 1 ′ γ−1 1 ′′ Ms (c) = ηs G (x) + xGs (x) − γGs (x) + Rems,c , 2 s 2
(93)
where |Rems,c | is bounded by ηsγ ∥Gs−1 − Gs ∥0,I + the right side of (84) with as = sγ , including the cross term involving Gs−1 − Gs . In particular, the remainder is lower order whenever the displayed derivative and time-variation bounds are lower order relative to the intended source term. Proof. For as = sγ , as−1 − as = −γsγ−1 + O(sγ−2 ). Substituting this into Lemma C.2 gives (93). The explicit time-change term ηsγ (Gs−1 (x) − Gs (x)), the O(sγ−2 )Gs (x) part of as−1 − as , and the error bound (84) are all included in Rems,c . Corollary C.4 (First difference on the standard scale). Let Bs (c) = √ ηas Gs (xs (c)). Suppose Gs is continuously differentiable on the active range and |xs (c)| ≤ Rs = O( log s). Then, whenever the line segment between xs−1 (c) and xs−1 (c − 1) lies inside the active range enlarged by one, |Ds (c)| = |Bs−1 (c) − Bs−1 (c − 1)| ≤
Cηas−1 √ sup |G′ (y)|. s y∈Is,c (1) s−1
Proof. The predecessor coordinates differ by 1 xs−1 (c) − xs−1 (c − 1) = √ . σ s−1 The mean-value theorem gives 1 |Ds (c)| ≤ ηas−1 √ sup |G′s−1 (y)|, σ s − 1 y∈Is,c (1) which is (94) after increasing the constant.
38
(94)
D
The gapped vanishing-density lower bound, β > 0
This section proves the gapped positive-exponent extension, where the support has a gap and the gap-facing densities vanish with exponent β > 0. The proof uses the common Bellman certificate inequality from Section 3, the binomial estimates from Appendix A, the edge-order estimates from Appendix B, and the standard-scale finite-difference expansion from Appendix C. The new ingredient √ in this section is the form of the certificate. It has a harmonic core on the s scale, but the core is √ allowed to grow out to the moderate-deviation radius s log s. Throughout this section Assumption B.1 holds with β > 0 for the harmonic-certificate construction; the exponents θ and γ are those in (67). The mean boundary overshoot and gap-margin estimates in Subsection D.2 are stated in a form that also covers the case β = 0. Recall that ∆ ≡ 0 on the gap [b1 , a2 ], that ∆ ≥ 0 is convex, and that near the two gap-facing edges ∆(a2 + u) ≍ uβ+2 ,
∆(b1 − u) ≍ uβ+2 .
(95)
The lower bound is proved by constructing a feasible Bellman certificate supported in the moderate-deviation band p |c − qs| ≲ s log s. At sufficiently small fixed shifts on this scale, the harmonic core contributes the height needed for the lower bound in Theorem D.10.
D.1
The harmonic core profile
The drift operator associated with standard-scale Bellman transport is 1 1 Lγ f (x) := f ′′ (x) + xf ′ (x) − γf (x). 2 2
(96)
The profile used near the critical line must be nearly annihilated by this operator. Otherwise the negative drift near x = O(1) would be too large to be balanced by the source. Define Hγ (x) := E|x + Z|2γ ,
Z ∼ N (0, 1),
x ∈ R.
Lemma D.1 (Harmonic core). The function Hγ belongs to C ∞ (R), is even and strictly positive, and Lγ Hγ = 0. (97) For each integer j ≥ 0 there is Cj < ∞ such that |Hγ(j) (x)| ≤ Cj (1 + |x|)2γ ,
x ∈ R.
For every integer j ≥ 1, sup |Hγ(j) (x)| < ∞.
(98)
x∈R
Finally, there are constants 0 < c0 < C0 < ∞ such that, for |x| ≥ 1, c0 |x|2γ ≤ Hγ (x) ≤ C0 |x|2γ . Proof. Write Z Hγ (x) =
|y|2γ φ(y − x) dy,
R
39
(99)
where φ is the standard normal density. This is the convolution of the locally integrable function y 7→ |y|2γ with a smooth Gaussian density. Hence Hγ ∈ C ∞ (R), and differentiation may be performed on the Gaussian factor. Evenness and positivity are immediate. We next prove the differential equation. The singularity of |y|2γ at zero is harmless, but it is better not to differentiate the singular integrand twice. Let fε (y) = (y 2 + ε2 )γ and Hγ,ε (x) := Efε (x + Z). For each fixed ε > 0, Stein’s identity gives, with W = x + Z, ′′ ′ Hγ,ε (x) + xHγ,ε (x) = E[W fε′ (W )].
Here W fε′ (W ) = 2γW 2 (W 2 + ε2 )γ−1 is bounded by a constant times 1 + |W |2γ uniformly in ε ≤ 1. Hence dominated convergence, uniformly on compact x-sets, yields lim E[W fε′ (W )] = 2γE|W |2γ = 2γHγ (x). ε↓0
The convergence Hγ,ε → Hγ and the convergence of the derivatives follow by differentiating the Gaussian kernel in the convolution representation above. Therefore Hγ′′ (x) + xHγ′ (x) = 2γHγ (x), which is equivalent to (97). The global derivative bounds follow by differentiating the Gaussian kernel. The derivative (j) Hγ (x) is an integral of |y|2γ times a degree-j polynomial in (y − x) times φ(y − x); after the change of variables z = y − x, this is bounded by Cj E(1 + |x + Z|)2γ (1 + |Z|)j ≤ Cj′ (1 + |x|)2γ . For |x| ≥ 1, the upper bound in (99) and the derivative bounds |Hγ(j) (x)| ≤ Cj |x|2γ−j ,
|x| ≥ 1, j ≥ 1,
follow similarly from Taylor expansion on the event |Z| ≤ |x|/2 and from Gaussian tails on the complement. The lower bound for Hγ follows from Hγ (x) ≥ E |x + Z|2γ 1{|Z|≤|x|/2} ≥ (|x|/2)2γ P(|Z| ≤ |x|/2), which is at least a positive constant times |x|2γ for |x| ≥ 1. For j ≥ 1, the large-x derivative bound above and the inequality 0 < 2γ < 1 imply boundedness on |x| ≥ 1. On |x| ≤ 1, continuity gives boundedness. This proves (98). Choose constants
√ 0 < α1 < α2 < A <
θ.
(100)
Let ψ ∈ C ∞ (R) be even, with 0 ≤ ψ ≤ 1, such that ψ(u) = 1
(|u| ≤ α1 ),
ψ(u) = 0
(|u| ≥ α2 ).
(101)
For all sufficiently large s, define p Gs (x) := (log s)θ Hγ (x)ψ(x/ log s).
(102)
Bs (c) := ηsγ Gs (xs (c)),
(103)
The certificate is 1 ≤ c < s,
with boundary values Bs (0) = 0 and Bs (c) = 0 for c ≥ s. Here η > 0 is a small constant chosen only after all other constants and the base time are fixed. 40
Lemma D.2 (Profile bounds). There is a constant C < ∞ such that, for all sufficiently large s, the following bounds hold. √ √ (i) The support of Gs is contained in [−α2 log s, α2 log s], and |Gs (x)| ≤ C(log s)θ (1 + |x|)2γ 1{|x|≤α2 √log s} .
(104)
In particular |Gs (x)| ≤ C(log s)(1+θ)/2 everywhere. (ii) For j = 1, 2, 3, θ √ |G(j) s (x)| ≤ C(log s) 1{|x|≤α2 log s} .
(105)
√ √ (iii) On the collar α1 log s ≤ |x| ≤ α2 log s, |Gs (x)| ≤ C(log s)(1+θ)/2 ,
|G′s (x)| ≤ C(log s)θ/2 ,
|G′′s (x)| ≤ C(log s)(θ−1)/2 ,
(θ−2)/2 |G′′′ . s (x)| ≤ C(log s)
(106)
√ (iv) Uniformly for |x| ≤ α2 log s + 2 and j = 0, 1, 2, (j)
|Gs−1 (x) − G(j) s (x)| ≤
C (log s)(1+θ)/2 . s
(107)
√ In the core region |x| ≤ α1 log s − 1, the sharper bound |Gs−1 (x) − Gs (x)| ≤
C (log s)θ−1 (1 + |x|)2γ s
(108)
holds. Proof. The support statement follows from the support of ψ. The size bound follows from Lemma D.1: |Gs (x)| ≤ C(log s)θ (1 + |x|)2γ 1{|x|≤α2 √log s} . On the support, (1 + |x|)2γ ≤ C(log s)γ , so |Gs | ≤ C(log s)θ+γ = C(log s)(1+θ)/2 , because θ + γ = (1 + θ)/2. √ For (log s)θ Hγ (x)ψ(x/ log s). Every derivative falling on √ derivatives, differentiate the product ψ(x/ log s) produces a factor (log s)−1/2 , and the derivatives of ψ are bounded. The conservative global bound (105) follows from the uniform derivative bound (98) for the terms in which at least one derivative falls on Hγ , and from the size bound |Hγ (x)| ≤ C(1 + |x|)2γ for the terms in which all derivatives fall on the cutoff. For example, (log s)θ Hγ (x) √ In the collar |x| ≍
√
p 1 ψ ′ (x/ log s) ≤ C(log s)θ (log s)γ−1/2 = C(log s)θ/2 ≤ C(log s)θ . log s
log s, the sharper estimates in (99) give
(log s)θ |Hγ (x)| = O((log s)(1+θ)/2 ),
(log s)θ |Hγ′ (x)| = O((log s)θ/2 ),
and the cutoff derivative term in G′s is also O((log s)θ (log s)γ (log s)−1/2 ) = O((log s)θ/2 ). The product rule gives, for instance, h i p G′′s = (log s)θ Hγ′′ ψ + 2Hγ′ (log s)−1/2 ψ ′ + Hγ (log s)−1 ψ ′′ (x/ log s), 41
whose three terms are all O((log s)(θ−1)/2 ) on the collar; differentiating once more gives terms of order O((log s)(θ−2)/2 ). This proves (106).√ For time differences, write Gs (x) = Γ( log s, x) with Γ(Y, x) := Y 2θ Hγ (x)ψ(x/Y ). p √ √ For |x| ≤ α2 log s + 2 and Y between log(s − 1) and log s, the same product-rule bounds used above give |∂Y ∂xj Γ(Y, x)| ≤ C(log s)θ/2 , j = 0, 1, 2. We carry out the largest case explicitly. Differentiating the displayed formula for ∂x2 Γ in Y produces terms such as Y 2θ−1 Hγ′′ ψ, Y 2θ−2 Hγ′ ψ ′ , Y 2θ−3 Hγ ψ ′′ , xY 2θ−4 Hγ ψ ′′′ , all evaluated at x/Y . In the present range, the sharp bounds for Hγ on the collar and the uniform derivative these at most C(log s)θ/2 ; the cases j = 0, 1 are easier. p in the core make√each of √ bounds (θ−1)/2 ); Since log s − log(s − 1) = O((s log s)−1 ), this implies the stronger √ bound O(s−1 p(log s) the displayed weaker bound (107) follows. In the core, ψ ≡ 1 for both log s and log(s − 1), so Γ(Y, x) = Y 2θ Hγ (x). The mean-value theorem gives |Gs−1 (x) − Gs (x)| ≤ C|
p p C log s − log(s − 1)|(log s)θ−1/2 Hγ (x) ≤ (log s)θ−1 (1 + |x|)2γ , s
which is (108).
D.2
Source estimates and gap margin
√ √ The certificate is supported on |xs (c)| ≤ α2 log s. Since α2 < θ, this active band lies in a moderate-deviation range where the offline marginal mean remains in the support gap with a polynomially large margin. We first record the source estimate, then prove the margin and show that the certificate perturbation is too small to move the threshold out of the gap. The mean boundary overshoot and gap-margin estimates are common estimates for the gapped regime. Although this section proves the positive-β certificate, Lemmas D.4 and D.5 are stated and proved under Assumption B.1 for any β ≥ 0, with θ = 1/(β + 1). Their moderate-deviation radius is denoted by A0 in the statements below; in the harmonic-certificate argument one takes A0 = A, while in Section 4 one may take any fixed A0 < 1 because θ = 1. Lemma D.3 (Gapped source on the active band). There are constants cS > 0 and sS < ∞ such that, for all s ≥ sS and all 1 ≤ c < s satisfying p |xs (c)| ≤ A log s, (109) one has E∆(Hs,c ) ≥ cS sγ−1 (1 + |xs (c)|)1+θ .
(110)
Proof. This is a direct consequence √ of Lemma B.9. The condition (109) is the same as |xs (c)| ≤ √ A log s, with A < 1 because A < θ ≤ 1. The two edge assumptions required in Lemma B.9 are exactly the edge-mass assumptions in Assumption B.1. Lemma B.9 gives the lower bound in (79), and 1 + θ = 2(1 − γ) gives precisely (110). The next estimate controls the average amount by which the offline marginal overshoots into one of the two support intervals. It is used to locate τs (c) = EHs,c inside the gap. 42
Lemma D.4 (Mean boundary overshoot). Under Assumption B.1 with any β ≥ 0, let θ be as in (67) and fix A0 < ∞. There are constants CP √ < ∞ and sP < ∞, depending also on A0 , such that, for all s ≥ sP and all c satisfying |xs (c)| ≤ A0 log s, with u := |xs (c)|, E[(Hs,c − a2 )+ ] ≤ CP s−θ/2 (1 + u)θ , −θ/2
E[(b1 − Hs,c )+ ] ≤ CP s
θ
(1 + u) .
(111) (112)
Proof. We prove (111); the other estimate is symmetric. The random variable (Hs,c − a2 )+ is nonzero only on {N ≥ c}. Conditional on N = n ≥ c, Hs,c is the upper-support order statistic of rank n − c + 1. The lower-edge quantile bound for the upper support applies because Assumption B.1 gives edge mass comparable to distanceβ+1 at a2 . Thus, by the global upper bound in Lemma B.3, after increasing the constant as in that lemma, the distance of this order statistic from a2 is at most θ in expectation, where j = n − c + 1. Lemma B.7 therefore gives CQ Uj:n n−c+1 θ E[(Hs,c − a2 )+ | N = n] ≤ C , n ≥ c. n+1 √ On the event n ≥ c, and for √ all states with |xs (c)| ≤ A0 log s, we have n + 1 ≥ c ≥ (q/2)s for all large s, because c = qs + O( s log s). Hence
E[(Hs,c − a2 )+ ] ≤ Cs−θ E[(N − c + 1)θ+ ]. The positive-part moment bound of Lemma A.5, applied with exponent θ, gives E[(N − c + 1)θ+ ] ≤ Csθ/2 (1 + u)θ , which proves (111). Lemma D.5 (Gap margin √ for the offline marginal). Under Assumption B.1 with any β ≥ 0, let θ = 1/(β + 1) and fix A0 < θ. There are constants cG√> 0 and sG < ∞, depending also on A0 , such that, for all s ≥ sG and all c satisfying |xs (c)| ≤ A0 log s, 2 dist τs (c), {b1 , a2 } ≥ cG s−A0 /2 (log s)−1/2 . (113) Proof. We prove the claim for the case xs (c) ≤ 0. Put u = |xs (c)|. Since Hs,c ≤ b1 on {N < c} and Hs,c ≥ a2 on {N ≥ c}, a2 − τs (c) = E[(a2 − Hs,c )1{N <c} ] − E[(Hs,c − a2 )1{N ≥c} ] ≥ GP(N < c) − E[(Hs,c − a2 )+ ]. (114) By Lemma A.3, 2
e−u /2 2 P(N < c) ≥ c0 ≥ c0 s−A0 /2 (log s)−1/2 , 1+u √ where the final inequality uses u ≤ A0 log s. By Lemma D.4, E[(Hs,c − a2 )+ ] ≤ Cs−θ/2 (1 + u)θ ≤ Cs−θ/2 (log s)θ/2 . Because A20 < θ,
(115)
(116)
2 s−θ/2 (log s)θ/2 = o s−A0 /2 (log s)−1/2 .
Combining (114)–(116) gives 2
a2 − τs (c) ≥ cs−A0 /2 (log s)−1/2 43
(117)
for all sufficiently large s. It remains to check that the opposite edge b1 is not close. On the same side, τs (c) − b1 ≥ GP(N ≥ c) − E[(b1 − Hs,c )+ ].
(118)
Since xs (c) ≤ 0, the event {N ≥ c} has probability bounded below by a positive constant, uniformly in the present range: c − µs √ = xs (c) + O(s−1/2 ) ≤ O(s−1/2 ), σ s so Berry–Esseen gives P(N ≥ c) ≥ c1 > 0 for all large s. The second term in (118) is o(1) by Lemma D.4. Thus τs (c) − b1 ≥ Gc1 /2 for large s, which is stronger than (113). The case xs (c) ≥ 0 is identical after interchanging the two support intervals and the two events {N ≥ c} and {N < c}. Lemma D.6 (Activity of neighboring states). If at least one of Bs (c),
Bs−1 (c),
Bs−1 (c − 1)
is nonzero, then for all sufficiently large s, |xs (c)| ≤ α2
p log s + 1.
(119)
p log s.
(120)
In particular, |xs (c)| ≤ A
Proof. If Bs (c)p̸= 0, then (119) follows from the support of Gs . Suppose Bs−1 (c) ̸= 0. Then |xs−1 (c)| ≤ α2 log(s − 1). By Lemma C.1, xs−1 (c) = xs (c) + O(s−1/2 ) + O(|xs (c)|/s). p √ √ √ Since log(s − 1) = log s + o(1) and log s → ∞, rearranging gives |xs (c)| ≤ α2 log s + 1 for all large s. The argument for Bs−1 (c − 1) ̸= 0 is the same. Finally, because α2 < A, the stronger bound (119) implies (120) for all sufficiently large s. Lemma D.7 (First difference and gap margin). For the certificate (103), fix any η0 < ∞. There are CD < ∞ and sD < ∞, uniform for 0 < η ≤ η0 , such that whenever s ≥ sD and a neighboring state is active, |Ds (c)| ≤ CD ηs−θ/2 (log s)θ . (121) Moreover, for all sufficiently large s, τs (c) − Ds (c) ∈ (b1 , a2 ).
(122)
∆(τs (c) − Ds (c)) = 0.
(123)
Hence Proof. If both predecessor values Bs−1 (c) and Bs−1 (c − 1) vanish, then Ds (c) = 0 and (121) is immediate. Otherwise at least one predecessor value is nonzero. By Lemma D.6, the active predecessor coordinate is within the support band enlarged by one. The two predecessor coordinates differ by O(s−1/2 ), so the whole line segment between them lies in the active range enlarged by one for all large s. Hence the mean-value argument in Corollary C.4 applies. Using the global first-derivative bound in Lemma D.2, |Ds (c)| ≤ Cηsγ s−1/2 (log s)θ = Cηs−θ/2 (log s)θ , 44
which proves (121). By Lemma D.6, the state lies in the range of Lemma D.5 with A0 = A. 2 Therefore the offline marginal has gap margin at least cG s−A /2 (log s)−1/2 . Since A2 < θ, s−θ/2 (log s)θ 2 = s−(θ−A )/2 (log s)θ+1/2 −→ 0. 2 /2 −A −1/2 s (log s) Thus, after increasing sD if necessary, uniformly for 0 < η ≤ η0 the perturbation Ds (c) is smaller than half the distance from τs (c) to the two gap boundaries. This proves (122). Since ∆ vanishes on the gap, (123) follows.
D.3
Drift and verification of the Bellman certificate inequality
We bound the affine-transport drift of the certificate by applying the finite-difference expansion from Appendix C. The two regions below isolate the harmonic cancellation that motivates the profile. Lemma D.8 (Drift of the harmonic certificate). There is a constant CM < ∞ such that, whenever a neighboring state is active, Ms (c) ≥ −CM ηsγ−1 (1 + |xs (c)|)1+θ . (124) √ √ Proof. Let x = xs (c). By Lemma D.6, |x| ≤ α2 log s + 1 ≤ A log s for all large s, so the standard-scale expansion of Lemma C.2 applies with as = sγ and profile Gs . Since (s − 1)γ − sγ = −γsγ−1 + O(sγ−2 ), we can rewrite the expansion as Ms (c) = ηsγ−1
i 1 G′′s (x) + xG′s (x) − γGs (x) + ηsγ Gs−1 (x) − Gs (x) + Rs,c , 2 2
h1
(125)
where Rs,c is bounded by the error terms in (84), with as = sγ , together with the additional lower-order term Cηsγ−2 |Gs (x)|. This additional term is the O(sγ−2 )Gs (x) remainder from expanding (s − 1)γ − sγ . We show that every term on the right of√(125) is bounded below by the right side of (124). First suppose |x| ≤ α1 log s − 1. Then the unit neighborhood of x lies in the core for large s, and Gs = (log s)θ Hγ there. The leading operator term in (125) is exactly zero by Lemma D.1. The time-variation bound (108) gives ηsγ |Gs−1 (x) − Gs (x)| ≤ Cηsγ−1 (log s)θ−1 (1 + |x|)2γ . Because θ − 1 < 0 and 1 + θ > 2γ, this is at most Cηsγ−1 (1 + |x|)1+θ . √ The error terms in (84) are smaller. Using (105), (107), and |x| ≤ O( log s), their contribution divided by ηsγ−1 is bounded by a sum of terms of the form (log s)1+θ , s
(log s)1/2+θ √ , s
(log s)(1+θ)/2 , s
45
(log s)(2+θ)/2 . s
The last two terms include the time-difference errors, the cross term added in Lemma C.2, and the O(ηsγ−2 |Gs (x)|) contribution above. All displayed terms are o(1) and hence the corresponding γ−1 (1 + |x|)1+θ . Thus (124) holds in the core. contributions to Ms √ (c) are bounded by Cηs √ Now suppose α1 log s − 1 < |x| ≤ α2 log s + 1. Then (1 + |x|)1+θ ≍ (log s)(1+θ)/2 . The collar bounds in Lemma D.2 imply 1 ′′ 1 Gs (x) + xG′s (x) − γGs (x) ≤ C(log s)(1+θ)/2 . 2 2 The time-variation term is at most Cηsγ−1 (log s)(1+θ)/2 by (107). The remainder terms in (84), including the cross term involving Gs−1 − Gs , and the√additional O(ηsγ−2 |Gs (x)|) term above are also bounded by Cηsγ−1 (log s)(1+θ)/2 because √ |x| = O( log s), |(s − 1)γ /sγ − 1| = O(1/s), and the profile derivatives have at most polynomial-in- log s size. Since (log s)(1+θ)/2 ≍ (1 + |x|)1+θ in this region, (124) follows. Proposition D.9 (Feasibility of the gapped harmonic certificate). There exist s0 < ∞ and η0 > 0 such that, for every η ∈ (0, η0 ], the certificate (103) satisfies the Bellman certificate inequality (13) for every s > s0 and 1 ≤ c < s. Proof. Fix s and c. If all three neighboring certificate values Bs (c),
Bs−1 (c),
Bs−1 (c − 1)
are zero, then Ms (c) = 0 and Ds (c) = 0. The Bellman certificate inequality becomes E∆(Hs,c ) − ∆(τs (c)) ≥ 0, which is the offline Jensen slack from Lemma 3.3. It remains to treat the case in which a neighboring state is active. Lemma D.7 gives ∆(τs (c) − Ds (c)) = 0. Therefore the source term in the Bellman certificate inequality is simply Ss (c, Ds (c)) = E∆(Hs,c ). By Lemmas D.6 and D.3, Ss (c, Ds (c)) ≥ cS sγ−1 (1 + |xs (c)|)1+θ . By Lemma D.8, Ms (c) ≥ −CM ηsγ−1 (1 + |xs (c)|)1+θ . Choose η0 ≤ cS /(2CM ) and choose s0 large enough that all preceding lemmas apply for s > s0 . Then cS Ms (c) + Ss (c, Ds (c)) ≥ sγ−1 (1 + |xs (c)|)1+θ ≥ 0. 2 This is exactly (13).
D.4
Shifted capacity lower bound
Theorem D.10 (Gapped lower bound at shifted capacity, β > 0). Assume the two-support gapped model and Assumption B.1 with β > 0. There is ᾱ > 0 such that, for every fixed α ∈ (0, ᾱ), there exists cα > 0 for which j k p ≥ cα T γ (log T )(β+2)/(2(β+1)) (126) BT⋆ qT + ασ T log T for all sufficiently large T . 46
Proof. Let s0 and η0 be as in Proposition D.9. By Corollary 3.6, after possibly reducing η ∈ (0, η0 ], the certificate satisfies the base condition at time s0 . Take ᾱ := α1 /2 and fix α ∈ (0, ᾱ). Let k j p (α) kT := qT + ασ T log T . Proposition D.9 verifies the Bellman certificate inequality for all later times, so B is feasible for (α) P(T, kT , s0 ) for all sufficiently large T . Proposition 3.4 gives (α)
(α)
(α)
BT⋆ (kT ) = Regret(T, kT ; F ) ≥ BT (kT ). Then (α)
xT (kT ) = α
p log T + o(1).
Since α < α1 , the cutoff is equal to one for all large T . By the large-x asymptotic in Lemma D.1, p Hγ (α log T + o(1)) ≥ cα (log T )γ for all large T ; the o(1) shift is negligible because α > 0 is fixed. Absorbing the fixed certificate multiplier η into cα , we obtain (α) BT (kT ) ≥ cα T γ (log T )θ+γ . Using θ + γ = (1 + θ)/2, this becomes (α)
BT (kT ) ≥ cα T γ (log T )(1+θ)/2 . Finally, 1+θ β+2 = . 2 2(β + 1) Combining this with the certified lower bound above gives (126).
E
Moderate-scale finite-difference details for the bounded-density case
This appendix records the finite-difference expansions behind Lemma 4.2. They are the asymptotic calculations used in the two-uniform proof. Throughout the appendix, write d = ds (c) and z = zs (c), with ds and zs defined in (29)–(30). The profile φs is the slow-tail profile of Lemma 4.1.
E.1
Scalar expansions
Lemma E.1 (Scalar s-asymptotics). As s → ∞, 2 log s log s (log(s − 1)) − (log s) = − +O , s s2 √ σ s log s 1 1 p =1+ + + O(s−2 ), 2s 2s log s σ (s − 1) log(s − 1) (log(s − 1))2 2 1 = 1 − + O . (log s)2 s log s s2 log s 2
2
47
(127) (128) (129)
Proof. The identity log(s − 1) = log s + log(1 − 1/s) = log s − 1/s + O(s−2 ) implies (127) by squaring. Since the square of the normalizer is σ 2 s log s, log s σ 2 s log s s 1 1 −2 2 −1 = = 1 + + O(s ) 1+ + O((s log s) ) , σ 2 (s − 1) log(s − 1) s − 1 log(s − 1) s s log s and taking square roots gives (128). Finally, log(s − 1)/ log s = 1 − 1/(s log s) + O((s2 log s)−1 ), and squaring gives (129).
E.2
Sign-stable predecessor representation
Lemma E.2 (Sign-stable representation). Fix α0 > 0. For all sufficiently large s, if zs (c) ≥ α0 , then the two predecessor deviations ds (c) + q and ds (c) − (1 − q) have the same sign as ds (c). Let ξ be the two-point random variable ξ = q sgn(ds (c))
with probability 1 − q,
ξ = −(1 − q) sgn(ds (c))
with probability q.
Then Eξ = 0, Eξ 2 = σ 2 , |ξ| ≤ 1, and, with |ds (c)| + ξ , Zs := p σ (s − 1) log(s − 1) one has (1 − q)φs−1 (zs−1 (c)) + qφs−1 (zs−1 (c − 1)) = Eφs−1 (Zs ). (130) √ Proof. If zs (c) ≥ α0 , then |ds (c)| = zs (c)σ s log s → ∞. Thus, for all large s, both predecessor deviations have the sign of ds (c), and |ds (c) + q| = |ds (c)| + q sgn(ds (c)),
|ds (c) − (1 − q)| = |ds (c)| − (1 − q) sgn(ds (c)).
The moment identities for ξ are immediate. The two values taken by Zs are precisely zs−1 (c) and zs−1 (c − 1) with probabilities 1 − q and q, respectively, proving (130). Lemma E.3 (Moments of the predecessor shift). Let Zs be as in Lemma E.2, set δZ := Zs − z, p where z = zs (c), and assume z ≤ C0 s/(log s) for a fixed constant C0 . Then ξ z Zs = z + √ + + Rs , σ s log s 2s
|Rs | ≤ C
1+z , s log s
(131)
and z 1+z EδZ = +O , 2s s log s 1 1 + z2 1+z 2 E(δZ) = +O + , s log s s2 (s log s)3/2 E|δZ|3 = O((s log s)−3/2 ). 48
(132) (133) (134)
Proof. By Lemma E.1, √ σ s log s 1 ξ ξ 1 −2 p 1+ Zs = z + √ = z+ √ + + O(s ) . 2s 2s log s σ s log s σ (s − 1) log(s − 1) σ s log s √ √ This gives (131). The omitted term involving ξ/(2sσ s log s) is O((s3/2 log s)−1 ), which is dominated by (1 + z)/(s log s) on the stated range. Taking √ expectations and using Eξ = 0 gives (132). Squaring (131), using Eξ 2 = σ 2 and the identity (σ s log s)2 = σ 2 s log s, gives the leading term in (133). The deterministic√square of the remainder contributes O((1 + z)2 /(s2 (log s)2 )), and the cross-term between ξ/(σ s log s) and Rs contributes O((1 + z)/(s log s)3/2 ) by Cauchy– Schwarz; both are covered by the displayed error bound. The third-moment bound follows from p 3 3 3 3 |a + b + c| ≤ 27(|a| + |b| + |c| ) and the assumed range z ≤ C0 s/(log s).
E.3
Bounded-range Taylor expansion
Lemma E.4 (Taylor expansion on a bounded z-range). Let Zs be as above and suppose z ∈ [α0 , α5 ]. Then z 1 1 (log(s − 1))2 E φs−1 (Zs ) − φs−1 (z) = (log s)2 φ′s (z) + log sφ′′s (z) + RT , (135) 2s 2 s where log s |RT | ≤ Cλ φs (z) . (136) s Proof. Taylor’s theorem gives 1 φs−1 (Zs ) − φs−1 (z) = φ′s−1 (z)δZ + φ′′s−1 (z)(δZ)2 + Θs , 2 with |Θs | ≤ Cλ |δZ|3 uniformly on [α0 , α5 ], by Lemma 4.1. Taking expectations and using (132)– (134), z 1 1 E[φs−1 (Zs ) − φs−1 (z)] = φ′s−1 (z) + φ′′s−1 (z) + R1 , 2s 2 s log s where (log(s − 1))2 |R1 | ≤ Cλ φs (z) log s/s. The time-variation bounds (28) allow φ′s−1 and φ′′s−1 to be replaced by φ′s and φ′′s ; after multiplication by (log(s − 1))2 , the resulting contribution is absorbed by the same remainder. Multiplying by (log(s − 1))2 = (log s)2 (1 + O((s log s)−1 )) proves (135).
E.4
Ratio expansion for large deviations
Lemma E.5 (Ratio expansion for z ≥ α5 ). Let Zs be as in Lemma E.2. Suppose p z ∈ [α5 , C0 s/(log s)] for a fixed C0 < ∞. Then Zs ≥ α4 almost surely for all sufficiently large s, and φs−1 (Zs ) λz 1+z 1 E =1− + Oλ + . φs (z) 2s log s s(log s)2 s(log s)3
(137)
Proof. Since z ≥ α5 > α4 and |Zs − z| = o(1) uniformly in the displayed range, all arguments lie in [α4 , ∞) for large s. In that region, φs (w) = φs (α4 ) exp{−λ(w − α4 )/ log s}. 49
Thus φs−1 (α4 ) λ 1 1 φs−1 (Zs ) (Zs − α4 ) . = exp − (Zs − z) − λ − φs (z) φs (α4 ) log s log(s − 1) log s By the time-variation bound in Lemma 4.1, the prefactor is 1 + Oλ ((s(log s)2 )−1 ), and 1 1 − = O((s(log s)2 )−1 ). log(s − 1) log s Write the exponent as As + Bs , where λ As := − (Zs − z), log s
Bs := −λ
1 1 − log(s − 1) log s
(Zs − α4 ).
The moment estimates in Lemma E.3 imply λz 1+z 1 z2 2 EAs = − + Oλ , Eas (c) = Oλ + . 2s log s s(log s)2 s(log s)3 s2 (log s)2 p In the displayed range z ≤ C0 s/(log s), the final term is O((s(log s)3 )−1 ). Also |Bs | ≤ Cλ
1 + z + |Zs − z| , s(log s)2
so E|Bs | = Oλ ((1 + z)/(s(log s)2 )). The third-order remainder in the exponential is bounded by Oλ (E|As |3 + E|Bs |2 + E|As Bs |), which is absorbed by Oλ ((1 + z)/(s(log s)2 ) + 1/(s(log s)3 )). Hence λz 1+z 1 As +Bs Ee =1− + Oλ + . 2s log s s(log s)2 s(log s)3 Multiplying by the prefactor 1 + Oλ ((s(log s)2 )−1 ) proves the lemma.
50