¿Podemos estimar el tamaño de un subconjunto X de un conjunto A, muestreando aleatoriamente subconjuntos de A?

Deje ser un conjunto finito y supongamos que queremos calcular el tamaño de un subconjunto .$A$$X$

Motivación : si podemos generar elementos de uniforme al azar, entonces podemos estimar el tamaño de por muestreo aleatorio. Es decir, tomamos muestras aleatorias de , si de ellas pertenecen a , entonces . Desafortunadamente, por lo que hago, generalmentees masivo y(aunque masivo) es bastante pequeño con respecto a. Entonces, si intento realizar la estimación anterior, es probable que obtenga , que, aunque no es inútil, no es realmente tan satisfactorio.A A n A m X | X | / | A | ≈ m / n | A | El | X | El | A | m = $x$$A$$A$$n$$A$$m$$X$$|X|/|A| \approx m/n$$|A|$$|X|$$|A|$$m=0$

Entonces, tengo una idea que espero acelere este proceso. En lugar de lanzar dardos en un tablero de dardos masivo, ¿por qué no arrojo pelotas? Es decir, en lugar de muestreo de elementos , nosotros, los subconjuntos de la muestra . Seguramente debería poder inferir algo sobre la densidad de en partir de este experimento.A X $x \in A$$A$$X$$A$

Supongamos que está equipado con una métrica (tengo en cuenta la distancia de Hamming). Para cualquier sea sea ​​la bola cerrada de radio en centrada en . Como podemos muestrear elementos uniforme al azar, podemos muestrear bolas uniforme al azar.d ( x , y ) y ∈ A Y ( y ) = { x ∈ A : d ( x , y ) ≤ k } k A t x ∈ A k Y k ( t $A$$d(x,y)$$y \in A$$Y(y)=\{x \in A:d(x,y) \leq k\}$$k$$A$$t$$x \in A$$k$$Y_k(t)$

Suponga que (a) cada pertenece exactamente al mismo número de bolas y (b) cada bola tiene el mismo tamaño .k k $x \in A$$k$$k$$r$

Ahora supongamos que genero bolas uniformemente al azar y supongamos que. Parece que podemos estimarde manera similar, es decir .Y 1 , Y 2 , … , Y n m = ∑ n i = 1 | Y i ∩ X | El | A | El | X | / | A | ≈ $k$$Y_1,Y_2,\ldots,Y_n$$m=\sum_{i=1}^n |Y_i \cap X|$$|A|$$|X|/|A| \approx \frac{m}{rn}$

Entonces mis preguntas son:

¿Tengo razón en que podemos aproximarnos¿de esta manera? Si es así, dudo que sea el primero en pensar en esto, ¿hay algún nombre para este método?$|X|$

Realmente probé esto en algunos sets, y parece coincidir con lo que afirmo.

¿Hay algún inconveniente en este enfoque? (por ejemplo, ¿es menos preciso? ¿Necesito más muestras?)

OK, intente leer la página de Wikipedia para la integración de Monte Carlo . Verás que mencionan una versión estratificada. Estratificación es el término técnico en estadística para lo que intenta: subdividir en subconjuntos (submuestras). Supongo que las referencias pueden ayudarte más.

Para cualquier subconjunto de , sea la probabilidad de que lo seleccione en su muestreo. Has descrito una variable aleatoriaA π ( Y $Y$$A$$\pi(Y)$

$$f(Y) = |Y \cap X|.$$

El total de en la población de subconjuntos de es$f$$A$

$$\tau(X) = \sum_{Y \subset A}|Y \cap X| = 2^{|A|-1}|X|.$$

De una muestra (con reemplazo) de subconjuntos de , digamos , el Estimador Hansen-Hurwitz obtiene una estimación imparcial de este total comoY 1 , Y 2 , ... , Y $A$$Y_1, Y_2, \ldots, Y_m$

$$\hat{f}_\pi = \sum_{i=1}^{m} \frac{|Y_i \cap X|}{\pi(Y_i)} .$$

Dividiendo esto porpor lo tanto, estima. La varianza de esEl | X | / | A | f$2^{|A|-1}|A|$$|X|/|A|$$\hat{f}_\pi$

$$\text{Var}(\hat{f}_\pi) = \frac{1}{m} \sum_{Y \subset A} \pi(Y) \left( \frac{|Y \cap X|}{\pi(Y)} - 2^{|A|-1}|X| \right)^2\text{.}$$

Al dividir esto entre obtiene la varianza de muestreo de. Dados , y un procedimiento de muestreo propuesto (que especifica para todo ), elija un valor de (el tamaño de la muestra) para el cual la varianza de estimación se vuelve aceptablemente pequeña.| X | $2^{2(|A|-1)}|A|^2$A X π ( Y ) Y ⊂ A $|X|/|A|$$A$$X$$\pi(Y)$$Y \subset A$$m$

Supongo que tu medida es finita. WLOG puede ser una probabilidad.

El primer procedimiento que menciona es la buena estimación empírica de probabilidad :

$\hat{P}(Y\in X)= | \{ x_i \in X\} | /n$

(hay una estimación de montecarlo de un inetgral es una buena interpretación también). En la dimensión alta no funciona ya que es probable que esté vacío para la típica A. Como ha notado, necesita regularización. La sofisticada regularización que necesita está relacionada con la dimensión de su espacio.$\{x_i\in X\}$

Una idea es agrandar o incluso darle un peso a que no está en acuerdo con su distancia a , esto es lo que yo llamaría estimación de probabilidad de kernel (por analogía con la estimación de densidad de kernel ):x i X $X$$x_i$$X$$X$

$\hat{P}(Y\in X)= 1/(c(k) n)\sum_{i} K(d(x_i,X)/k)$

donde es un núcleo que se integra a (en su caso puede ser pero el núcleo gaussiano tiene buenas propiedades) y una constante de normalización bien elegida (es decir, tal that ).1 K ( x ) = 1 { x ≤ 1 } c ( k ) P ( Y ∈ A ) = $K$$1$$K(x)=1\{x\leq 1\}$$c(k)$$\hat{P}(Y\in A)=1$