Heavy Hitters and Bernoulli Convolutions
This work addresses frequency approximation for time-sensitive events, likely in streaming or real-time data contexts, but appears incremental as it builds on existing concepts of Bernoulli convolutions and random walks.
The paper tackles the problem of approximating event frequencies with timeliness sensitivity by proposing a simple iterative algorithm that updates categorical click-distributions, resulting in a random walk on a simplex that corresponds to a biased Bernoulli convolution under certain conditions. The evaluation of this algorithm leads to the estimation of moments for biased Bernoulli convolutions, both finite and infinite.
A very simple event frequency approximation algorithm that is sensitive to event timeliness is suggested. The algorithm iteratively updates categorical click-distribution, producing (path of) a random walk on a standard $n$-dimensional simplex. Under certain conditions, this random walk is self-similar and corresponds to a biased Bernoulli convolution. Algorithm evaluation naturally leads to estimation of moments of biased (finite and infinite) Bernoulli convolutions.