Probabilidad de elegir determinado en un experimento de "muestreo ponderado sin reemplazo"

Question

Dado $n$ elementos con peso $w_n$ cada uno - ¿cuál es la probabilidad de que el elemento $i$ es elegido en un $k$- $n$ "ponderado de muestreo aleatorio sin reemplazo" experimento? Puede una forma cerrada de solución que sólo depende de $w_i / w_\cdot$ derivados ($w_\cdot = \sum_j w_j$.)?

EDIT: UNA solución que sólo depende de $w_i / w_\cdot$ es imposible. Asumir $n=3$, $i=1$, $w_1 = 1$, y dos casos: (1) $w_2 = 1, w_3 = 1 + \varepsilon$, (2) $w_2 = 2, w_3 = \varepsilon > 0$. En caso de que (1) la probabilidad es casi $2/3$, en el caso de (2) es casi la $1$, pero en ambos casos $w_1 = 1$$w_\cdot = 3 + \varepsilon$.

Lo que he intentado hasta ahora para resolver el problema:

Deje $P^n_k(w, i)$ la probabilidad de que el elemento $i$ es elegido en un $k$- $n$ experimento con el peso de vectores $w$. En el primer sorteo, el elemento está seleccionado con probabilidad de $w_i / w_\cdot$. De lo contrario, estamos buscando la probabilidad de elegir este elemento en un $k-1$- $n-1$ experimento, con el mismo peso vector excepto para el elemento que se ha seleccionado. Por lo tanto:

$$ P^n_k(w, i) = w_i / w_\cdot + \sum_{j \neq i} w_j / w_\cdot a \cdot P^{n-1}_{k-1}(w - j, i) $$ $$ = w_\cdot^{-1} \left( w_i + \sum_{j \neq i} w_j \cdot P^{n-1}_{k-1}(w - j, i) \right) $$

con $w-j$ "el vector $w$ sin $j$elemento th".

Cómo resolver esta relación de recurrencia? (Si es correcto del todo...)

Answer 1

Estoy tirando de este de Pavlos S. Efraimidis, Pablo G. Spirakis, Ponderado muestreo aleatorio con un embalse, el Procesamiento de la Información de las Letras, Volumen 97, número 5, De 16 de Marzo de 2006, Páginas 181-185, ISSN 0020-0190, 10.1016/j.ipl.2005.11.003.

Allí, los autores comienzan por describir un básico ponderado de muestreo aleatorio algoritmo con la siguiente definición:

Entrada: Una población $V$ $n$ ponderado de los elementos

Salida: Un conjunto de $S$ con los REPRESENTANTES de tamaño m

1. Repita los Pasos 2 y 3 para $k=1,2,...,m$
2. La probabilidad de $v_i$ para ser seleccionado es:$$p_i(k) = \frac{w_i} {\sum_S_j \in V - S ^ {w_j}}$$
3. Seleccionar aleatoriamente un elemento de $v_k \in V - S$ e insertarlo en $S$

Los autores explican cómo llegar a la probabilidad, pero lo voy a resumir. Empezando por el primer elemento, la probabilidad de que $w_n$ es seleccionada es su propio peso dividido por la suma de todos los pesos. $$\frac{w_n}{w_1 + w_2+w_3+...+w_n}$$ Bastante fácil. Ahora, la probabilidad de que cada elemento será elegido es el de su propio peso dividido por la suma de los restantes pesos. Si hacemos este cálculo para cada peso $w_i$ a fin de con $i=[1,n]$, llegamos a los autores resumen final ecuación para cualquier permutación $\Pi$:

$$ P(\Pi) = \prod_{i=1}^{n} {\frac{w_i} {w_1 + w_2 + ...+w_i}} $$

Es decir, la probabilidad de que un elemento es elegido puede ser definida como índices de un array $w$ que contiene todos los pesos, así: $$\frac{w(i)}{w([1,i])}$$

Esto no es particularmente difícil de trabajar, pero yo no quería crear la prueba a mí mismo, de ahí el entrecomillado de Efraimidis & Spirakis.