counting-complexity sample-complexity: Updated Mon, 13 Jun 2022 22:23:15 GMT

Almost uniform sampling implies approximate counting

I began studying papers about approximate counting and I keep seeing the above being quoted, without further explanation. I suppose the procedure that yields the result is very well known and that is why. Can anyone give me roughly the idea if possible and secondly some references about it?

Solution

Given a set $A \subseteq B$, if you can sample uniformly from $B$, then you can estimate by repeated sampling the probability of the event that the sample is in $A$. That is, you can approximate the probability $|A| / |B|$, which is indeed close to enumerating the elements of $A$, and thus computing its size.

References

https://cstheory.stackexchange.com/questions/30794