про математику: мера упорядоченности

 

если имеем более чем достаточный бинарный ряд (0/1 или buy/sell, кол-во 0 равно числу 1) то

вопросы:

№1: возможно ли её более-менее быстро оценить "степень упорядоченности" ряда или фрагмента,иначе чем префиксной компрессией по Шенону/Хафману или подсчёта минимального числа перестановок. 

№2: алгоритм/функция генерации рядов с такой заданной степенью порядка. 

поясню: например берём очень длинный ряд из 0,1 и считаем что строго чередующийся ряд то это порядок 0. А если числа сделаны равномерным Random() то 1. Круче равномерного перемешать нельзя никак, а вот меньше можно. 

 

А у таких последовательностей какой порядок?

00000000000000000000000000011111111111111111111111

0011001100110011001100110011001100110011001100110011

01001100011100001111000001111100000011111100000001111111

Все они явно плохо перемешаны, но весьма различаются.

 
Aleksey Nikolayev:

А у таких последовательностей какой порядок?

00000000000000000000000000011111111111111111111111

0011001100110011001100110011001100110011001100110011

01001100011100001111000001111100000011111100000001111111

Все они явно плохо перемешаны, но весьма различаются.

а если циклически сдвинуть Ваши последовательности.... это будут другие последовательности? 

00000000000000111111111111111111111110000000000000

;)

 
Maxim Kuznetsov:

если имеем более чем достаточный бинарный ряд (0/1 или buy/sell, кол-во 0 равно числу 1) то

вопросы:

№1: возможно ли её более-менее быстро оценить "степень упорядоченности" ряда или фрагмента,иначе чем префиксной компрессией по Шенону/Хафману или подсчёта минимального числа перестановок. 

№2: алгоритм/функция генерации рядов с такой заданной степенью порядка. 

поясню: например берём очень длинный ряд из 0,1 и считаем что строго чередующийся ряд то это порядок 0. А если числа сделаны равномерным Random() то 1. Круче равномерного перемешать нельзя никак, а вот меньше можно. 

сам себя спросил, сам себе ответил :-)

в постановке задачи, перестановки влекут парные битовые инверсии, поэтому "дистанция в перестановках от чередующего ряда" будет от 0 (ряд тоже строго-чередующийся) до N/2 (все еденицы(нули) справа).

И сдаётся белый шум (или вообще среднее расстояние) получается где-то sqrt(N) (тут возможно ошибаюсь).

 
Вопрос по сути, не поставлен. Во всяком случае, поставлен нечетко. 

Как я понял задачу: есть некая бинарная последовательность, упорядоченность которой нужно оценить. Есть некий известный метод, но автор спрашивает есть ли другой способ оценки.

Отвечаю, - есть. Любая последовательность может быть полным порядком, частичным порядком или вовсе хаосом. Все зависит от взгляда человека. Потому, оценка упорядоченности должна отталкиватся от заданного порядка с которым последовательность сравнивается. 

Если речь о степени перемешанности, то это другой вопрос.
 
Реter Konow:
Вопрос по сути, не поставлен. Во всяком случае, поставлен нечетко. 

Как я понял задачу: есть некая бинарная последовательность, упорядоченность которой нужно оценить. Есть некий известный метод, но автор спрашивает есть ли другой способ оценки.

Ямб, хорей и другие стихотворные размеры (рифмы).  ))

Арифметрика (арифметрия), другими словами.  ))
 

Специально для публицистов в любой теме:

Имеем некую последовательность X длинной N битов , кол-во 0 и 1 равно N/2 (то есть N строго чётное).

Сколько (произвольно)бит надо поменять местами, чтобы получить чередующийся ряд 0,1,0.. (или 1,0,1, к которому ближе) ?

Как оценить  конкретной X и в сколько вообще в среднем для длины N...

 
Maxim Kuznetsov:

Специально для публицистов в любой теме:

Имеем некую последовательность X длинной N битов , кол-во 0 и 1 равно N/2 (то есть N строго чётное).

Сколько (произвольно)бит надо поменять местами, чтобы получить чередующийся ряд 0,1,0.. (или 1,0,1, к которому ближе) ?

Как оценить  конкретной X и в сколько вообще в среднем для длины N...

Очевидно, смотрим чего больше на нечётных номерах. Пусть это будут нули, тогда меняем нули на чётных местах с единицами на нечётных местах. Максимально получится N/4 перестановок (когда N делится на 4) - в этом случае половина нулей на чётных местах, а половина на нечётных, например 00110011. Минимально - ноль, а для вычисления среднего нужны дополнительные предположения.

 
Aleksey Nikolayev:

Очевидно, смотрим чего больше на нечётных номерах. Пусть это будут нули, тогда меняем нули на чётных местах с единицами на нечётных местах. Максимально получится N/4 перестановок (когда N делится на 4) - в этом случае половина нулей на чётных местах, а половина на нечётных, например 00110011

это максимальная оценка. Как правильно оценить среднее число перестановок, я честно плаваю, иначе бы не спросил 

представляется что тесно связано с числом серий 0 и 1 от любимого СБ, и коэфф. С(2,N)

где-то порядка sqrt(N) но могу попасть пальцем в небо

 
Maxim Kuznetsov:

это максимальная оценка. Как правильно оценить среднее число перестановок, я честно плаваю, иначе бы не спросил 

представляется что тесно связано с числом серий 0 и 1 от любимого СБ, и коэфф. С(2,N)

где-то порядка sqrt(N) но могу попасть пальцем в небо

На первый взгляд, будет что-то вроде среднего от |N/2-2*n|, где n - наименьшее из числа нулей и единиц выпавших в серии длиной N/2. То есть, можно считать просто по нечётным броскам. Корень из N вроде бы должен получиться.

PS Возможно ошибаюсь и считать надо через гипергеометрическое распределение, а не биномиальное.

 
Maxim Kuznetsov:

если имеем более чем достаточный бинарный ряд (0/1 или buy/sell, кол-во 0 равно числу 1) то

вопросы:

№1: возможно ли её более-менее быстро оценить "степень упорядоченности" ряда или фрагмента,иначе чем префиксной компрессией по Шенону/Хафману или подсчёта минимального числа перестановок. 

№2: алгоритм/функция генерации рядов с такой заданной степенью порядка. 

поясню: например берём очень длинный ряд из 0,1 и считаем что строго чередующийся ряд то это порядок 0. А если числа сделаны равномерным Random() то 1. Круче равномерного перемешать нельзя никак, а вот меньше можно. 

Бинарный ряд действий трейдера (buy/sell), или ещё чего-нибудь? Я в экстазе, если честно,- мои реакции на движения рынка предлагают смоделировать статистически, исходя из предположения об их хаотичности.