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

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

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

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

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

probability stochastic-processes puzzle Whuber
источник

Предполагается ли это, что Триблс начали путешествовать в определенный момент времени (так что был Трибл # 1) и продолжаются с тех пор вечно, и вероятность должна быть вычислена за этот бесконечный промежуток времени?

говорит амеба: восстанови монику

@amoeba Если вы обнаружите, что есть разница, предполагая, что было определенное время начала, было бы очень интересно проанализировать эту разницу.

whuber

math.stackexchange.com/questions/1526292/colliding-bullets

Алекс Р.

Трибблз в Оз? Ваши вымышленные вселенные кажутся немного перепутанными.

Кодиолог

@Kodio Обе вселенные хорошо известны тем, что пересекают другие вселенные :-).

whuber

Ответы:

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

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

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

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

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

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

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

$1$ $I_0$ $v_0$ $k$ $I_0$ $v_1,\; v_2,\; …,\; v_k$ $v_k$ $k + 1$ $(v_k, 1)$ $(v_{k-1}, 1)$ $(v_0, 1)$ $I_0$ $(1 - v_k)(1 - v_{k-1})\cdots(1 - v_0)$

Kodiologist
источник