Random sequential bisection and its associated binary tree

DOI10.1007/BF02491450MaRDI QIDQ1091019zbMATH OpenOpenAlexFDO

Authors Masaaki Sibuya, Yoshiaki Itoh

Publication date 1987

Published in Annals of the Institute of Statistical Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02491450

zbMATH Keywords

random packing problemrandom sequential bisection

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Central limit and other weak theorems (60F05)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4140913
• Limiting distributions of two random sequences
• Random dissections and branching processes
• On random split of the segment
• Splitting intervals

Cites work

• A note on the height of binary search trees
• A proof of Kakutani's conjecture on random subdivision of longest intervals
• Entropy and maximal spacings for random partitions
• scientific article; zbMATH DE number 3171475 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3613892 (Why is no real title available?)
• scientific article; zbMATH DE number 3396865 (Why is no real title available?)
• scientific article; zbMATH DE number 3184376 (Why is no real title available?)
• On growing random binary trees
• On the minimum of gaps generated by one-dimensional random packing
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• The asymptotic behavior of spacings under Kakutani's model for interval subdivision

Cited in

(17)

• Size-biased and conditioned random splitting trees
• Normal limiting distribution of the size of binary interval trees
• Fragment size distributions in random fragmentations with cutoff
• Weak convergence results for the Kakutani interval splitting procedure.
• One-sided variations on binary search trees
• Paths in \(m\)-ary interval trees
• Probabilistic analysis of maximal gap and total accumulated length in interval division
• The random threshold and the bisection
• Random bisection and evolutionary walks
• scientific article; zbMATH DE number 2127735 (Why is no real title available?)
• scientific article; zbMATH DE number 4140913 (Why is no real title available?)
• One-sided variations on interval trees
• Statistical aspects of random fragmentations
• On Random Fragmentations Arising From Binary Splitting
• Moments of a non‐homogenous bi‐variate fragmentation process using integral equations tools
• Limiting distributions of two random sequences
• The size of random fragmentation trees

This page was built for publication: Random sequential bisection and its associated binary tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091019)