Распеределение суммы расстояний

[Cat]

Возникла такая проблема. Расмотрим $S$ сумму разностей между смежными элементами перестановки. То есть, для перестановки из 3 элементов $ \{1,2,3\}$, $S=|1-2|+|2-3|=2$, для перестановки $\{1,2,3,4\}$, $S=3$ и т.п. Возможно ли для общего случая всех возможных перестановок из $N$ элементов составить функцию распределения $S$?

[Sonic86]

Ну смотрите: когда $N=2$, тогда $S=2$, когда $N=3$, тогда $S=3$, когда $N=4$, тогда $S=?$.

[gris]

Я так понял, что $S$ считается для всех $n!$ перестановок. Два раза оно будет принимать минимальное значение $S_{\min}(n)=n-1$, два или четыре (?) раза максимальное значение, которое равно, например, $S_{\max}(3)=3, S_{\max}(4)=7, S_{\max}(5)=11$. Нетрудно его посчитать, оно ещё от чётности зависит.
Если все перестановки записать в лексикографическом порядке, то $S$ будет симметрично, то есть каждое значение будет принимать чётное число раз. Вот всё
Вообще, очень интересная характеристика перестановки. Наверняка это известно специалистам.
Кстати, я последовательность максимальных значений ввёл в OEIS, и там что-то про перестановки было. Возможно, что близкое по смыслу

[Cat]

Спасибо за ответы. Конечно я пробовала вычислить распределение для разных значений числа $N$. Но не удается понять закономерность для $S$ в середине распределения. Как отметил gris, $S_{\min(N)}=N-1$ и такое значение $S$ будет принимать два раза, в случае, когда числа в перестановке расположены по убыванию или возрастанию. Далее, если за исходную перестановку взять $(1,2,3, ..., N)$, то путем перестановки первых двух чисел или последних двух, получим $S=N$, что можно сделать и с обратной перестановкой $(N,N-1,N-2, ...,1)$. Таким образом, число случаев, когда $S=N -4$. А вот с максимальным значением не все так просто. Для $N=3..9$ последовательность случаев, когда S принимает максимальное значение, такова: $(4,2,8,8,48,72,96)$.

Здесь http://dl.dropbox.com/u/17459017/9.xlsx расчитанные распределения для N от 3 до 9.

Спасибо большое за упоминание OEIS. Действительно максимальные значения выводятся по формуле $floor(n^2/2-1)$.

[Руст]

Из приведенного не ясно, что вы считаете. Мне кажется вы хотели посчитать $S=\sum_{i=1}^n |\sigma(i)-i|$. Тогда для тождественной перестановки $S=0$. И максимальное расстояние в этом случае $[\frac{n^2-1}{2}]$.
Такого рода нормы, характеризующие отдаленность от тождественной в практике встречаются часто. Распределение должно выйти к нормальному при больших $n$.

[Cat]

Руст в сообщении #686870 писал(а):

Из приведенного не ясно, что вы считаете. Мне кажется вы хотели посчитать $S=\sum_{i=1}^n |\sigma(i)-i|$. Тогда для тождественной перестановки $S=0$. И максимальное расстояние в этом случае $[\frac{n^2-1}{2}]$.

Я считаю $S=\sum_{i=1}^{n-1} |\sigma(i+1)-\sigma(i)|$, т.е сумму расстояний между смежными элементами перестановки. Минимальное значение, которое принимает $S$ это $n-1$.

[Руст]

Но такая величина не является нормой, не удовлетворяет неравенству треугольника:
$S(\sigma_1(\sigma_2))\le S(\sigma_1)+S(\sigma_2)$.
Использование таких расстояний не целесообразно.

[Cat]

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

[Sonic86]

связка
Пока сильно не думал, но пробовали ли Вы считать матожидание и дисперсию $S(\sigma)$?
upd: матожидание у меня получилось $\frac{n^2-1}{3}$. Значит распределение скошено вправо (значит оно не нормальное).

[Cat]

Sonic86 в сообщении #687059 писал(а):

связка
Пока сильно не думал, но пробовали ли Вы считать матожидание и дисперсию $S(\sigma)$?
upd: матожидание у меня получилось $\frac{n^2-1}{3}$. Значит распределение скошено вправо (значит оно не нормальное).

Поясните, пожалуйста, как вы вывели мат. ожидание?

[Sonic86]

Cat в сообщении #687161 писал(а):

Поясните, пожалуйста, как вы вывели мат. ожидание?

Там по ссылке написано, как его считать. Можете выразить $M(S_n(\sigma))$ через $N(\sigma\in S_n:|\sigma(k)-k|=d)$ - число перестановок $\sigma$ таких, что $|\sigma(k)-k|=d$, а потом просуммировать по $k,d$. Можете выписать матожидание целиком, изменить порядок суммирования и во внутренней сумме сгруппировать слагаемые по величине (кажется, это одно и то же даже).

(Оффтоп)

Я вчера вспомнил, я такую задачу пытался когда-то решать. Но вычислить распределение тогда у меня не получилось даже рекуррентно, сейчас я понял почему - там модули "редуцируют информацию о знаке".
Насчет формы распределения - может быть оно все же нормальное, только усеченное справа.

[ex-math]

Sonic86
ТС нужна совсем другая $S(\sigma)$

[Sonic86]

ex-math в сообщении #687224 писал(а):

ТС нужна совсем другая $S(\sigma)$

Ой, прошу прощенья, действительно.