Вероятность встретить заданную последовательность байт

[wallflower]

Предположим, я ищу в потоке данных (бесконечная последовательность байт $(d_1,d_2,...)$ -- целых чисел от $0$ до $255$) некоторую (произвольно) заданную конечную последовательность байт $a=(a_1,...,a_n)$. Какова вероятность, что я найду данную последовательность на отрезке $(d_1,...,d_m)$, $m>n$?

(Приземлённое описание)

Пусть мы читаем большой файл. Предположим, что я ищу в нём строку "Привет, землянин!". Исходный файл может содержать случайные данные, поэтому фраза "Привет, землянин!" может просто случайно сложиться (даже обезьяна может написать "Гамлета", играя с печатной машинкой). А может -- это "реальное" сообщение, вставленное в файл. Ясно, что если я найду в произвольной последовательности байт сообщение "Привет, землянин" в первых 100 байтах, то вероятность "реальности" его больше, чем если бы я прочитал эксабайт.
Мне нужно как-то оценить вероятность "реальности" сообщения, если я его встретил на $k$-ой позиции читаемого потока данных.

В математике не силён и у меня получилось $1-(1-(1/256)^n)^{m-n+1}$, что не сильно похоже на правду. Прошу дать указания и пинком задать направление полёта к решению.

[svv]

Боюсь, что вероятность найти заданную последовательность $a=(a_1,...,a_n)$ на отрезке $[1, m]$ зависит не только от $m$ и $n$, но и от самих значений $a_1,...,a_n$.

Рассмотрим упрощённый пример. Пусть алфавит состоит из символов $0$ и $1$, и Вы изучаете первые четыре символа потока. Всего они могут принимать $16$ разных комбинаций значений. Считаем, что все комбинации равновероятны.

Если послание от братьев по разуму выглядит как $00$, Вы найдёте такое в восьми комбинациях из $16$:
$0000, 0001, 0010, 0011, 0100, 1000, 1001, 1100$

Но последовательность $01$ Вы встретите уже в одиннадцати комбинациях:
$0001, 0010, 0011, 0100, 0101, 0110, 0111, 1001, 1010, 1011, 1101$

Честно говоря, пока совершенно не понимаю, почему так получается, то есть каков механизм того, что одни последовательности более вероятны, чем другие той же длины. (Ну, и какие именно более вероятны, а какие -- менее).

[Casaubon]

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

Честно говоря, пока совершенно не понимаю, почему так получается, то есть каков механизм того, что одни последовательности более вероятны, чем другие той же длины. (Ну, и какие именно более вероятны, а какие -- менее).

Этот парадокс, вместе с некоторым объяснением, есть в Секей Г. "Парадоксы в теории вероятностей и мат. статистике" -- "парадоксы, связанные с бросанием монеты". Там и более длинные серии, которые мы ловим, есть, это ещё интереснее.

[wallflower]

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

Боюсь, что вероятность найти заданную последовательность $a=(a_1,...,a_n)$ на отрезке $[1, m]$ зависит не только от $m$ и $n$, но и от самих значений $a_1,...,a_n$.

А нельзя как-то "усреднить" это? Ведь последовательность, которую мы ищём, произвольна, заранее не известна и не фиксирована (можно в качестве неё взять случайную последовательность из $n$ байт). Да и мне интуитивно кажется, что в случае большого алфавита типа $\{0,...,255\}$ различие в вероятностях встретить различные последовательности уменьшается (строго объяснить это не могу; а, возможно, это и не верно).

-- 25.12.2011, 09:34 --

(Другой приземлённый пример)

Пусть имеется большой файл, в который, возможно, вставили RAR-архив. Как известно, RAR-архивы имеют вначале сигнатуру "Rar!". Наша задача -- найти архив в файле и оценить правдоводобность находки (ведь последовательность "Rar!" может и случайно сложиться, если файл очень большой).

Пусть мы нашли сигнатуру, прочитав 10 МБайт файла. Насколько правдоподобна наша находка?

[Joker_vD]

wallflower в сообщении #519310 писал(а):

Ясно, что если я найду в произвольной последовательности байт сообщение "Привет, землянин" в первых 100 байтах, то вероятность "реальности" его больше, чем если бы я прочитал эксабайт.

Но почему? Представьте себе, что в ваш файл идет поток данных с приемника. После того, как вы записали эксабайт шума (20 лет с момента старта записи), инопланетяне решили наконец выйти с вами на связь и отправили приветствие. Так что тут наоборот — было бы крайне подозрительно, если бы они отправили сообщение так, что оно пришло бы в первые же секунды после включения вами приемника.

