Распределение порядка во всех перестановках

[Хорхе]

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

Ну да ладно, Штирлиц, живите спокойно в своем лесу. А я буду жить в своем и впредь не буду вас упрекать.

[PAV]

Просьба прекратить выяснять отношения. Хорхе, по-моему, Вы в своих эмоциях в данном случае неправы. Я ничего предосудительного в поведении автора темы не вижу. По его мнению, Ваш текст не отвечает на его вопрос и не особо помогает в этом ответе, поэтому отсутствие благодарности тут вполне объяснимо. А извиняться ему не за что, на все дополнительные вопросы по поводу постановки задачи он быстро и корректно отвечал.

[nn910]

Кажется ,непрерывная задача будет неплохим приближением при больших n. Рассматриваются последовательности независимых испытаний $0<x_n<1$ равномерно распределенной СВ, нужно найти матожидания длины (=количества членов) монотонных участков последовательности (участки выделяются по естественному алгоритму топикстартера,поэтому всякий член последовательности попадет на участок длины хотя бы 2) Грубый подсчет дает около 3 а не 2,41, но есть ощущение что задача в этой постановке давно решенная точно.Разница с предложенной нам дискретной постановкой (где нет независимости) убывает с ростом n
Да,а грубый подсчет был такой.Пусть х -ы вообще на прямой и вероятности что х>у равны 0,5. Тогда матожидание равно сумме ряда $ \sum_{n=1}^{\infty}\dfrac{n+1}{2^n} =3$

[Scholium]

nn910 в сообщении #251359 писал(а):

Кажется ,непрерывная задача будет неплохим приближением при больших n. Рассматриваются последовательности независимых испытаний $0<x_n<1$ равномерно распределенной СВ, нужно найти матожидания длины (=количества членов) монотонных участков последовательности (участки выделяются по естественному алгоритму топикстартера,поэтому всякий член последовательности попадет на участок длины хотя бы 2) Грубый подсчет дает около 3 а не 2,41, но есть ощущение что задача в этой постановке давно решенная точно.Разница с предложенной нам дискретной постановкой (где нет независимости) убывает с ростом n
Да,а грубый подсчет был такой.Пусть х -ы вообще на прямой и вероятности что х>у равны 0,5. Тогда матожидание равно сумме ряда $ \sum_{n=1}^{\infty}\dfrac{n+1}{2^n} =3$

Очень интересные соображения. Меня как раз большие n и интересуют, так как я занят оптимизацией алгоритма внешней сортировки естественным слиянием для огромных файловых массивов. Поэтому стремлюсь увеличить эффективность данного алгоритма за счет использования естественного порядка в случайных последовательностях (в естественных базах данных случайный порядок данных обычно значительно выше, чем в равномерно распределенных случайных последовательностях). Можно взять специальную «зигзагообразную» последовательность любой четной длины, у которой будет средняя длина УПП (упорядоченной (монотонной) подпоследовательности) абсолютно точно равной 2. Но такие последовательности из ряда вон выходящие. У обычной случайно сгенерированной последовательности, которые я проверял, средняя длина примерно одинакова, что для тысячи элементов, что для миллиона. И действительно лежит в указанных пределах. Впрочем, эксперимент есть эксперимент, я ни на чем особо не настаиваю. Может быть, псевдослучайная последовательность была не слишком случайной .

Что касается ваших рассуждений, то меня смущает тот факт, что вы не учли события для х $\leqslant$ у. Грубо говоря, матожидание увеличится вдвое? И будет равно 6? Что-то тут не так. Я пробовал решать эту задачу, беря последовательно n = 1, 2, 3, 4 и т.д. с желанием воспользоваться затем матиндукцией. Но, пока еще не получил устойчивых результатов. Откровенно говоря, был больше занят программированием, чем математикой .

[Maslov]

Scholium в сообщении #251383 писал(а):

Что касается ваших рассуждений, то меня смущает тот факт, что вы не учли события для х $\leqslant$ у. Грубо говоря, матожидание увеличится вдвое? И будет равно 6?

Да нет, матожидание длины убывающей последовательности такое же, как и возрастающей.

-- Вт окт 13, 2009 20:24:38 --

Кстати, а почему Вы перестановки берете (без повторений)? Вы только по уникальному ключу сортируете?

[nn910]

Scholium в сообщении #251383 писал(а):

Что касается ваших рассуждений, то меня смущает тот факт, что вы не учли события для х $\leqslant$ у. Грубо говоря, матожидание увеличится вдвое? И будет равно 6? Что-то тут не так.

