Из {1,...,N} случайно выбирается k подмножеств с возвращением. Найти вероятность того, что а)никакие 2 не пересекаются. б) множества не имеют общего элемента.

Помогите, пожалуйста, никак не получается решить.

задан 29 Май '17 11:55

изменен 29 Май '17 22:17

10|600 символов нужно символов осталось
0

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

Удобно считать, что у нас получается случайная матрица kxn из нулей и единиц. Условие a_{ij}=1 означает, что i-му подмножеству принадлежит j-й элемент.

а) Отсутствие попарных пересечений означает, что каждый столбец или нулевой, или в нём ровно одна единица. Таких столбцов k+1. Вероятность того, что заданный столбец окажется таким, равна (k+1)/2^k. Вероятность, что все n столбцов такие, равна ((k+1)/2^k)^n.

б) Наличие общего элемента для всех подмножеств означает, что есть столбец из одних единиц. Вероятность того, что заданный столбец таковым не является, равна (2^k-1)/2^k=1-2^{-k}. Вероятность того, что все столбцы неединичны, равна (1-2^{-k})^n.

ссылка

отвечен 30 Май '17 0:35

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,958

задан
29 Май '17 11:55

показан
849 раз

обновлен
30 Май '17 0:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru