Consider an interval of length which is cut into two halves of
length and , where is uniformly
distributed on . Next, each of these two fragments is cut
again into two parts (independently of the other and previous
cuts). After the -th step, there are fragments whose lengths
are correlated random variables. Given the initial length , the
Random Bisection Problem is to determine the probability
that each of the fragments is shorter (or equal)
than . The result (we want to present) says that there exists a
monotonically decreasing function such that
Interestingly, there is a close connection to the distribution of the
height of binary search trees. There we have with the same
function