Комбинации событий

Материалы этого раздела основаны на книге В.Феллера "Введение в теорию вероятностей", том 1.

На практике нам часто приходится рассчитывать вероятности комбинации событий (см. примеры, приведенные ниже).

Итак, мы будем иметь дело с событиями, которые определяются посредством некоторых других событий A₁, A₂, ..., A_N.

Например, при игре в бридж событие A "по крайней мере один игрок имеет полную масть" является объединением четырех событий A_k "игрок с номером k имеет полную масть" (k=1, 2, 3, 4).

Из событий A_k одно, два или более могут осуществиться одновременно, и за счет этого частичного наложения вероятность события A не равна сумме четырех вероятностей P{A_k}. Мы покажем, как для заданного множества событий A₁, ..., A_N вычислить вероятности того, что 0, 1, 2, 3, ... из них осуществились.

 

1. Объединение событий
2. Приложение к классической задаче о размещении
3. Осуществление m из N событий
4. Приложение к задачам о совпадениях и к задаче об угадывании
5. Различные дополнения

 

1. Объединение событий

Если A₁ и A₂ - два события, то A₁ ∪ A₂ обозначает событие, состоящее в том, что осуществились либо A₁, либо A₂, либо они оба. Из элементарных формул известно, что

    (1.1)

Мы хотим обобщить эту формулу на случай N событий A₁, A₂, ..., A_N, т. е. вычислить вероятность того, что осуществится хотя бы одно из событий A_k. Символически это событие записывается в виде

.

Для нашей цели недостаточно знать вероятности отдельных событий A_k, нам должна быть дана полная информация о всевозможных пересечениях. Это означает, что для каждой пары (i, j), каждой тройки (i, j, k) и т. д. мы должны знать вероятности одновременного осуществления A_i и A_j, A_i, A_j и A_k и т. д. Для удобства будем обозначать эти вероятности буквой p с соответствующими индексами. Таким образом,

.     (1.2)

Порядок индексов несуществен, однако в целях однозначности мы всегда будем писать индексы в порядке возрастания; так, мы пишем p_3,7,11, а не p_7,3,11. Два индекса не совпадают. Для суммы всех p с r индексами будем использовать обозначение S, т. е. положим

.     (1.3)

Здесь i < j < ... ≤ N, так что в суммах каждая комбинация встречается один и только один раз; следовательно, S_r содержит слагаемых. Последняя сумма S_r сводится к единственному p_1,2,3,...,N, которое является вероятностью одновременного осуществления всех N событий.

При N=2 имеется только две суммы S₁ и S₂ и (1.1) можно записать в виде

.     (1.4)

Обобщение на произвольное число N событий дает следующая теорема.

Теорема. Вероятность P₁ осуществления хотя бы одного из событий A₁, A₂, ..., A_N равна

.     (1.5)

Замечание. Часто нам не нужны точные формулы, а достаточно иметь оценки сверху и снизу искомых вероятностей, таким образом, из формулы (1.5) получаются знаменитые неравенства Бонферрони.

Доказательство теоремы. Докажем (1.5) так называемым методом включения и исключения. Для того чтобы вычислить P₁, мы должны сложить вероятности всех элементарных событий, которые содержатся хотя бы в одном из A_i, но каждое элементарное событие должно быть взято только один раз. Действуя последовательно, мы сначала возьмем все элементарные события, которые содержатся только в одном A_i, затем те, которые содержатся ровно в двух из A_i и т. д., и наконец элементарные события (если они существуют), содержащиеся во всех A_i.

Пусть E - любое элементарное событие, содержащееся ровно в n из N событий A_i. Не ограничивая общности, мы можем занумеровать события так, что E содержится в A₁, A₂, ..., A_n, но не содержится в A_n+1, A_n+2, ..., A_N. Тогда P{E} является слагаемым в тех p_i, p_ij, p_ijk, ..., у которых индексы изменяются от 1 до n. Следовательно, P{E} входит n раз в S₁, раз - в S₂ и т. д. В итоге, выразив правую часть (1.5) через вероятности элементарных событий, мы убедимся, что P{E} входит в P₁ с коэффициентом

