A probabilistic data structure based on flipping bits with probability `1/2^x` for counting

63 views Asked by At

How does this data structure work and what is its application?

class X:
    def __init__(self):
        self.x = 0

    def plus_one(self):
        self.x = self.x + flip(self.x)

    def get(self):
        return 2**self.x #2 raised to the power of x

The flip() function is a random function that returns 1 with probability 1/2^x and 0 otherwise.

I suspect that this data structure is somehow related to R. Morris's probabilistic counting algorithm.

The question also mentions that this inequality might be helpful:
log(E[X]) >= E[log(X)]

where E denotes the expected value.

I would greatly appreciate any assistance or guidance.

0

There are 0 answers