| Título: | A Gaussian limit process for optimal FIND algorithms |
| Autores: |
Sulzbach, Henning; INRIA Paris-Rocquencourt Neininger, Ralph; Goethe University Frankfurt Drmota, Michael; TU Vienna |
| Fecha: | 2014-01-02 |
| Publicador: | Electronic journal of probability |
| Fuente: |
 |
| Tipo: | Peer-reviewed Article |
| Tema: |
FIND algorithm, Quickselect, complexity, key comparisons, functional limit theorem, contraction method, Gaussian process 60F17; 68P10; 60G15; 60C05; 68Q25 |
| Descripción: | We consider versions of the FIND algorithm where the pivot element used is the median of a subset chosen uniformly at random from the data. For the median selection we assume that subsamples of size asymptotic to $c \cdot n^\alpha$ are chosen, where $0< \alpha \leq \frac{1}{2}$, $c>0$ and $n$ is the size of the data set to be split. We consider the complexity of FIND as a process in the rank to be selected and measured by the number of key comparisons required. After normalization we show weak convergence of the complexity to a centered Gaussian process as $n \to \infty$, which depends on $\alpha$. The proof relies on a contraction argument for probability distributions on càdlàg functions. We also identify the covariance function of the Gaussian limit process and discuss path and tail properties. |
| Idioma: | Inglés |
1 Lévy Classes and Self-Normalization por Khoshnevisan, Davar; University of Utah | 6 Time-Space Analysis of the Cluster-Formation in Interacting Diffusions por Fleischmann, Klaus; Weierstrass Institute for Applied Analysis and Stochastics,Greven, Andreas; Universitat Erlangen-Nurnberg |
2 Hausdorff Dimension of Cut Points for Brownian Motion por Lawler, Gregory F.; Duke University and Cornell University | 7 Conditional Moment Representations for Dependent Random Variables por Bryc, Wlodzimierz; University of Cincinnati |
3 Eigenvalue Expansions for Brownian Motion with an Application to Occupation Times por Bass, Richard F.; University of Washington,Burdzy, Krzysztof; University of Washington | 8 Almost Sure Exponential Stability of Neutral Differential Difference Equations with Damped Stochastic Perturbations por Liao, Xiao Xin; University of Strathclyde,Mao, Xuerong; University of Strathclyde |
4 Random Discrete Distributions Derived from Self-Similar Random Sets por Pitman, Jim; University of California, Berkeley,Yor, Marc; Université Pierre et Marie Curie | 9 Quantitative Bounds for Convergence Rates of Continuous Time Markov Processes por Roberts, Gareth O.; University of Cambridge,Rosenthal, Jeffrey S.; University of Toronto |
5 A Microscopic Model for the Burgers Equation and Longest Increasing Subsequences por Seppäläinen, Timo; Iowa State University | 10 Metastability of the Three Dimensional Ising Model on a Torus at Very Low Temperatures por Ben Arous, Gérard; Ecole Normale Supérieure,Cerf, Raphaël; Université Paris Sud |