Вычитал у К.Кнопа в жж задачку.

Есть n ящиков, в каждом из которых лежат k белых и n-k чёрных шариков (k последовательно принимает значения 1..n).
Случайным образом выбрав ящик, мы запустили туда руку и вынули шарик. Он оказался белым.
Какова вероятность того, что если мы вынем оттуда ещё два шарика, они тоже окажутся белыми?

Задача номер 1. Получить аналитическое решение.
Задача номер 2. Можно ли эту задачу решить, или хотя бы сделать грубую оценку, как-то по-простому — на пальцах, на интуиции?

(Ответов ещё не знаю. Размышляю...)

Здравствуйте, Кодт, Вы писали:

К>Есть n ящиков, в каждом из которых лежат k белых и n-k чёрных шариков (k последовательно принимает значения 1..n).
К>Случайным образом выбрав ящик, мы запустили туда руку и вынули шарик. Он оказался белым.
К>Какова вероятность того, что если мы вынем оттуда ещё два шарика, они тоже окажутся белыми?

Как не странно, но для любого N получается ответ 0.5

Вот так решал:

Здравствуйте, Буравчик, Вы писали:
Б>Как не странно, но для любого N получается ответ 0.5
А у меня 1/3. Причину разногласия выделю жирным.

1) Задача несимметричная относительно белых и чёрных (не используется)
2) Во всех ящиках есть белый шар
3) После того как мы достали белый шар, мы не получили новой информации о выборе корзины и о распределении шаров в ней.
4) После того как мы достали шар ситуация стала абсолютно симметричной =>
Вероятность достать два белых = вероятности два чёрных. (не используется)
5) Вероятность равна сумме вероятностей по всем корзинам
6) P = 1/n SUM( k=3..n, (k-1)/(n-1) * (k-2)/(n-2)) = 1/3

Следствие:
P(два белых) = P(два чёрных) = P(белочёрный) + P(чёрнобелый) = 1/3

Для интуитивного решения надо как то воспользоваться пунктом 4 наверно.

Здравствуйте, <Аноним>, Вы писали:


А>3) После того как мы достали белый шар, мы не получили новой информации о выборе корзины и о распределении шаров в ней.

Возможно. Я часто ошибаюсь, решая такие задачи.

Но представим две урны. В одной 1 белый и миллиард черных шаров. В другой 1 черный и миллиард белых. В каждой из них есть белые шары. Мы выбрали случайно урну и вытащили из нее наугад шар. Он оказался белым. Разве это не говорит о том, что более вероятно то, что мы выбрали вторую урну (в которой очень много белых шаров)?

Здравствуйте, Буравчик, Вы писали:

Б>Но представим две урны. В одной 1 белый и миллиард черных шаров. В другой 1 черный и миллиард белых. В каждой из них есть белые шары. Мы выбрали случайно урну и вытащили из нее наугад шар. Он оказался белым. Разве это не говорит о том, что более вероятно то, что мы выбрали вторую урну (в которой очень много белых шаров)?

Думал, что ответ очевиден, но честно говоря, не могу корректно сформулировать.
Определение комбинаторной вероятности это отношение всех подходящих вариантов события к общему количеству вариантов. Все урны перебираем РАВНОВЕРОЯТНО. Нам дано, что что-то там вытащили, но ключевое — мы перебираем всевозможные варианты событий.

Твоя формулировка неоднозначна. Если подходить формально, то в твоей задаче определено другое пространство событий:
<Выбрали урну1, вытащили шар чёрный N1>
<Выбрали урну1, вытащили шар чёрный N2>
...
<Выбрали урну1, вытащили шар чёрный N1000..>
<Выбрали урну1, вытащили шар белый N1>
<Выбрали урну2, вытащили шар белый N1>
<Выбрали урну2, вытащили шар белый N1000..>
...

Найти P(выбрана урна1), если вытащили белый.

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

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, <Аноним>, Вы писали:


А>>3) После того как мы достали белый шар, мы не получили новой информации о выборе корзины и о распределении шаров в ней.

Б>Возможно. Я часто ошибаюсь, решая такие задачи.

