Michael Drmota: The Random Bisection Problem and the Distribution of the Height of Binary Search Trees

Consider an interval of length $x$ which is cut into two halves of length $x_1 = Ux$ and $x_2 = (1-U)x$, where $U$ is uniformly distributed on $[0,1]$. Next, each of these two fragments is cut again into two parts (independently of the other and previous cuts). After the $k$-th step, there are $2^k$ fragments whose lengths are correlated random variables. Given the initial length $x$, the Random Bisection Problem is to determine the probability $P_k(x,\ell)$ that each of the $2^k$ fragments is shorter (or equal) than $\ell$. The result (we want to present) says that there exists a monotonically decreasing function $\Psi(y)$ such that

$$P_k(x,l) = \Psi\left(\frac{x}{\ell x_k}\right) + o(1),$$

where $x_k$ is a increasing sequence with $x_k= e^{k/c + \frac {3}{2(c-1)}\log k + O(1)}$ and $c=4.31107\ldots$ is the (largest real) solution of the equation $c\log \left( \frac{2e}c\right) = 1.$

Interestingly, there is a close connection to the distribution of the height $H_n$ of binary search trees. There we have with the same function $\Psi(y)$

$${\bf Pr}[H_{n}\le k] = \Psi(n/y_k) + o(1),$$

where $y_k$ is another increasing sequence with $y_k = x_k + O(1)$.

Back to the Index