A general limit theorem for recursive algorithms and combinatorial structures. (English) Zbl 1041.60024
Limit laws of vector-valued recursive equations \(X_n=\sum_{r=1} A_n^r X_{I_r^n}^r+b_n^n\) are proved via the contraction method. The Zolotarev \(\xi_s\)-metric provides under suitable conditions a limit law \(X\) of \(X_n\). In contrary to Mallows \(\ell_P\)-metrics the Zolotarev metrics include the normal law as limit law and also limit laws, when the accompanying stochastic fixed point equation is degenerate. This is achieved by an accompanying sequence of rvs satisfying approximately the recursion. The Zolotarev metric allows also local limit laws. Many examples show the strength of this approach.
Reviewer: Uwe Rösler (Kiel)
MSC:
| 60F05 | Central limit and other weak theorems |
| 68P10 | Searching and sorting |
| 60F25 | \(L^p\)-limit theorems |
Keywords:
contraction method; multivariate limit law; recursive structure; divide-and-conquer algorithm; Zolotarev metricReferences:
| [1] | Aho, A. V., Hopcroft, J. E. and Ullman, J. D. (1983). Data Structures and Algorithms . Addison–Wesley, Reading, MA. · Zbl 0487.68005 |
| [2] | Baeza-Yates, R. A. (1987). Some average measures in \(m\)-ary search trees. Inform. Process. Lett. 25 375–381. · Zbl 0653.68058 · doi:10.1016/0020-0190(87)90215-8 |
| [3] | Bai, Z.-D., Hwang, H.-K., Liang, W.-Q. and Tsai, T.-H. (2001). Limit theorems for the number of maxima in random samples from planar regions. Electron. J. Probab. 6 . · Zbl 0986.60007 |
| [4] | Bai, Z.-D., Hwang, H.-K. and Tsai, T.-H. (2002). Berry–Esseen bounds for the number of maxima in planar regions. Electron J. Probab. 8 . |
| [5] | Burton, R. and Rösler, U. (1995). An \(L_2\) convergence theorem for random affine mappings. J. Appl. Probab. 32 183–192. · Zbl 0816.60004 · doi:10.2307/3214928 |
| [6] | Chen, W.-M., Hwang, H.-K. and Chen, G.-H. (1999). The cost distribution of queue-mergesort, optimal mergesorts, and power-of-2 rules. J. Algorithms 30 423–448. · Zbl 0923.68045 · doi:10.1006/jagm.1998.0986 |
| [7] | Chern, H.-H. and Hwang, H.-K. (2001). Phase changes in random \(m\)-ary search trees and generalized quicksort. Random Structures Algorithms 19 316–358. · Zbl 0990.68052 · doi:10.1002/rsa.10005 |
| [8] | Chern, H.-H., Hwang, H.-K. and Tsai, T.-H. (2002). An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms. J. Algorithms 44 177–225. · Zbl 1030.68114 · doi:10.1016/S0196-6774(02)00208-0 |
| [9] | Cramer, M. (1997). Stochastic analysis of the merge–sort algorithm. Random Structures Algorithms 11 81–96. · Zbl 0882.68049 · doi:10.1002/(SICI)1098-2418(199708)11:1<81::AID-RSA3>3.0.CO;2-Q |
| [10] | Cramer, M. and Rüschendorf, L. (1995). Analysis of recursive algorithms by the contraction method. Athens Conference on Applied Probability and Time Series Analysis. Lecture Notes in Statist. 114 18–33. Springer, New York. · Zbl 0858.60036 |
| [11] | Devroye, L. (1991). Limit laws for local counters in random binary search trees. Random Structures Algorithms 2 303–315. · Zbl 0728.60027 · doi:10.1002/rsa.3240020305 |
| [12] | Devroye, L. (2003). Limit laws for sums of functions of subtrees of random binary search trees. SIAM J. Comput. 32 152–171. · Zbl 1029.68076 · doi:10.1137/S0097539701383923 |
| [13] | Dobrow, R. P. and Fill, J. A. (1999). Total path length for random recursive trees. Combin. Probab. Comput. 8 317–333. · Zbl 0946.05077 · doi:10.1017/S0963548399003855 |
| [14] | Fill, J. A. (1996). On the distribution of binary search trees under the random permutation model. Random Structures Algorithms 8 1–25. · Zbl 0840.60065 · doi:10.1002/(SICI)1098-2418(199601)8:1<1::AID-RSA1>3.0.CO;2-1 |
| [15] | Flajolet, P. and Golin, M. (1994). Mellin transforms and asymptotics. The mergesort recurrence. Acta Inform. 31 673–696. · Zbl 0818.68064 · doi:10.1007/BF01177551 |
| [16] | Flajolet, P., Gourdon, X. and Martínez, C. (1997). Patterns in random binary search trees. Random Structures Algorithms 11 223–244. · Zbl 0895.60010 · doi:10.1002/(SICI)1098-2418(199710)11:3<223::AID-RSA2>3.0.CO;2-2 |
| [17] | Geiger, J. (2000). A new proof of Yaglom’s exponential limit law. In Algorithms, Trees Combinatorics and Probability (D. Gardy and A. Mokkadem, eds.) 245–249. Birkhäuser, Basel. · Zbl 0967.60089 |
| [18] | Grübel, R. and Rösler, U. (1996). Asymptotic distribution theory for Hoare’s selection algorithm. Adv. in Appl. Probab. 28 252–269. · Zbl 0853.60033 · doi:10.2307/1427920 |
| [19] | Hubalek, F., Hwang, H.-K., Lew, W., Mahmoud, H. M. and Prodinger, H. (2002). A multivariate view of random bucket digital search trees. J. Algorithms 44 121–158. · Zbl 1010.68047 · doi:10.1016/S0196-6774(02)00210-9 |
| [20] | Hwang, H.-K. (1996). Asymptotic expansions of the mergesort recurrences. Acta Inform. 35 911–919. · Zbl 0910.68058 · doi:10.1007/s002360050147 |
| [21] | Hwang, H.-K. (1998). Limit theorems for mergesort. Random Structures Algorithms 8 319–336. · Zbl 0855.60024 · doi:10.1002/(SICI)1098-2418(199607)8:4<319::AID-RSA3>3.0.CO;2-0 |
| [22] | Hwang, H.-K. (2001). Lectures on asymptotic analysis given at McGill Univ., Montreal. |
| [23] | Hwang, H.-K. and Neininger, R. (2002). Phase change of limit laws in the quicksort recurrence under varying toll functions. SIAM J. Comput. 31 1687–1722. · Zbl 1008.68166 · doi:10.1137/S009753970138390X |
| [24] | Hwang, H.-K. and Tsai, T.-H. (2002). Quickselect and Dickman function. Combin. Probab. Comput. 11 353–371. · Zbl 1008.68044 · doi:10.1017/S0963548302005138 |
| [25] | Jacquet, P. and Régnier, M. (1988). Normal limiting distribution of the size and the external path length of tries. Technical Report RR-0827, INRIA-Rocquencourt. |
| [26] | Jacquet, P. and Régnier, M. (1988). Normal limiting distribution of the size of tries. In Performance ’ 87 209–223. North-Holland, Amsterdam. |
| [27] | Jacquet, P. and Szpankowski, W. (1995). Asymptotic behavior of the Lempel–Ziv parsing scheme and digital search trees. Theoret. Comput. Sci. 144 161–197. · Zbl 0874.68179 · doi:10.1016/0304-3975(94)00298-W |
| [28] | Kirschenhofer, P., Prodinger, H. and Szpankowski, W. (1989). On the balance property of Patricia tries: External path length viewpoint. Theoret. Comput. Sci. 68 1–17. · Zbl 0678.68042 · doi:10.1016/0304-3975(89)90115-1 |
| [29] | Kirschenhofer, P., Prodinger, H. and Szpankowski, W. (1989). On the variance of the external path length in a symmetric digital trie. Discrete Appl. Math. 25 129–143. · Zbl 0685.68059 · doi:10.1016/0166-218X(89)90050-4 |
| [30] | Kirschenhofer, P., Prodinger, H. and Szpankowski, W. (1994). Digital search trees again revisited: The internal path length perspective. SIAM J. Comput. 23 598–616. · Zbl 0819.68067 · doi:10.1137/S0097539790189368 |
| [31] | Knuth, D. E. (1973). The Art of Computer Programming 3 . Addison–Wesley, Reading, MA. · Zbl 0191.17903 |
| [32] | Kodaj, B. and Móri, T. F. (1997). On the number of comparisons in Hoare’s algorithm “FIND.” Studia Sci. Math. Hungar. 33 185–207. · Zbl 0910.60002 |
| [33] | Lew, W. and Mahmoud, H. M. (1994). The joint distribution of elastic buckets in multiway search trees. SIAM J. Comput. 23 1050–1074. · Zbl 0820.68037 · doi:10.1137/S009753979223023X |
| [34] | Mahmoud, H. M. (1992). Evolution of Random Search Trees . Wiley, New York. · Zbl 0762.68033 |
| [35] | Mahmoud, H. M. (2000). Sorting. A Distribution Theory . Wiley, New York. · Zbl 0985.68015 |
| [36] | Mahmoud, H. M. and Pittel, B. (1989). Analysis of the space of search trees under the random insertion algorithm. J. Algorithms 10 52–75. · Zbl 0685.68060 · doi:10.1016/0196-6774(89)90023-0 |
| [37] | Mahmoud, H. M. and Smythe, R. T. (1991). On the distribution of leaves in rooted subtrees of recursive trees. Ann. Appl. Probab. 1 406–418. JSTOR: · Zbl 0738.05034 · doi:10.1214/aoap/1177005874 |
| [38] | Mahmoud, H. M. and Smythe, R. T. (1992). Asymptotic joint normality of outdegrees of nodes in random recursive trees. Random Structures Algorithms 3 255–266. · Zbl 0767.05086 · doi:10.1002/rsa.3240030305 |
| [39] | Mahmoud, H. M., Modarres, R. and Smythe, R. T. (1995). Analysis of quickselect: An algorithm for order statistics. RAIRO Inform. Théor. Appl. 29 255–276. · Zbl 0838.68029 |
| [40] | Mahmoud, H. M., Smythe, R. T. and Szymański, J. (1993). On the structure of random plane-oriented recursive trees and their branches. Random Structures Algorithms 4 151–176. · Zbl 0773.05040 · doi:10.1002/rsa.3240040204 |
| [41] | Neininger, R. (2001). On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Structures Algorithms 19 498–524. · Zbl 0990.68054 · doi:10.1002/rsa.10010 |
| [42] | Neininger, R. and Rüschendorf, L. (1999). On the internal path length of \(d\)-dimensional quad trees. Random Structures Algorithms 15 25–41. · Zbl 0927.68030 · doi:10.1002/(SICI)1098-2418(199908)15:1<25::AID-RSA2>3.0.CO;2-R |
| [43] | Neininger, R. and Rüschendorf, L. (2002). Rates of convergence for Quicksort. J. Algorithms 44 52–62. · Zbl 1010.68049 · doi:10.1016/S0196-6774(02)00206-7 |
| [44] | Pittel, B. (1999). Normal convergence problem? Two moments and a recurrence may be the clues. Ann. Appl. Probab. 9 1260–1302. · Zbl 0960.60014 · doi:10.1214/aoap/1029962872 |
| [45] | Rachev, S. T. (1991). Probability Metrics and the Stability of Stochastic Models . Wiley, New York. · Zbl 0744.60004 |
| [46] | Rachev, S. T. and Rüschendorf, L. (1994). On the rate of convergence in the CLT with respect to the Kantorovich metric. In Probability in Banach Spaces (J. Hoffmann-Jorgensen, J. Kuelbs and M. B. Marcus, eds.) 9 193–207. Birkhäuser, Boston. · Zbl 0807.60030 |
| [47] | Rachev, S. T. and Rüschendorf, L. (1995). Probability metrics and recursive algorithms. Adv. in Appl. Probab. 27 770–799. · Zbl 0829.60094 · doi:10.2307/1428133 |
| [48] | Rösler, U. (1991). A limit theorem for “Quicksort.” RAIRO Inform. Théor. Appl. 25 85–100. · Zbl 0718.68026 |
| [49] | Rösler, U. (1992). A fixed point theorem for distributions. Stochastic Process. Appl. 42 195–214. · Zbl 0761.60015 · doi:10.1016/0304-4149(92)90035-O |
| [50] | Rösler, U. (2001). On the analysis of stochastic divide and conquer algorithms. Algorithmica 29 238–261. · Zbl 0967.68168 · doi:10.1007/s004530010066 |
| [51] | Rösler, U. and Rüschendorf, L. (2001). The contraction method for recursive algorithms. Algorithmica 29 3–33. · Zbl 0967.68166 · doi:10.1007/s004530010053 |
| [52] | Schachinger, W. (2001). Asymptotic normality of recursive algorithms via martingale difference arrays. Discrete Math. Theor. Comput. Sci. 4 363–397. · Zbl 0990.68187 |
| [53] | Senatov, V. V. (1980). Some uniform estimates of the convergence rate in the multidimensional central limit theorem. Theory Probab. Appl. 25 745–759. · Zbl 0471.60031 · doi:10.1137/1125089 |
| [54] | Smythe, R. T. and Mahmoud, H. M. (1994). A survey of recursive trees. Teor. Īmovīr. ta Mat. Statist. 51 1–29. · Zbl 0933.05038 |
| [55] | Szpankowski, W. (2001). Average Case Analysis of Algorithms on Sequences . Wiley, New York. · Zbl 0968.68205 |
| [56] | Tenenbaum, G. (1995). Introduction to Analytic and Probabilistic Number Theory . (C. B. Thomas, transl.). Cambridge Univ. Press. · Zbl 0831.11001 |
| [57] | Zolotarev, V. M. (1976). Approximation of the distributions of sums of independent random variables with values in infinite-dimensional spaces. Theory Probab. Appl. 21 721–737. · Zbl 0378.60003 · doi:10.1137/1121086 |
| [58] | Zolotarev, V. M. (1977). Ideal metrics in the problem of approximating distributions of sums of independent random variables. Theory Probab. Appl. 22 433–449. · Zbl 0385.60025 · doi:10.1137/1122056 |
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.
