6 нояб. 2009 г.

Вероятности и подарки

Скоро Новый год и ещё неделя праздников, скоро масса подарков и встреч хороших людей. В это время в голову приходят идеи всяких праздничных игр. В некоторых группах принято делать так: все кладут по одному подарку под ёлку, нумеруя их, а потом для каждого участника выбирают номер подарка, который он сейчас получит (обычно пользуются компьютерным генератором псевдослучайных чисел). Это добавляет ситуации загадочности и праздничности :)

Какие рассуждения при этом используются?

Если у нас N участников и N подарков, то вероятность того, что лично мне достанется тот же подарок, что я положил под ёлку, равна 1/N (и это же можно сказать про остальных людей). Чем больше N, тем меньше вероятность вытянуть своё же (и при N стремящемся к бесконечности эта вероятность вообще стремится к нулю). Поэтому в больших группах очень мало шансов, что кто-то уйдёт со своим же подарком.

Недавно мы уже говорили о том, что словами «бесконечность» и «предел» нужно пользоваться очень осторожно, чтобы не обмануть самого себя. А про любые «очевидные» логические переходы надо уметь в течение 30 секунд детально и корректно объяснить, почему они очевидны. Но сегодня я предлагаю начать с обратной стороны: поставить эксперимент.

Проще всего для этого воспользоваться языком программирования javascript, потому что он есть под рукой почти у всех читателей (да и традицию не будем нарушать). Создайте файл presents.html со следующим содержимым и откройте его браузером:

<script type="text/javascript">
N = 100; // quantity of presents (and participants)
nbIt = 1000; // quantity of iterations
okIt = 0; // OK situaions
for (iter = 0; iter < nbIt; iter++) {
var a = new Array(N); // create array
for(i=0; i<N; i++)
a[i] = i; // fill it by numbers 0, 1, 2,... , N-1

// shuffle array
i = N;
while(i) {
j = Math.floor( (i--) * Math.random() );
t = a[i];
a[i] = a[j];
a[j] = t;
}

// calculate number of self-presents
selfp = 0;
for(i=0; i<N; i++)
if (a[i] == i)
selfp++;

if (selfp == 0) // if there are no self-presents
okIt++; // increase OK-counter
}

document.write('Probability of OK-situation: ' + (100*okIt/nbIt) + '%');
</script>

Данная программа реализует следующий эксперимент: сто участников складывают принесённые с собой подарки под ёлку, а потом получают на руки случайный подарок. Если никому не досталось то, что он принёс своими руками, то считаем ситуацию хорошей. Один раз так делать смысла нет, поэтому ребята повторяют это тысячу раз, считая хорошие ситуации. Последней строкой программа выводит долю случаев, в которых никто не получил свой подарок.

Оказывается, что только примерно в трети случаев каждый участник эксперимента получает что-то новое, а в остальных ситуациях кто-то оказывается не очень довольным. Попробуйте увеличить или уменьшить количество участников (конечно, не делая его слишком малым - больше 5 уже достаточно). Результат всё равно будет больше похож на температуру (потом мы поймём, что он колышется вокруг 36.8%).

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

Зачем это надо? Для калибровки своей интуиции! Редкий человек обладает достаточной дисциплиной ума, чтобы проверять каждый шаг всех выкладок. Иногда приходится полагаться на ощущение «это верное утверждение, потому что оно не может быть ошибочным»... Но чтобы чего-нибудь достичь, позволяя себе такие вольности, необходима тренированная интуиция, а не умение переспорить. Эти глубокие интуитивные шаги необходимы, чтобы не погрязать в рутине маленьких простых этапиков в размышлениях, а сразу выделять важные и серьёзные идеи (которые потом, конечно, надо будет детально обосновать, если они покажутся интересными).

Полагаю, скоро в комментариях появится объяснение, почему даже для небольших групп людей вероятность получения сюрприза каждым не очень высока. А самое интересное, почему эта вероятность не устремляется к 100% при росте количества участников :)

