A Note on the Height of Suffix Trees
Luc Devroye, Wojciech Szpankowski, Bonita Rais · SIAM Journal on Computing · 1992
Consider a random word in which the individual symbols are drawn from a finite or infinite alphabet with symbol probabilities $p_i $ , and let $H_n $ be the height of the suffix tree constructed from the first n suffixes of this word. It is shown that $H_n $ is asymptotically close to $2\log n/\log (1/\sum_i p_i^2 )$ in many respects: the difference is $O(\log \log n)$ in probability, and the ratio tends to one almost surely and in the mean.