.     (1.6)

Остается показать, что это число равно 1. Это непосредственно следует из сравнения (1.6) с биномиальным разложением (1-1)ⁿ. Последнее начинается с 1, и слагаемые из (1.6) содержатся в нем с противоположными знаками, следовательно, для любого n ≥ 1 выражение (1.6) равно 1. Теорема доказана.

Теперь рассмотрим некоторые применения этой теоремы.

Примеры

а) Пусть при игре в бридж A_i есть событие "игрок с номером i имеет полную масть". Тогда ; событие, состоящее в том, что два игрока i и j имеют полную масть, осуществляется в 3· случаях и имеет вероятность ; аналогично находим .

Наконец, p_1,2,3,4 = p_1,2,3, так как если три игрока имеют полную масть, то ее имеет и четвертый. Вероятность того, что хотя бы один игрок имеет полную масть, равна поэтому P₁ = 4p₁ - 6p_1,2 + 4p_1,2,3 - p_1,2,3,4. Используя формулу Стирлинга, находим, что приблизительно P₁ = (1/4)10^-10. В этом частном случае P₁ очень близко к сумме вероятностей A_i, но это скорее исключение, чем правило.

б) Пары (совпадения). Следующая задача, известная в различных вариантах и приводящая к неожиданному ответу, была предложена Монтмором (1708). Она была обобщена Лапласом и многими другими авторами.

Две одинаковые случайным образом перетасованные колоды, содержащие по N различных карт каждая, сравниваются друг с другом. Если карта находится на одном и том же месте в обеих колодах, то мы говорим, что имеет место пара (совпадение). Совпадения могут быть на любом из N мест и на нескольких местах одновременно.

Этот эксперимент может быть описан и шуточной форме. Например, две колоды карт можно заменить множеством писем и предназначенных для них конвертов, и своенравный секретарь запечатывает письма в конверты случайным образом. Или можно представить себе, что шляпы в гардеробе перепутаны и распределяются между посетителями случайным образом. Совпадение имеет место, если посетитель получает свою собственную шляпу. Поучительно попытаться угадать, как вероятность совпадения зависит от N: как вероятность получения своей шляпы хотя бы одним из 8 гостей соотносится с соответствующей вероятностью в собрании из 10000 человек? Кажется удивительным, что эта вероятность практически не зависит от N и близка к 2/3.

Вероятности наличия ровно 0, 1, 2, 3, ... совпадений будут вычислены далее, а здесь мы найдем только вероятность P₁ хотя бы одного совпадения. Для удобства занумеруем карты числами 1, 2, ..., N в том порядке, в котором они расположены в одной из колод, и предположим, что каждая перестановка карт во второй колоде имеет вероятность 1/N!. Пусть событие A_k означает, что имеет место совпадение на k-м месте. Это означает, что карта с номером k находится на k-м месте, а оставшиеся N - 1 карт могут быть расположены в произвольном порядке. Очевидно, . Аналогично для любой комбинации i, j имеем и т. д. Сумма S_r содержит слагаемых, каждое из которых равно . Следовательно, , и в силу (1.5) искомая вероятность равна

.     (1.7)

Заметим, что 1 - P¹ представляет собой 1 + N первых членов разложения

,     (1.8)

и, следовательно, приблизительно

.     (1.9)

Точность приближения видна из следующей таблицы истинных значений P₁:

 

N	3	4	5	6	7
P1	0,66667	0,62500	0,63333	0,63196	0,63214

 

 

2. Приложение к классической задаче о размещении

Вернемся теперь к задаче о случайном размещении r шаров по n ящикам, предполагая, что каждое размещение имеет вероятность n^-r. Найдем вероятность p_m(r, n) того, что ровно m ящиков остаются пустыми.

