Вдохновленный выступлением Питера Доннелли на TED , в котором он обсуждает, сколько времени потребуется, чтобы определенный шаблон появился в серии бросков монет, я создал следующий сценарий на языке R. Учитывая два шаблона: «hth» и «htt», он вычисляет, сколько времени в среднем (то есть сколько монет бросит), прежде чем вы нажмете одну из этих моделей.
coin <- c('h','t')
hit <- function(seq) {
miss <- TRUE
fail <- 3
trp <- sample(coin,3,replace=T)
while (miss) {
if (all(seq == trp)) {
miss <- FALSE
}
else {
trp <- c(trp[2],trp[3],sample(coin,1,T))
fail <- fail + 1
}
}
return(fail)
}
n <- 5000
trials <- data.frame("hth"=rep(NA,n),"htt"=rep(NA,n))
hth <- c('h','t','h')
htt <- c('h','t','t')
set.seed(4321)
for (i in 1:n) {
trials[i,] <- c(hit(hth),hit(htt))
}
summary(trials)
Сводная статистика выглядит следующим образом,
hth htt
Min. : 3.00 Min. : 3.000
1st Qu.: 4.00 1st Qu.: 5.000
Median : 8.00 Median : 7.000
Mean :10.08 Mean : 8.014
3rd Qu.:13.00 3rd Qu.:10.000
Max. :70.00 Max. :42.000
В разговоре объясняется, что среднее количество подбрасываний монет будет различным для двух моделей; как видно из моей симуляции. Несмотря на то, что я смотрел разговор несколько раз, я до сих пор не понимаю, почему это так. Я понимаю, что «hth» перекрывает себя, и интуитивно я думаю, что вы нажмете «hth» раньше, чем «htt», но это не так. Я был бы очень признателен, если бы кто-то мог мне это объяснить.
источник
Предположим, вы подбрасываете монету раза и считаете, сколько раз вы видите шаблон «HTH» (включая перекрытия). Ожидаемое число . Но это также для «НТТ». Поскольку может перекрывать себя, а «HTT» - нет, вы ожидаете большего скопления с «HTH», что увеличивает ожидаемое время первого появления . n n H T H H T H8 н + 2 N N ЧАСTЧАС ЧАСTЧАС
Другой способ взглянуть на это состоит в том, что после достижения «HT» буква «T» отправит «HTH» обратно на старт, а буква «H» начнет переходить к возможному «HTT».
Вы можете отработать два ожидаемых времени, используя алгоритм Конвея [я думаю], посмотрев на перекрытия: если первые бросков шаблона соответствуют последним , то добавьте . Таким образом, для «HTH» вы получите в качестве ожидаемого значения, а для «HTT» вы получите , что подтверждает ваше моделирование.k 2 k 2 + 0 + 8 = 10 0 + 0 + 8 = 8К К 2К 2 + 0 + 8 = 10 0 + 0 + 8 = 8
Странность не останавливается там. Если у вас есть гонка между двумя паттернами, они имеют равную вероятность появления первыми, и ожидаемое время, пока один из них не появится, равно (на один больше, чем ожидалось, чтобы получить «HT», после чего должен появиться один из них) ,5
Ситуация ухудшается: в игре Пенни вы выбираете шаблон для гонки, а затем я выбираю другой. Если вы выберете «HTH», я выберу «HHT» и получу шансы на выигрыш 2: 1; если вы выберете «HTT», я снова выберу «HHT», и у меня все еще будут шансы 2: 1 в мою пользу. Но если вы выберете «HHT», я выберу «THH» и получу шансы 3: 1. Второй игрок всегда может изменить шансы, и лучший выбор не является переходным.
источник
Я люблю рисовать картинки.
Эти диаграммы являются автоматами конечного состояния (FSAs). Это крошечные детские игры (такие как « Лотки и лестницы» ), которые «распознают» или «принимают» последовательности HTT и HTH, соответственно, путем перемещения токена от одного узла к другому в ответ на подбрасывание монет. Маркер начинается с верхнего узла, на который указывает стрелка (линия i ). После каждого броска монеты токен перемещается вдоль края, помеченного результатом этой монеты (либо H, либо T), в другой узел (который я назову «узлом H» и «узлом T» соответственно). Когда токен приземляется на терминальном узле (нет исходящих стрелок, обозначенных зеленым), игра заканчивается, и FSA принял последовательность.
Думайте о каждом FSA как о прогрессе вертикально вниз по линейной дорожке. Подбрасывание «правильной» последовательности голов и хвостов заставляет жетон продвигаться к месту назначения. Бросок «неправильного» значения приводит к резервному копированию токена (или, по крайней мере, остановке). Токен возвращается в самое продвинутое состояние, соответствующее самым последним броскам. Например, HTA FSA в строке ii остается на линии ii при просмотре головы, потому что эта голова может быть начальной последовательностью возможного HTH. Это не идет полностью назад к началу, потому что это фактически полностью проигнорировало бы эту последнюю голову.
После проверки этих двух игр действительно соответствуют HTT и HTH, как заявлено, и сравнения их построчно, и теперь должно быть очевидно, что HTH труднее выиграть . Они различаются по своей графической структуре только в строке iii , где H возвращает HTT обратно в строку ii (и T принимает), но в HTH T возвращает нас обратно к строке i (а H принимает). Наказание в строке III в игре HTH является более суровым, чем в игре HTT.
Это может быть определено количественно. Я пометил узлы этих двух FSA ожидаемым количеством бросков, необходимых для принятия. Давайте назовем их узлом «значения». Маркировка начинается с
Пусть вероятность головок равна p (H), а вероятность хвостов равна 1 - p (H) = p (T). (Для справедливой монеты обе вероятности равны 1/2.) Поскольку каждый бросок монеты добавляет один к числу бросков,
Эти правила определяют значения . Это быстрое и информативное упражнение, чтобы убедиться, что помеченные значения (при условии, что монета правильная) верны. В качестве примера рассмотрим значение HTH в строке ii . Правило гласит, что 8 должно быть на 1 больше среднего значения 8 (значение узла H в строке i ) и 6 (значение узла T в строке iii ): достаточно точно, 8 = 1 + (1/2) * 8 + (1/2) * 6. Вы также можете легко проверить оставшиеся пять значений на рисунке.
источник
Несколько отличных ответов. Я хотел бы взять немного другую тактику и обратиться к вопросу о противоинтуитивности. (Я вполне согласен, кстати)
Вот как я это понимаю. Представьте столбец случайных последовательных результатов броска монеты, напечатанных на бумажной ленте, состоящий из букв «H» и «T».
Произвольно оторвите часть этой ленты и сделайте идентичную копию.
На данной ленте последовательность HTH и последовательность HTT будут встречаться так часто, если лента достаточно длинная.
Но иногда экземпляры HTH будут работать вместе, то есть HTHTH. (или даже очень редко HTHTHTH)
Это перекрытие не может происходить с экземплярами HTT.
Используйте маркер, чтобы выделить «полосы» успешных результатов, HTH на одной ленте и HTT на другой. Несколько полос HTH будут короче из-за перекрытия. Следовательно, промежутки между ними, в среднем, будут немного длиннее, чем на другой ленте.
Это немного похоже на ожидание автобуса, когда в среднем он ходит каждые пять минут. Если автобусам разрешено перекрывать друг друга, интервал будет в среднем немного больше, чем пять минут, потому что когда-нибудь два пройдут вместе.
Если вы прибудете в произвольное время, вы будете ждать в среднем немного больше следующего (для вас, первого) автобуса, если им позволят перекрываться.
источник
Я искал интуицию к этому в целочисленном случае (поскольку я пробираюсь через введение Росса к вероятностным моделям). Так что я думал о целочисленных случаях. Я обнаружил, что это помогло:
Итак, позвольте мне представить, что у меня есть шанс закончить рисунок на следующем тираже. Я рисую следующий символ, и он не заканчивает шаблон. В случае, если мой шаблон не перекрывается, нарисованный символ может все же позволить мне начать строить шаблон с самого начала.
В случае наложения символ, который мне был нужен для завершения моего частичного шаблона, был таким же, как и символ, который мне понадобился бы для начала восстановления. Так что я тоже не могу, и поэтому определенно нужно будет дождаться следующего розыгрыша, чтобы снова начать строить.
источник