Expectativa da soma dos números K sem substituição

Dados números, em que o valor de cada número é diferente, indicado como , e a probabilidade de selecionar cada número é , respectivamente. $n$ $v_1, v_2, ..., v_n$ $p_1, p_2, ..., p_n$

Agora, se eu selecionar números $K$ base nas probabilidades fornecidas, onde $K \leq n$ , qual é a expectativa da soma desses números $K$ ? Observe que a seleção é sem substituição, para que os números $K$ não possam envolver números duplicados. Entendo que, se a seleção for com substituição, a expectativa da soma dos números $K$ é igual a $K \times E(V)$ , onde

E (V) = v_{1} \times p_{1} + v_{2} \times p_{2} + . . . + v_{n} \times p_{n} .

$E(V) = v_1 \times p_1 + v_2 \times p_2 + ... + v_n \times p_n.$

Além disso, e a expectativa da variação desses números $K$ ?

Eu sou um estudante de doutorado em CS que está trabalhando em um problema de grande volume de dados e não tenho formação em estatística. Espero que alguém possa me dar uma fórmula como resposta. No entanto, se a resposta for muito complicada para ser descrita por uma fórmula ou for necessário envolver computação intensiva, uma resposta aproximada é totalmente aceitável.

Você pode assumir que $n$ aqui é bastante grande e a probabilidade pode variar muito. Na prática, os valores dessas probabilidades vêm de um log de consultas, que registra uma série de consultas de agregação. O ponto é que a frequência de cada número envolvido nas consultas pode ser bastante distorcida, ou seja, alguns são raramente consultados, enquanto outros são consultados com muita frequência. Você pode assumir que a distribuição de probabilidade é distribuição normal, distribuição zipf ou qualquer outra alternativa razoável.

A distribuição de valor é apenas um subconjunto contíguo de qualquer distribuição possível. Em outras palavras, se você tiver um histograma que represente uma determinada distribuição, todos os números envolvidos nesse problema serão todos em um único intervalo.

Em termos do valor de K, você pode supor que seja sempre menor que o número de elementos frequentemente consultados.

probability SciPioneer
fonte

A expectativa da variação da soma será diferente sem substituição; você precisará de um fator finito de correção populacional se não houver substituição. (Para ver isso intuitivamente, observe que, se K = n, a variação da soma é zero, porque sempre será o mesmo número; de modo que K se aproxima de n, a variação da soma será menor.)

zbicyclist

Essa pergunta pode ser mais complicada do que parece. Considere o caso e . A soma esperada de dois valores sorteados com substituição é que é o dobro da soma esperada de um valor, é claro; mas a soma esperada de dois valores desenhados sem substituição obviamente é exceto quando .

n = 2

$n=2$

(v_{1}, v_{2}) = (0, 1)

$(v_1,v_2)=(0,1)$

2 p_{2}

$2p_2$

v_{1} + v_{2} = 1 \neq 2 p_{2}

$v_1+v_2=1\ne 2p_2$

p_{1} = p_{2} = 1 / 2

$p_1=p_2=1/2$

whuber

@ zbicyclist Talvez eu não tenha declarado o problema claramente. No meu cenário, se K = N, então a variação desses números K será a variação da população geral em vez de 0. #

SciPioneer

(1) Isso não me parece uma pergunta de auto-estudo : parece um verdadeiro problema aplicado em probabilidade. (2) Como grande poder ser? As soluções exatas parecem impraticáveis, exceto quando todos os subconjuntos podem ser enumerados. (3) Se puder ser muito maior que , impedindo a enumeração rápida, o que você pode dizer sobre o ? Por exemplo, eles podem variar ou serão todos muito próximos de ? Isso poderia informar os esforços para encontrar respostas aproximadas.

n

$n$

n

$n$

20

$20$

p_{i}

$p_i$

1 / n

$1/n$

whuber

Obrigado pelas edições. Quanto mais você puder nos contar sobre , , e , melhor. Por exemplo, se então as fórmulas para amostragem com substituição devem ser boas aproximações (porque poucos valores, se houver, seriam selecionados mais de uma vez). Eu acredito que os casos mais difíceis são onde existe uma ampla gama de valores de - para que você não possa simplesmente substituir a maioria deles por zeros e ainda por para um número apreciável de e .

N

$N$

K

$K$

v_{i}

$v_i$

p_{i}

$p_i$

K max (p_{i}) ≪ 1

$K\max(p_i)\ll 1$

p_{i}

$p_i$

p_{i} > 1 / K

$p_i\gt 1/K$

i

$i$

K \approx N / 2

$K\approx N/2$

whuber

Respostas:

Provavelmente, essa é a natureza de uma resposta que, embora exata, provavelmente não é tão útil. Horvitz e Thompson (1952) fornecem resultados que cobrem essa situação em geral. Esses resultados são dados em termos das expressões combinatórias que se pode esperar.

