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

[_hum_]

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

Боюсь, что вероятность найти заданную последовательность $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$

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

Ну, это как бы известный факт - более часто встречаются последовательности, которые попадают в "типичные события" - события, имеющие вероятность, приближающуюся к единице. В вашем случае это события $A_n^\varepsilon = $ "$\big|(x_1 + \dots + x_n)/n - 1/2\big| < \varepsilon$". А в общем случае имеется теорема, которая дает оценку вероятности $ P(A_n^\varepsilon) \approx e^{-n H_{P}(P^*)} $, где $H_{P}(P^*)$ - энтропия частотного распределения $P^*$ относительно исходного распределения $P$. Откуда с учетом того, что $H_{P}(P) = 0$, вытекает, что наибольшая вероятность у последовательностей, у которых частота встречаемости символа близка к его вероятности. У остальных экспоненциально убывающая вероятность.

[svv]

Ясно, спасибо!