Process convergence for the complexity of radix selection on Markov sources. (English) Zbl 1405.60042
Summary: A fundamental algorithm for selecting ranks from a finite subset of an ordered set is Radix Selection. This algorithm requires the data to be given as strings of symbols over an ordered alphabet, e.g., binary expansions of real numbers. Its complexity is measured by the number of symbols that have to be read. In this paper the model of independent data identically generated from a Markov chain is considered.
The complexity is studied as a stochastic process indexed by the set of infinite strings over the given alphabet. The orders of mean and variance of the complexity and, after normalization, a limit theorem with a centered Gaussian process as limit are derived. This implies an analysis for two standard models for the ranks: uniformly chosen ranks, also called grand averages, and the worst case rank complexities which are of interest in computer science.
For uniform data and the asymmetric Bernoulli model (i.e. memoryless sources), we also find weak convergence for the normalized process of complexities when indexed by the ranks while for more general Markov sources these processes are not tight under the standard normalizations.
The complexity is studied as a stochastic process indexed by the set of infinite strings over the given alphabet. The orders of mean and variance of the complexity and, after normalization, a limit theorem with a centered Gaussian process as limit are derived. This implies an analysis for two standard models for the ranks: uniformly chosen ranks, also called grand averages, and the worst case rank complexities which are of interest in computer science.
For uniform data and the asymmetric Bernoulli model (i.e. memoryless sources), we also find weak convergence for the normalized process of complexities when indexed by the ranks while for more general Markov sources these processes are not tight under the standard normalizations.
MSC:
| 60F17 | Functional limit theorems; invariance principles |
| 60G15 | Gaussian processes |
| 68P10 | Searching and sorting |
| 60C05 | Combinatorial probability |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
radix selection; Gaussian process; Markov source model; complexity; weak convergence; probabilistic analysis of algorithmsReferences:
| [1] | Billingsley, P., (Convergence of Probability Measures. Convergence of Probability Measures, Wiley Series in Probability and Statistics: Probability and Statistics (1999), A Wiley-Interscience Publication, John Wiley & Sons, Inc.: A Wiley-Interscience Publication, John Wiley & Sons, Inc. New York) · Zbl 0944.60003 |
| [2] | Boucheron, S.; Lugosi, G.; Massart, P., Concentration Inequalities: A Nonasymptotic Theory of Independence (2013), Oxford University Press · Zbl 1279.60005 |
| [3] | Broutin, N.; Neininger, R.; Sulzbach, H., A limit process for partial match queries in random quadtrees and 2-d trees, Ann. Appl. Probab., 23, 2560-2603 (2013) · Zbl 1358.68080 |
| [4] | Broutin, N.; Sulzbach, H., The dual tree of a recursive triangulation of the disk, Ann. Probab., 43, 738-781 (2015) · Zbl 1355.60014 |
| [5] | Cesaratto, E.; Vallée, B., Gaussian distribution of trie depth for strongly tame sources, Combin. Probab. Comput., 24, 54-103 (2015) · Zbl 1371.68056 |
| [6] | Chauvin, B.; Klein, T.; Marckert, J.-F.; Rouault, A., Martingales and profile of binary search trees, Electron. J. Probab., 10, 420-435 (2005) · Zbl 1109.60059 |
| [7] | Clément, J.; Fill, J. A.; Nguyen Thi, T. H.; Vallée, B., Towards a realistic analysis of the QuickSelect algorithm, Theory Comput. Syst., 58, 528-578 (2016) · Zbl 1341.68035 |
| [8] | Clément, J.; Flajolet, P.; Vallée, B., Dynamical sources in information theory: a general analysis of trie structures, Average-case Analysis of Algorithms (Princeton, NJ, 1998). Average-case Analysis of Algorithms (Princeton, NJ, 1998), Algorithmica, 29, 307-369 (2001) · Zbl 1035.68039 |
| [9] | Devroye, L., (Lecture Notes on Bucket Algorithms. Lecture Notes on Bucket Algorithms, Progress in Computer Science, vol. 6 (1986), Birkhäuser Boston, Inc.: Birkhäuser Boston, Inc. Boston, MA) · Zbl 0644.68086 |
| [10] | Devroye, L., A study of trie-like structures under the density model, Ann. Appl. Probab., 2, 402-434 (1992) · Zbl 0758.68051 |
| [11] | Devroye, L., On the probabilistic worst-case time of “find”, Mathematical Analysis of Algorithms. Mathematical Analysis of Algorithms, Algorithmica, 31, 291-303 (2001) · Zbl 1021.68030 |
| [12] | Drmota, M.; Janson, S.; Neininger, R., A functional limit theorem for the profile of search trees, Ann. Appl. Probab., 18, 288-333 (2008) · Zbl 1143.68019 |
| [13] | Falconer, K., (The Geometry of Fractal Sets. The Geometry of Fractal Sets, Cambridge Tracts in Mathematics, vol. 85 (1986), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0587.28004 |
| [14] | Fill, J. A.; Matterer, J., QuickSelect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find, Combin. Probab. Comput., 23, 805-828 (2014) · Zbl 1329.60082 |
| [15] | Fill, J. A.; Nakama, T., Analysis of the expected number of bit comparisons required by Quickselect, Algorithmica, 58, 730-769 (2010) · Zbl 1202.68128 |
| [16] | Fill, J. A.; Nakama, T., Distributional convergence for the number of symbol comparisons used by QuickSelect, Adv. Appl. Probab., 45, 425-450 (2013) · Zbl 1278.68354 |
| [17] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001 |
| [18] | Grincevičjus, A. K., The continuity of the distribution of a certain sum of dependent variables that is connected with independent walks on lines, Theor. Probab. Appl., 19, 163-168 (1974) · Zbl 0321.60053 |
| [19] | Grübel, R., On the silhouette of binary search trees, Ann. Appl. Probab., 19, 1781-1802 (2009) · Zbl 1203.60040 |
| [20] | Gr��bel, R.; Rösler, U., Asymptotic distribution theory for Hoare’s selection algorithm, Adv. Appl. Probab., 28, 252-269 (1996) · Zbl 0853.60033 |
| [21] | Hu, T. C.; Móricz, F.; Taylor, R. L., Strong laws of large numbers for arrays of rowwise independent random variables, Acta Math. Hungar., 54, 153-162 (1989) · Zbl 0685.60032 |
| [22] | K. Hun, B. Vallée, Typical depth of a digital search tree built on a general source, ANALCO14—Meeting on Analytic Algorithmics and Combinatorics, 2014, pp. 1-15.; K. Hun, B. Vallée, Typical depth of a digital search tree built on a general source, ANALCO14—Meeting on Analytic Algorithmics and Combinatorics, 2014, pp. 1-15. · Zbl 1430.68044 |
| [23] | P. Jacquet, M. Régnier, Normal limit distribution for the size and the external path length of tries, INRIA Research Report 827, 1988.; P. Jacquet, M. Régnier, Normal limit distribution for the size and the external path length of tries, INRIA Research Report 827, 1988. |
| [24] | Janson, S., Renewal theory in the analysis of tries and strings, Theoret. Comput. Sci., 416, 33-54 (2012) · Zbl 1236.60085 |
| [25] | Kirschenhofer, P.; Prodinger, H.; Szpankowski, W., On the variance of the external path length in a symmetric digital trie, Combinatorics and Complexity (Chicago, IL, 1987). Combinatorics and Complexity (Chicago, IL, 1987), Discrete Appl. Math., 25, 129-143 (1989) · Zbl 0685.68059 |
| [26] | Knuth, D. E., The Art of Computer Programming. Vol. 3, Sorting and Searching (1998), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0895.65001 |
| [27] | Leckey, K.; Neininger, R.; Sulzbach, H., Analysis of radix selection on Markov sources, (Bousquet-Mélou, M.; Soria, M., Proceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. Proceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, DMTCS-HAL Proceedings Series (2014)), 253-264 · Zbl 1355.60031 |
| [28] | K. Leckey, R. Neininger, W. Szpankowski, A limit theorem for radix sort and tries with markovian input, 2015, submitted for publication. Available at arXiv:1505.07321; K. Leckey, R. Neininger, W. Szpankowski, A limit theorem for radix sort and tries with markovian input, 2015, submitted for publication. Available at arXiv:1505.07321 |
| [29] | Mahmoud, H. M.; Flajolet, P.; Jacquet, P.; Régnier, M., Analytic variations on bucket selection and sorting, Acta Inform., 36, 735-760 (2000) · Zbl 0958.68056 |
| [30] | Neininger, R.; Rüschendorf, L., A general limit theorem for recursive algorithms and combinatorial structures, Ann. Appl. Probab., 14, 378-418 (2004) · Zbl 1041.60024 |
| [31] | Neininger, R.; Sulzbach, H., On a functional contraction method, Ann. Probab., 43, 1777-1822 (2015) · Zbl 1372.60045 |
| [32] | Ragab, M.; Rösler, U., The Quicksort process, Stoch. Process. Appl., 124, 1036-1054 (2014) · Zbl 1306.60011 |
| [33] | Rösler, U.; Rüschendorf, L., The contraction method for recursive algorithms, Algorithmica, 29, 3-33 (2001) · Zbl 0967.68166 |
| [34] | Sulzbach, H.; Neininger, R.; Drmota, M., A Gaussian limit process for optimal FIND algorithms, Electron. J. Probab., 19 (2014), 28pp · Zbl 1358.68085 |
| [35] | Szpankowski, W., (Average Case Analysis of Algorithms on Sequences, With a Foreword By Philippe Flajolet. Average Case Analysis of Algorithms on Sequences, With a Foreword By Philippe Flajolet, Wiley-Interscience Series in Discrete Mathematics and Optimization (2001), Wiley-Interscience: Wiley-Interscience New York) · Zbl 0968.68205 |
| [36] | Vallée, B.; Clément, J.; Fill, J. A.; Flajolet, P., The number of symbol comparisons in QuickSort and QuickSelect, (Automata, Languages and Programming. Part I. Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci., vol. 5555 (2009), Springer: Springer Berlin), 750-763 · Zbl 1248.68181 |
| [37] | Vervaat, W., On a stochastic difference equation and a representation of nonnegative infinitely divisible random variables, Adv. Appl. Probab., 4, 750-783 (1979) · Zbl 0417.60073 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
