¿Cómo la muestra sin reemplazo con una función de muestreo con reemplazo?

Question

Yo vagamente recuerdo de la escuela de posgrado que el siguiente es un enfoque válido para hacer un promedio ponderado de muestreo sin reemplazo:

1. Empezar con un vacío inicialmente "muestreadas conjunto".
2. Sorteo de una (sola) muestra ponderada con la sustitución con cualquiera que sea el método que usted tiene.
3. Comprobar si ya has escogido.
4. Si no, ignorarlo y pasar a la siguiente muestra. Si no, añadir a su conjunto muestreado.
5. Repita 2-4 hasta que la muestra de conjunto es del tamaño deseado.

Será esto me da una válida ponderado de la muestra?

(Contexto: por muy grande de muestras, R sample(x,n,replace=FALSE,p) toma un tiempo muy largo, mucho más largo que la aplicación de la estrategia anterior).

ACTUALIZACIÓN 2012-01-05

Gracias a todos por sus comentarios y respuestas! Sobre el código, he aquí un ejemplo que reproduce fielmente lo que yo estoy tratando de hacer (aunque en realidad estoy llamando R desde Python con RPy, pero parece que el tiempo de ejecución de las características son iguales).

En primer lugar, definir la siguiente función, que supone una suficientemente larga secuencia de con-reemplazo de muestras de entrada:

get_rejection_sample <- function(replace_sample, n) {
    top = length(replace_sample)
    bottom = 1
    mid = (top+bottom)/2
    u = unique(replace_sample[1:mid])
    while(length(u) != n) {
        if (length(u) < n) {
            bottom = mid
        }
        else {
            top = mid
        }
        mid = (top+bottom)/2
        u = unique(replace_sample[1:mid])
        if (mid == top || mid == bottom) {
            break
        }
    }
    u
}

Simplemente realiza una búsqueda binaria para el número de no-singulares muestras necesarias para obtener suficientes muestras únicas. Ahora, en el intérprete:

> x = 1:10**7
> w = rexp(length(x))
> system.time(y <- sample(x, 500, FALSE, w))
   user  system elapsed 
 12.820   0.048  12.902 
> system.time(y <- get_rejection_sample(sample(x, 1000, TRUE, w), 500))
   user  system elapsed 
  0.311   0.066   0.378 
Warning message:
In sample(x, 1000, TRUE, w) :
  Walker's alias method used: results are different from R < 2.2.0

Como se puede ver, aunque sea por sólo 500 de los elementos que la diferencia es enorme. En realidad estoy tratando de muestra $10^6$ índices a partir de una lista de alrededor de $1.2 \times 10^7$, que tiene horas de uso replace=FALSE.

Answer 1

Para que esto vale la pena hacer en lugar de utilizar el sample función en son el vector es mayor en tamaño o muestreo de las necesidades que sobre 1e7 y la muestra tiene que ser relativamente pequeña... dicen 1e2. Si la muestra que se desea es mucho más grande que es muestreo de menor sample será más rápido. Pero una vez que se alcanza un punto de inflexión un método como Juan describe será mucho más rápido.

Answer 2

Se describe una secuencia de rechazo de muestras.

Por definición, después de la selección de $k$ objetos en el proceso de obtención de una muestra ponderada de $m$ objetos sin reemplazo de una lista de $n$ objetos, dibujar uno de los restantes $n-k$ objetos de acuerdo a sus pesos relativos. En su descripción de la alternativa esquema de muestreo, en la misma etapa que va a ser el dibujo de todas las $n$ objetos de acuerdo a sus pesos relativos, pero usted va a tirar cualquier objeto igual a uno de los primeros a $k$ e inténtelo de nuevo: ese es el rechazo. Así que todo lo que tiene que convencerse de que es la probabilidad de extraer una de las restantes $n-k$ objetos es el mismo en ambos casos.

Si esta equivalencia no es perfectamente claro, no hay una clara demostración matemática. Deje que el peso de la primera $k$ objetos se $w_1, \ldots, w_k$ y dejar que el peso del resto de las $n-k$ objetos se $w_{k+1}, \ldots, w_n$. Escribir $w = w_1 + w_2 + \cdots + w_n$ y deje $w_{(k)} = w_1 + w_2 + \cdots + w_k$. La oportunidad de objeto de dibujo $i$ ($k \lt i \le n$) sin el reemplazo de las $n-k$ restante objetos, por supuesto

$$\frac{w_i}{w_{k+1} + w_{k+2} + \cdots + w_n} =\frac{w_i}{w-w_{(k)}}.$$

En la alternativa (rechazo) esquema, la probabilidad de extraer el objeto $i$ es igual a

$$\sum_{a=0}^\infty \left[\left(\frac{w_{(k)}}{w}\right)^a \frac{w_i}{w}\right] =\frac{1}{1 - w_{(k)}/w}\frac{w_i}{w} = \frac{w_i}{w-w_{(k)}}$$

exactamente como antes. La suma surge al dividir el evento por el número de rechazos ($a$) que preceden a los elementos de dibujo $i$; sus condiciones de dar la oportunidad de una secuencia de $a$ atrae desde el primer $k$ elementos seguido por el dibujo de la $i^\text{th}$ elemento: debido a que estos sorteos son independientes, sus posibilidades se multiplican. Forma una serie geométrica que es elemental para poner en forma cerrada (la primera igualdad). La segunda igualdad es un trivial algebraica de reducción.