Пусть событие A_k заключается в том, что ящик с номером k пуст (k = 1, 2, ..., n). При выполнении этого события все r шаров размещаются в остальных r - 1 ящиках, и это может быть сделано (n - 1)^r способами. Аналогично существует (n - 2)^r размещений, при которых два фиксированных ящика остаются пустыми и т. д. Следовательно,

,     (2.1)

и поэтому для любого ν ≤ n

.     (2.2)

Вероятность того, что хотя бы один ящик пуст, задается соотношением (1.5), и поэтому вероятность того, что все ящики заняты, равна

.     (2.3)

Рассмотрим теперь размещение, при котором ровно m ящиков остаются пустыми. Эти m ящиков могут быть выбраны способами. Тогда r шаров распределяются между остальными n - m ящиками так, что каждый из них занят; число таких распределений равно . Разделив на n^r, найдем вероятность того, что ровно m ящиков остаются пустыми:

.     (2.4)

Мы уже использовали модель случайного выбора r цифр для иллюстрации случайного размещения r предметов по n = 10 ящикам. Пустым ящикам соответствуют в этом случае отсутствующие цифры: если m ящиков пусты, то в данной последовательности встречаются 10 - m различных цифр. Численная иллюстрация приводится в таблице 1.

 

m	r = 10	r = 18
0	0,000363	0,134673
1	0,016330	0,385289
2	0,136080	0,342987
3	0,355622	0,119425
4	0,345144	0,016736
5	0,128596	0,000876
6	0,017189	0,000014
7	0,000672	0,000000
8	0,000005	0,000000
9	0,000000	0,000000

Таблица 1. Вероятности p_m(r, 10), полученные по формуле (2.4)

 

p_m(r, 10) - вероятность того, что ровно m из цифр 0, 1, ..., 9 не появятся в последовательности из r случайных цифр.

Ясно, что непосредственное вычисление по формуле (2.4) возможно в случае относительно малых n и r. С другой стороны, задача о размещении представляет собой интерес, когда n велико. Каковы шансы, что при размещении 10000 шаров по 1000 ящикам хотя бы один ящик останется пустым? Каковы шансы, что для группы из 2000 человек есть хотя бы один день в году, не являющийся чьим-либо днем рождения? К счастью, на подобные вопросы можно ответить с помощью замечательно простой приближенной формулы, погрешность которой стремится к нулю при n → ∞. Это приближение и приводящие к нему рассуждения типичны для многих предельных теорем теории вероятностей.

Таким образом, наша цель заключается в нахождении предельного вида (2.4) при n → ∞ и r → ∞. Соотношение между r и n в принципе может быть произвольным, но если среднее число r/n шаров чрезмерно велико, то мы не можем ожидать наличия пустых ящиков; в этом случае p₀(r, n) близка к единице и все p_m(r, n) при m ≥ 1 малы. С другой стороны, если r/n стремится к нулю, то практически все ящики должны быть пустыми, и в этом случае p_m(r, n) → 0 для любого фиксированного m. Поэтому действительный интерес представляет только промежуточный случай.

Мы начнем с оценки величины S_ν в (2.2). Так как

,

имеем

.     (2.5)

При 0 < t < 1 значение -log(1 - t)лежит между t и t/(1 - t). Поэтому

.     (2.6)

Положим для краткости

     (2.7)

и предположим, что r и n возрастают таким образом, что λ остается внутри конечного интервала 0 < a < λ < b. Для каждого фиксированного ν отношение крайних членов в (2.6) стремится к единице, и поэтому

.     (2.8)

Это соотношение очевидно справедливо, когда λ → 0, и, следовательно, (2.8) остается справедливым и тогда, когда r и n возрастают таким образом, что λ остается ограниченным. Но

     (2.9)

и из (2.8) следует, что правая часть стремится к нулю. Кроме того, множитель при p₀(r, n-m) в (2.4) равен S_m, и поэтому для каждого фиксированного m имеем

.     (2.10)

Тем самым доказана следующая теорема.

Теорема. Если n и r стремятся к бесконечности, так что остается ограниченным, то для каждого фиксированного m выполняется соотношение (2.10).

