Задача 365 человек день рождения

Logon

возник тут за пивом нелепый спор, по следующей ситуации: случайным образом отбирается 365 человек (по количеству дней в году сколько дней окажется без именинника? есть у меня подозрение, что повторяя такую выборку раз за разом, количество этих дней будет примерно одинаковое.
Рассчитывать, что выбрав 365 человек, получишь все 365 дней занятые день рождениями, как-бы не приходится.

Vlad128

есть у меня подозрение, что повторяя такую выборку раз за разом, количество этих дней будет примерно одинаковое.
тут говорится о дисперсии этого распределения или как? Иначе я не понял, что имеется в виду.

lenmas

Я правильно понимаю, что обсуждается вопрос, что вероятность этого 365!/365^365?
P.S. Ну так это по порядку есть 1/e^365.
P.P.S. Это при условии, что дни рождения распределены равномерно по году.
P.P.P.S. Наконец-то прочитал условие полностью: требуется среднее значение незанятых дней :grin:

Arthur8

понял задачу так: на улице берётся случайно 365 человек. Сколько человек в день отбора отмечают свой день рождения?
,
моё решение: средняя жизнь 70 лет, 365/70 = 5, т.е., имхо, у 5 человек из 365 будет день варенья в день их сбора, следовательно 360 без дня рождения в день сбора, раз спрашивается сколько в задаче.

Logon

средняя жизнь 70 лет
гммм, не понял, каким образом приплелась средняя продолжительность жизни?
Невнятно условия написал. Берется случайная выборка из 365 человек, смотрятся их дни рождения - и вычеркиваются дни на календаре, когда у кого-то из этой выборки есть днюхи.
сколько дней будет закрыто таким образом?
Делая раз-за разом эти выборки, соотношение дней (с днюхой/без днюхи) будет примерно одинаковым?

Andrey56

случайным образом отбирается 365 человек (по количеству дней в году сколько дней окажется без именинника? есть у меня подозрение, что повторяя такую выборку раз за разом, количество этих дней будет примерно одинаковое.
Ты определись, выборка одна или набирается статистика?

Logon

первоначально одна...
а потом набирается статистика :)

Arthur8

ну если 365 умножить на 70, то это число будет числом дней в 70 годах или числом разных людей, которые гарантированно имеют день варенья в это день. Это если без вероятностей, а если с вероятностью, то надо драть все население планеты, 6 млрд. или сколько их там, уже 7?

Logon

ну если 365 умножить на 70, то это число будет числом дней в 70 годах или числом людей, которые гарантированно имеют день варенья в это день.
шо за бред? :shocked:

Niklz

если предположить, что дни рождения в популяции распределены по дням года равномерно :)
то вероятность того, что какой-то конкретный день окажется незанят днем рождения - Bin(0; 365, 1/365 где Bin(k; n, p) - функция биномиального распределения.
Соответственно, среднее число дней в году незанятых днями рождения в твоем примере 365*Bin(0; 365, 1/365).

Martika1

вероятность того, что незанятых дней будет 0:
p(0) = 365! / 365^365
Вероятность того, что незанятых дней будет 1:
p(1) = 365! / 1! / 365^365 * (365 - 1)
Вероятность того, что незанятых дней будет n:
p(n) = 365! / n! / 365^365 * (365 - n)^n
Проверка на всякий случай:
вероятность того, что у нас 364 незанятых дня, то есть что все люди родились в один день:
p(364) = 365!/364! / 365^365 * 1^364 = 365^(-364 что, вроде бы, разумно
Другая проверка, экстремальная:
вероятность, что у нас 365 незанятых дней:
p(365) = 365!/365! / 365^365 * 0^365 = 0 — тоже разумно
Теперь осталось найти сумму
Σ(n*p(n по n от 0 до 364.
Вольфрам-альфа говорит, что это примерно 9.8e-66
что явно свидетельствует о том, что я чего-то не учел

Arthur8

забудь, это меня занесло не в ту степь =)

Vlad128

что-то разумность ответа ты и не проверил :)

Martika1

да, как-то с ответом плохо получилось

Logon

спасибо, это как раз примерно то самое, что я и хотел услышать.
Единственно, слегка недопетрю, что дает нам поиск суммы?
Теперь осталось найти сумму
Мы складываем вероятности того, что "незанятых дней будет n", где n - числа от о до 365 и что получаем?

Martika1

не, фигня у меня. В сумме эти вероятности должны дать единицу. А дают 10^-68, что бредово.
А, понятно, в чем ошибка. В моей формуле p(n) получается, будто мне важно, что именно n последних людей имеют дни рождения где-то в те же дни, что и кто-то из 365-n первых.

Vlad128

У меня получается в среднем 230.90 занятых.

Logon

У меня получается в среднем 230.90 занятых.
хммм.... как-то маловато

bdfne36

Мне кажется, в данном случае распределение Пуассона хорошо моделирует процесс.
p(n)=(lam^n/n!)e^(-lam)
В среднем один день рождения раз в день. lam=1
вероятность наблюдать ноль дней рождений p(n=0)=e^-1=0.367, т.е. в году таких дней будет 0.367*365=134.3 (прилично)
аналогично
p(n=1)=0.367 (в году 134.3)
p(n=2)=0.183 (в году 67.1)
p(n=3)=0.061 (в году 22.4)

Vlad128

куда уж больше-то?
ты в курсе про birthday attack? В частности, у ~25 человек с вероятностью ~75% (точных чисел не помню, в школе решали) ДР в один день?

lenmas

У тебя с ункулункулу хорошее соответствие.

Vlad128

В общем, вот программка. Если есть ошибки — пишите, я ухожу :)

namespace Birthdays
{
class Program
{
static void Main(string[] args)
{
const int days = 365;
double[,] prob = new double[days + 2,2]; // for zeroth and 365th
prob[1,0] = 1;
int index = 0;
for (int d = 2; d <= days; ++d)
{
for (int k = 1; k <= days; ++k)
{
prob[k, 1-index] = prob[k, index] * k / days + prob[k - 1, index] * (days - (k - 1 / days;
}
index = 1 - index;
}

double exp = 0;
for (int d = 1; d <= days; ++d)
{
exp += d * prob[d, index];
}
Console.WriteLine(exp);
}
}
}

Logon

у тебя значения для n=0 и n=1 одинаковые получились

Vlad128

бонус моего решения в том, что можно построить распределение в конечный момент времени и исследовать и другие вопросы (ту же дисперсию). Если кто-нибудь закинет график, будет очень круто, тукку поможет, мне просто надо бежать!

bdfne36

у тебя значения для n=0 и n=1 одинаковые получились

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

lenmas

у тебя значения для n=0 и n=1 одинаковые получились
Это потому что у него lam=1. Формула вероятностей e^lam*lam^k/k!, соответственно при k=0 и при k=1 получаются
одинаковые значения.
В общем, у angar'ы решение твоей задачи в духе теории случайных процессов. Для 365 респондентов
такое приближение вполне должно быть приемлемым.

lenmas

Но все равно ждем точного аналитического решения от кайафы.

Logon

Формула вероятностей e^lam*lam^k/k!, соответственно при k=0 и при k=1 получаются
одинаковые значения.
хммм, забавно - но вот физически, на ощупь, это не кажется верным

Niklz

omg, с какой скоростью люди прогаммы пишут
тут и простая формула бы сгодилась: среднее число незанятых 365 * (1 - 1/365)^365 = 134 дня, среднее число занятых 365 *(1 - (1 - 1/365)^365) = 231 дней, ответ с твоим совпадает. дисперсия числа незанятых sqrt(365 * (1-1/365)^365 * (1 - (1-1/365)^365 = 9 дней

с дисперсией тут неправильно - неучтена коррелированность событий "день i занят" по году.

Vlad128

ну я же говорю, я хотел распределение построить. Т.е. погонять марковскую цепь. Средние, конечно, легче считаются.

Logon

среднее число незанятых 365 * (1 - 1/365)^365 = 134 дня
спасибо :)
ЗЫ. Если вопрос уложнить - какой должен быть коллектив, чтобы гарантировано раз в год была днюха?

Niklz

>> ЗЫ. Если вопрос уложнить - какой должен быть коллектив, чтобы гарантировано раз в год была днюха?
1 человек!

semute

ЗЫ. Если вопрос уложнить - какой должен быть коллектив, чтобы гарантировано раз в год была днюха?
непустой :)

Vlad128

гарантировано
никакого не хватит :)

Logon

ну да, ошибся :grin:
речь про раз в день

Vlad128

дисперсия
это ты std посчитал? У меня дисперсия 35.5

Arthur8

чтобы гарантировано раз в год была днюха?
1 человек? У меня есть знакомый юрист, у него фирма, в которой он один и работает.

Arthur8

а штоб снизить затраты на зарплаты, бери к себе на работу только тех людей, у которых день рождения 29 или 30 февраля, первое отмечается раз в 4-ре года, а второе было всего три раза
p.s. я так задумался, вот ведь кому-то не повезло, раз в 4-ре года отмечаться

Niklz

у тебя наверное дисперсия числа занятых :)

griz_a

Число занятых дней X есть сумма индикаторов событий [math]$A_i $[/math], где [math]$ A_i$[/math] - событие, что i-ый день занят.
[math] $ E I_{A_i} = P(A_i) = 1-(364/365)^{365},  $[/math]
[math] $ E I_{A_i} I_{A_j} = P(A_i A_j) = 1-P(\overline{A_i})-P(\overline{A_j})+P(\overline{A_i A_j})=1-2(364/365)^{365}+(363/365)^{365} $[/math]
[math]$EX = 365-365(364/365)^{365} \approx 230,7 $ [/math]
[math]$ DX = \sum\limits_{i,j} \left(EI_{A_i} I_{A_j} - P(A_i) P(A_j)\right) = 365 (364/365)^{365}(1-(364/365)^{365}) + (365^2-365) (1-2(364/365)^{365}+(363/365)^{365}-(1-(364/365)^{365})^2) \approx  84,9  -49,3  = 35,6 $[/math]
Дисперсия действительно небольшая.

griz_a

Ты просто считаешь что занятость дней независима, а это бред, разумеется.
Если ковариации не считать, то да, 81 и получится.

Niklz

бред собачий и не говори!

griz_a

Если уж так хочется распределение, то задача нехитрая.
[math]$$P(X=k) = C^k_{365} k/365)^N-C^{k-1}_k k-1)/365)^N+C^{k-2}_k k-2)/365)^N-... $$[/math]
Толку только с него не густо.

