Ожидаемое число уникальных образов

[error420]

Пусть есть случайная функция $h: M \rightarrow N$. Мы хотим посчитать мат ожидание мощности следующего множества $B: \{y: \exists x: h(x)=y\}$. Соответственно $\Pr[h(x)=y] =\frac{1}{N}$. Мы можем на прямую задать данное мат ожидание следующей формулой: $E( \text{size of B}) = \frac{1}{N}^M \cdot \sum_{i=1}^{N} i \cdot \binom{N}{i} \cdot \binom{M-1}{k-1}$. Но такую сумму вычислить проблематично для больших значений. Хотелось бы ее свернуть каким-нибудь образом или получить хорошую оценку этому числу. Точной свертки кажется не существует, так как у нас частичная сумма биномиального коэффициента, такие вроде не вычисляются. Оценку дать затрудняюсь.

[mihaild]

Так $|B| = \sum_{x \in N} [x \in B]$. Заносим мат. ожидание под сумму и получаем легко считаемую вероятность.

[error420]

mihaild в сообщении #1530818 писал(а):

Так $|B| = \sum_{x \in N} [x \in B]$. Заносим мат. ожидание под сумму и получаем легко считаемую вероятность.

Ничего не понял. $|B| = \sum_{x \in N} [x \in B]$ - это какое-то тривиальное утверждение, записанное нетривиальном образом, если я его правильно понял. А куда что занести чтобы свернулось что-то я пока понять не в состоянии из Вашего комментария. Не могли бы Вы пожалуйста уточнить свою мысль.

[mihaild]

Вы можете найти мат. ожидание $[x \in B]$ (оно же $P(x \in B)$)?

[Евгений Машеров]

Откуда берутся иксы? Они как-то случайно выбираются, и если да - с равной ли вероятностью и из какого множества?

[error420]

-- 07.09.2021, 11:25 --

Евгений Машеров в сообщении #1530853 писал(а):

Откуда берутся иксы? Они как-то случайно выбираются, и если да - с равной ли вероятностью и из какого множества?

$x \in M$, они не выбираются. Мы хотим посмотреть на реальный образ функции а не на множество возможных значений. Соответственно в опеределении множества $B$ стоит знак "существует". Мы хотим найти все такие $y$ для которых существует прообраз. Функция же $h$ строилась таким образом что $\forall y \in N \Pr[h(x) = y] = \frac{1}{N}$

-- 07.09.2021, 11:37 --

mihaild в сообщении #1530820 писал(а):

Вы можете найти мат. ожидание $[x \in B]$ (оно же $P(x \in B)$)?

$P(x \in B) = 1 - P( x \notin B) = 1 - (\frac{N-1}{N})^M = 1 - (1- \frac{1}{N})^M$.

Таким образом $|B| = N \cdot (1 - (1 - \frac{1}{N})^M)$.

Спасибо

[Евгений Машеров]

Если Вы хотите матожидание, то должны вводить вероятность.

[mihaild]

error420 в сообщении #1530862 писал(а):

Таким образом $|B| = N \cdot (1 - (1 - \frac{1}{N})^M)$.

Так писать нехорошо. $|B|$ - это случайная величина, не константная, если $|M| > 1$, она не может быть равна числу.

[Geen]

Попробую перевести задачу на русский.
Мы $M$ раз равновероятно выбираем одно из $N$ значений (с возвратом).
Определим случайную величину как количество (различных) выбранных значений.
Необходимо найти математическое ожидание этой случайной величины.