The Pareto Record Frontier
share
For iid d-dimensional observations X^(1), X^(2), ... with independent Exponential(1) coordinates, consider the boundary (relative to the closed positive orthant), or "frontier", F_n of the closed Pareto record-setting (RS) region RS_n := {0 ≤ x ∈ R^d: x ≺ X^(i) for all 1 ≤ i ≤ n} at time n, where 0 ≤ x means that 0 ≤ x_j for 1 ≤ j ≤ d and x ≺ y means that x_j < y_j for 1 ≤ j ≤ d. With x_+ := ∑_j = 1^d x_j, let F_n^- := {x_+: x ∈ F_n} and F_n^+ := {x_+: x ∈ F_n}, and define the width of F_n as W_n := F_n^+ - F_n^-. We describe typical and almost sure behavior of the processes F^+, F^-, and W. In particular, we show that F^+_n ∼ n ∼ F^-_n almost surely and that W_n / n converges in probability to d - 1; and for d ≥ 2 we show that, almost surely, the set of limit points of the sequence W_n / n is the interval [d - 1, d]. We also obtain modifications of our results that are important in connection with efficient simulation of Pareto records. Let T_m denote the time that the mth record is set. We show that F̃^+_m ∼ (d! m)^1/d∼F̃^-_m almost surely and that W_T_m / m converges in probability to 1 - d^-1; and for d ≥ 2 we show that, almost surely, the sequence W_T_m / m has equal to 1 - d^-1 and equal to 1.
READ FULL TEXT