The statistical behaviour of digital expansions plays a role in the analysis of several algorithms (divide-and-conquer strategies such as mergesort, traffic cutback, determination of sets with maximal number of interconnecting edges, RSA, ...). For example, it is well known that the sum-of-digits function with respect to an integer base satisfies a central limit theorem on the set of integers with mean and variance proportional to . (Interestingly this is also true on the set of prime numbers as well as on polynomial sequences.)
The purpose of this talk is to demonstrate a general method for determining limiting distributions of that kind which also works for more general digital expansions, e.g. those with respect to a linear recurrence such as the Zeckendorf expansion (based on the Fibonacci numbers). The problem consists mostly in determining the value of a digit without using the greedy algorithm. For a large class of recurrences, this can be done by using Rauzy fractals. Finally, the central limit theorem is then an (almost automatic) consequence of estimates for exponential sums.
Back to the Index