Анализ бинарной последовательности

[zlon]

Добрый день,
Помогите, пожалуйста с решением задачи:
Есть последовательность типа: 0000001101101100000011011011000000
мне нужно ответить на несколько вопросов:
1) Насколько данная последовательность случайна? То есть оценивая из данных вероятность выпадения 1 как 12/34 насколько вероятно получить столь упорядоченную последовательность?
2) Если последовательность неслучайна, то существуют ли "островки плотности" единиц?
3) Глазами я вижу что есть периоды когда сигнал чаще меняется, но как их выделить?
4) Нельзя ли выделить высокочастотную и низкочастотную гармоники в этом сигнале?
------
P.S.
У меня "базовый" математический уровень. Я только начинаю вникать в эту проблему. По пункту 1 я думаю использовать хи квадрат (не уверен, что это верный подход). Пункт 2 и 3 вообще не представляю с какого конца за них браться. Пункт 4 пробовал fft, но так и не понял ресультата анализа :(
------
P.P.S
Прошу прощения если это совсем глупые вопросы и буду благодарен за ответы типа "читай ...... для чайников"

[svv]

Ваша последовательность состоит из чередующихся $000000$ и $11011011$. Это случайно или нет?

[patzer2097]

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

zlon в сообщении #820650 писал(а):

Насколько данная последовательность случайна?

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

[zlon]

svv в сообщении #820715 писал(а):

Ваша последовательность состоит из чередующихся $000000$ и $11011011$. Это случайно или нет?

Нет, не случайно, я ее специально для примера придумал. Мои длиннее (порядка 1000 символов) Но в них также видна закономерность, что есть периоды с частыми чередованиями 0 и 1, а есть относительно "пустые периоды" из нулей

-- 30.01.2014, 18:06 --

patzer2097 в сообщении #820726 писал(а):

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

может быть придан точный смысл, о котором можно прочесть тут. В частности, конкретную последовательность иногда называют случайной по Колмогорову, если эта последовательность короче, чем описание любой программы, ее генерирующей. [/quote]
Я имел в виду, что "интуитивно" 11110000 более упорядочена чем 10101010. Но как эту упорядоченность измерить?
В конкретном примере, понятно, что если я разобю последовательность на 2 блока и посчитаю хи-квадрат, то у меня будет достоверное отличие. Но что делать если я не знаю на сколько блоков бить последовательность

Спасибо за ссылку, почитаю.

[svv]

patzer2097 в сообщении #820726 писал(а):

конкретную последовательность иногда называют случайной по Колмогорову, если эта последовательность короче, чем описание любой программы, ее генерирующей

Допустим, вероятность выпадения единицы порядка $0.1$. Тогда последовательность из $1000$ символов можно описать, указав, что нули везде, кроме единиц на таких-то позициях. И, получается, такая последовательность случайной по Колмогорову не будет.

-- Чт янв 30, 2014 16:18:35 --

zlon в сообщении #820730 писал(а):

Я имел в виду, что "интуитивно" 11110000 более упорядочена чем 10101010. Но как эту упорядоченность измерить?

Для моей интуиции — совсем наоборот, $10101010$ упорядоченней.

Кстати, если для последовательности существует функция, дающая $n$-й элемент в зависимости от $k$ предыдущих, то $k$ и может быть такой мерой. В случае $10101010$ имеем просто: $a_{n}=\bar{a}_{n-1}$.

[patzer2097]

svv в сообщении #820736 писал(а):

Допустим, вероятность выпадения единицы порядка $0.1$. Тогда последовательность из $1000$ символов можно описать, указав, что нули везде, кроме единиц на таких-то позициях. И, получается, такая последовательность случайной по Колмогорову не будет.

ага обобщая Ваше утверждение, я бы сказал, что
любая последовательность из $N$ элементов, содержащая $o\left(\frac{N}{\ln N}\right)$ единиц, не будет случайной в этом смысле

UPD. Так как для указания номера элемента достаточно $O(\ln N)$ ресурсов.

[zlon]

Извините, я, видимо, неправильно с формулировал вопрос. Подобные данные получаются из эксперимента. Не вдаваясь в подробности его можно представить так:
Есть мигающая лапмочка. Каждую секунду я записываю горит она или нет. Вероятность горит или нет я априори не знаю но могу оценить из эксперимента.
1) Мне нужно понять я вижу просто шум или какую-то информацию.
2) Я вижу, что есть периоды когда лампочка мигает часто а есть периоды когда она мигает редко, вопрос как это "я вижу" обосновать
3) Если верно наблюдение, что лампочка мигает с разными частотами, то охарактеризовать эти частоты

