The Pareto record frontier

For i.i.d. 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 RSn := {0 <= x is an element of R-d : x not equal to or less than X-(i) for all 1 <= i <= n} at time n, where 0 <= x means that 0 <= x(j) for 1 <= j <= d and x (sic) y means that x(j) < y(j) for 1 <= j <= d. With x(+) := Sigma(d)(j=1) x(j), let F-n(-) := min{x(+) : x is an element of F-n} and F-n(+) := max{x(+) : x is an element of 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(+) similar to ln n similar to F-n(-) almost surely and that W-n/ln ln n converges in probability to d; and for d >= 2 we show that, almost surely, the set of limit points of the sequence W-n/ln ln 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-Tm(+) similar to (d!m)(1/d) similar to F-Tm(-) almost surely and that W-Tm/lnm converges in probability to 1 -d(-1); and for d >= 2 we show that, almost surely, the sequence W-Tm/ ln m has lim inf equal to 1 d and lim sup equal to 1.