We study the additive functional $X_n(alpha)$ on conditioned Galton-Watson trees given, for arbitrary complex $alpha$, by summing the $alpha$th power of all subtree sizes. Allowing complex $alpha$ is advantageous, even for the study of real $alpha$,
since it allows us to use powerful results from the theory of analytic functions in the proofs. For $Realpha < 0$, we prove that $X_n(alpha)$, suitably normalized, has a complex normal limiting distribution; moreover, as processes in $alpha$, the weak convergence holds in the space of analytic functions in the left half-plane. We establish, and prove similar process-convergence extensions of, limiting distribution results for $alpha$ in various regions of the complex plane. We focus mainly on the case where $Realpha > 0$, for which $X_n(alpha)$, suitably normalized, has a limiting distribution that is not normal but does not depend on the offspring distribution $xi$ of the conditioned Galton-Watson tree, assuming only that $E[xi] = 1$ and $0 < mathrm{Var} [xi] < infty$. Under a weak extra moment assumption on $xi$, we prove that the convergence extends to moments, ordinary and absolute and mixed, of all orders. At least when $Realpha > frac12$, the limit random variable $Y(alpha)$ can be expressed as a function of a normalized Brownian excursion.
We substantially refine asymptotic logarithmic upper bounds produced by Svante Janson (2015) on the right tail of the limiting QuickSort distribution function $F$ and by Fill and Hung (2018) on the right tails of the corresponding density $f$ and of
the absolute derivatives of $f$ of each order. For example, we establish an upper bound on $log[1 - F(x)]$ that matches conjectured asymptotics of Knessl and Szpankowski (1999) through terms of order $(log x)^2$; the corresponding order for the Janson (2015) bound is the lead order, $x log x$. Using the refined asymptotic bounds on $F$, we derive right-tail large deviation (LD) results for the distribution of the number of comparisons required by QuickSort that substantially sharpen the two-sided LD results of McDiarmid and Hayward (1996).
We establish a fundamental property of bivariate Pareto records for independent observations uniformly distributed in the unit square. We prove that the asymptotic conditional distribution of the number of records broken by an observation given that
the observation sets a record is Geometric with parameter 1/2.
We present, (partially) analyze, and apply an efficient algorithm for the simulation of multivariate Pareto records. A key role is played by minima of the record-setting region (we call these generators) each time a new record is generated, and two h
ighlights of our work are (i) efficient dynamic maintenance of the set of generators and (ii) asymptotic analysis of the expected number of generators at each time.
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{R
S}_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$.
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 bounds on absolute values of derivatives of f of each order.
As proved by Regnier and Rosler, the number of key comparisons required by the randomized sorting algorithm QuickSort to sort a list of $n$ distinct items (keys) satisfies a global distributional limit theorem. Fill and Janson proved results about th
e limiting distribution and the rate of convergence, and used these to prove a result part way towards a corresponding local limit theorem. In this paper we use a multi-round smoothing technique to prove the full local limit theorem.
We develop the theory of strong stationary duality for diffusion processes on compact intervals. We analytically derive the generator and boundary behavior of the dual process and recover a central tenet of the classical Markov chain theory in the di
ffusion setting by linking the separation distance in the primal diffusion to the absorption time in the dual diffusion. We also exhibit our strong stationary dual as the natural limiting process of the strong stationary dual sequence of a well chosen sequence of approximating birth-and-death Markov chains, allowing for simultaneous numerical simulations of our primal and dual diffusion processes. Lastly, we show how our new definition of diffusion duality allows the spectral theory of cutoff phenomena to extend naturally from birth-and-death Markov chains to the present diffusion context.
Wilfs Sixth Unsolved Problem asks for any interesting properties of the set of partitions of integers for which the (nonzero) multiplicities of the parts are all different. We refer to these as emph{Wilf partitions}. Using $f(n)$ to denote the number
of Wilf partitions, we establish lead-order asymptotics for $ln{f(n)}$.
Most previous studies of the sorting algorithm QuickSort have used the number of key comparisons as a measure of the cost of executing the algorithm. Here we suppose that the n independent and identically distributed (i.i.d.) keys are each represente
d as a sequence of symbols from a probabilistic source and that QuickSort operates on individual symbols, and we measure the execution cost as the number of symbol comparisons. Assuming only a mild tameness condition on the source, we show that there is a limiting distribution for the number of symbol comparisons after normalization: first centering by the mean and then dividing by n. Additionally, under a condition that grows more restrictive as p increases, we have convergence of moments of orders p and smaller. In particular, we have convergence in distribution and convergence of moments of every order whenever the source is memoryless, that is, whenever each key is generated as an infinite string of i.i.d. symbols. This is somewhat surprising; even for the classical model that each key is an i.i.d. string of unbiased (fair) bits, the mean exhibits periodic fluctuations of order n.
