Section 6.3: Digital Searching

Exercise 22. [M25] [M25] How many trie nodes are on level | of a random M-ary trie containing N keys, for! =0, 1, 2,...?

Verified: yes
Solve time: 2m29s

---

Solution

Let $X_l$ denote the number of trie nodes on level $l$ in a random $M$-ary trie containing $N$ keys. Since the trie is random, $X_l$ is a random variable. Thus the natural interpretation of the question is to determine the average number of nodes on level $l$, namely $E(X_l)$.

A node on level $l$ corresponds to a prefix of length $l$. There are exactly

$$ M^l $$

possible prefixes of length $l$.

Fix one such prefix $\alpha$. Each key begins with $\alpha$ with probability

$$ p=M^{-l}, $$

because the digits are independent and uniformly distributed among the $M$ symbols. Hence the number of keys having prefix $\alpha$ has the binomial distribution

$$ \Pr{\text{(k) keys begin with }\alpha}

\binom Nk (M^{-l})^k (1-M^{-l})^{N-k}. $$

The node corresponding to $\alpha$ is present if and only if at least one key begins with that prefix. Therefore

$$ \Pr{\alpha\text{ gives rise to a node}}

1-\Pr{\text{no key begins with }\alpha}

1-(1-M^{-l})^N. $$

For each prefix $\alpha$, define the indicator variable

$$ I_\alpha= \begin{cases} 1, & \text{if the node corresponding to }\alpha\text{ is present},\ 0, & \text{otherwise}. \end{cases} $$

Then

$$ X_l=\sum_{\alpha} I_\alpha, $$

where the sum extends over all $M^l$ prefixes of length $l$.

Taking expectations and using linearity of expectation,

$$ E(X_l)

\sum_{\alpha} E(I_\alpha). $$

Since

$$ E(I_\alpha)

\Pr{I_\alpha=1}

1-(1-M^{-l})^N, $$

it follows that

$$ E(X_l)

M^l\bigl(1-(1-M^{-l})^N\bigr). $$

Hence the average number of trie nodes on level $l$ of a random $M$-ary trie containing $N$ keys is

$$ \boxed{ E(X_l)

M^l\left(1-(1-M^{-l})^N\right), \qquad l=0,1,2,\ldots } $$

For $l=0$,

$$ E(X_0)

1\cdot\bigl(1-(1-1)^N\bigr)

1, $$

which corresponds to the root node.

Therefore the number of nodes on level $l$ is a random variable $X_l$, and its mean value is

$$ \boxed{ M^l\left(1-(1-M^{-l})^N\right). } $$