Чтобы найти среднюю длину поискового маршрута, не обязательно перечислять все порядки обхода. Достаточно для каждого тупика определить вероятность того, что до него дойдёт очередь раньше выхода.
Условие
Из грота ведут десять штреков длиной 100, 200, …, 1000 метров. Самый длинный ведёт на поверхность, остальные заканчиваются тупиками. Вася выбирает штреки наугад и в уже посещённые повторно не ходит.
Какова вероятность, что он посетит самый короткий штрек? Какой путь в среднем пройдёт до выхода на поверхность?
В расчёте каждый ещё не посещённый штрек выбирается с одинаковой вероятностью; из тупика Вася возвращается в грот. Это явное описание модели, используемой далее. В сборнике решения нет: ниже — редакционный разбор.
Случайный порядок обхода
Можно мысленно заранее расположить десять штреков в равномерно случайном порядке. Вася идёт по этому списку и останавливается, встретив выход. Такая модель эквивалентна последовательному равновероятному выбору среди оставшихся штреков.
Для любого конкретного тупика важен только его порядок относительно выходного штрека. Из двух возможностей — тупик раньше выхода или выход раньше тупика — ни одна не имеет преимущества.
Вероятность посетить любой выбранный тупик равна 1/2.
В частности, ответ для самого короткого штрека — 1/2. Его длина на эту вероятность не влияет, поскольку выбор не зависит от длины.
Длина маршрута через индикаторы
Пусть Ii = 1, если Вася посетил тупик длиной 100i метров, и 0 иначе, где i = 1, …, 9. Каждый посещённый тупик приходится пройти в обе стороны. Выходной штрек проходится один раз:
L = 1000 + 2 · Σi=1⁹ 100i · Ii.
Математическое ожидание каждого индикатора равно вероятности соответствующего события: E(Ii) = 1/2. По линейности ожидания:
E(L) = 1000 + 2 · Σi=1⁹ 100i · 1/2 = 1000 + 100 · (1 + … + 9) = 5500 метров.
Итого средний путь составляет 5,5 километра.
Нужна ли независимость посещений
Нет. События посещения разных тупиков зависимы: раннее появление выхода в случайном порядке одновременно исключает многие тупики. Но линейность математического ожидания не требует независимости слагаемых.
Именно поэтому здесь удобно считать ожидаемый вклад каждого штрека отдельно. При вычислении дисперсии зависимость уже нельзя было бы игнорировать.
Проверка масштаба ответа
Минимальная длина пути — 1000 метров: Вася сразу выбирает выход. Максимальная — 1000 + 2 · (100 + … + 900) = 10 000 метров: сначала обходит все тупики. Полученные 5500 метров лежат между этими границами.
Каждый из девяти тупиков посещается с вероятностью 1/2, поэтому среднее число посещённых тупиков равно 9/2 = 4,5. Это согласуется с равномерной позицией выхода среди десяти мест в случайном порядке.
Связанные материалы
Случайный порядок и момент остановки в задаче о лампочках · Математика.
Борис Демешев и участники · probability_pro, задача 12.1 · CC BY 4.0. Условие адаптировано; решение редакции.