Тут речь об условных матожиданиях (считаемых не по всему множеству вариантов),а полное находится по ним не сложением,а усреднением.
Я решил часика 2 подождать эрудита который даст нужную ссылку,но теперь вижу что задача слишком проста чтобы где-то публиковаться,да так чтобы ее люди запомнили.Однако число так и не посчитал.
Точно в указанной постановке обозначим $P_m(x)$ вероятность длины ровно m у возрастающей последовательности,начинающейся с x, тогда ответ=матожидание
$M=\int_0^1 {M(x)dx}$ где $(P_2(x)+P_2(1-x))M(x)=P_2(x) \sum_{m=2}^{\infty}mP_m(x)+P_2(1-x) \sum_{m=2}^{\infty}mP_m(1-x)$
Остается найти $P_m (x)=\int_x^1 {P_{m-1}(t)dt}=...$ в итоге выражается через объемы многомерных симплексов,т.е.факториалы,но сейчас у меня что-то не сошлось.Интегрировать точно придется квазимногочлен не выше 2 степени.
$P_m(x)=\dfrac{(1-x)^{m-1}}{(m-1)!}-\dfrac{(1-x)^{m}}{m!}$
Вроде так

[Scholium]

Maslov в сообщении #251386 писал(а):

Scholium в сообщении #251383 писал(а):

Что касается ваших рассуждений, то меня смущает тот факт, что вы не учли события для х $\leqslant$ у. Грубо говоря, матожидание увеличится вдвое? И будет равно 6?

Да нет, матожидание длины убывающей последовательности такое же, как и возрастающей.

-- Вт окт 13, 2009 20:24:38 --

Кстати, а почему Вы перестановки берете (без повторений)? Вы только по уникальному ключу сортируете?

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

По второму вопросу. В реальности у меня могут быть любые последовательности данных, как неупорядоченные, так и частично и вполне упорядоченные. Наличие повторений только увеличивает порядок на множестве монотонных (убывающих и неубывающих) подпоследовательностях. Но в теории интересно исследовать «чистые» варианты, затем постепенно усложняя их. Попутно можно будет искать ответы на другие вопросы, например, может ли критерий средней длины УПП для данной случайной последовательности служить мерой ее случайности? Если средняя длина УПП будет равна 2 или n (для достаточно больших n), то это будет говорить о том, что последовательность имеет явную структуру и очевидно не случайна. Из ваших утверждений следует, что если достаточно длинная последовательность имеет среднюю длину УПП равной 3, то с большой вероятностью (на множестве всех таких последовательностей) она будет случайной (равномерно распределенной на некотором интервале). Возможно, тройка дает в этом смысле максимальную вероятность, но не факт. Но это так, лирическое отступление .

[nn910]

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

[Scholium]

nn910 в сообщении #251409 писал(а):

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

Спасибо! У Вас очень неплохие результаты. Пока пытаюсь разобраться с ними. Давно уже не занимался математикой, так что нужно время, чтобы «въехать» .

Согласен что не в полной мере. Ибо средняя длина в некотором смысле интегральная характеристика. Но как необходимое условие, то почему бы и нет. Более информативным будет распределение УПП в случайной последовательности по длинам этих упорядоченных подпоследовательностей. Думаю, что равномерно распределенная случайная последовательность должна иметь строго определенное распределение порядка. Если Вы его откроете, то его можно будет назвать Вашим именем. Да и средняя длина в такой последовательности должна быть строго определенной (3 – по Вашему?).

-- Ср окт 14, 2009 08:33:07 --

Насчет не периодичности на конечном множестве. Теоретически тут нет проблемы, если взять достаточно большой период. Но практически генерация хороших и длинных псевдослучайных чисел – нетривиальная задача. Просто в наших рассуждениях мы добавляем еще один критерий случайности – соответствие теоретического распределения УПП фактическому. Не исключено, что мы ломимся в открытые ворота и это распределение уже известно. Но каково оно: Коши, Лапласа, Пуассона или другое известное? Или может быть совершено другое?

[Shtirlic]

Scholium
Могу предложить такое, для начала можно ограничиться тем чтобы рассмотреть просмотр только в одну сторону и искать последовательности по возрастанию. Дальше если взять два рядом стоящих числа, то вероятнось что они по возрастанию равна 0.5, если рассматривать три числа, то можно рассмотреть 1-е и 2-е, 2-е и 3-е, тогда вероятность 0,4. Причем надо учитывать пересечения. Исходя из этого можно попробовать что-то сделать.

-- Ср окт 14, 2009 20:16:24 --

Еще для упращения можно рассмотреть количество последовательностей по позрастанию начиная с первого элемента, а потом посчитать общее количество используя циклическое смещение, то есть если есть 12354 то есть и 41235. Но тут надо быть аккуратней, чтоб повторно одно и тоже не считать. Так пересчитать количество разных последовательносте не сложно, но надо учитывать, что последовательность длины 2 входит п последовательность длины 3.

[Scholium]

