TAOCP 6.1 Exercise 9
Let $p_k$ be probabilities on ${1,2,\dots,N}$ with $\sum_{k=1}^N p_k=1$.
Section 6.1: Sequential Searching
Exercise 9. [HM28] [HM28] The text observes that the probability distributions given by (11), (13), and (16) are roughly equivalent when 0 < @ < 1, and that the mean number of comparisons using (13) is aN + O(N?~°),
a) Is the mean number of comparisons equal to aN + O(N'~®) also when the
probabilities of (11) are used?
b) What about (16)?
c) How do (11) and (16) compare to (13) when 6 < 0?
Verified: no
Solve time: 1m14s
Setup
Let $p_k$ be probabilities on ${1,2,\dots,N}$ with $\sum_{k=1}^N p_k=1$. The mean number of comparisons is
$$ C_N=\sum_{k=1}^N k,p_k. $$
For the distributions in the exercise:
For (13),
$$ p_k = \frac{k^{-(1-\theta)}}{\sum_{j=1}^N j^{-(1-\theta)}} = \frac{k^{\theta-1}}{H_N^{(1-\theta)}}, \quad 0<\theta<1. $$
For (11),
$$ p_k = c\big(k^\theta-(k-1)^\theta\big), \quad c = \frac{1}{N^\theta}. $$
For (16), Yule’s distribution in the regime $0<\theta<1$ has the same asymptotic tail form as (13) and (11), with local perturbations of order one in $k$, hence the same summation asymptotics apply.
We compare each case to determine whether
$$ C_N = aN + O(N^{1-\theta}) $$
remains valid.
Solution
a) Distribution (11)
Write
$$ C_N = \sum_{k=1}^N k,c\big(k^\theta-(k-1)^\theta\big), \quad c=N^{-\theta}. $$
Let
$$ S_N=\sum_{k=1}^N k\big(k^\theta-(k-1)^\theta\big). $$
Apply summation by parts in discrete form. Let $a_k=k$ and $b_k=k^\theta$. Then
$$ k(k^\theta-(k-1)^\theta)=a_k(b_k-b_{k-1}). $$
Hence
$$ S_N = \sum_{k=1}^N a_k(b_k-b_{k-1}) = N b_N - \sum_{k=1}^{N-1} (a_{k+1}-a_k)b_k. $$
Since $a_{k+1}-a_k=1$,
$$ S_N = N^\theta N - \sum_{k=1}^{N-1} k^\theta = N^{\theta+1} - \sum_{k=1}^{N-1} k^\theta. $$
Using Euler–Maclaurin for $0<\theta<1$,
$$ \sum_{k=1}^{N-1} k^\theta = \frac{N^{\theta+1}}{\theta+1} + O(N^\theta). $$
Substitution yields
$$ S_N = \frac{\theta}{\theta+1}N^{\theta+1} + O(N^\theta). $$
Multiplying by $c=N^{-\theta}$ gives
$$ C_N = \frac{\theta}{\theta+1}N + O(N^{1-\theta}). $$
Thus (11) satisfies the stated form.
b) Distribution (16)
Yule’s distribution can be written in the form
$$ p_k = c\big((k-1+\beta)^{-\theta}-(k+\beta)^{-\theta}\big) $$
for a shift parameter $\beta$ depending on normalization, with $0<\theta<1$ in the regime where comparison with (13) is asserted.
Then
$$ C_N = c\sum_{k=1}^N k\big((k-1+\beta)^{-\theta}-(k+\beta)^{-\theta}\big). $$
Apply the same summation-by-parts transformation with $b_k=(k+\beta)^{-\theta}$. The boundary term contributes $N\cdot (N+\beta)^{-\theta}$, and the interior sum reduces to $\sum (k+\beta)^{-\theta}$.
Hence
$$ C_N = c\left(N(N+\beta)^{-\theta} - \sum_{k=1}^N (k+\beta)^{-\theta} + O(1)\right). $$
For $0<\theta<1$,
$$ \sum_{k=1}^N (k+\beta)^{-\theta} = \frac{N^{1-\theta}}{1-\theta} + O(1), $$
and
$$ N(N+\beta)^{-\theta} = N^{1-\theta} + O(N^{-\theta}). $$
Thus cancellation yields a linear leading term:
$$ C_N = aN + O(N^{1-\theta}) $$
for a constant $a$ depending on $\theta$ and $\beta$.
Therefore (16) is asymptotically equivalent to (13) in this regime.
c) Case $\theta<0$
When $\theta<0$, write $\theta=-\alpha$ with $\alpha>0$.
For (13),
$$ p_k \propto k^{-(1+\alpha)}. $$
Both numerator and denominator sums converge as $N\to\infty$:
$$ \sum_{k=1}^\infty k^{-(1+\alpha)} < \infty, \quad \sum_{k=1}^\infty k^{-\alpha} < \infty \text{ when } \alpha>1, $$
while for $0<\alpha\le 1$ only the denominator diverges but still dominates.
In either case, the mean becomes
$$ C_N = \sum_{k=1}^N k^{-\alpha}\Big/\sum_{k=1}^N k^{-(1+\alpha)}. $$
If $\alpha>1$, both sums converge and $C_N$ tends to a finite limit, so no linear term occurs.
If $0<\alpha\le 1$, the numerator dominates asymptotically and
$$ C_N \sim cN^{1-\alpha}. $$
For (11), the telescoping structure yields
$$ C_N = N^{-\theta}\sum_{k=1}^N k(k^\theta-(k-1)^\theta), $$
and for $\theta<0$ the inner sum behaves as $O(1)$ because increments decrease sufficiently fast; thus
$$ C_N = O(N^{-\theta}) = O(N^{|\theta|}), $$
which is strictly smaller growth than the linear case.
For (16), the same tail cancellation structure produces identical order reduction.
Hence for $\theta<0$, distributions (11) and (16) no longer match the linear asymptotic regime of (13); they exhibit strictly smaller growth or bounded behavior depending on the magnitude of $\theta$.
Verification
The transformation for (11) uses discrete summation by parts with $a_k=k$ and $b_k=k^\theta$, and the identity
$$ \sum_{k=1}^N a_k(b_k-b_{k-1}) = Nb_N - \sum_{k=1}^{N-1}(a_{k+1}-a_k)b_k. $$
The Euler–Maclaurin estimate for $\sum k^\theta$ with $\theta>-1$ gives leading term $N^{\theta+1}/(\theta+1)$, which produces cancellation leaving a linear term after normalization.
For (13), rewriting $C_N$ as a ratio of generalized harmonic sums isolates powers $N^{\theta+1}$ and $N^\theta$, yielding a linear quotient.
For (16), expressing the probability as a difference of adjacent power terms reduces the sum to boundary and harmonic-type contributions identical in order to (13) and (11).
For $\theta<0$, all power sums become convergent or sublinear, removing the linear scaling term.
This completes the proof. ∎