Б>Но представим две урны. В одной 1 белый и миллиард черных шаров. В другой 1 черный и миллиард белых. В каждой из них есть белые шары. Мы выбрали случайно урну и вытащили из нее наугад шар. Он оказался белым. Разве это не говорит о том, что более вероятно то, что мы выбрали вторую урну (в которой очень много белых шаров)?

У меня такое же решение и такой же ответ.

P(next_2_white | took_white) = Sum i=1,n : P(box = i | took_white) * P(next_2_white | took_white, box = i) — переписали событие took_white по всем возможным значениям дискретной случайной величины.
Интересно, что такая громоздкая сумма даёт в результате 0.5. Возможно, есть более простое решение без таких сумм.

Иногда одна вторая это просто одна вторая..

Я вижу только один способ как-то интуитивно обосновать, почему всегда получается одна вторая -- взять доказательство того что эта сумма равна 1/2 и попытаться "обратно портировать" это доказательство с языка чисел на язык элементарных исходов

Здравствуйте, Кодт, Вы писали:

К>Вычитал у К.Кнопа в жж задачку.

К>Есть n ящиков, в каждом из которых лежат k белых и n-k чёрных шариков (k последовательно принимает значения 1..n).
К>Случайным образом выбрав ящик, мы запустили туда руку и вынули шарик. Он оказался белым.
К>Какова вероятность того, что если мы вынем оттуда ещё два шарика, они тоже окажутся белыми?

К>Задача номер 1. Получить аналитическое решение.
К>Задача номер 2. Можно ли эту задачу решить, или хотя бы сделать грубую оценку, как-то по-простому — на пальцах, на интуиции?

Ответ P=1/2
Общее утверждение: P( вынем ещё p белых шариков, если q вынутых подряд оказались белыми ) = (q+1)/(p+q+1)
Например:
P( вынем ещё 1 белый шарик, если 1 оказался белым ) = 2/3
P( вынем ещё 2 белых шарика, если 1 оказался белым ) = 1/2
P( вынем ещё 10 белых шариков, если 1 оказался белым ) = 1/6
P( вынем ещё p белых шариков, если 1 оказался белым ) = 2/(p+2)
...
P( вынем ещё 4 белых шарика, если 3 вынутых подряд оказались белыми ) = 1/2

Решение
Обозначим событие A_p = {выбрали равновероятно ящик, взяли p шариков, а они все белые}.
P( вынем ещё p шариков, если q вынутых подряд оказались белыми ) = P( A_p+q при условии A_q ) = P(A_p+q и A_q) / P(A_q) = P(A_p+q) / P(A_q) = (q+1)/(p+q+1), так как P(A_q) = 1/(q+1) * (n+1)/n. Это следует из следующих равенств:

P(A_1) = 1/n (1/n + 2/n + ... + n/n) = (n+1)/n * 1/2
P(A_2) = 1/n (0 + 2/n*1/(n-1) + 3/n*2/(n-1) + ... n/n*(n-1)/(n-1)) = 1/n (1*2*3+2*3*4+...+(n-2)(n-1)n)) /((n-2)(n-1)n) = (n+1)/n * 1/3
...
P(A_q) = 1/n ( 1*2*...*q + 2*...*(q+1) + .. + (n-q+1)*....*n)/ ((n-q+1)*....*n) = (n+1)/n * 1/(q+1)

Самое сложное здесь посчитать сумму: S(n) = 1*2*..*q + 2*3*..*(q+1) + .... + (n-q+1)*(n-q+2)*...*n = 1/(q+1) * (n+1)n(n-1)...(n-q+1)
Это угадывается из общих соображений, и строго потом можно доказать индукцией по n.
— n=q — очевидно
— S(n+1)-S(n) = 1/{q+1} (n+1)n...(n-q) * (n+2-(n-q+1)) = (n+1)n..(n-q), что и требовалось

Здравствуйте, Кодт, Вы писали:

К>Вычитал у К.Кнопа в жж задачку.

