Среднее число шагов

[marie-la]

Пусть на столе лежат в ряд $n$ монет случайными сторонами. На каждом шаге, если решек ровно $k>0$, то $k-$я по порядку монета переворачивается. Если решек нет, процесс заканчивается. Пусть $S_n$ - количество шагов до конца процесса. Найти $ES_n$.


Ответ $\frac{n(n+1)}{4}$, я его получила, введя $x_1,x_2,...,x_n$ - положения монет 0 - герб, 1 - решка, $a_n=E(S_n|x_n=0), b_n=E(S_n|x_1=0, x_n=1), c_n=E(S_n|x_1=1, x_n=1)$ и построив реккурентное соотношение для этих последовательностей. Решение мне не нравится, оно громоздкое. Хотелось бы как-то упростить.

[gris]

Самое надёжное — это натурные испытания, которые я провёл несколько раз и убедился в правильности ответа.

 gp > {n=20; \\количество монет
m=1000; \\число испытаний
v=vector(n); \\ряд монет
sk=0; \\общее число шагов
for(i=1,m, \\цикл по испытаниям
  v=vector(n,j,random(2)); \\случайная выкладка монет
  k=0; \\количество шагов в текущем испытании
  until(0, \\ начало очередного шага
     r=vecsum(v); \\количество единиц
     if(r>0, k++; \\собственно шаг с проверкой завершения
        if(v[r],v[r]=0,v[r]=1); \\переворот
     , sk+=k; break \\завершение испытания
     );
  );
);
\\для простоты результат приводится в округлении до целого
print("number of steps=", sk\m, "  vs  n(n+1)/4=", n*(n+1)\4); 
}
number of steps=105  vs  n(n+1)/4=105

Пример испытания
[0, 0, 0, 1, 1, 0]
[0, 1, 0, 1, 1, 0]
[0, 1, 1, 1, 1, 0]
[0, 1, 1, 0, 1, 0]
[0, 1, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 1, 0]
[1, 1, 0, 0, 1, 0]
[1, 1, 1, 0, 1, 0]
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 0, 0]
[1, 1, 1, 0, 0, 0]
[1, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
number of steps=14 vs n(n+1)/4=10

wrest, спасибо! Я всегда внимательно отношусь к советам. Задумал провести проверку всех $2^n$ вариантов. Для сорока монет всего 33 года. У вас комп побыстрее будет Интересно, какая выкладка с наибольшим количеством шагов? Мне кажется, что оно в два раза больше среднего и реализуется на разных выкладках.

[wrest]

gris
С комментариями! Отлично!
Предложения (эстетические).

(Оффтоп)

Вместо
if(v[r],v[r]=0,v[r]=1); \\переворот
Пишем
v[r]=!v[r]; \\переворот

k=0; \\количество шагов в текущем испытании - удаляем
sk+=k; - удаляем

Вместо
k++
Пишем
sk++

Вместо
v=vector(n,j,random(2)); \\случайная выкладка монет
Пишем
v=apply(x->random(2),v); \\случайная выкладка монет

[b4b5]

Мат.ожидание $E_n=E_{n-1} + \frac{n}{2}$.

[marie-la]

b4b5 в сообщении #1697592 писал(а):

Мат.ожидание $E_n=E_{n-1} + \frac{n}{2}$.

Да, у меня это соотношение вышло в конце концов.
Можете написать, из каких соображений его получили?

-- 13.08.2025, 08:54 --

gris в сообщении #1697572 писал(а):

Интересно, какая выкладка с наибольшим количеством шагов? Мне кажется, что оно в два раза больше среднего и реализуется на разных выкладках.

Да-да, похоже, так и есть. Кажется, выкладка типа 11...100...0 - половина решек, потом половина орлов (если нечетное число монет, решек на 1 больше).

[b4b5]

marie-la
Добавление монеты 0 добавляет $0$ шагов.
Добавление монеты 1 добавляет $n$ шагов. Тут используем соображения симметрии при инверсии 0 на 1 для достижения "все 1".
$E_n= \frac{1}{2}E_{n-1} + \frac{1}{2}(E_{n-1} +n) }$

-- 14.08.2025, 23:48 --

Максимальное число шагов: $S_{max}(n) = n(n+1)/2$, достигается только на конфигурации, у которой первые $floor(n/2)$ нулей, затем $ceil(n/2) $ единиц.

[marie-la]

b4b5
Класс, спасибо!