30 комментариев:

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

    ОтветитьУдалить
  2. Решение

    Долго пытался доказать утверждение про 1/N.
    Доказательство простое, но когда к нему подходишь не с той стороны, да еще и складываешь зависимые вероятности...

    ОтветитьУдалить
  3. abyrvalg, давайте рассмотрим, какая вероятность вытянуть свой подарок будет у человека, который подходит к ёлочке вторым:

    1. С вероятностью 1/N его подарок забрал первый счастливчик, так?

    2. Значит, с вероятностью (N-1)/N его подарок находится под ёлкой, верно?

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

    Выходит, вероятность вытянуть свой подарок для второго участника равна ( (N-1)/N ) * ( 1/(N-1) ) = 1/N.

    Аналогичные рассуждения возможны для третьего и четвёртого участников, но для большей аккуратности лучше вывести общее доказательство для k-того. Его я здесь не привожу, чтобы не загромождать комментарии.

    ОтветитьУдалить
  4. Согласен, для каждого отдельного человека вероятность 1/N. Но это совсем не означает, что вероятность ВСЕХ получить правильные (не свои) подарки такова же. Это всё же разные события - "взять правильный подарок одному человеку" и "взять правильные подарки всем".

    ОтветитьУдалить
  5. Можно попытаться решить задачу через комбинаторику: в знаменателе - число перестановок (N!) в числителе - количество перестановок, в которых ни одной цифры не осталось на своем месте... Но для двузначных чисел значения уже слишком большие получаются, да формулу для числителя не могу вывести.
    Если составить программу - для 7 получается 1854 / 5040 = 36.7857%, для 8 - 14833 / 40320 = 36.7882%, для 9 - 133496 / 362880 = 36.7879%
    Эмпирически, в числителе a[i]=(a[i-2]+a[i-1]) * (i-1), но это, конечно же, нечестное решение

    ОтветитьУдалить
  6. abyrvalg, было бы здорово если бы вы сказали, что случайные величины (принадлежности подарков доставшихся разным людям), зависимы друг от друга. Так и Илье понятнее, и меня это смущает :)
    Величины независимы, потому что вытаскивание очередного подарка из под елки делается независимо от принадлежности подарка. Таким образом, состав оставшихся подарков тоже не зависит от их принадлежности.
    Вы же, разумеется, понимаете, что для независимых случайных величин, вероятность выпадения комбинации равна произведению вероятностей выпадения отдельных величин?

    ОтветитьУдалить
  7. Анонимный06.11.2009, 13:44

    Задачу решать пока не пытался, но возникло забавное предположение про ответ в пределе: это часом не 1/e?

    ОтветитьУдалить
  8. Можно посчитать вероятность сложного события "все люди вытащили чужой подарок", так как вероятность каждого участника вытащить чужой подарок равна 1 - 1/N, то вероятность этого сложного события будет равна (1-1/N)^N

    ОтветитьУдалить
  9. dyker, я тоже так думал :)
    N=2, Ваш ответ?

    ОтветитьУдалить
  10. Basilevs, (1-1/N)^N вообще неправильный ответ :)

    ОтветитьУдалить
  11. Хм. А мне казалось, что про парадокс дней рождений я уже видел заметку в архиве.

    ОтветитьУдалить
  12. Подарки у вас перемешиваются нетрадиционным способом. Или это часть условия задачи - именно так гости и перемешивают и потом вытаскивают?

    ОтветитьУдалить
  13. Denis, здорово Вы получили приближения!

    Basilevs, благодарю за разбор этого момента!

    Уважаемый аноним, похоже, у Вас хорошая интуиция - предел Вы угадали :)

    dyker, как далее Вам написали, похоже, что лишний раз возвели в степень, так?

    Xavier, да, было дело. Но я бы не сказал, что одна задачка полностью заменяет другую. Впрочем, они похоже по ощущениям :)

    eak, я согласен, моё перемешивание не идеально. Если сможете предложить короткий код, который делает его лучше, то это будет здорово! Впрочем, данное перемешивание ничего не портит, поэтому я считаю его допустимым в данном случае.

    ОтветитьУдалить
  14. Анонимный06.11.2009, 21:04

    Если у нас N участников и N подарков, то вероятность того, что лично мне достанется тот же подарок, что я положил под ёлку, равна 1/N (и это же можно сказать про остальных людей). Чем больше N, тем меньше вероятность вытянуть своё же (и при N стремящемся к бесконечности эта вероятность вообще стремится к нулю). Поэтому в больших группах очень мало шансов, что кто-то уйдёт со своим же подарком.
    Чтобы увидеть ошибочность последнего предложения, необязательно что-то считать.

    В большой группе у конкретного человека мало шансов уйти со своим подарком, но вот что кто-то из этой большой группы получит обратно свой подарок, очень даже вероятно. Маловероятные события имеют свойство иногда случаться, а народа в большой группе много.

    Вероятность, что после броска кубика выпадет, например, 4, равна 1/6 ― это возможно, но не очень вероятно. Но если мы бросим кубик 6 раз подряд, выпадение хоть раз четвёрки вполне ожидаемо.

    ОтветитьУдалить
  15. Анонимный06.11.2009, 22:15

    Я так полагаю, вероятность, что в группе из N человек все уйдут с чужими подарками = ((N-1)/N)^N, где (N-1)/N ― вероятность, что один человек уйдёт с чужим подарком.

    ОтветитьУдалить
  16. Анонимный06.11.2009, 23:59

    Не правильно полагаю, участники группы влияют друг на друга. Пока безрезультатно исписал кучу бумаги.

    ОтветитьУдалить
  17. Точное решение p(N) выражается рекуррентной формулой через p(k<N), но вывести явную формулу не получается :(
    Кстати, (1-1/N)^N и (1-1/N)^(N-1) ограничивают сверху и снизу и сходятся туда же, но точное решение сходится к 1/e гораздо быстрее.

    ОтветитьУдалить
  18. Я думаю, достаточно времени прошло, поэтому я могу уже написать уравнение, график которого выше предложил 7vies:

    P(N) = 1/2! - 1/3! + 1/4! - 1/5! + ... + ((-1)^N)/N!

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

    ОтветитьУдалить
  19. Basilevs, я считал вероятность p(N), что никто не получит свой подарок, через количество удачных исходов, сводя эту задачу к задаче N-k. У меня при этом получилось рекуррентное соотношение p(N)=1-sum p(k)/k!, k=0...N-1 и p(0)=1. Илья, а как получить явный ответ?

    ОтветитьУдалить
  20. 7vies, у меня формула получается из твоей заменой k!->(N-k)!

    База моего решения:
    Пусть L(N, k) - исходов с k проигравшими. Тогда исходов с N-k програвшими:
    L(N, N-k)=C_{N}^{k}L(k, 0)
    т.е. если k произвольно выбранных человек не проиграло и вариантов не проиграть у них было L(k, 0).
    Используем то, что всех исходов было N!, вычитаем сумму по всем k=0..N-1

    ОтветитьУдалить
  21. Мне кажется все это можно объяснить гораздо проще:

    Вероятность получить свой же подарок составляет 1/N.
    Порадок вытаскивает N человек. Следовательно при любом N в среднем 1 человек получит свой же подарок.

    А прикинуть вероятность того что это не произойдет моя интуиция уже отказывается.

    ОтветитьУдалить
  22. А на мой взгляд, решение проще рядов и комбинаторики (хотя, конечно, каждому своё):

    1. Вероятность получить свой подарок для каждого участника равна 1/N.
    2. Вероятность получить чужой - соответственно 1-1/N.
    3. Вероятность всем получить чужой подарок: (1-1/N)^N
    4. (1-1/N)^N = ( (N-1)/N )^N = ( N/(N-1) )^-N = ( (N-1+1)/(N-1) )^-N = ( 1 + 1/(N-1) )^-N = ((1+1/(N-1))^N)^-1

    При N->+∞: N-1 -> N; ((1+1/(N-1))^N)^-1 -> e^-1

    Т.е. При N->+∞ получаем (1-1/N)^N -> 1/e

    ОтветитьУдалить
  23. PASTor, (1-1/N)^N - лишь "приблизительный" ответ, он неверен для некоторого конечного N, хоть в пределе и совпадает.
    Неверен он потому, что вероятности не являются независимыми. А в пределе совпадает, потому что они "не очень зависимы" :)

    ОтветитьУдалить
  24. PASTor, размышления понятные, формула хорошая, но при N=2 должно быть P(N)=0.5, а (1-1/N)^N=0.25. Другими словами, в некоторых случаях формула не работает.

    7vies, в завтрашней заметке я планирую привести чёткой вывод честной формулы.

    ОтветитьУдалить
  25. 1/(N!) вероятность что все получат свои подарки, следовательно 1-1/(N!) вероятность того что никто не получит своего подарка

    ОтветитьУдалить
  26. misha, 1/N! - это вероятность того, что все разом получат свои подарки (т.е. свой подарок получат все N участников). Соответственно, 1-1/N! - это веротяность того, что все разом не получат свои подарки.

    А вопрос задачи в том, с какой вероятностью никто не получит свой подарок (т.е. свой подарок получат ровно 0 человек). Это разные вопросы.

    Мы разобрали эту задачку в новой заметке.

    ОтветитьУдалить
  27. Небольшая поправка
    1-1/N! — вероятность того что найдутся те, кто получил не свой подарок.

    ОтветитьУдалить
  28. Kentzo, совершенно верно! Спасибо за ясную и краткую формулировку.

    ОтветитьУдалить
  29. Код на Matlab/Octave, который проводит тот же эксперимент:

    a = zeros(500,1);
    for participants = 1:500
    for test = 1:1000
    x = randperm(participants);
    if ~any(x == 1:participants)
    a(participants) = a(participants) + 1;
    end
    end
    end

    Получилась картинка:
    kosenkov.com/html/tmp/presents_distribution.png

    Вероятность что никто не получит свой подарок примерно равна 36.73%

    В случае двух участников, как и ожидалось, вероятность около 50%

    ОтветитьУдалить
  30. kosiakk,
    спасибо за дополнение!

    ОтветитьУдалить