К>Есть n ящиков, в каждом из которых лежат k белых и n-k чёрных шариков (k последовательно принимает значения 1..n).
К>Случайным образом выбрав ящик, мы запустили туда руку и вынули шарик. Он оказался белым.
К>Какова вероятность того, что если мы вынем оттуда ещё два шарика, они тоже окажутся белыми?

К>Задача номер 1. Получить аналитическое решение.
К>Задача номер 2. Можно ли эту задачу решить, или хотя бы сделать грубую оценку, как-то по-простому — на пальцах, на интуиции?

К>(Ответов ещё не знаю. Размышляю...)

Кстати у тебя другая немного задача получилась чем у Кнопа. У него N+1 ящиков и существует ящик в котором только чёрные (k=0)
Оригинал (http://knop.livejournal.com/280937.html):
Имеется (N+1) ящиков с черными и белыми шариками. В одном из них N белых шариков. В другом — один черный и N-1 белый. В третьем — два черных, а остальные белые. И т.д, в последнем ящике все N шариков черные. Мы выбираем ящик наугад (не зная, сколько шариков в нем белых) и вытаскиваем из него шарик. Он оказался белым. Затем мы вытаскиваем из этого же ящика еще два шарика. Какова вероятность того, что они оба окажутся белыми?

ps. Ну это если ответы вдруг сравнивать будем.

Здравствуйте, Аноним, Вы писали:

А>ps. Ну это если ответы вдруг сравнивать будем.

Очевидно, что добавление любого количества ящиков чёрных шариков никак на ответ не влияет, так как мы достоверно знаем, что один белый мы таки достали...

Здравствуйте, Кодт, Вы писали:

К>Задача номер 2. Можно ли эту задачу решить, или хотя бы сделать грубую оценку, как-то по-простому — на пальцах, на интуиции?

Сначала более простой вариант — после первого выбора белого шара выбирается еще один шар.
Вот трехмерный куб (.png, 16кБ).

	Скрытый текст

По оси Х отложен выбор ящика, координата X — номер ящика.
В ящике номер X лежат X белых шаров.
По оси Y отложен первый выбор шара (номер шара в ящике).
По оси Z отложен второй выбор шара (номер шара в ящике).
Каждая точка куба соответствует результату испытания.

В плоскости XY белый треугольник — выбор ящика и белого шара (синяя часть — выбор черного шара).
Выбор двух белых шаров лежит в пирамиде (Y<=X, Z<=X) — на рисунке выделен черными линиями.
Вероятность выбрать два белых шара, соответственно, равна 1/3 (в пределе по числу ящиков).
В точности она равна сумме квадратов от 1 до n, деленное на n в кубе.

Нас интересует условная вероятность по условию — "первый шар белый".
Этот набор результатов испытаний соответствует половине куба (выделен коричневым).
Т.о., искомая вероятность будет 1/3, деленное на 1/2 (в пределе по числу ящиков).

Чуть более сложный случай выбора двух белых шаров.
Тут для наглядности нужен четырехмерный куб.
Но ход рассуждений такой же.
Вероятность выбора трех белых шаров будет 1/4 (объем четырехмерной пирамиды с единичными основаниями и высотой).
Условная вероятность по условию "первый шар белый" будет равна 1/4, деленная на 1/2, т.е. 1/2.
Это в пределе по числу ящиков.
В точности, должно быть что-то вроде удвоенной суммы кубов от 1 до N, деленное на N в четвертой степени.

Здравствуйте, Буравчик, Вы писали:

Б>Как не странно, но для любого N получается ответ 0.5

По-простому (интуитивно) будет так: либо вытащим еще два шара / либо не вытащим — вероятность 1/2.

Здравствуйте, Буравчик, Вы писали:

Б>По-простому (интуитивно) будет так: либо вытащим еще два шара / либо не вытащим — вероятность 1/2.

Вот я так и знал, что надо было оговорить в условиях — про динозавра на Невском проспекте!!!

Здравствуйте, Кодт, Вы писали:

К>Вычитал у К.Кнопа в жж задачку.

К>Есть n ящиков, в каждом из которых лежат k белых и n-k чёрных шариков (k последовательно принимает значения 1..n).
К>Случайным образом выбрав ящик, мы запустили туда руку и вынули шарик. Он оказался белым.
К>Какова вероятность того, что если мы вынем оттуда ещё два шарика, они тоже окажутся белыми?

К>Задача номер 1. Получить аналитическое решение.
К>Задача номер 2. Можно ли эту задачу решить, или хотя бы сделать грубую оценку, как-то по-простому — на пальцах, на интуиции?

К>(Ответов ещё не знаю. Размышляю...)

Задача простая если знать условную вероятность и правильно определить что мы ищем.
Итак, аналитическое решение:
Рассмотрим один ящик, вероятность того что любые два выбранные оттуда шарика окажутся белыми:
k/n (если рассматриваем ящик под номером k).
Мы также должны выбрать ящик собственно — вероятность выбрать kый ящик равна 1/n.
Итак что мы ищем?
Мы ищем вероятность C = вероятности вытащить два белых шарика выбрав наугад ящик.
Это событие можно описат следующим образом аналитически
C = A1 * B + A2 * B + ... + An * B.
Где например Ai = событие заключающиеся в том, что мы выбрали ящик под номером i (i=1..n, или можно вместо i написать k). B = событие — мы выбрали два белых шарика(неважно откуда). A1 * B = это произведение событий означает, что случились события A1 и B одновременно (вместе) и то и другое.
Сумма же A1 * B + A2 * B например означает, что произошло событие либо A1 * B либо A2 * B. То ест хотя бы одно событие из суммы произошло. Собственно это мы и ищем. События в сумме (слагаемые Ai * B) — это события не совместные — невозможно, чтобы произошли одновременно и A1 * B и A2 * B. А значит
P(C) = P(A1 * B) + ... + P(An * B).
Осталось разобрать, что такое P(Ai * B).
P(Ai * B) = P(Ai) * P(B|Ai)
P(Ai) = 1/n
P(B|Ai) = вероятность того, что выбраны два белых шарика, при условии, что выбран ящик под номером i.
P(B|Ai) = можно разбить на как бы подсобытия = P(B1*B2|Ai), где B1 = первый шарик белый, B2 = второй шарик белый. В случае ящика под номером i имеем: P(B1 * B2) = P(B1) * P(B2|B1) = i/n * (i-1)/(n-1)
Итак
P(Ai * B) = i/n * (i-1)/(n-1) * 1/n
P(C) = Сумма по i = 1 до n слагаемых вида i/n * (i-1)/(n-1) * 1/n

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

Спасибо за задачу, очень интересная! Давайте еще таких =)

