Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations
151
0
0.0
(
0
)
Added by
James Allen Fill
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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).
rate research
Read More
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.
In a continuous-time setting, Fill (2010) proved, for a large class of probabilistic sources, that the number of symbol comparisons used by QuickSort, when centered by subtracting the mean and scaled by dividing by time, has a limiting distribution, but proved little about that limiting random variable Y -- not even that it is nondegenerate. We establish the nondegeneracy of Y. The proof is perhaps surprisingly difficult.
In this article we study the Dyson Bessel process, which describes the evolution of singular values of rectangular matrix Brownian motions, and prove a large deviation principle for its empirical particle density. We then use it to obtain the asymptotics of the so-called rectangular spherical integrals as $m,n$ go to infinity while $m/n$ converges.
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 represented 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.
In this paper we consider the first passage percolation with identical and independent exponentially distributions, called the Eden growth model, and we study the upper tail large deviations for the first passage time ${rm T}$. Our main results prove that for any $xi>0$ and $x eq 0$, $mathbb{P}({rm T}(0,nx)>n(mu+xi))$ decays as $exp{(-(2dxi +o(1))n)}$ with a time constant $mu$ and a dimension $d$. Moreover, we extend the result to stretched exponential distributions. On the contrary, we construct a continuous distribution with a finite exponential moment where the rate function does not exist.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
