вероятно

[avva]

Какая из последовательностей в среднем появится раньше, если бросать монету - орел, решка, орел или орел, решка, решка?

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

(в комментариях наверняка будут правильные ответы, я их не буду скрывать)

Update: мне стоит уточнить условие задачи, потому что в моей формулировке его можно понять двояко (прошу прощения). Итак, предположим, мы кидаем монету снова и снова и записываем количество бросков до того, как впервые получили ОРО (орел, решка, орел). В среднем выходит, что ОРО впервые появляется после X бросков. Теперь делаем то же самое для ОРР и получаем, что в среднем ОРР впервые появляется после Y бросков. Вопрос: как соотносятся друг с другом числа X и Y?

В комментариях есть уже несколько правильных ответов на этот вопрос.

Comments

[dizzy57.livejournal.com]

Итересная задачка чтобы подумать в самолёте между Москвой и Mountain View, спасибо. =)

[avva.livejournal.com]

О, велкам! :)

Разве есть проблема?

[vakhabit.livejournal.com]

В какой-то момент в первый раз появится орел, решка. Для следующего броска шансы орел или решка равны.

Re: Разве есть проблема?

[avva.livejournal.com]

См. update.

[ex-dr-deliri146.livejournal.com]

Равновероятно, потому как монета "не запоминает" последний результат поэтому веротность выпадения орел или решка при любом по счету броске 50/50

0,5*0,5*0,5=0,125

[ex-dr-deliri146.livejournal.com]

да добавить забыл, вероятность любой комбинации будет 1/2^n, где n-длина последовательности

[ohtori.livejournal.com]

Вероятность выпадания любой последовательности равна вероятности выпадания любой другой последовательности такой же длины.

[bacek.livejournal.com]

Чё тут думать-то. Вероятность обоих последовательностей 1/2^3

[braindancer.livejournal.com]

Моя математическая интуиция подсказывает то же, что написали предыдущие ораторы. Однако общечеловеческая интуиция подсказывает, что если бы все было так просто - avva не задавал бы этот вопрос :-)

Буду с интересом ждать прояснения ситуации.

[avva.livejournal.com]

:)

Никакого подвоха быть не должно))

[ex-alexloto.livejournal.com]

Допустим, что уже выпала последовательность орел, решка. Следующим ходом выпадет либо орел, либо решка))

[upstartn.livejournal.com]

Одинаковая вероятность.

[maxvt.livejournal.com]

Вторая.

Вероятность выпадания каждой из серий равна, но:

Когда в эксперименте бросков первой выпадает первая серия, то с вероятностью 0.25 сразу за ней будет вторая. (последний "орел" - первый "орел" второй серии). А если первой выпадает вторая серия, то за ней будет первая только с вероятностью 0.125 (первая серия не начинается с "решки").

[avva.livejournal.com]

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

[(Anonymous)]

HTH vs THH better.

[denspb.livejournal.com]

Анатолий, а там точно последовательности отличаются последним элементом, а не первым?

Потому, что в нынешнем варанте вероятность появления OP при условии, что раньше не встречалось ОРО и ОРР одинакова для обеих последовательностей, а следующая монета выпадет равновероятно.
А вот если бы у них были одинаковые "хвосты", но разные "головы" — тут было бы сложнее и интереснее.

[avva.livejournal.com]

Нет, я не ошибся в условии, именно так.

[oxfv.livejournal.com]

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

не могу молчать :)

[i-talk.livejournal.com]

отображение Х устанавливает биекцию между множеством O_n (OPO сначала на месте n) и P_n (OPP соответственно) : x_{n+2} -> not x_{n+2}

так что одинаково. это такая хитрая подколка, да?

Re: не могу молчать :)

[avva.livejournal.com]

См. update :)

[roma.livejournal.com]

kazhetsja, chto ORR skoree pojavitsja, no dokazat' bystro ne vyshlo.

Программисты, фиглиш

[itman.livejournal.com]