И да, может я где-то ошибся, но вроде все правильно, если что поправьте)

Ответ будет

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, Кодт, Вы писали:

К>>Есть n ящиков, в каждом из которых лежат k белых и n-k чёрных шариков (k последовательно принимает значения 1..n).
К>>Случайным образом выбрав ящик, мы запустили туда руку и вынули шарик. Он оказался белым.
К>>Какова вероятность того, что если мы вынем оттуда ещё два шарика, они тоже окажутся белыми?

Б>Как не странно, но для любого N получается ответ 0.5

Б>Вот так решал:

Б>

Извините, что приходиться такое говорить, но я считаю, что ваш ответ неверен, пожалуйста прочтите мой (ник tsaple) ниже ответ. В моем случае в пределе будет 1/3 вероятность. От N зависит вероятность, вовсе не 0,5 всегда
в моем решении ответ = (N+1)/(3N)
А для интуитивного понимания нужно прочесть простую теорию о складывании и произведений событий — что это такое глянуть и понять (теория множеств — объединение и пересечение) а также условную вероятность,
совместность событий и зависимость. В данной задаче используется при решении зависимость некоторых событий друг от друга и поэтому собственно мы используем условную вероятность. Условную вероятность очень просто и легко объяснит учебник по теорверу, я советую для этого учебник автора Кремер Теор вер и мат стат.

Здравствуйте, tsaple, Вы писали:

T>Ответ будет
T>

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

