Бараны

[StaticZero]

$N$ баранов идут по узкой горной тропе с разными скоростями в одном направлении, причём обгоны запрещены (таким образом, когда один баран догоняет другого, то он замедляется до скорости того, кого он догнал). Скорости баранам придаются случайным образом. Определить математическое ожидание количество групп, на которые бараны разбиваются при достаточно долгом движении.

(Кому интересно, могут поискать дисперсию, но я не считал.)

[arseniiv]

Иначе говоря, есть цепочка попарно различных элементов какого-то линейно упорядоченного множества, а интересующей величиной будет число убывающих подцепочек. Однако надо задать распределение исходных цепочек, чтобы что-то считать. Каким его принимали вы?

(Можно представить, что скорость барана равномерно распределена на $[0; 1]$ и все скорости независимы в совокупности, а случаи их равенства образуют множество нулевой вероятности, так что ими здесь можно пренебречь. А можно, например, взять цепочки чисел из $1..n$ и каждой придать равную вероятность, и это будет другая история, и, по идее, более простая, но зато условия не такие естественные.)

[StaticZero]

arseniiv в сообщении #1253828 писал(а):

А можно, например, взять цепочки чисел из $1..n$ и каждой придать равную вероятность, и это будет другая история, и, по идее, более простая, но зато условия не такие естественные

Да. $k$-тый баран имеет скорость $v_k$, где $v_k$ - элемент перестановки множества $1\ldots n$. Все наборы скоростей баранов равновероятны.

[lel0lel]

Сначала я стал находить количество перестановок чисел от $1$ до $N$, которые могут быть разбиты на $k$ подпоследовательностей, в которых первый член меньше всех предыдущих. Например для $N=5$ набор $\{2,4,3,1,5\}$ приводит к двум таким подпоследовательностям $\{2,4,3\}$, $\{1,5\}$. Но потом стало ясно, что добавление ещё одного барана не особо-то меняет мат. ожидание. Для простоты пусть он плетётся в конце стада, тогда с некоторой вероятностью он его может догнать, тем самым не изменив мат. ожидание, которое получается без него, либо не догнать, тогда число групп меняется на единицу. Из этих соображений $M(N)=\sum_{i=1}^{N}1/i$

[Sergic Primazon]

StaticZero в сообщении #1253808 писал(а):

$N$ баранов идут по узкой горной тропе с разными скоростями в одном направлении, причём обгоны запрещены (таким образом, когда один баран догоняет другого, то он замедляется до скорости того, кого он догнал). Скорости баранам придаются случайным образом. Определить математическое ожидание количество групп, на которые бараны разбиваются при достаточно долгом движении.

(Кому интересно, могут поискать дисперсию, но я не считал.)

Если для какой то цепочки баранов образовалось $m$ групп, то для обратной цепочки баранов образуется $(N+1-m)$ групп.
Поэтому : $M=\dfrac{N+1}{2}$

[grizzly]

Sergic Primazon в сообщении #1253851 писал(а):

Если для какой то цепочки баранов образовалось $m$ групп, то для обратной цепочки баранов образуется $(N+1-m)$ групп.

Ой ли? См. пример в предыдущем сообщении:

lel0lel в сообщении #1253837 писал(а):

Например для $N=5$ набор $\{2,4,3,1,5\}$ приводит к двум таким подпоследовательностям $\{2,4,3\}$, $\{1,5\}$.

При движении в обратном порядке образуется также 2 группы: $\{5\}$, $\{1,3,4,2\}$

[DeBill]

lel0lel
Ага. И это и есть полное решение!

[Sergic Primazon]

StaticZero в сообщении #1253808 писал(а):

$N$ баранов идут по узкой горной тропе с разными скоростями в одном направлении, причём обгоны запрещены (таким образом, когда один баран догоняет другого, то он замедляется до скорости того, кого он догнал). Скорости баранам придаются случайным образом. Определить математическое ожидание количество групп, на которые бараны разбиваются при достаточно долгом движении.

(Кому интересно, могут поискать дисперсию, но я не считал.)

