Enumeración y selección aleatoria

Question

En el libro de Peter J. Cameron "Permutation Groups" encontré la siguiente cita

Es un lema de la teoría moderna de la enumeración que la capacidad de contar un conjunto está estrechamente relacionada con la capacidad de elegir un elemento al azar de ese conjunto (con todos los elementos igualmente probables).

En efecto, se puede contar y muestrear uniformemente a partir de árboles etiquetados, árboles de extensión, bosques de extensión, modelos de dímeros, tableaux jóvenes, particiones planas, etc. Sin embargo, no se puede hacer nada de esto de forma muy eficiente con grupos, por ejemplo. Mi pregunta es si se puede convertir esto en una afirmación rigurosa, quizás a través de la teoría de la complejidad. Es decir, si tengo un algoritmo para producir una muestra uniforme a partir de un conjunto de objetos, ¿puedo idear de alguna manera una forma eficiente de contarlos o viceversa?

¿Tiene este eslogan un nombre estándar? ¿Existen referencias?

Answer 1

Sí, hay una manera formal de decir esto utilizando la teoría de la complejidad. Creo que la afirmación es algo así como Para todas las relaciones autorreducibles, los problemas de muestreo aproximado y de recuento aproximado son equivalentes (con reducciones de tiempo polinómico). Más concretamente, para tales problemas, la existencia de un FPRAS (esquema de aproximación aleatoria de tiempo completamente polinomial) implica la existencia de un FPAUS (muestreador casi uniforme de tiempo completamente polinomial) y viceversa.

Referencias:

• Jerrum, Valiant y Vazirani, "Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme"
• Sinclair y Jerrum, "Recuento aproximado, generación uniforme y cadenas de Markov de mezcla rápida"

Como alternativa, busque "recuento aproximado", "muestreo aproximado" y "autorreductible" en Google, y encontrará muchos apuntes y presentaciones que explican las ideas.

Answer 2

Si tienes un algoritmo que produce muestras uniformes e independientes de un conjunto de objetos, puedes estimar el número total de objetos de la siguiente manera. En primer lugar, construye un subconjunto de los objetos a contar, a ser posible bastante grande, de forma que conozcas el tamaño del subconjunto y puedas comprobar fácilmente si un elemento determinado está en tu subconjunto. A continuación, empieza a utilizar tu algoritmo para producir elementos aleatorios $X_1,\ldots, X,n,\ldots$ . Por la ley de los grandes números, la fracción de $X_i$ que pertenecen a su subconjunto convergerán a su tamaño dividido por el número total de objetos, de modo que se obtiene su estimación. Los teoremas de convergencia más finos, como el CLT, te dan estimaciones cuantitativas sobre la probabilidad de que tu estimación sea mala.

Por supuesto, si su subconjunto es muy pequeño en comparación con el número total de objetos, tendrá que esperar mucho tiempo para que este método le dé algo.

Answer 3

Supongamos que hay dos conjuntos finitos $A$ , $B$ y tienes alguna relación en $A\times B$ . Si puede tomar una muestra aleatoria de $A$ y $B$ se puede estimar el número medio $a$ de elementos de $A$ relacionados con cada elemento de $B$ y el número medio $b$ de elementos de $B$ relacionados con cada elemento de $A$ . Entonces $a/b=|A|/|B|$ para poder estimar los tamaños relativos de $A$ y $B$ . Por lo tanto, si conoce el tamaño de $B$ puede estimar el tamaño de $A$ . De forma más general, se puede construir una cadena de tales relaciones desde el conjunto que se quiere estimar hasta uno del que se conoce el tamaño.

Por ejemplo, si se quiere estimar el número de árboles de orden $n$ , entonces considera los árboles de orden $n-1$ y la relación de quitar una hoja de un árbol más grande para hacer un árbol más pequeño. Extienda esta cadena a los árboles de orden $n-2$ , $n-3$ etc. por orden $1$ donde se sabe que el número de árboles es $1$ y utilizar el muestreo aleatorio para estimar las proporciones de los tamaños de las clases adyacentes.

Answer 4

Sospecho que no. No has preguntado por el recuento aproximado ni por el muestreo aproximadamente uniforme (y, por supuesto, eso no es lo que quiere decir Cameron). Hay muchas situaciones en las que el conjunto deseado para enumerar se encuentra en un conjunto más grande en el que podemos encontrar fácilmente y de manera uniforme un elemento aleatorio (por ejemplo: permutaciones de 1..n que evitan ciertos patrones (más algunas condiciones secundarias quizás) o listas de 17 enteros bajo n^10 cada 8 relativamente primos). El problema de la enumeración no parece estar ayudado por el hecho de que podamos escoger repetidamente un elemento aleatorio del conjunto mayor y detenernos cuando lleguemos al conjunto objetivo.