All missions

Why the walk slows down

A random walk in a random environment uses transition probabilities selected once for each site, rather than probabilities resampled at every step. Even when the site environments are independent and identically distributed, the walker revisits the same local bias whenever it returns to a site. Its long-time motion can therefore differ sharply from that of a walk with a single averaged right-step probability. Solomon’s 1975 paper established the recurrence and speed classification for this one-dimensional model and then examined a two-value example in which some sites are one-way mirrors: the walker can pass through them to the right but cannot cross them to the left. The example isolates how a sequence of random intervals between mirrors produces slow growth and phase-dependent limit laws Solomon 1975, §2.

The present mission concerns §2 of that paper, pp. 10–20. Its central question is how far the walker has traveled after $n$ steps when the mean crossing time reaches or exceeds the critical threshold. At criticality, a logarithmic correction replaces ordinary linear speed. Above criticality, the paper gives limits along subsequences whose logarithmic fractional parts approach a fixed phase.

The walk and its mirror environment

Let $(\Omega,\mathcal F,P)$ be a probability space and let $\alpha_j$, $j\in\mathbb Z$, be independent, identically distributed random variables in $[0,1]$. The environment is the complete sequence $\alpha=(\alpha_j)_{j\in\mathbb Z}$. Conditional on a fixed environment, a nearest-neighbour walk starts at $X_0=0$ and, from site $j$, moves to $j+1$ with probability $\alpha_j$ and to $j-1$ with probability $1-\alpha_j$. The annealed probability $P$ averages the conditional path law over the environment. In Lean this joint law is specified on every finite path cylinder together with every measurable event of the whole environment, so it determines the dependence between $X$ and $\alpha$.

Fix $\theta>1$ and $0<\gamma<1$. Solomon’s example has $\alpha_j=1$ with probability $1-\gamma$ and $\alpha_j=(1+\theta)^{-1}$ with probability $\gamma$. Equivalently, the left-to-right odds ratio $\sigma_j=(1-\alpha_j)/\alpha_j$ takes values $0$ and $\theta$. A site with $\sigma_j=0$ is a one-way mirror. Write $V_0=0$ and let $V_n$ be the position of the $n$th mirror strictly to the right of zero. Let $T_j$ be the first time the walk reaches site $j$, with $T_j=\infty$ if it never does. For $b>0$, $\log_b x$ means the logarithm in base $b$, and $\{x\}=x-\lfloor x\rfloor$ is the fractional part.

The parameters used below are

When $\gamma\theta>1$, the paper specifies a probability law $F_\varepsilon$ on $[0,\infty)$ by its Laplace transform

Here $F_\varepsilon(t)$ also denotes that law’s distribution function at $t$. The bilateral series converges in the supercritical parameter range. The source’s notation uses the same letter for a distribution and its distribution function; the Lean development keeps these roles separate as a measure and its value on $(-\infty,t]$.

Formalization targets

The first clause of Theorem (2.20) is the critical growth law. If $\gamma\theta=1$, then

The second clause describes the supercritical case. If $\gamma\theta>1$, $n_k\to\infty$, and $\{\log_\theta n_k\}\to\varepsilon$, then for each $x>0$,

Both clauses are the goal. The milestones record the transform identity of Lemma (2.5), its approximation and scaling limits in Lemmas (2.6)–(2.7), the mirror passage-time limits of Lemma (2.10), and the ordinary passage-time limits of Theorem (2.18). The fractional part in the goal uses base $\theta$; the two passage-time results use base $1/\gamma$, exactly as printed Solomon 1975, pp. 12–19.

What the result gives

The critical law identifies the constant in the growth scale $n/\log_\theta n$. The supercritical law shows that a single power normalization $n^{1/\rho}$ does not erase the logarithmic phase of the environment: the limiting distribution depends on the phase approached by the chosen subsequence. These assertions describe the position $X_n$ itself, rather than only the time needed to reach a distant site. They complement the paper’s general speed theorem by resolving the zero-speed behavior in a concrete model Solomon 1975, Theorems (1.16) and (2.20).

