For d ≥ 2 and i.i.d. d-dimensional observations 𝐗^(1), 𝐗^(2), … with independent Exponential(1) coordinates, let φ_n denote the minimum 𝓁¹-norm among the maxima of {𝐗^(1), …, 𝐗^(n)}. (A maximum from this set is an observation 𝐗^(k) with 1 ≤ k ≤ n such that 𝐗^(k) ⊀ 𝐗^(i) for all 1 ≤ i ≤ n, where 𝐱 ≺ 𝐲 means that x_j < y_j for 1 ≤ j ≤ d.) Key roles in the study of multivariate Pareto records are played by φ_n and by the more easily handled maximum with the maximum 𝓁¹-norm. Fill et al. proved [Fill et al., 2026, Theorem 1.11(a)] that φ_n = ln n - ln ln ln n - ln(d - 1) + O_p(1/ln ln n), where Z_n = O_p(a_n) means that Z_n / a_n is bounded in probability, and conjectured [Fill et al., 2026, Remarks 1.13 and 3.3] that (ln ln n) (φ_n - [ln n - ln ln ln n - ln(d - 1)]) has a nondegenerate limiting distribution, suggesting that the limiting distribution might be that of - G, where G has a Gumbel distribution with location - ln[(d - 1)!]/(d - 1) and scale 1/(d - 1). In the present extended abstract we outline a proof of a Berry-Esseen-type theorem for this convergence in distribution, thereby establishing a very sharp result for φ_n.

For $d\ge2$ and iid $d$-dimensional observations $X^{(1)},X^{(2)},\dots$ with independent Exponential$(1)$ coordinates, we revisit the study by Fill and Naiman (Electron. J. Probab., 2020) of the boundary (relative to the closed positive orthant), or "frontier", $F_n$ of the closed Pareto record-setting (RS) region \[ \mbox{RS}_n:=\{0\le x\in{\mathbb R}^d:x\not\prec X^{(i)}\mbox{\ for all $1\le i\le n$}\} \] at time $n$, where $0\le x$ means that $0\le x_j$ for $1\le j\le d$ and $x\prec y$ means that $x_j0$ and $c_n\to\infty$ we have \[ {\mathbb P}(F_n^- -\ln n\in (-(2+\varepsilon)\ln\ln\ln n,c_n))\to 1 \] (describing typical behavior) and almost surely \[ \limsup \frac{F_n^- - \ln n}{\ln \ln n} \le 0 \quad \mbox{and} \quad \liminf \frac{F_n^- - \ln n}{\ln \ln \ln n} \in [-2, -1]. \] In this paper we use the theory of generators (minima of $F_n$) together with the first- and second-moment methods to improve considerably the trailing-point location results to \[ F_n^- - (\ln n - \ln \ln \ln n) \overset{\mathrm{P}}{\longrightarrow} - \ln(d - 1) \] (describing typical behavior) and, for $d \ge 3$, almost surely \begin{align*} &\limsup [F_n^- - (\ln n - \ln \ln \ln n)] \leq -\ln(d - 2) + \ln 2 \\ \mbox{and }&\liminf [F_n^- - (\ln n - \ln \ln \ln n)] \ge - \ln d - \ln 2. \end{align*}

We give upper and lower asymptotic bounds for the left tail and for the right tail of the continuous limiting QuickSort density f that are nearly matching in each tail. The bounds strengthen results from a paper of Svante Janson (2015) concerning the corresponding distribution function F. Furthermore, we obtain similar upper bounds on absolute values of derivatives of f of each order.