Аппроксимирующее выражение

     (2.11)

определяет так называемое распределение Пуассона.

На практике можно использовать p(m; λ) в качестве приближения, когда n велико. Для небольших значений n необходима оценка погрешности, однако мы заниматься этим не будем.

Примеры

а) В таблице 2 приведены приближенные значения вероятностей того, что m ящиков окажутся пустыми при общем числе ящиков, равном 1000, и числе шаров, меняющемся от 5000 до 9000. При r = 5000 медиана числа пустых ящиков равна 6: наличие семи или более пустых ящиков имеет приблизительно такую же вероятность, как шести или менее. Даже в случае 9000 шаров в 1000 ящиках мы имеем около одного шанса из девяти найти пустой ящик.

 

r	λ	p(m; λ)
		m = 0	m = 1	m = 2	m = 3	m = 4	m = 5	m = 6	m = 7	m = 8	m = 9	m = 10	m = 11
5000	6,74	0,0012	0,0080	0,0269	0,0604	0,1017	0,1371	0,1540	0,1482	0,1249	0,0935	0,0630	0,0386
5500	4,09	0,0167	0,0685	0,100	0,1909	0,1951	0,1596	0,1088	0,0636	0,0325	0,0148	0,0060	0,0023
6000	2,48	0,0838	0,2077	0,2575	0,2128	0,1320	0,0655	0,0271	0,0096	0,0030	0,0008	0,0002
6500	1,50	0,2231	0,3347	0,2510	0,1255	0,0471	0,0141	0,0035	0,0008	0,0001
7000	0,91	0,4027	0,3661	0,1666	0,0506	0,0115	0,0021	0,0003
7500	0,55	0,5777	0,3163	0,0873	0,0162	0,0023	0,0003
8000	0,34	0,7126	0,2406	0,0414	0,0049	0,0004
8500	0,20	0,8187	0,1637	0,0164	0,0011	0,0001
9000	0,12	0,8869	0,1064	0,0064	0,0003

Таблица 2. Пуассоновское приближение (2.11) для вероятностей наличия ровно m пустых ящиков при случайном распределении r шаров по n = 1000 ящикам

 

б) В статистике дней рождения n = 365, а r равно числу людей. При r = 1900 приблизительно λ = 2. Вероятности P_[m] того, что в поселке с 1900 жителями m дней в году не являются днями рождения, приблизительно таковы:

 

P[0] = 0,135,	P[1] = 0,271,	P[2] = 0,271,	P[3] = 0,180,
P[4] = 0,090,	P[5] = 0,036,	P[6] = 0,012,	P[7] = 0,003.

в) Когда nlogn + an шаров размещаются в n ящиках и n велико, вероятность того, что все ящики заняты, равна 1 - e^-a.

Вместо пустых ящиков можно рассмотреть ящики, содержащие ровно k шаров. Здесь с небольшими изменениями применимы рассуждения, использованные выше в частном случае k = 0. Как показал Мизес, вероятность того, что ровно m ящиков содержат по k шаров, также аппроксимируется распределением Пуассона (2.11), но в этом случае λ определяется следующим образом:

.     (2.12)

 

3. Осуществление m из N событий

Теорема § 1 может быть усилена следующим образом.

Теорема. Для любого целого m, такого, что 1 ≤ m ≤ N, вероятность P_[m] того, что одновременно осуществляется ровно m из N событий A₁, ..., A_N, равна

.     (3.1)

Замечание. Согласно (1.5), вероятность P_[0] того, что не осуществилось ни одно из событий A_j, равна

.     (3.2)

Это показывает, что (3.1) дает правильное значение также и для m = 0, если мы положим S₀ = 1.

