2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Распределение порядка во всех перестановках
Сообщение14.10.2009, 18:13 


13/10/09
283
Ukraine
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? У меня это доказано нестрого, но соответствует экспериментальным данным.

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение14.10.2009, 19:41 
Модератор
Аватара пользователя


11/01/06
5660
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$. Для спусков аналогично. Формулу предлагаю вывести самостоятельно.

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение15.10.2009, 07:11 


13/10/09
283
Ukraine
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, то шанс стать «первооткрывателем» сохраняется у каждого :) .

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение15.10.2009, 08:57 


25/05/09
231
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!}$
Вроде так
Давно должен был исправить,но вчера :oops: сеть не работала$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.Насчет имени,надеюсь ,не всерьез? Кажется Карнеги сформулировал рекомендацию сенаторам "называть законопроект длинно и неудобочитаемо, тогда при обсуждении ДРУГИЕ сенаторы будут называть его Вашим именем."Здесь важно слово "другие"

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение15.10.2009, 11:13 


13/10/09
283
Ukraine
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!}$
Вроде так
Давно должен был исправить,но вчера :oops: сеть не работала$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» и далее), после некоторой адаптации могут претендовать на описание дискретного варианта.

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение15.10.2009, 14:19 


25/05/09
231
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}$

 Профиль  
                  
 
 Re: Распределение порядка во всех перестановках
Сообщение15.10.2009, 18:33 


13/10/09
283
Ukraine
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), мне не кажется противоречивым, но со временем это можно будет проверить.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group