Результат симуляции, написанной за 5 минут дает следующие времена для матожидания появления одной из восьми возможных последовательностей:
0 -> 10.784000
1 -> 4.963700
2 -> 6.975200
3 -> 4.926600
4 -> 5.006500
5 -> 6.908700
6 -> 4.994600
7 -> 10.919700
Как несложно видеть, симметрично с точностью до инверсии О в Р, что можно было бы ожидать.
ОРО - это 5, ОРР - это 4. Соответственно, ОРР появляется на два шага раньше.
PS: над математическим обоснованием надо подумать. :-)

Re: Программисты, фиглиш

[i-talk.livejournal.com]

ОР
сначала идет цепочка из >=0 штук Р ( в среднем 1 )
затем идет цепочка из >0 штук О ( в среднем 2 )
затем Р
итак, после в среднем 4 монет появляется ОР.

С вероятностью 1/2 дальше будет О, с вероятностью 1/2 дальше будет Р; ОРР и ОРО имеют одинаковые шансы "выиграть первый приз". Но что будет дальше?

...ОРО:
+ в среднем 1 О
+ Р
+ с вероятностью 1/2 пришла Р, на месте 8, то есть ОРР

...ОРР:
ОРО должно начинать сначала

Итак, среднее время
ОРР = 1/2 * 5 + 1/4 * 8 + 1/8 *11 + ... = 5/2 + 3/2 + ОРР/2
то есть ОРР = 8
ОРО = 1/2 * 5 + 1/4 * 10 + ... = 5 + ОРО/2 то есть ОРО = 10

Вот. То есть ОРО и ОРР, имеют одинаковые шансы выиграть скачку, но если ОРР приходит первым, оно ставит подлянку ОРО.

[sovok4ever.livejournal.com]

зависит от того, кто кидает монету.

[http://users.livejournal.com/malfet_/]

Ну, если интуиция подводит, то OPP в среднем должно появляться раньше чем OPO.
Точнее, для бесконечной случайной последовательности, в среднем, расстояние от начала последовательности до подстроки "ОРР" будет меньше чем до подстроки "ОРО"

[rxvm.livejournal.com]

Вы изменили формулировку. Речь идет не о среднем расстоянии, а том, какое расстояние из двух в среднем меньше.

[i-talk.livejournal.com]

offtop - did you hear about /dev/random vulnerabilities?

[qaraabayna.livejournal.com]

Да кому он вообще нужен даже и без vulnerabilities?

действительно, стоило бы уточнить

[a-shen.livejournal.com]

какой вопрос имеется в виду: для какой из двух последовательностей математическое ожидание числа бросаний до появления меньше, или какое событие - "в случайной последовательности ОРО раньше ОРР" или его отрицание -= более вероятно

Re: действительно, стоило бы уточнить

[avva.livejournal.com]

Да, вопрос о матожидании. Спасибо, добавил в запись.

[prettymoonlight.livejournal.com]

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

[white-lee.livejournal.com]

ОРО раньше чем ОРР, потому что серия из пяти бросков может содержать ОРО дважды, а ОРР - не может :). David Deutsch показывал это на одной из лекций в TED, имел феноменальный успех. Вообще очень полезная лекция, он там показывает гигантское влияние неправильно истолкованной статистики на нашу жизнь (там есть про женщину, к-рой из-за врача-специалиста, неправильно истолковавшего статистику, дали пожизненный срок за убийство двух своих детей, к-рого она не совершала). Могу дать ссылку :)

[avva.livejournal.com]

Только наоборот - ОРР раньше, а так все верно :)

[arish.livejournal.com]

Мне кажется тот же эффект виднее, если ждать выпадения 666 или 456 на кубике.

[max630.livejournal.com]

Не совсем понятно, что значит "в среднем появится раньше". Если то что из каждой серии определяется, какая последовательность вперёд, и сравнивается, сколько раз была ОРО и сколько ООР, тогда поровну, как указали vakhabit и все после него. Если в каждой серии смотрится, на каком месте была ОРО, а на каком ООР, а потом для каждой их них результ ат усредняется - то тут, возможно, будет несимметричность.

[avva.livejournal.com]

Да, см. update.

[109.livejournal.com]

мне стоит уточнить условие задачи

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

[igoralexeev.livejournal.com]

Ответ, который подсказывает интуиция:
орел, решка - 3/8.
орел, орел - 3/8.
решка, решка - 1/4.
Вообще ответ достаточно очевиден.
А еще есть интересные задачи?