# Trying to understand CLRS bucket sort analysis

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

• Those were indeed crucial typos. – Raphael Jan 31 '18 at 18:03

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