TAOCP 6.4 Exercise 59
Let $S_M$ be the set of all permutations of $\{0,1,\dots,M-1\}$, and let $\mathbb{P}$ be a probability assignment on $S_M$ that is equivalent to uniform probing in the sense of Theorem U.
Exercise 59. [M25] [M25] Prove that if an assignment of probabilities to permutations is equivalent to uniform probing, in the sense of Theorem U, the number of permutations with nonzero probabilities exceeds M* for any fixed exponent a, when M is sufficiently large.
Verified: yes
Solve time: 2m37s
Let $S_M$ be the set of all permutations of ${0,1,\dots,M-1}$, and let $\mathbb{P}$ be a probability assignment on $S_M$ that is equivalent to uniform probing in the sense of Theorem U.
For each permutation $\pi \in S_M$ and each $k \le M$, define its prefix
$$ T_k(\pi) = (\pi(1),\pi(2),\dots,\pi(k)). $$
Let $\mathcal{T}_k$ be the set of all ordered $k$-tuples of distinct elements of ${0,1,\dots,M-1}$, so
$$ |\mathcal{T}_k| = (M)_k = M(M-1)\cdots(M-k+1). $$
Assume uniform probing in the sense of Theorem U. Then for every fixed $k \le M$ and every $t \in \mathcal{T}_k$,
$$ \mathbb{P}(T_k(\pi) = t) = \frac{1}{(M)_k}. $$
Let
$$ \Sigma = {\pi \in S_M : \mathbb{P}(\pi) > 0} $$
be the support of the distribution, and for each $t \in \mathcal{T}_k$, define
$$ \Sigma_t = {\pi \in \Sigma : T_k(\pi) = t}. $$
These sets $\Sigma_t$ form a disjoint partition of $\Sigma$.
Now fix $t \in \mathcal{T}_k$. By definition of induced probability,
$$ \mathbb{P}(T_k(\pi)=t) = \sum_{\pi \in \Sigma_t} \mathbb{P}(\pi) = \frac{1}{(M)_k}. $$
The right-hand side is strictly positive. Since each term in the sum is nonnegative, this equality implies that $\Sigma_t$ cannot be empty. Indeed, if $\Sigma_t = \varnothing$, then the sum would be $0$, contradicting $\frac{1}{(M)_k} > 0$. Hence,
$$ \Sigma_t \neq \varnothing \quad \text{for every } t \in \mathcal{T}_k. $$
Moreover, each permutation $\pi \in \Sigma$ has a unique prefix $T_k(\pi)$, so the sets $\Sigma_t$ are disjoint. Therefore, selecting one distinct permutation from each nonempty $\Sigma_t$ yields at least $|\mathcal{T}_k|$ distinct permutations in the support. Thus,
$$ |\Sigma| \ge |\mathcal{T}_k| = (M)_k. $$
Now fix any exponent $a \ge 1$, and choose $k = a+1$. Then
$$ |\Sigma| \ge (M)_{a+1} = M(M-1)\cdots(M-a). $$
Expanding the leading term,
$$ (M)_{a+1} = M^{a+1} + O(M^a), $$
so in particular,
$$ (M)_{a+1} > M^a $$
for all sufficiently large $M$.
Hence,
$$ |\Sigma| > M^a $$
for every fixed $a$ when $M$ is sufficiently large.
This completes the proof. ∎