<p>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.</p>

CC BY-SA 3.0
2015-03-12T17:15:35.237Z
2015-03-12T17:45:06.450Z
2015-03-12T17:45:06.450Z
Sariel Har-Peled
<p>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? </p>

<counting-complexity><sample-complexity>
Almost uniform sampling implies approximate counting
Paramar
# Almost uniform sampling implies approximate counting

(Asked by: username_0 on 2015-03-12)

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?

**Tags:** counting-complexity, sample-complexity

---

## 1 answers

### Answer by username_1 on 2015-03-12. Score: 10 | Accepted answer

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.


---