nn910 в сообщении #251359 писал(а):

Да,а грубый подсчет был такой.Пусть х -ы вообще на прямой и вероятности что х>у равны 0,5. Тогда матожидание равно сумме ряда $ \sum_{n=1}^{\infty}\dfrac{n+1}{2^n} =3$

Я тут решил посмотреть на это дело немного по-другому. Вот смотрите.

Рассмотрим любую перестановку натуральных чисел от 1 до n. Вычислим матожидание полного порядка среди чисел, начинающегося с начала последовательности. Полный порядок означает, что все числа упорядочены по возрастанию или убыванию. Берем первое число перестановки. С вероятностью 1 оно обладает полным порядком (по определению). Берем первые два числа перестановки. Они также с вероятностью 1 образуют порядок (по возрастанию или убыванию). Берем первые три числа перестановки. Они, очевидно, образуют порядок с вероятностью $2/3!$. Четыре числа образуют порядок с вероятностью $2/4!$ и т.д. Для первых n чисел последовательности вероятность порядка равна $2/n!$. Матожиданием количества первых упорядоченных элементов перестановки будет сумма ряда $1+\sum\limits_{k=2}^n\dfrac{2}{k!}$. При переходе к бесконечности получаем:
$1+\sum\limits_{n=2}^{\infty}\dfrac{2}{n!} = 2e - 3 = 2.436563656$. Но это же число к которому стремиться экспериментально определенное для среднего количества упорядоченных подпоследовательностей (УПП) в последовательности случайных чисел равное 2,41 – 2,42, о котором я уже упоминал ранее! А в Вашей формуле еще надо добавить 1 для случая того, что подпоследовательность длины единица встретиться с вероятностью единица. Тогда, мой вывод Вашей формулы совпадет с Вашим выводом, в результате, искомой длиной будет 4, а не 3. Но эта интерпретация все же остается под вопросом.

-- Ср окт 14, 2009 14:27:01 --

Shtirlic в сообщении #251587 писал(а):

Scholium
Могу предложить такое, для начала можно ограничиться тем чтобы рассмотреть просмотр только в одну сторону и искать последовательности по возрастанию. Дальше если взять два рядом стоящих числа, то вероятнось что они по возрастанию равна 0.5, если рассматривать три числа, то можно рассмотреть 1-е и 2-е, 2-е и 3-е, тогда вероятность 0,4. Причем надо учитывать пересечения. Исходя из этого можно попробовать что-то сделать.

-- Ср окт 14, 2009 20:16:24 --

Еще для упращения можно рассмотреть количество последовательностей по позрастанию начиная с первого элемента, а потом посчитать общее количество используя циклическое смещение, то есть если есть 12354 то есть и 41235. Но тут надо быть аккуратней, чтоб повторно одно и тоже не считать. Так пересчитать количество разных последовательносте не сложно, но надо учитывать, что последовательность длины 2 входит п последовательность длины 3.

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

[Shtirlic]

Общее количество у меня получилось $2^{n-1}-n$ - для четного n и $2^{n-1}-n-1$ для нечетного.

[Scholium]

Shtirlic в сообщении #251614 писал(а):

Общее количество у меня получилось $2^{n-1}-n$ - для четного n и $2^{n-1}-n-1$ для нечетного.

Наверное, мы имеем в виду разные вещи. Если Вы имеете в виду количество всех УПП (упорядоченных подпоследовательностях) на всех перестановках, то для малых n получаются другие значения:
У Вас: $2\to-1; 3\to1; 4\to3; 5\to11; 6\to25; 7\to57; 8\to119$.
У меня (путем тупого перебора и подсчета): $2\to2; 3\to10; 4\to46$.
Идея такая, для n чисел берем n! перестановок и подсчитываем суммарное количество УПП (любого порядка, слева направо, пока сохраняется порядок). Пусть это число будет $q_n$, тогда средняя длина $L_n$УПП будет равна: $L_n = \dfrac{n! n}{q_n}$. Примерно так (если я не ошибся) . Соответственно, $L_2 = 2; L_3 = 9/5 = 1,8; L_4 = 48/23 = 2,087$. Дальше считать вручную тяжело. Можно, конечно, написать программу и получить фактические числа, то для теории я в них особого смысла не вижу.

-- Ср окт 14, 2009 16:19:50 --