Так что "вероятность "реальности" сообщения, если я его встретил на $k$-ой позиции читаемого потока данных" в общем случае от $k$ не зависит.

[wallflower]

Joker_vD
Не-не, про инопланетян был плохой пример, я уже понял и сам. Про архив пример лучше. А ещё лучше ориентироваться на первый абзац в первом сообщении.

-- 25.12.2011, 12:28 --

Может быть как-то можно свести к задаче о бросаниях. Пусть мы бросаем "кубик", который может принимать 256 различных значений. Какое среднее число бросков нужно сделать, чтобы получить некоторую заданную (но произвольно заданную) последовательность значений длины $n$?

[Joker_vD]

Ну все зависит от самой последовательности $d_n$ — может, она состоит из случайных независимых величин, а может — из неслучайных зависимых.

[wallflower]

Joker_vD
$d_n$ -- случайная последовательность с равномерным распределением.

$a_n$ тоже выбирается случайно, с равной вероятностью выбора любого байта в любом месте. Длина этой последовательности заранее фиксирована.

[Joker_vD]

Как насчет независимости? $P(d_{n+1}=b\mid d_{n}=a)=P(d_{n+1}=b)$ или нет?

Если все $d_i$ и $d_j$ независимы, то все довольно просто: вероятности $P(d_1=a_1,d_2=a_2,\ldots,d_n=a_n)=256^{-n}$, $P(d_2=a_1,d_3=a_2\ldots,d_{n+1}=a_n)=256^{-n}$, ..., $P(d_{m-n+1}=a_1,d_{m-n+2}=a_2,\ldots,d_m=a_n)=256^{-n}$. Теперь только надо очень аккуратно сложить — учитывая, есть ли в $(a_i)_{i=1}^n$ повторяющиеся подпоследовательности.

[wallflower]

Joker_vD в сообщении #519561 писал(а):

Как насчет независимости?

Независимы.

Joker_vD в сообщении #519561 писал(а):

Теперь только надо очень аккуратно сложить

Вероятность, что на отрезке от $d_1$ до $d_m$ мы не встретим последовательность $(a_1,...,a_n)$ равна $(255/256)^{n(m-n+1)}$. Встретим -- $1-(255/256)^{n(m-n+1)}$. Так?

[ИСН]

Вам svv во втором сообщении убедительно показал на простом примере, что не так. Или Вы полагаете, что от замены 2 на 256 происходит какое-то волшебство, которое это отменяет?

[wallflower]

ИСН
Я понимаю. Но... даже не знаю как объяснить. Так. Пускай мы играем в такую игру. Первый игрок сначала спрашивает у второго: "найду я или нет последовательность байт $(a_1,...,a_n)$ длины $n$, которую получим позже, в первых $m$ байтах случайной последовательности $(d_1,...,d_m)$, $m>n$, полученной с помощью бросания 256-гранника?" (выпадания кости случайны, независимы от предыдущих значений и с равной вероятностью на каждое из 256 возможных значений). Затем второй отвечает "да" или "нет". После этого первый получает искомую случайную последовательность $(a_1,...,a_n)$ так же с помощью 256-гранника.

Что должен отвечать второй игрок, чтобы увеличить вероятность верного ответа? Точнее, как ему рассичать вероятность того, что заданная (но пока неизвестная) последовательность найдётся, если он знает лишь $m$ и $n$?

[Joker_vD]

У, так $(a_i)$ у вас не фиксированная, а тоже случайная... Ну что ж. Пусть элементарный исход — это строка $d_1d_2\ldots d_ma_1a_2\ldots a_n$, где $0\leqslant d_i,a_j \leqslant 255$. Все они равновозможны. Теперь определим интересующее нас событие "угадывания" $A$ как сумму подсобытий $A_i$, $i=\overline{1,m-n+1}$, где $A_i =$ "строка a_i встречается в строке с $i$-ой позиции". Беда в том, что, например, $P(A_1A_2)\ne0$... а формула включений-исключений такая паршивая

[wallflower]

(Оффтоп)

Joker_vD в сообщении #519647 писал(а):

так $(a_i)$ у вас не фиксированная, а тоже случайная...

Ну дык я вроде про это уже примерно 42 раза говорил выше.

Joker_vD в сообщении #519647 писал(а):

а формула включений-исключений такая паршивая

OK. А хотя бы оценить можно как-нибудь по-проще?

[Joker_vD]

wallflower в сообщении #519654 писал(а):

OK. А хотя бы оценить можно как-нибудь по-проще?

Ну можно, например, взять только слагаемые вида $P(A_i)$, $P(A_iA_j)$ и $P(A_iA_jA_k)$, а остальные отбросить.