Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA local limit theorem for Quicksort key comparisons via multi-round smoothing
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 the 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.
rate research
Read More
Using a recursive approach, we obtain a simple exact expression for the L^2-distance from the limit in Regniers (1989) classical limit theorem for the number of key comparisons required by QuickSort. A previous study by Fill and Janson (2002) using a similar approach found that the d_2-distance is of order between n^{-1} log n and n^{-1/2}, and another by Neininger and Ruschendorf (2002) found that the Zolotarev zeta_3-distance is of exact order n^{-1} log n. Our expression reveals that the L^2-distance is asymptotically equivalent to (2 n^{-1} ln n)^{1/2}.
We define a multi-group version of the mean-field spin model, also called Curie-Weiss model. It is known that, in the high temperature regime of this model, a central limit theorem holds for the vector of suitably scaled group magnetisations, that is the sum of spins belonging to each group. In this article, we prove a local central limit theorem for the group magnetisations in the high temperature regime.
The Robbins-Monro algorithm is a recursive, simulation-based stochastic procedure to approximate the zeros of a function that can be written as an expectation. It is known that under some technical assumptions, a Gaussian convergence can be established for the procedure. Here, we are interested in the local limit theorem, that is, quantifying this convergence on the density of the involved objects. The analysis relies on a parametrix technique for Markov chains converging to diffusions, where the drift is unbounded.
We consider a particle undergoing Brownian motion in Euclidean space of any dimension, forced by a Gaussian random velocity field that is white in time and smooth in space. We show that conditional on the velocity field, the quenched density of the particle after a long time can be approximated pointwise by the product of a deterministic Gaussian density and a spacetime-stationary random field $U$. If the velocity field is additionally assumed to be incompressible, then $Uequiv 1$ almost surely and we obtain a local central limit theorem.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
