Intutition Behind Flajolet and Martin

Intuition behind Flajolet and Martin’s Analysis of Algorithm for Estimation of F0 as presented in Alon’s paper.

This is about the part where they show that the probability that their estimate deviates too much (by a factor of c) from the actual value is less than 2/c.

The idea is – in what way can we go wrong ? We can go wrong in 2 ways.
By Overestimation
By Underestimation

In overestimation it will happen that we estimate Y at a very high value when in fact F0 is indeed quite low. This will happen when we get an element that is mapped to a very-low probability bucket. But the probability of this itself is too low – by Markov’s Inequality.

In underestimation it will happen that we estimate Y at a very low value when in fact F0 is quite high. This will happen when we get a sequence of elements that map to a high probability bucket. But the probability that EVERY element will map to a high probability bucket is quite low – by Chebyshev’s Inequality

Now how the inequalities are applied are a matter of further investigation.