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:

- Proof that a randomly built binary search tree has logarithmic height
- Average height of a BST with n Nodes.
- 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.