Randomly built binary search trees

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 rank

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}$.

StackExchange Computer Science Q#111788, answer score: 3