N=5 p(1 after 1)=0.666894
N=5 p(2 after 1)=0.500238
N=5 p(3 after 1)=0.39992
N=50 p(1 after 1)=0.666837
N=50 p(2 after 1)=0.500143
N=50 p(3 after 1)=0.400049
N=500 p(1 after 1)=0.666254
N=500 p(2 after 1)=0.499915
N=500 p(3 after 1)=0.400039
N=500000 p(1 after 1)=0.666842
N=500000 p(2 after 1)=0.500157
N=500000 p(3 after 1)=0.399942

Код теста:

#include <random>
#include <iostream>
#include <vector>

int main()
{
  std::vector<int> boxesSizes;
  boxesSizes.push_back(5);
  boxesSizes.push_back(50);
  boxesSizes.push_back(500);
  boxesSizes.push_back(500000);
  const int nAttempts = 10000000;
  std::random_device rd;
  std::mt19937 gen(rd());

  for( int test = 0; test < boxesSizes.size(); ++test )
  {
    const int nBoxes = boxesSizes[test];
    std::uniform_int_distribution<> box(1, nBoxes);
    std::uniform_int_distribution<> ball1(1, nBoxes);
    std::uniform_int_distribution<> ball2(1, nBoxes-1);
    std::uniform_int_distribution<> ball3(1, nBoxes-2);
    std::uniform_int_distribution<> ball4(1, nBoxes-3);

    int nFirstIsWhite = 0;
    int nNextIsWhite = 0;
    int nNextTwoAreWhite = 0;
    int nNextThreeAreWhite = 0;
    for( int i = 0; i < nAttempts; ++i )
    {
      int boxNumber = box(gen);
      if( ball1(gen) > boxNumber )
        continue;
      ++nFirstIsWhite;
      if( ball2(gen) > boxNumber - 1 )
        continue;
      ++nNextIsWhite;
      if( ball3(gen) > boxNumber - 2 )
        continue;
      ++nNextTwoAreWhite;
      if( ball4(gen) > boxNumber - 3 )
        continue;
      ++nNextThreeAreWhite;
    }
    std::cout << "N=" << nBoxes << " p(1 after 1)=" << float(nNextIsWhite) / nFirstIsWhite << std::endl;
    std::cout << "N=" << nBoxes << " p(2 after 1)=" << float(nNextTwoAreWhite) / nFirstIsWhite << std::endl;
    std::cout << "N=" << nBoxes << " p(3 after 1)=" << float(nNextThreeAreWhite) / nFirstIsWhite << std::endl;  }

  return 0;
}

Здравствуйте, Константин, Вы писали:

К>Здравствуйте, tsaple, Вы писали:

T>>Ответ будет
T>>

К>Ваши расчёты разбиваются о суровую реальность. Эксперимент подтверждает ответ 1/2, как подсчитано раньше независимо несколько раз.


К>

К>N=5 p(1 after 1)=0.666894
К>N=5 p(2 after 1)=0.500238
К>N=5 p(3 after 1)=0.39992
К>N=50 p(1 after 1)=0.666837
К>N=50 p(2 after 1)=0.500143
К>N=50 p(3 after 1)=0.400049
К>N=500 p(1 after 1)=0.666254
К>N=500 p(2 after 1)=0.499915
К>N=500 p(3 after 1)=0.400039
К>N=500000 p(1 after 1)=0.666842
К>N=500000 p(2 after 1)=0.500157
К>N=500000 p(3 after 1)=0.399942

К>Код теста:


К>

К>#include <random>
К>#include <iostream>
К>#include <vector>