The results are proved in the 1975 paper; the open work here is machine checking their definitions, statements, and proofs. The development also yields reusable interfaces for a nearest-neighbour chain specified by cylinder probabilities, first-passage times that can be infinite, and Laplace-transform arguments for random time changes. The mission’s statements currently compile locally with proof placeholders, so they are formalization targets rather than machine-checked theorems.

Where the difficulty lies

The one-way mirrors create independent, identically distributed blocks of crossing times, but those times have tails governed by the random spacing between mirrors. At $\gamma\theta=1$, their accumulation produces a logarithmic correction; at $\gamma\theta>1$, the underlying geometric scales preserve the fractional part of a logarithm. An ordinary law of large numbers for passage times therefore cannot supply both limits. Moreover, a limit for passage times to the random mirror positions $V_n$ does not immediately give a limit for passage times to deterministic sites, and converting a passage-time limit into a position limit requires control of the inverse time change. The source separates these tasks across the milestone results Solomon 1975, pp. 11–20.

Formalization scope

The Lean environment is the pinned Mathlib revision 0df444a360eaa60ab8c11dca51a86af692955474. The position and environment are integer-indexed; time is natural-number-indexed. The one-way-mirror parameter range is $\theta>1$, $0<\gamma<1$, $\gamma\theta\ge1$. The strict bounds on $\gamma$ make both atom probabilities meaningful and the logarithm base $1/\gamma$ valid. The source uses these bounds implicitly. All probabilities concern the annealed joint law, not an arbitrary process with the same one-time marginals.

First-passage times are extended natural numbers, with infinity on paths that never hit the target. The real-valued limits convert finite passage times to real numbers; under the stated model, infinite passage times form a null event. The location of a nonexistent next mirror is assigned zero for a total Lean function, again only on a null event in this model. The Laplace transform of an infinite passage time is defined as zero. Convergence in probability uses TendstoInMeasure; convergence in law is expressed by convergence of distribution functions at continuity points. The limit-law family is constrained to probability measures supported on $[0,\infty)$ with the exact transform (2.12), preventing a degenerate or unrelated choice of $F$.

A complete proof needs measurable cylinder laws, independence of the mirror gaps, hitting-time and transform calculations, asymptotics of one-sided and bilateral series, distributional convergence from Laplace transforms, and inversion from passage time to position. Work on any of these components is in scope. The statement keeps both source regimes and every constant; replacing the joint walk law by independent marginals or choosing an arbitrary limit distribution would change the theorem.

Selected references

• Fred Solomon, Random Walks in a Random Environment, The Annals of Probability 3(1):1–31, 1975. DOI: 10.1214/aop/1176996444.

Motivation

Nonparametric regression estimates the conditional mean $E(Y\mid X=x)$ of a real response $Y$ given a predictor $X\in\mathbb R^d$ without assuming that it belongs to a finite-dimensional family. Most practical estimators of this kind are local averages: kernel estimators (Nadaraya 1964, Watson 1964), nearest-neighbor rules (Cover and Hart 1967), and their many variants all predict at a point $X$ by a weighted average $\sum_i W_{ni}(X)Y_i$ of the observed responses, with weights that depend only on the predictors.

C. J. Stone's 1977 paper in the Annals of Statistics (DOI 10.1214/aos/1176343886) asked when such a rule is consistent: when it converges to the true regression function in $L^r$ for every joint distribution of $(X,Y)$ with $E|Y|^r<\infty$, without smoothness or moment assumptions beyond that. Its Theorem 1 answers the question in terms of five conditions on the weights alone. The result is the standard starting point for distribution-free regression theory; it is the first theorem of the monograph of Györfi, Kohler, Krzyżak and Walk (2002), where it is called Stone's theorem, and it underlies the universal consistency of nearest-neighbor, kernel and partitioning estimates.

Setting

Let $\mu$ be a probability measure on $\mathbb R^d$ and let $X, X_1, X_2,\dots$ be independent with law $\mu$. A sequence of weights $\{W_n\}$ assigns to each $n\ge1$ and each point $(x,x_1,\dots,x_n)$ real numbers

