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

[Scholium]

maxal в сообщении #251636 писал(а):

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

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)!}.$$

Спасибо огромное за большую работу! Только, к сожалению, вопросы остаются. Я подсчитал некоторые значения по Вашей последней формуле при $1<k<n$:
$Q_n(k) = 2\frac{n!(-k^3 + nk^2 + (n + 2)k + n - 1)}{(k+2)!}.$
Вот что я получил:
$Q_3(2) = 8$;
$Q_4(2) = 46$; $Q_4(3) = 12$;
К сожалению, эти значения не соответствуют действительности. Возможно, я просто не очень удачно сформулировал условие задачи. Проще, наверное, показать, как я считал.
При n = 2 имеем последовательности: 12 и 21, т.е. две УПП (упорядоченные подпоследовательности) длины два на множестве всех перестановок длины 2. Аналогично, для n = 3 получаем следующие УПП (которые разделены точкой):
123
13.2
21.3
23.1
31.2
321 .
Т.е. здесь мы имеем:
Мы видим, что здесь «единиц» – четыре, «двоек» – четыре, «троек» – 2 (всего УПП: $q_3 = 10$), т.е.
$Q_3(1) = 4$ (УПП: 2, 3, 1 и 2); $Q_3(2) = 4$ (УПП: 13, 21, 23 и 31); $Q_3(3) = 2$ (УПП: 123 и 321);
Аналогично, для n = 4:
1234
124.3
13.24
134.2
14.23
14.32
21.34
21.43
23.14
234.1
24.13
24.31
31.24
31.42
321.4
32.41
34.12
34.21
41.23
41.32
421.3
42.31
431.2
4321 .
Мы видим, что здесь «единиц» – шесть, «двоек» – 32, «троек» – 6 и «четверок» – 2 (всего УПП: $q_4 = 46$), т.е. $Q_4(1) = 6$; $Q_4(2) = 32$; $Q_4(3) = 6$; $Q_4(4) = 2$;

Именно вот это я имею в виду при подсчете распределения УПП. Вполне могу согласится с критикой, что для других это было не очевидно, так что приношу свои запоздалые извинения .

maxal в сообщении #251636 писал(а):

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

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

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

Думаю, что предыдущий параграф текста, должен говорить о том, что «зависшие» УПП длины 1 отнюдь не искусственное ограничение, а естественное условие распределения порядка .

-- Ср окт 14, 2009 19:40:11 --

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

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

Похоже, что это уже «теплее» , постепенно мы начнем думать одинаково . Но чтобы говорить более предметно, давайте зададимся вопросом средняя длина УПП равна 2е – 3? У меня это доказано нестрого, но соответствует экспериментальным данным.

[maxal]

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

Вот что я получил:
$Q_3(2) = 8$;
$Q_4(2) = 46$; $Q_4(3) = 12$;
К сожалению, эти значения не соответствуют действительности. Возможно, я просто не очень удачно сформулировал условие задачи. Проще, наверное, показать, как я считал.
При n = 2 имеем последовательности: 12 и 21, т.е. две УПП (упорядоченные подпоследовательности) длины два на множестве всех перестановок длины 2. Аналогично, для n = 3 получаем следующие УПП (которые разделены точкой):
123
13.2
21.3
23.1
31.2
321 .

В 132 вообще говоря два максимальных отрезка монотонности длины 2: 13 и 32, и 213 тоже два: 21 и 13 и т.д. - всего их получается именно $Q_3(2)=8.$

Впрочем, несложно модифицировать мою формулу, чтобы получить аналогичную для количества отрезков монотонности в вашем понимании. Количество подъёмов длины $\ell$ равно случай 1) для $k=\ell$ плюс случай 1) для $k=\ell+1$ плюс случай 2) для $k=\ell+1$. Для спусков аналогично. Формулу предлагаю вывести самостоятельно.

[Scholium]

maxal в сообщении #251703 писал(а):

В 132 вообще говоря два максимальных отрезка монотонности длины 2: 13 и 32, и 213 тоже два: 21 и 13 и т.д. - всего их получается именно $Q_3(2)=8.$

