Ожидаемое количество различных цветов при рисовании без замены

Рассмотрим урну, содержащую шариков разных цветов, причем - это пропорция шариков цвета среди шариков ( ). Я рисую шариков из урны без замены и смотрю на число разных цветов среди нарисованных шариков. Каково ожидание как функции , в зависимости от подходящих свойств распределения ? $N$ $P$ $p_i$ $i$ $N$ $\sum_i p_i = 1$ $n \leq N$ $\gamma$ $\gamma$ $n/N$ $\mathbf{p}$

Чтобы лучше понять: если и для всех , то я всегда буду видеть ровно цветов, то есть . В противном случае, можно показать , что ожидание - IS . Казалось бы, для фиксированных и коэффициент умножения будет максимальным, если равномерен; может быть, ожидаемое количество разных цветов будет ограничено функцией и, например, энтропией ? $N = P$ $p_i = 1/P$ $i$ $n$ $\gamma = P (n/N)$ $\gamma$ $>P(n/N)$ $P$ $N$ $n/N$ $\mathbf{p}$ $n/N$ $\mathbf{p}$

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

probability expected-value coupon-collector-problem a3nm
источник

Я думаю, что эту проблему можно сформулировать так: каково ожидаемое число ненулевых элементов в выборке из многомерного гипергеометрического распределения ?

Kodiologist

Ответы:

Предположим , у вас есть цветов , где . Пусть обозначаю число шаров цвета так . Пусть , и пусть фиксировать множества, состоящие из элементных подмножеств . Пусть элементов из вышеуказанного набора таковы, что количество разных цветов в выбранном наборе равно . За $k$ $k \leq N$ $b_i$ $i$ $\sum b_i = N$ $B = \{b_1, \ldots, b_k\}$ $E_i(B)$ $i$ $B$ обозначает количество способов, которыми мы можем выбрать $Q_{n, c}$ $n$ $c$ формула проста: $c = 1$

Q_{n, 1} = \sum_{E \in E_{1} (B)} (\binom{\sum_{e \in E} e}{n})

$Q_{n, 1} = \sum_{E \in E_{1}(B)}\binom{\sum_{e \in E}e}{n}$

Для $c = 2$ мы можем считать наборы шариков размером которые имеют не более 2 цветов, минус количество наборов, которые имеют ровно цвет: $n$ $1$

Q_{n, 2} = \sum_{E \in E_{2} (B)} (\binom{\sum_{e \in E} e}{n}) - (\binom{k - 1}{1}) Q_{n, 1}

$Q_{n,2} = \sum_{E \in E_{2}(B)}\binom{\sum_{e \in E}e}{n} - \binom{k - 1}{1}Q_{n, 1}$

$\binom{k - 1}{1}$ - это количество способов добавить цвет к фиксированному цвету, чтобы у вас было 2 цвета, если у вас всего цветов. Общая формула, если у вас есть фиксированные цвета и вы хотите сделать $k$ $c_1$ $c_2$ из них цвета , а общее количество цветов ( ) равно . Теперь у нас есть все, чтобы вывести общую формулу для : $k$ $c_1 \leq c_2 \leq k$ $\binom{k - c_1}{c_2 - c_1}$ $Q_{n, c}$

Q_{n, c} = \sum_{E \in E_{c} (B)} (\binom{\sum_{e \in E} e}{n}) - \sum_{i = 1}^{c - 1} (\binom{k - i}{c - i}) Q_{n, i}

$Q_{n, c} = \sum_{E \in E_{c}(B)}\binom{\sum_{e \in E}e}{n} - \sum_{i = 1}^{c - 1}\binom{k - i}{c - i}Q_{n, i}$

Вероятность того, что у вас будет ровно цветов, если вы нарисуете шаров, равна: $c$ $n$

P_{n, c} = Q_{n, c} / (\binom{N}{n})

$P_{n, c} = Q_{n, c} / \binom{N}{n}$

Также обратите внимание, что если . $\binom{x}{y} = 0$ $y > x$

Вероятно, есть особые случаи, когда формула может быть упрощена. Я не удосужился найти эти упрощения на этот раз.

Ожидаемое значение числа цветов, зависящее от следующее: $n$

γ_{n} = \sum_{i = 1}^{k} P_{n, i} * i

$\gamma_{n} = \sum_{i = 1}^{k} P_{n, i} * i$

jakab922
источник

Вы называете вероятностью, но, похоже, вы определили ее как сумму целых чисел. Вы забыли разделить на что-то?

P_{n, c}

$P_{n,c}$

Кодиолог

Да, я думаю, ты прав. Вам нужно разделить на , но, к сожалению, все равно это не так. Если и я делаю двойной расчет в приведенной выше формуле.

(\binom{N}{n})

$\binom{N}{n}$

E, F \in E_{c} (B)

$E, F \in E_{c}(B)$

E \cap F \neq \emptyset

$E \cap F \neq \emptyset$

jakab922

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

jakab922