Доказательство. Будем рассуждать так же, как при доказательстве (1.5). Пусть E - произвольное элементарное событие; предположим, что оно содержится ровно в n из N событий A_j. Тогда P{E} дает вклад в P_m лишь тогда, когда n = m. Для того, чтобы узнать, каким образом P{E} входит в правую часть (3.1), заметим, что P{E} входит в суммы S₁, S₂, ..., S_n, но не входит в суммы S_n+1, ..., S_N. Отсюда следует, что P{E} не дает вклада в правую часть (3.1), если n < m. Если n = m, то P{E} входит в одно и только в одно слагаемое суммы S_m. Для завершения доказательства теоремы остается показать, что при n > m вклады P{E} в члены правой части S_m, S_m+1, ..., S_n взаимно уничтожаются. Действительно, P{E} входит в S_k с коэффициентом , равным числу наборов по k событий из n событий, содержащих E. Таким образом, при n > m полный вклад P{E} в правую часть (3.1) равен

.     (3.3)

Если выразить биномиальные коэффициенты через факториалы, то легко видеть, что это выражение сводится к следующему:

.     (3.4)

В скобках имеем биномиальное разложение для (1-1)^n-m, так что (3.3) обращается в нуль, что и утверждалось.

Читателю предлагается проверить, что подстановка выражения (2.2) в (3.1) непосредственно приводит к (2.4).

 

4. Приложение к задачам о совпадениях и к задаче об угадывании

В примере 1, б) мы рассматривали совпадения карт в двух колодах и нашли, что S_k = 1/k!. Подставив это выражение в (3.1), получим следующий результат.

При случайном сопоставлении двух одинаковых колод, состоящих из N различных карт, вероятности P_[m] получить ровно m совпадений равны

     (4.1)

Последнее соотношение очевидно. Обращение в нуль P_[N-1] выражает тот факт, что невозможно получить N - 1 совпадение без того, чтобы все N карт в каждой колоде были расположены в одинаковом порядке.

Выражения в фигурных скобках в правых частях (4.1) являются первыми членами разложения e^-1. Поэтому для больших N мы имеем приближенное равенство

.     (4.2)

Ниже, в таблице 3, колонки, озаглавленные P_[m], дают точные значения P_[m] при N = 3, 4, 5, 6, 10. В последней колонке приведены предельные значения

.     (4.3)

Числа p_m дают довольно хорошее приближение для P_[m] даже при небольших значениях N.

Для чисел p_m, определенных формулой (4.3), мы имеем

.

Следовательно, p_k могут трактоваться как вероятности. Отметим, что (4.3) является частным случаем распределения Пуассона (2.11) с λ = 1.

Пример. Проверка способности угадывать. При дегустации вин, угадывании карт, проверке медиумных способностей проверяемого просят назвать неизвестный ему порядок расположения N предметов, скажем карт. Действительная способность угадывать будет проявляться как отклонение от чистой случайности. Для оценки степени этой способности мы должны уметь находить вероятности случайных удач. Угадывающий может придерживаться разных систем, среди которых мы упомянем три крайние возможности. (i) Угадывающий выбирает одну карту и называет все время ее. При такой системе он будет иметь одно и только одно правильное угадывание в каждой серии; случайные флуктуации исключены. (ii) Угадывающий называет каждую карту один раз, так что так что каждая серия из N угадываний соответствует перетасовке колоды. Если проверяемый не обладает способностью угадывать, то можно применить формулы (4.1). (iii) Третья возможность заключается в том, что каждое из N угадываний производится совершенно независимо от других. Здесь имеется N_N возможных комбинаций. Несомненно, что каждый человек имеет свои привычки и склонен называть определенные комбинации чаще других, однако в первом приближении можно считать все N_N комбинаций равновероятными. Так как m верных и N - m неверных угадываний могут быть произведены различными способами, вероятность ровно m угадываний равна

.     (4.4)

 

m	N = 3		N = 4		N = 5		N = 6		N = 10		pm
	P[m]	bm	P[m]	bm	P[m]	bm	P[m]	bm	P[m]	bm