Ну, в условии задачи написано: «Подпоследовательности рассматриваются до тех пор, пока сохраняется их локальный порядок и не пересекаются между собой». А реально это нужно для слияния двух непересекающихся последовательных отрезков монотонности в один при сортировке естественным слиянием (см. мою тему в http://sql.ru/forum/actualthread.aspx?bid=24&tid=686605&pg=2 ). Понятно, что при слиянии 21 и 13 получим 1123, что не есть хорошо. Использование существующего естественного порядка в случайных последовательностях позволяет слегка увеличить производительность лучших алгоритмов сортировки. А практически в таких алгоритмах почти достигнут предел их эффективности. Так что есть шанс внести свою лепту в установку «мировых рекордов» для сортировки чисел .

maxal в сообщении #251703 писал(а):

Впрочем, несложно модифицировать мою формулу, чтобы получить аналогичную для количества отрезков монотонности в вашем понимании. Количество подъёмов длины $\ell$ равно случай 1) для $k=\ell$ плюс случай 1) для $k=\ell+1$ плюс случай 2) для $k=\ell+1$. Для спусков аналогично. Формулу предлагаю вывести самостоятельно.

Я как раз этим и занимаюсь . Думаю, что формулы должны получится достаточно красивыми и элегантными, типа как у гипергеометрического распределения. Поэтому тот, кто сумеет сделать это первым, может претендовать на право, чтобы это естественное распределение порядка в случайных последовательностях называлось его именем . Если конечно, такие формулы еще не открыты кем-то ранее . Уже несколько человек в данной теме достаточно близко подошли к их формулировке. Но поскольку, ни у кого нет достаточно строгого доказательства их вывода и соответствия реальным данным для малых n и k, то шанс стать «первооткрывателем» сохраняется у каждого .

[nn910]

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

Точно в указанной постановке обозначим $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)=\dfrac{(1-x)^{m-1}}{(m-1)!}-\dfrac{(1-x)^{m}}{m!}$
Вроде так

Давно должен был исправить,но вчера сеть не работала$M(x)= \sum_{m+k \geq3}(m+k-1)P_m(1-x)P_k(x)=e^{1-x}+ e^x-1$
$M=2e-3$
Дискретная постановка отличается от непрерывной двумя бесконечно убывающими поправками :1)положительная зависимость вероятности наличия продолжения последовательности от набранной длины(запрещены некоторые значения,обрывающие последовательность); 2)интегрирование (=взятие суммы) ступенчатого приближения степенной функции всегда уменьшает интеграл .Первая увеличивает матожидание (>$2e-3$), вторая уменьшает.Но обе стремятся к 0.
PS.Насчет имени,надеюсь ,не всерьез? Кажется Карнеги сформулировал рекомендацию сенаторам "называть законопроект длинно и неудобочитаемо, тогда при обсуждении ДРУГИЕ сенаторы будут называть его Вашим именем."Здесь важно слово "другие"

[Scholium]

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

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

Точно в указанной постановке обозначим $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)=\dfrac{(1-x)^{m-1}}{(m-1)!}-\dfrac{(1-x)^{m}}{m!}$
Вроде так

Давно должен был исправить,но вчера сеть не работала$M(x)= \sum_{m+k \geq3}(m+k-1)P_m(1-x)P_k(x)=e^{1-x}+ e^x-1$
$M=2e-3$
Дискретная постановка отличается от непрерывной двумя бесконечно убывающими поправками :1)положительная зависимость вероятности наличия продолжения последовательности от набранной длины(запрещены некоторые значения,обрывающие последовательность); 2)интегрирование (=взятие суммы) ступенчатого приближения степенной функции всегда уменьшает интеграл .Первая увеличивает матожидание (>$2e-3$), вторая уменьшает.Но обе стремятся к 0.

Круто! Это уже очень неплохие результаты! Формулы для матожидания (средней длины УПП – L) очень правдоподобны, тем более, что результат для $L = 2e - 3$ у меня был уже получен здесь путем нестрогого доказательства (сообщения от «Ср окт 14, 2009 13:57:36» и «Ср окт 14, 2009 15:38:43») и, кроме того, это значение соответствует экспериментальному. Соответственно Ваша формула: $M(x) = e^{1-x}+ e^x-1$ также похожа на истинную. Ее интеграл на отрезке [0, 1] действительно равен $L = 2e - 3$, но ее физический смысл я улавливаю слабо. Если $L(x) \equiv M(x)$ это средняя длина УПП для последовательности, равномерно распределенной случайной величины на промежутке $(0, 1) \cap [x, 1)$, тогда $L(0) = e$ как средняя длина УПП на всем интервале (0, 1), не соответствует найденному $L = 2e - 3$. Может быть, это плотность распределения средних длин? Тогда вроде все сходится .

