Random sequential bisection and its associated binary tree. (English) Zbl 0622.60020

Let \(U_{d,2j}\), \(d\geq 1\), \(0\leq j<2^{d-1}\), be a family of independent random variables uniformly distributed over the unit interval. Let \(X_{00}=x>0\) and define recursively \(X_{d,2j}=X_{d- 1,j}U_{d,2j}\), \(X_{d,2j+1}=X_{d-1,j}(1-U_{d,2j})\), \(d\geq 1\). The \(X_{d,k}\) describe a random sequential bisection of the interval (0,x). The authors are concerned with various aspects of the asymptotic behaviour of the \(X_{d,k}\) as \(d\to \infty\). The relationship with the random packing problem is discussed in some detail.
Reviewer: M.Iosifescu


60D05 Geometric probability and stochastic geometry
60F05 Central limit and other weak theorems
Full Text: DOI


[1] Bánkövi, G. (1962). On gaps generated by a random space filling procedure,Publ. Math. Inst. Hungar. Acad. Sci.,7, 395-407. · Zbl 0113.34202
[2] Dvoretzky, A. and Robbins, H. (1964). On the ‘parking problem’,Publ. Math. Inst. Hungar. Acad. Sci.,9, 209-225. · Zbl 0251.60023
[3] Itoh, Y. (1980). On the minimum of gaps generated by one-dimensional random packing,J. Appl. Prob.,17, 134-144. · Zbl 0424.60014
[4] Knuth, D. E. (1973).The Art of Computer Programming, Vol. I,Fundamental Algorithms (2nd edition), Vol. IIISorting and Searching, Addison-Wesley. · Zbl 0302.68010
[5] Mahmoud, H. and Pittel, B. (1984). On the most probable shape of a binary search tree grown from a random permutation,SIAM J. Algebraic Discrete Methods,5, 69-81. · Zbl 0529.05002
[6] Pittel, B. (1984). On growing binary trees,J. Math. Analysis and Appl.,103, 461-480. · Zbl 0593.60014
[7] Rényi, A. (1958). On a one-dimensional problem concerning space-filling,Publ. Math. Inst. Hungar. Acad. Sci.,3, 109-127. · Zbl 0105.11903
[8] Robson, J. M. (1979). The height of binary search trees,The Australian Computer J.,11(4), 151-153.
[9] Lootgieter, J. C., No article title, Ann. Inst. Henri Poincaré, 13, 385-410 (1977)
[10] Zwet, W. R., No article title, Ann. Prob., 6, 133-137 (1978) · Zbl 0374.60036
[11] Slud, E., No article title, Zeit. Wahrscheinlichkeitsth., 41, 341-352 (1978) · Zbl 0353.60019
[12] Pyke, R., No article title, Ann. Prob., 8, 157-163 (1980) · Zbl 0426.60031
[13] Devroye, L., No article title, J. Ass. Comput. Math., 33, 489-498 (1986) · Zbl 0741.05062
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.