The Pareto Record Frontier

For iid $d$-dimensional observations $X^{(1)}, X^{(2)}, ldots$ 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 [ mbox{RS}_n := {0 leq x in {mathbb R}^d: x otprec X^{(i)} mbox{for all $1 leq i leq n$}} ] at time $n$, where $0 leq x$ means that $0 leq x_j$ for $1 leq j leq d$ and $x prec y$ means that $x_j < y_j$ for $1 leq j leq d$. With $x_+ := sum_{j = 1}^d x_j$, let [ F_n^- := min{x_+: x in F_n} quad mbox{and} quad F_n^+ := max{x_+: x in 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 sim ln n sim F^-_n$ almost surely and that $W_n / ln ln n$ converges in probability to $d - 1$; and for $d geq 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 $m$th record is set. We show that $F^+_{T_m} sim (d! m)^{1/d} sim F^-_{T_m}$ almost surely and that $W_{T_m} / ln m$ converges in probability to $1 - d^{-1}$; and for $d geq 2$ we show that, almost surely, the sequence $W_{T_m} / ln m$ has $liminf$ equal to $1 - d^{-1}$ and $limsup$ equal to $1$.