Пусть $n$ баранов идут один за одним c cкоростями $ V_1, V_2, \ ...\ V_n$. Все скорости разные.

Расставим между этими скоростями знаки $>, <$.

Тогда $\left( ... <\underbrace{> ...>}_k <...\right )$ - образуют одну группу из $k+1$ баранов.


Достаточно заметить, что если для какой то расстановки знаков $(... ><>...)$ у нас получалось $(m)$ групп, то для обратной расстановки знаков у нас будет $(n+1-m)$ групп.

Поэтому среднее число групп $M_n=\dfrac{n+1}{2}$

[grizzly]

Sergic Primazon в сообщении #1253976 писал(а):

Тогда $\left( ... <\underbrace{> ...>}_k <...\right )$ - образуют одну группу из $k+1$ баранов.

Ну вот для повторения почти тот же конкретный пример: 6 баранов, первым идёт баран со скоростью 1, затем 5,4,3,2,6. Получаем $(1<5>4>3>2<6)$. Тогда это одна группа из 6 баранов. Что бы Вы не назвали здесь $k$ -- это в любом случае не $k+1$.

Sergic Primazon в сообщении #1253976 писал(а):

Достаточно заметить, что если для какой то расстановки знаков $(... ><>...)$ у нас получалось $(m)$ групп, то для обратной расстановки знаков у нас будет $(n+1-m)$ групп.

Смотрим на обратную цепочку: 6, 2, 3, 4, 5, 1. Имеем 3 группы -- 6; 2,3,4,5; и 1. И уж точно $6+1-1\ne 3$.

Посмотрите, пожалуйста, примеры (эти и в моём сообщении выше) и проверьте, так ли Вы понимаете условие, как все мы, или, может, ошибка где-то в рассуждениях.

-- 07.10.2017, 22:31 --

Ну и правильный ответ уже есть, да.

[waxtep]

Для проверки ответа достаточно посмотреть пример трех баранов, когда впереди самый медленный, а сразу за ним самый быстрый. В этой расстановке "в итоге" образуется одна группа, а не две (т.о. я голосую за ответ lel0lel)

[grizzly]

waxtep в сообщении #1253989 писал(а):

Для проверки ответа достаточно посмотреть пример трех баранов

Пример трёх баранов легко и быстро просчитывается полностью в уме. Так что да -- матожидание там 11/6 в полном соответствии.

[Sergic Primazon]

Да, я неправильно представил баранов)

Если в стаде самый медленный баран окажется в хвосте стада ( вероятность $p_1=\dfrac{1}{n}$), то мат. ожидание увеличится на 1,

а если не в хвосте ( вероятность $p_2=\dfrac{n-1}{n}$), то мат. ожидание не изменится.

т.е. $M_n=\left( M_{n-1}+1 \right ) \dfrac{1}{n}+M_{n-1}\dfrac{n-1}{n}=M_{n-1}+\dfrac{1}{n}$

[StaticZero]

Решал в лоб.

Для дисперсии красивого выражения не получается. Хотя и для матожидания рекуррентное соотношение свернуть не получилось, не зная заранее, что это частичная сумма гармонического ряда.

[Мастак]

grizzly в сообщении #1253892 писал(а):

lel0lel в сообщении #1253837 писал(а):

Например для $N=5$ набор $\{2,4,3,1,5\}$ приводит к двум таким подпоследовательностям $\{2,4,3\}$, $\{1,5\}$.

При движении в обратном порядке образуется также 2 группы: $\{5\}$, $\{1,3,4,2\}$

+
Все на группы, потом группы в группы, ..., и в итоге на длинных тропах останется только
две группы.
Что, например, всегда получается у велосипедистов на больших длинных гонках.

[StaticZero]

Пусть $L^k_n$ — количество способов разбить $n$ баранов на $k$ групп, $1 \leqslant k \leqslant n$. Ясно, что $L^1_1 = 1$.

Пусть мы располагаем $n-1$ бараном. Введём дополнительного барана с минимальной скоростью, что не умаляет общности, в конец цепочки. Этот баран не сможет никого догнать, стало быть, образует отдельную группу, состоящую из самого себя. Остальные $n-1$ баранов должны тогда образовать $k-1$ групп, что они могут сделать $L^{k-1}_{n-1}$ способами.