denis24

А я вот человек простой, таких страшных формул не знаю (и на сях прогать не умею зато могу в VBA бабахнуть прогу, которая по циклу добавляет галочки в одну из 365 клеток.
Сделав это 200 раз я получил табличку (первое значение - количество галочек в ячейке, второе значение - среднее количество ячеек с этим числом галочек, третье значение - среднеквадратичное отклонение среднего кол-ва ячеек)
0 134,13 5,83
1 135,22 9,13
2 68,2 5,91
3 21,86 4,11
4 5,37 2,3
5 1,04 0,94
6 0,125 0,35
Это видимо означает, что в VBA хороший генератор случайных чисел.

Vlad128

Чтобы эту сумму C_n^k считать "в лоб" потребуется еще больше вычислений, чем в моем алгоритме :)

griz_a

Хе, если можно с погрешностью, то слагаемые довольно быстро убывают и откинуть их не проблема. цэшки же считаются формулой стирлинга на ура при больших k.

Vlad128

ну это бесспорно :)
Ну да, у обоих методов есть достоинства и недостатки. У вас видна суть решения, у меня просто другой подход, который, кстати, полезен в более сложных задачках.

denis24

Помогите, плиз. Я вот как рассуждаю: матожидание считается как сумма вероятности, умноженной на значение, т.е.:
M=p(1)*364 + p(2)*363 + ... + p(364)*1 + p(365)*0
где р(х) - вероятность того, что у 365 человек х разных дней рождения.
С р(1) всё понятно, это (1/365)^365. А как посчитать р(2) или р(3)? Я вроде весь тред осилил, но понять аналитические формулы Фрау не могу.

