3
$\begingroup$

In section 9.2 of CLRS (Introduction to Algorithms; page 185 in the 2nd edition and page 215 in the 3rd edition), a randomized selection algorithm is presented.

For its analysis, $T(n)$ is a random variable denoting the time required on an input array $A[p \cdots r]$ of $n$ elements and $X_k$ is an indicator random variable $X_k = I \{ \text{the subarray } A[p \cdots q] \text{ has exactly } k \text{ elements (due to the pivot)} \}$.

It has been claimed that $X_k$ and $T(\max(k-1, n-k))$ are independent (page 187 in the 2nd edition and page 218 in the 3rd edition). However, I find it quite counter-intuitive to understand. How to verify it?

$\endgroup$
2
$\begingroup$

The two random variables $X_k$ and $T(\max(k-1, n-k))$ are independent because in each recursive call to RANDOMIZED-SELECT() we invoke RANDOMIZED-PARTITION(), a pivot is randomly selected, and the choice of the pivot in one recursive call is independent from the choice of the pivot in another recursive call. Remember that in the analysis we assume that the elements are distinct, so that each element in a particular subarray has the same probability of being selected as the pivot. Moreover, simply stated, the value of $\max(k-1,n-k)$ does not depend on $X_k$: it is the same independently of $X_k$ being equal to zero or one.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please elaborate as to why "the choice of the pivot in one recursive call is independent from the choice of the pivot in another recursive call" $\implies$ $Pr\{X_k=a \land \max(k-1,n-k)=m\}=Pr\{X_k=a\}.Pr\{\max(k-1,n-k)=m\}$ $\endgroup$ – Abhishek Ghosh Jun 22 at 21:00
  • 1
    $\begingroup$ There is a precise assumption: the random numbers are independent, i.e., they must be chosen independently from each other. As a consequence, each time RANDOMIZED-PARTITION() is called, it generates a completely independent random number from all the other successive times RANDOMIZED-PARTITION() is called. In practice that means that the pivot selected during the $i$-th invocation does not depend functionally on the pivots selected in the previous calls. Finally, the value of $\max(๐‘˜โˆ’1,๐‘›โˆ’๐‘˜)$ does not depend on $X_K$: it is the same independently of $X_K$ being equal to zero or one. $\endgroup$ – Massimo Cafaro Jun 23 at 13:05
2
$\begingroup$

Apparently it seems that "$X_k$ and $T(\max(k-1,n-k)$ are independent" is counter-intuitive, as at glimpse it seems that the value of $X_k$ depends on $k$ and so does $T(\max(k-1,n-k)$. So to clarify the situation we much look at the case and definition more closely.

Now as per the definition, $X_k$ is used to reflect the randomness of the algorithm in the recurrence relation of its time complexity. A deeper look at the definition of $X_k$ says that it depends on the value of the index of the pivot which is chosen in a particular call to the RANDOMIZED-PARTITION. As only one index of the array is selected as the pivot in a particular call to RANDOMIZED-PARTITION $X_k$ can have the value $1$ only for that particular pivot index $k$ and all other indices we have $X_k=0$ and the summation on the RHS of the recurrence reduces to only one term.

$$\sum_{k=1}^{n} X_k.T(\max(k-1,n-k))$$

$$=X_1.T(\max(1-1,n-1))+X_2.T(\max(2-1,n-2))+X_3.T(\max(3-1,n-3))+\ldots+X_n.T(\max(n-1,n-n)) \tag 1$$

Now suppose if RANDOMIZED-PARTITION returns $2$ we have,

$$=0.T(\max(1-1,n-1))+1.T(\max(2-1,n-2))+0.T(\max(3-1,n-3))+\ldots+0.T(\max(n-1,n-n))$$

Or if RANDOMIZED-PARTITION returns $n$ we have,

$$=0.T(\max(1-1,n-1))+0.T(\max(2-1,n-2))+0.T(\max(3-1,n-3))+\ldots+1.T(\max(n-1,n-n))$$

Note that in $(1)$ whatever be the value of $X_k$ the value $T(\max(k-1,n-k))$ does not change, this is so because of the following,

Thought it seems that $X_k$ depends on the summation variable $k$ but it is not the complete truth.

A more closer look into the definition of this indicator random-variable shows that $X_k$ depends on whether a particular value of the summation variable is choosen as the pivot index by the RANDOMIZED-PARTITION. So if in a call RANDOMIZED-PARTITION selects the pivot index as say $j$ then for $k=j$ we have $X_j=1$ and zero for all other $X_{k\neq j}$. So $X_k$ depend on the RANDOMIZED-PARTITION.

On the other hand $T(\max(k-1,n-k))$ is a random variable (as the text defines) but it has as its parameter $\max(k-1,n-k)$ which in turn depends only on the summation variable and no other hidden conditions.

From our above two claims we can say that $X_k$ and $T(\max(k-1,n-k)$ are independent.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.