К>int main()
К>{
К>  std::vector<int> boxesSizes;
К>  boxesSizes.push_back(5);
К>  boxesSizes.push_back(50);
К>  boxesSizes.push_back(500);
К>  boxesSizes.push_back(500000);
К>  const int nAttempts = 10000000;
К>  std::random_device rd;
К>  std::mt19937 gen(rd());

К>  for( int test = 0; test < boxesSizes.size(); ++test )
К>  {
К>    const int nBoxes = boxesSizes[test];
К>    std::uniform_int_distribution<> box(1, nBoxes);
К>    std::uniform_int_distribution<> ball1(1, nBoxes);
К>    std::uniform_int_distribution<> ball2(1, nBoxes-1);
К>    std::uniform_int_distribution<> ball3(1, nBoxes-2);
К>    std::uniform_int_distribution<> ball4(1, nBoxes-3);

К>    int nFirstIsWhite = 0;
К>    int nNextIsWhite = 0;
К>    int nNextTwoAreWhite = 0;
К>    int nNextThreeAreWhite = 0;
К>    for( int i = 0; i < nAttempts; ++i )
К>    {
К>      int boxNumber = box(gen);
К>      if( ball1(gen) > boxNumber )
К>        continue;
К>      ++nFirstIsWhite;
К>      if( ball2(gen) > boxNumber - 1 )
К>        continue;
К>      ++nNextIsWhite;
К>      if( ball3(gen) > boxNumber - 2 )
К>        continue;
К>      ++nNextTwoAreWhite;
К>      if( ball4(gen) > boxNumber - 3 )
К>        continue;
К>      ++nNextThreeAreWhite;
К>    }
К>    std::cout << "N=" << nBoxes << " p(1 after 1)=" << float(nNextIsWhite) / nFirstIsWhite << std::endl;
К>    std::cout << "N=" << nBoxes << " p(2 after 1)=" << float(nNextTwoAreWhite) / nFirstIsWhite << std::endl;
К>    std::cout << "N=" << nBoxes << " p(3 after 1)=" << float(nNextThreeAreWhite) / nFirstIsWhite << std::endl;  }

К>  return 0;
К>}
К>

Признаюсь, я ошибся, решил не ту задачу
Предлагаю следующее решение:
Можно ведь выразить задачу следующим образом,
У нас ящики со следующим содержанием шариков белых
1 2 3...N
Мы выбрали один из них ящиков и выбрали оттуда один белый шарик. Нас не интересует вероятность этого события, нас интересует чт будет дальше
а именно вероятность вытащить два белых шарика из того же ящика. Если не ошибаюсь то задача станет следующей.
C = K1 A1 A2 + ... + KN A1 A1, Ki = вероятность выбора iго ящика
A1 — вытащить белый шарик, A2 — вытащить еще раз белый шарик (второй раз)

с учетом того что шариков белых стало на один меньше:
P(Ki A1 A2) = P(Ki) P(A1 A2|Ki) = 1/N * (i-1)*(i-2)/((N-1)(N-2))
итого сумма будет следующей
1/N * (i-1)*(i-2)/((N-1)(N-2)) По i = 3..N
В итоге выходит ровно 1/3,
Вопрос такой тогда — если вы правы и овтет 0,5 то в чем моя ошибка?

Здравствуйте, tsaple, Вы писали:

T>Здравствуйте, Буравчик, Вы писали:

Б>>Здравствуйте, Кодт, Вы писали:

К>>>Есть n ящиков, в каждом из которых лежат k белых и n-k чёрных шариков (k последовательно принимает значения 1..n).
К>>>Случайным образом выбрав ящик, мы запустили туда руку и вынули шарик. Он оказался белым.
К>>>Какова вероятность того, что если мы вынем оттуда ещё два шарика, они тоже окажутся белыми?

Б>>Как не странно, но для любого N получается ответ 0.5

Б>>Вот так решал:

Б>>

T>Извините, что приходиться такое говорить, но я считаю, что ваш ответ неверен, пожалуйста прочтите мой (ник tsaple) ниже ответ. В моем случае в пределе будет 1/3 вероятность. От N зависит вероятность, вовсе не 0,5 всегда
T>в моем решении ответ = (N+1)/(3N)
T>А для интуитивного понимания нужно прочесть простую теорию о складывании и произведений событий — что это такое глянуть и понять (теория множеств — объединение и пересечение) а также условную вероятность,
T>совместность событий и зависимость. В данной задаче используется при решении зависимость некоторых событий друг от друга и поэтому собственно мы используем условную вероятность. Условную вероятность очень просто и легко объяснит учебник по теорверу, я советую для этого учебник автора Кремер Теор вер и мат стат.

Я ошибся не правильно поняв условия задачи, так что извиняйтся еще раз =)