The weights are nonnegative if every $W_{ni}\ge0$ and probability weights if in addition $\sum_i W_{ni}(x)=1$.

When $(X,Y),(X_1,Y_1),(X_2,Y_2),\dots$ are i.i.d. with $Y$ real valued, the estimate of $E(Y\mid X)$ is

The sequence $\{W_n\}$ is consistent if, for every such joint distribution with $X$-marginal $\mu$ and every $r\ge1$ with $E|Y|^r<\infty$,

The five conditions of Theorem 1 are:

1. there is a $C\ge1$ with $E\sum_i|W_{ni}(X)|f(X_i)\le C\,Ef(X)$ for every nonnegative Borel $f$ and every $n\ge1$;
2. there is a $D\ge1$ with $P\big(\sum_i|W_{ni}(X)|\le D\big)=1$ for every $n\ge1$;
3. $\sum_i|W_{ni}(X)|\,I_{\{\|X_i-X\|>a\}}\to0$ in probability for every $a>0$;
4. $\sum_i W_{ni}(X)\to1$ in probability;
5. $\max_i|W_{ni}(X)|\to0$ in probability.

Formalization targets

Goal: Theorem 1 (p. 598)

and conversely, if $\{W_n\}$ is consistent, then (4) and (5) hold; if moreover $W_n\ge0$ for all $n\ge1$, then (3) holds; and if $W_n\ge0$ and (2) holds, then (1) holds. The goal is the full theorem, both directions, as one statement.

Milestones (§10, pp. 607–610)

• Proposition 1: under (1)–(3), $E\sum_i|W_{ni}(X)||f(X_i)-f(X)|^r\to0$ whenever $r\ge1$ and $E|f(X)|^r<\infty$.
• Propositions 2 and 3: for nonnegative weights (respectively for $W_{ni}^2$), bounds on $\liminf$ and $\limsup$ of $E\sum_i W_{ni}(X)f(X_i)$ in terms of constants $M_n\le\sum_i W_{ni}(X)\le N_n$ holding with probability tending to one.
• Proposition 5: under (1)–(4), $\sum_i W_{ni}(X)f(X_i)\to f(X)$ in $L^r$.
• Proposition 6: nonnegative weights that reproduce every bounded continuous $f$ in probability satisfy (3).
• Proposition 7: if $\limsup_n E\sum_i W_{ni}(X)f(X_i)<\infty$ for every integrable nonnegative $f$, a single pair $(n_0, C)$ works for all $f$.
• Proposition 8: if $\sum_i W_{ni}(X)Y_i\to0$ in probability for independent standard normal $Y_i$, then $\sum_i W^2_{ni}(X)\to0$ in probability.

Significance

The result. Theorem 1 reduces a statement about all joint distributions of $(X,Y)$ to properties of the weights under the law of $X$ alone. For probability weights, conditions (2) and (4) hold automatically, and (1), (3), (5) become necessary and sufficient (Corollary 1). This is how Stone proves that nearest-neighbor weights with suitably vanishing coefficients are universally consistent (Theorem 2 of the paper), and how consistency transfers to estimators of conditional quantiles and to approximate Bayes rules in classification and decision problems (Sections 7–8). Condition (1), the only condition that is not a convergence statement, is the one that later work on kernel and partitioning estimates had to verify by geometric covering arguments.

Formalizing it. The theorem is proved in the paper and in textbooks; it has no machine-checked proof that we know of. A formalization produces a reusable criterion: any later development of local-averaging estimators can discharge consistency by checking five conditions about the predictor distribution. The supporting propositions are of independent use: Proposition 1 is an $L^r$ approximation lemma for weighted empirical averages, and Proposition 7 is a uniform-boundedness principle for sequences of positive operators on $L^1(\mu)$.

Difficulty

