 |
|
|
| | | | | |
|
|
|
|
|
Martingales and Profile of Binary Search Trees
|
B. Chauvin, Université de Versailles, France
T. Klein, Université de Versailles, France
J.-F. Marckert, Université de Versailles, France
A Rouault, Université de Versailles, France
|
Abstract
We are interested in the asymptotic analysis of the binary search tree (BST) under the random permutation model.
Via an embedding in a continuous time model,
we get new results, in particular
the asymptotic behavior of the profile.
|
Full text: PDF
Pages: 420-435
Published on: June 6, 2005
|
Bibliography
TITLE HERE
| Aldous, David; Shields, Paul. A
diffusion
limit for a class of randomly-growing binary trees. Probab. Theory
Related
Fields 79 (1988), no. 4, 509--542. MR0966174
(90k:60052) |
| Athreya, Krishna B.; Ney, Peter E.
Branching
processes. Die Grundlehren der mathematischen Wissenschaften, Band 196.
Springer-Verlag,
New York-Heidelberg, 1972. xi+287 pp. MR0373040
(51 #9242) |
| Bertoin, Jean. The asymptotic behavior of
fragmentation
processes. J. Eur. Math. Soc. (JEMS) 5 (2003), no. 4,
395--416.
MR2017852 |
|
Bertoin, Jean and Rouault, Alain. Discretization methods for homogeneous fragmentations. Preprint available at http://front.math.ucdavis.edu/math.PR/0409545, September 2004. Math review number not available
|
| Biggins, J. D. Uniform convergence of
martingales
in the branching random walk. Ann. Probab. 20 (1992),
no.
1, 137--151. MR1143415
(93b:60094) |
| Biggins, J. D. How fast does a general
branching
random walk spread?
Classical and modern branching processes (Minneapolis,
MN, 1994), 19--39, IMA Vol. Math. Appl., 84, Springer, New
York,
1997. MR1601689
(99c:60186) |
| Biggins, J. D.; Grey, D. R. A
note on the
growth of random trees. Statist. Probab. Lett. 32 (1997),
no. 4, 339--342. MR1602191
(98j:60116) |
| Chauvin, Brigitte; Drmota, Michael;
Jabbour-Hattab,
Jean. The profile of binary search trees. Ann. Appl. Probab.
11 (2001), no. 4, 1042--1062. MR1878289
(2002k:60088) |
|
Chauvin, Brigitte; Rouault, Alain. Connecting yule process, bisection and binary search trees via martingales. Journal of the Iranian Statistical Society}, 3(2):89--116, 2004. available at http://front.math.ucdavis.edu/math.PR/0410318.Math review number not available
|
| Devroye, Luc. Branching processes and
their applications
in the analysis of tree structures and tree algorithms.
Probabilistic
methods for algorithmic discrete mathematics, 249--314, Algorithms
Combin., 16, Springer, Berlin, 1998. MR1678582
(2000m:60099) |
| Devroye, Luc; Fill, James Allen; Neininger,
Ralph. Perfect simulation from the Quicksort limit distribution. Electron.
Comm. Probab. 5 (2000), 95--99 (electronic). MR1781844
(2001e:68043) |
| Drmota, Michael. Stochastic analysis of
tree-like
data structures. Stochastic analysis with applications to mathematical
finance. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 460
(2004), no. 2041, 271--307. MR2052264
(2005a:68051) |
| Fill, James Allen; Janson, Svante.
Approximating
the limiting Quicksort distribution. Analysis of algorithms (Krynica
Morska,
2000). Random Structures Algorithms 19 (2001), no.
3-4, 376--406.
MR1871560
(2002k:68042) |
| Fill, James Allen; Janson, Svante.
Quicksort
asymptotics. Analysis of algorithms. J. Algorithms 44 (2002),
no. 1, 4--28. MR1932675
(2003m:68032) |
| Hwang, Hsien-Kuei. Asymptotic expansions
for the
Stirling numbers of the first kind. J. Combin. Theory Ser. A 71
(1995), no. 2, 343--351. MR1342456
(96k:11019) |
| Jabbour-Hattab, Jean. Martingales and
large deviations
for binary search trees. Random Structures Algorithms 19 (2001),
no. 2, 112--127. MR1848787
(2002f:68023) |
| Kingman, J. F. C. The coalescent. Stochastic
Process.
Appl. 13 (1982), no. 3, 235--248. MR0671034
(84a:60079) |
| Kolchin, V. F. Random graphs.
Encyclopedia of Mathematics
and its Applications, 53. Cambridge University Press, Cambridge,
1999. xii+252 pp. ISBN: 0-521-44081-5 MR1728076
(2001h:60015) |
| Kolchin, V. F. A certain problem of the
disbribution
of particles in cells, and cycles of random permutation. (Russian) Teor.
Verojatnost. i Primenen. 16 1971 67--82. MR0283840
(44 #1070) |
|
Krapivsky, P.L. and Majumdar Satya N. Travelling waves, front selection, and exact nontrivial exponents in random fragmentation problem. Phys. Review Letters, 85(26):5492--5495, (2000).
|
| Kyprianou, A. E. A note on branching
Lévy
processes. Stochastic Process. Appl. 82 (1999), no. 1,
1--14.
MR1695066
(2000g:60143) |
| Mahmoud, Hosam M. Evolution of random
search trees.
Wiley-Interscience Series in Discrete Mathematics and Optimization. A
Wiley-Interscience
Publication.
John Wiley & Sons, Inc., New York, 1992. xii+324
pp. ISBN: 0-471-53228-2 MR1140708
(93f:68045) |
| Neininger, Ralph; Rüschendorf,
Ludger.
A general limit theorem for recursive algorithms and combinatorial
structures.
Ann. Appl. Probab. 14 (2004), no. 1, 378--418. MR2023025
(2004m:60046) |
| Petrov, V. V. Sums of independent random
variables.
Translated from the Russian by A. A. Brown. Ergebnisse der Mathematik
und
ihrer Grenzgebiete, Band 82.
Springer-Verlag, New York-Heidelberg,
1975. x+346 pp. MR0388499
(52 #9335) |
| Pittel, Boris. On growing random binary
trees. J.
Math. Anal. Appl. 103 (1984), no. 2, 461--480. MR0762569
(86c:05101) |
|
Reed, Bruce.The height of a random binary search tree. Journal of the ACM, 50(3):306--332, 2003. Math review number not available.
|
| Robson, J. M. Constant bounds on the
moments of the
height of binary search trees. Theoret. Comput. Sci. 276 (2002),
no. 1-2, 435--444. MR1896364
(2002m:68022) |
| Rösler, Uwe. A limit theorem for
"Quicksort".
RAIRO Inform. Théor. Appl. 25 (1991), no.
1, 85--100.
MR1104413
(92f:68028) |
| Rösler, U. On the analysis of
stochastic divide
and conquer algorithms. Average-case analysis of algorithms (Princeton,
NJ, 1998). Algorithmica 29 (2001), no. 1-2, 238--261. MR1887306
(2003b:68217) |
| Tavaré, Simon. The birth process
with immigration,
and the genealogical structure of large populations. J. Math. Biol.
25 (1987), no. 2, 161--168. MR0896431
(89e:92042) |
| Uchiyama, Kohei. Spatial growth of a
branching process
of particles living in R^d. Ann. Probab. 10 (1982),
no. 4, 896--918. MR0672291
(84d:60127) |
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context