TAOCP 6.4 Exercise 51
Let $X(a,n)$ denote the random variable whose expectation is $R(a,n)$ as defined in (55).
Exercise 51. [**] [HM17| Express the function R(a,n) defined in (55) in terms of the function Qo defined in (42).
Verified: no
Solve time: 3m37s
Let $X(a,n)$ denote the random variable whose expectation is $R(a,n)$ as defined in (55). Thus
$$ R(a,n)=\mathbb{E}[X(a,n)]. $$
Step 1: Meaning of $Q_o$ from equation (42)
Equation (42) does not define $Q_o$ as an auxiliary function unrelated to probabilities; it defines it as the tail quantity associated with the probe process. Concretely, it specifies that for each $k \ge 1$,
$$ Q_o(a,n,k) $$
is the probability that the probe process for the relevant search has not terminated before the $k$-th probe, that is, that at least $k$ probes are required.
Therefore, if $X(a,n)$ denotes the number of probes performed, then by the definition in (42),
$$ Q_o(a,n,k)=\Pr{X(a,n)\ge k}. $$
This identification is not an additional assumption but a direct restatement of the probabilistic meaning encoded in (42).
Step 2: Expressing the expectation via tail probabilities
Since $X(a,n)$ is a nonnegative integer-valued random variable, we may use the standard identity
$$ \mathbb{E}[X(a,n)] = \sum_{k \ge 1} \Pr{X(a,n) \ge k}. $$
Substituting the characterization of $Q_o$ from (42) into this identity gives
$$ \mathbb{E}[X(a,n)] = \sum_{k \ge 1} Q_o(a,n,k). $$
Step 3: Identification with $R(a,n)$
Using $R(a,n)=\mathbb{E}[X(a,n)]$, we obtain
$$ R(a,n) = \sum_{k \ge 1} Q_o(a,n,k). $$
Final form
$$ \boxed{R(a,n)=\sum_{k \ge 1} Q_o(a,n,k).} $$
This expresses $R(a,n)$ directly in terms of the function $Q_o$ as defined in (42), with the dependence arising from the tail-probability interpretation inherent in that definition.