2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Вероятность пересечения двух множеств
Сообщение11.10.2014, 09:06 


29/04/14
139
Есть такая задача:
Из совокупности всех подмножеств множества $S = \{  1, 2, ..., N\}$ выбирают случайным образом (по схеме с возвращением) два множества $A_1, A_2$. Найти вероятность, что $A_1 \cap A_2 =  \varnothing $

Мои рассуждения:
1. Всего различных вариантов $2^N$, куда входит и $\varnothing$.
2. Всего вариантов взять по два множества из совокупности всех подмножеств $C_{2^N}^2 =  \frac{2^N !} { (2^{N} - 2)! 2! }$
3. Подсчитаем число удовлетворяющих нас случаев:
3.1 Понятно, что если мы возьмем пустое множество, как один двух элементов, то все остальные подойду под требование задачи, то есть $2^N$.
3.2 пусть мы выбрали одноэлементное множество, как одно из $A_1, A_2$, тогда всего непересекающихся вариантов $ N \cdot ( 2^{N-1} - 1) $, поскольку множество $S = \{  1, 2, ..., N\}$ без выбранного множества имеет мощность $N-1$ и всевозможные комбинации таким образом $2^{N-1}$. Отсюда следует вычесть пустое множесто, так как мы его уже учли (пункт 3.1)
3.3 Аналогичный расчет следует провести и для каждого выбора двухэлементного, трехэлементного и т.д множества. На каждом iм шаге справедлива будет формула всех комбинаций $C_{N}^i (2^{N-i} -1)$
3.4 Как посчитать сумму всех удовлетворяющих нас комбинаций $\sum_{i=0}^{N-1} C_{N}^i (2^{N-i} -1)$ я не знаю. Я могу ее посчитать без числа сочетаний, но в смысле решения этой задачи это не поможет.

 Профиль  
                  
 
 Re: Вероятность пересечения двух множеств
Сообщение11.10.2014, 10:06 
Аватара пользователя


14/10/13
339
xolodec в сообщении #917548 писал(а):
3.4 Как посчитать сумму всех удовлетворяющих нас комбинаций $\sum_{i=0}^{N-1} C_{N}^i (2^{N-i} -1)$ я не знаю.
$$\sum_{i=0}^{N-1} C_{N}^i (2^{N-i} -1) = \sum_{i=0}^{N-1} C_{N}^i 2^{N-i} - \sum_{i=0}^{N-1} C_{N}^i = \sum_{i=0}^{N-1} C_{N}^i \cdot 1^i \cdot 2^{N-i} -\sum_{i=0}^{N-1} C_{N}^i \cdot 1^i \cdot 1^{N-i}.$$

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


08/04/08
8556
xolodec в сообщении #917548 писал(а):
3.4 Как посчитать сумму всех удовлетворяющих нас комбинаций $\sum_{i=0}^{N-1} C_{N}^i (2^{N-i} -1)$ я не знаю.
бином Ньютона, слышали?

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


23/07/05
17973
Москва
xolodec в сообщении #917548 писал(а):
1. Всего различных вариантов $2^N$, куда входит и $\varnothing$.
Наверное, не вариантов, а подмножеств. (Впрочем, это, скорее, придирка.)
xolodec в сообщении #917548 писал(а):
2. Всего вариантов взять по два множества из совокупности всех подмножеств $C_{2^N}^2 =  \frac{2^N !} { (2^{N} - 2)! 2! }$
Написано ведь:
xolodec в сообщении #917548 писал(а):
по схеме с возвращением
Поэтому сочетания тут ни при чём.

 Профиль  
                  
 
 Re: Вероятность пересечения двух множеств
Сообщение11.10.2014, 18:39 


29/04/14
139
Благодарю за биномиальную формулу и число сочетаний!
Действительно не уводел первого и ошибся во втором. А также, кажется ошибся в том, что можно выбрать пустое множество, когда мы его уже выбрали первый раз (схема с возвращением), поскольку пересечение двух пустых есть также пустое.

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


27/06/08
4058
Волгоград
А xolodec,
А стоит ли рассматривать отдельно пустое, одноэлементные etc.
Для того, чтобы множества не пересекались необходимо и достаточно, чтобы ни один элемент не был выбран дважды.

 Профиль  
                  
 
 Re: Вероятность пересечения двух множеств
Сообщение12.10.2014, 07:14 


29/04/14
139
Этого действительно достаточно, только вот я не могу посчитать как этим способом сосчитать количество комбинаций не пересекающихся множеств.
Это же множество всех подмножеств, как вы прежподагаете, это можно посчитать?

Биномиальной схемой посчитано, с ответом сошлось, благодарю!

 Профиль  
                  
 
 Re: Вероятность пересечения двух множеств
Сообщение12.10.2014, 08:07 
Заслуженный участник


27/06/08
4058
Волгоград
xolodec в сообщении #917845 писал(а):
Этого действительно достаточно, только вот я не могу посчитать как этим способом сосчитать количество комбинаций не пересекающихся множеств.
Это же множество всех подмножеств, как вы прежподагаете, это можно посчитать?
А я не предлагаю считать количество непересекающихся множеств.
Я предлагаю считать вероятность того, что множества не пересекаются.
Веорятность того, что данный элемент не вошел в пересечение очевидно равна $1-\left(\frac12\right)^2=\frac34$. Всего элементов $N$. Поэтому искомая вероятность $\left(\frac34\right)^N$. Все.
Цитата:
Биномиальной схемой посчитано, с ответом сошлось, благодарю!
Надеюсь, ответ такой же?

 Профиль  
                  
 
 Re: Вероятность пересечения двух множеств
Сообщение12.10.2014, 17:04 


29/04/14
139
Да, ответ сошелся. Очень красивое решение, только мне непонятное пока.
Цитата:
Веорятность того, что данный элемент не вошел в пересечение

Если честно, не могу понять: данный элемент, это, видимо, элемент множества S.
Непопадание в какое пересечение вы считаете?

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


27/06/08
4058
Волгоград
xolodec в сообщении #918026 писал(а):
Да, ответ сошелся. Очень красивое решение, только мне непонятное пока.
Цитата:
Веорятность того, что данный элемент не вошел в пересечение

Если честно, не могу понять: данный элемент, это, видимо, элемент множества S.
Да.
Поочередно перебираем все элементы $S$.
Каждый элемент с вероятностью $\frac12$ попадает в $A$. Аналогично в $B$. Следовательно, с вероятностью $\frac14$ он попадает в пересечение.
Для того, чтобы пересечение было пусто, нужно чтобы ни один элемент из $S$ туда не попал.
Цитата:
Непопадание в какое пересечение вы считаете?
В то, о котором спрашивается в условии.

 Профиль  
                  
 
 Re: Вероятность пересечения двух множеств
Сообщение13.10.2014, 07:36 


29/04/14
139
$A$ и $B$, насколько я понимаю, есть аналоги множеств $A_1, A_2$, о которой говорилось в задаче.

Цитата:
Каждый элемент с вероятностью $\frac{1}{2}$ попадает в $A$

Всего вариантов выбора $2^N$, вариантов выбора, куда попадет конкретный элемент $2^{N-1}$.
Да, действительно $\frac{1}{2}$.
Благодарю за интересное решение!

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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