For many probability distributions of interest, it is quite difficult to obtain samples efficiently. Often, Markov chains are employed to obtain approximately random samples from these distributions. The primary drawback to traditional Markov chain methods is that the mixing time of the chain is usually unknown, which makes it impossible to determine how close the output samples are to having the target distribution. The authors present a novel protocol, the randomness recycler (RR), that overcomes this difficulty. Unlike classical Markov chain approaches, an RR-based algorithm creates samples drawn exactly from the desired distribution. Other perfect sampling methods such as coupling from the past, use existing Markov chains, but RR does not use the traditional Markov chain at all. While by no means universally useful, RR does apply to a wide variety of problems. In restricted instances of certain problems, it gives the first expected linear time algorithms for generating samples. The authors apply RR to self-organizing lists, the Ising model, random independent sets, random colorings, and the random cluster model.

For a large class of examples arising in statistical ph~ics known as attnxtiue spin @ems (e.g., the Ising model), one seeks to sample from a probability distribution T on an enormously large state space, but elementary sampling is ruled out by the infeaaibility of calculating an appropriate normalizing constant.The same difficulty arises in computer science problems where one seeks to sample randomly from a large finite distributive lattice whose precise size cannot be ascertained in any reasonable amount of time.The Markov chain Monte Carlo (MCMC) approximate sampling approach to such a problem is to construct and run "for a long time" a Markov chain with long-run distribution r.But determining how long is long enough to get a good approximation can be both analytically and empirically difncult.Recently, Jim Propp and David Wilson have devised an ingenious and efficient algorithm to use the same Markov chains to produce per$xt(i.e., exact) samples from T. However, the nmning time of their algorithm is an unbounded random wuiable whoee order of magnitude is typically unknown a priori and which is not independent of the state sampled, so a naive user with limited patience who aborts a long run of the algorithm will introduce bias.We present a new algorithm which (1) again uses the same Markov chains to produce perfect samples from n, but is baaed on a different idea (namely, acceptance/rejection sampling); and (2) eliminates user-impatience bias.Like the PropP-Wilson algorithm, the new algorithm applies to a general class of suitably monotone chains, and also (with modification) to "anti-monotone" chains.When the chain is reversible, naive implementation of the algorithm uaw fewer transitions but more epaoe than Propp-Wilson.When finetuned and applied with the aid of a typical peeudorandom number generator to an attractive spin system on n sits "Waearch supported by NSF grants DMS-93-11367 and DMS-9626756.Mailing addIees James Allen Fti, The Johns Hop kins Univemity, Department of Mathematical Sciences, Whitahead Hall, 34th and Charles Stm%s, Baltimore, MD 2121S-26S2.Email addr~jirn6110jhu.edu.using a random site updating Gibbs sampler whose mixing time T is polynomial in n, the algorithm runs in time of the same order (bound) as Propp-WMm [expectation O(T log n)] and uaee only logarithmically more space [expectation O(n log n), VS.O(n) fir Propp-Whn].If truly random bits are used instead, then the time and space bounda for a fine-tuned implementation of the new algorithm are no worse than those for Propp-Wilson.The full paper is available on the author's web PEW% at the Um http: //WU .mts.jhu.edul-f ill/

We derive upper and lower bounds on total variation distance to stationarity for the distribution of search cost under the move-to-front (MTF) rule for self-organizing lists with i.i.d. record requests. These enable us to obtain sharp rates of convergence for several standard examples of weights, including Zipf's law and geometric weights, as the length of the list becomes large. The upper bound also shows that a number of moves of the order of the length of the list is uniformly sufficient for near-stationarity over all choices of weights. Concerning the stationary search cost distribution itself, we use a representation obtained by considering the continuized MTF Markov chain to derive, for each of the standard examples, the asymptotic distribution for long lists.

The Radon transform on $\mathbb{Z}_n $ that arises in the analysis of directional data and circular time series replaces each value $f(k)$ of a function f by the average value of f over the translate of a set S by k. For general S the discrete Fourier transform is used to characterize the null space and range of the transform and to calculate a (generalized) inverse transform. Explicit forms of the coefficients in the inversion formula are obtained in the two cases $S = \{ - r, + r\} $ and the symmetric moving average $S = \{ - r, \ldots , + r\} $. We show that the proportion of all choices S of size t giving invertible transforms is nearly unity when min $(t,n - t)$ is large.