[svv]

Попробуйте «продифференцировать» Вашу последовательность $(a_n)$. Постройте другую последовательность $(b_n)$, где $b_n$ равно
$0$, если $a_n=a_{n-1}$ (состояние лампы не изменилось), и
$1$, если $a_n\neq a_{n-1}$ (состояние лампы изменилось).

Теперь подсчитайте частоту единиц на участке фиксированной длины $k$ (как функцию позиции $n$ начального элемента):
$p_n=\frac 1 k{\sum\limits_{i=0}^{k-1}}b_{n+i}$
Эта частота единиц будет тем больше, чем чаще лампа мигает.
Надо только удачно выбрать «ширину окна» $k$.

[AV_77]

http://csrc.nist.gov/publications/nistp ... 2rev1a.pdf

[nikvic]

Можно построить бинарное дерево частот. Корень - пустое слово, 100%. Каждая вершина-слово порождает "детей", равных родителю плюс нолик или единичка, их веса - условные частоты.
Такая схема используется для сжатия. Вершина "бездетна", если вес мал.

[B@R5uk]

zlon в сообщении #820755 писал(а):

Есть мигающая лапмочка.

zlon в сообщении #820755 писал(а):

Мне нужно понять я вижу просто шум или какую-то информацию.

А у вас есть какая-то модель системы, которая управляет тем, горит лампочка или нет? Если да, то надо просто определить параметры модели по экспериментальным данным. Или же вам совершенно ничего не известно и необходимо эту модель придумать в хоть каком-то адекватном виде?

AV_77 в сообщении #820816 писал(а):

http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf

Думаю, что это ну очень круто для данного случая. Автору надо начинать сначала хотя бы с автокорреляционной функции.

zlon в сообщении #820650 писал(а):

Пункт 4 пробовал fft, но так и не понял результата анализа :(

В какой программе вы пробовали fft? И что именно не понятно в результатах?

[zlon]

Спасибо за ценные советы.
Вот так выглядит мой сигнал (х):
http://i.imgur.com/urHb6Tj.jpg
На первый взгляд он не периодичен.
В Матлабе написал:
plot(abs(fft(x)))
Получил такую диаграмму- надеялся увидеть 2 пика, вижу только 1 и то не понимаю до конца что это значит
http://i.imgur.com/3i4MvwI.jpg
А вот автокорреляция код: plot(xcorr(x))
Результат:
http://i.imgur.com/vQA0S0U.jpg
Очевидно есть периодичность.
Делаю фурье трансформацию
http://i.imgur.com/hqr6pBz.jpg
и опять ничего не понимаю:(

[svv]

zlon
А Вы можете мне дать эту последовательность в цифровом виде?

[zlon]

У меня их много :). Могу дать, конечно, только не понимаю как- через личку?
В каком формате?

[svv]

Берется Ваша последовательность $(a_n)$.
По ней строится $(b_n)$, в которой единицы соответствуют изменениям сигнала.

Дальше строится последовательность (красная линия), элементы которой равны разности позиций двух соседних единиц $(b_n)$. Эти элементы, следовательно, тем больше, чем реже меняется исходный сигнал.

Синяя линия — сглаженная красная.

Видно, что действительно чередуются периоды более частой и более редкой смены состояний сигнала.