The sufficiency half combines three ingredients that have to fit together at the level of measure theory: approximation of an arbitrary $L^r$ function by continuous functions with compact support, uniformly over $n$ through condition (1); a variance computation for the noise term that conditions on the predictors; and a truncation argument to pass from bounded responses and $r=2$ to all $r\ge1$. The natural first idea, to apply a weak law of large numbers to $\sum_i W_{ni}(X)Y_i$, fails because the weights are dependent on all of $X, X_1,\dots,X_n$ and are not identically distributed.

The necessity half needs separate arguments for each condition: a test-function argument with bounded continuous $f$ for (3), a contradiction argument summing a sequence of functions $f_\nu$ for (1), and a Gaussian anti-concentration argument for (5), which is where the auxiliary normal variables of the paper enter.

Formalization scope

• Data. The i.i.d. sequence $X, X_1, X_2,\dots$ is the coordinate process of the product measure $\mu^{\otimes\mathbb N}$ on $(\mathbb R^d)^{\mathbb N}$, coordinate $0$ being $X$. "Whenever $(X,Y),(X_1,Y_1),\dots$ are i.i.d." is encoded by quantifying over every Markov kernel $\kappa$ from $\mathbb R^d$ to $\mathbb R$ (the conditional law of $Y$ given $X$); the pairs are the coordinates of $(\mu\otimes\kappa)^{\otimes\mathbb N}$ and $E(Y\mid X=x)=\int y\,\kappa(x,dy)$. Every joint law with $X$-marginal $\mu$ arises in this way.
• Standing assumptions. The paper's assumption (p. 596) that independent standard normal variables are available on the probability space is supplied by the kernel $\kappa\equiv N(0,1)$. The weights are assumed jointly Borel in $(x,x_1,\dots,x_n)$; the paper treats $W_{ni}(X)$ as random variables without saying so.
• Conventions. Expectations of nonnegative quantities (in (1), in $E|Y|^r$, in the $L^r$ distances and in Propositions 1–3, 5, 7) are lower Lebesgue integrals in $[0,\infty]$, and the $\liminf$/$\limsup$ of Propositions 2, 3, 7 are in $[0,\infty]$, so no infinite expectation is silently read as $0$. Convergence in probability is Mathlib's TendstoInMeasure. Sample indices are $0$-based. Conditions on individual $n$ are stated for $n\ge1$.
• Correction of the print. The definition of consistency on p. 597 prints "$r>1$"; the proof of Theorem 1 (p. 611, (13)) and the rest of the paper work with every $r\ge1$, which is the formalized reading.
• Not a trivialization. The goal quantifies over every conditional law $\kappa$ and every real $r\ge1$; a version for bounded $Y$ or for $r=2$ only would be weaker than the theorem, and the converse parts conclude the conditions (1), (3), (4), (5) themselves.
• Infrastructure. A complete development needs products of probability measures and their coordinate processes, Lusin-type density of compactly supported continuous functions in $L^r(\mu)$, conditional variance computations given finitely many coordinates, and the Gaussian tail bound. These pieces are reusable well beyond this mission. Proofs of individual propositions, and of either direction of Theorem 1 separately, are welcome contributions.

Selected references

• C. J. Stone, Consistent nonparametric regression, Ann. Statist. 5(4), 595–645, 1977. https://doi.org/10.1214/aos/1176343886
• L. Györfi, M. Kohler, A. Krzyżak, H. Walk, A Distribution-Free Theory of Nonparametric Regression, Springer, 2002. https://doi.org/10.1007/b97848
• T. M. Cover, P. E. Hart, Nearest neighbor pattern classification, IEEE Trans. Inform. Theory 13(1), 21–27, 1967. https://doi.org/10.1109/TIT.1967.1053964
• E. A. Nadaraya, On estimating regression, Theory Probab. Appl. 9(1), 141–142, 1964. https://doi.org/10.1137/1109020
• G. S. Watson, Smooth regression analysis, Sankhyā Ser. A 26(4), 359–372, 1964. https://www.jstor.org/stable/25049340

Motivation

