Будет ли когда-нибудь несчастный Трибл в Озе?

12

Вот забавная проблема, принесенная мне студентом. Хотя первоначально он был сформулирован в терминах взаимно уничтожающих пуль, выпущенных из пистолета через равные промежутки времени, я подумал, что вам может понравиться более миролюбивая презентация.

В бесконечном плоском мире Оз, Желтая Кирпичная Дорога начинается в центре Изумрудного Города, разматывается по всей сельской местности и продолжается вечно, не пересекая себя. Каждый день в полдень одна похотливая молодая гермафродитная Триббл отправляется по этой дороге от ее начала с равномерно случайно выбранной скоростью до одного километра в день. На протяжении всего пути он будет вращаться с одинаковой скоростью, не останавливаясь. Но если когда-либо один Трибл обгоняет другого на дороге, каждый мгновенно распознает свою вторую половинку, и эти двое уходят в сторону (предположительно, чтобы воспроизвести и в конечном итоге поставить больше Трибблса домой).

Как вы знаете, такие спаривания происходят часто, потому что вероятность того, что любые два Триблса будут катиться с одинаковой скоростью, равна нулю. О, счастливые Триблз! Но гарантирована ли жизнь всем им?

Какова вероятность того, что хотя бы один Трибл продолжится вечно, никогда не обгоняя и не обгоняя?

Whuber
источник
1
Предполагается ли это, что Триблс начали путешествовать в определенный момент времени (так что был Трибл # 1) и продолжаются с тех пор вечно, и вероятность должна быть вычислена за этот бесконечный промежуток времени?
говорит амеба: восстанови монику
1
@amoeba Если вы обнаружите, что есть разница, предполагая, что было определенное время начала, было бы очень интересно проанализировать эту разницу.
whuber
1
Трибблз в Оз? Ваши вымышленные вселенные кажутся немного перепутанными.
Кодиолог
3
@Kodio Обе вселенные хорошо известны тем, что пересекают другие вселенные :-).
whuber

Ответы:

2

Изменить: Я, кажется, смешал идею положительной вероятности и вероятности 1. Утверждение, доказанное здесь, гораздо слабее, чем я надеялся.

Интуитивно понятно, что ответ 0. Нетрудно доказать, что

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

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

Вот доказательство цитируемого утверждения. Во-первых, давайте заменим проблему более простой альтернативной формулировкой следующим образом. Есть стек, который начинается пустым. Компьютер рисует случайные изменения в последовательности независимо и равномерно из [0, 1]. Каждый раз, когда значение рисуется, стек меняется.

  • Если стек пуст или верхний элемент в стеке имеет большее значение, то добавляется новый элемент с новым значением. (Пуля медленнее, чем последняя пуля, или Трибл медленнее, чем последняя Триббл.)
  • В противном случае верхний элемент удаляется. (Пули или Трайблз сталкиваются.)

(Эта формулировка не включает в себя событие пули или триббла быстрее, чем создаваемое предыдущее, но затем уничтожается до попадания в предыдущее, но такое событие оставляет стек таким же, поэтому оно не имеет значения.)

1I0v0kI0v1,v2,,vkvkk+1(vk,1)(vk1,1)(v0,1)I0(1vk)(1vk1)(1v0)

Kodiologist
источник