Перестановки и комбинации интервью
Это хороший вариант, потому что он настолько противоречит интуиции:
Imagine an urn filled with balls, two-thirds of which are of one color and one-third of which are of another. One individual has drawn 5 balls from the urn and found that 4 are red and 1 is white. Another individual has drawn 20 balls and found that 12 are red and 8 are white. Which of the two individuals should feel more confident that the urn contains two-thirds red balls and one-third white balls, rather than vice-versa? What odds should each individual give?
Я знаю правильный ответ, но, возможно, я не совсем понимаю расчет шансов. Кто-нибудь может объяснить?
Также укажите, можем ли мы считать, что количество шаров в урне очень велико по сравнению с количеством выпавших, а если нет, то сколько шаров в урне.
dsimcha, количество шаров в урне не указано в копии вопроса, который у меня есть
Позвольте мне заявить, что я считаю это особенно плохим вопросом для интервью. Концепции действительно легко понять, но необходимые вычисления слишком длинны и утомительны, чтобы проводить их в контексте собеседования.
@Daniel: Это было бы правдой, если бы утомительные, но простые байесовские вычисления были простейшими из возможных. Но, вероятно, никто не знает, может быть, есть умное наблюдение, которое позволит нам избежать вычислений и сделает проблему тривиальной.
Полностью согласен с Даниилом. Это интересная проблема, но это очень плохой вопрос для собеседования с программистами.
@ Федерико - Да, но тогда это был бы вопрос "попался". Если вы хотите проверить, есть ли у кого-нибудь ключ к разгадке, спросите его: «В следующую субботу вероятность дождя составляет 50%, а в следующее воскресенье - вероятность дождя 50%. Какова вероятность того, что в выходные дни пойдет дождь?» ... Некоторые скажут 100% :)
Позвольте мне добавить к моему первому комментарию, что концепции действительно для понимания ... и пару неопределенных данных в проблеме также легко найти, поэтому я бы заподозрил интервьюеров - если они не ожидают, что я укажу на undefined ... неужели они сделали это специально? хм ...
Здесь слишком много предположений. Знает ли кто-либо о том, что извлек другой? Они оба положили свои яйца обратно, когда закончили считать?
@Federico - Эти шансы будут полностью зависеть от того, запланировал ли я поход. Если бы у меня был дождь, все время шел бы дождь, если бы я собирался сидеть дома и смотреть телевизор все выходные, было бы великолепное солнце. Хотя с математической точки зрения более вероятно, что будет дождь, но не сильно.
Ответы 4
Я предполагаю, что «априорная» вероятность одной гипотезы по сравнению с другой равна 1/2, и, более того, оба человека повторно вставляют каждый шар после его извлечения (извлечения независимы друг от друга).
Правильный ответ - наблюдатель второй должен быть увереннее первого. Мой предыдущий ответ был неправильным из-за тривиальной ошибки в вычислениях, большое спасибо и +1 Адаму Розенфилду за его исправление.
Пусть 2 / 3R 1 / 3Вт обозначает событие «урна содержит 2/3 красных шаров и 1/3 белых шаров», а 4R, 1 Вт обозначает событие «извлечены 4 красных шара и 1 белый шар». Затем, используя правило Байеса,
P [2 / 3R 1 / 3Вт | 4R, 1 Вт] = P [4R, 1 Вт | 2 / 3R 1 / 3Вт] P [2 / 3R 1 / 3Вт] / P [4R, 1 Вт] = (2/3) 4 (1/3) 1 (1/2) / P [4R, 1 Вт]
Теперь, поскольку 2 / 3R 1 / 3Вт и 1 / 3R 2 / 3Вт дополняют друг друга по гипотезе,
P [4R, 1 Вт] = P [4R, 1 Вт | 2 / 3R 1 / 3Вт] P [2 / 3R 1 / 3Вт] + P [4R, 1 Вт | 1 / 3R 2 / 3Вт] P [1 / 3R 2 / 3Вт] = (2/3) 4 (1/3) 1 (1/2) + (1/3) 4 (2/3) 1 (1/2)
Таким образом,
P [2 / 3R 1 / 3Вт | 4R, 1 Вт] = (2/3) 4 (1/3) 1 (1/2) / {(2/3) 4 (1/3) 1 (1/2) + (1/3) 4 (2/3) 1 (1/2)} = 2 ^ 4 / (2 ^ 4 + 2) = 8/9
Такой же расчет для P [2 / 3R 1 / 3Вт | 12R, 8 Вт] (т.е. имея (2/3) 12 (1/3) 8 вместо (2/3) 4 (1/3) 1) теперь дает 16/17, следовательно, уверенность второго наблюдателя выше, чем у первого. .
re: повторная вставка - не требуется, если количество шаров велико (вероятно, столь же верное предположение)
не следует P [4R, 1W | 2 / 3R 1 / 3W] = (2/3) ^ 4 * (1/3) ^ 1 * (5 выберите 4)? Кроме того, я не уверен, как вы пришли к априорному распределению 50%.
@FryGuy 50% (или любое другое известное число!) Априори является обязательным предварительным условием для принятия решения ... Если я скажу вам априори «100% уверен, что есть 2/3 красных шариков», тогда проблема тривиальна. , оба человека могут быть одинаково уверены ... я думаю, что здесь отсутствует слишком много данных
Проверьте свою арифметику - ваши рассуждения верны, но если вы вставите свои числа, вы должны получить 8/9 для первого наблюдателя и 16/17 для второго наблюдателя.
@ Адам Розенфилд: AAARGH! есть 2 ^ 1, которое волшебным образом превращается в 1. Исправление через минуту. Большое спасибо!
P[2/3R 1/3W | 4R, 1W] = (2/3)^4 * (1/3)^1 * (1/2) / { (2/3)^4 * (1/3)^1 * (1/2) + (1/3)^4 * (2/3)^1 * (1/2) } = 2^4 / (2^4 + 1) = 16/17
эээ,
= ⅔^4*⅓ / (⅔^4*⅓ + ⅓^4*⅔)
= 16/243 / (16/243 + 2/243)
= 16/18
Однако P (⅔R⅓W | 12R8W) действительно = 16/17, так что 12R8W может быть более уверенным.
Если это так, то насколько интуитивно понятна эта проблема? больше выборки = больше уверенности, особенно когда ваш образец соответствует вашим ожиданиям
Кстати, мой комментарий был больше направлен на строку «Это хороший, потому что он настолько противоречивый:», - сказал создатель темы.
Я не понимаю, как можно «интуитивно» что-нибудь из постановки задачи. Один забрал больше мячей, у другого процент красных выше, поэтому у обоих есть аргументы в пользу большей уверенности. Надо посчитать и найти результат, ничего не угадаешь.
Да, я не знаю, если только не возникнет еще одна коварная арифметическая ошибка, вызванная моим потреблением джина. Я бы предположил, что 12R8W более вероятен, хотя я бы не был в этом уверен ...
@Daneil Daranas: Ваши комментарии к вопросу о "простом множителе 3 * 10 ^ 11" были забавными. К сожалению, эта проблема требует вычисления нет и легко, если вы знаете теорию. Вы правы, это плохой вопрос программирования, но он не «слишком длинный и утомительный», и вы может интуитивно понимаете ответ.
@A. Рекс. Кто же тогда прав, Федерико (с одинаковой вероятностью) или Бобинс (с большей вероятностью)? А что такое «рассуждение» без всяких расчетов?
@ Дэниел Даранас (извините за мою опечатку в прошлый раз): Бобинс и Адам Розенфилд правы, потому что их арифметика верна. Пожалуйста, смотрите мое объяснение рассуждений без расчета, а также расчет без ошибок.
@bobince: (2/3) ^ 4 * (1/3) ^ 1 * (1/2) / {(2/3) ^ 4 * (1/3) ^ 1 * (1/2) + (1 / 3) ^ 4 * (2/3) ^ 1 * (1/2)}, вы можете упростить 1/2 и (1/3) ^ 5 как в числителе, так и в знаменателе, у вас останется 2 ^ 4 / ( 2 ^ 4 + 2) = 8/9. (2 ^ 4 + 1) было ошибкой, когда я набирал свой ответ, извините за это.
Действительно, правильно - я оставил знаменатель, чтобы прояснить, что 16/17> 16/18.
@yx: Я полагаю, что контринтуиция проистекает из того факта, что первый наблюдатель имеет выборку, которая «более смещена» в сторону гипотезы 2/3 красного цвета (у него большая доля красных шаров). Но помните, что у второго есть больший образец, и оба эти факта необходимо учитывать.
Что я сказал. Есть две конфликтующие «причины для уверенности», по одной для каждого человека, и вы не можете угадать что-нибудь. Просто сделайте математику обычным способом или с помощью @A. Интересный метод стенографии Рекса.
Пусть А - это событие, когда 2/3 шаров красные, а затем ¬А - событие, когда 2/3 шаров белые. Пусть B будет событием, когда первый наблюдатель видит 4 красных шара из 5, и пусть C будет событием, когда второй наблюдатель видит 12 красных шаров из 20.
Применяя простую комбинаторику, мы получаем, что
- P (B | А) = (5 выберите 4) (2/3) 4 (1/3) 1 = 80/243
- P (B | ¬А) = (5 выберите 4) (1/3) 4 (2/3) 1 = 10/243
Следовательно, согласно закону Байеса, наблюдатель 1 имеет уровень уверенности 80 / (80 + 10) = 8/9, что А истинно.
Для второго наблюдателя:
- P (C | А) = (20 выберите 12) (2/3) 12 (1/3) 8 = 125970 * 212 / 320
- P (C | ¬А) = (20 выберите 12) (1/3) 12 (2/3) 8 = 125970 * 28 / 320
Итак, снова из закона Байеса, наблюдатель 2 имеет уровень уверенности 212 / (212 + 28) = 16/17, что А истинно.
Следовательно, наблюдатель два имеет более высокий уровень достоверности, чем 2/3 шаров красные. Главное - понять, как работает закон Байеса. Фактически, все, что имеет значение, - это разница в количестве наблюдаемых красных и белых шаров. Все остальное (в частности, общее количество выпавших шаров) сокращается в уравнениях.
Адам, если вы еще не видели этого расчета с отношениями вероятностей и шансов, взгляните на мой пост. Я надеюсь, тебе это нравится.
Хе-хе. Может быть, я совершенно ошибаюсь, но разве не интуитивно понятно, что ответ должен быть вторым?
Видно соотношение: 4: 1 4/5: 1/5
Два видит соотношение 3: 1 3/4: 1/4
Итак, простой вопрос: кто ближе к 2/3: 1/3? Следовательно, ответ - Obs. Два.
Возможно, я сделал две ошибки и получаю простой ответ на что-то сложное, но прошу прощения за мое терпение, чтобы пройти долгие объяснения того, что я считал на самом деле интуитивно понятным.
Пожалуйста, откройте снова. Строго говоря это не связано с программированием, но определенно, по крайней мере, имеет косвенное отношение.