How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?
There are two prominent uses of the term "average" in algorithm analysis.


Average-case as a special case of expected costs

Here, "average case" just means "expected case w.r.t. uniform distribution". Since we usually analyse with uniform inputs in mind (everything else is hard, and there's not much reason to prefer one distribution over the other in most cases).

Example: the average-case running-time cost of sorting algorithms
is often analyzed w.r.t uniformly-random permutations.
Average cost in the classic sense.

When analyzing data structures, we can look at average costs across
the contained elements for a fixed instance -- no probability 
distribution here (well, you could...).
That is, we may still have/want to consider a worst-, average- or 
best-case instance.

Example: Consider BSTs. The average search cost of a given tree is 
the total cost for searching all contained elements (one after the other)
divided by the number of contained elements. This is a classic quantity
in AofA called internal path length.


Note: There are situations where average and expected do not usually mean the same thing. For instance, the expected (also: average-case) height of BSTs is in $O(\log n)$ but the average height is in $\Theta(\sqrt{n})$. That is because "expected" is implicitly (by tradition) meant w.r.t. uniformly-random permutations of insertion operations whereas "average" means the average over all BSTs of a given size. The two distributions are not the same, and apparently significantly so!

Recommendation: Whenever you use "expected" or "average-case", be very clear about which quantities are random w.r.t. which distribution.



The specific sentence you quote is indeed not clear if read in isolation -- if you ignore that CLRS specify exactly what "simple uniform hashing" means on the very same page.

There are two potentially random variables here: 1) the content of the hashtable itself, and 2) the key searched for. Simple uniform hashing is a simple way of specifying both.


We abstract from sequences of insertions¹ and just assume that every one of the $n$ elements we inserted independently hashed to each of the $m$ addresses with probability $1/m$.
We assume that the searched key hashes to each address with probabilty $1/m$.


That's how the proof works: our search hits each list with probability $1/m$ (cf 2), and they all have the same expected length of $n/m$ (via 1). Hence, the expected cost (under this specific model) for searching for $x$ not in the table is proportional to

$\qquad\displaystyle\begin{align*}
  T_u(x,n,m) &amp;= 1 + \sum_{i=1}^m \operatorname{Pr}[h(x) = i] \cdot \mathbb{E}[\operatorname{length}(T[i])] \\
              &amp;\overset{1,2}{=} 1 +\sum_{i=1}^m \frac{1}{m} \cdot \frac{n}{m} \\
              &amp;= 1 + \frac{n}{m}.
\end{align*}$

The "$+1$" is there to account for computing $h(x)$ and accessing $T[h(x)]$, the sum represents the cost for searching along the list.




That is fair since the sequence of insertions does not have as much impact on the resulting structure as for, say, BSTs. The hash function shakes everything up. We don't want to talk about the precise interaction of sequence and hash function, so we just assume that the result of both is independently uniform -- that's something we can work with. It may not represent reality, of course!