Random sequential bisection and its associated binary tree

Summary Random sequential bisection is a process to divide a given interval into two, four, eight, ... parts at random. Each division point is uniformly distributed on the interval and conditionally independent of the others. To study the asymptotic behavior of the lengths of subintervals in random seqential bisection, the associated binary tree is introduced. The number of internal or external nodes of the tree is asymptotically normal. The levels of the lowest and the highest external nodes are bounded with probability one or with probability increasing to one as the number of nodes increases to infinity. The associated binary tree is closely related to random binary tree which arises in computer algorithms, such as binary search tree and quicksort, and one-dimensional packing or the parking problem.