Para manter a consistência com a notação e também corresponder melhor com a notação mais usada, permita-me redefinir algumas quantidades. Deixe que é o número de elementos na população e ser o tamanho da amostra. $N$ $n$

Seja , , represente os elementos da população, com os valores , e probabilidades de seleção . Para uma determinada amostra de tamanho , permita que os valores observados na amostra sejam . $u_i$ $i=1,...,N$ $N$ $V_i$ $i=1,...,N$ $p_1,...,p_N$ $n$ $v_1,..., v_n$

O que se deseja é a média e a variação do total da amostra

\sum_{i = 1}^{n} v_{i} .

$\sum_{i=1}^n v_i.$

Como mencionado nos comentários, a probabilidade de selecionar uma amostra específica desenhada nessa ordem é onde a probabilidade inicial de desenhar é dada por , a segunda probabilidade de desenhar depende de ter removido da população e assim por diante. Portanto, cada unidade subsequente sorteada resulta em uma nova distribuição de probabilidade para a próxima unidade (portanto, a escolha de letras indiciais diferentes, porque cada uma representa uma distribuição diferente). $s = \{u_i, u_j, ..., u_t\}$

Pr (s) = p_{i_{1}} p_{j_{2}} \dots p_{t_{n}},

$\textrm{Pr}(s) = p_{i_1}p_{j_2}\cdots p_{t_n},$

p_{i_{1}}

$p_{i_1}$

u_{i}

$u_i$

p_{i}

$p_i$

p_{j_{2}}

$p_{j_2}$

u_{j}

$u_j$

u_{i}

$u_i$

Existem amostras de tamanho que contêm de toda a população. Observe que isso leva em conta opermutações da amostra.

S^{(i)} = n! (\binom{N - 1}{n - 1})

$S^{(i)} = n! \binom{N-1}{n-1}$

n

$n$

u_{i}

$u_i$

n!

$n!$

Deixe denotar uma amostra específica de tamanho que inclui . Então, a probabilidade de selecionar o elemento é dada por onde a soma está acima do conjunto de tamanho de todas as amostras possíveis do tamanho que contêm . (Mudei a notação um pouco do papel, pois me pareceu confuso.) $s_n^{(i)}$ $n$ $u_i$ $u_i$

P (u_{i}) = \sum Pr (s_{n}^{(i)}),

$P(u_i) = \sum \textrm{Pr}(s_n^{(i)}),$

S^{(i)}

$S^{(i)}$

s_{n}^{(i)}

$s_n^{(i)}$

n

$n$

u_{i}

$u_i$

Da mesma forma, defina como o número de amostras que contêm e . Em seguida, podemos definir a probabilidade de uma amostra contendo ambos como onde a soma está acima do conjunto de tamanho de todas as amostras possíveis de tamanho que contêm e .

S^{(i j)} = n! (\binom{N - 2}{n - 2})

$S^{(ij)} = n! \binom{N-2}{n-2}$

u_{i}

$u_i$

u_{j}

$u_j$

P (u_{i} u_{j}) = \sum Pr (s_{n}^{(i j)}),

$\textrm{P}(u_i u_j) = \sum \textrm{Pr}(s_n^{(ij)}),$

S^{(i j)}

$S^{(ij)}$

s_{n}^{(i j)}

$s_n^{(ij)}$

n

$n$

u_{i}

$u_i$

u_{j}

$u_j$

O valor esperado é então derivado como

E (\sum_{i = 1}^{n} v_{i}) = \sum_{i = 1}^{N} P (u_{i}) V_{i} .

$E \left( \sum_{i=1}^n v_i \right) = \sum_{i=1}^N \textrm{P}(u_i) V_i.$

Embora a variância não é derivado explicitamente no papel, pode ser obtido a partir de expections do th momento e os produtos cruzados $q$

E (\sum_{i = 1}^{n} v_{i}^{q}) = \sum_{i = 1}^{N} P (u_{i}) V_{i}^{q}

$E \left( \sum_{i=1}^n v_i^q \right) = \sum_{i=1}^N \textrm{P}(u_i) V_i^q$

E (\sum_{i \neq j}^{n} v_{i} v_{j}) = \sum_{i \neq j} P (u_{i} u_{j}) V_{i} V_{j} .

$E \left( \sum_{i \ne j}^n v_iv_j \right) = \sum_{i \ne j} \textrm{P}(u_i u_j) V_i V_j.$

Em outras palavras, parece que seria necessário passar por todos os subconjuntos possíveis para fazer esses cálculos. Talvez isso possa ser feito para valores menores de , no entanto. $n$

Horvitz, DG e Thompson, DJ (1952) Uma generalização da amostragem sem substituição de um universo finito. Jornal da Associação Estatística Americana 47 (260): 663-685.

jvbraun
fonte