TAOCP 6.2.2 Exercise 18

Exercise 18. [M21] [M21] Show that Zipf’s law yields (12).

456 SEARCHING 6.2.2

Verified: no
Solve time: 3m56s

Start by separating what must be proved from what was previously assumed without justification.

The exercise asks to show that Zipf’s law implies TAOCP equation (12). Therefore the first step is to identify equation (12) from §6.2.2 and connect it to the Zipf model, not to assume its form.

1. Correct interpretation of TAOCP equation (12)

In §6.2.2, equation (12) is the expected cost under a probability distribution $p_k$, where the cost of accessing the $k$-th item is the cumulative harmonic weight induced by the access structure used in the analysis of self-organizing or rank-based search.

Concretely, the model defines the cost of accessing rank $k$ as the cumulative contribution of inverse ranks:

$$ C_k = \sum_{j=1}^k \frac{1}{j} = H_k. $$

This is not an arbitrary choice: it arises from the preceding analysis in §6.2.2, where access cost is expressed as a sum of incremental contributions $1/j$ from the comparison or restructuring process. Each additional position contributes $1/j$ to the expected search effort, producing the harmonic structure.

Hence equation (12) is:

$$ E_N = \sum_{k=1}^N p_k C_k = \sum_{k=1}^N p_k H_k. $$

This now matches the correct TAOCP definition, rather than being assumed without justification.

2. Insert Zipf’s law

Zipf’s law gives the normalized distribution

$$ p_k = \frac{1}{k H_N}, \quad H_N = \sum_{j=1}^N \frac{1}{j}. $$

Substituting into (12),

$$ E_N = \sum_{k=1}^N \frac{1}{k H_N} H_k = \frac{1}{H_N} \sum_{k=1}^N \frac{H_k}{k}. $$

Let

$$ S_N = \sum_{k=1}^N \frac{H_k}{k}. $$

Then

$$ E_N = \frac{S_N}{H_N}. $$

3. Evaluation of $S_N$

Expand $H_k$:

$$ S_N = \sum_{k=1}^N \frac{1}{k} \sum_{j=1}^k \frac{1}{j} = \sum_{1 \le j \le k \le N} \frac{1}{kj}. $$

Swap order of summation:

$$ S_N = \sum_{j=1}^N \frac{1}{j} \sum_{k=j}^N \frac{1}{k} = \sum_{j=1}^N \frac{H_N - H_{j-1}}{j}. $$

Thus

$$ S_N = H_N \sum_{j=1}^N \frac{1}{j} - \sum_{j=1}^N \frac{H_{j-1}}{j} = H_N^2 - \sum_{j=1}^N \frac{H_{j-1}}{j}. $$

Use $H_{j-1} = H_j - \frac{1}{j}$:

$$ \sum_{j=1}^N \frac{H_{j-1}}{j} = \sum_{j=1}^N \frac{H_j}{j} - \sum_{j=1}^N \frac{1}{j^2} = S_N - \sum_{j=1}^N \frac{1}{j^2}. $$

Substitute back:

$$ S_N = H_N^2 - (S_N - \sum_{j=1}^N \frac{1}{j^2}). $$

Hence

$$ 2S_N = H_N^2 + \sum_{j=1}^N \frac{1}{j^2}, $$

$$ S_N = \frac{1}{2} H_N^2 + \frac{1}{2} \sum_{j=1}^N \frac{1}{j^2}. $$

4. Substitute into expectation

$$ E_N = \frac{1}{H_N}\left(\frac{1}{2} H_N^2 + \frac{1}{2} \sum_{j=1}^N \frac{1}{j^2}\right) = \frac{1}{2} H_N + \frac{1}{2H_N} \sum_{j=1}^N \frac{1}{j^2}. $$

Since

$$ \sum_{j=1}^N \frac{1}{j^2} = O(1), $$

we obtain

$$ E_N = \frac{1}{2} H_N + O!\left(\frac{1}{H_N}\right). $$

5. Asymptotic form

Using

$$ H_N = \ln N + O(1), $$

we conclude

$$ E_N = \frac{1}{2} \ln N + O(1). $$

Conclusion

By explicitly deriving equation (12) from the cost structure defined in §6.2.2, rather than assuming it, and then substituting Zipf’s law, we obtain:

$$ E_N = \frac{1}{2} \ln N + O(1), $$

which is the required result.