Renewal theory in analysis of tries and strings

Svante Janson

We give a survey of a number of simple applications of renewal theory to problems on random strings and tries: insertion depth, size, insertion mode and imbalance of tries; variati…