Далее, рассмотрим Вашу формулу (в которой я для соответствия своим обозначениям изменил m на k):
$P_k(x) = \dfrac{(1-x)^{k-1}}{(k-1)!} - \dfrac{(1-x)^{k}}{k!}$. Отсюда следует, что
$P_k(0) = \dfrac{k-1}{k!}$ и что $P_2(0) = \dfrac{1}{2}$ и $P_3(0) = \dfrac{1}{3}$, что также очень похоже на истину! Осталось найти формулы для $Q_n(k)$ из условия задачи (для дискретного и непрерывного (ассимтотического) случаев). Думаю, что из этих Ваших формул это вполне можно будет сделать. Таким образом, похоже, Ваши результаты наиболее правдоподобны!

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

PS.Насчет имени,надеюсь ,не всерьез? Кажется Карнеги сформулировал рекомендацию сенаторам "называть законопроект длинно и неудобочитаемо, тогда при обсуждении ДРУГИЕ сенаторы будут называть его Вашим именем."Здесь важно слово "другие"

Карнеги – умница, если такое сформулировал. Только наши бюрократы придумали контр довод, чтобы его рекомендация не выполнялась. Они любые законы просто нумеруют и ставят дату и по ним ссылаются. В крайнем случае, могут добавить первые два три слова из его названия и поставить троеточие. Так что, в наших странах это не сильно работает . Но насчет имени я вполне серьезен. Главное оформить все в виде какой-нибудь статьи, опубликовать официально в Интернете или на бумаге, найти пару применений данного распределения, например, при оптимизации сортировки и все – официально Вы первооткрыватель (при условии, что это не было известно ранее). А мы можем в своих статьях официально писать «распределение nn910», если назовете реальное имя, то будем ссылаться по имени . Кстати, возможно формулы maxal’a (см. сообщение от «Ср окт 14, 2009 16:57:43» и далее), после некоторой адаптации могут претендовать на описание дискретного варианта.

[nn910]

Scholium
М(х)-это условное матожидание длины последовательности при условии что она где-то содержит число х, другого физического смысла не вижу,но считать через $P_k(x)$ удобно.
Пусть $q_n (k)=\dfrac{Q_n (k)}{n!}$
$q_{\infty}(k)=\sum_{m+i=k+1}\int_0^1 P_m(x)P_i(1-x)dx$ ,откуда по определению В и Г-функций получаем
$q_{\infty}(k)=k( \dfrac{1}{k!}+\dfrac{1}{(k+2)!}-\dfrac{2}{(k+1)!})=\dfrac{k(k^2+k-1)}{(k+2)!}$ сильно напоминает формулы maxal'a в пределе по n
В частности,$q_{\infty}(2)=\dfrac{5}{12}$

[Scholium]

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

Scholium
М(х)-это условное матожидание длины последовательности при условии что она где-то содержит число х, другого физического смысла не вижу,но считать через $P_k(x)$ удобно.
Пусть $q_n (k)=\dfrac{Q_n (k)}{n!}$
$q_{\infty}(k)=\sum_{m+i=k+1}\int_0^1 P_m(x)P_i(1-x)dx$ ,откуда по определению В и Г-функций получаем
$q_{\infty}(k)=k( \dfrac{1}{k!}+\dfrac{1}{(k+2)!}-\dfrac{2}{(k+1)!})=\dfrac{k(k^2+k-1)}{(k+2)!}$ сильно напоминает формулы maxal'a в пределе по n
В частности,$q_{\infty}(2)=\dfrac{5}{12}$

Вы вместе с maxal'ом молодцы! Результаты получаете быстрее, чем я успеваю их переваривать . Практически, поставленная задача в принципиальном плане, можно сказать, решена. По крайней мере, концептуально. Т.е. лично мне ваших идей вполне достаточно, для работы в этом направлении. Проблема только в том, что математикой я уже не занимался много лет, поэтому немного «торможу» . Думаю, было бы неплохо, если бы вы развили ваши мысли до уровня статьи. Во всех учебниках по теории вероятности пишут про распределения Бернулли и гипергеометрическое распределение и про их асимптотику. Мне почему-то кажется, что это распределение должно стоять там рядом. Главное привести достаточное количество примеров его использования. Про возможность улучшения известных алгоритмов сортировки я уже говорил. Далее, сам факт наличия порядка в случайных последовательностях теоретически может иметь физический и философский смысл. Возможно прикладное применение для оценки меры случайности произвольной информации. Наверное, можно поискать и другие применения.

То, что Ваш M(x) можно еще считать плотностью распределения средних длин УПП на промежутке [x, 1), мне не кажется противоречивым, но со временем это можно будет проверить.