3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Can you explain what you mean by trie and how you generate a random trie? $\endgroup$
    – Yuval Filmus
    Dec 5, 2014 at 1:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Dec 5, 2014 at 1:55
  • $\begingroup$ 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? $\endgroup$
    – user94715
    Dec 5, 2014 at 2:32
  • $\begingroup$ 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)$? $\endgroup$
    – D.W. ♦
    Dec 5, 2014 at 8:13

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.