0	0,333	0,296	0,375	0,316	0,367	0,328	0,368	0,335	0,36788	0,34868	0,367879
1	0,500	0,444	0,333	0,422	0,375	0,410	0,357	0,402	0,36788	0,38742	0,367879
2	...	0,222	0,250	0,211	0,167	0,205	0,187	0,201	0,18394	0,19371	0,183940
3	0,167	0,037	...	0,047	0,083	0,051	0,056	0,053	0,06131	0,05740	0,061313
4			0,042	0,004	...	0,006	0,021	0,008	0,01534	0,01116	0,015328
5					0,008	0,000	...	0,001	0,00306	0,00149	0,003066
6							0,001	0,000	0,00052	0,00014	0,000511
7									0,00007	0,00001	0,000073
8									0,00001	.....	0,000009
9									.....	.....	0,000001
10									.....	.....	0,000000

Таблица 3. Вероятности m правильных угадываний в колоде из N различных карт

 

P_[m] заданы формулой (4.1), b_m - формулой (4.4). В последнем столбце приведены предельные вероятности (4.3) (распределение Пуассона).

В таблице 3 приведены вероятности успеха, когда угадывание производится по системе (ii) или (iii). Чтобы оценить достоинства этих двух методов, необходимо найти средние значения и величины случайных флуктуаций. Оказывается, что среднее число правильных угадываний одинаково во всех системах; случайные отклонения несколько больше при системе (2), чем при (3). Просмотр таблицы 3 показывает, что практически разница не очень велика.

 

5. Различные дополнения

a. Осуществление по меньшей мере m событий

В обозначениях § 3 вероятность P_m того, что одновременно осуществляются m или более из событий A₁, ..., A_N, равна

.     (5.1)

Для того чтобы выразить P_m через S_k, проще всего действовать методом индукции, начиная с выражения (1.5) для P₁ и используя рекуррентное соотношение P_m+1 = P_m - P_[m]. При m ≥ 1 получаем

.     (5.2)

Соотношение (5.2) можно вывести также и непосредственно, используя рассуждения, которые привели к (3.1).

б. Прочие тождества

Коэффициенты S_ν можно выразить через P_[k] или P_k следующим образом:

     (5.3)

и

.     (5.4)

Идея доказательства. При заданных значениях P_[m] соотношения (3.1) можно рассматривать как линейные уравнения относительно неизвестных S_ν, и мы должны доказать, что (5.3) представляет собой их единственное решение. Если подставить (5.3) в выражение (3.1) для P_[m], то коэффициент при P_[k] (m ≤ k ≤ N) в правой части будет равен

.     (5.5)

При k = m это выражение равно 1. при k > m сумма представляет собой биномиальное разложение (1-1)^k-m и поэтому равна нулю. Следовательно, подстановка (5.3) сводит (3.1) к тождеству P_[m] = P_[m]. Единственность решения (3.1) следует из того, что каждое последующее уравнение содержит только одно новое неизвестное по сравнению с предыдущим, так что S_ν могут быть вычислены последовательно. Справедливость (5.4) может быть доказана аналогичным образом.

в. Неравенства Бонферрони

Ряд неравенств как для P_[m], так и для P_m может быть получен следующим образом. Если либо в формуле (3.1), либо в (5.2) оставлены лишь слагаемые, содержащие S_m, S_m+1, ..., S_m+r-1, а слагаемые, содержащие S_m+r, S_m+r+1, ..., S_N, отброшены, то погрешность (т. е. истинное значение минус приближенное значение) имеет знак первого отброшенного члена [а именно, (-1)^r] и не превосходит его по абсолютной величине. Таким образом, при r = 1 и r = 2

     (5.6)

и

.     (5.7)

Идея доказательства. Тождество (3.1) показывает, что утверждение (5.6) эквивалентно неравенству

     (5.8)

для любого t. Для того, чтобы представить левую часть в виде линейной комбинации P_[k], воспользуемся соотношением (5.3). При t ≤ k ≤ N коэффициент при P_[k] равен

.

Последняя сумма равна и, следовательно, положительна.

Дальнейшие неравенства можно найти в монографии Фреше, цитированной в начале главы.

 

В начало

Содержание портала