Section 6.3: Digital Searching

Exercise 21. [M25] [M25] How many of the nodes, in a random M-ary trie containing N keys, have a null pointer in table entry 0? (For example, 9 of the 12 nodes in Table 1 have a null pointer in the “.,” position. “Random” in this exercise means as usual that the digits

of the keys are uniformly distributed between 0 and M, 1.)

Verified: yes
Solve time: 1m42s

---

Solution

Let $M \ge 2$ and consider a random $M$-ary trie built from $N$ keys, where each digit of each key is independently uniformly distributed in ${0,1,\dots,M-1}$.

For each finite string $w$ over ${0,\dots,M-1}$, let $X_w$ denote the number of keys having prefix $w$. A node corresponding to $w$ exists exactly when $X_w \ge 1$.

The node corresponding to $w$ has a null pointer in table entry $0$ exactly when no key has prefix $w0$, that is, when $X_{w0} = 0$, under the condition $X_w \ge 1$.

Hence the indicator variable for the event “node $w$ exists and has a null pointer at entry $0$” is

$$ I_w = [X_w \ge 1 \ \wedge\ X_{w0} = 0]. $$

The required expectation is

$$ \sum_w \mathbb{P}(I_w), $$

where the sum runs over all finite strings $w$.

Fix a prefix $w$ of length $j$. Each key falls into one of the $M^{j+1}$ equally likely categories determined by its first $j+1$ digits. Thus

$$ \mathbb{P}(\text{a key has prefix } w0) = M^{-(j+1)}, \quad \mathbb{P}(\text{a key has prefix } w) = M^{-j}. $$

Let $p_0 = M^{-(j+1)}$. Then

$$ \mathbb{P}(X_{w0} = 0) = (1 - p_0)^N = \left(1 - M^{-(j+1)}\right)^N, $$

and

$$ \mathbb{P}(X_w = 0) = (1 - M^{-j})^N. $$

The event ${X_{w0}=0 \ \wedge\ X_w \ge 1}$ is equivalent to “no key has prefix $w0$ but at least one key has prefix $w$”. This can be written as a difference:

$$ \mathbb{P}(X_{w0}=0 \ \wedge\ X_w \ge 1) = \mathbb{P}(X_{w0}=0) - \mathbb{P}(X_w=0), $$

since $X_w=0$ implies $X_{w0}=0$.

Therefore, for a fixed prefix $w$ of length $j$,

$$ \mathbb{P}(I_w) = \left(1 - M^{-(j+1)}\right)^N - \left(1 - M^{-j}\right)^N. $$

There are exactly $M^j$ distinct prefixes of length $j$. Summing over all levels $j \ge 0$ gives

$$ \mathbb{E}[\text{number of nodes with a null pointer at entry }0]

\sum_{j \ge 0} M^j \left[\left(1 - M^{-(j+1)}\right)^N - \left(1 - M^{-j}\right)^N\right]. $$

This expression already accounts for every trie node exactly once, since each node corresponds uniquely to a prefix $w$.

Thus the final result is

$$ \boxed{ \sum_{j \ge 0} M^j \left[\left(1 - M^{-(j+1)}\right)^N - \left(1 - M^{-j}\right)^N\right] }. $$

This completes the solution. ∎