griz_a

Однажды Попов читал лекцию о телеграфе и радиотелеграфе. В конце лекции к нему подошла девушка и сказала: "Вы все очень понятно рассказали про телеграф, но у меня остался один вопрос. Если кабели проложены по дну Атлантического океана, то как новости доходят до нас сухими?"

denis24

Ну да, смешно. Вопрос их серии я про ваши космические корабли всё понял, мне только непонятно, как карамельки делают: дырки нет, а повидло внутри есть.
Ну блин, я не могу посчитать вероятность. Мне очень стыдно, объясните, пожалуйста.

griz_a

Я как бы намекнул, что тред неплохо бы почитать. :confused:
В частности, чуть выше я эту вероятность выписал.
Правда, я плохо понимаю, откуда взялся ответ [math]$365^{-365}$[/math], поэтому может быть я плохо понимаю вопрос.
А еще я совсем плохо понимаю, зачем для подсчета матожидания (которое считается легко, см. тред выше) считать вероятности, которые считать сложно.

demiurg

А я вот человек простой, таких страшных формул не знаю (и на сях прогать не умею зато могу в VBA бабахнуть прогу, которая по циклу добавляет галочки в одну из 365 клеток.
метод Монте-Карло часто более практичен (особенно, когда проще заставить комп сделать может и лишнюю работу, зато самому не думать и быть уверенным что не ошибся и даже времени может в итоге меньше уйти :)

denis24

Вроде, понял. Скажи, правильно ли я понимаю, что первое слагаемое в скобках - вероятность того, что все 365 человек попадут в ровно k дней? Но эта вероятность учитывает и события, когда какие-то из этих k дней остались незаполненными. И тогда мы должны вычитать вероятность того, что из этих k ровно 1 день остался незаполненным, ровно 2 дня остались незаполненными и т.д. до (k-1) незаполненного дня (т.е. как раз случай, когда все дни рождения попали в один день). Ну и понятно, в каждом случае нам нужно домножать на количество способов выбрать несколько дней из множества.
Но я не могу понять, почему ты умножаешь на C(k,k-1 не только вероятность того, что ровно один из k дней останется свободным от дней рождения, но и все остальные слагаемые. Т.е. получается, что вероятность того, что останется ровно 2 свободных дня из k ты умножаешь и на C(k, k-1) и на C(k, k-2). Можешь объяснить?

griz_a

 
Но я не могу понять, почему ты умножаешь на C(k,k-1 не только вероятность того, что ровно один из k дней останется свободным от дней рождения, но и все остальные слагаемые. Т.е. получается, что вероятность того, что останется ровно 2 свободных дня из k ты умножаешь и на C(k, k-1) и на C(k, k-2).

Не умножаю, это оптический обман.
Там дробь в скобках и числитель ее в скобках. Обе скобки моментально закрываются :)
Оставить комментарий
Имя или ник:
Комментарий: