Случайное блуждание — это математическая модель с богатыми приложениями. Она описывает движение, направление которого в определенные моменты времени меняется случайным образом.
Самый простой случай — одномерное блуждание, вдоль прямой.
Допустим, в начале координат стоит Корней и шагает влево или вправо вдоль прямой. Чтобы выбрать направление, он перед каждым шагом бросает монетку. Если выпадет орел, — шагает вправо, а если решка — влево. Этот процесс и есть случайное блуждание. Путь Корнея, конечно, непредсказуем. Зависимость траектории от времени может выглядеть как-то так (на картинке разными цветами показаны разные варианты траектории):
В группе "Незадача дня" мы изучали, как могут быть устроены такие траектории. На рисунке голубым цветом отмечены фрагменты одной формы, они соответствуют комбинации "Решка-Орел-Решка-Орел". Много ли таких участков можно ожидать на одной траектории? Эту задачу можно переформулировать так:
Денежная прогулка
Есть 2019 монет, у каждой из которых на одной стороне 2, а на другой 0. Корней рассыпал монеты на пол строго наугад, а потом выложил их в ряд. Он шагает вдоль этого ряда и считает, сколько раз число 2020 встретится по пути. Это случайная величина N.
Найти математическое ожидание N.
Числа могут перекрываться. Например, в строке 20202020 Корней насчитает три числа 2020.
Александр Виноградов предложил решение, основанное на методе индикаторов.
Индикатор случайного события — случайная величина, которая равна 1, если событие произошло, и 0, если нет.
Для этой задачи нам понадобится 2016 индикаторов Х_i для i от 1 до 2016:
Х_i — случайная величина, которая равна 1, если на местах с i до i+3 включительно лежат монетки 2020 именно в таком порядке, и равна 0 в противоположном случае.
Эти случайные величины нельзя назвать независимыми. И правда, два "соседних" индикатора Х_i и Х_{i+1} не могут быть равны 1 одновременно, значит, они зависимы. Но это нам не мешает, важно только, что
N=Х_1+Х_2+...+Х_{2016}.
Математическое ожидание каждого индикатора найти легко, это
1⋅Р(на соответствующих местах лежат монетки 2020)+0⋅Р(на соответствующих местах не лежат монетки 2020),
то есть Р(на соответствующих местах лежат монетки 2020). Вероятность того, что одна монетка лежит правильно, равна 1/2. Вероятность того, что все четыре лежат правильно, равна 1/2⋅1/2⋅1/2⋅1/2=1/16. Раз МО(Х_i)=1/16, то
МО(N)=МО(Х_1)+МО(Х_2)+...+МО(Х_{2016})=2016/16=126.
Другие конструкции
Этот же прием годится, чтобы посчитать другие конструкции. Стоит ли ожидать, что за 2019 шагов выпадет 10 раз подряд одно и то же? Интуиция говорит нам, что если 10 раз подряд бросить правильную монетку, то не стоит ждать 10 подряд орлов или 10 подряд решек.
А если бросить ее 2019 раз?
Мы возьмем 2010 индикаторов, математическое ожидание каждого равно 1/512. Так что при 2019 бросаниях стоит ожидать 2010/512≈3,9 отрезков длины 10 из одинаковых элементов.