Пусть теперь самый медленный баран введён в цепочку на второе место с конца. В таком случае он отсекает от цепочки группу, состоящую из самого себя и того барана, который будет идти за ним. Но скорость отсечённого таким образом барана можно выбрать $n-1$ способами, а оставшиеся $n-2$ баранов должны образовать $k-1$ группу. Суммарное количество способов для такого положения дополнительного барана $(n-1)L^{k-1}_{n-2}$.

Пусть теперь самый медленный баран введён в цепочку на $s$-тое место с конца. Тогда цепочка рассекается на одну группу, которая будет плестись сзади, численностью $s$ баранов и группировку из $n-s$ баранов, которая должна образовать $k-1$ группу. Но скорости отсечённой отстающей группе можно выбрать $(n-1)(n-2)\ldots(n-s+1)$ способами. Всего способов получить данную расстановку $\dfrac{(n-1)!}{(n-s)!}L^{k-1}_{n-s}$.

В процессе такого разбиения баранов на подгруппы мы рано или поздно введём дополнительного барана на то место, где численность "лидирующей группы" баранов будет меньше, чем количество групп, которые она должна образовать. Стало быть, способов, которыми можно так сделать, будет нуль, откуда заключаем, что $L_p^q = 0$ при $q>p$. Заметим дополнительно, что $\sum \limits_k L^k_n = n!$.

После этих рассуждений можно написать

$$ L^k_n = \sum \limits_{s = 1}^{n-1} L^{k-1}_{n-s} \dfrac{(n-1)!}{(n-s)!}. $$

Искомое в задаче матожидание $\mu_n$ количества групп, на которые разобьются $n$ баранов, равно

$$ \mu_n = \sum \limits_{k=1}^n \dfrac{k L^k_n}{n!}. $$

Получим отсюда рекуррентное соотношение на $\mu_n$:

\begin{align*}\mu_n &= \sum \limits_{k=1}^n \dfrac{(k-1) L^k_n}{n!} = \dfrac{\sum \limits_{k=1}^{n-1} \sum \limits_{s = 1}^{n-1} k L^k_{n-s} \dfrac{(n-1)!}{(n-s)!}}{n!} + \sum \limits_{k=1}^n \dfrac{L^k_n}{n!} = 1 + \dfrac{\sum \limits_{s = 1}^{n-1} \sum \limits_{k=1}^{n-1} \dfrac{k L^k_{n-s}}{(n-s)!}}{n} = 1 + \dfrac{\sum \limits_{k=1}^{n-1} \mu_k}{n}. \end{align*} $$

Введём подстановку

$$ \mu_p = \sum \limits_{k=1}^p c_k, \quad 1 \leqslant p \leqslant n, $$

что ведёт к

$$ n \sum \limits_{k=1}^n c_k = n + c_1 + (c_1 + c_2) + \ldots + (c_1 + \ldots + c_{n-1}) = n + (n-1)c_1 + (n-2)c_2 + \ldots + (n-n+1) c_{n-1}, $$

откуда

$$ n c_n + (n-1) c_{n-1} + \ldots + 2 c_2 + c_1 = n. $$

Слева стоит сумма $n$ слагаемых, а $c_1 = \mu_1 = 1$, где последнее равенство очевидно. Поэтому естественно положить $c_k = 1/k$, окончательно получая

$$ \mu_n = \sum \limits_{k=1}^n \dfrac{1}{k}. $$

Используя тот же подход, можно получить рекуррентное соотношение на второй момент

$$ \chi_n = \dfrac{\chi_1 + \ldots + \chi_{n-1}}{n} + 2 \mu_n - 1, $$

которое той же подстановкой приводится к виду

$$ \chi_n = \mu_n + 2 \sum \limits_{k=1}^{n-1} \dfrac{\mu_k}{k+1}. $$

Дисперсия получается отсюда так: $D_n = \chi_n - \mu^2_n$.