Many quantities in queueing, inventory and reliability models are additive functionals of a regenerative process: the total work processed by a server up to time $t$, the cost accumulated by an inventory policy, the time a machine spends broken. Each such quantity grows by independent, identically distributed amounts over the cycles between successive regeneration points. W. L. Smith called these cumulative processes in Regenerative stochastic processes (Proc. R. Soc. Lond. A, 1955), the paper that introduced the term "regenerative process" and laid out its limit theory. Long-run averages of such quantities are estimated by simulation and by statistical observation of real systems. Confidence intervals for these estimates, and the regenerative method of simulation output analysis, rest on the central limit theorem for cumulative processes. When several quantities are estimated at once (a ratio of two rewards, a vector of costs), they rest on its joint version for several cumulative processes driven by the same regenerations.

Timeline:

• 1949. Feller proves the central limit theorem for the renewal counting process.
• 1952. Anscombe proves that a central limit theorem survives replacing the number of summands by a random index $m_t$ with $m_t/\psi(t)\to 1$ in probability, without independence between the index and the summands (Anscombe, Proc. Camb. Phil. Soc. 48, 1952).
• 1955. Smith extends Anscombe's theorem to random vectors and deduces the univariate (Theorem 9, Corollary 9·1) and multivariate (Theorem 10) central limit theorems for cumulative processes (Smith 1955).

Setting

