Randomly built binary search trees

Question

In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:

The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.

We define "randomly built binary search tree on $n$ keys" as:

a binary search tree that arises from inserting the keys in random order into an initially empty tree, where each of the $n!$ permutations of the input keys is equally likely.

In the proof, we defined some random variables:

Let $X_n$ denotes the height of a randomly built binary search tree on $n$ keys and the exponential height $Y_n = 2^{X_n}$. Of the $n$ keys, we choose one key as the root of the tree, and we let $R_n$ denotes the random variable that holds the position that this key would occupy if the set of keys were sorted (also know as 'rank' in the text). If we know that $R_n=i$, it follows that $Y_n=2\cdot max(Y_{i-1},Y_{n-1})$.

We also define indicator random variables $Z_{n,1}, Z_{n,2}, ..., Z_{n,n}$, $Z_{n,i} = I\{R_n=i\}$.

\begin{equation} \begin{split} E[Y_n] & = E\Big[\sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))\Big] \\ & = \sum_{i=1}^{n} E[Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))] && \text{(by linearity of expectation)}\\ & = \sum_{i=1}^{n} E[Z_{n,i}] E[(2\cdot max(Y_{i-1}, Y_{n-i}))] && \text{(by independence)}\\ \end{split} \end{equation}

I would like to ask why is the last equality correct? In other words, why can we assume independence of $Z_{n,i}$ and $max(Y_{i-1},Y_{n-i})$?

In the proof, there was a brief explanation:

Having chosen $R_n = i$, the left subtree (whose ranks are less than $i$. This subtree is just like any other randomly built binary search tree on $i-1$ keys. Other than the number of keys it contains, this subtree's structure is not affected at all by the choice of $R_n=i$, and hence the random variables $Y_{i-1}$ and $Z_{n,i}$ are independent. Likewise, the right subtree, whose exponential height is $Y_{n-i}$, is randomly built on the $n-i$ keys whose ranks are greater than $i$.

However, since $R_n$ does affect the number of keys $Y_{i-1}$ and $Y_{n-i}$ contain (as acknowledged by the explanation above), wouldn't it mean that $Y_{i-1}$ and $Y_{n-i}$ are dependent on $Z_{n,i}$?

A note regarding similar questions posted on CS stackexchange

I have read the answers for the following questions which are very similar to mine:

1. Proof that a randomly built binary search tree has logarithmic height
2. Average height of a BST with n Nodes.
3. Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

For 1 & 2, the question was a more general one which asked for an explanation for the entire proof. Also, the answer for both questions did not attempt to justify the independence and simply used the result.

For 3, the question was based on a MIT lecture, https://www.youtube.com/watch?v=vgELyZ9LXX4 and it lacked some of the details which I have included above. Also, the answer was also not clear.

Answer 1

The idea is that the following two experiments produce the same random variable:

1. A random permutation $\pi$ of $[n]$ subject to $\pi_i = n$.
2. Choose a random subset $S$ of $[n-1]$ of size $i$, a random permutation $\alpha$ of $S$, a random permutation $\beta$ of $[n-1] \setminus S$, and let $\pi = \alpha, n, \beta$.

The height of a BST based on the $\alpha$ part doesn't depend on $S$, which is why it is captured by $Y_{i-1}$. It does depend on $|S|$, but that's fine, since we conditioned on the value of $i$. Similarly, the height of a BST based on the $\beta$ part doesn't depend on the identity of the particular elements in $[n-1] \setminus S$, only on $|[n-1] \setminus S| = n-i$, which is why it is captured by $Y_{n-i}$.

You are worried that $R_n$ affects the number of keys that $Y_i$ and $Y_{n-i}$ contain, but that's false – $Y_i$ is the random height of a BST on $i$ elements, and this has absolutely nothing to do with $R_n$. Instead, you should really think of these as $Y_<$ and $Y_>$, where $Y_<$ is the height of the BST formed by elements to the left of $R_n$, and $Y_>$ is the height of the BST formed by elements to the right of $R_n$. The random variables $R_n,Y_<,Y_>$ are certainly dependent. But once we condition on the value of $R_n$, we are breaking this dependence – $Y_<$ has the same distribution as $Y_i$, and $Y_>$ has the same distribution as $Y_{n-i}$. At the same time, $R_n$ is no longer random, since we conditioned on its value.

As another example, let us consider the following random process: $A$ is a random bit, and $B$ is equal to $A$ with probability $2/3$, and otherwise it is opposite from $A$. Clearly $A$ and $B$ are dependent. If we know that $A = 0$, then $B$ is just a Bernoulli random variable, equal to $1$ with probability $1/3$.

Answer 2

Just to add on to the answer provided by @Yuval Filmus to further illustrate why the pair $Y_{i-1},Y_{n-i}$ should be independent on $Z_{n,i}$.

Here is what I got wrong:

From $Y_n = \sum_{i=1}^{n} Z_{n,i} (2\cdot max(Y_{i-1}, Y_{n-i}))$, I had mistakenly thought that $i$ is a random variable. When I put this back into the definitions: $Z_{n,i}$ denotes the indicator random variable for the event that the rank of the root node is $i$. $Y_{i-1}, Y_{i-1}$ denotes the exponential height of a randomly built binary search tree with $i$ elements and $i-1$ elements respectively. In this case, since $Z_{n,i}, Y_{i-1}, Y_{i-1}$ all dependent on this random variable $i$, I assumed that they must be dependent (through $i$).

Here is how I should have seen the equation above. By expanding out the summation: $$Y_n = Z_{n,1} (2\cdot max(Y_{1-1}, Y_{n-1})) + Z_{n,2} (2\cdot max(Y_{2-1}, Y_{n-2})) + ... + Z_{n,n} (2\cdot max(Y_{n-1}, Y_{n-n}))$$

Thus, $i$ is just a variable and should not affect the independence between the pair $Y_{i-1},Y_{n-i}$ and $Z_{n,i}$. For instance in the first term $Z_{n,1} (2\cdot max(Y_{1-1}, Y_{n-1}))$, $Z_{n,1}$ denotes the indicator random variable for the event that the rank of the root node is 1. On the other hand, $Y_{1-1}, Y_{n-1}$ denotes the exponential height of a randomly built binary search tree with $0$ elements and $n-1$ elements respectively. Thus, from the definition alone, it should be clear that the pair $Y_{i-1},Y_{n-i}$ should not depend on $Z_{n,i}$.

Answer 3

I was stuck thinking about this proof for a long time and why $Z_{n,i}$ and $Y_{i-1}$ should be independent. "Clearly" they depend on each other as they share the variable $i$. What made it click for me is that $Y_{i-1}$ is not a single random variable whose values depend on $i$, rather it is any of the $Y_0,Y_1,\cdots, Y_{n-1}$.

Think of a concrete example. Suppose $n=10$ and $i=4$. $Y_3$ is the exponential height of a randomly built binary search tree having $3$ nodes. It takes the values $2^1,2^2$. Knowing the value of $Z_{10,4}$ tells you nothing about the value that $Y_3$ takes. Whether $Z_{10,4}=1$ or $0$ ie. $R_{10}=4$ or $R_{10}\not=4$, $Y_3$ still takes the values $2^1,2^2$ with the same probability distribution.