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.