0
$\begingroup$

I'm trying to understand the analysis of bucket sort in CLRS. Specifically, equation 8.2 that states:

$$ E[{n_i^2}] = 2 - \frac{1}{n} $$

To prove, CLRS:

Random variable denoting number of elements that fall into bucket i:

$$ {n_i} $$

An indicator random variable that a given element in the input falls into a particular bucket.

$$ X{_i}{_j} $$

so

$$ {n_i} = \sum_{j=1}^{n}X{_i}{_j} $$

Now, CLRS says to expand the square and regroup the terms:

$$ E[{n_i^2}] = E\left[\left(\sum_{j=1}^{n}X{_i}{_j}\right)^2\right] $$

I can see how the above goes to the next step:

$$ = E\left[\sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{ik}\right]$$

I'm confused as to how the above turns into:

$$ = E\left[\sum_{j=1}^{n}X_{ij}^2 + \sum_{1 <= j <= n}\sum_{1 <= k <= n, k != j}X_{ij}X_{ik}\right] $$

For what it's worth, the Algorithms in a Nutshell books has a section on bucket sort that also analyzes why it's 2 - 1/n, and it helps me see things a bit more clearly, but still am unclear about the above. From the AiaN book:

$$ E[n_i^2] = Var[{n_i}]+ E^2[n_i]$$

where

$$ Var[{n_i}] = n * p * (1-p) = n * \frac{1}{n} * \left(1 - \frac{1}{n}\right) = 1 - \frac{1}{n} $$

and

$$ E[{n_i}] = n * p = n * \frac{1}{n} = 1$$

which equals 2 - 1/n

$\endgroup$
  • $\begingroup$ Those were indeed crucial typos. $\endgroup$ – Raphael Jan 31 '18 at 18:03
2
$\begingroup$

You are asking why

$\qquad\displaystyle \sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{ik} \quad=\quad \sum_{j=1}^{n}X_{ij}^2 + \sum_{j = 1}^{n}\sum_{1 \leq k \leq n,\\ k \neq j}X_{ij}X_{ik}$

holds (in expectation, but that's irrelevant for this; it might not always be, though!).

Note that the left-hand side and the second summand on the right-hand site are identical except for the $k \neq j$ constraint. That is, the difference between the two terms is exactly

$\qquad\displaystyle \sum_{j=1}^n \sum_{1 \leq k \leq n,\\k=j} X_{ij}X_{ik} \quad=\quad \sum_{j=1}^n X_{ij}X_{ij} \quad=\quad \sum_{j=1}^{n}X_{ij}^2$.

No deep insight here, just basic manipulation of sums.

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