Enumeration and random selection

Question

In Peter J. Cameron's book "Permutation Groups" I found the following quote

It is a slogan of modern enumeration theory that the ability to count a set is closely related to the ability to pick a random element from that set (with all elements equally likely).

Indeed, one can count and sample uniformly from labeled trees, spanning trees, spanning forests, dimer models, young tableaux, plane partitions etc. However one can't do either of these very efficiently with groups, for example. My question is if one can make this into a rigorous statement, perhaps through complexity theory. That is, if I have an algorithm to produce a uniform sample from a set of objects, can I somehow come up with an efficient way to count them or vice-versa?

Does this slogan have a standard name? Are there any references?

Answer 1

Yes, there is formal way of saying this using complexity theory. I think the statement is something like: For all self-reducible relations, the problems of approximate sampling and approximate counting are equivalent (with polynomial time reductions). More specifically, for such problems, the existence of an FPRAS (fully polynomial-time randomized approximation scheme) implies the existence of an FPAUS (fully polynomial-time almost uniform sampler) and vice versa.

References:

• Jerrum, Valiant, and Vazirani, "Random generation of combinatorial structures from a uniform distribution"
• Sinclair and Jerrum, "Approximate counting, uniform generation and rapidly mixing Markov chains"

Alternately, just search for "approximate counting", "approximate sampling" and "self-reducible" on google, and you'll find lots of lecture notes and presentations explaining the ideas.

Answer 2

If you have an algorithm that produces uniform and independent samples from a set of object, you can estimate the total number of objects as follows. First, construct a subset of the objects to be counted, if possible quite large, in a way such that you know the size of the subset and you can check easily if a given element is in your subset. Then start using your algorithm to produce random elements $X_1,\ldots, X,n,\ldots$. By the law of large numbers, the fraction of $X_i$ that belong to your subset will converge to its size divided by the total number of objects, so that you get your estimation. Finer convergence theorems like CLT give you quantitative estimates on the probability that your estimate is bad.

Of course, if your subset is very small compared to the total number of objects, you will have to wait very long for this method to give you something.

Answer 3

Suppose there are two finite sets $A$, $B$ and you have some relation on $A\times B$. If you can randomly sample from $A$ and $B$, you can estimate the average number $a$ of elements of $A$ related to each element of $B$, and the average number $b$ of elements of $B$ related to each element of $A$. Then $a/b=|A|/|B|$, so you can estimate the relative sizes of $A$ and $B$. So if you know the size of $B$ you can estimate the size of $A$. More generally, you can construct a chain of such ratios from the set you want to estimate to one you know the size of.

For example, if you want to estimate the number of trees of order $n$, then consider the trees of order $n-1$ and the relation of removing one leaf from a larger tree to make a smaller tree. Extend this chain to trees of order $n-2$, $n-3$, etc down to order $1$, where you know the number of trees is $1$, and use random sampling to estimate the ratios of the sizes of adjacent classes.

Answer 4

I suspect not. You did not ask about approximate counting or approximately uniform sampling (and of course that isn't what Cameron means). There are many situations where the desired set to enumerate sits in a larger set where we can easily and uniformly find a random element (for example: permutations of 1..n avoiding certain patterns (plus some side conditions perhaps) or lists of 17 integers under n^10 every 8 relatively prime). The enumeration problem does not seem aided by the fact that we can repeatedly pick a random element of the larger set and stop when we land in the target set.