Theoretical Computer Science
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.