Counting nodes in a trie

I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem.

Question: Given a random $m$-ary trie with $n$ total leaves, letting $I$ be the number of internal nodes in the tree (that is, nodes which aren't a leaf), show that $E(I)$ is $O(n)$.

About the distribution: We have an alphabet of $m$ letters (hence an $m$-ary trie), each with a corresponding probability $p_i$. We randomly create $n$ words of infinite length by drawing the first letter from our distribution, the second letter, etc. Finally, we insert these $n$ infinite words into a $k$-ary trie. This trie will be infinite in length, but we prune it by removing any paths which are traversed by only one of our $n$ words, to eliminate 'redundancy'.

Attempt: I tried relating things back to the size of the random trie, which I call $S$. Every non-root node in the trie is the child of some internal node, so $mI = S-1$
That is $E(I) = E\left(\frac S m\right) - \frac 1 m$
So if I can show that the expected size of a random trie is O(n) I'm golden. But unfortunately everything we've covered in class relates to expected depths and heights of a given trie, and I don't have any ideas moving forward. Could anyone offer advice on what might be useful here?

• Can you explain what you mean by trie and how you generate a random trie? – Yuval Filmus Dec 5 '14 at 1:01
• Please define precisely what distribution on tries you have in mind. Without that, your problem is not well-defined and it's not possible to answer it. – D.W. Dec 5 '14 at 1:55
• We have an alphabet of m letters (hence an m-ary trie), each with a corresponding probability $p_{i}$. We create n words of infinite length by drawing the first letter from our distribution, the second letter, etc... Finally, we put out n infinite words into a k-ary trie. This trie will be infinite in length, but we prune it by removing any paths which are traversed by only one of our m strings, to eliminate 'redundancy'. Hopefully this helps? – user94715 Dec 5 '14 at 2:32
• I'm confused. 1. First you mention a $m$-ary trie, then you mention a $k$-ary trie. Which is it? What's $k$? Is the $k$ a typo? 2. You are using the same variable $n$ for two different things: the total number of leaves, and the number of strings generated during the distribution. That's confusing. Please avoid that -- please edit your question to pose the question more carefully. 3. Given your distribution on tries, both the number of leaves (your first $n$) and $I$ are random variables, so writing $E(I) = O(n)$ doesn't make any sense. Do you mean $E(I) = O(E(n))$? $E(I/n)=O(1)$? – D.W. Dec 5 '14 at 8:13

If you don't have any degree-1 nodes in your trie (which is a tree) than you have more leaves than interior nodes. So in this case you have $I\le n$.
It depends a bit how you define the trie whether you can have many interior degree-1 nodes. If you study a compressed trie the all the path of degree-1 nodes are merges to an edge, so you are done. For an uncompressed trie, I am afraid, you can have many degree-1 nodes. Say you have one letter $a_i$ that is very common and has a high probability of $1-\varepsilon$ and $\varepsilon\in \Omega(1/n^2)$. Then your trie contains many long degree-1 paths with high probability. In this case the you can have more than $O(n)$ interior nodes. Please do the computations by yourself (you might choose a smaller $\varepsilon$ if you like).