On a probability space $(\Omega, P)$, let $t_1, t_2, \dots$ be independent, identically distributed, non-negative random variables with $P\{t_1 = 0\} < 1$ (a renewal process), and $t_0 = 0$. The regeneration epochs are $T_k = t_0 + t_1 + \dots + t_k$ ($k \ge 0$), and $n_t$ is the number of epochs in $[0,t]$ (in Smith's words, the greatest $k$ with $T_{k-1} \le t$, where $T_{-1} = 0$). Write $\mu_r = E t_1^r$.

A real process $w_t$ with $w_0 = 0$ is a cumulative process if (C1) its cycle increments $y_n = \Delta_n w_t = w_{T_n} - w_{T_{n-1}}$, $n \ge 1$, are i.i.d., and (C2) with probability one its paths have bounded variation on every finite interval. The variation process $\tilde w_t = \int_0^t |\mathrm d w_t|$ has increments $\tilde y_n = \Delta_n \tilde w_t$. Moments are written $\kappa_r = E y_n^r$ and $\tilde\kappa_r = E \tilde y_n^{\,r}$.

$M$ cumulative processes $w^{(1)}_t, \dots, w^{(M)}_t$ are based on the same sequence of regeneration points when the cycle vectors $(t_n, y^{(1)}_n, \dots, y^{(M)}_n, \tilde y^{(1)}_n, \dots, \tilde y^{(M)}_n)$ are i.i.d. in $n$. Put $\kappa^{(i)}_1 = E y^{(i)}_1$. The covariance matrices are

Formalization targets

Goal: Theorem 10

If $\mu_1 < \infty$ and $E(\tilde y^{(i)}_1)^2 < \infty$ for every $i$, then as $t \to \infty$

and if in addition $\mu_2 < \infty$,

Milestones

• The renewal strong law $n_t/t \to 1/\mu_1$ almost surely (§5·3).
• Lemma 8: if $\mu_1 < \infty$ and $\tilde\kappa_p < \infty$, then $(w_{t+Z_t} - w_t)/t^{1/p} \to 0$ almost surely, where $Z_t = \sum_1^{n_t+1} t_i - t$.
• Theorem B (Anscombe): $P\{\sum_1^{m_t} y_i/(\sigma\psi(t)^{1/2}) \le \alpha\} \to \Phi(\alpha)$ for i.i.d. centred $y_i$ with variance $\sigma^2 > 0$ and $m_t/\psi(t) \to 1$ in probability.
• Its $M$-dimensional form (§5·4): $\psi(t)^{-1/2}\sum_1^{m_t} \mathbf y_j \xrightarrow{d} \mathcal N(0, a)$ for i.i.d. centred random vectors.
• Theorem 9: if $E y_1 = 0$ and $\operatorname{var} y_1 = \sigma^2 > 0$, then $P\{w_t/(\sigma(t/\mu_1)^{1/2}) \le \alpha\} \to \Phi(\alpha)$.
• Corollary 9·1: the univariate forms of both assertions of the goal, with normalisations $\sigma = (\kappa_2 - \kappa_1^2)^{1/2}$ and $\gamma = \operatorname{var}(y_1 - (\kappa_1/\mu_1)t_1)$.

Significance

Theorem 10 is the multivariate central limit theorem for regenerative processes. Its second assertion with $M = 2$ and the delta method gives the asymptotic normality of ratio estimators $w^{(1)}_t / w^{(2)}_t$, the basis of the regenerative method of simulation output analysis. With $w_t = n_t$, Corollary 9·1 recovers Feller's central limit theorem for renewal processes, which Smith points out (p. 9). The first assertion, with the random centring $\kappa_1 n_t$, needs only $\mu_1 < \infty$, which matters for heavy-tailed cycle lengths.

The results are classical and proved, and none of them is formalized. Mathlib has the central limit theorem for i.i.d. real sums with a deterministic number of terms and multivariate Gaussian laws, but no random-index central limit theorem, no renewal counting process and no regenerative process. A formal development would supply Anscombe's theorem (useful well beyond renewal theory, for sequential analysis and random sums), the renewal strong law and a reusable model of cumulative processes.

Difficulty

The obvious argument writes $w_t$ as the sum of the first $n_t$ cycle increments plus a remainder and applies the classical central limit theorem. This fails at two points. First, the number of summands $n_t$ is random and depends on the summands themselves (cycle lengths and rewards are typically dependent), so the classical theorem with a deterministic index does not apply and conditioning on $n_t$ destroys the i.i.d. structure. Anscombe's theorem is needed exactly for this; it requires control of the partial sums uniformly over a window of indices around $t/\mu_1$, not at a single index. Second, the remainder over the incomplete cycle at time $t$ must be shown negligible on the scale $\sqrt t$ using only a second moment of the cycle variation; Lemma 8 does this almost surely. For the vector statement, the scalar theorem must be lifted to convergence in distribution in $\mathbb R^M$ with a possibly degenerate covariance matrix, where the scalar theorem's hypothesis $\sigma > 0$ can fail along some directions.

Formalization scope

• Time is real; every limit is along $t \to \infty$ in $\mathbb R$. Processes are functions $w : \mathbb R \to \Omega \to \mathbb R$ (or a family indexed by Fin M); cycle lengths are a sequence $\mathbb N \to \Omega \to \mathbb R$ with $t_0 = 0$.
• $n_t$ is a natural number, the number of epochs $T_j \le t$; on the null event where infinitely many epochs are $\le t$ it is $0$. Finiteness is never assumed.
• $\tilde w_t$ is the total variation (eVariationOn) of the path on $[0,t]$, set to $0$ for all $t$ on paths of infinite variation, as Smith allows.
• Condition (C1) is read for the whole cycle vector $(t_n, y_n, \tilde y_n)$. No independence between components is assumed. Assuming the cycle length independent of the rewards, or the components independent, would make $a$ diagonal or force $b$ into a special form; that trivialization is ruled out.
• "Jointly normally distributed with covariance matrix $a$" is TendstoInDistribution to multivariateGaussian 0 a on EuclideanSpace ℝ (Fin M). The matrices $a$ and $b$ are defined as covariance matrices, hence positive semidefinite, so the limit is a genuine (possibly degenerate) Gaussian law and not Mathlib's Dirac fallback for non-PSD input.
• The scalar statements keep the paper's form: convergence of $P\{\cdot \le \alpha\}$ to $\Phi(\alpha) =$ cdf (gaussianReal 0 1) α for every real $\alpha$. The paper's implicit $\sigma > 0$ and $\gamma > 0$ are explicit hypotheses; without them the quotients are $0$ in Lean and the statements would be false.
• $\mu_1 < \infty$, $\mu_2 < \infty$ and $E\tilde y^2 < \infty$ are Integrable hypotheses, never encoded through the value of an integral.

Contributions welcome: a proof of Anscombe's theorem from Mathlib's central limit theorem; the renewal strong law from strong_law_ae; measurability lemmas for $n_t$ and $\tilde w_t$; the Cramér–Wold step.

Selected references

• W. L. Smith, Regenerative stochastic processes, Proc. R. Soc. Lond. A 232(1188):6–31, 1955. https://doi.org/10.1098/rspa.1955.0198
• F. J. Anscombe, Large-sample theory of sequential estimation, Proc. Cambridge Philos. Soc. 48, 600, 1952 (cited in Smith 1955, p. 31).
• W. Feller, Fluctuation theory of recurrent events, Trans. Amer. Math. Soc. 67, 98, 1949 (cited in Smith 1955, p. 31).
• J. L. Doob, Renewal theory from the point of view of the theory of probability, Trans. Amer. Math. Soc. 63, 422, 1948 (cited in Smith 1955, p. 31).

Motivation

Two-stage stochastic programming with recourse models a decision taken in two steps: a first-stage decision $x_1$ is fixed before a random outcome $s$ is observed, and a recourse decision $x_2(s)$ is taken afterwards, once $s$ is known. The model goes back to Dantzig (1955) and Beale (1955) and is the basic template of stochastic optimization in operations research: capacity planning before demand is known, production before prices are revealed, reservoir management before inflows are observed.

When the outcome space is not finite, the recourse is a function $x_2(\cdot)$, and the problem must specify the class of functions it ranges over. Rockafellar and Wets (Pacific J. Math. 62 (1976) 173–195) develop the duality theory of the convex case with recourse functions that are measurable and essentially bounded ($\mathcal L^\infty$), the setting in which the dual multipliers and their interpretation as prices become available. Their §3 asks whether that restriction loses anything: whether minimizing over $\mathcal L^\infty$ recourses gives the same first-stage problem as minimizing, scenario by scenario, the best attainable second-stage cost.

Setting

Let $(S,\Sigma,\sigma)$ be a probability space. The data are closed convex nonempty sets $C_1\subseteq\mathbb R^{n_1}$, $C_2\subseteq\mathbb R^{n_2}$, finite convex functions $f_{10},f_{1i}$ on $\mathbb R^{n_1}$ ($i=1,\dots,m_1$), and functions $f_{20}(s,x_1,x_2)$, $f_{2i}(s,x_1,x_2)$ ($i=1,\dots,m_2$), finite and jointly convex in $(x_1,x_2)$ for each $s$, and measurable in $s$ for each $(x_1,x_2)$, summable for $i=0$ and bounded for $i\ge1$. These are the paper's standing assumptions.

With $X=\mathbb R^{n_1}\times\mathcal L^\infty_{n_2}$, the essential objective of the problem $\mathbf P$ is

where $F_1(x_1,u_1)=f_{10}(x_1)$ if $x_1\in C_1$ and $f_{1i}(x_1)\le u_{1i}$ for all $i$, and $+\infty$ otherwise, and $F_2(s,x_1,x_2,u_2)=f_{20}(s,x_1,x_2)$ if $x_2\in C_2$ and $f_{2i}(s,x_1,x_2)\le u_{2i}$ for all $i$, and $+\infty$ otherwise. Integrals of extended-real functions follow the paper's convention (2.4): the ordinary integral (real or $-\infty$) when the integrand is majorized by a summable function, and $+\infty$ otherwise.

Two first-stage problems are compared:

• the first-stage problem induced by $\mathbf P$ minimizes $J(x_1)=\inf_{x_2\in\mathcal L^\infty_{n_2}}f(x_1,x_2)$;
• the intrinsic first-stage problem $\mathbf Q$ minimizes $j(x_1)=F_1(x_1,0)+\int_S q(s,x_1)\,\sigma(ds)$, where $q(s,x_1)=\inf_{x_2\in\mathbb R^{n_2}}F_2(s,x_1,x_2,0)$ is the optimal recourse cost in scenario $s$.