1 Introduction
Small random perturbations of stable deterministic systems often produce a characteristic metastable behaviour: the process remains close to an attracting state for a long time and then leaves its neighbourhood through a rare fluctuation. In population models this mechanism is related to persistence near a carrying capacity and to the onset of extinction [5–7]. This motivation leads naturally to the study of small-noise autoregressive recursions.
The model considered here is
where the innovations are independent standard Gaussian random variables and $\varepsilon \gt 0$ is small. We study the first exit time ${\tau _{\varepsilon }}:=\min \{n\ge 1:|{X_{n}^{\varepsilon }}|\ge 1\}$ from $(-1,1)$. The large-deviation method of Klebaner and Liptser [12] (see [17] for the general theory) reduces an exponential upper bound for ${\mathbb{E}_{0}}{\tau _{\varepsilon }}$ to an infimum, over finite horizons, of quadratic path actions. The resulting constant is a discrete quasipotential: it measures the least noise energy required to drive the deterministic system from the stable fixed point to the boundary. The present paper evaluates this variational constant exactly for a continuous two-slope map.
(1.1)
\[{X_{n+1}^{\varepsilon }}=h({X_{n}^{\varepsilon }})+\varepsilon {\xi _{n+1}},\hspace{20.0pt}{X_{0}^{\varepsilon }}=0,\]For the linear autoregression $h(x)=\mathit{px}$, $|p|\lt 1$, the variational problem is explicit and gives the sharp value $(1-{p^{2}})/2$. The same large-deviation framework has been developed for past-dependent recursions, moderate deviations, multivariate autoregressions, ARMA processes, and non-Gaussian noise [12, 13, 11, 14, 9]. Complementary approaches to first-passage and level-crossing questions use martingale and analytic methods [16, 15, 4, 2, 3]. Piecewise-linear and threshold autoregressions are classical nonlinear time-series models [1], but their exit variational problems are much less explicit than in the linear case.
Högnäs and Jung [10] studied several nonlinear and piecewise-linear autoregressive maps and obtained explicit bounds in a number of special cases; see also [8] for exit times and invariant distributions of a related stochastic difference equation. For the continuous two-slope family considered below, their formulas cover the boundary cases in which one of the two slopes vanishes. The case in which both slopes are nonzero was not evaluated. This is the remaining case in which the breakpoint constraints genuinely enter the variational minimization.
We solve this remaining case over the full admissible parameter range. The analysis separates two classes of candidate minimizing paths: paths having a vertex at the breakpoint and paths with no internal vertex at the breakpoint. We compute the least cost in both classes, determine exactly when the stationary candidate in the second class satisfies the required inequalities, and compare it with the best breakpoint path. This yields a complete parameter classification involving an interior stationary value, a breakpoint value, or the linear value $(1-{p^{2}})/2$. We also treat the remaining boundary regimes $q=1$ and $p=0,\hspace{2.5pt}q\gt 1$, as well as the limiting case $f(1)=1$, and determine whether the variational infimum is attained at a finite horizon.
The condition studied in this paper is that the graph of the positive branch lies strictly below the diagonal, $f(x)\lt x$ for $0\lt x\lt 1$. It guarantees deterministic attraction toward the origin from every interior initial state, but it does not require both slopes to be smaller than one; in particular, an expanding second slope is allowed when the affine branch still remains below the diagonal. The regimes in which
the graph meets or rises above the diagonal inside $(0,1)$ have different deterministic and variational structures and are therefore left for separate treatment.
The paper is organized as follows. Section 2 formulates the exit-time variational problem, introduces the two-slope family and the monotone reduction, recalls the previously known boundary cases, and states the main classification. Section 3 proves the affine one-segment minimization used throughout, and Sections 4 and 5 analyze, respectively, paths that hit the breakpoint and paths with no internal vertex there. Section 6 states the key admissibility and comparison results needed for the constrained classification, Section 7 proves the main theorem, and Section 8 treats the remaining boundary regimes. The detailed proofs of the admissibility and comparison results are given in Section 9.
2 Variational formulation and proof architecture
2.1 Exit-time variational problem
Let $h:[-1,1]\to [-1,1]$ be continuous, with $h(0)=0$ and $|h(x)|\lt |x|$ for $0\lt |x|\lt 1$. For a finite path $\mathbf{y}=({y_{0}},\dots ,{y_{N}})$, define the quadratic action
The associated exit-time variational cost is
The large-deviation reduction gives the following statement, which is the only probabilistic result from [12, 10] used in the variational analysis below. We emphasize that no matching lower bound is asserted here for the nonlinear maps of this paper.
(2.1)
\[{I_{N}}(\mathbf{y};h):=\frac{1}{2}{\sum \limits_{j=1}^{N}}{\Bigl({y_{j}}-h({y_{j-1}})\Bigr)^{2}}.\](2.2)
\[S(h):=\inf \limits_{N\ge 1}\hspace{2.5pt}\min \limits_{\substack{{y_{0}}=0,\hspace{2.5pt}|{y_{N}}|=1\\ {} |{y_{j}}|\lt 1\hspace{2.5pt}(1\le j\lt N)}}{I_{N}}(\mathbf{y};h).\]For $h(x)=\mathit{px}$, $|p|\lt 1$, direct minimization gives $S(h)=(1-{p^{2}})/2$, recovering the classical linear value. The problem in the nonlinear setting is thus to compute $S(h)$, keeping this exact variational value distinct from a matching lower bound for the mean exit-time exponent, which is not presently available for the maps considered here.
2.2 Two-slope family and monotone reduction
We now specialize the map h to the two-slope family and fix the notation. Let $\mathcal{F}$ be the family of continuous two-slope functions $f:[0,1]\to [0,1]$ of the form
which additionally satisfy
Continuity at c is built into (2.3), because the slope-p and slope-q pieces both take the value pc there.
(2.3)
\[f(x)=\left\{\begin{array}{l@{\hskip0pt}l}\mathit{px},\hspace{10.0pt}& 0\le x\le c,\\ {} \mathit{qx}+c(p-q),\hspace{10.0pt}& c\le x\le 1,\end{array}\right.\hspace{20.0pt}0\le p\lt 1,\hspace{10.0pt}q\ge 0,\hspace{10.0pt}0\lt c\lt 1,\]For $f\in \mathcal{F}$, the exit-time problem for (1.1) is driven by the symmetric extension of f to $[-1,1]$ defined in (2.5) below, whose quasipotential (2.2) is the object to be evaluated. We record, in the notation used throughout, the reduction of Högnäs and Jung [10] of this two-sided problem to a one-sided minimization over monotone paths. Take arbitrary $f,g\in \mathcal{F}$ and define a function on $[-1,1]$ by
Because $f(0)=g(0)=0$, this function is continuous at the origin; moreover it is increasing and satisfies $|{h_{f,g}}(x)|\lt |x|$ for $x\in (-1,1)\setminus \{0\}$. Write, for the one-sided monotone problem,
Using Lemmas 1 and 3 of [10], the two-sided N-step problem decomposes into these one-sided monotone problems:
In particular, for the symmetric extension ${h_{f,f}}$, the two-sided N-step problem has value ${S_{N}}(f)$. Taking the infimum over N in (2.7) identifies the quasipotential (2.2) of the introduction with these one-sided costs, $S({h_{f,g}})=\min \{S(f),S(g)\}$ and $S({h_{f,f}})=S(f)$, so that Theorem 2.1 applies with the constant $S(f)$ evaluated below.
(2.5)
\[{h_{f,g}}(x)=\left\{\begin{array}{l@{\hskip0pt}l}f(x),\hspace{10.0pt}& 0\le x\le 1,\\ {} -g(-x),\hspace{10.0pt}& -1\le x\le 0.\end{array}\right.\](2.6)
\[{S_{N}}(f):=\min \limits_{0={y_{0}}\le {y_{1}}\le \cdots \le {y_{N}}=1}{I_{N}}(\mathbf{y};f),\hspace{20.0pt}S(f):=\inf \limits_{N\ge 1}{S_{N}}(f).\](2.7)
\[\min \limits_{\substack{{y_{0}}=0,\hspace{2.5pt}|{y_{N}}|=1\\ {} |{y_{j}}|\lt 1,\hspace{2.5pt}1\le j\lt N}}{I_{N}}(\mathbf{y};{h_{f,g}})=\min \{{S_{N}}(f),{S_{N}}(g)\}.\]2.3 Previously known boundary cases
Högnäs and Jung [10] evaluated $S(f)$ in the two boundary cases of the family (2.3), where one of the slopes vanishes. We restate their results in the present notation.
Proposition 2.2 (Högnäs–Jung [10]).
Proposition 2.3 (Högnäs–Jung [10]).
These two propositions cover the boundary cases $p=0,\hspace{2.5pt}0\le q\le 1$ and $q=0$ of the family (2.3); the case in which both slopes are nonzero is covered by neither, and it is the subject of this paper.
2.4 Main classification and boundary results
We now state the complete classification of the variational problem (2.6) for a general continuous two-slope map. A minimizing path belongs to one of two classes according to whether it has a vertex at the breakpoint c: a path that hits c has a cost $\hat{S}$, and a path with no internal vertex at c has a cost ${S_{m}}$, and the theorem compares the two. We record these values and the parameters that govern them. Set
For $m\in {\mathbb{Z}_{\ge 0}}$, the stationary calculation for paths with no internal vertex at c gives the limiting algebraic quantities
with ${S_{0}}=(1-{p^{2}})/2$ and ${Y_{0}}=1-{p^{2}}$. An index satisfies the limiting feasibility condition if $c(1-{p^{2}})\lt {Y_{m}}\lt c(1-{p^{2}})/p$, and we write $\mathcal{M}:=\{m\in {\mathbb{Z}_{\ge 0}}:c(1-{p^{2}})\lt {Y_{m}}\lt c(1-{p^{2}})/p\}$ for this limiting feasibility set; the full nondecreasing-path admissibility of the indices used in the theorem is established later. We also introduce the real number ${m_{0}}:={\log _{q}}\Bigl(c(1-{p^{2}})/((p+q)\Delta )\Bigr)$ and, for $n\ge 1$, the breakpoint values
and, as proved in Section 4, the actual infimum over paths that hit the breakpoint is
The following is our main result.
(2.12)
\[{S_{m}}:=\frac{(1+q){\Bigl(\Delta -c(q-p){q^{m}}\Bigr)^{2}}}{2(1-q)\Bigl(1-\lambda {q^{2m}}\Bigr)},\hspace{20.0pt}{Y_{m}}:=\frac{(1+q)\hspace{1.67pt}{q^{m}}\Bigl(\Delta -c(q-p){q^{m}}\Bigr)}{1-\lambda {q^{2m}}},\](2.13)
\[{\hat{S}_{n}}:=\frac{1-{p^{2}}}{2}{c^{2}}+\frac{(1+q){\Bigl(\Delta -c(1-p){q^{n}}\Bigr)^{2}}}{2(1-q)\Bigl(1-{q^{2n}}\Bigr)},\]Theorem 2.4.
Assume $0\lt p\lt 1$, $q\gt 0$, $q\ne p,1$, and $\Delta \gt 0$. Then
\[S(f)=\left\{\begin{array}{l@{\hskip0pt}l}{S_{{m^{\ast }}}},\hspace{10.0pt}& q\gt p,\hspace{2.5pt}c\lt {c_{0}},\\ {} {S_{{m^{\ast }}}},\hspace{10.0pt}& q\lt p,\hspace{2.5pt}c\lt {c_{0}},\hspace{2.5pt}\mathcal{M}=\{{m^{\ast }}\},\\ {} \hat{S},\hspace{10.0pt}& q\lt p,\hspace{2.5pt}c\lt {c_{0}},\hspace{2.5pt}\mathcal{M}=\mathrm{\varnothing },\\ {} (1-{p^{2}})/2,\hspace{10.0pt}& c\ge {c_{0}}.\end{array}\right.\]
Here ${m^{\ast }}\in \{\lfloor {m_{0}}\rfloor ,\lceil {m_{0}}\rceil \}$: when $q\gt p$ it is whichever of the two gives the smaller value of ${S_{m}}$, and when $q\lt p$ it is whichever of the two is feasible—at most one is—so that $\mathcal{M}=\{{m^{\ast }}\}$ if such an index exists and $\mathcal{M}=\mathrm{\varnothing }$ otherwise. None of the displayed values of $S(f)$ is attained at a finite horizon.
Fig. 2
The classification of Theorem 2.4 in the $(c,q)$-plane at a fixed first slope p (here $p=0.7$), computed exactly from the closed forms for ${S_{m}}$, ${Y_{m}}$, and $\hat{S}$. Each colour marks which value $S(f)$ takes: the interior stationary value ${S_{{m^{\ast }}}}$, the breakpoint value $\hat{S}$, the linear value $(1-{p^{2}})/2$ (arising for $c\ge {c_{0}}$), and the excluded area $\Delta \le 0$
The cases $q=p$, $q=0$, and $p=0,q\le 1$ were described above through the results of Klebaner–Liptser and Högnäs–Jung. For completeness, we state here the three remaining boundary results proved in this paper.
Proposition 2.5.
Assume $0\lt p\lt 1$, $q=1$, and $0\lt c\lt 1$, and put $d:=c(1-p)$, $a:=1/(1-{p^{2}})$. If $c\ge (1+p)/2$, then $S(f)=(1-{p^{2}})/2$. If $c\lt (1+p)/2$, then
the minimum being attained at one of the two integers adjacent to ${m_{1}}:=1/d-2a$. This value is not attained at any finite horizon.
Proposition 2.7.
Assume $0\le p\lt 1$, $0\lt c\lt 1$, and $\Delta =0$, so that $q=(1-\mathit{pc})/(1-c)\gt 1$. Then $c\lt {c_{0}}$ and
\[S(f)=\lim \limits_{m\to \mathrm{\infty }}{S_{m}}=\frac{(1-{p^{2}})({q^{2}}-1)}{2({q^{2}}-{p^{2}})}.\]
This value is not attained at a finite horizon. In particular, for $p=0$, $S(f)=c-{c^{2}}/2$.
Proof architecture. Every admissible path belongs to exactly one of two classes: (I) at least one vertex satisfies ${y_{j}}=c$; (II) every internal vertex satisfies ${y_{j}}\ne c$. These cases require different arguments. In Case I, fixing a vertex at c splits the action into two independent minimizations; we therefore analyze this case first and denote its optimal value by $\hat{S}$. In Case II, there is a unique index k with ${y_{k}}\lt c\lt {y_{k+1}}$; we first compute the stationary solution of the quadratic equations, and only afterwards verify the breakpoint inequalities, monotonicity, and comparison with Case I. The final theorem compares the best feasible limiting value with $\hat{S}$. Both the decomposition of Case I and the boundary analyses reduce to a single affine minimization, isolated as the one-segment minimization of Section 3; the structural results needed for the Case II comparison are stated in Section 6 and proved in Section 9.
3 A one-segment minimization
The analysis of Case I and of the boundary regimes repeatedly reduces to minimizing the action over a single affine piece, and we isolate that minimization here. Let $a\lt b$ and $g(x)=\mathit{\alpha x}+\gamma $, where $\alpha \gt 0$ and $\alpha \ne 1$; for $N\ge 1$, denote the constrained and unconstrained minima, respectively, by
\[\begin{array}{r@{\hskip0pt}l}\displaystyle {I_{N}}(a,b;g)& \displaystyle :=\min \limits_{a={x_{0}}\le \cdots \le {x_{N}}=b}\frac{1}{2}{\sum \limits_{i=1}^{N}}{\Bigl({x_{i}}-g({x_{i-1}})\Bigr)^{2}},\\ {} \displaystyle {J_{N}}(a,b;g)& \displaystyle :=\min \limits_{\substack{{x_{0}}=a,\hspace{2.5pt}{x_{N}}=b\\ {} {x_{1}},\dots ,{x_{N-1}}\in \mathbb{R}}}\frac{1}{2}{\sum \limits_{i=1}^{N}}{\Bigl({x_{i}}-g({x_{i-1}})\Bigr)^{2}}.\end{array}\]
Lemma 3.1.
Suppose that $g(x)\le x$ on $[a,b]$, and set ${d_{a}}:=a-g(a)$, ${d_{b}}:=b-g(b)$. Then, for every $N\ge 1$, the unrestricted minimum is
If ${d_{a}}=0$, then necessarily $0\lt \alpha \lt 1$, and
If ${d_{b}}=0$, then necessarily $\alpha \gt 1$, and
Finally, if ${d_{a}}{d_{b}}\ne 0$, define ${N_{0}}:=\max \{1,\lfloor {\log _{\alpha }}({d_{a}}/{d_{b}})\rfloor \}$. Then
(3.1)
\[{J_{N}}(a,b;g)=\frac{1-{\alpha ^{2}}}{2{(1-\alpha )^{2}}}\frac{{\Bigl({d_{b}}-{d_{a}}{\alpha ^{N}}\Bigr)^{2}}}{1-{\alpha ^{2N}}}.\]Proof.
Fix $N\ge 1$ and write ${e_{i}}:={x_{i}}-g({x_{i-1}})={x_{i}}-\alpha {x_{i-1}}-\gamma $ for $i=1,\dots ,N$. Multiplying by ${\alpha ^{N-i}}$ and summing gives the telescoping identity
so that, by the Cauchy–Schwarz inequality,
and it is unique, the map from the intermediate vertices to the error vector being invertible. Halving the bound proves (3.1).
(3.5)
\[{\sum \limits_{i=1}^{N}}{\alpha ^{N-i}}{e_{i}}=b-{\alpha ^{N}}a-\gamma {\sum \limits_{r=0}^{N-1}}{\alpha ^{r}}=\frac{{d_{b}}-{d_{a}}{\alpha ^{N}}}{1-\alpha },\]
\[{\sum \limits_{i=1}^{N}}{e_{i}^{2}}\ge \frac{{\Bigl({\sum _{i=1}^{N}}{\alpha ^{N-i}}{e_{i}}\Bigr)^{2}}}{{\sum _{i=1}^{N}}{\alpha ^{2(N-i)}}}=\frac{1-{\alpha ^{2}}}{{(1-\alpha )^{2}}}\frac{{\Bigl({d_{b}}-{d_{a}}{\alpha ^{N}}\Bigr)^{2}}}{1-{\alpha ^{2N}}},\]
with equality exactly when the error vector is proportional to $({\alpha ^{N-1}},\dots ,\alpha ,1)$. The endpoint identity (3.5) fixes the proportionality constant, so the unrestricted minimizer satisfies
(3.6)
\[{e_{i}}={x_{i}}-g({x_{i-1}})=\beta {\alpha ^{N-i}},\hspace{10.0pt}i=1,\dots ,N,\hspace{20.0pt}\beta =\frac{1-{\alpha ^{2}}}{1-\alpha }\frac{{d_{b}}-{d_{a}}{\alpha ^{N}}}{1-{\alpha ^{2N}}},\]We next determine when this minimizer is nondecreasing. Since $g(x)\le x$ on $[a,b]$, the endpoint gaps ${d_{a}}$ and ${d_{b}}$ are nonnegative, and
hence ${d_{a}}=0$ forces $0\lt \alpha \lt 1$, and ${d_{b}}=0$ forces $\alpha \gt 1$. Put ${L_{N}}:=({d_{b}}-{d_{a}}{\alpha ^{N}})/(1-{\alpha ^{2N}})$. Iterating (3.6) from ${x_{0}}=a$ and subtracting successive coordinates,
If ${d_{a}}=0$, then $0\lt \alpha \lt 1$ and ${L_{N}}={d_{b}}/(1-{\alpha ^{2N}})\gt 0$, so every increment is positive. If ${d_{b}}=0$, then $\alpha \gt 1$ and ${L_{N}}={d_{a}}{\alpha ^{N}}/({\alpha ^{2N}}-1)\gt 0$; after division by ${\alpha ^{i-1}}$ the right-hand side of (3.8) decreases with i, and its last value ${x_{N}}-{x_{N-1}}={d_{a}}{\alpha ^{N-1}}(1+\alpha )/({\alpha ^{2N}}-1)$ is positive. Thus in both endpoint cases the minimizer is strictly increasing.
(3.8)
\[{x_{i}}-{x_{i-1}}=-{d_{a}}{\alpha ^{i-1}}+{L_{N}}\Bigl({\alpha ^{N-i}}+{\alpha ^{N+i-1}}\Bigr),\hspace{20.0pt}i=1,\dots ,N.\]Assume now ${d_{a}}{d_{b}}\gt 0$. If $0\lt \alpha \lt 1$, the normalized increments $({x_{i}}-{x_{i-1}})/{\alpha ^{i-1}}$ increase with i, so only $i=1$ matters: substituting ${L_{N}}$ into ${x_{1}}-{x_{0}}=-{d_{a}}+{L_{N}}({\alpha ^{N-1}}+{\alpha ^{N}})\ge 0$ and clearing the positive denominator $1-{\alpha ^{2N}}$, the condition becomes
If $\alpha \gt 1$, the same normalized increments decrease, so $i=N$ is decisive, and ${x_{N}}-{x_{N-1}}=-{d_{a}}{\alpha ^{N-1}}+{L_{N}}(1+{\alpha ^{2N-1}})\ge 0$ with ${L_{N}}=({d_{a}}{\alpha ^{N}}-{d_{b}})/({\alpha ^{2N}}-1)$ becomes
Thus, when ${d_{a}}{d_{b}}\gt 0$, the unrestricted minimizer is admissible for a given N precisely when the relevant one of (3.9) and (3.10) holds. Neither condition is automatic, and we do not check them yet: we first carry out the minimization over N, which singles out two candidate integers, and then return at the end of the proof to verify the appropriate condition at those two integers only.
We now minimize over N. If ${d_{a}}=0$, then (3.1) reads ${J_{N}}(a,b;g)=\frac{1+\alpha }{2(1-\alpha )}\frac{{d_{b}^{2}}}{1-{\alpha ^{2N}}}$, which decreases strictly to the value in (3.2); if ${d_{b}}=0$, then $\alpha \gt 1$ and
\[{J_{N}}(a,b;g)=\frac{1+\alpha }{2(\alpha -1)}{d_{a}^{2}}\frac{{\alpha ^{2N}}}{{\alpha ^{2N}}-1}\downarrow \frac{1+\alpha }{2(\alpha -1)}{d_{a}^{2}}.\]
In both cases the unrestricted minimizer is nondecreasing for every N, so ${I_{N}}(a,b;g)={J_{N}}(a,b;g)$; this proves (3.2) and (3.3) together with the nonattainment statements.Suppose finally that ${d_{a}}{d_{b}}\gt 0$. Extend the right-hand side of (3.1) to real $x\gt 0$ and set $z={\alpha ^{x}}$; apart from its constant prefactor it becomes ${({d_{b}}-{d_{a}}z)^{2}}/(1-{z^{2}})$, with
For $0\lt \alpha \lt 1$, (3.7) gives $0\lt {d_{a}}\lt {d_{b}}$, and $z={d_{a}}/{d_{b}}$ is the only critical point in the admissible range $0\lt z\lt 1$; for $\alpha \gt 1$ one has ${d_{a}}\gt {d_{b}}\gt 0$, and the same point is the only critical point in the admissible range $z\gt 1$. Taking into account the direction of $z={\alpha ^{x}}$ and, for $\alpha \gt 1$, the sign of the prefactor in (3.1), the real-variable cost is in both cases strictly decreasing before $\hspace{1.67pt}{N_{\mathrm{r}}}={\log _{\alpha }}({d_{a}}/{d_{b}})$ and strictly increasing afterwards. Its integer minimum is therefore among ${N_{0}}$ and ${N_{0}}+1$, with ${N_{0}}$ as in Lemma 3.1; if $\hspace{1.67pt}{N_{\mathrm{r}}}\lt 1$, it occurs at $N=1$.
(3.11)
\[\frac{d}{\mathit{dz}}\frac{{({d_{b}}-{d_{a}}z)^{2}}}{1-{z^{2}}}=\frac{2({d_{b}}-{d_{a}}z)({d_{b}}z-{d_{a}})}{{(1-{z^{2}})^{2}}}.\]It remains to check the ordering constraint at these two integers. Let $0\lt \alpha \lt 1$ and $\hspace{1.67pt}{N_{\mathrm{r}}}\ge 1$, so that ${\alpha ^{{N_{0}}+1}}\le {d_{a}}/{d_{b}}\le {\alpha ^{{N_{0}}}}$. For $N={N_{0}}$,
\[{d_{a}}\Bigl(1+{\alpha ^{2N-1}}\Bigr)\le {d_{b}}{\alpha ^{N}}\Bigl(1+{\alpha ^{2N-1}}\Bigr)\le {d_{b}}{\alpha ^{N-1}}(1+\alpha ),\]
while for $N={N_{0}}+1$ the same bound, written ${d_{a}}/{d_{b}}\le {\alpha ^{N-1}}$, gives ${d_{a}}(1+{\alpha ^{2N-1}})\le {d_{b}}{\alpha ^{N-1}}(1+\alpha )$ directly; thus (3.9) holds at both. Let now $\alpha \gt 1$ and $\hspace{1.67pt}{N_{\mathrm{r}}}\ge 1$, so that ${\alpha ^{{N_{0}}}}\le {d_{a}}/{d_{b}}\le {\alpha ^{{N_{0}}+1}}$. For $N={N_{0}}$ we get ${d_{a}}(1+\alpha )\ge {d_{b}}{\alpha ^{N}}(1+\alpha )\ge {d_{b}}({\alpha ^{N}}+{\alpha ^{1-N}})$, and for $N={N_{0}}+1$, using ${d_{a}}/{d_{b}}\ge {\alpha ^{N-1}}$, ${d_{a}}(1+\alpha )\ge {d_{b}}{\alpha ^{N-1}}(1+\alpha )\ge {d_{b}}({\alpha ^{N}}+{\alpha ^{1-N}})$; thus (3.10) holds at both. If $0\lt \hspace{1.67pt}{N_{\mathrm{r}}}\lt 1$, the optimal one-step path has no internal vertex and is automatically nondecreasing.Therefore an unrestricted minimizer realizing the integer minimum is admissible for the monotone problem, and since ${J_{N}}(a,b;g)\le {I_{N}}(a,b;g)$ for every N, this proves (3.4). □
We keep throughout the distinction just established: for fixed N and ${d_{a}}{d_{b}}\gt 0$, the unrestricted value (3.1) need not equal the constrained value ${I_{N}}(a,b;g)$; the two problems agree only after optimization over N, because at least one of the optimal adjacent integers is admissible.
4 Case I: paths that hit the breakpoint
Assume throughout this section that $0\lt p\lt 1$, $q\gt 0$, $q\ne 1$, and $\Delta \gt 0$. We compute the infimum over nondecreasing paths that hit the breakpoint c; fixing the breakpoint vertex separates the action into two affine one-segment problems.
Lemma 4.1.
Fix $N\ge 2$ and $j\in \{1,\dots ,N-1\}$. Among paths satisfying ${y_{j}}=c$, the two parts of the action can be minimized independently:
(4.1)
\[\begin{array}{r@{\hskip0pt}l}& \displaystyle \min \limits_{\substack{0={y_{0}}\le \cdots \le {y_{N}}=1\\ {} {y_{j}}=c}}{I_{N}}(\mathbf{y};f)\\ {} & \displaystyle \hspace{10.0pt}=\min \limits_{0={y_{0}}\le \cdots \le {y_{j}}=c}\frac{1}{2}{\sum \limits_{i=1}^{j}}{({y_{i}}-f({y_{i-1}}))^{2}}+\min \limits_{c={y_{j}}\le \cdots \le {y_{N}}=1}\frac{1}{2}{\sum \limits_{i=j+1}^{N}}{({y_{i}}-f({y_{i-1}}))^{2}}.\end{array}\]Proof.
With ${y_{0}}=0$, ${y_{j}}=c$, and ${y_{N}}=1$ fixed, write ${A_{j}}({y_{1}},\dots ,{y_{j-1}}):=\frac{1}{2}{\sum _{i=1}^{j}}{({y_{i}}-f({y_{i-1}}))^{2}}$ and ${B_{N-j}}({y_{j+1}},\dots ,{y_{N-1}}):=\frac{1}{2}{\sum _{i=j+1}^{N}}{({y_{i}}-f({y_{i-1}}))^{2}}$. The variables occurring in ${A_{j}}$ and ${B_{N-j}}$ are disjoint, and every admissible full path with ${y_{j}}=c$ satisfies ${I_{N}}(\mathbf{y};f)={A_{j}}+{B_{N-j}}$; hence its action is at least $\min {A_{j}}+\min {B_{N-j}}$. Conversely, the two admissible sets are compact and the two actions continuous, so minimizing left and right subpaths exist, and concatenating them at their common endpoint c gives an admissible full path of action exactly $\min {A_{j}}+\min {B_{N-j}}$. □
Denote by
For the left one-segment problem the endpoint gaps are ${d_{0}}=0$ and ${d_{c}}=c-{g_{p}}(c)=c(1-p)$; the fixed-j minimizer is increasing, and Lemma 3.1 gives
the limit being strict and not attained at a finite left-hand length. For the right one-segment problem the endpoint gaps ${d_{c}}=c-{g_{q}}(c)=c(1-p)$ and ${d_{1}}=1-{g_{q}}(1)=\Delta $ are both positive, and the unconstrained n-step value from Lemma 3.1 is
We compare with the sequence ${\hat{S}_{n}}$ of (2.13), whose second term is, at an arbitrary fixed n, an unrestricted algebraic value whose stationary path need not be nondecreasing; thus ${\hat{S}_{n}}$ is not to be read as an admissible path cost for every n. The minimizer of the real-variable extension of the right one-segment problem is ${x_{\mathrm{b}}}:={\log _{q}}\Bigl(c(1-p)/\Delta \Bigr)\gt 0$, and by Lemma 3.1 the constrained right one-segment minimum is attained at one of the two adjacent integer lengths ${n^{\ast }}$ and ${n^{\ast }}+1$ of (2.14), at which the unrestricted minimizers are themselves nondecreasing. Consequently the algebraic values in (2.13) are attained by admissible paths hitting the breakpoint for the two lengths that determine the minimum.
\[{\mathcal{S}_{\mathrm{b}}}(f):=\inf \limits_{\substack{N\ge 2,\hspace{2.5pt}1\le j\lt N\\ {} 0={y_{0}}\le \cdots \le {y_{N}}=1,\hspace{2.5pt}{y_{j}}=c}}{I_{N}}(\mathbf{y};f)\]
the infimum over the class of paths that hit the breakpoint, put $n:=N-j$, and set ${g_{p}}(x):=\mathit{px}$, ${g_{q}}(x):=\mathit{qx}+c(p-q)$. Since the two positive lengths j and n vary independently, the decomposition lemma yields
(4.2)
\[{\mathcal{S}_{\mathrm{b}}}(f)=\inf \limits_{j\ge 1}{I_{j}}(0,c;{g_{p}})+\inf \limits_{n\ge 1}{I_{n}}(c,1;{g_{q}}).\](4.3)
\[{I_{j}}(0,c;{g_{p}})=\frac{1-{p^{2}}}{2(1-{p^{2j}})}{c^{2}}\downarrow \frac{1-{p^{2}}}{2}{c^{2}}\hspace{20.0pt}(j\to \mathrm{\infty }),\](4.4)
\[{J_{n}}(c,1;{g_{q}})=\frac{(1+q){\Bigl(\Delta -c(1-p){q^{n}}\Bigr)^{2}}}{2(1-q)(1-{q^{2n}})}.\]Proposition 4.2.
The infimum over all paths that hit the breakpoint is
with $\hat{S}$ as in (2.14), and it is not attained by any finite path.
Proof.
Combining (4.2) with (4.3) and the integer-minimization part of Lemma 3.1,
\[{\mathcal{S}_{\mathrm{b}}}(f)=\frac{1-{p^{2}}}{2}{c^{2}}+\min \{{J_{{n^{\ast }}}}(c,1;{g_{q}}),{J_{{n^{\ast }}+1}}(c,1;{g_{q}})\}=\min \{{\hat{S}_{{n^{\ast }}}},{\hat{S}_{{n^{\ast }}+1}}\},\]
which is (4.5). The right one-segment problem has an optimal finite length, but the left contribution in (4.3) approaches its infimum strictly as $j\to \mathrm{\infty }$; therefore no finite full path attains $\hat{S}$. □5 Case II: paths with no vertex at the breakpoint
Throughout this section we work under the assumptions of Theorem 2.4: $0\lt p\lt 1$, $q\gt 0$, $q\ne p,1$, and $\Delta \gt 0$, and we assume that no internal vertex equals c. Since the path is nondecreasing with ${y_{0}}=0\lt c\lt 1={y_{N}}$, there is a unique index $k\in \{0,\dots ,N-1\}$ such that
we write $m:=N-k-1$ for the number of steps on the right piece $[c,1]$. The following lemmas compute the corresponding algebraic stationary path and then determine when it satisfies (5.1). For $m\in {\mathbb{Z}_{\ge 0}}$, put
where an empty sum is zero, so ${N_{0}}=1$ and ${D_{0}}={(1-{p^{2}})^{-1}}$. The quantities ${S_{m}}$ and ${Y_{m}}$ of (2.12) then have the equivalent form
which defines them for every $m\ge 0$; the value ${S_{m}}$ is a Case II action only for indices satisfying the feasibility condition (5.8).
(5.2)
\[{N_{m}}:=1-c(p-q){\sum \limits_{j=0}^{m-1}}{q^{j}},\hspace{20.0pt}{D_{m}}:={\sum \limits_{j=0}^{m-1}}{q^{2j}}+\frac{{q^{2m}}}{1-{p^{2}}},\](5.3)
\[{S_{m}}=\frac{{N_{m}^{2}}}{2{D_{m}}},\hspace{20.0pt}{Y_{m}}=\frac{{N_{m}}{q^{m}}}{{D_{m}}},\]5.1 Quadratic minimization and exact coordinates
For fixed m and k, we first derive a Cauchy–Schwarz lower bound, as in the linear case, and then use its equality case to compute ${y_{k}}$ and ${y_{k+1}}$; the ordering and breakpoint constraints are not imposed in the inequality itself, but verified afterwards as feasibility (Corollary 5.2). Throughout, the terminal-side slope products are
Lemma 5.1.
Fix $N\ge 1$ and an index $k\in \{0,\dots ,N-1\}$, and put $m=N-k-1$. Consider paths $0={y_{0}}\le \cdots \le {y_{N}}=1$ for which ${y_{0}},\dots ,{y_{k}}\lt c\lt {y_{k+1}},\dots ,{y_{N}}$, so that $f({y_{j-1}})=p{y_{j-1}}$ for $1\le j\le k+1$ and $f({y_{j-1}})=q{y_{j-1}}+c(p-q)$ for $k+2\le j\le N$. Then ${D_{m,k}}={\sum _{j=0}^{m-1}}{q^{2j}}+{q^{2m}}{\sum _{j=0}^{k}}{p^{2j}}$, and every such path obeys
with equality if and only if the errors ${e_{j}}={y_{j}}-f({y_{j-1}})$ satisfy ${e_{j}}={\alpha _{j+1}}{e_{j+1}}$; equivalently,
In particular, the equality case in (5.4) determines a unique path. For this path, (5.5) holds, the action equals $S(m,k)={N_{m}^{2}}/(2{D_{m,k}})$, and the two coordinates adjacent to c are
(5.5)
\[{y_{j}}-f({y_{j-1}})={f^{\prime }}({y_{j}})\Bigl({y_{j+1}}-f({y_{j}})\Bigr),\hspace{20.0pt}1\le j\le N-1.\]Proof.
Write ${e_{j}}={y_{j}}-f({y_{j-1}})$, so that ${e_{j}}={y_{j}}-{\alpha _{j}}{y_{j-1}}$ for $1\le j\le k+1$ and ${e_{j}}={y_{j}}-{\alpha _{j}}{y_{j-1}}-c(p-q)$ for $k+2\le j\le N$. The weights satisfy ${W_{j-1}}={\alpha _{j}}{W_{j}}$ and ${W_{N}}=1$, so the terms ${y_{j}}-{\alpha _{j}}{y_{j-1}}$ telescope to ${\sum _{j=1}^{N}}{W_{j}}({y_{j}}-{\alpha _{j}}{y_{j-1}})={W_{N}}{y_{N}}-{W_{0}}{y_{0}}=1$. Since ${W_{j}}={q^{N-j}}$ for $j\ge k+1$, the constant $c(p-q)$, present only for $j\ge k+2$, contributes ${\sum _{j=1}^{N}}{W_{j}}{e_{j}}=1-c(p-q){\sum _{j=k+2}^{N}}{W_{j}}=1-c(p-q){\sum _{i=0}^{m-1}}{q^{i}}={N_{m}}$, and the Cauchy–Schwarz inequality yields ${N_{m}^{2}}={({\sum _{j}}{W_{j}}{e_{j}})^{2}}\le ({\sum _{j}}{W_{j}^{2}})({\sum _{j}}{e_{j}^{2}})=2{D_{m,k}}{I_{N}}(\mathbf{y};f)$, which is (5.4). Equality holds precisely when ${e_{j}}=\lambda {W_{j}}$ for a common scalar λ; since ${W_{j}}/{W_{j+1}}={\alpha _{j+1}}={f^{\prime }}({y_{j}})$, this proportionality is exactly the recurrence ${e_{j}}={\alpha _{j+1}}{e_{j+1}}$, that is, (5.5). Evaluating ${\sum _{j}}{W_{j}^{2}}$ on the slope-p and slope-q blocks gives the stated closed form for ${D_{m,k}}$. The equality profile forces $\lambda {D_{m,k}}={\sum _{j}}{W_{j}}{e_{j}}={N_{m}}$, so $\lambda ={N_{m}}/{D_{m,k}}$ and ${I_{N}}(\mathbf{y};f)=\frac{1}{2}{\lambda ^{2}}{D_{m,k}}={N_{m}^{2}}/(2{D_{m,k}})$.
It remains to read off ${y_{k}}$ and ${y_{k+1}}$. Since ${W_{1}}={p^{k}}{q^{m}}$, the equality profile gives ${e_{1}}=\lambda {W_{1}}={N_{m}}{p^{k}}{q^{m}}/{D_{m,k}}$ and ${e_{j}}={e_{1}}/{p^{j-1}}$ for $1\le j\le k+1$. On the left piece ${y_{j}}=p{y_{j-1}}+{e_{j}}$, so induction yields ${y_{i}}={e_{1}}(1-{p^{2i}})/\Bigl({p^{i-1}}(1-{p^{2}})\Bigr)$ for $1\le i\le k+1$: the identity holds at $i=1$, and if it holds at i, then
\[{y_{i+1}}=p\hspace{1.67pt}{e_{1}}\frac{1-{p^{2i}}}{{p^{i-1}}(1-{p^{2}})}+\frac{{e_{1}}}{{p^{i}}}={e_{1}}\frac{1-{p^{2(i+1)}}}{{p^{i}}(1-{p^{2}})}.\]
Taking $i=k$ and $i=k+1$ and substituting ${e_{1}}={N_{m}}{p^{k}}{q^{m}}/{D_{m,k}}$ gives (5.6)–(5.7). □Proof.
Since $0\lt p\lt 1$, we have ${\sum _{j=0}^{k}}{p^{2j}}=(1-{p^{2(k+1)}})/(1-{p^{2}})\nearrow {(1-{p^{2}})^{-1}}$, so ${D_{m,k}}\nearrow {D_{m}}$ while ${N_{m}}$ does not depend on k; consequently $S(m,k)={N_{m}^{2}}/(2{D_{m,k}})\downarrow {S_{m}}$, strictly. Equations (5.6)–(5.7) tend to
so the feasibility condition ${y_{k}}\lt c\lt {y_{k+1}}$ is precisely (5.8). □
(5.9)
\[{y_{k}}\longrightarrow \frac{p{Y_{m}}}{1-{p^{2}}},\hspace{20.0pt}{y_{k+1}}\longrightarrow \frac{{Y_{m}}}{1-{p^{2}}},\]5.2 Continuous optimization of the algebraic value
Corollary 5.2 leaves us to minimize the limiting values ${S_{m}}$ over $m\in {\mathbb{Z}_{\ge 0}}$; we first analyze this sequence as a real-variable function and then use the result in the four cases of Theorem 2.4. Throughout we assume $q\ne 1$. It follows directly from the definitions of ${N_{m}}$, ${D_{m}}$, and ${S_{m}}={N_{m}^{2}}/(2{D_{m}})$ that
so that ${S_{m}}$ has the equivalent closed form
To optimize over m we relax it to a real variable: setting $t={q^{m}}\gt 0$ and
we minimize the smooth function $\mathcal{S}(t)=\frac{1+q}{2(1-q)}{(\Delta -\mathit{\delta t})^{2}}/(1-\lambda {t^{2}})$, for which ${S_{m}}=\mathcal{S}({q^{m}})$, and round to an adjacent integer afterwards (the rounding is performed in Theorem 2.4 and Lemma 6.1).
Lemma 5.3.
Let $q\ne 1$. On the half-line $m\ge 0$, the derivative of the continuous extension of ${S_{m}}=\mathcal{S}({q^{m}})$ can vanish only at the real point ${m_{0}}$ defined in Section 2.4, equivalently at ${t_{0}}:={q^{{m_{0}}}}=c(1-{p^{2}})/((p+q)\Delta )$. If ${m_{0}}\gt 0$, this point is a strict minimum when $q\gt p$ and a strict maximum when $q\lt p$. If ${m_{0}}\le 0$, there is no critical point on $m\gt 0$.
Proof.
The constant factor in $\mathcal{S}$ does not affect the critical points, and by the quotient rule
\[\frac{d}{\mathit{dt}}\frac{{(\Delta -\mathit{\delta t})^{2}}}{1-\lambda {t^{2}}}=\frac{-2\delta (\Delta -\mathit{\delta t})(1-\lambda {t^{2}})+2\mathit{\lambda t}{(\Delta -\mathit{\delta t})^{2}}}{{(1-\lambda {t^{2}})^{2}}}=\frac{2(\Delta -\mathit{\delta t})(-\delta +\lambda \Delta t)}{{(1-\lambda {t^{2}})^{2}}}.\]
The numerator vanishes at $t=\Delta /\delta $ and at $t=\delta /(\lambda \Delta )$.The first root lies outside the domain $t={q^{m}}$, $m\ge 0$. If $q\lt p$, then $\delta \lt 0$ and $\Delta /\delta \lt 0$. If $p\lt q\lt 1$, then $\Delta -\delta =1-q\gt 0$, so $\Delta /\delta \gt 1$, whereas $t\le 1$. If $q\gt 1$, then $0\lt \Delta /\delta \lt 1$, whereas $t\ge 1$. Hence the sole possible critical point is
To read off its type, restore the prefactor $(1+q)/(2(1-q))$ and factor $-\delta +\lambda \Delta t=\lambda \Delta (t-{t_{0}})$, which gives ${\mathcal{S}^{\prime }}(t)=\frac{1+q}{1-q}(\Delta -\mathit{\delta t})\lambda \Delta (t-{t_{0}})/{(1-\lambda {t^{2}})^{2}}$. Here ${(1-\lambda {t^{2}})^{2}}\gt 0$; the factor $\Delta -\mathit{\delta t}=(1-q){N_{m}}$ carries the sign of $1-q$; and λ carries the sign of $q-p$ (as $\Delta \gt 0$). Since $(1+q)/(1-q)$ also carries the sign of $1-q$, the two factors $1-q$ cancel and $sgn{\mathcal{S}^{\prime }}(t)=sgn(q-p)\cdot sgn(t-{t_{0}})$. Thus ${\mathcal{S}^{\prime }}$ passes from negative to positive at ${t_{0}}$ when $q\gt p$, and from positive to negative when $q\lt p$; as $t={q^{m}}$ is a monotone reparametrization, ${m_{0}}$ is correspondingly the unique minimizer of ${S_{m}}$ when $q\gt p$ and its unique maximizer when $q\lt p$. This applies inside the domain only when ${m_{0}}\gt 0$; if ${m_{0}}\le 0$, the critical point lies outside $m\gt 0$. □
Proof.
By (5.13), ${t_{0}}={q^{{m_{0}}}}=c(1-{p^{2}})/((p+q)\Delta )\gt 0$. If $0\lt q\lt 1$, then $m\mapsto {q^{m}}$ is decreasing, so ${m_{0}}\gt 0$ is equivalent to ${t_{0}}\lt 1$, that is, since $(p+q)\Delta \gt 0$, to $c(1-{p^{2}})\lt (p+q)\Delta =(p+q)(1-q)+c(p+q)(q-p)$, or $c\Bigl(1-{p^{2}}-(p+q)(q-p)\Bigr)\lt (p+q)(1-q)$. The bracket equals $1-{q^{2}}=(1-q)(1+q)$, and dividing by $1-q\gt 0$ gives $c(1+q)\lt p+q$, that is, $c\lt {c_{0}}$. If $q\gt 1$, then ${q^{m}}$ is increasing, so ${m_{0}}\gt 0$ is equivalent to ${t_{0}}\gt 1$, i.e. $c(1-{p^{2}})\gt (p+q)\Delta $; the same algebra gives $c(1-q)(1+q)\gt (p+q)(1-q)$, and division by $1-q\lt 0$ reverses it into $c(1+q)\lt p+q$ once again. Thus ${m_{0}}\gt 0$ if and only if $c\lt {c_{0}}$. □
Remark 5.5.
For $q\gt 1$, the assumption $\Delta \gt 0$ already supplies a lower bound on c: since $\Delta =1-q+c(q-p)$ and $q-p\gt 0$, one has $\Delta \gt 0$ if and only if $c\gt {c_{1}}:=(q-1)/(q-p)$. Hence, for $q\gt 1$, the condition ${m_{0}}\gt 0$ describes the interval ${c_{1}}\lt c\lt {c_{0}}$.
Corollary 5.6.
Recall ${S_{0}}=(1-{p^{2}})/2$. Over the nonnegative integers m: (a) if $c\lt {c_{0}}$, then ${m_{0}}\gt 0$ and ${S_{m}}$ is unimodal, with an interior extremum near ${m_{0}}$—a minimum when $q\gt p$, in which case the integer optimum is one of the two integers adjacent to ${m_{0}}$, and a maximum when $q\lt p$; (b) if $c\ge {c_{0}}$, then ${m_{0}}\le 0$ and ${S_{m}}$ is monotone for $m\ge 0$: increasing when $q\gt p$, so that ${\inf _{m}}{S_{m}}={S_{0}}=(1-{p^{2}})/2$, and decreasing when $q\lt p$.
Proof.
Combine Lemmas 5.3 and 5.4. If $c\lt {c_{0}}$, the unique real extremum ${m_{0}}$ is positive, which gives the unimodal alternative (a), the adjacent-integer statement being the standard rounding of a unimodal sequence. If $c\ge {c_{0}}$, then ${m_{0}}\le 0$, so the real extremum lies at or below 0 and $\mathcal{S}$ is monotone for $m\ge 0$; translating through $t={q^{m}}$ as in the proof of Lemma 5.3 gives the stated monotonicity of ${S_{m}}$, with value ${S_{0}}=(1-{p^{2}})/2$ at the endpoint $m=0$. □
Proof.
Rewriting the closed form of ${D_{m}}$ as ${D_{m}}=(1-\lambda {q^{2m}})/(1-{q^{2}})$ and using (5.10) gives ${Y_{m}}={N_{m}}{q^{m}}/{D_{m}}=(1+q){q^{m}}(\Delta -\delta {q^{m}})/(1-\lambda {q^{2m}})$, with $\delta =c(q-p)$ as in (5.12). At ${m_{0}}$ the critical relation $\delta =\lambda \Delta {q^{{m_{0}}}}$ (proof of Lemma 5.3) gives $\Delta -\delta {q^{{m_{0}}}}=\Delta (1-\lambda {q^{2{m_{0}}}})$, so, with ${q^{{m_{0}}}}={t_{0}}=c(1-{p^{2}})/((p+q)\Delta )$, one gets ${Y_{{m_{0}}}}=(1+q)\Delta {q^{{m_{0}}}}=c(1+q)(1-{p^{2}})/(p+q)$. Dividing (5.8), that is $c(1-{p^{2}})\lt {Y_{{m_{0}}}}\lt c(1-{p^{2}})/p$, by $c(1-{p^{2}})\gt 0$ turns it into $1\lt (1+q)/(p+q)\lt 1/p$, and each of the two inequalities is equivalent to $p\lt 1$, which holds. □
Proof.
A common-denominator reduction of ${\hat{S}_{n}}$ from (2.13) and ${S_{n}}$ from (5.11) gives
where ${D_{n}},{Y_{n}}$ denote ${D_{m}},{Y_{m}}$ at $m=n$. Writing the second denominator factor as $1-{p^{2}}-({q^{2}}-{p^{2}}){q^{2n}}=(1-{q^{2}})(1-{p^{2}}){D_{n}}$ with ${D_{n}}\gt 0$, the denominator equals $2({q^{2n}}-1)(1-{q^{2}})(1-{p^{2}}){D_{n}}$, which is negative because ${q^{2n}}-1$ and $1-{q^{2}}$ have opposite signs for every $q\ne 1$; as the numerator is the negative of a square, ${\hat{S}_{n}}\ge {S_{n}}$. Finally $(1-{q^{2}}){D_{n}}\ne 0$, so the numerator vanishes precisely when ${Y_{n}}=c(1-{p^{2}})$, i.e. when the limiting value of ${y_{k+1}}$ equals c. The boundary case $q=1$ is excluded from (5.14) but obeys the same bound: there, with $d=c(1-p)$ and $a=1/(1-{p^{2}})$ (Proposition 2.5),
(5.14)
\[{\hat{S}_{n}}-{S_{n}}=-\frac{{\Bigl[(1-{q^{2}}){D_{n}}\Bigl(c(1-{p^{2}})-{Y_{n}}\Bigr)\Bigr]^{2}}}{2({q^{2n}}-1)(1-{p^{2}}-({q^{2}}-{p^{2}}){q^{2n}})},\]
\[\begin{array}{r@{\hskip0pt}l}\displaystyle {S_{n}}& \displaystyle =\frac{{(1+\mathit{dn})^{2}}}{2(n+a)},\hspace{20.0pt}{\hat{S}_{n}}=\frac{1-{p^{2}}}{2}{c^{2}}+\frac{{(1-c+\mathit{nd})^{2}}}{2n},\\ {} \displaystyle {\hat{S}_{n}}-{S_{n}}& \displaystyle =\frac{{\Bigl(1-c-\mathit{cnp}(1-p)\Bigr)^{2}}}{2n\Bigl(1+(1-{p^{2}})n\Bigr)}\ge 0,\end{array}\]
again with equality precisely when $1-c-\mathit{cnp}(1-p)=0$, i.e. when ${Y_{n}}=c(1-{p^{2}})$, equivalently the limiting value of ${y_{k+1}}$ equals c. □6 Feasibility and comparison lemmas
The proof of Theorem 2.4 rests on the lemmas collected below, grouped by the regime that uses them and proved in Section 9. For $q\gt p$ and $c\lt {c_{0}}$ the sequence ${S_{m}}$ has an interior minimum, and the integer nearest that minimum is itself feasible.
Lemma 6.1.
Assume $q\gt p$, $\Delta \gt 0$, and $c\lt {c_{0}}$. Let ${m^{\ast }}$ be whichever of the two integers adjacent to ${m_{0}}$ yields the smaller value of ${S_{m}}$. Then ${m^{\ast }}$ satisfies the feasibility condition (5.8); equivalently, ${m^{\ast }}\in \mathcal{M}$.
For $q\lt p$ and $c\lt {c_{0}}$, instead, ${S_{m}}$ has an interior maximum, so feasibility is decided at the two ends of a short interval. The next three lemmas control the length of that interval, compare the feasible value of ${S_{m}}$ with the breakpoint value, and bound the cost of every path whose number of steps on the right-hand piece is not feasible.
Lemma 6.2.
Assume $0\lt q\lt p\lt 1$ and $c\lt {c_{0}}$. Then the real solutions m of the feasibility condition (5.8) form an interval of length less than one, so $\mathcal{M}$ contains at most one integer.
Finally, for $q\lt p$ and $c\ge {c_{0}}$ the sequence ${S_{m}}$ is monotone and only $m=0$ is feasible; the last lemma excludes every $m\ge 1$.
7 Proof of the classification theorem
Proof of Theorem 2.4.
Every admissible nondecreasing path belongs to one of the two classes studied above: it either has an internal vertex at c, or it has none. The first class is governed by Proposition 4.2, the second by Corollary 5.2 and the lemmas of Section 6. We separate the four cases.
Case 1: $q\gt p$, $c\lt {c_{0}}$. We prove $S(f)={S_{{m^{\ast }}}}$, where ${m^{\ast }}$ is the better of the two integers adjacent to ${m_{0}}$; three things must be checked: that ${m^{\ast }}$ is the integer minimizer, that it is feasible, and that ${S_{{m^{\ast }}}}$ is smaller than the breakpoint value $\hat{S}$. By Corollary 5.6(a), ${m_{0}}\gt 0$ and ${S_{m}}$ is unimodal with an interior minimum, so its minimum over $m\in {\mathbb{Z}_{\ge 0}}$ is attained at one of the two integers adjacent to ${m_{0}}$; call it ${m^{\ast }}$. By Lemma 6.1 it satisfies the feasibility condition (5.8), so ${S_{{m^{\ast }}}}$ is the relevant limiting value: the finite costs $S({m^{\ast }},k)$ decrease strictly to it as $k\to \mathrm{\infty }$ (Corollary 5.2). For the comparison with the breakpoint value, Lemma 5.8 gives ${\hat{S}_{n}}\ge {S_{n}}\ge {S_{{m^{\ast }}}}$ for each threshold index $n\in \{{n^{\ast }},{n^{\ast }}+1\}$, and this is strict: if ${S_{n}}\gt {S_{{m^{\ast }}}}$, then ${\hat{S}_{n}}\ge {S_{n}}\gt {S_{{m^{\ast }}}}$; and if ${S_{n}}={S_{{m^{\ast }}}}$, then n minimizes ${S_{m}}$ and so is feasible (Lemma 6.1), whence ${\hat{S}_{n}}\gt {S_{n}}={S_{{m^{\ast }}}}$ by Remark 5.9. In either case ${\hat{S}_{n}}\gt {S_{{m^{\ast }}}}$, so ${S_{{m^{\ast }}}}\lt \hat{S}$. Since the finite costs decrease strictly to ${S_{{m^{\ast }}}}$ and this value is smaller than every breakpoint value, $S(f)={S_{{m^{\ast }}}}$, attained at no finite horizon. This is the first line of the theorem.
Case 2: $q\lt p$, $c\lt {c_{0}}$. Here ${m_{0}}\gt 0$ is a maximum of ${S_{m}}$ (Corollary 5.6(a)): ${S_{m}}$ increases on $(0,{m_{0}})$ and decreases on $({m_{0}},\mathrm{\infty })$. It has no interior minimum, so among the feasible indices the cost decreases toward the two ends of the feasible interval, not toward the interior maximum ${m_{0}}$. By Lemma 5.7, ${m_{0}}$ lies strictly inside that interval, and by Lemma 6.2 the interval has length less than one; hence the only integers it can contain are $\lfloor {m_{0}}\rfloor $ and $\lceil {m_{0}}\rceil $, and at most one of them is feasible. Its endpoints, where ${y_{k}}=c$ or ${y_{k+1}}=c$, are breakpoint configurations of Case I and are excluded from Case II. Thus $\mathcal{M}=\{{m^{\ast }}\}$ or $\mathcal{M}=\mathrm{\varnothing }$, giving the second and third lines of the theorem.
If $\mathcal{M}=\{{m^{\ast }}\}$, the only feasible limiting value from Case II is ${S_{{m^{\ast }}}}$; by Lemma 6.3 ${S_{{m^{\ast }}}}\lt \hat{S}$, and by Lemma 6.4 every path whose number of steps on the right-hand piece lies outside $\mathcal{M}$ costs at least $\hat{S}$, so no other path can do better. Since $S({m^{\ast }},k)$ decreases strictly to ${S_{{m^{\ast }}}}$ (Corollary 5.2), $S(f)={S_{{m^{\ast }}}}$, attained at no finite horizon. If $\mathcal{M}=\mathrm{\varnothing }$, there is no feasible Case II limiting value, and by Lemma 6.4 every path costs at least $\hat{S}$; the breakpoint class of Case I therefore supplies the infimum, whose value $\hat{S}$ is realized in the limit but at no finite horizon, so $S(f)=\hat{S}$.
Case 3: $q\gt p$, $c\ge {c_{0}}$. Here ${m_{0}}\le 0$, so by Corollary 5.6(b) ${S_{m}}$ is increasing for $m\ge 0$ and ${S_{m}}\ge {S_{0}}=(1-{p^{2}})/2$. The finite algebraic costs exceed this, $S(m,k)\gt {S_{m}}\ge {S_{0}}$ (Corollary 5.2), and so do the breakpoint values, ${\hat{S}_{n}}\ge {S_{n}}\ge {S_{0}}$ (Lemma 5.8); thus $(1-{p^{2}})/2$ is a lower bound for every admissible cost. It is approached along the feasible $m=0$ configurations,
each term lying strictly above the limit. Therefore $S(f)=(1-{p^{2}})/2$, attained at no finite horizon.
Case 4: $q\lt p$, $c\ge {c_{0}}$. Here ${m_{0}}\le 0$, so by Corollary 5.6(b) the formula ${S_{m}}$ is decreasing for $m\ge 0$, sinking toward its infimum as $m\to \mathrm{\infty }$. None of these small values is feasible, however: by Lemma 6.5 every index $m\ge 1$ has ${y_{k+1}}\lt c$. The only feasible index is $m=0$, admissible because $c\ge {c_{0}}\gt p$ (indeed ${c_{0}}-p=q(1-p)/(1+q)\gt 0$); as in Case 3 it gives (7.1). For the matching lower bound, $q\lt p$ gives $f(x)\le \mathit{px}$ on $[0,1]$, so every nondecreasing path has $0\le {y_{j}}-p{y_{j-1}}\le {y_{j}}-f({y_{j-1}})$, and the linear Cauchy–Schwarz estimate yields
Together with the preceding $m=0$ paths this gives $S(f)=(1-{p^{2}})/2$, attained at no finite horizon.
(7.2)
\[{I_{N}}(\mathbf{y};f)\ge \frac{1}{2}{\sum \limits_{j=1}^{N}}{({y_{j}}-p{y_{j-1}})^{2}}\ge \frac{1-{p^{2}}}{2(1-{p^{2N}})}\gt \frac{1-{p^{2}}}{2}.\]The four cases prove the formula, and the strict finite-k inequalities above prove nonattainment. □
8 Boundary regimes
Proof of Proposition 2.5.
Let $d=c(1-p)$, so $f(x)=x-d$ on $[c,1]$. The finite and limiting costs for paths with no internal vertex at c are
\[S(m,k)=\frac{{(1+\mathit{dm})^{2}}}{2(m+{C_{k}})},\hspace{10.0pt}{C_{k}}=\frac{1-{p^{2(k+1)}}}{1-{p^{2}}},\hspace{20.0pt}{S_{m}}=\frac{{(1+\mathit{dm})^{2}}}{2(m+a)},\hspace{10.0pt}a=\frac{1}{1-{p^{2}}},\]
and a direct differentiation gives ${S^{\prime }_{m}}=(1+\mathit{dm})(\mathit{dm}+2\mathit{da}-1)/\Bigl(2{(m+a)^{2}}\Bigr)$; thus ${m_{1}}=1/d-2a$, and ${m_{1}}\gt 0$ if and only if $c\lt (1+p)/2$. As in Corollary 5.2, the limiting coordinates satisfy ${y_{k}}\lt c\lt {y_{k+1}}$ exactly when the feasibility condition (5.8) holds; at $q=1$ the quantity appearing there is
so feasibility reads $c(1-{p^{2}})\lt {Y_{m}}\lt c(1-{p^{2}})/p$. Both denominators are positive and $d\gt 0$; clearing them turns these two inequalities into $L\lt m\lt U$, where $L:=(p-c)/d$ and $U:=(1-c)/(\mathit{pd})$. The real minimizer ${m_{1}}$ always lies strictly inside this interval, since ${m_{1}}-L=(1+p-c)/\Bigl(c(1+p)\Bigr)\gt 0$ and $U-{m_{1}}=(1+p-c)/\Bigl(\mathit{cp}(1+p)\Bigr)\gt 0$.By the sign of ${S^{\prime }_{m}}$, the map $m\mapsto {S_{m}}$ is unimodal, strictly decreasing before ${m_{1}}$ and strictly increasing after. When ${m_{1}}\gt 0$ its integer minimizer over $m\ge 0$ is therefore one of the neighbours ${m^{\ast }}\in \{\lfloor {m_{1}}\rfloor ,\lceil {m_{1}}\rceil \}$, and this ${m^{\ast }}$ is feasible by the same floor/ceiling contrapositive as in Lemma 6.1, in the simpler form available here. Indeed, a common-denominator subtraction gives $sgn({S_{m}}-{S_{m+1}})=sgnF(m)$ with $F(m)=1-{d^{2}}{m^{2}}-{d^{2}}m-2a{d^{2}}m-a{d^{2}}-2\mathit{ad}$, which plays the role of P in (9.2) but is now simply strictly decreasing for $m\ge 0$, with endpoint values $F(L)=(c-1)(p-1)(1+p-c)\gt 0$ and $F(U-1)=-(c-1)(p-1)(1+p-c)/{p^{2}}\lt 0$. So if the floor $n=\lfloor {m_{1}}\rfloor $ were the minimizer yet $n\le L$, then $F(n)\ge F(L)\gt 0$, i.e. ${S_{n}}\gt {S_{n+1}}$, contradicting minimality; and if the ceiling $n+1=\lceil {m_{1}}\rceil $ were the minimizer yet $n+1\ge U$, then $F(n)\le F(U-1)\lt 0$, i.e. ${S_{n}}\lt {S_{n+1}}$, again a contradiction. Since $n\lt {m_{1}}\lt U$ and $n+1\gt {m_{1}}\gt L$ are automatic, ${m^{\ast }}\in (L,U)$ in every case.
It remains to compare with paths having an internal vertex at c: such a path has cost ${\hat{S}_{n}}$ for some $n\ge 1$, and ${\hat{S}_{n}}\ge {S_{n}}$ by Lemma 5.8, while every finite path with no internal vertex at c is represented by a pair $(m,k)$ with $S(m,k)\gt {S_{m}}$, since ${C_{k}}\lt a$. If $c\lt (1+p)/2$, then ${m_{1}}\gt 0$ and the integer minimizer ${m^{\ast }}$ is feasible, so $S({m^{\ast }},k)\downarrow {S_{{m^{\ast }}}}$; for every threshold index $n\ge 1$ we have ${\hat{S}_{n}}\ge {S_{n}}\ge {S_{{m^{\ast }}}}$, and this is strict, since ${S_{n}}\gt {S_{{m^{\ast }}}}$ gives ${\hat{S}_{n}}\gt {S_{{m^{\ast }}}}$ while ${S_{n}}={S_{{m^{\ast }}}}$ makes n a minimizer of ${S_{m}}$, hence feasible, whence ${\hat{S}_{n}}\gt {S_{n}}={S_{{m^{\ast }}}}$ by Remark 5.9. Thus ${S_{{m^{\ast }}}}\lt \hat{S}$, while every Case II path has cost $S(m,k)\gt {S_{m}}\ge {S_{{m^{\ast }}}}$; hence $S(f)={S_{{m^{\ast }}}}$. If $c\ge (1+p)/2$, then ${m_{1}}\le 0$, so ${S_{m}}$ increases on $m\ge 0$ and its integer minimizer is $m=0$; moreover $c\gt p$ makes $m=0$ feasible, with ${S_{0}}=(1-{p^{2}})/2$ and $S(0,k)\downarrow {S_{0}}$. Every threshold index gives ${\hat{S}_{n}}\ge {S_{n}}\ge {S_{0}}$, and every Case II path gives $S(m,k)\gt {S_{m}}\ge {S_{0}}$; hence $S(f)=(1-{p^{2}})/2$. In both cases the finite costs decrease strictly to the infimum, which is therefore attained at no finite horizon. Collecting the two cases,
□
Proof of Proposition 2.6.
Since $p=0$, the map is $f(x)=0$ on $[0,c]$ and $f(x)=q(x-c)$ on $[c,1]$. As $f(x)\lt x$ on $(0,1]$—for $x\ge c$, $x-f(x)\ge \Delta \gt 0$—a minimizing path may be taken nondecreasing, $0={y_{0}}\le \cdots \le {y_{N}}=1$.
Let ${j_{0}}=\min \{j\ge 1:{y_{j}}\ge c\}$. The vertices before ${j_{0}}$ lie in $[0,c)$, where $f\equiv 0$, so
\[\frac{1}{2}{\sum \limits_{j=1}^{{j_{0}}}}{\Bigl({y_{j}}-f({y_{j-1}})\Bigr)^{2}}=\frac{1}{2}{\sum \limits_{j=1}^{{j_{0}}}}{y_{j}^{2}}\ge \frac{1}{2}{y_{{j_{0}}}^{2}},\]
which is the cost of a single step from c to ${y_{{j_{0}}}}$ under $g(x)=q(x-c)$, since $g(c)=0$. As the remaining vertices lie in $[c,1]$, where $f=g$, the path costs at least the l-step value ${J_{l}}(c,1)$ with $l=N-{j_{0}}+1$; conversely each admissible $c={x_{0}}\le \cdots \le {x_{l}}=1$ gives the admissible path $0,{x_{1}},\dots ,{x_{l}}$ of equal cost. Hence $S(f)={\inf _{l\ge 1}}{J_{l}}(c,1)$.We apply Lemma 3.1 on $[c,1]$ with slope $\alpha =q$. The endpoint gaps ${d_{c}}=c$ and ${d_{1}}=\Delta $ are positive, and ${d_{c}}-{d_{1}}=(q-1)(1-c)\gt 0$, so ${\log _{q}}(c/\Delta )\gt 0$. By (3.1) and (3.4), the l-step value ${J_{l}}(c,1)=(1+q){(\Delta -c{q^{l}})^{2}}/[2(1-q)(1-{q^{2l}})]$ is unimodal in l, with integer minimum at one of ${n_{0}},{n_{0}}+1$, where ${n_{0}}=\max \{1,\lfloor {\log _{q}}(c/\Delta )\rfloor \}$. Thus $S(f)$ is the stated minimum of ${J_{l}}(c,1)$ over $l\in \{{n_{0}},{n_{0}}+1\}$, realised by the minimizing path itself; in contrast with the preceding cases, the infimum is attained at a finite horizon. □
Proof of Proposition 2.7.
Since $\Delta =0$, we have $c(q-p)=q-1$ and $q\gt 1$. Moreover, ${c_{0}}-c=(1-{p^{2}})/[(1+q)(q-p)]\gt 0$. For paths hitting c, affine minimization gives the left and right block infima $(1-{p^{2}}){c^{2}}/2$ and $(1+q){c^{2}}{(1-p)^{2}}/[2(q-1)]$; their sum is $\hat{S}=c(1-p)$.
In Case II, write ${y_{k}}\lt c\lt {y_{k+1}}$ and $m=N-k-1$. The calculation of Lemma 5.1 gives ${I_{N}}(\mathbf{y};f)\ge S(m,k)\ge {S_{m}}$, where
\[{S_{m}}={\left(\frac{2(1-{q^{-2m}})}{{q^{2}}-1}+\frac{2}{1-{p^{2}}}\right)^{-1}}\downarrow \frac{(1-{p^{2}})({q^{2}}-1)}{2({q^{2}}-{p^{2}})}\hspace{10.0pt}(m\to \mathrm{\infty }).\]
For $0\lt p\lt 1$, $S(m,k)\downarrow {S_{m}}$ as $k\to \mathrm{\infty }$; for $p=0$, $S(m,0)={S_{m}}$.For $0\lt p\lt 1$, the equality coordinates (5.6)–(5.7), as $k\to \mathrm{\infty }$ and then $m\to \mathrm{\infty }$, approach $p({q^{2}}-1)/({q^{2}}-{p^{2}})\lt c$ and $c\lt ({q^{2}}-1)/({q^{2}}-{p^{2}})\lt 1$, respectively. Thus, for sufficiently large m and then sufficiently large k, the crossing constraints hold. Both affine blocks are increasing by Lemma 3.1, so these equality paths are admissible and their actions approach ${\lim \nolimits_{m}}{S_{m}}$. For $p=0$, take $k=0$: then ${y_{1}}=2{S_{m}}\in (c,1)$ for $m\ge 1$, and the right block is increasing by Lemma 3.1. Hence these paths are also admissible and approach the same limit.
Finally, $c=(q-1)/(q-p)$ gives
\[\hat{S}-\lim \limits_{m\to \mathrm{\infty }}{S_{m}}=\frac{{(1-p)^{2}}{(q-1)^{2}}}{2({q^{2}}-{p^{2}})}\gt 0.\]
Thus $S(f)={\lim \nolimits_{m}}{S_{m}}$, with ${S_{m}}\lt \hat{S}$ for all sufficiently large m. Both classes have strictly larger finite-path costs, so the infimum is not attained. For $p=0$, substituting $q=1/(1-c)$ yields $S(f)=c-{c^{2}}/2$. □9 Proofs of the feasibility and comparison lemmas
Proof of Lemma 6.1.
Throughout, $t={q^{m}}$, and $\delta =c(q-p)\gt 0$, $\lambda =({q^{2}}-{p^{2}})/(1-{p^{2}})\gt 0$ as in (2.11) and (5.12). As in Lemma 5.7, put
\[Y(t):={Y_{m}}=\frac{(1+q)t(\Delta -\mathit{\delta t})}{1-\lambda {t^{2}}},\hspace{20.0pt}L:=c(1-{p^{2}}),\hspace{10.0pt}U:=\frac{c(1-{p^{2}})}{p},\]
so that (5.8) reads $L\lt Y(t)\lt U$. By Lemma 5.7 the real minimizer ${m_{0}}$ is strictly feasible; hence the floor can only fall too far to the left and the ceiling only too far to the right. We treat the two failures separately, each time showing that the supposedly chosen integer is beaten by its neighbour.Subtracting (5.11) at m and $m+1$ gives
For $p\lt q\lt 1$ we have $0\lt \lambda \lt {q^{2}}\lt 1$ and $0\lt t\le 1$, while for $q\gt 1$ we have $\lambda \gt {q^{2}}\gt 1$ and $t\ge 1$; in both ranges the two denominator factors carry the same sign, so the denominator is positive and
The quadratic P opens upward, $P(0)=2\delta \Delta \gt 0$, and at ${t_{\ast }}:={\lambda ^{-1/2}}$,
We also record the upward-opening quadratic
whose vertex is ${c_{0}}=(p+q)/(1+q)$, with $Q({c_{0}})=({p^{2}}-1)(p+q)/(1+q)\lt 0$. If $p\lt q\lt 1$, the lemma allows $0\lt c\lt {c_{0}}$ and $Q(0)=(p+q)(q-1)\lt 0$; if $q\gt 1$, then $\Delta \gt 0$ forces $c\gt {c_{1}}:=(q-1)/(q-p)$, the lemma allows ${c_{1}}\lt c\lt {c_{0}}$, and $Q({c_{1}})=-(1-{p^{2}})(q-1)/(q-p)\lt 0$. In both cases the admissible range lies to the left of the vertex, where Q decreases towards $Q({c_{0}})$; hence
(9.1)
\[{S_{m}}-{S_{m+1}}=\frac{-(1+q)\mathit{tP}(t)}{2(1-\lambda {t^{2}})(1-\lambda {q^{2}}{t^{2}})},\hspace{20.0pt}P(t)=2\delta \Delta -(1+q)({\delta ^{2}}+\lambda {\Delta ^{2}})t+2\mathit{q\lambda \delta }\Delta {t^{2}}.\](9.2)
\[P({q^{m}})\lt 0\Rightarrow {S_{m}}\gt {S_{m+1}},\hspace{20.0pt}P({q^{m}})\gt 0\Rightarrow {S_{m}}\lt {S_{m+1}}.\](9.3)
\[P({t_{\ast }})=-\frac{(1+q){(\delta -\sqrt{\lambda }\hspace{1.67pt}\Delta )^{2}}}{\sqrt{\lambda }}\le 0.\]
Case ${m^{\ast }}=\lfloor {m_{0}}\rfloor $. If ${m_{0}}\in {\mathbb{Z}_{\ge 0}}$ there is nothing to prove; otherwise put $n=\lfloor {m_{0}}\rfloor $ and ${t_{n}}={q^{n}}$. If the floor is the better adjacent integer then ${S_{n}}\le {S_{n+1}}$, so by (9.2) it suffices to derive $P({t_{n}})\lt 0$ from the contrary assumption that n is infeasible on the left, i.e. $n\le {m_{-}}$, where ${m_{-}}$ is the left endpoint of the feasible component containing ${m_{0}}$. There the upper inequality is sharp, $Y({t_{-}})=U$ with ${t_{-}}={q^{{m_{-}}}}$, equivalently ${G_{-}}({t_{-}})=0$, where ${G_{-}}(t):=(1+q)(\Delta t-\delta {t^{2}})-U(1-\lambda {t^{2}})=(1-\lambda {t^{2}})(Y(t)-U)$.
Claim 1: $P({t_{-}})\lt 0$. The leading coefficient of ${G_{-}}$ is $\mathit{U\lambda }-(1+q)\delta =\mathit{cq}(1-p)(q-p)/p\gt 0$ and its constant term is $-U\lt 0$, so ${G_{-}}$ has a unique positive root, namely ${t_{-}}$, and ${G_{-}}(s)\lt 0$ for $0\lt s\lt {t_{-}}$. Dividing the quadratic P by the quadratic ${G_{-}}$ leaves a linear remainder, so evaluation at the root gives
where $R(c)=(q-p)(1+{q^{2}}-2p){c^{2}}+2(q-p)(p+q)(1-q)c+(p+q){(1-q)^{2}}$. Grant for a moment that $u\lt 0$. Then $s\mapsto \mathit{us}+v$ is negative exactly for $s\gt -v/u$, while ${G_{-}}$ is negative exactly to the left of ${t_{-}}$; hence $P({t_{-}})\lt 0\hspace{2.78pt}\Longleftrightarrow \hspace{2.78pt}{t_{-}}\gt -v/u\hspace{2.78pt}\Longleftrightarrow \hspace{2.78pt}{G_{-}}(-v/u)\lt 0$. That $u\lt 0$, i.e. $R(c)\gt 0$: for $p\lt q\lt 1$ every coefficient of R is positive, since $1+{q^{2}}-2p\gt 1+{q^{2}}-2q={(1-q)^{2}}$; for $q\gt 1$, the upward-opening R has vertex ${c_{R}}=(p+q)(q-1)/(1+{q^{2}}-2p)$ with ${c_{R}}-{c_{1}}=-{(1-p)^{2}}(q-1)/\Bigl((q-p)(1+{q^{2}}-2p)\Bigr)\lt 0$, so R increases on $({c_{1}},\mathrm{\infty })$ and $R(c)\gt R({c_{1}})={(1-p)^{2}}{(q-1)^{2}}/(q-p)\gt 0$. Finally, substituting (9.6) and factoring gives the identity
where $\Lambda (c):=c(q+1-2p)-(q-1)$ and $\kappa =1/\Bigl(p{(1-p)^{2}}\Bigr)\gt 0$. Here $\Lambda \gt 0$ in both parameter ranges: for $p\lt q\lt 1$ this is immediate from $q-1\lt 0$, and for $q\gt 1$ it follows from $c\gt {c_{1}}$ and $q+1-2p\gt q-p$. Since $Q(c)\lt 0$ by (9.5), the right-hand side of (9.7) is negative, so ${G_{-}}(-v/u)\lt 0$ and therefore
(9.6)
\[P({t_{-}})=u{t_{-}}+v,\hspace{10.0pt}v=\frac{2c\Delta (1+q)(q-p)}{1-p}\gt 0,\hspace{10.0pt}u=-\frac{(q+1)(q-p)}{{(1-p)^{2}}}R(c),\](9.7)
\[{u^{2}}{G_{-}}(-v/u)=\kappa \hspace{1.67pt}c(1-c){(q-p)^{3}}{(q-1)^{2}}{(q+1)^{2}}\hspace{1.67pt}\Lambda (c)\hspace{1.67pt}Q(c),\]It remains to move this sign to ${t_{n}}$. If $q\lt 1$, then ${t_{\ast }}\gt 1$ and $n\le {m_{-}}$ gives ${t_{-}}\le {t_{n}}\le 1\lt {t_{\ast }}$; if $q\gt 1$, then ${t_{\ast }}\lt 1$ and the same assumption gives ${t_{\ast }}\lt 1\le {t_{n}}\le {t_{-}}$. Either way ${t_{n}}$ lies between ${t_{\ast }}$ and ${t_{-}}$, where P is nonpositive at both ends by (9.3) and (9.8); convexity yields $P({t_{n}})\lt 0$, hence ${S_{n}}\gt {S_{n+1}}$ by (9.2), a contradiction. Thus the floor, whenever it is chosen, is feasible.
Case ${m^{\ast }}=\lceil {m_{0}}\rceil $. With $n=\lfloor {m_{0}}\rfloor $, the ceiling $n+1$ satisfies its left inequality automatically, so it can only fail at the right endpoint, where $Y(t)\gt L$ is lost. If the ceiling is the better adjacent integer then ${S_{n+1}}\le {S_{n}}$, so by (9.2) it suffices to derive $P({t_{n}})\gt 0$ from the contrary assumption that the ceiling is infeasible at that right endpoint. The right boundary is a root ${t_{+}}={q^{{m_{+}}}}$ of ${G_{+}}(t):=(1+q)(\Delta t-\delta {t^{2}})-L(1-\lambda {t^{2}})=(1-\lambda {t^{2}})(Y(t)-L)$, whose leading coefficient is $\mathit{L\lambda }-(1+q)\delta =c(q-p)(p-1)\lt 0$, so ${G_{+}}$ opens downward; whenever it has real roots ${\rho _{1}}\lt {\rho _{2}}$, Vieta’s formulas ${\rho _{1}}{\rho _{2}}=-L/\Bigl(\mathit{L\lambda }-(1+q)\delta \Bigr)\gt 0$ and ${\rho _{1}}+{\rho _{2}}=-(1+q)\Delta /\Bigl(\mathit{L\lambda }-(1+q)\delta \Bigr)\gt 0$ show that both are positive, and ${G_{+}}\gt 0$ exactly on $({\rho _{1}},{\rho _{2}})$. Dividing $P(t/q)$ by ${G_{+}}(t)$ again leaves a linear remainder, so at each root
where ${R_{+}}(c)=(p+q){(1-q)^{2}}+2(q-p)(1-q)(p+q)c-(q-p)\Bigl(1-{q^{2}}-2p(1-p)\Bigr){c^{2}}$.
(9.9)
\[\begin{array}{r@{\hskip0pt}l}\displaystyle P({\rho _{i}}/q)& \displaystyle ={u_{+}}{\rho _{i}}+{v_{+}},\hspace{10.0pt}{v_{+}}=-\frac{2\mathit{cp}\Delta (1+q)(q-p)}{q(1-p)}\lt 0,\\ {} \displaystyle {u_{+}}& \displaystyle =\frac{(q-p)(1+q)}{q{(1-p)^{2}}}{R_{+}}(c),\end{array}\]
The range $p\lt q\lt 1$. Here ${t_{0}}={q^{{m_{0}}}}$, so $Y({t_{0}})\gt L$ by the strict feasibility of ${m_{0}}$ (Lemma 5.7), and $1-\lambda {t_{0}^{2}}\gt 0$ because $0\lt {t_{0}}\lt 1$ and $0\lt \lambda \lt 1$; hence ${G_{+}}({t_{0}})=(1-\lambda {t_{0}^{2}})(Y({t_{0}})-L)\gt 0$ and ${t_{0}}\in ({\rho _{1}},{\rho _{2}})$. The ceiling lies to the right of ${m_{0}}$, and $q\lt 1$ makes $t={q^{m}}$ decrease as m increases; so t leaves $({\rho _{1}},{\rho _{2}})$ through its left end, and the right endpoint of the component is ${t_{+}}={\rho _{1}}$, not ${\rho _{2}}$. Infeasibility of the ceiling means $n+1\ge {m_{+}}$, i.e. ${q^{n+1}}\le {t_{+}}$, i.e. ${t_{n}}\le {t_{+}}/q$. Since P opens upward with $P(0)\gt 0$ and $P({t_{\ast }})\le 0$, it has a first zero ${r_{1}}\in (0,{t_{\ast }}]$, and on $(0,{t_{\ast }}]$ positivity of P occurs exactly to the left of ${r_{1}}$; moreover ${t_{+}}\lt {t_{0}}\lt 1$ and $\lambda \lt {q^{2}}$ give ${t_{+}}/q\lt 1/q\lt {t_{\ast }}$. So it suffices to prove that $P({t_{+}}/q)\gt 0$, for then ${t_{+}}/q$ lies to the left of ${r_{1}}$, and so does ${t_{n}}$.
By (9.9) with ${\rho _{1}}={t_{+}}$, and since ${v_{+}}\lt 0$, the inequality $P({t_{+}}/q)\gt 0$ is equivalent to ${u_{+}}\gt 0$ together with ${t_{+}}\gt -{v_{+}}/{u_{+}}$. Positivity of ${u_{+}}$ is positivity of ${R_{+}}$: its derivative ${R^{\prime }_{+}}(c)=2(q-p)\Bigl((1-q)(p+q)-c(1-{q^{2}}-2p(1-p))\Bigr)$ has its linear factor positive at both $c=0$ and $c={c_{0}}$, so ${R_{+}}$ increases on $[0,{c_{0}}]$ and ${R_{+}}(c)\gt {R_{+}}(0)=(p+q){(1-q)^{2}}\gt 0$. Next, the same computation that gave (9.7) yields the identical product for ${G_{+}}$, now with $\kappa =1/\Bigl({q^{2}}{(1-p)^{2}}\Bigr)$ in place of $1/\Bigl(p{(1-p)^{2}}\Bigr)$; hence ${u_{+}^{2}}{G_{+}}(-{v_{+}}/{u_{+}})\lt 0$ by the same two signs $\Lambda \gt 0$ and $Q\lt 0$. This places $-{v_{+}}/{u_{+}}$ outside $[{\rho _{1}},{\rho _{2}}]$; to exclude the far side, compare it with ${t_{0}}$. From (9.9),
\[-\frac{{v_{+}}}{{u_{+}}}=\frac{2\mathit{cp}\Delta (1-p)}{{R_{+}}(c)},\hspace{20.0pt}{t_{0}}=\frac{\delta }{\lambda \Delta }=\frac{c(1-{p^{2}})}{(p+q)\Delta },\]
so $-{v_{+}}/{u_{+}}\lt {t_{0}}$ is equivalent to ${R_{+}}(c)\gt 2p(p+q){\Delta ^{2}}/(1+p)$, which is exactly the identity ${R_{+}}(c)-2p(p+q){\Delta ^{2}}/(1+p)=-(p-1)(q-1)Q(c)/(p+1)\gt 0$. As ${t_{0}}\in ({\rho _{1}},{\rho _{2}})$, the point $-{v_{+}}/{u_{+}}$ must lie to the left of ${\rho _{1}}={t_{+}}$. Hence $P({t_{+}}/q)\gt 0$, so $P({t_{n}})\gt 0$ and ${S_{n}}\lt {S_{n+1}}$ by (9.2), contradicting ${S_{n+1}}\le {S_{n}}$.
The range $q\gt 1$. Here ${c_{1}}\lt c\lt {c_{0}}$, and the discriminant of ${G_{+}}$ is $\mathcal{D}={(1+q)^{2}}{\Delta ^{2}}-4{c^{2}}(q-p){(1-p)^{2}}(1+p)$. If $\mathcal{D}\lt 0$, then the downward-opening ${G_{+}}$ is negative everywhere; since $t\ge 1$ and $\lambda \gt {q^{2}}\gt 1$ give $1-\lambda {t^{2}}\lt 0$, the identity ${G_{+}}(t)=(1-\lambda {t^{2}})(Y(t)-L)$ forces $Y(t)\gt L$ for every integer m, so the ceiling is automatically feasible. Assume therefore $\mathcal{D}\ge 0$. Now $1-\lambda {t^{2}}\lt 0$, so $Y(t)\gt L$ means ${G_{+}}(t)\lt 0$, i.e. t lies outside $[{\rho _{1}},{\rho _{2}}]$, and $t={q^{m}}$ increases with m. Hence a component contained in $({\rho _{2}},\mathrm{\infty })$ is unbounded to the right and has no finite endpoint, whereas on $(0,{\rho _{1}})$ the point t moves right towards ${\rho _{1}}$ and leaves the component there. So again ${t_{+}}={\rho _{1}}$, and infeasibility of the ceiling gives ${q^{n+1}}\ge {t_{+}}$, i.e. ${t_{n}}\ge {t_{+}}/q$. Because $\lambda \gt {q^{2}}$ we have ${t_{\ast }}\lt 1$. Since P opens upward with $P({t_{\ast }})\le 0$ by (9.3), its larger zero ${r_{2}}$ satisfies ${r_{2}}\ge {t_{\ast }}$, and for $t\gt {t_{\ast }}$ one has $P(t)\gt 0$ exactly when $t\gt {r_{2}}$; the integer range $t\ge 1\gt {t_{\ast }}$ lies in that regime. Moreover ${m_{+}}\gt {m_{0}}\gt 0$ gives ${t_{+}}\gt 1$, and $q{t_{\ast }}=q/\sqrt{\lambda }\lt 1$ gives ${t_{\ast }}\lt 1/q$, whence ${t_{+}}/q\gt 1/q\gt {t_{\ast }}$. Thus it again suffices to prove
for then ${t_{+}}/q\gt {r_{2}}$, and ${t_{n}}\ge {t_{+}}/q$ gives ${t_{n}}\gt {r_{2}}$, i.e. $P({t_{n}})\gt 0$.
We evaluate $P(\cdot /q)$ at both roots at once. By (9.9) and Vieta’s formulas,
The prefactor is positive, because $c\gt {c_{1}}$ is equivalent to $\delta \gt q-1$. If $q\lt 2p+1$, the second term in (9.12) is strictly positive, so $\mathcal{H}(c)\gt 0$ whenever $\mathcal{D}\ge 0$. If $q\ge 2p+1$, the case $\mathcal{D}\ge 0$ is empty: there $\mathcal{D}$ is an upward-opening quadratic in c with $\mathcal{D}({c_{1}})=4{(p-1)^{2}}(p+1){(q-1)^{2}}/(p-q)\lt 0$ (negative for every $q\gt p$) and $\mathcal{D}({c_{0}})={(1-p)^{2}}(1+p)\Bigl[(1+p)-4{(p+q)^{2}}(q-p)/{(1+q)^{2}}\Bigr]\lt 0$, the latter because $q\ge 2p+1$ gives $q-p\ge 1+p$ while $q\gt 1$ gives $4{(p+q)^{2}}\gt {(1+q)^{2}}$; so by convexity $\mathcal{D}\lt 0$ throughout $({c_{1}},{c_{0}})$. In every nonempty case the sum is therefore positive, which together with (9.11) gives $P({\rho _{i}}/q)\gt 0$ for $i=1,2$. Since ${t_{+}}={\rho _{1}}$, this proves (9.10).
\[\begin{array}{r@{\hskip0pt}l}\displaystyle P({\rho _{1}}/q)P({\rho _{2}}/q)& \displaystyle ={u_{+}^{2}}{\rho _{1}}{\rho _{2}}+{u_{+}}{v_{+}}({\rho _{1}}+{\rho _{2}})+{v_{+}^{2}}\\ {} & \displaystyle =\frac{(c-1){(p-q)^{2}}{(q-1)^{2}}{(q+1)^{2}}}{{q^{2}}{(p-1)^{3}}}{M_{1}}(c)Q(c),\end{array}\]
with ${M_{1}}(c)=2\mathit{cp}-\mathit{cq}-c+q-1$. The prefactor is positive, ${M_{1}}$ is linear and negative at both endpoints of $({c_{1}},{c_{0}})$, and $Q\lt 0$ by (9.5); hence
so the two values share a sign. To identify it, take their sum:
(9.12)
\[\begin{array}{c}\displaystyle P({\rho _{1}}/q)+P({\rho _{2}}/q)={u_{+}}({\rho _{1}}+{\rho _{2}})+2{v_{+}}=\frac{(q+1)\Bigl(\delta -(q-1)\Bigr)}{\mathit{cq}{(1-p)^{3}}}\hspace{1.67pt}\mathcal{H}(c),\\ {} \displaystyle \mathcal{H}(c)={c_{0}}\mathcal{D}+\frac{{(p-1)^{2}}(q-p)(2p+q-1)(2p+1-q)}{q+1}{c^{2}}.\end{array}\]Both alternatives are now covered, so the adjacent integer that minimizes ${S_{m}}$ satisfies (5.8), as claimed. □
Proof of Lemma 6.2.
We keep the notation of Lemma 6.1: $t={q^{m}}$, with δ and λ as in (5.12) and (2.11) – both negative in the present regime – and $Y(t)=(1+q)t(\Delta -\mathit{\delta t})/(1-\lambda {t^{2}})$. Since $0\lt q\lt 1$, increasing m moves t to the left. The limit feasibility condition is $c(1-{p^{2}})\lt Y(t)\lt c(1-{p^{2}})/p$; let ${t_{+}}$ and ${t_{-}}$ be the two boundary points of the feasible interval, so that $Y({t_{+}})=c(1-{p^{2}})$ and $Y({t_{-}})=c(1-{p^{2}})/p$. The feasible interval in the m-variable has length less than one exactly when
and this last inequality is what we prove.
Claim 1: Y is strictly increasing on $(0,{t_{-}}]$; in particular ${t_{+}}\in (0,{t_{-}})$. The upper boundary equation $Y(t)=c(1-{p^{2}})/p$ is equivalent to ${G_{-}}(t)=0$, where ${G_{-}}(t):=\frac{c(1-{p^{2}})}{p}(1-\lambda {t^{2}})-(1+q)t(\Delta -\mathit{\delta t})$, the negative of the ${G_{-}}$ of Lemma 6.1 in the opposite regime. Its leading coefficient is $-c(1-{p^{2}})\lambda /p+(1+q)\delta =c(p-q)q(1-p)/p\gt 0$, while ${G_{-}}(0)=c(1-{p^{2}})/p\gt 0$ and ${G_{-}}(1/q)=-(c-1)(q-1)(q+1)/q\lt 0$, so ${t_{-}}$ is the smaller positive root of this upward-opening quadratic and ${G^{\prime }_{-}}({t_{-}})\lt 0$. Differentiating the identity ${G_{-}}(t)=-(1-\lambda {t^{2}})\Bigl(Y(t)-c(1-{p^{2}})/p\Bigr)$ at ${t_{-}}$ therefore gives ${Y^{\prime }}({t_{-}})\gt 0$. Now ${Y^{\prime }}$ has numerator $\Delta -2\mathit{\delta t}+\lambda \Delta {t^{2}}$ and positive denominator ${(1-\lambda {t^{2}})^{2}}$, so this numerator is $\gt 0$ at ${t_{-}}$. It is a concave quadratic, its ${t^{2}}$-coefficient $\lambda \Delta $ being negative, with value $\Delta \gt 0$ at $t=0$; positive at both ends of $[0,{t_{-}}]$, it is positive throughout, so Y is strictly increasing on $(0,{t_{-}}]$. The same monotonicity and $Y(0)=0\lt c(1-{p^{2}})=Y({t_{+}})\lt Y({t_{-}})$ place ${t_{+}}\in (0,{t_{-}})$.
By Claim 1 both $q{t_{-}}$ and ${t_{+}}$ lie in $(0,{t_{-}}]$, where Y is strictly increasing, so
The lemma is thus reduced to the following claim.
Claim 2: $Y(q{t_{-}})\lt \mathit{pY}({t_{-}})$. Reducing to a common denominator gives
\[\begin{array}{r@{\hskip0pt}l}\displaystyle \mathit{pY}(t)-Y(\mathit{qt})& \displaystyle =\frac{(1+q)t}{(1-\lambda {t^{2}})(1-\lambda {q^{2}}{t^{2}})}\hspace{1.67pt}W(t),\\ {} \displaystyle W(t)& \displaystyle =p(\Delta -\mathit{\delta t})(1-\lambda {q^{2}}{t^{2}})-q(\Delta -\mathit{\delta qt})(1-\lambda {t^{2}}).\end{array}\]
Since $\lambda \lt 0$ and $t\gt 0$, the factor in front is positive, so $Y(\mathit{qt})\lt \mathit{pY}(t)$ if and only if $W(t)\gt 0$; Claim 2 is thus the single sign $W({t_{-}})\gt 0$. Dividing the cubic W by the quadratic ${G_{-}}$ leaves a linear remainder, so at the root ${t_{-}}$,
\[W({t_{-}})=u{t_{-}}+v,\hspace{20.0pt}u=-\frac{p(q+1)}{c{(p-1)^{2}}}R(c),\hspace{20.0pt}v=\frac{2p(q+1)(\mathit{cp}-\mathit{cq}+q-1)}{p-1},\]
where $R(c):=(p-q)(2p-{q^{2}}-1){c^{2}}+2(q-1)(p-q)(p+q)c+(p+q){(q-1)^{2}}$. Here $v\gt 0$, because $\mathit{cp}-\mathit{cq}+q-1\lt 0$ and $p-1\lt 0$. Moreover $R(c)\gt 0$ on $[0,{c_{0}}]$, whence $u\lt 0$. Indeed, the endpoint values are
\[R(0)=(p+q){(q-1)^{2}}\gt 0,\hspace{20.0pt}R({c_{0}})=\frac{{(p-1)^{2}}(p+q)(2p+{q^{2}}+1)}{{(q+1)^{2}}}\gt 0;\]
if the coefficient $(p-q)(2p-{q^{2}}-1)$ of ${c^{2}}$ is non-positive, then R is concave or linear and attains its minimum on $[0,{c_{0}}]$ at an endpoint, while if $2p-{q^{2}}-1\gt 0$, then R opens upward with vertex ${c_{R}}=(1-q)(p+q)/(2p-{q^{2}}-1)$, and $0\lt 2p-{q^{2}}-1\lt 1-{q^{2}}$ gives ${c_{R}}/{c_{0}}=(1-{q^{2}})/(2p-{q^{2}}-1)\gt 1$, so R decreases on $[0,{c_{0}}]$ with minimum $R({c_{0}})\gt 0$.Since $u\lt 0$ and $v\gt 0$, the inequality $W({t_{-}})\gt 0$ is equivalent to ${t_{-}}\lt {t^{\ast }}:=-v/u\gt 0$. Substituting ${t^{\ast }}$ into the boundary quadratic and multiplying by ${u^{2}}\gt 0$,
\[\begin{array}{c}\displaystyle {u^{2}}{G_{-}}({t^{\ast }})=\frac{p{(q+1)^{2}}(c-1)(p-q){(q-1)^{2}}}{c{(p-1)^{2}}}{F_{1}}(c){F_{2}}(c),\\ {} \displaystyle {F_{1}}(c)=2\mathit{cp}-\mathit{cq}-c+q-1,\\ {} \displaystyle {F_{2}}(c)=-(p-q)(q+1){c^{2}}+2(p-q)(p+q)c+(p+q)(q-1).\end{array}\]
Both factors are negative for $0\lt c\lt {c_{0}}$: if $2p-q-1\le 0$ then ${F_{1}}\lt 0$ outright, and otherwise ${F_{1}}$ increases in c with ${F_{1}}({c_{0}})=(p-1)(2p+1+q)/(q+1)\lt 0$; and ${F_{2}}$ opens downward with vertex ${c_{0}}$, where ${F_{2}}({c_{0}})=(p-1)(p+1)(p+q)/(q+1)\lt 0$. As the prefactor is negative, ${G_{-}}({t^{\ast }})\lt 0$. By Claim 1 the upward-opening ${G_{-}}$ is negative precisely between its two positive roots, of which ${t_{-}}$ is the smaller; hence ${t^{\ast }}\gt {t_{-}}$ and $W({t_{-}})\gt 0$. This proves Claim 2, and with it the lemma. □Proof of Lemma 6.3.
We keep the notation of Lemma 6.2 and write ${n_{0}}=c(1-p)/\Delta $. Assume $m\in \mathcal{M}$; we must prove ${S_{m}}\lt \hat{S}$. The comparison is governed by the real minimizer ${\log _{q}}{n_{0}}$ of the breakpoint sequence ${\hat{S}_{n}}$, rather than by the critical point ${m_{0}}$ of ${S_{m}}$. Feasibility of m links the two: it forces ${n_{0}}/{q^{m}}$ to lie between q and 1, so that ${\log _{q}}{n_{0}}$ lies between m and $m+1$; hence $\hat{S}$ is decided by the two adjacent breakpoint values ${\hat{S}_{m}}$ and ${\hat{S}_{m+1}}$ (Claim 1), each of which we then show exceeds ${S_{m}}$ (Claim 2).
Claim 1: $m\lt {\log _{q}}{n_{0}}\lt m+1$; consequently $\hat{S}=\min \{{\hat{S}_{m}},{\hat{S}_{m+1}}\}$ when $m\ge 1$, and $\hat{S}={\hat{S}_{m+1}}$ when $m=0$. Write $t={q^{m}}$. Feasibility of m reads $c(1-{p^{2}})\lt Y(t)\lt c(1-{p^{2}})/p$; substituting $c={n_{0}}\Delta /(1-p)$ and clearing positive denominators gives $\frac{p(1+q)}{p+1+(p-q)q{t^{2}}}\lt \frac{{n_{0}}}{t}\lt \frac{1+q}{p+1-(p-q){t^{2}}}$. The upper bound is at most 1, because $p+1-(p-q){t^{2}}-(1+q)=(p-q)(1-{t^{2}})\ge 0$, while the lower bound exceeds q, because its denominator is positive and $\frac{p(1+q)}{p+1+(p-q)q{t^{2}}}-q=\frac{(p-q)(1-{q^{2}}{t^{2}})}{p+1+(p-q)q{t^{2}}}\gt 0$ by $p\gt q$ and ${q^{2}}{t^{2}}={q^{2(m+1)}}\lt 1$. Hence $q\lt {n_{0}}/t\lt 1$, that is, ${q^{m+1}}\lt {n_{0}}\lt {q^{m}}$, equivalently $m\lt {\log _{q}}{n_{0}}\lt m+1$. By Lemma 3.1 the real minimizer of ${\hat{S}_{n}}$ is ${\log _{q}}{n_{0}}$. For $m\ge 1$ it lies in $(m,m+1)$, so the integer minimizer is ${n^{\ast }}=m$ and $\hat{S}=\min \{{\hat{S}_{m}},{\hat{S}_{m+1}}\}$. For $m=0$ it lies in $(0,1)$, at or below the first admissible index $n=1$; by the unimodality in Lemma 3.1 the sequence ${\hat{S}_{n}}$ is then increasing from $n=1$, so $\hat{S}={\hat{S}_{1}}={\hat{S}_{m+1}}$.
Claim 2: ${S_{m}}\lt {\hat{S}_{m+1}}$, and if $m\ge 1$, also ${S_{m}}\lt {\hat{S}_{m}}$. For $m\ge 1$ the second inequality is exactly Lemma 5.8: since $m\in \mathcal{M}$, the lower feasibility inequality $c(1-{p^{2}})\lt {Y_{m}}$ in (5.8) makes it strict (Remark 5.9), so ${\hat{S}_{m}}\gt {S_{m}}$. For the first inequality, write $t={q^{m}}$ and ${A_{m+1}}={\sum _{j=0}^{m}}{q^{2j}}$. Since $\Delta -c(1-p){q^{m+1}}=(1-q)({N_{m+1}}-c{q^{m+1}})$ and $1-{q^{2(m+1)}}=(1-{q^{2}}){A_{m+1}}$, the right-hand term of ${\hat{S}_{m+1}}$ in (2.13) equals ${({N_{m+1}}-c{q^{m+1}})^{2}}/(2{A_{m+1}})$, and the recurrence ${N_{m+1}}={N_{m}}-c(p-q){q^{m}}$ collapses its numerator to ${N_{m+1}}-c{q^{m+1}}={N_{m}}-\mathit{cpt}$. Thus ${\hat{S}_{m+1}}=\frac{1}{2}(1-{p^{2}}){c^{2}}+{({N_{m}}-\mathit{cpt})^{2}}/(2{A_{m+1}})$, and a common-denominator reduction against ${S_{m}}={N_{m}^{2}}/(2{D_{m}})$, using $(1-{p^{2}}){A_{m+1}}=(1-{p^{2}}){D_{m}}-{p^{2}}{t^{2}}$, gives
The denominator is positive, and the upper feasibility inequality $p{Y_{m}}\lt c(1-{p^{2}})$ forces $c(1-{p^{2}}){D_{m}}\ne p{N_{m}}{q^{m}}$; hence (9.13) is strict, ${\hat{S}_{m+1}}\gt {S_{m}}$.
(9.13)
\[{\hat{S}_{m+1}}-{S_{m}}=\frac{{\Bigl(c(1-{p^{2}}){D_{m}}-p{N_{m}}{q^{m}}\Bigr)^{2}}}{2(1-{p^{2}}){D_{m}}\hspace{1.67pt}{A_{m+1}}}\ge 0.\]By Claim 1 every breakpoint value entering $\hat{S}$ is ${\hat{S}_{m}}$ (only for $m\ge 1$) or ${\hat{S}_{m+1}}$, and by Claim 2 both exceed ${S_{m}}$. Hence ${S_{m}}\lt \hat{S}$ for every $m\in \mathcal{M}$; in particular ${S_{{m^{\ast }}}}\lt \hat{S}$. □
Proof of Lemma 6.4.
First assume $m\ge 1$, fix such a path, and set $u:={y_{k}}\in [0,c)$, $v:={y_{k+1}}\in (c,1]$. Splitting the action at these two vertices: the k steps in $[0,c]$ contribute at least $\frac{1-{p^{2}}}{2}{u^{2}}$ (trivially when $k=0$, and by Lemma 3.1 with ${g_{p}}(x)=\mathit{px}$ when $k\ge 1$), the step from u to v contributes $\frac{1}{2}{(v-\mathit{pu})^{2}}$, and the m steps in $[c,1]$ contribute at least ${J_{m}}(v,1;{g_{q}})$ (Lemma 3.1, with ${g_{q}}(x)=\mathit{qx}+c(p-q)$). Hence ${I_{N}}(\mathbf{y};f)\ge {\Phi _{m}}(u,v):=\frac{1-{p^{2}}}{2}{u^{2}}+\frac{1}{2}{(v-\mathit{pu})^{2}}+{J_{m}}(v,1;{g_{q}})$, so ${I_{N}}(\mathbf{y};f)\ge {\bar{S}_{m}}:={\min _{R}}{\Phi _{m}}$ with $R:=\{(u,v):0\le u\le c\le v\le 1\}$; we prove ${\bar{S}_{m}}\ge \hat{S}$ for $m\notin \mathcal{M}$.
The quadratic ${\Phi _{m}}$ is strictly convex. Minimizing first in u, ${\partial _{u}}{\Phi _{m}}=u-\mathit{pv}=0$ gives $u=\mathit{pv}$ and ${\Phi _{m}}(\mathit{pv},v)=\frac{1-{p^{2}}}{2}{v^{2}}+{J_{m}}(v,1;{g_{q}})$, a strictly convex function of v with unique minimizer ${v_{\ast }}:={Y_{m}}/(1-{p^{2}})$ and value ${S_{m}}$ (Corollary 5.2). Thus the unconstrained minimizer of ${\Phi _{m}}$ is $(p{v_{\ast }},{v_{\ast }})$; by (5.8) it lies in the interior of R precisely when $c\lt {v_{\ast }}\lt c/p$, that is, when $m\in \mathcal{M}$. Hence for $m\notin \mathcal{M}$ the minimizer over R lies on the boundary, and two of the four sides are excluded, since at every boundary point
\[{\partial _{u}}{\Phi _{m}}(0,v)=-\mathit{pv}\lt 0,\hspace{10.0pt}{\partial _{v}}{\Phi _{m}}(u,1)=(1-\mathit{pu})-\frac{(1+q){q^{m}}\Delta }{1+{q^{m}}}\ge (1-\mathit{pc})-q\Delta \gt 0,\]
the last inequality using $(1+q){q^{m}}/(1+{q^{m}})\le q$ for $m\ge 1$ and $(1-\mathit{pc})-q\Delta =(1-p)(1-q)+(1-c)(p(1-q)+{q^{2}})\gt 0$. The first sign shows that ${\Phi _{m}}$ strictly decreases as one moves off the side $u=0$ into R, the second that it strictly increases toward the side $v=1$; so the minimum lies on $u=c$ or on $v=c$. On the side $v=c$,
\[\begin{array}{r@{\hskip0pt}l}\displaystyle \min \limits_{0\le u\le c}{\Phi _{m}}(u,c)& \displaystyle =\min \limits_{0\le u\le c}\Biggl\{\frac{1-{p^{2}}}{2}{u^{2}}+\frac{1}{2}{(c-\mathit{pu})^{2}}\Biggr\}+{J_{m}}(c,1;{g_{q}})\\ {} & \displaystyle =\frac{1-{p^{2}}}{2}{c^{2}}+{J_{m}}(c,1;{g_{q}})={\hat{S}_{m}}\ge \hat{S},\end{array}\]
the first minimum being attained at $u=\mathit{pc}$; and on the side $u=c$, concatenating the transition from c to v with the unrestricted m-step fixed-endpoint path from v to 1,
\[\begin{array}{r@{\hskip0pt}l}\displaystyle \min \limits_{c\le v\le 1}{\Phi _{m}}(c,v)& \displaystyle =\frac{1-{p^{2}}}{2}{c^{2}}+\min \limits_{c\le v\le 1}\Biggl\{\frac{1}{2}{(v-\mathit{pc})^{2}}+{J_{m}}(v,1;{g_{q}})\Biggr\}\\ {} & \displaystyle \ge \frac{1-{p^{2}}}{2}{c^{2}}+{J_{m+1}}(c,1;{g_{q}})={\hat{S}_{m+1}}\ge \hat{S}.\end{array}\]
Thus every boundary minimum of ${\Phi _{m}}$ is at least $\hat{S}$, and therefore ${\bar{S}_{m}}\ge \hat{S}$. For $m=0$ the right block is empty and $v={y_{N}}=1$, so the cost is a function of u alone; minimizing $\frac{1-{p^{2}}}{2}{u^{2}}+\frac{1}{2}{(1-\mathit{pu})^{2}}$ over $0\le u\le c$, with the minimum at $u=c$ (forced by $0\notin \mathcal{M}$, i.e. $c\le p$), gives ${\bar{S}_{0}}=\frac{1-{p^{2}}}{2}{c^{2}}+\frac{1}{2}{(1-\mathit{pc})^{2}}={\hat{S}_{1}}\ge \hat{S}$. Thus ${I_{N}}(\mathbf{y};f)\ge \hat{S}$ for every such path when $m\notin \mathcal{M}$. □Proof of Lemma 6.5.
Fix $m\ge 1$ and write $t={q^{m}}\in (0,q]$. By Corollary 5.2 the coordinate ${y_{k+1}}$ increases to ${Y_{m}}/(1-{p^{2}})$ as $k\to \mathrm{\infty }$, and in the limit ${y_{k}}\lt c\lt {y_{k+1}}$ holds exactly under the feasibility condition (5.8). Since ${y_{k+1}}\lt {Y_{m}}/(1-{p^{2}})$ at every finite k, a violation of the lower bound of (5.8),
already forces ${y_{k+1}}\lt c$ for all $k\ge 0$; it therefore suffices to prove (9.14) for every $t={q^{m}}\in (0,q]$. Expressing ${N_{m}}$ and ${D_{m}}$ through t turns ${Y_{m}}={N_{m}}{q^{m}}/{D_{m}}$ into ${Y_{m}}=(1+q)t(\Delta +c(p-q)t)\Big/\Bigl(1-\frac{{q^{2}}-{p^{2}}}{1-{p^{2}}}{t^{2}}\Bigr)$, whose denominator is positive because $q\lt p$. Clearing it, (9.14) is equivalent to $h(t)\gt 0$, where
\[\begin{array}{r@{\hskip0pt}l}\displaystyle h(t)& \displaystyle =c\Bigl[(1-{p^{2}})-({q^{2}}-{p^{2}}){t^{2}}\Bigr]-(1+q)t(\Delta +c(p-q)t)\\ {} & \displaystyle =c(1-{p^{2}})-(1+q)\Delta t-c(p-q)(1-p){t^{2}}.\end{array}\]
The quadratic h is concave in t, its ${t^{2}}$-coefficient $-c(p-q)(1-p)$ being negative, so on $[0,q]$ it attains its minimum at an endpoint. At $t=0$ we have $h(0)=c(1-{p^{2}})\gt 0$, while at $t=q$
\[\begin{array}{r@{\hskip0pt}l}\displaystyle h(q)& \displaystyle =(1-{q^{2}})\Bigl(c(1-{p^{2}}+\mathit{pq})-q\Bigr)\ge (1-{q^{2}})\Bigl({c_{0}}(1-{p^{2}}+\mathit{pq})-q\Bigr)\\ {} & \displaystyle =(1-{q^{2}})\frac{(1-p)({p^{2}}+p-{q^{2}})}{1+q}\gt 0,\end{array}\]
where the first inequality uses $c\ge {c_{0}}$ together with $1-{p^{2}}+\mathit{pq}\gt 0$, and the last uses ${p^{2}}+p-{q^{2}}\gt {p^{2}}\gt 0$. Hence $h\gt 0$ on $[0,q]$, which is (9.14); therefore ${y_{k+1}}\lt c$ for all k, and no pair $(m,k)$ with $m\ge 1$ is feasible. □
