2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Ожидаемое число уникальных образов
Сообщение06.09.2021, 19:13 


02/04/18
44
Пусть есть случайная функция $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}$. Но такую сумму вычислить проблематично для больших значений. Хотелось бы ее свернуть каким-нибудь образом или получить хорошую оценку этому числу. Точной свертки кажется не существует, так как у нас частичная сумма биномиального коэффициента, такие вроде не вычисляются. Оценку дать затрудняюсь.

 Профиль  
                  
 
 Re: Ожидаемое число уникальных образов
Сообщение06.09.2021, 19:28 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Ожидаемое число уникальных образов
Сообщение06.09.2021, 19:35 


02/04/18
44
mihaild в сообщении #1530818 писал(а):
Так $|B| = \sum_{x \in N} [x \in B]$. Заносим мат. ожидание под сумму и получаем легко считаемую вероятность.



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

 Профиль  
                  
 
 Re: Ожидаемое число уникальных образов
Сообщение06.09.2021, 19:44 
Заслуженный участник
Аватара пользователя


16/07/14
8352
Цюрих
Вы можете найти мат. ожидание $[x \in B]$ (оно же $P(x \in B)$)?

 Профиль  
                  
 
 Re: Ожидаемое число уникальных образов
Сообщение07.09.2021, 09:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Ожидаемое число уникальных образов
Сообщение07.09.2021, 11:21 


02/04/18
44
-- 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)$.

Спасибо

 Профиль  
                  
 
 Re: Ожидаемое число уникальных образов
Сообщение07.09.2021, 11:48 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Если Вы хотите матожидание, то должны вводить вероятность.

 Профиль  
                  
 
 Re: Ожидаемое число уникальных образов
Сообщение07.09.2021, 11:55 
Заслуженный участник
Аватара пользователя


16/07/14
8352
Цюрих
error420 в сообщении #1530862 писал(а):
Таким образом $|B| = N \cdot (1 - (1 - \frac{1}{N})^M)$.
Так писать нехорошо. $|B|$ - это случайная величина, не константная, если $|M| > 1$, она не может быть равна числу.

 Профиль  
                  
 
 Re: Ожидаемое число уникальных образов
Сообщение07.09.2021, 12:17 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group