{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:58Z","timestamp":1787323018079,"version":"build-2736575974"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>The Wiener index has been studied for simply generated random trees, nonplane unlabeled random trees, and a huge subclass of random grid trees containing random binary search trees, random median-of-(2k+1) search trees, random $m$-ary search trees, random quadtrees, random simplex trees, etc. An important class of random grid trees for which the Wiener index was not studied so far is random digital trees. In this work, we close this gap. More precisely, we derive asymptotic expansions of moments of the Wiener index and show that a central limit law for the Wiener index holds. These results are obtained for digital search trees and bucket versions as well as tries and PATRICIA tries. Our findings answer in the affirmative two questions posed by Neininger.<\/jats:p>","DOI":"10.1137\/140977989","type":"journal-article","created":{"date-parts":[[2015,3,24]],"date-time":"2015-03-24T16:20:56Z","timestamp":1427214056000},"page":"586-614","source":"Crossref","is-referenced-by-count":13,"title":["The Wiener Index of Random Digital Trees"],"prefix":"10.1137","volume":"29","author":[{"given":"Michael","family":"Fuchs","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chung-Kuei","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,3,24]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-006-0019-7"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1152413729"},{"key":"atypb3","first-page":"279","author":"Ali Khan T.","year":"2007","journal-title":"Discrete Math. Theor. Comput. Sci. Proc."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000106"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283954"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703424521"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.2307\/3215356"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010767517079"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1021\/ci980158r"},{"key":"atypb10","first-page":"211","volume":"10","author":"Entringer R. C.","year":"1994","journal-title":"Australas. J. Combin."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-009-0006-0"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030309"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00002-E"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/0215054"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.01.024"},{"key":"atypb16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/3763","volume":"21","author":"Fuchs M.","year":"2014","journal-title":"Electron. J. Combin."},{"key":"atypb17","unstructured":"A. Gut,\n                      Probability: A Graduate Course\n                      , Springer Texts in Statistics, Springer-Verlag, New York, 2005."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00213-8"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00210-9"},{"key":"atypb20","first-page":"103","volume":"12","author":"Hwang H.-K.","year":"2010","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb21","unstructured":"P. Jacquet and M. Re\u0301gnier,\n                      Normal Limiting Distribution of the Size and the External Path Length of Tries\n                      , Technical Report RR-0827, INRIA-Rocquencourt, 1988."},{"key":"atypb22","first-page":"209","author":"Jacquet P.","year":"1988","journal-title":"Amsterdam"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00298-W"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00167-9"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10074"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v9-1088"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90050-4"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90115-1"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790189368"},{"key":"atypb30","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming, Volume3:Searching and Sorting\n                      , Addison-Wesley, Reading, MA, 1973."},{"key":"atypb31","unstructured":"C.K. Lee,\n                      Probabilistic Analysis of Additive Shape Parameters in Random Digital Trees\n                      , Ph.D. thesis, National Chiao Tung University, 2014."},{"key":"atypb32","unstructured":"M. Mahmoud,\n                      Evolution of Random Search Trees\n                      , Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1992."},{"key":"atypb33","first-page":"253","volume":"13","author":"Mahmoud M.","year":"2002","journal-title":"Ann. Appl. Probab."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80012-6"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v16-889"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1339878805"},{"key":"atypb37","first-page":"8","volume":"4","author":"Munsonius G. O.","year":"2011","journal-title":"J. Appl. Probab."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005321"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1075828056"},{"key":"atypb40","unstructured":"M. Nguyen-The,\n                      Distribution de valuations sur les arbres\n                      , Ph.D. Thesis, LIX, Ecole polytechnique, 2003."},{"key":"atypb41","unstructured":"F. W. J. Olver\n                      Asymptotics and Special Functions\n                      , Academic Press, New York, 1974."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20027"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1214\/105051604000000071"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/070685531"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1109\/18.42197"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00306-4"},{"key":"atypb47","first-page":"363","volume":"4","author":"Schachinger W.","year":"2001","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb48","unstructured":"W. Szpankowski,\n                      Average Case Analysis of Algorithms on Sequences\n                      , Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2001."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1007\/s10440-006-9026-5"},{"key":"atypb50","first-page":"187","volume":"37","author":"Wagner S. G.","year":"2007","journal-title":"Australas. J. Combin."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.05.008"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1021\/ja01193a005"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140977989","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:22Z","timestamp":1787319442000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140977989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140977989"],"URL":"https:\/\/doi.org\/10.1137\/140977989","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}