Introduction
The classical secretary problem asks a decision maker to select the best candidate from a sequence arriving in uniformly random order. Each candidate must be accepted or rejected immediately, and a rejected candidate cannot be recalled. When the decision maker observes only relative ranks, the optimal probability of selecting the best candidate tends to 1 / e 1/e 1/ e [4 ] . Observing numerical values drawn i.i.d. from a known continuous distribution improves the limit to approximately 0.58 in the full-information best-choice problem [8 GKS23] . In both settings, selecting the single best candidate leaves a constant probability of failure even as the number of candidates grows.
Several criteria can change which outcomes are acceptable. A hiring committee may compare candidates by education and professional experience without assigning a common numerical score to the two attributes. One candidate may have more education, while another has more experience. These candidates represent different tradeoffs, and either can be a reasonable choice when the criteria are assessed together. This setting leads naturally to a selection objective that allows several mutually incomparable outcomes.
We represent a candidate by a point in R d \mathbb{R}^{d} R d Pareto maximal if no other point in the sample dominates it; the set of all such points is the Pareto frontier . We study a known number n n n Z 1 , … , Z n Z_1,\ldots,Z_n Z 1 , … , Z n d = 1 d=1 d = 1
This additional freedom changes the asymptotic outcome. For every fixed d ≥ 2 d\ge2 d ≥ 2
Main results
We compare two information settings. A full-information rule knows the joint distribution and observes numerical values. A rank-based rule observes only the ranking of all observations seen so far in each coordinate. Below, we specify what distributional knowledge the rank-based rules need. We consider fixed dimensions d ≥ 2 d\ge2 d ≥ 2 n → ∞ n\to\infty n → ∞
The expected number of acceptable observations gives a common way to express our main result. Let M n M_n M n
1 − p n ∗ ∼ 2 M n log M n , 1-p_n^* \sim\frac{2}{M_n\log M_n}, 1 − p n ∗ ∼ M n log M n 2 , where p n ∗ p_n^* p n ∗ ∼ \sim ∼ n → ∞ n\to\infty n → ∞ § 6.5 derives the common relation from the distribution-specific bounds.
Independent coordinates. We first assume that the coordinates of each observation are independent and have continuous distributions, which may differ across coordinates. A simple cutoff rule rejects the first s s s
log log n ( log n ) d − 1 \frac{\log\log n}{(\log n)^{d-1}} ( log n ) d − 1 log log n (Theorems 3.2 and 3.3 ).
We then improve this bound with a time-dependent threshold rule. It selects the first point that no earlier observation dominates and whose probability of being dominated by a new independent observation is below a threshold specified for its arrival time. This threshold increases as fewer observations remain, allowing more points to be accepted near the end. The failure probability improves to order
1 ( log n ) d − 1 log log n . \frac{1}{(\log n)^{d-1}\log\log n}. ( log n ) d − 1 log log n 1 . We determine the leading constants for both rules, which depend only on the dimension. A rank-based implementation of the more selective rule achieves the same leading failure probability as the optimal full-information rule, for every choice of continuous marginal distributions (Theorem 4.1 ). It needs to know only that the coordinates are independent.
Allowing dependence. We next allow dependence between coordinates, while observations remain independent. Without restrictions on this dependence, the improvement over one-dimensional selection can disappear. We construct a fixed distribution with a joint density and uniform marginals whose optimal full-information probability tends to ≈ 0.5801 \approx0.5801 ≈ 0.5801 [8 ] . This is the sharp asymptotic worst-case constant among distributions with a joint density, since using a single coordinate always gives at least the one-dimensional full-information probability (Theorem 5.1 ).
For Gaussian observations with a fixed positive definite covariance matrix Σ \Sigma Σ a Σ a_{\Sigma} a Σ
M n ∼ a Σ ( log n ) d − 1 . M_n \sim a_{\Sigma}(\log n)^{d-1}. M n ∼ a Σ ( log n ) d − 1 . A larger coefficient means a larger expected frontier at the same sample size, to first order. It equals 1 / ( d − 1 ) ! 1/(d-1)! 1/ ( d − 1 )! 6.2 ). A rank-based rule again matches the optimal full-information leading term, knowing only that the observations are Gaussian, without knowing their means, variances, or correlations.
We also consider singular Gaussian distributions, whose observations lie in a lower-dimensional affine subspace, and characterize how the relationships between coordinates affect the selection guarantees (§ 6.4 ).
Proof overview
For independent coordinates, we apply each marginal distribution function and then the inverse standard Gaussian distribution function to obtain independent standard Gaussian coordinates. Because we assume the distributions are absolutely continuous, this preserves independence and, almost surely, the ranking in every coordinate and hence which points are maximal. It gives us a common starting point for the later extension to Gaussian dependence.
Our rules never select a point already dominated by an earlier observation. They can therefore fail in two ways, by selecting nothing or by selecting a point that a later observation dominates. For a cutoff rule, waiting longer leaves fewer opportunities to select, but also fewer later observations that might dominate the selected point. We estimate both probabilities and balance them to find the best cutoff.
A more selective rule accepts only points that a new observation is unlikely to dominate. Such points are rare, so a rule that selects with high probability must sometimes accept a point that a later observation dominates. This gives a lower bound on failure. Our time-dependent threshold rule matches it. We bound how often an observation meets the threshold without being dominated by earlier observations, and hence how likely the rule is still waiting at each time. We then add the probabilities of selecting a point that a later observation dominates, bounding all failure near the end by the probability of still waiting.
To implement the rule using only coordinate rankings, we reject the first half of the observations and use them as a sample. For each later observation, we use the number of sample observations exceeding it in each coordinate to estimate the probability of being exceeded in that coordinate. Under independence, the product estimates its probability of being dominated by a new observation. We prove that these estimates are accurate enough to give the same leading failure probability as with known distributions.
With Gaussian dependence, a linear transformation makes the coordinates independent, but changes the directions in which one point dominates another (Figure 1 ). Probability estimates for the new comparison regions let us extend both the fixed-cutoff analysis and the lower and upper bounds on the optimal failure probability from the independent case. The rank-based rule also estimates the correlations from the initial sample.
Figure 1. A change of coordinates makes the Gaussian coordinates independent. The shaded regions identify the same dominating observations; after the change, comparisons follow the slanted region.
The other results use separate arguments. For arbitrary dependence, we construct a distribution where the additional coordinates provide no useful alternative to selecting the first-coordinate maximum. To compare values with ranks in the worst case, we adapt the method of Correa et al. [2 ] . We change numerical values without changing their order, making a rule’s decisions depend almost entirely on ranks.
Related work
The early literature on stopping at a Pareto-optimal option includes Gnedin [Gne83]; Ferguson [5 ] discusses this line of multicriteria stopping problems. Gnedin models the criteria as independent uniform random rankings and proves that, for two criteria, a fixed-cutoff rule can select a Pareto-maximal observation with probability tending to one. Independent continuous marginals induce the same rank distribution, so this conclusion also applies to our rank-based setting. The fixed-cutoff rule is the same as the one we analyze under independence. His result establishes the existence of cutoffs whose selection probability tends to one; we characterize all such cutoff sequences and determine the best cutoff failure asymptotics. Our analysis determines the sharp first-order failure asymptotics, compares numerical and rank information, and relates stopping difficulty to expected frontier size under independent coordinates and Gaussian dependence.
Another multiple-criteria objective accepts an observation that is best in at least one criterion. Gnedin [10 ] studies this objective using relative ranks under independent criteria. With two criteria, at most two observations are acceptable. Pareto maximality also accepts intermediate tradeoffs that maximize neither coordinate, and the expected frontier size grows with the sample under independence. Ferguson [5 ] and Gnedin [Gne94] study dependent-criteria variants. Samuels and Chotlos [SC86] instead minimize the expected sum of final coordinate ranks, with rank one best in each coordinate. Yu, Jacobson, and Kiyavash [YJK19] consider multiple selections with full information and two expected-reward objectives, studying policies that are Pareto optimal with respect to those objectives.
Secretary problems on partially ordered sets share the objective of selecting a maximal element. Freij and Wästlund [6 ] obtain a probability at least 1 / e 1/e 1/ e [9 ] obtain a sharp improving bound when the width, the largest number of mutually incomparable elements, equals the number of maximal elements; they also obtain a 1 / e 1/e 1/ e (34) . Partial comparisons also arise in selection models motivated by biased evaluations and fairness, with score-based or group-based objectives [SG24, CCDNF21].
The unknown-marginal reduction adapts the Ramsey-theoretic method of Correa et al. [2 ] for making stopping decisions insensitive to numerical labels. Their objective maximizes the expected selected value relative to the expected sample maximum; ours maximizes the probability of selecting a Pareto-maximal point. Applying Ramsey theory to coordinate grids gives increasing changes of numerical values that preserve all coordinate comparisons. The argument allows dependence and ties, including singular distributions. The complete reduction appears in Appendix § 11 .
Organization. § 2 gives the model and information settings. § 3 and § 4 analyze fixed cutoffs and optimal stopping for independent coordinates. § 5 studies arbitrary dependence, and § 6 extends the analysis to Gaussian dependence and singular cases, followed by discussion.
The appendices contain the rank-sufficiency reduction and the probability and sample estimates used in the stopping proofs.
Model and Information Settings
Model
Fix a horizon n ∈ N n \in\mathbb{N} n ∈ N d ≥ 2 d \ge2 d ≥ 2 Z 1 , … , Z n Z_1,\ldots,Z_n Z 1 , … , Z n F F F R d \mathbb{R}^d R d F F F z , z ′ ∈ R d z,z' \in\mathbb{R}^d z , z ′ ∈ R d z ⪯ z ′ z \preceq z' z ⪯ z ′ z ( k ) ≤ z ′ ( k ) z^{(k)} \le z'^{(k)} z ( k ) ≤ z ′ ( k ) k ∈ [ d ] k \in[d] k ∈ [ d ] z ≺ z ′ z \prec z' z ≺ z ′ z ≠ z ′ z \ne z' z = z ′ z ′ z' z ′ dominates z z z z 1 , … , z t z_1,\ldots,z_t z 1 , … , z t Pareto frontier is
Max ( z 1 , … , z t ) = { z i : ∄ j ∈ [ t ] such that z i ≺ z j } . \operatorname{Max}(z_1,\ldots,z_t) = \{z_i : \nexists j \in[t]\text{ such that }z_i \prec z_j\}. Max ( z 1 , … , z t ) = { z i : ∄ j ∈ [ t ] such that z i ≺ z j } . At time t t t Z t Z_t Z t currently maximal when Z t ∈ Max ( Z 1 , … , Z t ) Z_t \in\operatorname{Max}(Z_1,\ldots,Z_t) Z t ∈ Max ( Z 1 , … , Z t ) maximal when Z t ∈ Max ( Z 1 , … , Z n ) Z_t \in\operatorname{Max}(Z_1,\ldots,Z_n) Z t ∈ Max ( Z 1 , … , Z n )
The decision maker knows the horizon n n n t t t Z t Z_t Z t success ; selecting a nonmaximal observation or making no selection counts as a failure .
A stopping rule r = ( r 1 , … , r n ) \mathbf{r}=(r_1,\ldots,r_n) r = ( r 1 , … , r n ) r t : ( R d ) t → [ 0 , 1 ] r_t:(\mathbb{R}^d)^t \to[0,1] r t : ( R d ) t → [ 0 , 1 ] r t r_t r t t t t U 1 , … , U n ∼ Unif [ 0 , 1 ] U_1,\ldots,U_n \sim\operatorname{Unif}[0,1] U 1 , … , U n ∼ Unif [ 0 , 1 ]
τ r = inf { t ∈ [ n ] : U t ≤ r t ( Z 1 , … , Z t ) } , inf ∅ = ∞ . \tau_{\mathbf{r}}=\inf\{t\in[n]:U_t\le r_t(Z_1,\ldots,Z_t)\},\qquad\inf\varnothing=\infty. τ r = inf { t ∈ [ n ] : U t ≤ r t ( Z 1 , … , Z t )} , inf ∅ = ∞. For a fixed rule we write τ \tau τ τ r \tau_{\mathbf{r}} τ r
p F ( r ) = P F { τ ≤ n , Z τ ∈ Max ( Z 1 , … , Z n ) } . p_F(\mathbf{r})=\mathbb{P}_F\{\tau\le n,\ Z_\tau\in\operatorname{Max}(Z_1,\ldots,Z_n)\}. p F ( r ) = P F { τ ≤ n , Z τ ∈ Max ( Z 1 , … , Z n )} . For conditioning in proofs, write
H 0 = { ∅ , Ω } , H t = σ ( Z 1 , … , Z t , U 1 , … , U t ) , t ∈ [ n ] , \mathcal{H}_0=\{\varnothing,\Omega\},\qquad\mathcal{H}_t=\sigma(Z_1,\ldots,Z_t,U_1,\ldots,U_t),\qquad t\in[n], H 0 = { ∅ , Ω } , H t = σ ( Z 1 , … , Z t , U 1 , … , U t ) , t ∈ [ n ] , where σ ( ⋅ ) \sigma(\cdot) σ ( ⋅ ) t t t
For a point z z z q F ( z ) = P { z ≺ Z } q_F(z)=\mathbb{P}\{z\prec Z\} q F ( z ) = P { z ≺ Z } domination risk of z z z Z ∼ F Z\sim F Z ∼ F q ( z ) q(z) q ( z ) F F F t t t Z t Z_t Z t
P { Z t ∈ Max ( Z 1 , … , Z n ) ∣ Z 1 , … , Z t } = 1 { Z t ∈ Max ( Z 1 , … , Z t ) } ( 1 − q ( Z t ) ) n − t . (1) \mathbb{P}\{Z_t\in\operatorname{Max}(Z_1,\ldots,Z_n)\mid Z_1,\ldots,Z_t\}
=\mathbb{1}\{Z_t\in\operatorname{Max}(Z_1,\ldots,Z_t)\}(1-q(Z_t))^{n-t}. \tag*{(1)} P { Z t ∈ Max ( Z 1 , … , Z n ) ∣ Z 1 , … , Z t } = 1 { Z t ∈ Max ( Z 1 , … , Z t )} ( 1 − q ( Z t ) ) n − t . (1) The indicator requires that no earlier observation dominates Z t Z_t Z t
{ τ = ∞ } ⏟ no selection and { τ ≤ n , ∃ j > τ : Z τ ≺ Z j } ⏟ later domination \underbrace{\{\tau= \infty\}}_{\text{no selection}}
\quad\text{and}\quad
\underbrace{\{\tau\le n,\ \exists j > \tau: Z_\tau\prec Z_j\}}_{\text{later domination}} no selection { τ = ∞ } and later domination { τ ≤ n , ∃ j > τ : Z τ ≺ Z j } These names refer to these two events. An unrestricted rule can also fail by selecting an observation already dominated when it arrives.
Additional Notation. All logarithms are natural unless a base is displayed. Dimensions and distribution parameters are fixed as n → ∞ n \to\infty n → ∞ c c c c d c_d c d c Σ c_\Sigma c Σ O O O o o o Ω \Omega Ω Θ \Theta Θ X s → p X X_s \xrightarrow{p} X X s p X o p ( 1 ) o_p(1) o p ( 1 )
Information Settings
We distinguish what the decision maker observes from what it knows about F F F full-information setting , it knows F F F [8 ] , with the objective of selecting a maximal observation. Write
p n ∗ ( F ) = sup r p F ( r ) p_n^*(F) = \sup_{\mathbf r} p_F(\mathbf r) p n ∗ ( F ) = r sup p F ( r ) for the optimal probability in this setting; the rule may depend on F F F
A rank-based rule uses only coordinate comparisons among the observations seen so far, together with their arrival order. Such rules are natural when the marginal distributions are unknown, as comparisons still determine which observations are maximal, without requiring a numerical scale for each criterion. Formally, for i ≤ t i \le t i ≤ t k ∈ [ d ] k \in[d] k ∈ [ d ]
R t , i ( k ) = 1 + # { j ≤ t : Z j ( k ) < Z i ( k ) } , R t = ( R t , i ( k ) ) i ∈ [ t ] , k ∈ [ d ] . R_{t,i}^{(k)} = 1 + \#\{j \le t : Z_j^{(k)} < Z_i^{(k)}\}, \qquad\mathcal{R}_t = \left(R_{t,i}^{(k)}\right)_{i \in[t],\,k \in[d]}. R t , i ( k ) = 1 + # { j ≤ t : Z j ( k ) < Z i ( k ) } , R t = ( R t , i ( k ) ) i ∈ [ t ] , k ∈ [ d ] . The array R t \mathcal{R}_t R t rank grid [ t ] d [t]^d [ t ] d i i i Figure 2 ). A rule is rank-based if its stopping probability at time t t t R t \mathcal{R}_t R t
Figure 2. Six observations and their coordinate ranks on a 6 × 6 6 \times6 6 × 6
To specify that knowledge, let G G G R n \mathcal{R}_n R n n n n
F ( G ) = { F : R n has distribution G under F ⊗ n } . \mathcal{F}(G) = \{F : \mathcal{R}_n\text{ has distribution }G\text{ under }F^{\otimes n}\}. F ( G ) = { F : R n has distribution G under F ⊗ n } . The complete array determines all earlier comparisons and whether a selected observation is maximal. Thus any fixed rank-based rule has the same value for every F ∈ F ( G ) F \in\mathcal{F}(G) F ∈ F ( G ) p n , r a n k ∗ ( G ) p_{n,\mathrm{rank}}^*(G) p n , rank ∗ ( G ) G G G
Theorem 2.1. Fix n n n d d d G G G R n \mathcal{R}_n R n G G G F ∈ F ( G ) F \in\mathcal{F}(G) F ∈ F ( G )
sup F ∈ F ( G ) p F ( r ) = p n , rank ⋆ ( G ) . \sup_{F \in\mathcal{F}(G)} p_F(\mathbf{r}) = p^\star_{n,\operatorname{rank}}(G). F ∈ F ( G ) sup p F ( r ) = p n , rank ⋆ ( G ) . More strongly, fix any F 0 ∈ F ( G ) F_0 \in\mathcal{F}(G) F 0 ∈ F ( G ) r \mathbf{r} r ε > 0 \varepsilon> 0 ε > 0 T 1 , … , T d T_1,\ldots,T_d T 1 , … , T d r ′ \mathbf{r}' r ′ F F F ( T 1 ( Z ( 1 ) ) , … , T d ( Z ( d ) ) ) (T_1(Z^{(1)}),\ldots,T_d(Z^{(d)})) ( T 1 ( Z ( 1 ) ) , … , T d ( Z ( d ) )) Z ∼ F 0 Z \sim F_0 Z ∼ F 0
p F ( r ) ≤ p F ( r ′ ) + ε . p_F(\mathbf{r}) \le p_F(\mathbf{r}') + \varepsilon. p F ( r ) ≤ p F ( r ′ ) + ε . The proof in Appendix A adapts the finite-Ramsey argument of Correa et al. [2 ] . The equality applies when the marginal scales are unknown and unrestricted. Numerical values can still help when F F F
When F F F G G G
Independent coordinates. First consider independent coordinates with continuous marginal distributions. Write
F d = { F 1 ⊗ ⋯ ⊗ F d : F 1 , … , F d have continuous distribution functions } . \mathcal{F}_d = \{F_1 \otimes\cdots\otimes F_d : F_1,\ldots,F_d \text{ have continuous distribution functions}\}. F d = { F 1 ⊗ ⋯ ⊗ F d : F 1 , … , F d have continuous distribution functions } . Continuity excludes point masses but does not require a density. In the rank-based setting, the marginals are unknown, but independence is known. It determines G G G F d \mathcal{F}_d F d Φ \Phi Φ
Φ ( x ) = ∫ − ∞ x e − t 2 / 2 2 π d t . \Phi(x) = \int_{-\infty}^{x} \frac{e^{-t^2/2}}{\sqrt{2\pi}}\,\mathrm{d}t. Φ ( x ) = ∫ − ∞ x 2 π e − t 2 /2 d t . When the marginals are known, the coordinate transformation
z ( k ) ⟼ Φ − 1 ( F k ( z ( k ) ) ) z^{(k)} \longmapsto\Phi^{-1}\left(F_k\left(z^{(k)}\right)\right) z ( k ) ⟼ Φ − 1 ( F k ( z ( k ) ) ) gives independent standard Gaussian coordinates and preserves all sample comparisons with probability one. We denote their joint distribution by N d ( 0 , I d ) \mathcal{N}_d(0,I_d) N d ( 0 , I d ) [ 0 , 1 ] [0,1] [ 0 , 1 ]
The same rank observations arise from fixed coordinate lists. For each coordinate, fix n n n i i i i i i F d \mathcal{F}_d F d
Gaussian coordinates. More generally, write N d ( μ , Σ ) \mathcal{N}_d(\mu,\Sigma) N d ( μ , Σ ) d d d μ \mu μ Σ \Sigma Σ G G G
Strictly increasing transformations of individual coordinates preserve all comparisons. The Gaussian rank model therefore also covers observations obtained by applying such transformations to Gaussian coordinates, even when the transformed marginals are not Gaussian. § 3 and § 4 analyze independent coordinates through N d ( 0 , I d ) \mathcal{N}_d(0,I_d) N d ( 0 , I d ) § 6 extends the analysis to Gaussian dependence, including singular covariances. Independent continuous coordinates are therefore included in this comparison model. In the independent model, independence is given to the rule; in the Gaussian model, the correlations may be unknown.
Fixed-Cutoff Rules under Independence
We begin with a fixed-cutoff rule for independent coordinates with continuous marginal distributions. It rejects the first s s s
Throughout this section d ≥ 2 d \ge2 d ≥ 2 m = n − s m=n-s m = n − s s n s_n s n m n m_n m n n n n
Failure Decomposition
As explained in § 2 , an increasing transformation of each coordinate allows us to analyze every continuous product distribution using F = N d ( 0 , I d ) F=\mathcal{N}_d(0,I_d) F = N d ( 0 , I d ) § 12 with Σ = I d \Sigma=I_d Σ = I d § 4 , Z 1 , … , Z n Z_1,\ldots,Z_n Z 1 , … , Z n q q q § 2 is therefore
q ( z ) = ∏ k = 1 d ( 1 − Φ ( z ( k ) ) ) . q(z)=\prod_{k=1}^{d}\left(1-\Phi\left(z^{(k)}\right)\right). q ( z ) = k = 1 ∏ d ( 1 − Φ ( z ( k ) ) ) . For s ∈ { 1 , … , n − 1 } s \in\{1,\ldots,n-1\} s ∈ { 1 , … , n − 1 }
τ = inf { s < t ≤ n : Z t ∈ Max ( Z 1 , … , Z t ) } , inf ∅ = ∞ . \tau= \inf\{s < t \le n : Z_t \in\operatorname{Max}(Z_1,\ldots,Z_t)\}, \qquad\inf\varnothing= \infty. τ = inf { s < t ≤ n : Z t ∈ Max ( Z 1 , … , Z t )} , inf ∅ = ∞. Write p n ( s ) p_n(s) p n ( s ) n n n
Let U s U_s U s A s A_s A s F F F
U s = { z ∈ R d : z ⊀ Z t for all t ≤ s } , A s = F ( U s ) . U_s = \{z \in\mathbb{R}^d : z \not\prec Z_t \text{ for all } t \le s\}, \qquad A_s = F(U_s). U s = { z ∈ R d : z ≺ Z t for all t ≤ s } , A s = F ( U s ) . More generally, U t U_t U t A t A_t A t t t t s s s U s U_s U s s s s U s U_s U s Figure 3 shows the same region after applying Φ \Phi Φ
Figure 3. The initial frontier (dark gray) bounds the remaining region U s U_s U s z z z z z z
The rule fails if it does not select any observation, or if the selected point is dominated by a later observation. Write Z 1 : s = ( Z 1 , … , Z s ) Z_{1:s} = (Z_1,\ldots,Z_s) Z 1 : s = ( Z 1 , … , Z s ) ( 1 − A s ) m (1-A_s)^m ( 1 − A s ) m s + j s+j s + j ( 1 − A s ) j − 1 A s (1-A_s)^{j-1}A_s ( 1 − A s ) j − 1 A s F F F U s U_s U s m − j m-j m − j U s U_s U s Z 1 : s Z_{1:s} Z 1 : s A s − A s + m − j A_s-A_{s+m-j} A s − A s + m − j E [ A s − A s + m − j ∣ Z 1 : s ] / A s \mathbb{E}[A_s-A_{s+m-j}\mid Z_{1:s}]/A_s E [ A s − A s + m − j ∣ Z 1 : s ] / A s
1 − p s + m ( s ) = E [ ( 1 − A s ) m ] + E [ ∑ j = 1 m ( 1 − A s ) j − 1 ( A s − A s + m − j ) ] . (2) 1-p_{s+m}(s)=\mathbb{E}[(1-A_s)^m]+\mathbb{E}\left[\sum_{j=1}^{m}(1-A_s)^{j-1}(A_s-A_{s+m-j})\right]. \tag*{(2)} 1 − p s + m ( s ) = E [( 1 − A s ) m ] + E [ j = 1 ∑ m ( 1 − A s ) j − 1 ( A s − A s + m − j ) ] . (2) Vanishing Failure Probability
The two terms in (2) admit the following approximation.
Theorem 3.1. As s → ∞ s \to\infty s → ∞ m ≥ 1 m \ge1 m ≥ 1
1 − p s + m ( s ) = e − m E [ A s ] + 1 − E [ A s + m ] E [ A s ] + o d ( 1 ) . (3) 1-p_{s+m}(s)=e^{-m\mathbb{E}[A_s]}+1-\frac{\mathbb{E}[A_{s+m}]}{\mathbb{E}[A_s]}+o_d(1). \tag*{(3)} 1 − p s + m ( s ) = e − m E [ A s ] + 1 − E [ A s ] E [ A s + m ] + o d ( 1 ) . (3) The error tends to zero independently of m m m
Proof. Lemma B.7 gives E [ ( 1 − A s ) m ] = e − m E [ A s ] + o d ( 1 ) \mathbb{E}[(1-A_s)^m]=e^{-m\mathbb{E}[A_s]}+o_d(1) E [( 1 − A s ) m ] = e − m E [ A s ] + o d ( 1 ) (2) , that lemma allows us to replace A s + m − j A_{s+m-j} A s + m − j A s + m A_{s+m} A s + m
E [ ∑ j = 1 m ( 1 − A s ) j − 1 ( A s − A s + m − j ) ] = E [ ( 1 − A s + m A s ) ( 1 − ( 1 − A s ) m ) ] + O d ( ( log s ) 1 − d ) = 1 − E [ A s + m A s ] + O d ( ( log s ) 1 − d ) = 1 − E [ A s + m ] E [ A s ] + o d ( 1 ) . (4) \begin{aligned}
\mathbb{E}\left[\sum_{j=1}^{m}(1-A_s)^{j-1}(A_s-A_{s+m-j})\right]
=\mathbb{E}\left[\left(1-\frac{A_{s+m}}{A_s}\right)\left(1-(1-A_s)^m\right)\right]+O_d((\log s)^{1-d}) \\
&=1-\mathbb{E}\left[\frac{A_{s+m}}{A_s}\right]+O_d((\log s)^{1-d}) \\
&=1-\frac{\mathbb{E}[A_{s+m}]}{\mathbb{E}[A_s]}+o_d(1). \tag*{(4)}
\end{aligned} E [ j = 1 ∑ m ( 1 − A s ) j − 1 ( A s − A s + m − j ) ] = E [ ( 1 − A s A s + m ) ( 1 − ( 1 − A s ) m ) ] + O d (( log s ) 1 − d ) = 1 − E [ A s A s + m ] + O d (( log s ) 1 − d ) = 1 − E [ A s ] E [ A s + m ] + o d ( 1 ) . (4) The last two equalities use (64) and the mean-ratio bound in that lemma.
For example, if s n / n → α ∈ ( 0 , 1 ) s_n/n \to\alpha\in(0,1) s n / n → α ∈ ( 0 , 1 )
m n E [ A s n ] → ∞ , E [ A n ] E [ A s n ] ∼ s n n ( log n log s n ) d − 1 → α . m_n\mathbb{E}[A_{s_n}]\to\infty,\qquad
\frac{\mathbb{E}[A_n]}{\mathbb{E}[A_{s_n}]}\sim\frac{s_n}{n}\left(\frac{\log n}{\log s_n}\right)^{d-1}\to\alpha. m n E [ A s n ] → ∞ , E [ A s n ] E [ A n ] ∼ n s n ( log s n log n ) d − 1 → α . Hence p n ( s n ) → α p_n(s_n)\to\alpha p n ( s n ) → α (3) . To make failure vanish, the fraction left after the cutoff must instead tend to zero, while leaving enough observations to select. Write
a s = ( log s ) d − 1 ( d − 1 ) ! s ∼ E [ A s ] . a_s=\frac{(\log s)^{d-1}}{(d-1)!s}\sim\mathbb{E}[A_s]. a s = ( d − 1 )! s ( log s ) d − 1 ∼ E [ A s ] . Theorem 3.2. For any sequence s n ∈ { 1 , … , n − 1 } s_n\in\{1,\ldots,n-1\} s n ∈ { 1 , … , n − 1 } m n = n − s n m_n=n-s_n m n = n − s n
1 − p n ( s n ) → 0 ⟺ m n s n → 0 and m n a s n → ∞ . 1-p_n(s_n)\to0\quad\Longleftrightarrow\quad\frac{m_n}{s_n}\to0\ \text{ and }\ m_na_{s_n}\to\infty. 1 − p n ( s n ) → 0 ⟺ s n m n → 0 and m n a s n → ∞. Proof. Under the two conditions, s n ∼ n → ∞ s_n\sim n\to\infty s n ∼ n → ∞ E [ A n ] / E [ A s n ] → 1 \mathbb{E}[A_n]/\mathbb{E}[A_{s_n}]\to1 E [ A n ] / E [ A s n ] → 1 m n E [ A s n ] → ∞ m_n\mathbb{E}[A_{s_n}]\to\infty m n E [ A s n ] → ∞ Theorem 3.1 gives 1 − p n ( s n ) → 0 1-p_n(s_n)\to0 1 − p n ( s n ) → 0
Conversely, suppose 1 − p n ( s n ) → 0 1-p_n(s_n)\to0 1 − p n ( s n ) → 0 s n → ∞ s_n\to\infty s n → ∞ q ( Z ) > 0 q(Z)>0 q ( Z ) > 0
For any fixed c > 0 c>0 c > 0 m ≥ c s m\ge cs m ≥ cs A s + m ≤ A s + ⌈ c s ⌉ A_{s+m}\le A_{s+\lceil cs\rceil} A s + m ≤ A s + ⌈ cs ⌉ Theorem 3.1 gives
1 − p s + m ( s ) ≥ 1 − E [ A s + ⌈ c s ⌉ ] E [ A s ] − o d ( 1 ) = c 1 + c + o ( 1 ) . 1-p_{s+m}(s)\ge1-\frac{\mathbb{E}[A_{s+\lceil cs\rceil}]}{\mathbb{E}[A_s]}-o_d(1)=\frac{c}{1+c}+o(1). 1 − p s + m ( s ) ≥ 1 − E [ A s ] E [ A s + ⌈ cs ⌉ ] − o d ( 1 ) = 1 + c c + o ( 1 ) . The last equality follows from Lemma B.6. Thus 1 − p n ( s n ) → 0 1-p_n(s_n)\to0 1 − p n ( s n ) → 0 m n / s n → 0 m_n/s_n\to0 m n / s n → 0 E [ A n ] / E [ A s n ] → 1 \mathbb{E}[A_n]/\mathbb{E}[A_{s_n}]\to1 E [ A n ] / E [ A s n ] → 1 Theorem 3.1 also requires m n E [ A s n ] → ∞ m_n\mathbb{E}[A_{s_n}]\to\infty m n E [ A s n ] → ∞ E [ A s n ] ∼ a s n \mathbb{E}[A_{s_n}]\sim a_{s_n} E [ A s n ] ∼ a s n
For d = 2 d=2 d = 2 m n = ⌈ n log log n / log n ⌉ m_n=\lceil n\log\log n/\log n\rceil m n = ⌈ n log log n / log n ⌉
Optimal Cutoff
The two causes of failure suggest minimizing e − m a s + m / s e^{-m a_s}+m/s e − m a s + m / s x = m a s x=m a_s x = m a s e − x + x / ( s a s ) e^{-x}+x/(s a_s) e − x + x / ( s a s ) x = log ( s a s ) x=\log(s a_s) x = log ( s a s )
Theorem 3.3. For fixed d ≥ 2 d\ge2 d ≥ 2
min 1 ≤ s < n ( 1 − p n ( s ) ) ∼ ( d − 1 ) ( d − 1 ) ! log log n ( log n ) d − 1 . \min_{1\le s<n}(1-p_n(s))\sim(d-1)(d-1)!\frac{\log\log n}{(\log n)^{d-1}}. 1 ≤ s < n min ( 1 − p n ( s )) ∼ ( d − 1 ) ( d − 1 )! ( log n ) d − 1 log log n . Every minimizing cutoff has m n ∼ ( d − 1 ) ( d − 1 ) ! n log log n / ( log n ) d − 1 m_n\sim(d-1)(d-1)!n\log\log n/(\log n)^{d-1} m n ∼ ( d − 1 ) ( d − 1 )! n log log n / ( log n ) d − 1
For all sufficiently large n n n
m n = ⌈ ( d − 1 ) ( d − 1 ) ! n log log n ( log n ) d − 1 ⌉ , s n = n − m n . (5) m_n=\left\lceil(d-1)(d-1)!\frac{n\log\log n}{(\log n)^{d-1}}\right\rceil,\qquad s_n=n-m_n. \tag*{(5)} m n = ⌈ ( d − 1 ) ( d − 1 )! ( log n ) d − 1 n log log n ⌉ , s n = n − m n . (5) Proof. We first sharpen the probability of later domination. Suppose m / s → 0 m/s\to0 m / s → 0 m a s → ∞ m a_s\to\infty m a s → ∞ (4) give
P { τ ≤ n , Z τ ∉ Max ( Z 1 , … , Z n ) } = E [ 1 A s ∫ U s ( 1 − ( 1 − q ( z ) ) m ) d F ( z ) ] + O d ( ( log s ) 1 − d ) ∼ m / s . (6) \begin{aligned}
\mathbb{P}\{\tau\le n,\ Z_\tau\notin\operatorname{Max}(Z_1,\ldots,Z_n)\}
=\mathbb{E}\left[\frac{1}{A_s}\int_{\mathcal{U}_s}\left(1-(1-q(z))^m\right)\,dF(z)\right]+O_d((\log s)^{1-d}) \\
&\sim m/s. \tag*{(6)}
\end{aligned} P { τ ≤ n , Z τ ∈ / Max ( Z 1 , … , Z n )} = E [ A s 1 ∫ U s ( 1 − ( 1 − q ( z ) ) m ) d F ( z ) ] + O d (( log s ) 1 − d ) ∼ m / s . (6) For the upper bound, use 1 − ( 1 − q ) m ≤ m q 1-(1-q)^m\le mq 1 − ( 1 − q ) m ≤ m q { A s ≥ ( 1 − ε ) E [ A s ] } \{A_s\ge(1-\varepsilon)\mathbb{E}[A_s]\} { A s ≥ ( 1 − ε ) E [ A s ]} 1 − ( 1 − q ) m ≥ m q − m 2 q 2 / 2 1-(1-q)^m\ge mq-m^2q^2/2 1 − ( 1 − q ) m ≥ m q − m 2 q 2 /2 { q ≤ T / s } \{q\le T/s\} { q ≤ T / s }
1 + o ( 1 ) 1 − ε m s + O d , ε ( ( log s ) 1 − d ) , m s ( ∫ 0 T t e − t d t + o ( 1 ) ) − m 2 T 2 2 s 2 . \frac{1+o(1)}{1-\varepsilon}\frac{m}{s}+O_{d,\varepsilon}((\log s)^{1-d}),\qquad
\frac{m}{s}\left(\int_0^Tte^{-t}\,dt+o(1)\right)-\frac{m^2T^2}{2s^2}. 1 − ε 1 + o ( 1 ) s m + O d , ε (( log s ) 1 − d ) , s m ( ∫ 0 T t e − t d t + o ( 1 ) ) − 2 s 2 m 2 T 2 . For fixed T T T ε \varepsilon ε o ( m / s ) o(m/s) o ( m / s ) m a s → ∞ m a_s\to\infty m a s → ∞ m / s → 0 m/s\to0 m / s → 0 T → ∞ T\to\infty T → ∞ ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0
For the choice (5) , m a s = ( d − 1 ) log log s + o ( 1 ) m a_s=(d-1)\log\log s+o(1) m a s = ( d − 1 ) log log s + o ( 1 ) (54) bounds P { τ = ∞ } \mathbb{P}\{\tau=\infty\} P { τ = ∞ } O d ( ( log s ) 1 − d ) = o ( m / s ) O_d((\log s)^{1-d})=o(m/s) O d (( log s ) 1 − d ) = o ( m / s ) (6) proves the upper bound.
Conversely, the upper bound and Theorem 3.2 imply s ∼ n s\sim n s ∼ n m a s → ∞ m a_s\to\infty m a s → ∞
( 1 − E [ A s ] ) m ≤ P { τ = ∞ } ≤ 1 − p n ( s ) = O d ( log log n ( log n ) d − 1 ) . (7) (1-\mathbb{E}[A_s])^m\le\mathbb{P}\{\tau=\infty\}\le1-p_n(s)=O_d\left(\frac{\log\log n}{(\log n)^{d-1}}\right). \tag*{(7)} ( 1 − E [ A s ] ) m ≤ P { τ = ∞ } ≤ 1 − p n ( s ) = O d ( ( log n ) d − 1 log log n ) . (7) Taking logarithms shows that m E [ A s ] ≥ ( d − 1 − o ( 1 ) ) log log n m\mathbb{E}[A_s]\ge(d-1-o(1))\log\log n m E [ A s ] ≥ ( d − 1 − o ( 1 )) log log n
1 − p n ( s ) ≥ ( 1 − o ( 1 ) ) m / s ≥ ( ( d − 1 ) ( d − 1 ) ! − o ( 1 ) ) log log n ( log n ) d − 1 . 1-p_n(s)\ge(1-o(1))m/s\ge\left((d-1)(d-1)!-o(1)\right)\frac{\log\log n}{(\log n)^{d-1}}. 1 − p n ( s ) ≥ ( 1 − o ( 1 )) m / s ≥ ( ( d − 1 ) ( d − 1 )! − o ( 1 ) ) ( log n ) d − 1 log log n . The matching upper bound fixes both the leading failure probability and the asymptotic location of every minimizing cutoff.
For d = 2 d=2 d = 2 log log n / log n \log\log n/\log n log log n / log n § 4 improves this by a factor asymptotic to 1 2 ( log log n ) 2 \frac{1}{2}(\log\log n)^2 2 1 ( log log n ) 2
Optimal Stopping under Independence
Fixed-cutoff rules can select a maximal observation with probability tending to one, but their failure probability can be reduced further. We now let the threshold depend on how many observations remain. This gives the leading constant in the smallest possible failure probability. A rule with known marginals and a rule using only coordinate ranks both achieve it.
As in § 3 , we work with independent standard Gaussian coordinates with F = N d ( 0 , I d ) F = \mathcal{N}_d(0, I_d) F = N d ( 0 , I d ) p ( r ) = p F ( r ) p(\mathbf{r}) = p_F(\mathbf{r}) p ( r ) = p F ( r ) m = n − s m = n-s m = n − s G G G § 2 .
Theorem 4.1. For every fixed d ≥ 2 d \ge2 d ≥ 2
1 − p n , rank ⋆ ( G ) ∼ 1 − p n ⋆ ( F ) ∼ 2 ( d − 2 ) ! ( log n ) d − 1 log log n . (8) 1-p_{n,\operatorname{rank}}^{\star}(G) \sim1-p_n^{\star}(F) \sim\frac{2(d-2)!}{(\log n)^{d-1}\log\log n}. \tag*{(8)} 1 − p n , rank ⋆ ( G ) ∼ 1 − p n ⋆ ( F ) ∼ ( log n ) d − 1 log log n 2 ( d − 2 )! . (8) For every product distribution with continuous marginals, the two time-dependent rules below achieve this asymptotic. One uses the known marginals; the other uses only coordinate ranks.
By Theorem 3.3 , the ratio of the best fixed-cutoff failure probability to either optimal failure probability is asymptotic to 1 2 ( d − 1 ) 2 ( log log n ) 2 \frac{1}{2}(d-1)^2(\log\log n)^2 2 1 ( d − 1 ) 2 ( log log n ) 2
The lower bound rests on the fact that points with very small q q q q ( Z s ) q(Z_s) q ( Z s ) m m m
Lower Bound
Selecting a currently maximal observation at time s s s 1 − ( 1 − q ( Z s ) ) n − s 1-(1-q(Z_s))^{n-s} 1 − ( 1 − q ( Z s ) ) n − s (1) . When this probability is small, it is close to ( n − s ) q ( Z s ) (n-s)q(Z_s) ( n − s ) q ( Z s ) q q q
H ( v ) : = P { q ( Z ) ≤ v } = v ∑ j = 0 d − 1 ( log ( 1 / v ) ) j j ! , 0 < v ≤ 1 , (9) H(v) := \mathbb{P}\{q(Z) \le v\} = v \sum_{j=0}^{d-1}\frac{(\log(1/v))^j}{j!}, \qquad0 < v \le1, \tag*{(9)} H ( v ) := P { q ( Z ) ≤ v } = v j = 0 ∑ d − 1 j ! ( log ( 1/ v ) ) j , 0 < v ≤ 1 , (9) limits how often such points arrive. The formula is the tail probability of the sum − log q ( Z ) -\log q(Z) − log q ( Z ) d d d q q q
Theorem 4.2. For every fixed d ≥ 2 d \ge2 d ≥ 2
1 − p ( r ) ≥ 2 ( d − 2 ) ! − o d ( 1 ) ( log n ) d − 1 log log n . 1-p(\mathbf{r}) \ge\frac{2(d-2)!-o_d(1)}{(\log n)^{d-1}\log\log n}. 1 − p ( r ) ≥ ( log n ) d − 1 log log n 2 ( d − 2 )! − o d ( 1 ) . Proof. It suffices to consider rules with failure probability at most 3 ( d − 2 ) ! / [ ( log n ) d − 1 log log n ] 3(d-2)!/[(\log n)^{d-1}\log\log n] 3 ( d − 2 )! / [( log n ) d − 1 log log n ] § 2 , assume the rule selects only currently maximal observations. Then
1 − p ( r ) = P { τ = ∞ } + ∑ s = 1 n E [ 1 { τ = s } ( 1 − ( 1 − q ( Z s ) ) n − s ) ] . (10) 1-p(\mathbf{r}) = \mathbb{P}\{\tau=\infty\} + \sum_{s=1}^{n}\mathbb{E}\left[1\{\tau=s\}\left(1-(1-q(Z_s))^{n-s}\right)\right]. \tag*{(10)} 1 − p ( r ) = P { τ = ∞ } + s = 1 ∑ n E [ 1 { τ = s } ( 1 − ( 1 − q ( Z s ) ) n − s ) ] . (10) Choices used in the bound. Put ℓ = ⌊ n / [ ( log n ) d − 1 log log n ] ⌋ \ell=\left\lfloor n/[(\log n)^{d-1}\log\log n]\right\rfloor ℓ = ⌊ n / [( log n ) d − 1 log log n ] ⌋ s ≤ n − ℓ s\le n-\ell s ≤ n − ℓ
B s = { z ∈ R d : 1 n ( log n ) 3 ( d − 1 ) ≤ q ( z ) ≤ 1 ( n − s ) log log n } . (11) B_s=\left\{z\in\mathbb{R}^d:\frac{1}{n(\log n)^{3(d-1)}}\le q(z)\le\frac{1}{(n-s)\log\log n}\right\}. \tag*{(11)} B s = { z ∈ R d : n ( log n ) 3 ( d − 1 ) 1 ≤ q ( z ) ≤ ( n − s ) log log n 1 } . (11) The lower boundary excludes points that almost never appear; the upper boundary makes the probability of later domination asymptotic to ( n − s ) q ( z ) (n-s)q(z) ( n − s ) q ( z ) τ ′ = τ \tau'=\tau τ ′ = τ τ ≤ n − ℓ \tau\le n-\ell τ ≤ n − ℓ Z τ ∈ B τ Z_\tau\in B_\tau Z τ ∈ B τ τ ′ = ∞ \tau'=\infty τ ′ = ∞
P { τ ′ = ∞ } ≤ ( 1 − p ( r ) ) + ∑ s = n − ℓ + 1 n E [ ( 1 − q ( Z s ) ) s − 1 ] + n H ( 1 n ( log n ) 3 ( d − 1 ) ) + 1 − p ( r ) 1 − e − 1 / log log n = O ( ( 1 − p ( r ) ) log log n ) + o ( 1 ) = o ( 1 ) . (12) \begin{aligned}
\mathbb{P}\{\tau'=\infty\}&\le(1-p(\mathbf{r}))+\sum_{s=n-\ell+1}^{n}\mathbb{E}\left[(1-q(Z_s))^{s-1}\right]+nH\left(\frac{1}{n(\log n)^{3(d-1)}}\right)+\frac{1-p(\mathbf{r})}{1-e^{-1/\log\log n}}\\
&=O((1-p(\mathbf{r}))\log\log n)+o(1)=o(1). \tag*{(12)}
\end{aligned} P { τ ′ = ∞ } ≤ ( 1 − p ( r )) + s = n − ℓ + 1 ∑ n E [ ( 1 − q ( Z s ) ) s − 1 ] + n H ( n ( log n ) 3 ( d − 1 ) 1 ) + 1 − e − 1/ l o g l o g n 1 − p ( r ) = O (( 1 − p ( r )) log log n ) + o ( 1 ) = o ( 1 ) . (12) The four terms cover τ = ∞ \tau=\infty τ = ∞ ℓ \ell ℓ B s B_s B s O ( ℓ ( log n ) d − 1 / n ) = o ( 1 ) O(\ell(\log n)^{d-1}/n)=o(1) O ( ℓ ( log n ) d − 1 / n ) = o ( 1 ) 1 − e − 1 / log log n 1-e^{-1/\log\log n} 1 − e − 1/ l o g l o g n 1 − p ( r ) 1-p(\mathbf{r}) 1 − p ( r )
Failure at a stop. Let Z Z Z B s B_s B s x ≥ 0 x\ge0 x ≥ 0 s ≤ n − ℓ s\le n-\ell s ≤ n − ℓ
P { Z ∈ B s , q ( Z ) ≤ x } ≤ ( 1 + o ( 1 ) ) ( log n ) d − 1 ( d − 1 ) ! x . (13) \mathbb{P}\{Z\in B_s,q(Z)\le x\}\le(1+o(1))\frac{(\log n)^{d-1}}{(d-1)!}x. \tag*{(13)} P { Z ∈ B s , q ( Z ) ≤ x } ≤ ( 1 + o ( 1 )) ( d − 1 )! ( log n ) d − 1 x . (13) Indeed, log ( 1 / q ( z ) ) = log n + O ( log log n ) \log(1/q(z))=\log n+O(\log\log n) log ( 1/ q ( z )) = log n + O ( log log n ) B s B_s B s H H H H s − 1 \mathcal{H}_{s-1} H s − 1 § 2 , independence gives
P { τ ′ = s , q ( Z s ) ≤ x ∣ H s − 1 } ≤ P { Z ∈ B s , q ( Z ) ≤ x } . \mathbb{P}\{\tau'=s,q(Z_s)\le x\mid\mathcal{H}_{s-1}\}\le\mathbb{P}\{Z\in B_s,q(Z)\le x\}. P { τ ′ = s , q ( Z s ) ≤ x ∣ H s − 1 } ≤ P { Z ∈ B s , q ( Z ) ≤ x } . Also, since { τ ′ ≥ s } \{\tau'\ge s\} { τ ′ ≥ s } Z s Z_s Z s B s ⊆ B n − ℓ B_s\subseteq B_{n-\ell} B s ⊆ B n − ℓ
P { τ ′ = s } P { τ ′ ≥ s } ≤ P { Z ∈ B s } ≤ P { Z ∈ B n − ℓ } = O ( ( log n ) 2 ( d − 1 ) n ) = o ( 1 ) . \frac{\mathbb{P}\{\tau'=s\}}{\mathbb{P}\{\tau'\ge s\}}\le\mathbb{P}\{Z\in B_s\}\le\mathbb{P}\{Z\in B_{n-\ell}\}=O\left(\frac{(\log n)^{2(d-1)}}{n}\right)=o(1). P { τ ′ ≥ s } P { τ ′ = s } ≤ P { Z ∈ B s } ≤ P { Z ∈ B n − ℓ } = O ( n ( log n ) 2 ( d − 1 ) ) = o ( 1 ) . Integrating the preceding conditional bound and applying Cauchy–Schwarz gives
1 − p ( r ) ≥ ( 1 − o ( 1 ) ) ∑ s = 1 n − ℓ ( n − s ) E [ q ( Z s ) 1 { τ ′ = s } ] ≥ ( 1 − o ( 1 ) ) ( d − 1 ) ! 2 ( log n ) d − 1 ∑ s = 1 n − ℓ ( n − s ) P { τ ′ = s } 2 P { τ ′ ≥ s } ≥ ( 1 − o ( 1 ) ) ( d − 1 ) ! 2 ( log n ) d − 1 4 ( 1 − P { τ ′ = ∞ } ) 2 ∑ j = ℓ n − 1 j − 1 = ( 2 − o ( 1 ) ) ( d − 2 ) ! ( log n ) d − 1 log log n . (14) \begin{aligned}
1-p(\mathbf{r})&\ge(1-o(1))\sum_{s=1}^{n-\ell}(n-s)\mathbb{E}\left[q(Z_s)\mathbf{1}\{\tau'=s\}\right]\\
&\ge\frac{(1-o(1))(d-1)!}{2(\log n)^{d-1}}\sum_{s=1}^{n-\ell}\frac{(n-s)\mathbb{P}\{\tau'=s\}^{2}}{\mathbb{P}\{\tau'\ge s\}}\\
&\ge\frac{(1-o(1))(d-1)!}{2(\log n)^{d-1}}\frac{4\left(1-\sqrt{\mathbb{P}\{\tau'=\infty\}}\right)^2}{\sum_{j=\ell}^{n-1}j^{-1}}\\
&=\frac{(2-o(1))(d-2)!}{(\log n)^{d-1}\log\log n}. \tag*{(14)}
\end{aligned} 1 − p ( r ) ≥ ( 1 − o ( 1 )) s = 1 ∑ n − ℓ ( n − s ) E [ q ( Z s ) 1 { τ ′ = s } ] ≥ 2 ( log n ) d − 1 ( 1 − o ( 1 )) ( d − 1 )! s = 1 ∑ n − ℓ P { τ ′ ≥ s } ( n − s ) P { τ ′ = s } 2 ≥ 2 ( log n ) d − 1 ( 1 − o ( 1 )) ( d − 1 )! ∑ j = ℓ n − 1 j − 1 4 ( 1 − P { τ ′ = ∞ } ) 2 = ( log n ) d − 1 log log n ( 2 − o ( 1 )) ( d − 2 )! . (14) The first line uses (10) and m q − m 2 q 2 / 2 ≤ 1 − ( 1 − q ) m ≤ m q mq-m^2q^2/2\le1-(1-q)^m\le mq m q − m 2 q 2 /2 ≤ 1 − ( 1 − q ) m ≤ m q m q ( Z s ) ≤ 1 / log log n mq(Z_s)\le1/\log\log n m q ( Z s ) ≤ 1/ log log n B s B_s B s P { τ ′ = s ∣ H s − 1 } − ( 1 + o ( 1 ) ) ( log n ) d − 1 x / ( d − 1 ) ! \mathbb{P}\{\tau'=s\mid\mathcal{H}_{s-1}\}-(1+o(1))(\log n)^{d-1}x/(d-1)! P { τ ′ = s ∣ H s − 1 } − ( 1 + o ( 1 )) ( log n ) d − 1 x / ( d − 1 )! x x x { τ ′ ≥ s } \{\tau'\ge s\} { τ ′ ≥ s } 0 / 0 = 0 0/0=0 0/0 = 0 s s s o ( 1 ) o(1) o ( 1 ) ∑ j = ℓ n − 1 j − 1 ∼ ( d − 1 ) log log n \sum_{j=\ell}^{n-1}j^{-1}\sim(d-1)\log\log n ∑ j = ℓ n − 1 j − 1 ∼ ( d − 1 ) log log n § 2 extends the result to every continuous product distribution.
Time-Dependent Threshold Rule
In one-dimensional full-information best choice, the optimal value threshold falls as time runs out [8 ] . We use the same idea by allowing a larger probability q ( Z s ) q(Z_s) q ( Z s )
For n ≥ 3 n \ge3 n ≥ 3 0 ≤ m < n 0 \le m < n 0 ≤ m < n
h = n exp ( log log n ) ( log n ) d − 1 , u m = 2 ( d − 1 ) ! ( m + 1 ) ( log n ) d − 1 log ( 1 + m + 1 h ) (15) h = \frac{n\exp(\sqrt{\log\log n})}{(\log n)^{d-1}}, \qquad u_m = \frac{2(d-1)!}{(m+1)(\log n)^{d-1}\log\left(1+\frac{m+1}{h}\right)} \tag*{(15)} h = ( log n ) d − 1 n exp ( log log n ) , u m = ( m + 1 ) ( log n ) d − 1 log ( 1 + h m + 1 ) 2 ( d − 1 )! (15) The full-information rule stops at
τ = inf { s ∈ [ n ] : Z s ∈ Max ( Z 1 , … , Z s ) , q ( Z s ) ≤ u n − s } , inf ∅ = ∞ , \tau= \inf\{s \in[n] : Z_s \in\operatorname{Max}(Z_1,\ldots,Z_s),\ q(Z_s) \le u_{n-s}\}, \qquad\inf\varnothing= \infty, τ = inf { s ∈ [ n ] : Z s ∈ Max ( Z 1 , … , Z s ) , q ( Z s ) ≤ u n − s } , inf ∅ = ∞ , and selects Z τ Z_\tau Z τ τ ≤ n \tau\le n τ ≤ n
For 0 < u < 1 0 < u < 1 0 < u < 1 q ( z ) ≤ u q(z) \le u q ( z ) ≤ u z ≥ Φ − 1 ( 1 − u ) z \ge\Phi^{-1}(1-u) z ≥ Φ − 1 ( 1 − u ) ( 1 − x ) ( 1 − y ) = u n − s (1-x)(1-y)=u_{n-s} ( 1 − x ) ( 1 − y ) = u n − s 0 < u n − s < 1 0 < u_{n-s} < 1 0 < u n − s < 1 u n − s ≥ 1 u_{n-s} \ge1 u n − s ≥ 1 Figure 4 ). The increase near the end provides enough chances to select. We prove that this rule matches the leading constant in the lower bound.
Figure 4. Time-dependent thresholds for n = 1000 n = 1000 n = 1000 x = Φ ( z ( 1 ) ) x = \Phi(z^{(1)}) x = Φ ( z ( 1 ) ) y = Φ ( z ( 2 ) ) y = \Phi(z^{(2)}) y = Φ ( z ( 2 ) ) u n − s u_{n-s} u n − s ( 1 − x ) ( 1 − y ) = u n − s (1-x)(1-y)=u_{n-s} ( 1 − x ) ( 1 − y ) = u n − s ( 0.8 , 0.7 ) (0.8,0.7) ( 0.8 , 0.7 )
When the marginals are unknown, we estimate their upper-tail probabilities from the first ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊ n /2 ⌋ N N N 0 ≤ j < N 0 \le j < N 0 ≤ j < N
P { Bin ( N , p ‾ N ( j ) ) ≤ j } = n − 2 , p ‾ N ( N ) = 1. \mathbb{P}\{\operatorname{Bin}(N,\overline{p}_N(j)) \le j\} = n^{-2}, \qquad\overline{p}_N(N)=1. P { Bin ( N , p N ( j )) ≤ j } = n − 2 , p N ( N ) = 1. This table depends only on n n n j j j z z z
q ^ ( z ) = ∏ k = 1 d p ‾ ⌊ n / 2 ⌋ ( # { i ≤ ⌊ n / 2 ⌋ : Z i ( k ) > z ( k ) } ) . (16) \widehat{q}(z)=\prod_{k=1}^{d}\overline{p}_{\lfloor n/2\rfloor}\left(\#\left\{i\le\lfloor n/2\rfloor:Z_i^{(k)}>z^{(k)}\right\}\right). \tag*{(16)} q ( z ) = k = 1 ∏ d p ⌊ n /2 ⌋ ( # { i ≤ ⌊ n /2 ⌋ : Z i ( k ) > z ( k ) } ) . (16) The rank-based rule uses the stopping time
τ = inf { s > ⌊ n / 2 ⌋ : s ≤ n , Z s ∈ Max ( Z 1 , … , Z s ) , q ^ ( Z s ) ≤ u n − s } , inf ∅ = ∞ . (17) \tau=\inf\left\{s>\lfloor n/2\rfloor:s\le n,\ Z_s\in\operatorname{Max}(Z_1,\ldots,Z_s),\ \widehat{q}(Z_s)\le u_{n-s}\right\},\qquad\inf\varnothing=\infty. \tag*{(17)} τ = inf { s > ⌊ n /2 ⌋ : s ≤ n , Z s ∈ Max ( Z 1 , … , Z s ) , q ( Z s ) ≤ u n − s } , inf ∅ = ∞. (17) The initial observations remain part of the maximality comparison. The counts use only coordinate ranks, and the estimates stay fixed after the initial sample.
With probability 1 − O d ( n − 1 ) 1-O_d(n^{-1}) 1 − O d ( n − 1 ) q ( z ) ≤ q ^ ( z ) q(z)\le\widehat{q}(z) q ( z ) ≤ q ( z ) z z z q ( Z s ) ≤ u n − s q(Z_s)\le u_{n-s} q ( Z s ) ≤ u n − s q q q
Upper Bound
Theorem 4.3. For every fixed d ≥ 2 d\ge2 d ≥ 2 § 4.2 satisfies
1 − p F ( r ) ≤ 2 ( d − 2 ) ! + o d ( 1 ) ( log n ) d − 1 log log n 1-p_F(r)\le\frac{2(d-2)!+o_d(1)}{(\log n)^{d-1}\log\log n} 1 − p F ( r ) ≤ ( log n ) d − 1 log log n 2 ( d − 2 )! + o d ( 1 ) for every product distribution F F F F F F
Proof. We work with F = N d ( 0 , I d ) F=\mathcal{N}_d(0,I_d) F = N d ( 0 , I d )
Selection and continuation. Fix 0 < ε < 1 / 4 0<\varepsilon<1/4 0 < ε < 1/4
ℓ = ⌈ h exp ( − 1 4 log log n ) ⌉ . \ell=\left\lceil h\exp\left(-\frac{1}{4}\sqrt{\log\log n}\right)\right\rceil. ℓ = ⌈ h exp ( − 4 1 log log n ) ⌉ . We analyze decisions with ℓ ≤ m ≤ ⌈ n / 2 ⌉ − 1 \ell\le m\le\lceil n/2\rceil-1 ℓ ≤ m ≤ ⌈ n /2 ⌉ − 1 n − ℓ n-\ell n − ℓ (15) , the smallest threshold has order 1 / [ n ( log n ) d − 1 log log n ] 1/[n(\log n)^{d-1}\log\log n] 1/ [ n ( log n ) d − 1 log log n ] e − log log n / 2 / n e^{-\sqrt{\log\log n}/2}/n e − l o g l o g n /2 / n
P { τ = s ∣ H s − 1 } ≥ ( 1 − ε ) ( log n ) d − 1 ( d − 1 ) ! u m , \mathbb{P}\{\tau=s\mid\mathcal{H}_{s-1}\}\ge(1-\varepsilon)\frac{(\log n)^{d-1}}{(d-1)!}u_m, P { τ = s ∣ H s − 1 } ≥ ( 1 − ε ) ( d − 1 )! ( log n ) d − 1 u m , E [ q ( Z s ) 1 { τ = s } ∣ H s − 1 ] ≤ ( 1 + ε ) ( log n ) d − 1 2 ( d − 1 ) ! u m 2 . (18) \mathbb{E}\left[q(Z_s)1\{\tau=s\}\mid\mathcal{H}_{s-1}\right]\le(1+\varepsilon)\frac{(\log n)^{d-1}}{2(d-1)!}u_m^2. \tag*{(18)} E [ q ( Z s ) 1 { τ = s } ∣ H s − 1 ] ≤ ( 1 + ε ) 2 ( d − 1 )! ( log n ) d − 1 u m 2 . (18) for both rules on { τ ≥ s } \{\tau\ge s\} { τ ≥ s } o ( 1 / [ ( log n ) d − 1 log log n ] ) o(1/[(\log n)^{d-1}\log\log n]) o ( 1/ [( log n ) d − 1 log log n ]) S m S_m S m n − m n-m n − m
S m ≤ exp { − 2 ( 1 − ε ) ∑ j = m + 1 ⌈ n / 2 ⌉ − 1 1 ( j + 1 ) log ( 1 + ( j + 1 ) / h ) } ≤ { ( 1 + o ( 1 ) ) ( log ( 1 + m / h ) log ( n / h ) ) 2 − 2 ε , m ≥ h , c ε e − h / ( 2 m ) [ log ( n / h ) ] 2 − 2 ε , ℓ ≤ m < h . (19) \begin{aligned}
S_m\le\exp\left\{-2(1-\varepsilon)\sum_{j=m+1}^{\lceil n/2\rceil-1}\frac{1}{(j+1)\log(1+(j+1)/h)}\right\} \\
&\le
\begin{cases}
(1+o(1))\left(\dfrac{\log(1+m/h)}{\log(n/h)}\right)^{2-2\varepsilon}, & m\ge h,\\[6pt]
\dfrac{c_\varepsilon e^{-h/(2m)}}{[\log(n/h)]^{2-2\varepsilon}}, & \ell\le m<h.
\end{cases} \tag*{(19)}
\end{aligned} S m ≤ exp ⎩ ⎨ ⎧ − 2 ( 1 − ε ) j = m + 1 ∑ ⌈ n /2 ⌉ − 1 ( j + 1 ) log ( 1 + ( j + 1 ) / h ) 1 ⎭ ⎬ ⎫ ≤ ⎩ ⎨ ⎧ ( 1 + o ( 1 )) ( log ( n / h ) log ( 1 + m / h ) ) 2 − 2 ε , [ log ( n / h ) ] 2 − 2 ε c ε e − h / ( 2 m ) , m ≥ h , ℓ ≤ m < h . (19) The integral comparison for m ≥ h m \ge h m ≥ h 1 / [ x log ( 1 + x / h ) ] ≥ ( d / d x ) log log ( 1 + x / h ) 1/[x\log(1+x/h)] \ge(d/dx)\log\log(1+x/h) 1/ [ x log ( 1 + x / h )] ≥ ( d / d x ) log log ( 1 + x / h ) h h h log ( 1 + x / h ) ≤ x / h \log(1+x/h) \le x/h log ( 1 + x / h ) ≤ x / h h / x 2 h/x^2 h / x 2 o ( 1 ) o(1) o ( 1 ) ℓ → ∞ \ell\to\infty ℓ → ∞ h / ℓ 2 → 0 h/\ell^2 \to0 h / ℓ 2 → 0 h / ℓ ∼ e log log n / 4 h/\ell\sim e^{\sqrt{\log\log n}/4} h / ℓ ∼ e l o g l o g n /4 S ℓ = o ( 1 / [ ( log n ) d − 1 log log n ] ) S_\ell=o(1/[(\log n)^{d-1}\log\log n]) S ℓ = o ( 1/ [( log n ) d − 1 log log n ])
Summing the failure probabilities. The failure decomposition, 1 − ( 1 − q ) m ≤ m q 1-(1-q)^m \le mq 1 − ( 1 − q ) m ≤ m q (18) give
1 − p F ( r ) ≤ S ℓ + ∑ s ≤ ⌊ n / 2 ⌋ n E [ q ( Z s ) 1 { q ( Z s ) ≤ u n − s } ] + ( 1 + ε ) ( log n ) d − 1 2 ( d − 1 ) ! ∑ m = ℓ ⌈ n / 2 ⌉ − 1 S m m u m 2 + o ( 1 ( log n ) d − 1 log log n ) ≤ 2 ( 1 + ε ) ( d − 1 ) ! ( log n ) d − 1 ∑ m = ℓ ⌈ n / 2 ⌉ − 1 S m m [ log ( 1 + m / h ) ] 2 + o ( 1 ( log n ) d − 1 log log n ) ≤ ( 2 ( 1 + ε ) + o ( 1 ) ) ( d − 2 ) ! ( 1 − 2 ε ) ( log n ) d − 1 log log n . (20) \begin{aligned}
1-p_F(\mathbf r) \le S_\ell+\sum_{s\le\lfloor n/2\rfloor} n\mathbb{E}\left[q(Z_s)\mathbf{1}\{q(Z_s)\le u_{n-s}\}\right] \\
&+\frac{(1+\varepsilon)(\log n)^{d-1}}{2(d-1)!}\sum_{m=\ell}^{\lceil n/2\rceil-1}S_m m u_m^2+o\left(\frac{1}{(\log n)^{d-1}\log\log n}\right) \\
&\le\frac{2(1+\varepsilon)(d-1)!}{(\log n)^{d-1}}\sum_{m=\ell}^{\lceil n/2\rceil-1}\frac{S_m}{m[\log(1+m/h)]^2}+o\left(\frac{1}{(\log n)^{d-1}\log\log n}\right) \\
&\le\frac{(2(1+\varepsilon)+o(1))(d-2)!}{(1-2\varepsilon)(\log n)^{d-1}\log\log n}. \tag*{(20)}
\end{aligned} 1 − p F ( r ) ≤ S ℓ + s ≤ ⌊ n /2 ⌋ ∑ n E [ q ( Z s ) 1 { q ( Z s ) ≤ u n − s } ] + 2 ( d − 1 )! ( 1 + ε ) ( log n ) d − 1 m = ℓ ∑ ⌈ n /2 ⌉ − 1 S m m u m 2 + o ( ( log n ) d − 1 log log n 1 ) ≤ ( log n ) d − 1 2 ( 1 + ε ) ( d − 1 )! m = ℓ ∑ ⌈ n /2 ⌉ − 1 m [ log ( 1 + m / h ) ] 2 S m + o ( ( log n ) d − 1 log log n 1 ) ≤ ( 1 − 2 ε ) ( log n ) d − 1 log log n ( 2 ( 1 + ε ) + o ( 1 )) ( d − 2 )! . (20) The first bound uses (10) to separate failure from time n − ℓ n-\ell n − ℓ O d ( 1 / [ ( log n ) d − 1 ( log log n ) 2 ] ) O_d(1/[(\log n)^{d-1}(\log\log n)^2]) O d ( 1/ [( log n ) d − 1 ( log log n ) 2 ]) (47) . This and the bound on S ℓ S_\ell S ℓ u m u_m u m (19) and integral comparison, splitting at m = h m=h m = h m < h m<h m < h log ( n / h ) ∼ ( d − 1 ) log log n \log(n/h)\sim(d-1)\log\log n log ( n / h ) ∼ ( d − 1 ) log log n ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0
Proof of Theorem 4.1 . Theorem 4.2 gives the lower bound on the failure probability of every full-information rule, and hence of every rank-based rule. Theorem 4.3 gives the matching upper bound for a rule of each type. Together they imply (8) , and both time-dependent rules achieve it.
Arbitrary Dependence
Independent coordinates allow the probability of selecting a Pareto-maximal point to approach one. A joint density alone does not imply this result, even when every marginal is uniform. We construct a fixed dependent distribution for which the optimal probability of selecting a maximal observation with full information approaches the one-dimensional optimal probability.
Let v n v_n v n n n n ( 0 , 1 ) (0,1) ( 0 , 1 ) [8 ] ; its limiting value is
v n ⟶ v ∞ = 0.580164 … ; (21) v_n \longrightarrow v_\infty=0.580164\ldots; \tag*{(21)} v n ⟶ v ∞ = 0.580164 … ; (21) see Gnedin, Kozieł, and Sulkowska [GKS23, Section 3] for a modern derivation. We use the full-information value p n ∗ ( F ) p_n^*(F) p n ∗ ( F ) § 2 , allowing private randomization in the stopping rule.
Theorem 5.1. Fix d ≥ 2 d\ge2 d ≥ 2 F F F R d \mathbb{R}^d R d n ≥ 1 n\ge1 n ≥ 1
p n ∗ ( F ) ≥ v n . (22) p_n^*(F)\ge v_n. \tag*{(22)} p n ∗ ( F ) ≥ v n . (22) There exists a fixed distribution F d F_d F d ( 0 , 1 ) d (0,1)^d ( 0 , 1 ) d n ≥ 2 n\ge2 n ≥ 2
v n ≤ p n ∗ ( F d ) ≤ v n + 4 n + 1 . (23) v_n\le p_n^*(F_d)\le v_n+\frac{4}{n+1}. \tag*{(23)} v n ≤ p n ∗ ( F d ) ≤ v n + n + 1 4 . (23) Thus, p n ∗ ( F d ) → v ∞ p_n^*(F_d) \to v_\infty p n ∗ ( F d ) → v ∞
The theorem identifies v ∞ v_\infty v ∞
A Dependent Distribution
We partition ( 0 , 1 ) (0,1) ( 0 , 1 ) 1 1 1
Construction 5.2. For each integer k ≥ 1 k \ge1 k ≥ 1
I k = ( 1 − 1 k , 1 − 1 k + 1 ) , Q k = I k d . I_k = \left(1-\frac{1}{k},1-\frac{1}{k+1}\right), \qquad Q_k = I_k^d. I k = ( 1 − k 1 , 1 − k + 1 1 ) , Q k = I k d . Draw an index J J J P { J = k } = ∣ I k ∣ = 1 / [ k ( k + 1 ) ] \mathbb{P}\{J=k\}=|I_k|=1/[k(k+1)] P { J = k } = ∣ I k ∣ = 1/ [ k ( k + 1 )] J = k J=k J = k d d d I k I_k I k F d F_d F d
Conditional on J = k J=k J = k Q k Q_k Q k F d F_d F d
g d ( z ) = ∑ k = 1 ∞ ∣ I k ∣ 1 − d 1 { z ∈ Q k } . g_d(z)=\sum_{k=1}^{\infty}|I_k|^{1-d}\mathbf{1}\{z\in Q_k\}. g d ( z ) = k = 1 ∑ ∞ ∣ I k ∣ 1 − d 1 { z ∈ Q k } . Integrating over all but any one coordinate gives marginal density ∣ I k ∣ 1 − d ∣ I k ∣ d − 1 = 1 |I_k|^{1-d}|I_k|^{d-1}=1 ∣ I k ∣ 1 − d ∣ I k ∣ d − 1 = 1 I k I_k I k
If ℓ > k \ell>k ℓ > k Q ℓ Q_\ell Q ℓ Q k Q_k Q k Figure 5 illustrates the construction in dimension two. For example, Q 1 = ( 0 , 1 / 2 ) 2 Q_1=(0,1/2)^2 Q 1 = ( 0 , 1/2 ) 2 1 / 2 1/2 1/2 Q 2 = ( 1 / 2 , 2 / 3 ) 2 Q_2=(1/2,2/3)^2 Q 2 = ( 1/2 , 2/3 ) 2 Q 2 Q_2 Q 2 Q 1 Q_1 Q 1
Figure 5. The two-dimensional support, with a magnified view. Every point in a higher square dominates every point in a lower square. The squares continue toward ( 1 , 1 ) (1,1) ( 1 , 1 )
The probabilities satisfy P { J ≥ k } = 1 / k \mathbb{P}\{J\ge k\}=1/k P { J ≥ k } = 1/ k ∣ I k ∣ = 1 / [ k ( k + 1 ) ] |I_k|=1/[k(k+1)] ∣ I k ∣ = 1/ [ k ( k + 1 )]
One-Dimensional Comparison
Let Z 1 , … , Z n Z_1,\ldots,Z_n Z 1 , … , Z n F d F_d F d X i = Z i ( 1 ) X_i=Z_i^{(1)} X i = Z i ( 1 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) T n T_n T n T n c T_n^c T n c T n c T_n^c T n c
Lemma 5.3. For every n ≥ 2 n \ge2 n ≥ 2
P { T n } ≤ 4 n + 1 . \mathbb{P}\{T_n\} \le\frac{4}{n+1}. P { T n } ≤ n + 1 4 . Proof. The event T n T_n T n U = max i ≤ n X i U = \max_{i \le n} X_i U = max i ≤ n X i u ∈ I k u \in I_k u ∈ I k a ( u ) = 1 − 1 / k a(u) = 1 - 1/k a ( u ) = 1 − 1/ k U = u U = u U = u n − 1 n-1 n − 1 ( 0 , u ) (0,u) ( 0 , u ) u − a ( u ) ≤ 1 / [ k ( k + 1 ) ] ≤ 2 ( 1 − u ) 2 u-a(u) \le1/[k(k+1)] \le2(1-u)^2 u − a ( u ) ≤ 1/ [ k ( k + 1 )] ≤ 2 ( 1 − u ) 2 u ∈ I k u \in I_k u ∈ I k
P { T n } = n ∫ 0 1 [ 1 − ( a ( u ) u ) n − 1 ] u n − 1 d u ≤ n ( n − 1 ) ∫ 0 1 ( u − a ( u ) ) u n − 2 d u ≤ 2 n ( n − 1 ) ∫ 0 1 ( 1 − u ) 2 u n − 2 d u = 4 n + 1 . \begin{aligned}
\mathbb{P}\{T_n\}
&= n \int_0^1 \left[1-\left(\frac{a(u)}{u}\right)^{n-1}\right]u^{n-1}\,du \\
&\le n(n-1)\int_0^1 (u-a(u))u^{n-2}\,du \\
&\le2n(n-1)\int_0^1 (1-u)^2u^{n-2}\,du
= \frac{4}{n+1}.
\end{aligned} P { T n } = n ∫ 0 1 [ 1 − ( u a ( u ) ) n − 1 ] u n − 1 d u ≤ n ( n − 1 ) ∫ 0 1 ( u − a ( u )) u n − 2 d u ≤ 2 n ( n − 1 ) ∫ 0 1 ( 1 − u ) 2 u n − 2 d u = n + 1 4 . The equality conditions on the maximum; the first inequality uses 1 − x n − 1 ≤ ( n − 1 ) ( 1 − x ) 1-x^{n-1} \le(n-1)(1-x) 1 − x n − 1 ≤ ( n − 1 ) ( 1 − x )
A vector rule observes more than the first coordinate. For the distribution F d F_d F d
Lemma 5.4. For every n ≥ 1 n \ge1 n ≥ 1 τ \tau τ F d F_d F d
P { τ ≤ n , X τ = max i ≤ n X i } ≤ v n . \mathbb{P}\left\{\tau\le n,\ X_\tau= \max_{i \le n} X_i\right\} \le v_n. P { τ ≤ n , X τ = i ≤ n max X i } ≤ v n . Proof. Given an arriving one-dimensional observation X i = x ∈ I k X_i=x\in I_k X i = x ∈ I k d − 1 d-1 d − 1 I k I_k I k x x x Z i Z_i Z i τ \tau τ
This is a valid one-dimensional stopping rule with the same joint distribution of observations and decisions as the vector rule. Its probability of selecting the largest first coordinate is therefore at most v n v_n v n □ \square □
Proof of Theorem 5.1 . For a distribution F F F v n v_n v n (22) .
Construction 5.2 gives a single distribution F d F_d F d n n n T n T_n T n τ \tau τ
P { τ ≤ n , Z τ ∈ Max ( Z 1 , … , Z n ) } ≤ P { τ ≤ n , X τ = max i ≤ n X i } + P { T n } ≤ v n + 4 n + 1 . \mathbb{P}\{\tau\le n,\ Z_\tau\in\operatorname{Max}(Z_1,\ldots,Z_n)\}
\le\mathbb{P}\{\tau\le n,\ X_\tau=\max_{i\le n}X_i\}+\mathbb{P}\{T_n\}
\le v_n+\frac{4}{n+1}. P { τ ≤ n , Z τ ∈ Max ( Z 1 , … , Z n )} ≤ P { τ ≤ n , X τ = i ≤ n max X i } + P { T n } ≤ v n + n + 1 4 . by Lemmas 5.3 and 5.4. Taking the supremum over all rules proves the upper bound in (23) ; its lower bound follows from (22) . Finally, (21) gives p n ∗ ( F d ) → v ∞ p_n^*(F_d)\to v_\infty p n ∗ ( F d ) → v ∞ □ \square □
Within each cube, the distribution has a d d d 1 − O ( 1 / n ) 1-O(1/n) 1 − O ( 1/ n ) F d F_d F d
Gaussian Dependence
Arbitrary dependence can keep the optimal selection probability below one, as § 5 shows. We now extend the results under independence to Gaussian dependence. We first transform the observations into independent standard Gaussian variables, so that the region dominating each point becomes a cone with its vertex at that point (§ 6.1 ). We then extend the fixed-cutoff and optimal failure results from independent coordinates, with the rank-based rule also estimating correlations (§ 6.2 and § 6.3 ). We next determine the optimal failure asymptotics for singular Gaussian distributions, including cases where every observation is maximal or the problem reduces to one-dimensional selection (§ 6.4 ). Finally, we relate the failure probabilities to the expected frontier size (§ 6.5 ).
Throughout the first three subsections, let F = N d ( 0 , Σ ) F=\mathcal{N}_d(0,\Sigma) F = N d ( 0 , Σ ) d ≥ 2 d\ge2 d ≥ 2 Σ \Sigma Σ q q q U s \mathcal{U}_s U s A s = F ( U s ) A_s=F(\mathcal{U}_s) A s = F ( U s ) m = n − s m=n-s m = n − s p n ( s ) p_n(s) p n ( s ) p ( r ) p(r) p ( r ) F F F
Cone Representation
In two dimensions, a linear change of coordinates turns the elliptical Gaussian density contours into circles. The same change turns the upper-right region above each point into a wedge. Thus the distribution becomes standard Gaussian, but the comparison between points changes. In dimension d d d
X s = Σ − 1 / 2 Z s ∼ N d ( 0 , I d ) , C = { Σ − 1 / 2 y : y ∈ R + d } . X_s=\Sigma^{-1/2}Z_s\sim\mathcal{N}_d(0,I_d),\qquad C=\{\Sigma^{-1/2}y:y\in\mathbb{R}_+^d\}. X s = Σ − 1/2 Z s ∼ N d ( 0 , I d ) , C = { Σ − 1/2 y : y ∈ R + d } . Here R + d = [ 0 , ∞ ) d \mathbb{R}_+^d=[0,\infty)^d R + d = [ 0 , ∞ ) d Σ 1 / 2 \Sigma^{1/2} Σ 1/2 Σ \Sigma Σ Σ − 1 / 2 \Sigma^{-1/2} Σ − 1/2 C C C § 2 , define
x ⪯ C x ′ ⟺ x ′ − x ∈ C , x ≺ C x ′ ⟺ x ⪯ C x ′ and x ≠ x ′ . x\preceq_C x'\quad\Longleftrightarrow\quad x'-x\in C,\qquad x\prec_C x'\quad\Longleftrightarrow\quad x\preceq_C x'\text{ and }x\ne x'. x ⪯ C x ′ ⟺ x ′ − x ∈ C , x ≺ C x ′ ⟺ x ⪯ C x ′ and x = x ′ . Then Z s ≺ Z i Z_s\prec Z_i Z s ≺ Z i X s ≺ C X i X_s\prec_C X_i X s ≺ C X i x = Σ − 1 / 2 z x=\Sigma^{-1/2}z x = Σ − 1/2 z Z = Σ 1 / 2 X ∼ F Z=\Sigma^{1/2}X\sim F Z = Σ 1/2 X ∼ F
q C ( x ) : = P { x ≺ C X } = P { X ∈ x + C } = ( 2 π ) − d / 2 ∫ C e − ∥ x + y ∥ 2 / 2 d y = q F ( z ) . \begin{aligned}
q_C(x):=\mathbb{P}\{x\prec_C X\}=\mathbb{P}\{X\in x+C\} \\
&=(2\pi)^{-d/2}\int_C e^{-\lVert x+y\rVert^2/2}\,dy=q_F(z).
\end{aligned} q C ( x ) := P { x ≺ C X } = P { X ∈ x + C } = ( 2 π ) − d /2 ∫ C e − ∥ x + y ∥ 2 /2 d y = q F ( z ) . Here ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ x + C = { x + y : y ∈ C } x+C=\{x+y:y\in C\} x + C = { x + y : y ∈ C } x x x P { X = x } = 0 \mathbb{P}\{X=x\}=0 P { X = x } = 0 q C q_C q C q = q F q=q_F q = q F ≺ C \prec_C ≺ C
To use the stopping arguments, we need to know how often an observation has a small domination risk. The coefficient a Σ a_\Sigma a Σ § 12 , used with Σ = I d \Sigma=I_d Σ = I d § 3 and § 4 , give
H ( v ) : = P { q ( Z ) ≤ v } ∼ a Σ v ( log ( 1 / v ) ) d − 1 , v ↓ 0 , (24) H(v):=\mathbb{P}\{q(Z)\le v\}\sim a_\Sigma v(\log(1/v))^{d-1},\qquad v\downarrow0, \tag*{(24)} H ( v ) := P { q ( Z ) ≤ v } ∼ a Σ v ( log ( 1/ v ) ) d − 1 , v ↓ 0 , (24) with the following integral expression for the coefficient:
a Σ = det Σ ( d − 1 ) ! ∫ ( 0 , ∞ ) d ( ∏ k = 1 d z ( k ) ) e − z T Σ z / 2 d z . (25) a_\Sigma=\frac{\det\Sigma}{(d-1)!}\int_{(0,\infty)^d}\left(\prod_{k=1}^{d}z^{(k)}\right)e^{-z^\mathsf{T}\Sigma z/2}\,dz. \tag*{(25)} a Σ = ( d − 1 )! det Σ ∫ ( 0 , ∞ ) d ( k = 1 ∏ d z ( k ) ) e − z T Σ z /2 d z . (25) For Σ = I d \Sigma=I_d Σ = I d a I = 1 / ( d − 1 ) ! a_I=1/(d-1)! a I = 1/ ( d − 1 )! (9) .
To estimate how often q C ( X ) q_C(X) q C ( X ) x x x x ⋅ y ≥ 0 x\cdot y\ge0 x ⋅ y ≥ 0 y ∈ C y\in C y ∈ C ∥ x + y ∥ 2 − ∥ x ∥ 2 = 2 x ⋅ y + ∥ y ∥ 2 \lVert x+y\rVert^2-\lVert x\rVert^2=2x\cdot y+\lVert y\rVert^2 ∥ x + y ∥ 2 − ∥ x ∥ 2 = 2 x ⋅ y + ∥ y ∥ 2 dual cone
C ∗ = { x : x ⋅ y ≥ 0 for every y ∈ C } . C^*=\{x:x\cdot y\ge0\text{ for every }y\in C\}. C ∗ = { x : x ⋅ y ≥ 0 for every y ∈ C } . Along any fixed direction outside C ∗ C^* C ∗ x + C x+C x + C ∥ x ∥ \lVert x\rVert ∥ x ∥ x x x ∥ x ∥ \lVert x\rVert ∥ x ∥ q C ( x ) ≤ v q_C(x)\le v q C ( x ) ≤ v x x x Theorem B.1 makes this comparison precise and controls directions near the boundary. It shows that these outside directions contribute only a smaller-order term to P { q C ( X ) ≤ v } \mathbb{P}\{q_C(X) \le v\} P { q C ( X ) ≤ v } v ↓ 0 v \downarrow0 v ↓ 0 C ∗ C^* C ∗ a Σ a_\Sigma a Σ
In two dimensions, write ρ = Σ 12 \rho= \Sigma_{12} ρ = Σ 12 C C C π − arccos ρ \pi- \arccos\rho π − arccos ρ C ∗ C^* C ∗ arccos ρ \arccos\rho arccos ρ Figure 6 shows both cones.
Figure 6. Gray arrows bound C C C C ∗ C^* C ∗ x x x C ∗ C^* C ∗ x x x P { q C ( X ) ≤ v } \mathbb{P}\{q_C(X) \le v\} P { q C ( X ) ≤ v } v ↓ 0 v \downarrow0 v ↓ 0
In dimension two, the coefficient has the simpler form
a ρ = 1 − ρ arccos ρ 1 − ρ 2 , − 1 < ρ < 1. (26) a_\rho= 1 - \frac{\rho\arccos\rho}{\sqrt{1-\rho^2}}, \qquad-1 < \rho< 1. \tag*{(26)} a ρ = 1 − 1 − ρ 2 ρ arccos ρ , − 1 < ρ < 1. (26) It equals one at independence. Its derivation is in the proof of Corollary B.2 ; § 6.5 relates the same coefficient to the expected number of maximal observations.
The distribution in (24) also fixes the scale of both stopping arguments. Write
M n = E [ ∣ Max ( Z 1 , … , Z n ) ∣ ] . M_n = \mathbb{E}\left[\left|\operatorname{Max}(Z_1,\ldots,Z_n)\right|\right]. M n = E [ ∣ Max ( Z 1 , … , Z n ) ∣ ] . Conditioning on one observation and using the Gaussian mean estimate in Lemma B.4 gives
M n = n E [ ( 1 − q ( Z ) ) n − 1 ] ∼ a Σ ( log n ) d − 1 . (27) M_n = n\mathbb{E}\left[(1-q(Z))^{n-1}\right] \sim a_\Sigma(\log n)^{d-1}. \tag*{(27)} M n = n E [ ( 1 − q ( Z ) ) n − 1 ] ∼ a Σ ( log n ) d − 1 . (27) In two dimensions, the coefficient a ρ a_\rho a ρ (26) decreases as correlation increases. Figure 7 shows that fewer maximal points correspond to a larger optimal failure probability.
Figure 7. For two Gaussian coordinates with fixed correlation ρ \rho ρ a ρ log n a_\rho\log n a ρ log n 2 / ( a ρ log n log log n ) 2/(a_\rho\log n \log\log n) 2/ ( a ρ log n log log n )
For u u u (51) , (24) and (47) give
P { q ( Z ) ≤ u } ∼ M n u , E [ q ( Z ) 1 { q ( Z ) ≤ u } ] ∼ M n u 2 2 . (28) \mathbb{P}\{q(Z) \le u\} \sim M_nu,\qquad\mathbb{E}[q(Z)\mathbf{1}\{q(Z) \le u\}] \sim\frac{M_nu^2}{2}. \tag*{(28)} P { q ( Z ) ≤ u } ∼ M n u , E [ q ( Z ) 1 { q ( Z ) ≤ u }] ∼ 2 M n u 2 . (28) The first quantity counts points that meet a threshold; the second measures their chance of being dominated later. The proof for fixed-cutoff rules also needs estimates for the random probability A s A_s A s Σ \Sigma Σ
Fixed-Cutoff Rules
Theorem 6.1. For the fixed-cutoff rule of § 3 , as n n n p n ( s n ) → 1 p_n(s_n) \to1 p n ( s n ) → 1
m n s n → 0 and m n ( log s n ) d − 1 s n → ∞ , \frac{m_n}{s_n} \to0 \quad\text{and}\quad\frac{m_n(\log s_n)^{d-1}}{s_n} \to\infty, s n m n → 0 and s n m n ( log s n ) d − 1 → ∞ , where m n = n − s n m_n = n-s_n m n = n − s n
min 1 ≤ s < n ( 1 − p n ( s ) ) ∼ d − 1 a Σ log log n ( log n ) d − 1 , \min_{1\le s<n}(1-p_n(s)) \sim\frac{d-1}{a_\Sigma}\frac{\log\log n}{(\log n)^{d-1}}, 1 ≤ s < n min ( 1 − p n ( s )) ∼ a Σ d − 1 ( log n ) d − 1 log log n , and every minimizing cutoff s n ∗ s_n^* s n ∗
n − s n ∗ ∼ d − 1 a Σ n log log n ( log n ) d − 1 . n-s_n^* \sim\frac{d-1}{a_\Sigma}\frac{n\log\log n}{(\log n)^{d-1}}. n − s n ∗ ∼ a Σ d − 1 ( log n ) d − 1 n log log n . Proof. Apply the proofs of Theorems Theorems 3.2 and 3.3 with a s = a Σ ( log s ) d − 1 / s a_s = a_\Sigma(\log s)^{d-1}/s a s = a Σ ( log s ) d − 1 / s (2) uses only independent arrivals and transitivity of domination. Lemmas B.6 and B.7 supply the same mean, concentration, and replacement bounds for this fixed Σ \Sigma Σ a Σ a_\Sigma a Σ (3) . Also q ( z ) > 0 q(z)>0 q ( z ) > 0 z z z
For m / s → 0 m/s \to0 m / s → 0 m a s → ∞ ma_s \to\infty m a s → ∞ (6) , with later-domination probability asymptotic to m / s m/s m / s
m n = ⌈ ( d − 1 ) n log log n a Σ ( log n ) d − 1 ⌉ . m_n=\left\lceil\frac{(d-1)n\log\log n}{a_{\Sigma}(\log n)^{d-1}}\right\rceil. m n = ⌈ a Σ ( log n ) d − 1 ( d − 1 ) n log log n ⌉ . Then m a s = ( d − 1 ) log log s + o ( 1 ) ma_s=(d-1)\log\log s+o(1) m a s = ( d − 1 ) log log s + o ( 1 ) (54) makes P { τ = ∞ } = o ( m / s ) \mathbb{P}\{\tau=\infty\}=o(m/s) P { τ = ∞ } = o ( m / s ) m a s ≥ ( d − 1 − o ( 1 ) ) log log n ma_s\ge(d-1-o(1))\log\log n m a s ≥ ( d − 1 − o ( 1 )) log log n (7) . This gives both the lower bound and the cutoff location.
Optimal Stopping
We use the time-dependent threshold from § 4.2 , with a Σ a_{\Sigma} a Σ 1 / ( d − 1 ) ! 1/(d-1)! 1/ ( d − 1 )! G G G F F F
Theorem 6.2. For fixed d ≥ 2 d\ge2 d ≥ 2 Σ \Sigma Σ
1 − p n ⋆ ( F ) ∼ 1 − p n , r a n k ⋆ ( G ) ∼ 2 a Σ ( d − 1 ) ( log n ) d − 1 log log n . 1-p_n^{\star}(F)\sim1-p_{n,\mathop{\rm rank}}^{\star}(G)\sim\frac{2}{a_{\Sigma}(d-1)(\log n)^{d-1}\log\log n}. 1 − p n ⋆ ( F ) ∼ 1 − p n , rank ⋆ ( G ) ∼ a Σ ( d − 1 ) ( log n ) d − 1 log log n 2 . The full-information rule uses (29) below. The rank-based rule constructed below knows that the observations are Gaussian but is not given their means, variances, or correlations. Both have the displayed leading failure probability.
Lower bound. Apply Theorem 4.2’s proof with the same ℓ \ell ℓ B s B_s B s τ ′ \tau' τ ′ q q q (11) . Its distribution inputs are (24) and (48) , with a Σ a_{\Sigma} a Σ 1 / ( d − 1 ) ! 1/(d-1)! 1/ ( d − 1 )! (12) are still o ( 1 ) o(1) o ( 1 ) ℓ \ell ℓ H H H 1 − ( 1 − q ) m ≥ 1 − e − m q 1-(1-q)^m\ge1-e^{-mq} 1 − ( 1 − q ) m ≥ 1 − e − m q P { τ ′ = ∞ } = o ( 1 ) \mathbb{P}\{\tau'=\infty\}=o(1) P { τ ′ = ∞ } = o ( 1 ) B s B_s B s log ( 1 / q ) = log n + O ( log log n ) \log(1/q)=\log n+O(\log\log n) log ( 1/ q ) = log n + O ( log log n ) (13) holds with a Σ a_{\Sigma} a Σ 1 / ( d − 1 ) ! 1/(d-1)! 1/ ( d − 1 )! P { Z ∈ B n − ℓ } = o ( 1 ) \mathbb{P}\{Z\in B_{n-\ell}\}=o(1) P { Z ∈ B n − ℓ } = o ( 1 ) (14) give
1 − p ( r ) ≥ 1 − o ( 1 ) 2 a Σ ( log n ) d − 1 4 − o ( 1 ) ( d − 1 ) log log n . 1-p(r)\ge\frac{1-o(1)}{2a_{\Sigma}(\log n)^{d-1}}\frac{4-o(1)}{(d-1)\log\log n}. 1 − p ( r ) ≥ 2 a Σ ( log n ) d − 1 1 − o ( 1 ) ( d − 1 ) log log n 4 − o ( 1 ) . This gives the claimed lower bound.
Full-information upper bound. Use the full-information rule of § 4.2 , with the same h = n exp ( log log n ) / ( log n ) d − 1 h=n\exp(\sqrt{\log\log n})/(\log n)^{d-1} h = n exp ( log log n ) / ( log n ) d − 1
u m = 2 a Σ ( m + 1 ) ( log n ) d − 1 log ( 1 + ( m + 1 ) / h ) . (29) u_m=\frac{2}{a_{\Sigma}(m+1)(\log n)^{d-1}\log(1+(m+1)/h)}. \tag*{(29)} u m = a Σ ( m + 1 ) ( log n ) d − 1 log ( 1 + ( m + 1 ) / h ) 2 . (29) Figure 8 compares the acceptance boundaries after applying Φ \Phi Φ
Figure 8. Gaussian threshold boundaries for n = 1000 n = 1000 n = 1000 u n − s u_{n-s} u n − s
Corollary B.11, used with Σ = I d \Sigma=I_d Σ = I d § 4 , now applies with the present Σ \Sigma Σ q ^ = q \widehat q=q q = q
P { τ = s ∣ H s − 1 } ≥ ( 1 − ε ) a Σ ( log n ) d − 1 u m , \mathbb{P}\{\tau=s\mid\mathcal{H}_{s-1}\}\ge(1-\varepsilon)a_{\Sigma}(\log n)^{d-1}u_m, P { τ = s ∣ H s − 1 } ≥ ( 1 − ε ) a Σ ( log n ) d − 1 u m , E [ q ( Z s ) 1 { τ = s } ∣ H s − 1 ] ≤ ( 1 + ε ) a Σ 2 ( log n ) d − 1 u m 2 . (30) \mathbb{E}\left[q(Z_s)\mathbf{1}\{\tau=s\}\mid\mathcal{H}_{s-1}\right]\le(1+\varepsilon)\frac{a_{\Sigma}}{2}(\log n)^{d-1}u_m^2. \tag*{(30)} E [ q ( Z s ) 1 { τ = s } ∣ H s − 1 ] ≤ ( 1 + ε ) 2 a Σ ( log n ) d − 1 u m 2 . (30) These are the two inputs in (18) , with a Σ a_{\Sigma} a Σ 1 / ( d − 1 ) ! 1/(d-1)! 1/ ( d − 1 )! ℓ ≤ m ≤ ⌈ n / 2 ⌉ − 1 \ell\le m \le\lceil n/2\rceil-1 ℓ ≤ m ≤ ⌈ n /2 ⌉ − 1 a Σ > 0 a_{\Sigma} > 0 a Σ > 0 (29) into the first bound cancels a Σ a_{\Sigma} a Σ (19) . In the second bound, the contribution is multiplied by 1 / [ a Σ ( d − 1 ) ! ] 1/[a_{\Sigma}(d-1)!] 1/ [ a Σ ( d − 1 )!] S ℓ S_{\ell} S ℓ (47) bounds the initial contribution by O Σ ( 1 / [ ( log n ) d − 1 ( log log n ) 2 ] ) O_{\Sigma}(1/[(\log n)^{d-1}(\log\log n)^2]) O Σ ( 1/ [( log n ) d − 1 ( log log n ) 2 ]) (20) gives
lim sup n → ∞ ( log n ) d − 1 log log n ( 1 − p ( r ) ) ≤ 2 ( 1 + ε ) ( 1 − 2 ε ) a Σ ( d − 1 ) . \limsup_{n\to\infty}(\log n)^{d-1}\log\log n\,(1-p(r)) \le\frac{2(1+\varepsilon)}{(1-2\varepsilon)a_{\Sigma}(d-1)}. n → ∞ lim sup ( log n ) d − 1 log log n ( 1 − p ( r )) ≤ ( 1 − 2 ε ) a Σ ( d − 1 ) 2 ( 1 + ε ) . Let ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0
Rank-based rule. Use the initial sample and the marginal probability estimates from § 4.2 . The product in (16) is replaced by a Gaussian rectangle probability. Its marginal inputs are estimated in exactly the same way; the additional unknown quantity is the correlation matrix.
Estimating correlations. Use the ⌊ n / 4 ⌋ \lfloor n/4\rfloor ⌊ n /4 ⌋ N k ℓ N_{k\ell} N k ℓ
N k ℓ = ∑ i = 1 ⌊ n / 4 ⌋ 1 { ( Z 2 i ( k ) − Z 2 i − 1 ( k ) ) ( Z 2 i ( ℓ ) − Z 2 i − 1 ( ℓ ) ) > 0 } . N_{k\ell}=\sum_{i=1}^{\lfloor n/4\rfloor}\mathbf{1}\{(Z_{2i}^{(k)}-Z_{2i-1}^{(k)})(Z_{2i}^{(\ell)}-Z_{2i-1}^{(\ell)})>0\}. N k ℓ = i = 1 ∑ ⌊ n /4 ⌋ 1 {( Z 2 i ( k ) − Z 2 i − 1 ( k ) ) ( Z 2 i ( ℓ ) − Z 2 i − 1 ( ℓ ) ) > 0 } . The probability that the comparisons agree is 1 − arccos ( Σ k ℓ ) / π 1-\arccos(\Sigma_{k\ell})/\pi 1 − arccos ( Σ k ℓ ) / π
Σ ‾ k ℓ = − cos ( π p ‾ ⌊ n / 4 ⌋ ( N k ℓ ) ) ( k ≠ ℓ ) , Σ ‾ k k = 1. (31) \overline{\Sigma}_{k\ell}=-\cos\left(\pi\overline{p}_{\lfloor n/4\rfloor}(N_{k\ell})\right)\quad(k\ne\ell),\qquad\overline{\Sigma}_{kk}=1. \tag*{(31)} Σ k ℓ = − cos ( π p ⌊ n /4 ⌋ ( N k ℓ ) ) ( k = ℓ ) , Σ k k = 1. (31) Only comparisons within each pair are needed.
Estimating marginal positions. When Σ ‾ \overline{\Sigma} Σ z z z
z ^ ( k ) = Φ − 1 ( 1 − p ‾ ⌊ n / 2 ⌋ ( # { i ≤ ⌊ n / 2 ⌋ : Z i ( k ) > z ( k ) } ) ) , \widehat{z}^{(k)}=\Phi^{-1}\left(1-\overline{p}_{\lfloor n/2\rfloor}\left(\#\{i\le\lfloor n/2\rfloor:Z_i^{(k)}>z^{(k)}\}\right)\right), z ( k ) = Φ − 1 ( 1 − p ⌊ n /2 ⌋ ( # { i ≤ ⌊ n /2 ⌋ : Z i ( k ) > z ( k ) } ) ) , q ^ ( z ) = P W ∼ N d ( 0 , Σ ‾ ) { W ( k ) ≥ z ^ ( k ) for every k ∈ [ d ] } . (32) \widehat{q}(z)=\mathbb{P}_{W\sim\mathcal{N}_d(0,\overline{\Sigma})}\left\{W^{(k)}\ge\widehat{z}^{(k)}\text{ for every }k\in[d]\right\}. \tag*{(32)} q ( z ) = P W ∼ N d ( 0 , Σ ) { W ( k ) ≥ z ( k ) for every k ∈ [ d ] } . (32) The count estimates the marginal probability of exceeding z ( k ) z^{(k)} z ( k ) z ^ ( k ) \hat{z}^{(k)} z ^ ( k ) − ∞ -\infty − ∞
Use the stopping time (17) with this q ^ \hat{q} q ^ a Σ ‾ a_{\overline{\Sigma}} a Σ a Σ a_{\Sigma} a Σ (29) . If there are no pairs or Σ ‾ \overline{\Sigma} Σ n n n Z n Z_n Z n n n n
Rank-based upper bound. Use Corollary B.11 with a smaller error parameter, say ε / 4 \varepsilon/4 ε /4
Lemma B.9 gives a Σ ‾ / a Σ = 1 + o ( 1 ) a_{\overline{\Sigma}}/a_{\Sigma}=1+o(1) a Σ / a Σ = 1 + o ( 1 ) O d ( n − 1 ) O_d(n^{-1}) O d ( n − 1 ) ( 1 + o ( 1 ) ) (1+o(1)) ( 1 + o ( 1 )) (29) . The endpoint estimates in the proof of Theorem 4.3 leave room for this relative change within the permitted interval. For large n n n ε \varepsilon ε (30) with u m u_m u m (29) . The continuation and summation bounds therefore apply unchanged. The additional exceptional probability is negligible at the claimed rate, and there are no early selections.
The full-information argument also applies to any fixed closed convex cone C ⊂ R d C \subset\mathbb{R}^{d} C ⊂ R d C ∩ ( − C ) = { 0 } C \cap(-C)=\{0\} C ∩ ( − C ) = { 0 } H ( v ) = P { q C ( X ) ≤ v } H(v)=\mathbb{P}\{q_C(X)\leq v\} H ( v ) = P { q C ( X ) ≤ v }
inf r ( 1 − p ( r ) ) ∼ 2 ( d − 1 ) n H ( 1 / n ) log log n . (33) \inf_{r}(1-p(r)) \sim\frac{2}{(d-1)nH(1/n)\log\log n}. \tag*{(33)} r inf ( 1 − p ( r )) ∼ ( d − 1 ) n H ( 1/ n ) log log n 2 . (33) Theorem B.1 supplies H H H n H ( 1 / n ) nH(1/n) n H ( 1/ n ) ( log n ) d − 1 (\log n)^{d-1} ( log n ) d − 1 (29) changes the threshold by 1 + o ( 1 ) 1+o(1) 1 + o ( 1 )
Singular Gaussian Distributions
We now allow Σ \Sigma Σ r = rank Σ r=\operatorname{rank}\Sigma r = rank Σ Z = μ + A X Z=\mu+AX Z = μ + A X A ∈ R d × r A\in\mathbb{R}^{d\times r} A ∈ R d × r r r r A A T = Σ AA^{\mathsf{T}}=\Sigma A A T = Σ X ∼ N r ( 0 , I r ) X\sim\mathcal{N}_{r}(0,I_r) X ∼ N r ( 0 , I r )
C = { z ∈ R r : A z ≥ 0 } . C=\{z\in\mathbb{R}^{r}:Az\geq0\}. C = { z ∈ R r : A z ≥ 0 } . Because A A A C ∩ ( − C ) = { 0 } C\cap(-C)=\{0\} C ∩ ( − C ) = { 0 } r ≥ 1 r\geq1 r ≥ 1 q C ( x ) = q F ( μ + A x ) q_C(x)=q_F(\mu+Ax) q C ( x ) = q F ( μ + A x ) R r \mathbb{R}^{r} R r R r \mathbb{R}^{r} R r r ≥ 2 r\geq2 r ≥ 2 C C C
H ( v ) = P { q F ( Z ) ≤ v } ∼ a Σ v ( log ( 1 / v ) ) r − 1 , v ↓ 0. H(v)=\mathbb{P}\{q_F(Z)\leq v\}\sim a_{\Sigma}v(\log(1/v))^{r-1},\qquad v\downarrow0. H ( v ) = P { q F ( Z ) ≤ v } ∼ a Σ v ( log ( 1/ v ) ) r − 1 , v ↓ 0. with a Σ > 0 a_{\Sigma}>0 a Σ > 0 a Σ a_{\Sigma} a Σ Σ \Sigma Σ (39) , with dimension r r r (33) then apply in dimension r r r q q q
Proposition 6.3. For a fixed positive semidefinite Gaussian covariance Σ \Sigma Σ
If r = 0 r=0 r = 0
If r ≥ 1 r \ge1 r ≥ 1 C C C
If r = 1 r = 1 r = 1 C C C 1 / e 1/e 1/ e v ∞ = 0.580164 … v_\infty= 0.580164\ldots v ∞ = 0.580164 … § 5 .
If r ≥ 2 r \ge2 r ≥ 2 C C C
2 a Σ ( r − 1 ) ( log n ) r − 1 log log n . \frac{2}{a_\Sigma(r-1)(\log n)^{r-1}\log\log n}. a Σ ( r − 1 ) ( log n ) r − 1 log log n 2 . Proof. Identical observations do not dominate one another under our convention. A convex cone with empty interior is contained in a proper linear subspace. Since X i − X j ∼ N r ( 0 , 2 I r ) X_i-X_j \sim\mathcal{N}_r(0,2I_r) X i − X j ∼ N r ( 0 , 2 I r ) P { X i − X j ∈ C ∪ ( − C ) } = 0 \mathbb{P}\{X_i-X_j \in C \cup(-C)\}=0 P { X i − X j ∈ C ∪ ( − C )} = 0 Σ \Sigma Σ (32) with the known Σ \Sigma Σ Σ \Sigma Σ (29) with r r r d d d h h h ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊ n /2 ⌋ r r r (30) with r r r d d d Theorem 4.3 proves the upper bound, while (33) gives the lower bound.
The geometric condition can be checked directly. After deleting zero rows of A A A C C C A z > 0 Az > 0 A z > 0 Z = ( X ( 1 ) , X ( 2 ) , − X ( 2 ) ) Z=(X^{(1)},X^{(2)},-X^{(2)}) Z = ( X ( 1 ) , X ( 2 ) , − X ( 2 ) ) C = { ( x , 0 ) : x ≥ 0 } C=\{(x,0):x \ge0\} C = {( x , 0 ) : x ≥ 0 } + 1 +1 + 1 − 1 -1 − 1
The fixed-covariance bounds need not hold uniformly near singularity. For example, let F n F_n F n ρ n ∈ ( − 1 , 1 ) \rho_n \in(-1,1) ρ n ∈ ( − 1 , 1 ) 1 − ρ n = o ( n − 4 ) 1-\rho_n=o(n^{-4}) 1 − ρ n = o ( n − 4 ) arccos ( ρ n ) / π \arccos(\rho_n)/\pi arccos ( ρ n ) / π
P { ∃ i < j : ( Z i ( 1 ) − Z j ( 1 ) ) ( Z i ( 2 ) − Z j ( 2 ) ) < 0 } ≤ ( n 2 ) arccos ( ρ n ) π = o ( 1 ) . \mathbb{P}\left\{\exists i<j:\left(Z_i^{(1)}-Z_j^{(1)}\right)\left(Z_i^{(2)}-Z_j^{(2)}\right)<0\right\}
\le\binom{n}{2}\frac{\arccos(\rho_n)}{\pi}=o(1). P { ∃ i < j : ( Z i ( 1 ) − Z j ( 1 ) ) ( Z i ( 2 ) − Z j ( 2 ) ) < 0 } ≤ ( 2 n ) π arccos ( ρ n ) = o ( 1 ) . Outside this event, the maximal observation is the first-coordinate maximum. Given the arriving first coordinates, we can generate the second coordinates as Z i ( 2 ) = ρ n Z i ( 1 ) + 1 − ρ n 2 W i Z_i^{(2)}=\rho_n Z_i^{(1)}+\sqrt{1-\rho_n^2}\,W_i Z i ( 2 ) = ρ n Z i ( 1 ) + 1 − ρ n 2 W i W i W_i W i § 5 therefore gives p n ⋆ ( F n ) ≤ v n + o ( 1 ) p^\star_n(F_n)\le v_n+o(1) p n ⋆ ( F n ) ≤ v n + o ( 1 ) o ( 1 ) o(1) o ( 1 ) v ∞ v_\infty v ∞ 1 / e 1/e 1/ e
Expected Frontier Size
We return to a fixed positive definite correlation matrix Σ \Sigma Σ (27) gives log M n ∼ ( d − 1 ) log log n \log M_n \sim(d-1)\log\log n log M n ∼ ( d − 1 ) log log n 6.2 become
1 − max 1 ≤ s < n p n ( s ) ∼ log M n M n , 1 − p n ∗ ∼ 2 M n log M n . (34) 1-\max_{1\le s<n}p_n(s)\sim\frac{\log M_n}{M_n},\qquad1-p_n^*\sim\frac{2}{M_n\log M_n}. \tag*{(34)} 1 − 1 ≤ s < n max p n ( s ) ∼ M n log M n , 1 − p n ∗ ∼ M n log M n 2 . (34) Here p n ∗ p_n^* p n ∗ 1 2 ( log M n ) 2 \frac{1}{2}(\log M_n)^2 2 1 ( log M n ) 2 Σ \Sigma Σ Σ = I d \Sigma=I_d Σ = I d
The two estimates in (28) explain the shared calculation. At a threshold u u u M n u M_nu M n u q q q u / 2 u/2 u /2 m m m m u → 0 mu\to0 m u → 0 m u / 2 mu/2 m u /2
In (14) , the constant 2 comes from multiplying the factor ( 1 − o ( 1 ) ) / ( 2 M n ) (1-o(1))/(2M_n) ( 1 − o ( 1 )) / ( 2 M n ) q q q ( 4 − o ( 1 ) ) / log M n (4-o(1))/\log M_n ( 4 − o ( 1 )) / log M n (18) and sums their contributions over time.
There is one further requirement for that upper bound. A point that meets the threshold may already be dominated by an earlier observation. The bound (52) controls how many such points are excluded, including when Σ = I d \Sigma=I_d Σ = I d
Discussion
In our problem, n n n
The expected number of acceptable observations makes the benefit of this flexibility precise. Let M n M_n M n p n ∗ p_n^* p n ∗ d ≥ 2 d\ge2 d ≥ 2
1 − p n ∗ ∼ 2 M n log M n . 1-p_n^*\sim\frac{2}{M_n\log M_n}. 1 − p n ∗ ∼ M n log M n 2 . The relation holds both with full information, where the distribution is known and numerical values are observed, and with coordinate ranks alone. Within these families, the growing expected frontier determines how quickly the failure probability tends to zero. Gaussian correlation changes the frontier size and, through it, the leading failure constant.
A simple cutoff rule already exploits these opportunities. After rejecting an initial sample, it selects the first currently maximal observation, meaning one that no earlier point dominates. Waiting longer leaves fewer future observations that might dominate the selected point, but also fewer opportunities to select. We characterize all cutoff sequences whose success probability tends to one and determine the best leading failure probability among them.
The time-dependent rule improves on this performance by considering each candidate’s domination risk, the probability that a new independent observation dominates it. A currently maximal point is accepted only when this risk falls below a threshold that rises as time runs out, balancing later domination against the chance of selecting nothing. The scarcity of observations with very small domination risk yields a matching lower bound on failure. To attain this bound, the proof shows that enough points meeting the threshold remain available after excluding those dominated by earlier observations.
These risk estimates can be obtained from coordinate comparisons. Under independence, counts from an initial sample estimate the probability that a fresh observation exceeds a candidate in each coordinate; their product estimates its domination risk. For nonsingular Gaussian observations, the rule also estimates the correlations. These estimates preserve the optimal leading failure probability without requiring prior knowledge of the marginal distributions or the Gaussian parameters.
Other forms of dependence can remove this abundance of acceptable choices. Our counterexample has a joint density and uniform marginals, with observations lying in cubes arranged so that every point in a higher cube dominates every point in a lower one. With probability tending to one, the highest occupied cube contains a single observation, which is both the unique Pareto maximum and the first-coordinate maximum. Given each first coordinate, the remaining coordinates can be generated using fresh independent randomness, so they provide no additional information for identifying this maximum. Even with full information, the optimal success probability converges to the one-dimensional limit, approximately 0.58.
The two-dimensional Gaussian endpoints show how widely dependence can change the difficulty of selection. Perfect positive correlation gives the same ranking in both coordinates and recovers the one-dimensional problem. Perfect negative correlation makes every observation maximal.
Pareto maximality treats different undominated tradeoffs as equally successful, although specific preferences may distinguish sharply between them. If these preferences become known only after the observations have arrived, a decision maker may want to retain several candidates as they arrive. For a specified class of preferences, the question is how closely the best retained candidate can approximate the best point in the complete sample under the eventual preferences, and how the guarantee improves with the number of selections. Another objective keeps a single selection but distinguishes degrees of failure: require a choice by the end and minimize the expected number of observations that dominate it.
Dependence across time raises a different issue. Our analysis allows dependence between coordinates while successive observations are independent. With temporal dependence, past observations can change the conditional distribution of future candidates, so domination risk must be assessed using both the current point and the history already seen. Understanding how to use this information, and how it changes the best achievable success probability, provides a further direction for research.
A companion formalization in Lean 4 with mathlib is available in the GitHub repository. The repository contains the formal proofs, instructions for checking them, and a guide connecting the results in this paper to their Lean declarations.
Declaration of AI usage
We used OpenAI’s ChatGPT and Codex to assist with mathematical proof development and checking, including the refinement of estimates and stopping rules. This paper builds on a preliminary version developed by the authors. In preparing the current version, we determined the extensions to pursue, guided their mathematical development, and critically evaluated and revised the AI-assisted arguments.
These tools also assisted with improving the exposition and notation, checking references, preparing LaTeX source and figures, and developing and debugging the accompanying Lean 4 formalization. The authors reviewed the resulting material and take full responsibility for the mathematical results, proofs, citations, and final manuscript.
References
No Numerical Gain with a Known Rank Distribution
When the rank distribution is known but the sampling distribution is not, numerical values cannot improve the best worst-case guarantee. We prove Theorem 2.1 and its extension to arbitrary Borel probability distributions, including distributions with atoms. In this extension, F ( G ) \mathcal{F}(G) F ( G ) G G G [2 ] , and preserves the given dependence by changing only the numerical coordinate scales. We use the following finite Ramsey theorem [Ram30].
Theorem A.1. For positive integers t t t M M M K K K R t ( M ; K ) R_t(M;K) R t ( M ; K ) K K K t t t R t ( M ; K ) R_t(M;K) R t ( M ; K ) t t t M M M
For a finite set X X X [ X ] t = { A ⊆ X : ∣ A ∣ = t } [X]^t = \{A \subseteq X : |A| = t\} [ X ] t = { A ⊆ X : ∣ A ∣ = t } t t t
Lemma A.2. Fix positive integers t 1 , … , t d , M , K t_1,\ldots,t_d,M,K t 1 , … , t d , M , K M ≥ max k t k M \ge\max_k t_k M ≥ max k t k X k X_k X k ∏ k [ X k ] t k → [ K ] \prod_k [X_k]^{t_k} \to[K] ∏ k [ X k ] t k → [ K ] ∏ k [ Y k ] t k \prod_k [Y_k]^{t_k} ∏ k [ Y k ] t k M M M Y k ⊆ X k Y_k \subseteq X_k Y k ⊆ X k
Proof. Induct on d d d d = 1 d=1 d = 1 Q Q Q 2 , … , d 2,\ldots,d 2 , … , d Q Q Q t 1 t_1 t 1 X 1 X_1 X 1 K ∏ k = 2 d ( Q t k ) K^{\prod_{k=2}^d {Q \choose t_k}} K ∏ k = 2 d ( t k Q ) M M M X 1 X_1 X 1 M M M □ \square □
Corollary A.3. For finitely many such colorings, possibly with different subset sizes in each coordinate, sufficiently large coordinate sets contain M M M
Proof. Choose the required sizes backward through the finite list of colorings, and apply Lemma A.2 successively. Restriction preserves the constancy of the earlier colorings.
Proof of Theorem 2.1 . Fix F 0 F_0 F 0 r r r ε > 0 \varepsilon> 0 ε > 0
Cell partition. For any h > 0 h > 0 h > 0 h h h h h h h h h M M M n n n
For an i.i.d. sample Z 1 , … , Z n ∼ F 0 Z_1,\ldots,Z_n \sim F_0 Z 1 , … , Z n ∼ F 0 D D D h h h
P { D c } ≤ d ( n 2 ) h . \mathbb{P}\{D^{c}\} \leq d\binom{n}{2}h. P { D c } ≤ d ( 2 n ) h . This uses independence across observations, not across coordinates.
Ramsey reduction. For a time-t t t g g g m k ( g ) m_k(g) m k ( g ) k k k g g g t t t r t r_t r t f t , g f_{t,g} f t , g ∑ k m k ( g ) \sum_k m_k(g) ∑ k m k ( g )
Fix δ > 0 \delta> 0 δ > 0 X k ⊂ ( 0 , 1 ) X_k \subset(0,1) X k ⊂ ( 0 , 1 ) ∏ k [ X k ] m k ( g ) \prod_k [X_k]^{m_k(g)} ∏ k [ X k ] m k ( g ) [ 0 , 1 ] [0,1] [ 0 , 1 ] δ \delta δ f t , g f_{t,g} f t , g t ≤ n t \leq n t ≤ n g g g
Corollary A.3 gives M M M S k S_k S k r t ′ ( g ) r'_t(g) r t ′ ( g )
∣ f t , g ( x ) − r t ′ ( g ) ∣ ≤ δ (35) \lvert f_{t,g}(x)-r'_t(g)\rvert\leq\delta \tag*{(35)} ∣ f t , g ( x ) − r t ′ ( g )∣ ≤ δ (35) at every grid tuple with rank array g g g r t ′ ( g ) r'_t(g) r t ′ ( g ) k k k S k S_k S k
Monotone transformations. In an interval cell assigned to grid point a a a v ( x ) = 2 arctan ( x ) / π v(x)=2\arctan(x)/\pi v ( x ) = 2 arctan ( x ) / π v = 0 v=0 v = 0
T ( x ) = a + U + b v ( x ) , U ∼ Unif ( − b , b ) . T(x)=a+U+bv(x), \qquad U\sim\operatorname{Unif}(-b,b). T ( x ) = a + U + b v ( x ) , U ∼ Unif ( − b , b ) . Use independent offsets for every coordinate and cell. Choose b > 0 b>0 b > 0 ( a − 2 b , a + 2 b ) (a-2b,a+2b) ( a − 2 b , a + 2 b ) T k T_k T k R \mathbb{R} R F T F_T F T F ( G ) \mathcal{F}(G) F ( G ) F 0 F_0 F 0 F T F_T F T Theorem 2.1 .
Fix an original sample in D D D ( 2 b ) − ∑ k m k ( g ) (2b)^{-\sum_k m_k(g)} ( 2 b ) − ∑ k m k ( g ) 2 b 2b 2 b f t , g f_{t,g} f t , g
There are finitely many grid tuples, all Lebesgue points. We can therefore decrease b b b ∣ f t , g ( y ) − f t , g ( a ) ∣ \lvert f_{t,g}(y)-f_{t,g}(a)\rvert ∣ f t , g ( y ) − f t , g ( a )∣ 2 − d n δ 2^{-dn}\delta 2 − d n δ 2 d n 2^{dn} 2 d n D D D
E T [ ∣ r t ( T ( Z 1 ) , … , T ( Z t ) ) − f t , g ( a ) ∣ ] ≤ δ . \mathbb{E}_T\left[\left\lvert r_t(T(Z_1),\ldots,T(Z_t))-f_{t,g}(a)\right\rvert\right]\le\delta. E T [ ∣ r t ( T ( Z 1 ) , … , T ( Z t )) − f t , g ( a ) ∣ ] ≤ δ . Together with (35) , this bounds the expected difference from r t ′ ( g ) r'_t(g) r t ′ ( g ) 2 δ 2\delta 2 δ
Run both stopping rules using the same extra uniform random variables. The probability of a first disagreement is at most the sum of the differences of their stopping probabilities. Therefore
E T [ ∣ p F T ( r ) − p F T ( r ′ ) ∣ ] ≤ d ( n 2 ) h + 2 n δ . \mathbb{E}_T\left[\left\lvert p_{F_T}(r)-p_{F_T}(r')\right\rvert\right]\le d\binom{n}{2}h+2n\delta. E T [ ∣ p F T ( r ) − p F T ( r ′ ) ∣ ] ≤ d ( 2 n ) h + 2 n δ . Choose h , δ > 0 h,\delta>0 h , δ > 0 ε / 2 \varepsilon/2 ε /2 F T F_T F T r ′ r' r ′ ε \varepsilon ε
Thus every numerical rule has worst-case value at most p n , r a n k ⋆ ( G ) + ε p^\star_{n,\mathop{\rm rank}}(G)+\varepsilon p n , rank ⋆ ( G ) + ε ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 F ∈ F ( G ) F\in\mathcal{F}(G) F ∈ F ( G ) F 0 F_0 F 0
Gaussian Probability Estimates
The estimates below apply to Sections 3, 4, and 6. Independent coordinates correspond to Σ = I d \Sigma=I_d Σ = I d C = R + d C=\mathbb{R}_+^d C = R + d a I = 1 / ( d − 1 ) ! a_I=1/(d-1)! a I = 1/ ( d − 1 )! q q q
Moment identities
We first record identities valid for any distribution of the observations. For any observation Z Z Z H ( v ) = P { q ( Z ) ≤ v } H(v)=\mathbb{P}\{q(Z)\le v\} H ( v ) = P { q ( Z ) ≤ v } 0 < u ≤ 1 0<u\le1 0 < u ≤ 1 s ≥ 2 s\ge2 s ≥ 2 λ > 0 \lambda>0 λ > 0
E [ q ( Z ) 1 { q ( Z ) ≤ u } ] = u H ( u ) − ∫ 0 u H ( v ) d v . \mathbb{E}\left[q(Z)1\{q(Z)\le u\}\right]=uH(u)-\int_0^u H(v)\,dv. E [ q ( Z ) 1 { q ( Z ) ≤ u } ] = u H ( u ) − ∫ 0 u H ( v ) d v . E [ ( 1 − q ( Z ) ) s − 1 ] = ( s − 1 ) ∫ 0 1 ( 1 − v ) s − 2 H ( v ) d v . \mathbb{E}\left[(1-q(Z))^{s-1}\right]=(s-1)\int_0^1(1-v)^{s-2}H(v)\,dv. E [ ( 1 − q ( Z ) ) s − 1 ] = ( s − 1 ) ∫ 0 1 ( 1 − v ) s − 2 H ( v ) d v . E [ e − λ q ( Z ) ] = e − λ + λ ∫ 0 1 e − λ v H ( v ) d v . \mathbb{E}\left[e^{-\lambda q(Z)}\right]=e^{-\lambda}+\lambda\int_0^1e^{-\lambda v}H(v)\,dv. E [ e − λ q ( Z ) ] = e − λ + λ ∫ 0 1 e − λ v H ( v ) d v . If H ( v ) / ( v ( log ( 1 / v ) ) d − 1 ) H(v)/(v(\log(1/v))^{d-1}) H ( v ) / ( v ( log ( 1/ v ) ) d − 1 ) v ↓ 0 v \downarrow0 v ↓ 0
E [ q ( Z ) 1 { q ( Z ) ≤ u } ] ∼ 1 2 u H ( u ) , E [ ( 1 − q ( Z ) ) s − 1 ] ∼ H ( 1 / s ) , E [ e − λ q ( Z ) ] ∼ H ( 1 / λ ) , E [ q ( Z ) e − λ q ( Z ) ] = O ( H ( 1 / λ ) / λ ) . (36) \begin{aligned}
\mathbb{E}\left[q(Z)1\{q(Z)\le u\}\right]&\sim\tfrac{1}{2}uH(u),\\
\mathbb{E}\left[(1-q(Z))^{s-1}\right]&\sim H(1/s),\\
\mathbb{E}\left[e^{-\lambda q(Z)}\right]&\sim H(1/\lambda),\\
\mathbb{E}\left[q(Z)e^{-\lambda q(Z)}\right]&=O(H(1/\lambda)/\lambda). \tag*{(36)}
\end{aligned} E [ q ( Z ) 1 { q ( Z ) ≤ u } ] E [ ( 1 − q ( Z ) ) s − 1 ] E [ e − λ q ( Z ) ] E [ q ( Z ) e − λ q ( Z ) ] ∼ 2 1 u H ( u ) , ∼ H ( 1/ s ) , ∼ H ( 1/ λ ) , = O ( H ( 1/ λ ) / λ ) . (36) Here u ↓ 0 u\downarrow0 u ↓ 0 s → ∞ s\to\infty s → ∞ λ → ∞ \lambda\to\infty λ → ∞ v = u t v=ut v = u t v = t / s v=t/s v = t / s v = t / λ v=t/\lambda v = t / λ t ( 1 + ∣ log t ∣ ) d − 1 t(1+|\log t|)^{d-1} t ( 1 + ∣ log t ∣ ) d − 1 ( 0 , 1 ) (0,1) ( 0 , 1 ) t e − t / 2 ( 1 + ∣ log t ∣ ) d − 1 te^{-t/2}(1+|\log t|)^{d-1} t e − t /2 ( 1 + ∣ log t ∣ ) d − 1 ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) x e − λ x ≤ 2 ( e λ ) − 1 e − λ x / 2 xe^{-\lambda x}\le2(e\lambda)^{-1}e^{-\lambda x/2} x e − λ x ≤ 2 ( e λ ) − 1 e − λ x /2
The same substitution gives the moments used to analyze fixed-cutoff rules. For k = 0 , 1 k=0,1 k = 0 , 1 T ∈ ( 0 , ∞ ] T\in(0,\infty] T ∈ ( 0 , ∞ ]
∫ 0 min { T / s , 1 } v k ( 1 − v ) s d H ( v ) ∼ H ( 1 / s ) s k ∫ 0 T t k e − t d t . (37) \int_{0}^{\min\{T/s,1\}}v^k(1-v)^s\,dH(v)\sim\frac{H(1/s)}{s^k}\int_{0}^{T}t^k e^{-t}\,dt. \tag*{(37)} ∫ 0 m i n { T / s , 1 } v k ( 1 − v ) s d H ( v ) ∼ s k H ( 1/ s ) ∫ 0 T t k e − t d t . (37) Here min { T / s , 1 } = 1 \min\{T/s,1\}=1 min { T / s , 1 } = 1 T = ∞ T=\infty T = ∞ T / s T/s T / s T < ∞ T<\infty T < ∞
The following bound also applies to other distributions and transitive comparisons. Write A s = F ( U s ) A_s=F(U_s) A s = F ( U s ) A s > 0 A_s>0 A s > 0 z ∈ U s z\in U_s z ∈ U s z z z U s U_s U s q ( z ) ≤ A s q(z)\le A_s q ( z ) ≤ A s
0 ≤ A s − 2 ∫ U s q d F ≤ 1 , (38) 0\le A_s^{-2}\int_{U_s}q\,dF\le1, \tag*{(38)} 0 ≤ A s − 2 ∫ U s q d F ≤ 1 , (38) E [ A s − 2 ∫ U s q d F ] ≤ 4 ( E [ A s ] ) 2 E [ ∫ U s q d F ] + P { A s < E [ A s ] / 2 } . \mathbb{E}\left[A_s^{-2}\int_{U_s}q\,dF\right]\le\frac{4}{(\mathbb{E}[A_s])^2}\mathbb{E}\left[\int_{U_s}q\,dF\right]+\mathbb{P}\{A_s<\mathbb{E}[A_s]/2\}. E [ A s − 2 ∫ U s q d F ] ≤ ( E [ A s ] ) 2 4 E [ ∫ U s q d F ] + P { A s < E [ A s ] /2 } . The second line splits according to A s ≥ E [ A s ] / 2 A_s\ge\mathbb{E}[A_s]/2 A s ≥ E [ A s ] /2
Gaussian tail asymptotics
In this appendix, ∥ x ∥ \lVert x\rVert ∥ x ∥ int ( C ) \operatorname{int}(C) int ( C ) C C C B ( 0 , t ) = { x : ∥ x ∥ < t } B(0,t)=\{x:\lVert x\rVert<t\} B ( 0 , t ) = { x : ∥ x ∥ < t } vol \operatorname{vol} vol γ \gamma γ R d \mathbb{R}^d R d ϕ ( x ) = ( 2 π ) − d / 2 e − ∥ x ∥ 2 / 2 \phi(x)=(2\pi)^{-d/2}e^{-\lVert x\rVert^2/2} ϕ ( x ) = ( 2 π ) − d /2 e − ∥ x ∥ 2 /2 C C C C ∩ ( − C ) = { 0 } C\cap(-C)=\{0\} C ∩ ( − C ) = { 0 } § 6 ,
q C ( x ) = γ ( x + C ) , H ( v ) = P { q C ( X ) ≤ v } , X ∼ γ . q_C(x)=\gamma(x+C),\qquad H(v)=\mathbb{P}\{q_C(X)\le v\},\qquad X\sim\gamma. q C ( x ) = γ ( x + C ) , H ( v ) = P { q C ( X ) ≤ v } , X ∼ γ . We use the dual cone C ∗ C^* C ∗ § 6 . For x ∈ int ( C ∗ ) x\in\operatorname{int}(C^*) x ∈ int ( C ∗ )
J ( x ) = ∫ C e − x ⋅ z d z . J(x)=\int_C e^{-x\cdot z}\,dz. J ( x ) = ∫ C e − x ⋅ z d z . It is finite since x ⋅ z x\cdot z x ⋅ z ∥ z ∥ \lVert z\rVert ∥ z ∥ C C C J ( t x ) = t − d J ( x ) J(tx)=t^{-d}J(x) J ( t x ) = t − d J ( x )
Theorem B.1. For a fixed cone C C C d ≥ 1 d\ge1 d ≥ 1
H ( v ) ∼ v ( log ( 1 / v ) ) d − 1 ( 2 d − 1 ∫ S d − 1 ∩ int ( C ∗ ) d σ ( θ ) J ( θ ) ) . (39) H(v)\sim v(\log(1/v))^{d-1}\left(2^{d-1}\int_{S^{d-1}\cap\operatorname{int}(C^*)}\frac{d\sigma(\theta)}{J(\theta)}\right). \tag*{(39)} H ( v ) ∼ v ( log ( 1/ v ) ) d − 1 ( 2 d − 1 ∫ S d − 1 ∩ int ( C ∗ ) J ( θ ) d σ ( θ ) ) . (39) Here S d − 1 S^{d-1} S d − 1 σ \sigma σ d = 1 d=1 d = 1 { − 1 , 1 } \{-1,1\} { − 1 , 1 }
Proof. We compute the radial contribution in each direction, then use a common bound to integrate over directions. Translating the Gaussian density gives
q C ( r θ ) = ϕ ( 0 ) e − r 2 / 2 ∫ C exp { − r θ ⋅ z − ∥ z ∥ 2 / 2 } d z . (40) q_C(r\theta)=\phi(0)e^{-r^2/2}\int_C\exp\{-r\theta\cdot z-\lVert z\rVert^2/2\}\,dz. \tag*{(40)} q C ( r θ ) = ϕ ( 0 ) e − r 2 /2 ∫ C exp { − r θ ⋅ z − ∥ z ∥ 2 /2 } d z . (40) Substituting y = r z y=rz y = r z int ( C ∗ ) ∩ S d − 1 \operatorname{int}(C^*)\cap S^{d-1} int ( C ∗ ) ∩ S d − 1
q C ( r θ ) ∼ ϕ ( 0 ) J ( θ ) e − r 2 / 2 r − d . (41) q_C(r\theta)\sim\phi(0)J(\theta)e^{-r^2/2}r^{-d}. \tag*{(41)} q C ( r θ ) ∼ ϕ ( 0 ) J ( θ ) e − r 2 /2 r − d . (41) Here domination follows from θ ⋅ y ≥ c ∥ y ∥ \theta\cdot y\ge c\lVert y\rVert θ ⋅ y ≥ c ∥ y ∥ H ( v ) H(v) H ( v )
A v ( θ ) = ϕ ( 0 ) ∫ 0 ∞ 1 { q C ( r θ ) ≤ v } e − r 2 / 2 r d − 1 d r . A_v(\theta)=\phi(0)\int_0^\infty\mathbf{1}\{q_C(r\theta)\le v\}e^{-r^2/2}r^{d-1}\,dr. A v ( θ ) = ϕ ( 0 ) ∫ 0 ∞ 1 { q C ( r θ ) ≤ v } e − r 2 /2 r d − 1 d r . If t v t_v t v ϕ ( 0 ) J ( θ ) e − t v 2 / 2 t v − d = v \phi(0)J(\theta)e^{-t_v^2/2}t_v^{-d}=v ϕ ( 0 ) J ( θ ) e − t v 2 /2 t v − d = v t v 2 ∼ 2 log ( 1 / v ) t_v^2\sim2\log(1/v) t v 2 ∼ 2 log ( 1/ v )
ϕ ( 0 ) ∫ t v ∞ e − r 2 / 2 r d − 1 d r ∼ ϕ ( 0 ) e − t v 2 / 2 t v d − 2 = v t v 2 d − 2 J ( θ ) . \phi(0)\int_{t_v}^\infty e^{-r^2/2}r^{d-1}\,dr\sim\phi(0)e^{-t_v^2/2}t_v^{d-2}=\frac{vt_v^{2d-2}}{J(\theta)}. ϕ ( 0 ) ∫ t v ∞ e − r 2 /2 r d − 1 d r ∼ ϕ ( 0 ) e − t v 2 /2 t v d − 2 = J ( θ ) v t v 2 d − 2 . Sandwiching (41) between its ( 1 ± ε ) (1\pm\varepsilon) ( 1 ± ε )
A v ( θ ) v ( log ( 1 / v ) ) d − 1 ⟶ 2 d − 1 J ( θ ) for θ ∈ int ( C ∗ ) . (42) \frac{A_v(\theta)}{v(\log(1/v))^{d-1}}\longrightarrow\frac{2^{d-1}}{J(\theta)}
\quad\text{for }\theta\in\operatorname{int}(C^*). \tag*{(42)} v ( log ( 1/ v ) ) d − 1 A v ( θ ) ⟶ J ( θ ) 2 d − 1 for θ ∈ int ( C ∗ ) . (42) For these upper and lower bounds, any bounded interval of radii contributes nothing once v v v q C q_C q C
Next fix θ ∉ C ∗ \theta\notin C^* θ ∈ / C ∗ z 0 ∈ int ( C ) z_0\in\operatorname{int}(C) z 0 ∈ int ( C ) θ ⋅ z 0 < 0 \theta\cdot z_0<0 θ ⋅ z 0 < 0 λ > 0 \lambda>0 λ > 0 ∥ θ + λ z 0 ∥ < 1 \lVert\theta+\lambda z_0\rVert<1 ∥ θ + λ z 0 ∥ < 1 r r r r λ z 0 + B ( 0 , 1 ) r\lambda z_0+B(0,1) r λ z 0 + B ( 0 , 1 ) C C C β ∈ ( ∥ θ + λ z 0 ∥ 2 , 1 ) \beta\in(\lVert\theta+\lambda z_0\rVert^2,1) β ∈ (∥ θ + λ z 0 ∥ 2 , 1 ) r r r
q C ( r θ ) ≥ ∫ r ( θ + λ z 0 ) + B ( 0 , 1 ) ϕ ( 0 ) e − ∥ z ∥ 2 / 2 d z ≥ c C , θ e − β r 2 / 2 q_C(r\theta)\ge\int_{r(\theta+\lambda z_0)+B(0,1)}\phi(0)e^{-\lVert z\rVert^2/2}\,dz\ge c_{C,\theta}e^{-\beta r^2/2} q C ( r θ ) ≥ ∫ r ( θ + λ z 0 ) + B ( 0 , 1 ) ϕ ( 0 ) e − ∥ z ∥ 2 /2 d z ≥ c C , θ e − β r 2 /2 for some c C , θ > 0 c_{C,\theta}>0 c C , θ > 0 q C ( r θ ) ≤ v q_C(r\theta)\le v q C ( r θ ) ≤ v r 2 ≥ ( 2 / β ) log ( c C , θ / v ) r^2\ge(2/\beta)\log(c_{C,\theta}/v) r 2 ≥ ( 2/ β ) log ( c C , θ / v ) v v v O C , θ ( v 1 / β ( log ( 1 / v ) ) ( d − 2 ) / 2 ) = o ( v ( log ( 1 / v ) ) d − 1 ) O_{C,\theta}(v^{1/\beta}(\log(1/v))^{(d-2)/2})=o(v(\log(1/v))^{d-1}) O C , θ ( v 1/ β ( log ( 1/ v ) ) ( d − 2 ) /2 ) = o ( v ( log ( 1/ v ) ) d − 1 )
To integrate these limits across all directions, restrict the integral in (40) to ( 1 + r ) − 1 ( C ∩ B ( 0 , 1 ) ) (1+r)^{-1}(C\cap B(0,1)) ( 1 + r ) − 1 ( C ∩ B ( 0 , 1 )) r ≥ 0 r\ge0 r ≥ 0
q C ( r θ ) ≥ c C e − r 2 / 2 ( 1 + r ) d , c C = ϕ ( 0 ) e − 3 / 2 vol ( C ∩ B ( 0 , 1 ) ) > 0. (43) q_C(r\theta)\ge c_C\frac{e^{-r^2/2}}{(1+r)^d},\qquad c_C=\phi(0)e^{-3/2}\operatorname{vol}(C\cap B(0,1))>0. \tag*{(43)} q C ( r θ ) ≥ c C ( 1 + r ) d e − r 2 /2 , c C = ϕ ( 0 ) e − 3/2 vol ( C ∩ B ( 0 , 1 )) > 0. (43) With this fixed c C c_C c C r v r_v r v c C e − r v 2 / 2 ( 1 + r v ) − d = v c_Ce^{-r_v^2/2}(1+r_v)^{-d}=v c C e − r v 2 /2 ( 1 + r v ) − d = v (43) is decreasing in r r r q C ( r θ ) ≤ v q_C(r\theta)\le v q C ( r θ ) ≤ v r ≥ r v r\ge r_v r ≥ r v θ \theta θ
r v 2 = 2 log ( 1 / v ) − d log log ( 1 / v ) + O C ( 1 ) . r_v^2=2\log(1/v)-d\log\log(1/v)+O_C(1). r v 2 = 2 log ( 1/ v ) − d log log ( 1/ v ) + O C ( 1 ) . Thus, uniformly over the sphere,
A v ( θ ) ≤ ϕ ( 0 ) ∫ r v ∞ e − r 2 / 2 r d − 1 d r ≤ O C ( v ( 1 + r v ) d r v d − 2 ) = O C ( v ( log ( 1 / v ) ) d − 1 ) . A_v(\theta)\le\phi(0)\int_{r_v}^\infty e^{-r^2/2}r^{d-1}\,dr\le O_C\bigl(v(1+r_v)^dr_v^{d-2}\bigr)=O_C\bigl(v(\log(1/v))^{d-1}\bigr). A v ( θ ) ≤ ϕ ( 0 ) ∫ r v ∞ e − r 2 /2 r d − 1 d r ≤ O C ( v ( 1 + r v ) d r v d − 2 ) = O C ( v ( log ( 1/ v ) ) d − 1 ) . This also holds for d = 1 d=1 d = 1 H ( v ) = ∫ S d − 1 A v ( θ ) d σ ( θ ) H(v)=\int_{S^{d-1}}A_v(\theta)\,d\sigma(\theta) H ( v ) = ∫ S d − 1 A v ( θ ) d σ ( θ ) (39) . The coefficient is finite by this same uniform bound and strictly positive because the dual cone has nonempty interior.
For a Gaussian distribution, write Z = A X Z=AX Z = A X Σ = A A T \Sigma=A A^{\mathsf T} Σ = A A T A A A d d d C = { x : A x ≥ 0 } C=\{x:Ax\ge0\} C = { x : A x ≥ 0 } (39) is a Σ a_{\Sigma} a Σ q C ( X ) = q F ( Z ) q_C(X)=q_F(Z) q C ( X ) = q F ( Z ) d d d Σ \Sigma Σ Z Z Z (39) instead.
For a compact P ⊂ int ( C ∗ ) ∩ S d − 1 P\subset\operatorname{int}(C^*)\cap S^{d-1} P ⊂ int ( C ∗ ) ∩ S d − 1
a P = 2 d − 1 ∫ P d σ ( θ ) J ( θ ) . a_P=2^{d-1}\int_P\frac{d\sigma(\theta)}{J(\theta)}. a P = 2 d − 1 ∫ P J ( θ ) d σ ( θ ) . Equation (42) gives the corresponding asymptotic restricted to directions in P P P P P P C ∗ C^* C ∗ a P a_P a P a Σ a_{\Sigma} a Σ
Corollary B.2. For Z ∼ N d ( μ , Σ ) Z\sim\mathcal{N}_d(\mu,\Sigma) Z ∼ N d ( μ , Σ ) Σ \Sigma Σ (24) holds with the coefficient in (25) . Equivalently,
a Σ = 2 d − 1 ( det Σ ) 1 / 2 ∫ θ ∈ S d − 1 Σ − 1 / 2 θ > 0 ∏ k = 1 d ( Σ − 1 / 2 θ ) ( k ) d σ ( θ ) . (44) a_{\Sigma}=2^{d-1}(\det\Sigma)^{1/2}\int_{\substack{\theta\in S^{d-1}\\\Sigma^{-1/2}\theta>0}}\prod_{k=1}^{d}(\Sigma^{-1/2}\theta)^{(k)}\,d\sigma(\theta). \tag*{(44)} a Σ = 2 d − 1 ( det Σ ) 1/2 ∫ θ ∈ S d − 1 Σ − 1/2 θ > 0 k = 1 ∏ d ( Σ − 1/2 θ ) ( k ) d σ ( θ ) . (44) Positive diagonal rescaling leaves this coefficient unchanged, and a I = 1 / ( d − 1 ) ! a_I=1/(d-1)! a I = 1/ ( d − 1 )! (26) gives the coefficient as a function of the correlation.
Proof. After translation, write Z = Σ 1 / 2 X Z=\Sigma^{1/2}X Z = Σ 1/2 X X ∼ N d ( 0 , I d ) X\sim\mathcal{N}_d(0,I_d) X ∼ N d ( 0 , I d ) z = Σ − 1 / 2 y z=\Sigma^{-1/2}y z = Σ − 1/2 y J J J
J ( θ ) = ( det Σ ) − 1 / 2 ∏ k = 1 d [ ( Σ − 1 / 2 θ ) ( k ) ] − 1 J(\theta)=(\det\Sigma)^{-1/2}\prod_{k=1}^{d}\left[(\Sigma^{-1/2}\theta)^{(k)}\right]^{-1} J ( θ ) = ( det Σ ) − 1/2 k = 1 ∏ d [ ( Σ − 1/2 θ ) ( k ) ] − 1 for directions inside the dual cone. This proves (44) . To obtain (25) , substitute z = Σ − 1 / 2 t θ z=\Sigma^{-1/2}t\theta z = Σ − 1/2 tθ t t t
∫ ( 0 , ∞ ) d ( ∏ k = 1 d z ( k ) ) e − z T Σ z / 2 d z = ( det Σ ) − 1 / 2 2 d − 1 ( d − 1 ) ! ∫ θ ∈ S d − 1 Σ − 1 / 2 θ > 0 ∏ k = 1 d ( Σ − 1 / 2 θ ) ( k ) d σ ( θ ) . \begin{aligned}
\int_{(0,\infty)^d}\left(\prod_{k=1}^{d}z^{(k)}\right)e^{-z^{\mathsf T}\Sigma z/2}\,dz \\
&=(\det\Sigma)^{-1/2}2^{d-1}(d-1)!\int_{\substack{\theta\in S^{d-1}\\\Sigma^{-1/2}\theta>0}}\prod_{k=1}^{d}(\Sigma^{-1/2}\theta)^{(k)}\,d\sigma(\theta).
\end{aligned} ∫ ( 0 , ∞ ) d ( k = 1 ∏ d z ( k ) ) e − z T Σ z /2 d z = ( det Σ ) − 1/2 2 d − 1 ( d − 1 )! ∫ θ ∈ S d − 1 Σ − 1/2 θ > 0 k = 1 ∏ d ( Σ − 1/2 θ ) ( k ) d σ ( θ ) . The radial integral is 2 d − 1 ( d − 1 ) ! 2^{d-1}(d-1)! 2 d − 1 ( d − 1 )! d d d Σ = I \Sigma=I Σ = I
For the bivariate formula, the geometry in Figure 6 can be obtained by writing Z = ( a 1 ⋅ X , a 2 ⋅ X ) Z=(a_1\cdot X,a_2\cdot X) Z = ( a 1 ⋅ X , a 2 ⋅ X ) a 1 = ( cos α , sin α ) a_1=(\cos\alpha,\sin\alpha) a 1 = ( cos α , sin α ) a 2 = ( cos α , − sin α ) a_2=(\cos\alpha,-\sin\alpha) a 2 = ( cos α , − sin α ) α = 1 2 arccos ρ \alpha=\frac{1}{2}\arccos\rho α = 2 1 arccos ρ { x : a 1 ⋅ x ≥ 0 , a 2 ⋅ x ≥ 0 } \{x:a_1\cdot x\ge0,\ a_2\cdot x\ge0\} { x : a 1 ⋅ x ≥ 0 , a 2 ⋅ x ≥ 0 } π − arccos ρ \pi-\arccos\rho π − arccos ρ arccos ρ \arccos\rho arccos ρ (25) , substitute z ( 2 ) = t z ( 1 ) z^{(2)}=tz^{(1)} z ( 2 ) = t z ( 1 ) z ( 1 ) z^{(1)} z ( 1 )
a ρ = 2 ( 1 − ρ 2 ) ∫ 0 ∞ t d t ( t 2 + 2 ρ t + 1 ) 2 . a_{\rho}=2(1-\rho^2)\int_0^\infty\frac{t\,dt}{(t^2+2\rho t+1)^2}. a ρ = 2 ( 1 − ρ 2 ) ∫ 0 ∞ ( t 2 + 2 ρt + 1 ) 2 t d t . Since
∫ 0 ∞ d t t 2 + 2 ρ t + 1 = arccos ρ 1 − ρ 2 , \int_0^\infty\frac{dt}{t^2+2\rho t+1}=\frac{\arccos\rho}{\sqrt{1-\rho^2}}, ∫ 0 ∞ t 2 + 2 ρt + 1 d t = 1 − ρ 2 arccos ρ , differentiating in ρ \rho ρ (26) . In particular, a 0 = 1 a_0=1 a 0 = 1 a ρ ∼ 2 3 ( 1 − ρ ) a_\rho\sim\frac{2}{3}(1-\rho) a ρ ∼ 3 2 ( 1 − ρ ) ρ ↑ 1 \rho\uparrow1 ρ ↑ 1 a ρ ∼ π 2 ( 1 + ρ ) a_\rho\sim\frac{\pi}{\sqrt{2(1+\rho)}} a ρ ∼ 2 ( 1 + ρ ) π ρ ↓ − 1 \rho\downarrow-1 ρ ↓ − 1
Domination by earlier observations
The next bound is used both to control the points excluded by the sample and to bound the variance of the probability left undominated. For the explicit cutoff, its constant must remain bounded while the set of directions expands towards the boundary of C ∗ C^* C ∗ n n n
P n = { θ ∈ S d − 1 : θ ⋅ z ≥ ∥ z ∥ log log n for every z ∈ C } . P_n=\left\{\theta\in S^{d-1}:\theta\cdot z\ge\frac{\lVert z\rVert}{\log\log n}\text{ for every }z\in C\right\}. P n = { θ ∈ S d − 1 : θ ⋅ z ≥ log log n ∥ z ∥ for every z ∈ C } . Every fixed compact subset of int ( C ∗ ) ∩ S d − 1 \operatorname{int}(C^*)\cap S^{d-1} int ( C ∗ ) ∩ S d − 1 P n P_n P n n n n
Lemma B.3. Fix d ≥ 2 d\ge2 d ≥ 2 C C C c C c_C c C n n n n − 1 ( log n ) − 22 d ≤ u ≤ n − 1 ( log n ) 2 n^{-1}(\log n)^{-22d}\le u\le n^{-1}(\log n)^2 n − 1 ( log n ) − 22 d ≤ u ≤ n − 1 ( log n ) 2 ∥ x i ∥ ≤ 2 log n + 40 d log log n \lVert x_i\rVert\le\sqrt{2\log n+40d\log\log n} ∥ x i ∥ ≤ 2 log n + 40 d log log n
P { q C ( X ) ≤ u , X / ∥ X ∥ ∈ P n , x i − X ∈ C } ≤ c C u 1 { q C ( x i ) ≤ u } ( 1 + log u q C ( x i ) ) d . (45) \mathbb{P}\left\{q_C(X)\le u,\ X/\lVert X\rVert\in P_n,\ x_i-X\in C\right\}
\le c_Cu\mathbf{1}\{q_C(x_i)\le u\}\left(1+\log\frac{u}{q_C(x_i)}\right)^d. \tag*{(45)} P { q C ( X ) ≤ u , X / ∥ X ∥ ∈ P n , x i − X ∈ C } ≤ c C u 1 { q C ( x i ) ≤ u } ( 1 + log q C ( x i ) u ) d . (45) The right side is defined to be zero when q C ( x i ) > u q_C(x_i)>u q C ( x i ) > u
Proof. We first make (41) quantitative. If θ ⋅ z ≥ δ ∥ z ∥ \theta\cdot z\ge\delta\lVert z\rVert θ ⋅ z ≥ δ ∥ z ∥ z ∈ C z\in C z ∈ C 1 − e − ∥ z ∥ 2 / ( 2 t 2 ) ≤ ∥ z ∥ 2 / ( 2 t 2 ) 1-e^{-\lVert z\rVert^2/(2t^2)}\le\lVert z\rVert^2/(2t^2) 1 − e − ∥ z ∥ 2 / ( 2 t 2 ) ≤ ∥ z ∥ 2 / ( 2 t 2 )
0 ≤ 1 − q C ( t θ ) ϕ ( t θ ) J ( t θ ) ≤ 1 2 t 2 δ 2 J ( θ ) ∫ C ( θ ⋅ z ) 2 e − θ ⋅ z d z = d ( d + 1 ) 2 t 2 δ 2 . (46) 0\le1-\frac{q_C(t\theta)}{\phi(t\theta)J(t\theta)}
\le\frac{1}{2t^2\delta^2J(\theta)}\int_C(\theta\cdot z)^2e^{-\theta\cdot z}\,dz
=\frac{d(d+1)}{2t^2\delta^2}. \tag*{(46)} 0 ≤ 1 − ϕ ( tθ ) J ( tθ ) q C ( tθ ) ≤ 2 t 2 δ 2 J ( θ ) 1 ∫ C ( θ ⋅ z ) 2 e − θ ⋅ z d z = 2 t 2 δ 2 d ( d + 1 ) . (46) The equality follows by differentiating J ( a θ ) = a − d J ( θ ) J(a\theta)=a^{-d}J(\theta) J ( a θ ) = a − d J ( θ ) a a a a = 1 a=1 a = 1
Now take δ = 1 / log log n \delta=1/\log\log n δ = 1/ log log n (45) has the form x = t θ x=t\theta x = tθ θ ∈ P n \theta\in P_n θ ∈ P n y = x i − x ∈ C y=x_i-x\in C y = x i − x ∈ C r = ∥ x i ∥ r=\lVert x_i\rVert r = ∥ x i ∥ (43) and q C ( x ) ≤ u q_C(x)\le u q C ( x ) ≤ u t 2 ≥ 2 log n − O C ( log log n ) t^2\ge2\log n-O_C(\log\log n) t 2 ≥ 2 log n − O C ( log log n )
r 2 − t 2 = 2 t θ ⋅ y + ∥ y ∥ 2 ≥ 2 δ t ∥ y ∥ . r^2-t^2=2t\theta\cdot y+\lVert y\rVert^2\ge2\delta t\lVert y\rVert. r 2 − t 2 = 2 tθ ⋅ y + ∥ y ∥ 2 ≥ 2 δ t ∥ y ∥ . Consequently t ≤ r t\le r t ≤ r
∥ y ∥ = O C ( ( log log n ) 2 log n ) , ∥ x i r − θ ∥ = O C ( ( log log n ) 2 log n ) = o ( δ ) . \lVert y\rVert=O_C\left(\frac{(\log\log n)^2}{\sqrt{\log n}}\right),\qquad
\left\lVert\frac{x_i}{r}-\theta\right\rVert=O_C\left(\frac{(\log\log n)^2}{\log n}\right)=o(\delta). ∥ y ∥ = O C ( log n ( log log n ) 2 ) , r x i − θ = O C ( log n ( log log n ) 2 ) = o ( δ ) . Thus the direction x i / r x_i/r x i / r δ / 2 \delta/2 δ /2 (46) applies to both x x x x i x_i x i z ∈ C z\in C z ∈ C
∣ y ⋅ z ∣ ≤ 2 ∥ y ∥ r δ x i ⋅ z = O C ( ( log log n ) 3 log n ) x i ⋅ z . \lvert y\cdot z\rvert\le\frac{2\lVert y\rVert}{r\delta}x_i\cdot z
=O_C\left(\frac{(\log\log n)^3}{\log n}\right)x_i\cdot z. ∣ y ⋅ z ∣ ≤ r δ 2 ∥ y ∥ x i ⋅ z = O C ( log n ( log log n ) 3 ) x i ⋅ z . Since x = x i − y x=x_i-y x = x i − y x i ⋅ z x_i\cdot z x i ⋅ z J J J
J ( x ) J ( x i ) = 1 + O C ( ( log log n ) 3 log n ) . \frac{J(x)}{J(x_i)}=1+O_C\left(\frac{(\log\log n)^3}{\log n}\right). J ( x i ) J ( x ) = 1 + O C ( log n ( log log n ) 3 ) . Combining this with (46) yields
q C ( x ) q C ( x i ) = e ( r 2 − t 2 ) / 2 [ 1 + O C ( ( log log n ) 3 log n ) ] . \frac{q_C(x)}{q_C(x_i)}
=e^{(r^2-t^2)/2}\left[1+O_C\left(\frac{(\log\log n)^3}{\log n}\right)\right]. q C ( x i ) q C ( x ) = e ( r 2 − t 2 ) /2 [ 1 + O C ( log n ( log log n ) 3 ) ] . The inclusion x i + C ⊆ x + C x_i+C\subseteq x+C x i + C ⊆ x + C q C ( x i ) ≤ q C ( x ) ≤ u q_C(x_i)\le q_C(x)\le u q C ( x i ) ≤ q C ( x ) ≤ u ∥ y ∥ 2 = o ( 1 ) \lVert y\rVert^2=o(1) ∥ y ∥ 2 = o ( 1 )
x i ⋅ y = r 2 − t 2 + ∥ y ∥ 2 2 ≤ log u q C ( x i ) + o ( 1 ) . x_i\cdot y=\frac{r^2-t^2+\lVert y\rVert^2}{2}\le\log\frac{u}{q_C(x_i)}+o(1). x i ⋅ y = 2 r 2 − t 2 + ∥ y ∥ 2 ≤ log q C ( x i ) u + o ( 1 ) . All error bounds above hold for every point being counted, with constants independent of that point.
For all sufficiently large n n n y ∈ C y\in C y ∈ C x i ⋅ y ≤ 1 + log ( u / q C ( x i ) ) x_i\cdot y\le1+\log(u/q_C(x_i)) x i ⋅ y ≤ 1 + log ( u / q C ( x i ))
vol { y ∈ C : x i ⋅ y ≤ t } = J ( x i ) t d d ! , t ≥ 0. \operatorname{vol}\{y\in C:x_i\cdot y\le t\}=\frac{J(x_i)t^d}{d!},\qquad t\ge0. vol { y ∈ C : x i ⋅ y ≤ t } = d ! J ( x i ) t d , t ≥ 0. Using ϕ ( x i − y ) ≤ ϕ ( x i ) e x i ⋅ y \phi(x_i-y)\le\phi(x_i)e^{x_i\cdot y} ϕ ( x i − y ) ≤ ϕ ( x i ) e x i ⋅ y
P { q C ( X ) ≤ u , X / ∥ X ∥ ∈ P n , x i − X ∈ C } ≤ ϕ ( x i ) J ( x i ) ( d − 1 ) ! ∫ 0 1 + log ( u / q C ( x i ) ) e t t d − 1 d t ≤ c C u ( 1 + log u q C ( x i ) ) d . \begin{aligned}
\mathbb{P}\{q_C(X)\le u,\ X/\lVert X\rVert\in P_n,\ x_i-X\in C\} \\
&\le\frac{\phi(x_i)J(x_i)}{(d-1)!}\int_0^{1+\log(u/q_C(x_i))}e^t t^{d-1}\,dt \\
&\le c_Cu\left(1+\log\frac{u}{q_C(x_i)}\right)^d.
\end{aligned} P { q C ( X ) ≤ u , X / ∥ X ∥ ∈ P n , x i − X ∈ C } ≤ ( d − 1 )! ϕ ( x i ) J ( x i ) ∫ 0 1 + l o g ( u / q C ( x i )) e t t d − 1 d t ≤ c C u ( 1 + log q C ( x i ) u ) d . The last inequality uses (46) ; if there is no point to count, the bound is immediate.
Moments and sample bounds
Lemma B.4. Let C = { x : A x ≥ 0 } ⊂ R d C=\{x:Ax\ge0\}\subset\mathbb{R}^d C = { x : A x ≥ 0 } ⊂ R d Σ = A A T \Sigma=A A^{\mathsf T} Σ = A A T d ≥ 2 d\ge2 d ≥ 2 X ∼ N d ( 0 , I d ) X\sim\mathcal{N}_d(0,I_d) X ∼ N d ( 0 , I d ) P ⊂ int ( C ∗ ) ∩ S d − 1 P\subset\operatorname{int}(C^*)\cap S^{d-1} P ⊂ int ( C ∗ ) ∩ S d − 1 n − 1 ( log n ) − 2 ( d − 1 ) ≤ u ≤ n − 1 n^{-1}(\log n)^{-2(d-1)}\le u\le n^{-1} n − 1 ( log n ) − 2 ( d − 1 ) ≤ u ≤ n − 1
P { q C ( X ) ≤ u , X / ∥ X ∥ ∈ P } = ( a P + o ( 1 ) ) u ( log n ) d − 1 , \mathbb{P}\{q_C(X)\le u,\ X/\lVert X\rVert\in P\}=(a_P+o(1))u(\log n)^{d-1}, P { q C ( X ) ≤ u , X / ∥ X ∥ ∈ P } = ( a P + o ( 1 )) u ( log n ) d − 1 , E [ q C ( X ) 1 { q C ( X ) ≤ u } ] = ( a Σ / 2 + o ( 1 ) ) u 2 ( log n ) d − 1 . (47) \mathbb{E}\left[q_C(X)\mathbf{1}\{q_C(X)\le u\}\right]=(a_\Sigma/2+o(1))u^2(\log n)^{d-1}. \tag*{(47)} E [ q C ( X ) 1 { q C ( X ) ≤ u } ] = ( a Σ /2 + o ( 1 )) u 2 ( log n ) d − 1 . (47) The errors tend to zero independently of u u u n → ∞ n\to\infty n → ∞
E [ ( 1 − q C ( X ) ) n − 1 ] ∼ a Σ ( log n ) d − 1 n . (48) \mathbb{E}\left[(1-q_C(X))^{n-1}\right]\sim\frac{a_\Sigma(\log n)^{d-1}}{n}. \tag*{(48)} E [ ( 1 − q C ( X ) ) n − 1 ] ∼ n a Σ ( log n ) d − 1 . (48) The exponential and weighted exponential bounds follow from (36) and (50) . Among n n n o ( ( ( log n ) d − 1 log log n ) − 1 ) o(((\log n)^{d-1}\log\log n)^{-1}) o ((( log n ) d − 1 log log n ) − 1 )
max i ≤ n ∥ X i ∥ ≤ 2 log n + 40 d log log n , \max_{i\le n}\lVert X_i\rVert\le\sqrt{2\log n}+40d\log\log n, i ≤ n max ∥ X i ∥ ≤ 2 log n + 40 d log log n , # { i ≤ n : q C ( X i ) ≤ n − 1 e − log log n / 3 } ≤ ⌈ ( log n ) d − 1 e − log log n / 4 ⌉ . (49) \#\{i\le n:q_C(X_i)\le n^{-1}e^{-\sqrt{\log\log n}/3}\}\le\left\lceil(\log n)^{d-1}e^{-\sqrt{\log\log n}/4}\right\rceil. \tag*{(49)} # { i ≤ n : q C ( X i ) ≤ n − 1 e − l o g l o g n /3 } ≤ ⌈ ( log n ) d − 1 e − l o g l o g n /4 ⌉ . (49) Proof. Theorem B.1 and its restriction to P P P H ( u ) ∼ a Σ u ( log ( 1 / u ) ) d − 1 H(u)\sim a_\Sigma u(\log(1/u))^{d-1} H ( u ) ∼ a Σ u ( log ( 1/ u ) ) d − 1 a P a_P a P P P P
H ( u ) = O C ( u ( 1 + log ( 1 / u ) ) d − 1 ) , 0 < u ≤ 1. (50) H(u)=O_C\left(u(1+\log(1/u))^{d-1}\right),\qquad0<u\le1. \tag*{(50)} H ( u ) = O C ( u ( 1 + log ( 1/ u ) ) d − 1 ) , 0 < u ≤ 1. (50) The moment assertions now follow from (36) and log ( 1 / u ) = log n + O ( log log n ) \log(1/u)=\log n+O(\log\log n) log ( 1/ u ) = log n + O ( log log n )
Sample bounds. The Gaussian radial tail is P { ∥ X ∥ > t } = O d ( t d − 2 e − t 2 / 2 ) \mathbb{P}\{\lVert X\rVert>t\}=O_d(t^{d-2}e^{-t^2/2}) P {∥ X ∥ > t } = O d ( t d − 2 e − t 2 /2 ) t → ∞ t\to\infty t → ∞ (49) gives O d ( ( log n ) ( d − 2 ) / 2 − 20 d ) O_d((\log n)^{(d-2)/2-20d}) O d (( log n ) ( d − 2 ) /2 − 20 d )
O C ( ( log n ) d − 1 e − log log n / 3 ) . O_C\left((\log n)^{d-1}e^{-\sqrt{\log\log n}/3}\right). O C ( ( log n ) d − 1 e − l o g l o g n /3 ) . Applying (65) at the upper bound on the count in (49) gives error o ( ( ( log n ) d − 1 log log n ) − 1 ) o(((\log n)^{d-1}\log\log n)^{-1}) o ((( log n ) d − 1 log log n ) − 1 )
Lemma B.5. Fix d ≥ 2 d\ge2 d ≥ 2 C C C P ⊂ int ( C ∗ ) ∩ S d − 1 P\subset\operatorname{int}(C^*)\cap S^{d-1} P ⊂ int ( C ∗ ) ∩ S d − 1 (49) . The probability of any such history is o ( ( ( log n ) d − 1 log log n ) − 1 ) o(((\log n)^{d-1}\log\log n)^{-1}) o ((( log n ) d − 1 log log n ) − 1 ) s ≤ n s\le n s ≤ n
1 n ( log n ) 2 ( d − 1 ) ≤ u ≤ e − log log n / 3 n , (51) \frac{1}{n(\log n)^{2(d-1)}}\le u\le\frac{e^{-\sqrt{\log\log n}/3}}{n}, \tag*{(51)} n ( log n ) 2 ( d − 1 ) 1 ≤ u ≤ n e − l o g l o g n /3 , (51) we have, using H s − 1 \mathcal{H}_{s-1} H s − 1 § 2 with X i X_i X i Z i Z_i Z i
P { q C ( X s ) ≤ u , X s / ∥ X s ∥ ∈ P , ∃ i < s : X s ≺ C X i ∣ H s − 1 } = o ( u ( log n ) d − 1 ) . (52) \mathbb{P}\{q_C(X_s)\le u,\ X_s/\lVert X_s\rVert\in P,\ \exists i<s:X_s\prec_C X_i\mid\mathcal{H}_{s-1}\}=o(u(\log n)^{d-1}). \tag*{(52)} P { q C ( X s ) ≤ u , X s / ∥ X s ∥ ∈ P , ∃ i < s : X s ≺ C X i ∣ H s − 1 } = o ( u ( log n ) d − 1 ) . (52) The error is uniform in s s s u u u
Proof. The norm bound and (43) imply q C ( X i ) ≥ n − 1 ( log n ) − c C q_C(X_i)\ge n^{-1}(\log n)^{-c_C} q C ( X i ) ≥ n − 1 ( log n ) − c C c C c_C c C P ⊆ P n P\subseteq P_n P ⊆ P n n n n (45) is O C ( log log n ) O_C(\log\log n) O C ( log log n ) (49) gives
P { q C ( X s ) ≤ u , X s / ∥ X s ∥ ∈ P , ∃ i < s : X s ≺ C X i ∣ H s − 1 } ≤ c C u ( log log n ) d [ ( log n ) d − 1 e − log log n / 4 ] = o ( u ( log n ) d − 1 ) . \begin{aligned}
\mathbb{P}\{q_C(X_s)\le u,\ X_s/\lVert X_s\rVert\in P,\ \exists i<s:X_s\prec_C X_i\mid\mathcal{H}_{s-1}\}
&\le c_Cu(\log\log n)^d\left[(\log n)^{d-1}e^{-\sqrt{\log\log n}/4}\right] \\
&=o(u(\log n)^{d-1}).
\end{aligned} P { q C ( X s ) ≤ u , X s / ∥ X s ∥ ∈ P , ∃ i < s : X s ≺ C X i ∣ H s − 1 } ≤ c C u ( log log n ) d [ ( log n ) d − 1 e − l o g l o g n /4 ] = o ( u ( log n ) d − 1 ) . The exceptional probability and its dependence only on observations already seen follow from Lemma B.4 .
Cutoff estimates
Lemma B.6. Let C = { x : A x ≥ 0 } C=\{x:Ax\ge0\} C = { x : A x ≥ 0 } Σ = A A T \Sigma=AA^{\mathsf{T}} Σ = A A T d ≥ 2 d\ge2 d ≥ 2 s s s U s = { x : ∄ i ≤ s with x ≺ C X i } U_s=\{x:\nexists i\le s\text{ with }x\prec_C X_i\} U s = { x : ∄ i ≤ s with x ≺ C X i } A s = γ ( U s ) A_s=\gamma(U_s) A s = γ ( U s ) s → ∞ s\to\infty s → ∞
E [ A s ] ∼ a Σ ( log s ) d − 1 s , E [ ∫ U s q C ( x ) d γ ( x ) ] ∼ a Σ ( log s ) d − 1 s 2 . (53) \mathbb{E}[A_s]\sim\frac{a_\Sigma(\log s)^{d-1}}{s},\qquad
\mathbb{E}\left[\int_{U_s}q_C(x)\,d\gamma(x)\right]\sim\frac{a_\Sigma(\log s)^{d-1}}{s^2}. \tag*{(53)} E [ A s ] ∼ s a Σ ( log s ) d − 1 , E [ ∫ U s q C ( x ) d γ ( x ) ] ∼ s 2 a Σ ( log s ) d − 1 . (53) If m a Σ ( log s ) d − 1 / s = ( d − 1 ) log log s + O ( 1 ) ma_\Sigma(\log s)^{d-1}/s=(d-1)\log\log s+O(1) m a Σ ( log s ) d − 1 / s = ( d − 1 ) log log s + O ( 1 )
E [ ( 1 − A s ) m ] = O C ( ( log s ) 1 − d ) . (54) \mathbb{E}[(1-A_s)^m]=O_C((\log s)^{1-d}). \tag*{(54)} E [( 1 − A s ) m ] = O C (( log s ) 1 − d ) . (54) For every fixed ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 )
P { A s < ( 1 − ϵ ) E [ A s ] } = O C , ϵ ( ( log s ) 1 − d ) , A s E [ A s ] ⟶ 1 in L 1 . (55) \mathbb{P}\{A_s<(1-\epsilon)\mathbb{E}[A_s]\}=O_{C,\epsilon}((\log s)^{1-d}),\qquad
\frac{A_s}{\mathbb{E}[A_s]}\longrightarrow1\text{ in }L^1. \tag*{(55)} P { A s < ( 1 − ϵ ) E [ A s ]} = O C , ϵ (( log s ) 1 − d ) , E [ A s ] A s ⟶ 1 in L 1 . (55) Moreover,
E [ 1 A s 2 ∫ U s q C ( x ) d γ ( x ) ] = O C ( ( log s ) 1 − d ) , (56) \mathbb{E}\left[\frac{1}{A_s^2}\int_{U_s}q_C(x)\,d\gamma(x)\right]=O_C((\log s)^{1-d}), \tag*{(56)} E [ A s 2 1 ∫ U s q C ( x ) d γ ( x ) ] = O C (( log s ) 1 − d ) , (56) and, for each fixed T > 0 T>0 T > 0
s E [ 1 A s ∫ U s q C ( x ) 1 { q C ( x ) ≤ T / s } d γ ( x ) ] ⟶ ∫ 0 T t e − t d t . s\mathbb{E}\left[\frac{1}{A_s}\int_{U_s}q_C(x)1\{q_C(x)\le T/s\}\,d\gamma(x)\right]\longrightarrow\int_0^Tte^{-t}\,dt. s E [ A s 1 ∫ U s q C ( x ) 1 { q C ( x ) ≤ T / s } d γ ( x ) ] ⟶ ∫ 0 T t e − t d t . Changing coordinates gives the same estimates for a fixed positive definite Gaussian correlation matrix, with F F F q F q_F q F γ \gamma γ q C q_C q C U s U_s U s a Σ a_\Sigma a Σ
Proof. We estimate the mean and variance of the probability left in directions P s P_s P s A s A_s A s A s A_s A s
Means. Conditioning on an independent X X X
E [ ∫ U s q C ( x ) k d γ ( x ) ] = ∫ 0 1 v k ( 1 − v ) s d H ( v ) , k = 0 , 1. \mathbb{E}\left[\int_{U_s}q_C(x)^k\,d\gamma(x)\right]=\int_0^1v^k(1-v)^s\,dH(v),\qquad k=0,1. E [ ∫ U s q C ( x ) k d γ ( x ) ] = ∫ 0 1 v k ( 1 − v ) s d H ( v ) , k = 0 , 1. Apply (37) with T = ∞ T=\infty T = ∞ H ( 1 / s ) ∼ a Σ ( log s ) d − 1 / s H(1/s)\sim a_\Sigma(\log s)^{d-1}/s H ( 1/ s ) ∼ a Σ ( log s ) d − 1 / s (53) . For fixed T > 0 T>0 T > 0
E [ ∫ U s q C ( x ) 1 { q C ( x ) ≤ T / s } d γ ( x ) ] ∼ a Σ ( log s ) d − 1 s 2 ∫ 0 T t e − t d t . (57) \mathbb{E}\left[\int_{U_s}q_C(x)1\{q_C(x)\le T/s\}\,d\gamma(x)\right]\sim\frac{a_\Sigma(\log s)^{d-1}}{s^2}\int_0^Tte^{-t}\,dt. \tag*{(57)} E [ ∫ U s q C ( x ) 1 { q C ( x ) ≤ T / s } d γ ( x ) ] ∼ s 2 a Σ ( log s ) d − 1 ∫ 0 T t e − t d t . (57) Uniform mean bound. Put δ = 1 / log log s \delta=1/\log\log s δ = 1/ log log s u = ( log s ) 2 / s u=(\log s)^2/s u = ( log s ) 2 / s
V = ∫ U s 1 { x / ∥ x ∥ ∈ P s , q C ( x ) ≤ u } d γ ( x ) . V=\int_{U_s}1\{x/\lVert x\rVert\in P_s,\ q_C(x)\le u\}\,d\gamma(x). V = ∫ U s 1 { x / ∥ x ∥ ∈ P s , q C ( x ) ≤ u } d γ ( x ) . We use V ≤ A s V\le A_s V ≤ A s
0 ≤ a Σ − a P s = O C ( δ ) . (58) 0\le a_\Sigma-a_{P_s}=O_C(\delta). \tag*{(58)} 0 ≤ a Σ − a P s = O C ( δ ) . (58) To see this, choose a unit vector e ∈ int ( C ∗ ) e\in\operatorname{int}(C^*) e ∈ int ( C ∗ ) b > 0 b>0 b > 0 e ⋅ z ≥ b ∥ z ∥ e\cdot z\ge b\lVert z\rVert e ⋅ z ≥ b ∥ z ∥ C C C h = 2 δ / b h=2\delta/b h = 2 δ / b θ ↦ ( θ + h e ) / ∥ θ + h e ∥ \theta\mapsto(\theta+he)/\lVert\theta+he\rVert θ ↦ ( θ + h e ) / ∥ θ + h e ∥ C ∗ ∩ S d − 1 C^*\cap S^{d-1} C ∗ ∩ S d − 1 P s P_s P s s s s h < 1 h<1 h < 1 ( 1 + h θ ⋅ e ) / ∥ θ + h e ∥ d = 1 + O C ( δ ) (1+h\theta\cdot e)/\lVert\theta+he\rVert^d=1+O_C(\delta) ( 1 + h θ ⋅ e ) / ∥ θ + h e ∥ d = 1 + O C ( δ ) P s P_s P s O C ( δ ) O_C(\delta) O C ( δ ) 1 / J ( θ ) 1/J(\theta) 1/ J ( θ ) J ( θ ) ≥ e − 1 vol ( C ∩ B ( 0 , 1 ) ) J(\theta)\ge e^{-1}\operatorname{vol}(C\cap B(0,1)) J ( θ ) ≥ e − 1 vol ( C ∩ B ( 0 , 1 )) θ ∈ C ∗ \theta\in C^* θ ∈ C ∗ (58) .
We next quantify the radial calculation used in (42) . For θ ∈ P s \theta\in P_s θ ∈ P s
0 < e − 1 vol ( C ∩ B ( 0 , 1 ) ) ≤ J ( θ ) ≤ O d ( δ − d ) . 0<e^{-1}\operatorname{vol}(C\cap B(0,1))\le J(\theta)\le O_d(\delta^{-d}). 0 < e − 1 vol ( C ∩ B ( 0 , 1 )) ≤ J ( θ ) ≤ O d ( δ − d ) . The upper bound follows by integrating e − δ ∥ z ∥ e^{-\delta\lVert z\rVert} e − δ ∥ z ∥ R d \mathbb{R}^d R d t v ( θ ) t_v(\theta) t v ( θ ) q C ( t v θ ) = v q_C(t_v\theta)=v q C ( t v θ ) = v q C ( t θ ) q_C(t\theta) q C ( tθ ) s − 1 ( log s ) − 22 d ≤ v ≤ s − 1 ( log s ) 2 s^{-1}(\log s)^{-22d}\le v\le s^{-1}(\log s)^2 s − 1 ( log s ) − 22 d ≤ v ≤ s − 1 ( log s ) 2 (46) gives
t v ( θ ) 2 = 2 log s + O C ( log log s ) . t_v(\theta)^2=2\log s+O_C(\log\log s). t v ( θ ) 2 = 2 log s + O C ( log log s ) . The Gaussian radial tail and the same relative error bound then give
ϕ ( 0 ) ∫ t v ( θ ) ∞ e − t 2 / 2 t d − 1 d t = v t v ( θ ) 2 d − 2 J ( θ ) [ 1 + O C ( ( log log s ) 2 log s ) ] = 2 d − 1 v ( log s ) d − 1 J ( θ ) [ 1 + O C ( ( log log s ) 2 log s ) ] . (59) \begin{aligned}
\phi(0)\int_{t_v(\theta)}^\infty e^{-t^2/2}t^{d-1}\,dt
&=\frac{v\,t_v(\theta)^{2d-2}}{J(\theta)}
\left[1+O_C\left(\frac{(\log\log s)^2}{\log s}\right)\right]\\
&=\frac{2^{d-1}v(\log s)^{d-1}}{J(\theta)}
\left[1+O_C\left(\frac{(\log\log s)^2}{\log s}\right)\right]. \tag*{(59)}
\end{aligned} ϕ ( 0 ) ∫ t v ( θ ) ∞ e − t 2 /2 t d − 1 d t = J ( θ ) v t v ( θ ) 2 d − 2 [ 1 + O C ( log s ( log log s ) 2 ) ] = J ( θ ) 2 d − 1 v ( log s ) d − 1 [ 1 + O C ( log s ( log log s ) 2 ) ] . (59) Integrating over P s P_s P s
E [ V ] = ( 1 − u ) s P { q C ( X ) ≤ u , X / ∥ X ∥ ∈ P s } + s ∫ 0 u ( 1 − v ) s − 1 P { q C ( X ) ≤ v , X / ∥ X ∥ ∈ P s } d v = a P s ( log s ) d − 1 s [ 1 + O C ( ( log log s ) 2 log s ) ] = a Σ ( log s ) d − 1 s [ 1 + O C ( 1 log log s ) ] . (60) \begin{aligned}
\mathbb{E}[V]=(1-u)^s\mathbb{P}\{q_C(X)\le u,\ X/\lVert X\rVert\in P_s\}
+s\int_0^u(1-v)^{s-1}\mathbb{P}\{q_C(X)\le v,\ X/\lVert X\rVert\in P_s\}\,dv \\
&=\frac{a_{P_s}(\log s)^{d-1}}{s}\left[1+O_C\left(\frac{(\log\log s)^2}{\log s}\right)\right] \\
&=\frac{a_\Sigma(\log s)^{d-1}}{s}\left[1+O_C\left(\frac{1}{\log\log s}\right)\right]. \tag*{(60)}
\end{aligned} E [ V ] = ( 1 − u ) s P { q C ( X ) ≤ u , X / ∥ X ∥ ∈ P s } + s ∫ 0 u ( 1 − v ) s − 1 P { q C ( X ) ≤ v , X / ∥ X ∥ ∈ P s } d v = s a P s ( log s ) d − 1 [ 1 + O C ( log s ( log log s ) 2 ) ] = s a Σ ( log s ) d − 1 [ 1 + O C ( log log s 1 ) ] . (60) The second equality uses (59) , whose error holds throughout P s P_s P s v v v e − ( log s ) 2 e^{-(\log s)^2} e − ( l o g s ) 2 (50) bounds the contribution below s − 1 ( log s ) − 22 d s^{-1}(\log s)^{-22d} s − 1 ( log s ) − 22 d (58) .
Variance. Let V ( − i ) V^{(-i)} V ( − i ) X i X_i X i P s P_s P s u u u X i X_i X i E [ ( V ( − i ) − V ) 2 ] \mathbb{E}\left[(V^{(-i)}-V)^2\right] E [ ( V ( − i ) − V ) 2 ] X i = x i X_i=x_i X i = x i
g x i ( v ) = P { X / ∥ X ∥ ∈ P s , q C ( X ) ≤ v , x i − X ∈ C } . g_{x_i}(v)=\mathbb{P}\{X/\lVert X\rVert\in P_s,\ q_C(X)\le v,\ x_i-X\in C\}. g x i ( v ) = P { X / ∥ X ∥ ∈ P s , q C ( X ) ≤ v , x i − X ∈ C } . Two points x , x ′ x,x' x , x ′ V ( − i ) − V V^{(-i)}-V V ( − i ) − V s − 1 s-1 s − 1 max { q C ( x ) , q C ( x ′ ) } \max\{q_C(x),q_C(x')\} max { q C ( x ) , q C ( x ′ )} e − ( s − 1 ) max { q C ( x ) , q C ( x ′ ) } e^{-(s-1)\max\{q_C(x),q_C(x')\}} e − ( s − 1 ) m a x { q C ( x ) , q C ( x ′ )}
E [ ( V ( − i ) − V ) 2 ∣ X i = x i ] ≤ e − ( s − 1 ) u g x i ( u ) 2 + ( s − 1 ) ∫ 0 u e − ( s − 1 ) v g x i ( v ) 2 d v . (61) \mathbb{E}\left[(V^{(-i)}-V)^2\mid X_i=x_i\right]
\le e^{-(s-1)u}g_{x_i}(u)^2
+(s-1)\int_0^u e^{-(s-1)v}g_{x_i}(v)^2\,dv. \tag*{(61)} E [ ( V ( − i ) − V ) 2 ∣ X i = x i ] ≤ e − ( s − 1 ) u g x i ( u ) 2 + ( s − 1 ) ∫ 0 u e − ( s − 1 ) v g x i ( v ) 2 d v . (61) Here we integrate by parts against the distribution g x i ( v ) 2 g_{x_i}(v)^2 g x i ( v ) 2 q C q_C q C
Suppose ∥ x i ∥ ≤ 2 log s + 40 d log log s \lVert x_i\rVert\le\sqrt{2\log s+40d\log\log s} ∥ x i ∥ ≤ 2 log s + 40 d log log s s − 1 ( log s ) − 22 d ≤ v ≤ u s^{-1}(\log s)^{-22d}\le v\le u s − 1 ( log s ) − 22 d ≤ v ≤ u
g x i ( v ) ≤ c C v 1 { q C ( x i ) ≤ v } ( 1 + log ( v / q C ( x i ) ) ) d . g_{x_i}(v)\le c_Cv\,\mathbf{1}\{q_C(x_i)\le v\}(1+\log(v/q_C(x_i)))^d. g x i ( v ) ≤ c C v 1 { q C ( x i ) ≤ v } ( 1 + log ( v / q C ( x i )) ) d . For smaller v v v (43) give q C ( x i ) ≥ c C s − 1 ( log s ) − 20 d − d / 2 > s − 1 ( log s ) − 22 d q_C(x_i)\ge c_Cs^{-1}(\log s)^{-20d-d/2}>s^{-1}(\log s)^{-22d} q C ( x i ) ≥ c C s − 1 ( log s ) − 20 d − d /2 > s − 1 ( log s ) − 22 d s s s x i − X ∈ C x_i-X\in C x i − X ∈ C q C ( x i ) ≤ q C ( X ) q_C(x_i)\le q_C(X) q C ( x i ) ≤ q C ( X ) k ≥ 1 k\ge1 k ≥ 1
E [ 1 { q C ( X ) ≤ v } ( 1 + log ( v / q C ( X ) ) ) k ] = H ( v ) + k ∫ 0 ∞ ( 1 + t ) k − 1 H ( v e − t ) d t ≤ c C , k v ( 1 + log ( 1 / v ) ) d − 1 . \mathbb{E}\left[\mathbf{1}\{q_C(X)\le v\}(1+\log(v/q_C(X)))^k\right]
=H(v)+k\int_0^\infty(1+t)^{k-1}H(ve^{-t})\,dt
\le c_{C,k}v(1+\log(1/v))^{d-1}. E [ 1 { q C ( X ) ≤ v } ( 1 + log ( v / q C ( X )) ) k ] = H ( v ) + k ∫ 0 ∞ ( 1 + t ) k − 1 H ( v e − t ) d t ≤ c C , k v ( 1 + log ( 1/ v ) ) d − 1 . By (50) the integral is finite. Taking k = 2 d k=2d k = 2 d
E [ g X i ( v ) 2 1 { ∥ X i ∥ ≤ 2 log s + 40 d log log s } ] ≤ c C v 3 ( log s ) d − 1 , 0 < v ≤ u . \mathbb{E}\left[g_{X_i}(v)^2\mathbf{1}\{\lVert X_i\rVert\le\sqrt{2\log s+40d\log\log s}\}\right]
\le c_Cv^3(\log s)^{d-1},\qquad0<v\le u. E [ g X i ( v ) 2 1 {∥ X i ∥ ≤ 2 log s + 40 d log log s } ] ≤ c C v 3 ( log s ) d − 1 , 0 < v ≤ u . Substitution into (61) bounds each term by O C ( ( log s ) d − 1 / s 3 ) O_C((\log s)^{d-1}/s^3) O C (( log s ) d − 1 / s 3 ) V ( − i ) − V ≤ H ( u ) = O C ( ( log s ) d + 1 / s ) V^{(-i)}-V \le H(u)=O_C((\log s)^{d+1}/s) V ( − i ) − V ≤ H ( u ) = O C (( log s ) d + 1 / s ) Lemma B.4 , with n = s n=s n = s O d ( s − 1 ( log s ) ( d − 2 ) / 2 − 20 d ) O_d(s^{-1}(\log s)^{(d-2)/2-20d}) O d ( s − 1 ( log s ) ( d − 2 ) /2 − 20 d ) o ( ( log s ) d − 1 / s 2 ) o((\log s)^{d-1}/s^2) o (( log s ) d − 1 / s 2 ) [3 ] now gives
Var ( V ) ≤ ∑ i = 1 s E [ ( V ( − i ) − V ) 2 ] ≤ s O C ( ( log s ) d − 1 s 3 ) + o ( ( log s ) d − 1 s 2 ) = O C ( ( log s ) d − 1 s 2 ) . (62) \operatorname{Var}(V)\le\sum_{i=1}^{s}\mathbb{E}\left[(V^{(-i)}-V)^2\right]\le sO_C\left(\frac{(\log s)^{d-1}}{s^3}\right)+o\left(\frac{(\log s)^{d-1}}{s^2}\right)=O_C\left(\frac{(\log s)^{d-1}}{s^2}\right). \tag*{(62)} Var ( V ) ≤ i = 1 ∑ s E [ ( V ( − i ) − V ) 2 ] ≤ s O C ( s 3 ( log s ) d − 1 ) + o ( s 2 ( log s ) d − 1 ) = O C ( s 2 ( log s ) d − 1 ) . (62) Exponential moment and concentration. For any nonnegative random variable Y Y Y E [ Y ] = 1 \mathbb{E}[Y]=1 E [ Y ] = 1
E [ e − t Y ] ≤ e − t + ( 1 − ( 1 + t ) e − t ) Var ( Y ) ≤ e − t + Var ( Y ) , t ≥ 0. \mathbb{E}\left[e^{-tY}\right]\le e^{-t}+\left(1-(1+t)e^{-t}\right)\operatorname{Var}(Y)\le e^{-t}+\operatorname{Var}(Y),\qquad t\ge0. E [ e − t Y ] ≤ e − t + ( 1 − ( 1 + t ) e − t ) Var ( Y ) ≤ e − t + Var ( Y ) , t ≥ 0. Indeed, the quadratic polynomial agreeing with e − t x e^{-tx} e − t x x = 0 , 1 x=0,1 x = 0 , 1 x = 1 x=1 x = 1 x ≥ 0 x\ge0 x ≥ 0 e − t x e^{-tx} e − t x Y = V / E [ V ] Y=V/\mathbb{E}[V] Y = V / E [ V ] t = m E [ V ] t=m\mathbb{E}[V] t = m E [ V ] V ≤ A s V\le A_s V ≤ A s (60) and (62) give
E [ ( 1 − A s ) m ] ≤ E [ e − m V ] ≤ e − m E [ V ] + Var ( V ) ( E [ V ] ) 2 = O C ( ( log s ) 1 − d ) \mathbb{E}\left[(1-A_s)^m\right]\le\mathbb{E}\left[e^{-mV}\right]\le e^{-m\mathbb{E}[V]}+\frac{\operatorname{Var}(V)}{(\mathbb{E}[V])^2}=O_C((\log s)^{1-d}) E [ ( 1 − A s ) m ] ≤ E [ e − mV ] ≤ e − m E [ V ] + ( E [ V ] ) 2 Var ( V ) = O C (( log s ) 1 − d ) when m a Σ ( log s ) d − 1 / s = ( d − 1 ) log log s + O ( 1 ) m a\Sigma(\log s)^{d-1}/s=(d-1)\log\log s+O(1) ma Σ ( log s ) d − 1 / s = ( d − 1 ) log log s + O ( 1 ) (54) .
For fixed ε > 0 \varepsilon>0 ε > 0
P { A s < ( 1 − ε ) E [ A s ] } ≤ P { V < ( 1 − ε ) E [ A s ] } = O C , ε ( ( log s ) 1 − d ) \mathbb{P}\{A_s<(1-\varepsilon)\mathbb{E}[A_s]\}\le\mathbb{P}\{V<(1-\varepsilon)\mathbb{E}[A_s]\}=O_{C,\varepsilon}((\log s)^{1-d}) P { A s < ( 1 − ε ) E [ A s ]} ≤ P { V < ( 1 − ε ) E [ A s ]} = O C , ε (( log s ) 1 − d ) by Chebyshev’s inequality. Since Y = A s / E [ A s ] Y=A_s/\mathbb{E}[A_s] Y = A s / E [ A s ]
E [ ∣ Y − 1 ∣ ] = 2 E [ ( 1 − Y ) + ] ≤ 2 ε + 2 P { Y < 1 − ε } = 2 ε + o ( 1 ) . \mathbb{E}[|Y-1|]=2\mathbb{E}[(1-Y)_+]\le2\varepsilon+2\mathbb{P}\{Y<1-\varepsilon\}=2\varepsilon+o(1). E [ ∣ Y − 1∣ ] = 2 E [( 1 − Y ) + ] ≤ 2 ε + 2 P { Y < 1 − ε } = 2 ε + o ( 1 ) . Let s → ∞ s\to\infty s → ∞ ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0
Apply (38) with γ \gamma γ q C q_C q C (53) bounds its first term, and (55) with ε = 1 / 2 \varepsilon=1/2 ε = 1/2 O C ( ( log s ) 1 − d ) O_C((\log s)^{1-d}) O C (( log s ) 1 − d ) (56) .
Finally,
s E [ 1 A s ∫ u s q C 1 { q C ≤ T / s } d γ ] = s E [ A s ] E [ ∫ u s q C 1 { q C ≤ T / s } d γ ] + o ( 1 ) s\mathbb{E}\left[\frac{1}{A_s}\int_{u_s}q_C1\{q_C\le T/s\}\,d\gamma\right]=\frac{s}{\mathbb{E}[A_s]}\mathbb{E}\left[\int_{u_s}q_C1\{q_C\le T/s\}\,d\gamma\right]+o(1) s E [ A s 1 ∫ u s q C 1 { q C ≤ T / s } d γ ] = E [ A s ] s E [ ∫ u s q C 1 { q C ≤ T / s } d γ ] + o ( 1 ) ⟶ ∫ 0 T t e − t d t . \longrightarrow\int_0^T te^{-t}\,dt. ⟶ ∫ 0 T t e − t d t . The replacement error is at most T E [ ∣ A s / E [ A s ] − 1 ∣ ] = o ( 1 ) T\mathbb{E}[|A_s/\mathbb{E}[A_s]-1|]=o(1) T E [ ∣ A s / E [ A s ] − 1∣ ] = o ( 1 ) s ∫ u s q C 1 { q C ≤ T / s } d γ ≤ T A s s\int_{u_s}q_C1\{q_C\le T/s\}\,d\gamma\le TA_s s ∫ u s q C 1 { q C ≤ T / s } d γ ≤ T A s (57) and (53) . □
Random denominators
Lemma B.7. For fixed positive definite Σ \Sigma Σ s → ∞ s\to\infty s → ∞
E [ ( 1 − A s ) m ] = e − m E [ A s ] + o Σ ( 1 ) , E [ A s + ℓ A s ] = E [ A s + ℓ ] E [ A s ] + o Σ ( 1 ) \mathbb{E}[(1-A_s)^m]=e^{-m\mathbb{E}[A_s]}+o_\Sigma(1),\qquad\mathbb{E}\left[\frac{A_{s+\ell}}{A_s}\right]=\frac{\mathbb{E}[A_{s+\ell}]}{\mathbb{E}[A_s]}+o_\Sigma(1) E [( 1 − A s ) m ] = e − m E [ A s ] + o Σ ( 1 ) , E [ A s A s + ℓ ] = E [ A s ] E [ A s + ℓ ] + o Σ ( 1 ) for all integers m ≥ 1 m\ge1 m ≥ 1 ℓ ≥ 0 \ell\ge0 ℓ ≥ 0 m , ℓ m,\ell m , ℓ
E [ ∑ j = 1 m ( 1 − A s ) j − 1 ( A s + m − j − A s + m ) ] = O Σ ( ( log s ) 1 − d ) , (63) \mathbb{E}\left[\sum_{j=1}^{m}(1-A_s)^{j-1}(A_{s+m-j}-A_{s+m})\right]=O_\Sigma((\log s)^{1-d}), \tag*{(63)} E [ j = 1 ∑ m ( 1 − A s ) j − 1 ( A s + m − j − A s + m ) ] = O Σ (( log s ) 1 − d ) , (63) E [ ( 1 − A s + m A s ) ( 1 − A s ) m ] = O Σ ( ( log s ) 1 − d ) . (64) \mathbb{E}\left[\left(1-\frac{A_{s+m}}{A_s}\right)(1-A_s)^m\right]=O_\Sigma((\log s)^{1-d}). \tag*{(64)} E [ ( 1 − A s A s + m ) ( 1 − A s ) m ] = O Σ (( log s ) 1 − d ) . (64) The same bounds hold for the cone model in Lemma B.6, with constants depending on C C C
Proof. Lemma B.6 gives E [ ∣ A s / E [ A s ] − 1 ∣ ] = o Σ ( 1 ) \mathbb{E}\left[\lvert A_s/\mathbb{E}[A_s]-1\rvert\right]=o_{\Sigma}(1) E [ ∣ A s / E [ A s ] − 1 ∣ ] = o Σ ( 1 )
0 ≤ e − m x − ( 1 − x ) m ≤ c x , ∣ e − t y − e − t ∣ ≤ c ∣ y − 1 ∣ ( 0 ≤ x ≤ 1 , y , t ≥ 0 ) 0\le e^{-mx}-(1-x)^m\le cx,\qquad\lvert e^{-ty}-e^{-t}\rvert\le c\lvert y-1\rvert\quad(0\le x\le1,\ y,t\ge0) 0 ≤ e − m x − ( 1 − x ) m ≤ c x , ∣ e − t y − e − t ∣ ≤ c ∣ y − 1 ∣ ( 0 ≤ x ≤ 1 , y , t ≥ 0 ) follow from − log ( 1 − x ) = x + O ( x 2 ) -\log(1-x)=x+O(x^2) − log ( 1 − x ) = x + O ( x 2 ) x ≤ 1 / 2 x\le1/2 x ≤ 1/2 y ≥ 1 / 2 y\ge1/2 y ≥ 1/2 m ≥ 1 m\ge1 m ≥ 1
∣ E [ ( 1 − A s ) m ] − e − m E [ A s ] ∣ ≤ c E [ A s ] + c E [ ∣ A s / E [ A s ] − 1 ∣ ] = o Σ ( 1 ) . \left\lvert\mathbb{E}\left[(1-A_s)^m\right]-e^{-m\mathbb{E}[A_s]}\right\rvert\le c\mathbb{E}[A_s]+c\mathbb{E}\left[\lvert A_s/\mathbb{E}[A_s]-1\rvert\right]=o_{\Sigma}(1). E [ ( 1 − A s ) m ] − e − m E [ A s ] ≤ c E [ A s ] + c E [ ∣ A s / E [ A s ] − 1 ∣ ] = o Σ ( 1 ) . Similarly,
∣ E [ A s + ℓ A s ] − E [ A s + ℓ ] E [ A s ] ∣ ≤ E [ A s + ℓ A s ∣ 1 − A s E [ A s ] ∣ ] ≤ E [ ∣ 1 − A s E [ A s ] ∣ ] . \left\lvert\mathbb{E}\left[\frac{A_s+\ell}{A_s}\right]-\frac{\mathbb{E}[A_s+\ell]}{\mathbb{E}[A_s]}\right\rvert\le\mathbb{E}\left[\frac{A_s+\ell}{A_s}\left\lvert1-\frac{A_s}{\mathbb{E}[A_s]}\right\rvert\right]\le\mathbb{E}\left[\left\lvert1-\frac{A_s}{\mathbb{E}[A_s]}\right\rvert\right]. E [ A s A s + ℓ ] − E [ A s ] E [ A s + ℓ ] ≤ E [ A s A s + ℓ 1 − E [ A s ] A s ] ≤ E [ 1 − E [ A s ] A s ] . For the last two assertions, conditional on Z 1 : s Z_{1:s} Z 1 : s J U s q d F \mathcal{J}_{\mathcal{U}_s}q\,dF J U s q d F A s + m − j − A s + m A_{s+m-j}-A_{s+m} A s + m − j − A s + m j j j A s − A s + m A_s-A_{s+m} A s − A s + m m m m (63) and (64) are bounded, respectively, by
E [ ∫ U s q d F ∑ j = 1 m j ( 1 − A s ) j − 1 ] ≤ E [ A s − 2 ∫ U s q d F ] , \mathbb{E}\left[\int_{\mathcal{U}_s}q\,dF\sum_{j=1}^{m}j(1-A_s)^{j-1}\right]\le\mathbb{E}\left[A_s^{-2}\int_{\mathcal{U}_s}q\,dF\right], E [ ∫ U s q d F j = 1 ∑ m j ( 1 − A s ) j − 1 ] ≤ E [ A s − 2 ∫ U s q d F ] , E [ ∫ U s q d F m ( 1 − A s ) m A s ] ≤ 1 e E [ A s − 2 ∫ U s q d F ] . \mathbb{E}\left[\int_{\mathcal{U}_s}q\,dF\frac{m(1-A_s)^m}{A_s}\right]\le\frac{1}{e}\mathbb{E}\left[A_s^{-2}\int_{\mathcal{U}_s}q\,dF\right]. E [ ∫ U s q d F A s m ( 1 − A s ) m ] ≤ e 1 E [ A s − 2 ∫ U s q d F ] . The inequalities use ∑ j ≥ 1 j ( 1 − A s ) j − 1 = A s − 2 \sum_{j\ge1}j(1-A_s)^{j-1}=A_s^{-2} ∑ j ≥ 1 j ( 1 − A s ) j − 1 = A s − 2 m A s ( 1 − A s ) m ≤ 1 / e mA_s(1-A_s)^m\le1/e m A s ( 1 − A s ) m ≤ 1/ e (56) to finish. □
Marginal tail estimates
From this point on, d d d r r r
For a binomial count N N N k ≥ E [ N ] k\ge\mathbb{E}[N] k ≥ E [ N ]
P { N ≥ k } ≤ ( e E [ N ] / k ) k . (65) \mathbb{P}\{N\ge k\}\le(e\mathbb{E}[N]/k)^k. \tag*{(65)} P { N ≥ k } ≤ ( e E [ N ] / k ) k . (65) Lemma B.8. For any continuous marginals, outside an event of probability O d ( n − 1 ) O_d(n^{-1}) O d ( n − 1 ) N = ⌊ n / 2 ⌋ N=\lfloor n/2\rfloor N = ⌊ n /2 ⌋ p p p j j j
0 ≤ p ‾ N ( j ) − p ≤ c ( p ( 1 − p ) log n N + log n N ) . (66) 0\le\overline{p}_N(j)-p\le c\left(\sqrt{\frac{p(1-p)\log n}{N}}+\frac{\log n}{N}\right). \tag*{(66)} 0 ≤ p N ( j ) − p ≤ c ( N p ( 1 − p ) log n + N log n ) . (66) No independence between coordinates is required.
Proof. For one coordinate, let N = ⌊ n / 2 ⌋ N=\lfloor n/2\rfloor N = ⌊ n /2 ⌋ V ( 1 ) , … , V ( N ) V_{(1)},\ldots,V_{(N)} V ( 1 ) , … , V ( N ) p p p j < N j<N j < N p ≤ V ( j + 1 ) p\le V_{(j+1)} p ≤ V ( j + 1 )
P { V ( j + 1 ) > p ‾ N ( j ) } = P { Bin ( N , p ‾ N ( j ) ) ≤ j } = n − 2 . \mathbb{P}\left\{V_{(j+1)}>\overline{p}_N(j)\right\}=\mathbb{P}\left\{\operatorname{Bin}(N,\overline{p}_N(j))\le j\right\}=n^{-2}. P { V ( j + 1 ) > p N ( j ) } = P { Bin ( N , p N ( j )) ≤ j } = n − 2 . For j = N j=N j = N p ‾ N ( N ) = 1 \overline{p}_N(N)=1 p N ( N ) = 1 d N / n 2 dN/n^2 d N / n 2 p ≤ p ‾ N ( j ) p\le\overline{p}_N(j) p ≤ p N ( j ) F ‾ N ( p ) = N − 1 # { i : V i < p } \overline{F}_N(p)=N^{-1}\#\{i: V_i<p\} F N ( p ) = N − 1 # { i : V i < p } p = i / n 3 p=i/n^3 p = i / n 3 1 − O ( n − 3 ) 1-O(n^{-3}) 1 − O ( n − 3 )
∣ F ‾ N ( p ) − p ∣ ≤ c ( p ( 1 − p ) log n N + log n N ) , 0 ≤ p ≤ 1. \left|\overline{F}_N(p)-p\right|\le c\left(\sqrt{\frac{p(1-p)\log n}{N}}+\frac{\log n}{N}\right),\qquad0\le p\le1. F N ( p ) − p ≤ c ( N p ( 1 − p ) log n + N log n ) , 0 ≤ p ≤ 1. The grid error is absorbed by ( log n ) / N (\log n)/N ( log n ) / N
Inverting the lower-tail Bernstein bound also gives, for r = j / N r=j/N r = j / N c c c
0 ≤ p ‾ N ( j ) − r ≤ c ( r ( 1 − r ) log n N + log n N ) . 0\le\overline{p}_N(j)-r\le c\left(\sqrt{\frac{r(1-r)\log n}{N}}+\frac{\log n}{N}\right). 0 ≤ p N ( j ) − r ≤ c ( N r ( 1 − r ) log n + N log n ) . Combine these inequalities with r = F ‾ N ( p ) r=\overline{F}_N(p) r = F N ( p ) ∣ r ( 1 − r ) − p ( 1 − p ) ∣ ≤ ∣ r − p ∣ |r(1-r)-p(1-p)|\le|r-p| ∣ r ( 1 − r ) − p ( 1 − p ) ∣ ≤ ∣ r − p ∣ (66) simultaneously in all coordinates.
For fixed κ > 0 \kappa>0 κ > 0 p , 1 − p ≥ n − 1 + κ p,1-p\ge n^{-1+\kappa} p , 1 − p ≥ n − 1 + κ O ( n − κ / 2 log n + n − κ log n ) O(n^{-\kappa/2}\sqrt{\log n}+n^{-\kappa}\log n) O ( n − κ /2 log n + n − κ log n ) ϕ \phi ϕ 1 / ϕ ( Φ − 1 ( u ) ) ≤ O ( 1 ) / min ( u , 1 − u ) 1/\phi(\Phi^{-1}(u))\le O(1)/\min(u,1-u) 1/ ϕ ( Φ − 1 ( u )) ≤ O ( 1 ) / min ( u , 1 − u ) o ( 1 / log n ) o(1/\sqrt{\log n}) o ( 1/ log n )
Correlation estimates
Lemma B.9. Fix d ≥ 2 d\ge2 d ≥ 2 Σ \Sigma Σ ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊ n /2 ⌋ 1 − O d ( n − 1 ) 1-O_d(n^{-1}) 1 − O d ( n − 1 ) n n n
Σ ‾ is positive definite , Σ ‾ k ℓ ≥ Σ k ℓ , ∥ Σ ‾ − Σ ∥ = O d ( log n n ) , \overline{\Sigma}\text{ is positive definite},\qquad\overline{\Sigma}_{k\ell}\ge\Sigma_{k\ell},\qquad\|\overline{\Sigma}-\Sigma\|=O_d\left(\sqrt{\frac{\log n}{n}}\right), Σ is positive definite , Σ k ℓ ≥ Σ k ℓ , ∥ Σ − Σ∥ = O d ( n log n ) , a Σ ‾ / a Σ = 1 + o ( 1 ) , q ( z ) ≤ q ‾ ( z ) for every z . a_{\overline{\Sigma}}/a_{\Sigma}=1+o(1),\qquad q(z)\le\overline{q}(z)\quad\text{for every }z. a Σ / a Σ = 1 + o ( 1 ) , q ( z ) ≤ q ( z ) for every z . For each fixed κ > 0 \kappa>0 κ > 0 q ‾ ( z ) / q ( z ) = 1 + o ( 1 ) \overline{q}(z)/q(z)=1+o(1) q ( z ) / q ( z ) = 1 + o ( 1 ) O ( log n ) O(\sqrt{\log n}) O ( log n ) n − 1 + κ n^{-1+\kappa} n − 1 + κ
Proof. Use the marginal bounds and the standardized-coordinate error proved in Lemma B.8.
Correlation estimates. For this estimate, let N = ⌊ n / 4 ⌋ N=\lfloor n/4\rfloor N = ⌊ n /4 ⌋ arccos ( Σ k ℓ ) \arccos(\Sigma_{k\ell}) arccos ( Σ k ℓ ) arccos ( Σ k ℓ ) / π \arccos(\Sigma_{k\ell})/\pi arccos ( Σ k ℓ ) / π p k ℓ = 1 − arccos ( Σ k ℓ ) / π p_{k\ell}=1-\arccos(\Sigma_{k\ell})/\pi p k ℓ = 1 − arccos ( Σ k ℓ ) / π N k ℓ ∼ Bin ( N , p k ℓ ) N_{k\ell}\sim\operatorname{Bin}(N,p_{k\ell}) N k ℓ ∼ Bin ( N , p k ℓ ) P { p ‾ N ( N k ℓ ) < p k ℓ } ≤ n − 2 \mathbb{P}\{\overline{p}_N(N_{k\ell})<p_{k\ell}\}\le n^{-2} P { p N ( N k ℓ ) < p k ℓ } ≤ n − 2
p ‾ N ( j ) ≤ min { 1 , j / N + log n / N } , ∣ N k ℓ / N − p k ℓ ∣ = O ( log n / N ) \overline{p}_N(j)\le\min\{1,j/N+\sqrt{\log n/N}\},\qquad|N_{k\ell}/N-p_{k\ell}|=O\left(\sqrt{\log n/N}\right) p N ( j ) ≤ min { 1 , j / N + log n / N } , ∣ N k ℓ / N − p k ℓ ∣ = O ( log n / N ) simultaneously for all coordinate pairs except with probability O d ( n − 2 ) O_d(n^{-2}) O d ( n − 2 ) − cos ( π p ) -\cos(\pi p) − cos ( π p ) Σ \Sigma Σ Σ ˉ \bar{\Sigma} Σ ˉ n n n (25) gives a Σ ˉ / a Σ → 1 a_{\bar{\Sigma}}/a_{\Sigma} \to1 a Σ ˉ / a Σ → 1
Gaussian rectangle probabilities. Work in standardized marginal coordinates in this step, and write
q S ( z ) = P W ∼ N d ( 0 , S ) { W ( k ) ≥ z ( k ) for every k ∈ [ d ] } . q_S(z) = \mathbb{P}_{W\sim\mathcal{N}_d(0,S)}\left\{W^{(k)} \ge z^{(k)}\text{ for every }k\in[d]\right\}. q S ( z ) = P W ∼ N d ( 0 , S ) { W ( k ) ≥ z ( k ) for every k ∈ [ d ] } . when the correlation matrix S S S S ≥ Σ S \ge\Sigma S ≥ Σ q S ( z ) ≥ q Σ ( z ) q_S(z) \ge q_\Sigma(z) q S ( z ) ≥ q Σ ( z ) g ( x ) = ∏ k g k ( x ( k ) ) g(x)=\prod_k g_k(x^{(k)}) g ( x ) = ∏ k g k ( x ( k ) ) g k g_k g k
d d t E [ g ( W t ) ] = 1 2 ∑ k , ℓ ( S − Σ ) k ℓ E [ ∂ k ℓ g ( W t ) ] , W t ∼ N d ( 0 , ( 1 − t ) Σ + t S ) . \frac{d}{dt}\mathbb{E}[g(W_t)] = \frac{1}{2}\sum_{k,\ell}(S-\Sigma)_{k\ell}\mathbb{E}[\partial_{k\ell}g(W_t)], \qquad W_t\sim\mathcal{N}_d(0,(1-t)\Sigma+tS). d t d E [ g ( W t )] = 2 1 k , ℓ ∑ ( S − Σ ) k ℓ E [ ∂ k ℓ g ( W t )] , W t ∼ N d ( 0 , ( 1 − t ) Σ + tS ) . Diagonal terms vanish and all remaining terms are nonnegative. Taking limits proves the bound, also when some thresholds are − ∞ -\infty − ∞
q Σ ( z ) ≤ q Σ ( z ^ ) ≤ q Σ ˉ ( z ^ ) = q ^ ( z ) . q_\Sigma(z)\le q_\Sigma(\widehat{z})\le q_{\bar{\Sigma}}(\widehat{z})=\widehat{q}(z). q Σ ( z ) ≤ q Σ ( z ) ≤ q Σ ˉ ( z ) = q ( z ) . Finally, fix constants B , κ > 0 B,\kappa>0 B , κ > 0 ∥ z ∥ ≤ B log n \lVert z\rVert\le B\sqrt{\log n} ∥ z ∥ ≤ B log n min { Φ ( z ( k ) ) , 1 − Φ ( z ( k ) ) } ≥ n − 1 + κ \min\{\Phi(z^{(k)}),1-\Phi(z^{(k)})\}\ge n^{-1+\kappa} min { Φ ( z ( k ) ) , 1 − Φ ( z ( k ) )} ≥ n − 1 + κ k ∈ [ d ] k\in[d] k ∈ [ d ] ∥ z ^ − z ∥ = o ( 1 / log n ) \lVert\widehat{z}-z\rVert=o(1/\sqrt{\log n}) ∥ z − z ∥ = o ( 1/ log n ) ∥ Σ ˉ − Σ ∥ log n = o ( 1 ) \lVert\bar{\Sigma}-\Sigma\rVert\log n=o(1) ∥ Σ ˉ − Σ ∥ log n = o ( 1 ) f S f_S f S N d ( 0 , S ) \mathcal{N}_d(0,S) N d ( 0 , S )
q S ( z ) = ∫ [ 0 , ∞ ) d f S ( z + v ) d v . q_S(z)=\int_{[0,\infty)^d}f_S(z+v)\,dv. q S ( z ) = ∫ [ 0 , ∞ ) d f S ( z + v ) d v . We compare the two integrals first on a ball and then control their tails. Since the eigenvalues of Σ ˉ \bar{\Sigma} Σ ˉ ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) R R R
sup ∥ z ∥ ≤ B log n , v ≥ 0 ∥ z + v ∥ ≤ R log n min k ∈ [ d ] min { Φ ( z ( k ) ) , 1 − Φ ( z ( k ) ) } ≥ n − 1 + κ ∣ log f Σ ˉ ( z ^ + v ) f Σ ( z + v ) ∣ = o ( 1 ) . (67) \sup_{\substack{\lVert z\rVert\le B\sqrt{\log n},\ v\ge0\\ \lVert z+v\rVert\le R\sqrt{\log n}\\ \min_{k\in[d]}\min\{\Phi(z^{(k)}),1-\Phi(z^{(k)})\}\ge n^{-1+\kappa}}}
\left|\log\frac{f_{\bar{\Sigma}}(\widehat{z}+v)}{f_\Sigma(z+v)}\right|=o(1). \tag*{(67)} ∥ z ∥ ≤ B l o g n , v ≥ 0 ∥ z + v ∥ ≤ R l o g n m i n k ∈ [ d ] m i n { Φ ( z ( k ) ) , 1 − Φ ( z ( k ) )} ≥ n − 1 + κ sup log f Σ ( z + v ) f Σ ˉ ( z + v ) = o ( 1 ) . (67) The log-density error is O Σ ( ∥ Σ ˉ − Σ ∥ log n + ∥ z ^ − z ∥ log n ) = o ( 1 ) O_\Sigma(\lVert\bar{\Sigma}-\Sigma\rVert\log n+\lVert\widehat{z}-z\rVert\sqrt{\log n})=o(1) O Σ (∥ Σ ˉ − Σ ∥ log n + ∥ z − z ∥ log n ) = o ( 1 ) v ≥ 0 v\ge0 v ≥ 0
Next integrate f Σ ( z + v ) f_\Sigma(z+v) f Σ ( z + v ) v ∈ [ 0 , 1 ] d v\in[0,1]^d v ∈ [ 0 , 1 ] d K = K ( B , Σ ) K=K(B,\Sigma) K = K ( B , Σ ) c = c ( B , Σ ) > 0 c=c(B,\Sigma)>0 c = c ( B , Σ ) > 0
q Σ ( z ) ≥ c n − K whenever ∥ z ∥ ≤ B log n . (68) q_\Sigma(z)\ge cn^{-K}\qquad\text{whenever }\lVert z\rVert\le B\sqrt{\log n}. \tag*{(68)} q Σ ( z ) ≥ c n − K whenever ∥ z ∥ ≤ B log n . (68) Choose R R R O ( n − K − 2 ) O(n^{-K-2}) O ( n − K − 2 ) Σ ˉ \bar{\Sigma} Σ ˉ (68) , both discarded integrals are o ( q Σ ( z ) ) o(q_\Sigma(z)) o ( q Σ ( z )) (67) on the ball therefore proves q Σ ˉ ( z ^ ) / q Σ ( z ) = 1 + o ( 1 ) q_{\bar{\Sigma}}(\widehat{z})/q_\Sigma(z)=1+o(1) q Σ ˉ ( z ) / q Σ ( z ) = 1 + o ( 1 )
To apply the relative estimate in the stopping proof, choose P P P C ∗ C^* C ∗ ± a k \pm a_k ± a k a k a_k a k Σ 1 / 2 \Sigma^{1/2} Σ 1/2 d ≥ 2 d\ge2 d ≥ 2 a P a_P a P a Σ a_\Sigma a Σ ∣ a k ⋅ θ ∣ ≤ b < 1 |a_k\cdot\theta|\le b<1 ∣ a k ⋅ θ ∣ ≤ b < 1 k k k ∥ X ∥ ≤ 2 log n + 40 d log log n \lVert X\rVert\le\sqrt{2\log n}+40d\log\log n ∥ X ∥ ≤ 2 log n + 40 d log log n n − 1 + κ n^{-1+\kappa} n − 1 + κ κ > 0 \kappa>0 κ > 0 O d ( n − 1 ( log n ) ( d − 2 ) / 2 − 20 d ) = o ( u ( log n ) d − 1 ) O_d(n^{-1}(\log n)^{(d-2)/2-20d})=o(u(\log n)^{d-1}) O d ( n − 1 ( log n ) ( d − 2 ) /2 − 20 d ) = o ( u ( log n ) d − 1 ) (51) .
Known correlation matrix
Lemma B.10. Suppose the correlation matrix Σ = A A T \Sigma= AA^{\mathsf T} Σ = A A T A ∈ R d × r A \in\mathbb{R}^{d\times r} A ∈ R d × r r ≥ 2 r \ge2 r ≥ 2 a 1 T , … , a d T a_1^{\mathsf T},\ldots,a_d^{\mathsf T} a 1 T , … , a d T C = { x ∈ R r : A x ≥ 0 } C = \{x \in\mathbb{R}^r : Ax \ge0\} C = { x ∈ R r : A x ≥ 0 } (32) with Σ \Sigma Σ Σ ^ \widehat{\Sigma} Σ O d ( n − 1 ) O_d(n^{-1}) O d ( n − 1 ) q ( z ) ≤ q ^ ( z ) q(z) \le\widehat{q}(z) q ( z ) ≤ q ( z ) z z z C ∗ C^* C ∗ ± a k \pm a_k ± a k q ^ ( A x ) = ( 1 + o ( 1 ) ) q C ( x ) \widehat{q}(Ax) = (1 + o(1))q_C(x) q ( A x ) = ( 1 + o ( 1 )) q C ( x ) ∥ x ∥ ≤ 2 log n + 40 r log log n \lVert x\rVert\le\sqrt{2\log n} + 40r\log\log n ∥ x ∥ ≤ 2 log n + 40 r log log n
Proof. Lemma B.8 gives the marginal confidence bounds without any assumption on dependence. Applying them with the known Σ \Sigma Σ δ = o ( 1 / log n ) \delta= o(1/\sqrt{\log n}) δ = o ( 1/ log n ) v v v ( A v ) ( k ) ≥ 1 (Av)^{(k)} \ge1 ( A v ) ( k ) ≥ 1 k k k C C C A A A
x + C ⊆ { y : A y ≥ z ^ } ⊆ x − δ v + C , z = A x . x + C \subseteq\{y : Ay \ge\widehat{z}\} \subseteq x - \delta v + C,\qquad z = Ax. x + C ⊆ { y : A y ≥ z } ⊆ x − δ v + C , z = A x . Hence q C ( x ) ≤ q ^ ( z ) ≤ q C ( x − δ v ) q_C(x) \le\widehat{q}(z) \le q_C(x-\delta v) q C ( x ) ≤ q ( z ) ≤ q C ( x − δ v ) (67) , now in dimension r r r I r I_r I r − δ v -\delta v − δ v O v , R ( δ log n + δ 2 ) = o ( 1 ) O_{v,R}(\delta\sqrt{\log n}+\delta^2) = o(1) O v , R ( δ log n + δ 2 ) = o ( 1 ) ∥ y ∥ ≤ R log n \lVert y\rVert\le R\sqrt{\log n} ∥ y ∥ ≤ R log n R R R x + C x+C x + C 1 + o ( 1 ) 1+o(1) 1 + o ( 1 ) (43) gives a polynomial lower bound on q C ( x ) q_C(x) q C ( x ) R R R q C ( x ) q_C(x) q C ( x ) q C ( x − δ v ) / q C ( x ) = 1 + o ( 1 ) q_C(x-\delta v)/q_C(x)=1+o(1) q C ( x − δ v ) / q C ( x ) = 1 + o ( 1 )
Conditional selection bounds
The preceding estimates give the same two bounds whether a rule uses q q q
Corollary B.11. Let Z = A X Z = AX Z = A X X ∼ N r ( 0 , I r ) X \sim\mathcal{N}_r(0,I_r) X ∼ N r ( 0 , I r ) r ≥ 2 r \ge2 r ≥ 2 A A A r r r C = { x : A x ≥ 0 } C = \{x : Ax \ge0\} C = { x : A x ≥ 0 } Σ = A A T \Sigma= AA^{\mathsf T} Σ = A A T a Σ a_\Sigma a Σ (39) , in dimension r r r q ^ = q \widehat{q}=q q = q Σ \Sigma Σ Σ \Sigma Σ ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊ n /2 ⌋
For every fixed ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) n n n o ( ( ( log n ) r − 1 log log n ) − 1 ) o(((\log n)^{r-1}\log\log n)^{-1}) o ((( log n ) r − 1 log log n ) − 1 ) q ≤ q ^ q \le\widehat{q} q ≤ q
P { Z s ∈ Max ( Z 1 , … , Z s ) , q ^ ( Z s ) ≤ u ∣ H s − 1 } ≥ ( 1 − ϵ ) a Σ ( log n ) r − 1 u , \mathbb{P}\{Z_s \in\operatorname{Max}(Z_1,\ldots,Z_s),\ \widehat{q}(Z_s) \le u \mid\mathcal{H}_{s-1}\} \ge(1-\epsilon)a_\Sigma(\log n)^{r-1}u, P { Z s ∈ Max ( Z 1 , … , Z s ) , q ( Z s ) ≤ u ∣ H s − 1 } ≥ ( 1 − ϵ ) a Σ ( log n ) r − 1 u , E [ q ( Z s ) 1 { q ^ ( Z s ) ≤ u } ∣ H s − 1 ] ≤ ( 1 + ϵ ) a Σ 2 ( log n ) r − 1 u 2 . \mathbb{E}[q(Z_s)1\{\widehat{q}(Z_s) \le u\}\mid\mathcal{H}_{s-1}] \le(1+\epsilon)\frac{a_\Sigma}{2}(\log n)^{r-1}u^2. E [ q ( Z s ) 1 { q ( Z s ) ≤ u } ∣ H s − 1 ] ≤ ( 1 + ϵ ) 2 a Σ ( log n ) r − 1 u 2 . Here H s − 1 \mathcal{H}_{s-1} H s − 1 § 2 , s > ⌈ n / 2 ⌉ s > \lceil n/2\rceil s > ⌈ n /2 ⌉
1 n ( log n ) 2 ( r − 1 ) ≤ u ≤ e − log log n / 3 n . \frac{1}{n(\log n)^{2(r-1)}} \le u \le\frac{e^{-\sqrt{\log\log n}/3}}{n}. n ( log n ) 2 ( r − 1 ) 1 ≤ u ≤ n e − l o g l o g n /3 . The bounds hold for all these times, thresholds, and histories. Each exception is determined by observations already seen. The same exceptional histories work for every threshold in this interval, including a threshold chosen using the initial sample. For independent coordinates, take A = I d A=I_d A = I d r = d r=d r = d a I = 1 / ( d − 1 ) ! a_I=1/(d-1)! a I = 1/ ( d − 1 )! (16) . For q ^ = q \widehat{q}=q q = q q C q_C q C ∄ i < s : X s ≺ C X i \nexists i < s : X_s \prec_C X_i ∄ i < s : X s ≺ C X i a Σ a_\Sigma a Σ (39) .
Proof. Choose a fixed compact set P ⊂ int ( C ∗ ) ∩ S r − 1 P \subset\operatorname{int}(C^*) \cap S^{r-1} P ⊂ int ( C ∗ ) ∩ S r − 1 A A A a P > ( 1 − ε / 8 ) a Σ a_P > (1-\varepsilon/8)a_\Sigma a P > ( 1 − ε /8 ) a Σ Lemma B.9 , give q ≤ q ^ q \le\widehat{q} q ≤ q q ^ ( A X ) ≤ ( 1 + ε / 8 ) q C ( X ) \widehat{q}(AX) \le(1+\varepsilon/8)q_C(X) q ( A X ) ≤ ( 1 + ε /8 ) q C ( X ) P P P ∥ X ∥ ≤ 2 log n + 40 r log log n \lVert X\rVert\le\sqrt{2}\log n + 40r\log\log n ∥ X ∥ ≤ 2 log n + 40 r log log n n n n q ^ = q \widehat{q}=q q = q o ( u ( log n ) r − 1 ) o(u(\log n)^{r-1}) o ( u ( log n ) r − 1 ) H s − 1 \mathcal{H}_{s-1} H s − 1
P { Z s ∈ Max ( Z 1 , … , Z s ) , q ^ ( Z s ) ≤ u ∣ H s − 1 } ≥ P { q ^ ( Z s ) ≤ u , X s / ∥ X s ∥ ∈ P ∣ H s − 1 } − P { q C ( X s ) ≤ u , X s / ∥ X s ∥ ∈ P , ∃ i < s : X s ≺ C X i ∣ H s − 1 } ≥ ( 1 − ε / 2 ) a Σ u ( log n ) r − 1 − o ( u ( log n ) r − 1 ) ≥ ( 1 − ε ) a Σ u ( log n ) r − 1 . \begin{aligned}
\mathbb{P}\{Z_s \in\operatorname{Max}(Z_1,\ldots,Z_s),\ \widehat{q}(Z_s) \le u \mid\mathcal{H}_{s-1}\}
&\ge\mathbb{P}\{\widehat{q}(Z_s) \le u,\ X_s/\lVert X_s\rVert\in P \mid\mathcal{H}_{s-1}\}\\
&\quad-\mathbb{P}\{q_C(X_s) \le u,\ X_s/\lVert X_s\rVert\in P,\ \exists i<s:X_s \prec_C X_i \mid\mathcal{H}_{s-1}\}\\
&\ge(1-\varepsilon/2)a_\Sigma u(\log n)^{r-1}-o(u(\log n)^{r-1})\\
&\ge(1-\varepsilon)a_\Sigma u(\log n)^{r-1}.
\end{aligned} P { Z s ∈ Max ( Z 1 , … , Z s ) , q ( Z s ) ≤ u ∣ H s − 1 } ≥ P { q ( Z s ) ≤ u , X s / ∥ X s ∥ ∈ P ∣ H s − 1 } − P { q C ( X s ) ≤ u , X s / ∥ X s ∥ ∈ P , ∃ i < s : X s ≺ C X i ∣ H s − 1 } ≥ ( 1 − ε /2 ) a Σ u ( log n ) r − 1 − o ( u ( log n ) r − 1 ) ≥ ( 1 − ε ) a Σ u ( log n ) r − 1 . The first inequality uses q ≤ q ^ q \le\widehat{q} q ≤ q (47) at u / ( 1 + ε / 8 ) u/(1+\varepsilon/8) u / ( 1 + ε /8 )
E [ q ( Z s ) 1 { q ^ ( Z s ) ≤ u } ∣ H s − 1 ] ≤ E [ q ( Z s ) 1 { q ( Z s ) ≤ u } ] ≤ ( 1 + ε ) a Σ 2 u 2 ( log n ) r − 1 . \mathbb{E}\left[q(Z_s)1\{\widehat{q}(Z_s)\le u\}\mid\mathcal{H}_{s-1}\right]
\le\mathbb{E}\left[q(Z_s)1\{q(Z_s)\le u\}\right]
\le(1+\varepsilon)\frac{a_\Sigma}{2}u^2(\log n)^{r-1}. E [ q ( Z s ) 1 { q ( Z s ) ≤ u } ∣ H s − 1 ] ≤ E [ q ( Z s ) 1 { q ( Z s ) ≤ u } ] ≤ ( 1 + ε ) 2 a Σ u 2 ( log n ) r − 1 . where the last inequality is the truncated-moment estimate in (47) . The exceptional histories come from Lemma B.5 and, when estimating q q q q ^ = q \widehat{q}=q q = q