В принципе, $L_n$ похоже, что уже ассимтотически вычислена, т.е.
$L_n = 1+\sum\limits_{i=2}^n\dfrac{2}{n!}$, отсюда находим ассимтотическое значение для $q_n = \dfrac{n! n}{L_n}$.
Этот ряд быстро сходящийся, поэтому можно сделать подстановку $L_n = 2e - 3$, тогда суммарное количество УПП ассимтотически равно: $q_n = \dfrac{n! n}{2e - 3}$. Можно даже подсчитать эту величину по двум формулам («точной» и «приближенной»):
$q_2 = 2$ и $q_2 = 1.64$. Реальное значение: $q_2 = 2$;
$q_3 = 7.71$ и $q_3 = 7.39$. Реальное значение: $q_3 = 10$;
$q_4 = 39.7$ и $q_4 = 39.4$. Реальное значение: $q_4 = 46$;
$q_5 = 246.6$ и $q_5 = 246.2$. Реальное значение: ? ;
$q_6 = 1773$ и $q_6 = 1773$. Реальное значение: ? ;
$q_7 = 14479$ и $q_7 = 14479$. Реальное значение: ? .

[maxal]

Scholium в сообщении #251277 писал(а):

Дано множество всех перестановок натуральных чисел от 1 до n. Сколько в них будет упорядоченных (по возрастанию или убыванию) подпоследовательностей длины $Q_n(k)$ для $1 \leqslant k \leqslant n$? Случай $k = 1$ будем рассматривать только для тех перестановок, которые дают «зависшую» подпоследовательность длины 1 в конце перестановки. Порядок подпоследовательностей рассматривается относительно начала перестановки. Подпоследовательности рассматриваются до тех пор, пока сохраняется их локальный порядок и не пересекаются между собой. Также интересует средняя длина таких упорядоченных подпоследовательностей.

Очевидно, что $Q_n(n) = 2$. Но для остальных k формулы, очевидно, будут сложнее.

Здесь проще перебрать все такие возможные подпоследовательности (точнее здесь правильнее говорить о подстроках, которые по-научному называются "подъёмами" или "спусками"). Для определенности будем подсчитывать максимальные подъёмы. Рассмотрим два случая:

1) Пусть $1<k\leq n-1$ и подъём идет в начале перестановки (или в конце - подсчёт аналогичен). Количество таких перестановок равно

$$\binom{n}{k+1}\cdot k\cdot (n-k-1)!=\frac{n!}{(k-1)!(k+1)},$$

где $\binom{n}{k+1}$ - количество различных $k+1$ начальных элементов, $k$ - количество способов выбрать $k+1$-й элемент (он не может быть максимальным), и $(n-k-1)!$ - все возможные перестановки остальных элементов.

2) Пусть $1<k\leq n-2$ и подъём идет в середине перестановки. Количество таких перестановок равно:

$$(n-1-k)\binom{n}{k+2}(k(k-1)+2k+1)(n-k-2)!=\frac{n!(n-1-k)(k^2+k+1)}{(k+2)!}.$$

Здесь первый множитель отвечает за выбор начальной позиции для подъёма, второй - за выбор содержимого подъёма вместе с окаймляющими элементами, третий - за выбор пары окаймляющих элементов из выбранных (первый не может быть минимальным, последний - максимальным), четвертый - за перестановки остальных элементов.

Итак,

$$Q_n(k) = 2\left(1 + [k\leq n-1]\cdot 2\frac{n!}{(k-1)!(k+1)} + [k\leq n-2]\cdot \frac{n!(n-1-k)(k^2+k+1)}{(k+2)!}\right).$$

-- Wed Oct 14, 2009 08:16:17 --

Впрочем, так как последнее слагаемое обнуляется при $k=n-1$, то формулу для $1<k<n$ можно записать просто как:

$$Q_n(k) = 2\left(1 + 2\frac{n!}{(k-1)!(k+1)} + \frac{n!(n-1-k)(k^2+k+1)}{(k+2)!}\right)=2\frac{n!(-k^3 + nk^2 + (n + 2)k + n - 1)}{(k+2)!}.$$

-- Wed Oct 14, 2009 08:19:48 --

Scholium в сообщении #251277 писал(а):

Случай $k = 1$ будем рассматривать только для тех перестановок, которые дают «зависшую» подпоследовательность длины 1 в конце перестановки.

Это слишком искусственное ограничение - последний элемент вместе с предпоследним всегда будет образовывать либо спуск, либо подъём. Строго говоря, максимальный подъём или спуск длины $1$ существует только для $n=1$.

[Shtirlic]

Я ошибся при расчетах. Идея такова: на первом месте могут быть любывая два числа, нас интересует когда они по возрастанию, то есть доля рядов длины два равна $1/{2!}$, на первом месте могут быть любые три числа, но вариантов когда они по возрастанию 1 из 3!, то есть доля - $1/{3!}$, и так далее аналагично. Теперь доля чистых рядов разномерности 2 будет $1/{2!}-1/{3!}$, все которые не входят в последовательности длины 3, для 3-х эта доля $1/{3!}-1/{4!}$, долее аналагично. Это что касается если брать первые ряды в последовательности, теперь надо понять что будет при циклическом смещении.