Random sequential bisection and its associated binary tree (Q1091019)

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.