Ожидание суммы K чисел без замены

Для заданных чисел, где значение каждого числа различно, обозначается как , и вероятность выбора каждого числа равна соответственно. $n$ $v_1, v_2, ..., v_n$ $p_1, p_2, ..., p_n$

Теперь, если я выберу чисел на основе заданных вероятностей, где , каково ожидание суммы этих чисел? Обратите внимание, что выбор без замены, так что номера не могут включать повторяющиеся числа. Я понимаю, что если выбор сделан с заменой, ожидание суммы чисел равно , где $K$ $K \leq n$ $K$ $K$ $K$ $K \times E(V)$

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.$

Кроме того, как насчет ожидания дисперсии этих чисел ? $K$

Я учусь в аспирантуре, работаю над проблемой больших данных, и у меня нет статистических данных. Я ожидаю, что кто-то может дать мне формулу в качестве ответа. Однако, если ответ слишком сложен, чтобы его можно было описать формулой, или требуются интенсивные вычисления, приблизительный ответ является полностью приемлемым.

Вы можете предположить, что здесь довольно велико, и вероятность может сильно варьироваться. На практике значения этих вероятностей берутся из журнала запросов, в котором записана серия запросов агрегации. Дело в том, что частота каждого числа, участвующего в запросах, может быть довольно искаженной, то есть некоторые запрашиваются редко, а некоторые запрашиваются очень часто. Вы можете предположить, что распределение вероятностей - это нормальное распределение, распределение zipf или любые другие разумные альтернативы. $n$

Распределение значений является только непрерывным подмножеством любого возможного распределения. Другими словами, если у вас есть гистограмма, которая представляет определенное распределение, все числа, вовлеченные в эту проблему, являются числами в пределах одного сегмента.

Что касается значения K, вы можете предположить, что оно всегда меньше количества часто запрашиваемых элементов.

probability SciPioneer
источник

Ожидание дисперсии суммы будет отличаться без замены; вам понадобится конечный поправочный коэффициент населения, если нет замены. (Чтобы понять это интуитивно, обратите внимание, что если K = n, дисперсия суммы равна нулю, потому что она всегда будет одним и тем же числом; поэтому, когда K приближается к n, дисперсия суммы будет ниже.)

zbicyclist

Этот вопрос может быть сложнее, чем может показаться. Рассмотрим случай и . Ожидаемая сумма двух значений, полученных с заменой, равна что вдвое больше ожидаемой суммы одного значения, конечно; но ожидаемая сумма двух значений, выведенных без замены, очевидно, равна за исключением случаев, когда .

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 Возможно, я не четко сформулировал проблему. В моем сценарии, если K = N, тогда дисперсия этих чисел K будет дисперсией общего населения, а не 0.

SciPioneer

(1) Для меня это не похоже на вопрос для самостоятельного изучения : это похоже на настоящую прикладную проблему вероятности. (2) Насколько большим может быть ? Точные решения выглядят неосуществимыми, за исключением случаев, когда можно перечислить все подмножества. (3) Если может быть намного больше или около того, исключая быстрое перечисление, что вы можете сказать о ? Например, могут ли они меняться или все они будут очень близки к ? Это может помочь в поиске приблизительных ответов.

n

$n$

n

$n$

20

$20$

p_{i}

$p_i$

1 / n

$1/n$

whuber

Спасибо за правки. Чем больше вы можете рассказать нам о , , и , тем лучше. Например, если то формулы для выборки с заменой должны быть хорошими приближениями (потому что очень мало значений, если таковые имеются, будут выбраны более одного раза). Я считаю, что самые сложные случаи - это широкий диапазон значений так что вы не можете просто заменить большинство из них нулями, но при этом для значительного числа - и .

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

Ответы:

Это, вероятно, характер ответа, который, хотя и точен, вероятно, не так полезен. Horvitz and Thompson (1952) дают результаты, которые охватывают эту ситуацию в целом. Эти результаты приведены в терминах комбинаторных выражений, которые можно ожидать.

Чтобы соответствовать их обозначениям, а также лучше соответствовать более широко используемым обозначениям, позвольте мне переопределить некоторые величины. Пусть будет количеством элементов в совокупности, а будет размером выборки. $N$ $n$

Пусть , , представляют элементов совокупности с заданными значениями , и вероятностями выбора . Для данной выборки размера пусть наблюдаемые значения в выборке будут . $u_i$ $i=1,...,N$ $N$ $V_i$ $i=1,...,N$ $p_1,...,p_N$ $n$ $v_1,..., v_n$

Что желательно, так это среднее значение и дисперсия итоговой выборки

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

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

Как упоминалось в комментариях, вероятность выбора конкретного образца нарисованного в этом порядке, равна где начальная вероятность рисования задается , вторая вероятность рисования обусловлена удалением из совокупности и так далее. Таким образом, каждая последующая нарисованная единица приводит к новому распределению вероятности для следующей единицы (следовательно, выбор различных условных букв, потому что каждая представляет различное распределение.) $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$

Есть выборок размера которые содержат из всей совокупности. Обратите внимание, что это учитываетперестановки образца.

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

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

n

$n$

u_{i}

$u_i$

n!

$n!$

Пусть обозначает конкретную выборку размера которая включает в себя . Тогда вероятность выбора элемента задается где суммирование ведется по множеству размера из все возможные образцы размера , содержащие . (Я немного изменил обозначения на бумаге, потому что мне это показалось непонятным.) $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$

Аналогично, определите как число выборок, содержащих как и . Затем мы можем определить вероятность выборки, содержащей как где суммирование по набору размера из всех возможных выборок размера которые содержат и .

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$

Ожидаемое значение затем получается как

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.$

Хотя дисперсия не получена явно в статье, она может быть получена из ожиданий го момента и перекрестные произведения $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.$

Другими словами, похоже, что для выполнения этих вычислений потребуется пройти через все возможные подмножества. Возможно, это можно сделать для меньших значений , хотя. $n$

Horvitz, DG и Thompson, DJ (1952) Обобщение выборки без замены из конечной вселенной. Журнал Американской статистической ассоциации 47 (260): 663-685.

jvbraun
источник