Вероятность встретить подстроку в строке

[Willow]

Меня уже длительное время мучает следующая задача:

Есть битовая строка $S$, длиной $n$ бит. Какова вероятность, того что в ней отсутствует битовая подстрока $C$ длиной $l$ бит, при условии, что $l<n$.

Ну и возможны вариации относительно того, что не отсутствует, а наоборот присутствует, но в определенных количествах - например два или три раза.


Одна из моих оценок, $\left(\frac{2^l-1}{2^l}\right)^{n-l+1}$, не учитывает факта зависимости не встретить строку в соседних позициях, но я к сожалению не могу оценить ее неточность.

P.S. Дабы устранить неточность проявившуюся во время обсуждения, добавляю, что и строка и подстрока выбираются случайным образом из всего множества строк/подстрок равновероятно.

[Capella]

Для того, чтобы ответить на этот вопрос нужно понять, сколько раз $l$ может встретится в $n$. Допустим существует такое равенство $n - l = m$, тогда вероятность будет равна $ \frac 1 {m+1}$, что присутствует. Далее образуете сумму по индексу $k$, который указывает количество возможный подстрок ($n = k\cdot l + r$) и вычитаете из 1.

[Willow]

1)Я не совсем понял формулу $n = k\cdot l + r$

2) по формуле $ \frac 1 {m+1}$, получается, что в любой строке с вероятностью $0.5$ встретится любая подстрока ровно один раз?

[Capella]

Willow писал(а):

1)Я не совсем понял формулу $n = k\cdot l + r$

Эта формула описывает остаточный член не использованных под подстроку байтов и максимальное количество подстрок, если подстрока встречается более чем один раз.
Пример.
Допустим сама строка $n = 12$, а длина подстроки равна $l = 5$. Какое наибольшее число подстрок (не пересекающихся) можно разместить на одной строке? Правильно: 2. Но при этом следует учитывать, что 2 байта всё равно остануться незанятыми ($12 - 2 \cdot 5 = 2$). В любом случае для нахождения максимального индекса должно выполняться неравенство $r < l$

Цитата:

2) по формуле $ \frac 1 {m+1}$, получается, что в любой строке с вероятностью $0.5$ встретится любая подстрока ровно один раз?

Хм, а это как? Вообще-то предполагается, что ответ будет зависеть от количесва ячеек, а само это количество будет зависеть от длин строки и подстроки.

Добавлено спустя 2 минуты 29 секунд:

Кстати, Вам надо ещё учитывать в самой сумме, что подстрока идёт сплошным потоком, т.е. не имеет разрывов

[Willow]

Вот строка из 12-ти символов
101010101010
сколько в ней раз может встретится строка из 5-ти символов 10101
ответ четыре раза а не два.


P.S. Возможно или я, что-то не договорил в условии, или абсолютно не понял вашей задумки.

[Capella]

Willow писал(а):

Вот строка из 12-ти символов
101010101010
сколько в ней раз может встретится строка из 5-ти символов 10101
ответ четыре раза а не два.


P.S. Возможно или я, что-то не договорил в условии, или абсолютно не понял вашей задумки.

4 потому что у Вас пересечение есть. Я думала так: если есть первые 5 символов, то они уже не относятся к другой подстроке, т.е. вот так:

101010101010 - две подстроки

Добавлено спустя 1 минуту 25 секунд:

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

Добавлено спустя 4 минуты 46 секунд:

Во вторых подсчёт вероятности под именно это условие проходит как-раз через $m+1$ ячеек. Всего у Вас образовано 8 ячеек, в половине которых возможно появление Вашего кода.
Вам для этого надо вычислить саму вероятность появления подстроки в ячейки. Поскольку это будет зависеть от количества символов алфавита (ну у Вас их всего 2 - и их появление равновозможно), а во вторых появления нужной последовательности.
Я предлагаю тогда следующее: рассмотреть для начала саму подстроку и определить именно эту вероятность, исходя из вышеприведённых соображений. Домножать каждый раз количество ячеек на эту самую вероятность.
Прошу прощения, я просто изначально исходила из того, что появление подстроки имеет устойчивую вероятность в $\frac 1 2$. На практике безусловно это не совсем так.

Добавлено спустя 10 минут 7 секунд:

Вероятности появления нужной подстроки в 5 символов из алфавита в 2 буквы ("1" и "0") равна $\frac 1 {2^5}$

Добавлено спустя 21 минуту 50 секунд:

Ну и наконец последнее - перечетав Ваше сообщение, я, честно говоря, не совсем хорошо поняла, что Вы делаете.
Проблема там вот в чём, обычно под вероятностью понимают отношение счастливых исходов ко всем исходам. Почему Вы вдруг решили рассмотреть именно эту строку? Это не всё $n$...
Количество всех строк будет описано так: $n = 2^{12}$ и будет содержать все перстановки "1" и "0" начиная с 000000000000 и заканчивая 111111111111. Или это у Вас просто какой-то конкретный пример?

Добавлено спустя 40 минут 42 секунды:

Вот, у меня возникла одна мысля, как эту задачу вообще очень просто сделать.
Для случая, когда строка не содержит подстрок. Нужно подсчитать вероятность не выпадания подстроки в ячейки. Она в этом случае будет $1 - \frac 1 {64} = \frac {63}{64}$. Т.е вероятность всех других вариантов. A теперь надо просто перемножить (пересечение эту вероятность по всем ячейкам, т.е. $\frac {63}{64} ^{ (m + 1)}$ или более общая формула

$$\frac {\frac {a^l - 1}{a^l} ^{ (m+1)}} {a^n}$$

, где $a$- количество знаков, $l$ длина подстроки и $m = n - l$, где $n$ длина самой строки. Вот, вышла Ваша формула.

[Willow]

Я решаю следующую задачу:

Есть случайная строка, есть случайная подстрока. Надо оценить вероятность не появления (или появления какого-то конкретного числа раз) подстроки в строке. Причем единственная фиксированная информация это длины.

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

Capella писал(а):

Вот, вышла Ваша формула.

Не совсем моя, - у меня не было деления на $a^n$

Если рассмотреть случай, когда $l=1$, то окажется, что ни Ваша ни моя формулы не верны.

[Capella]

Да, на $a^n$ не надо делить. Это я неправильно оценила новую омегу, она не будет больше зависеть от длины строки, а от длины подстроки

Добавлено спустя 3 минуты 56 секунд:

А какой Вы случай рассмотрели для $l=1$?
Для $n = 2$ и $n = 3$ вроде всё в порядке. Да и в целом формула ${\frac 1 2}^{n-l+1} = {\frac 1 2}^{n}$ верна, поскольку подразумевает одно распределение двух элементов по $n$ ячейкам (в данном случае везде "0" например).

[Willow]

Дам... это я напутал.
Но формула все равно не правильная. Она не учитывает, то что события не независимы. И для случая $l=2$ завышает примерно в два раза (ну как минимум для некоторых $n$).

[Capella]

Да нет, думается мне формула правильная для счастливых случаев. Просто теперь осталось рассмотреть все возможные ячейки. По длине строки надо будет брать их пересечение, но учитывая то, что строк тоже много (вот где всё-таки приходит в игру $a^n$), надо будет рассмотреть их объединение. Пересечение будет иметь $m+1$ членов, т.е. сколько ячеек возможно в одной строке (все они должны выполняться). А вот объединение будет задаваться через $2^n$ - т.е. для $n = 4$ Вы имеете 16 различных строк.
Например $n = 4, l = 2$. Вам подходит такой случай: $(\frac 3 4)^3$, т.е. Вы рассматриваете 3 варианта из четырёх для трёх ячеек - то что код не появляется в одной из подстрок какой-то отдельной строки. Это счастливые случаи. Их надо обощить для общего числа строк. Каждая строка имеет по 3 таких случая (здесь зависимость), но всего таких строк 16 - нужно взять их объединение.
Возможно лучше разбить строки по группам (например по количеству "1" в строке) и рассмотреть отдельно вероятность каждой группы, потому что там вероятности там не будут равны (вероятность для отдельных подстрок).

Добавлено спустя 32 минуты 17 секунд:

А всё таки я правильно делила в начале на $a^n$. Это даёт Вам все возможные строки - и те, которые имеют в себе подстроку, и те, которые не имеют. Именно из этого числа надо выбирать теперь те строки, которую подстроку содержат.
А вообще для разных подстрок Вы имеете и разные вероятности: например для кода "10" в вышеприведённом примере найдётся 11 строк из 16, а для "11" только 8. поэтому лучше разбивать по группам и считать в них.

[Willow]

$\frac{2\frac{11}{16}+2\frac{8}{16}}{4}=\frac{19}{32}$ - вероятность вычисленная практически.

Если считать по формуле без деления то получается $\frac{27}{64}$,
а если еще поделить на $a^n$ то получится $\frac{27}{1024}$. Даже если домножить последнее на кол-во строк которые не встречались, то все равно ничего не получится.

[Capella]

А что значит Ваша формула?

Смотрите, сделаем полный расклад.
Условие: какова вероятность, что подстрока "11" (например) не будет проходить в 4-значной строке. (это насколько я понимаю та идея, которую Вы хотите посчитать).

Решение: Очевидно, если строка не содержит знака "1" или содержит его на каком-то месте вероятность встречи искомой подстроки равна 0. Эта вероятность равна 1, если строка содержит три или четыре знака "1". Таким образом Вы получаете 5 заведомо удачных и 5 заведомо неудачных решений.
Рассмотрите теперь случай, когда количество "0" и "1" в строке по 2 знака. Перечислим все случаи:
1100, 1010, 1001, 0110, 0101, 0011
Имеем 3 удачных случая (2,3,5 случаи). Таким образом работая по группам имеем для групп с:
ни одной "1": 1 из 1
одна "1": 4 из 4
две "1": 3 из 6
три "1": 0 из 4
четыре "1": 0 из 1
Cкладывая ненулевые вероятности первых трёх групп получится: $\frac 1 {16} + \frac 4 {16} + \frac 3 {16} = \frac 8 {16} = \frac 1 2$.
В знаменателе стоит общее количество строк ($a^n$), а в числителе только тех строк, где точно не встречается "11".

[Willow]

Предложенный Вами вариант это частное решение.
Я хочу (пытаюсь) решить общий вариант. Я беру на угад последовательность короткую и длинную, и хочу знать вероятность того, что короткой последовательности не будет в длинной, или она там будет, ну скажем, ровно три раза.
Вот пример практических расчетов для последовательностей с длиной 4 и 2:
Таблица в которой приводится количество встреч строк 01 и 11 (для 10 и 00 варианты зеркальные)
_____01 11
0000
0001 1
0010 1
0011 1 1
0100 1
0101 2
0110 1
0111 1 2
1000
1001 1
1010 1
1011 1 1
1100 1
1101 1 1
1110 2
1111 3
То есть, строка 01 - 10 раз встречается единожды, 1 раз дважды, и 5 раз не встречается. Строка 11 - 4 раза единожды, 2 раза дважды, один раз трижды и 9 раз не встречается. Вероятность встретить строки 01, 11 - 1/4. Таким образом:

вероятность не встретить строку длиной 2 символа в строке длиной 4 символа:
$\left(\frac{1}{4}\frac{5}{16}+\frac{1}{4}\frac{9}{16}\right)2=\frac{7}{16}$

вероятность встретить строку длиной 2 символа 1 раз в строке длиной 4 символа:
$\left(\frac{1}{4}\frac{10}{16}+\frac{1}{4}\frac{4}{16}\right)2=\frac{7}{16}$

вероятность встретить строку длиной 2 символа 2 раза в строке длиной 4 символа:
$\left(\frac{1}{4}\frac{1}{16}+\frac{1}{4}\frac{2}{16}\right)2=\frac{3}{32}$

вероятность встретить строку длиной 2 символа 3 раза в строке длиной 4 символа:
$\left(\frac{1}{4}\frac{0}{16}+\frac{1}{4}\frac{1}{16}\right)2=\frac{1}{32}$

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

Предложенные Вами и мною последние варианты - это частные решения. Если удастся использовать алгоритмы их подсчета для получения общей формулы будет прекрасно, но я пока не готов к обобщению.

[Capella]

Тогда я снова предлагаю сделать так. Разбить всё-таки на группы (по значку алфавита), и рассмотреть внутри каждой группы с какой вероятностью там будет выпадать Ваше условие, сколько строк содержит группа и сделать после этого объединение всех событий (т.е. благоприятных событий из всех групп). Ну и в знаменателе указать просто общее количество строк.
Конечно чем больше длина строки и (или) подстроки, тем более громоздкой будет сумма.

[RIP]

Несколько соображений. Несложно оценить вероятность того, что короткая строка не будет совсем входить в длинную, в случае, когда $l$ фиксировано, а $n$ растёт.

Скажем, при $l=2$: Строки 01 и 10 не будут входить в $n+1$ строк каждая, строки 00 и 11 --- в $F_{n+2}$ строк каждая, где

$$F_n=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^n+\left(\frac{1-\sqrt5}2\right)^n\right)$$

--- последовательность Фибоначчи. Соответственно, вероятность равна

$$\frac{F_{n+2}+n+1}{2^{n+1}}\sim\frac{3+\sqrt5}{4\sqrt5}\cdot\left(\frac{\sqrt5+1}4\right)^n$$

.
Видно, что "основной вклад" в вероятность дают строки 00 и 11. Так будет и в общем случае. А именно, пусть $l$ фиксировано. Тогда при $n\to\infty$ количество строк длины $n$, в которые не входит

$$\underset{l}{\underbrace{00\ldots0}}$$

, асимптотически равно

$$\sim\frac{\alpha-1}{\alpha^{l+1}-l}\cdot\alpha^{n+l+1},$$

где $\alpha=\alpha_l$ --- корень уравнения $\alpha^{l+1}-2\alpha^l+1=0$, $\alpha>1$. При больших $l$ он приближённо равен

$$\alpha_l=2-2^{-l}-l2^{-2l-1}-(3l^2+l)2^{-3l-3}-\left(\frac83l^3+2l^2+\frac13l\right)2^{-4l-3}+O(l^42^{-5l}).$$

(Если я не наврал в вычислениях...)

Для каждой из строк длины $l$, отличной от сплошных нулей или единиц, количество строк длины $n$, не содержащих её, есть $O(\beta^n)$, где $\beta=\beta_l<\alpha_l$. Соответственно, при фиксированном $l$ и растущих $n$, вероятность получается

$$\sim\frac{4(\alpha-1)}{\alpha^{l+1}-l}\cdot\left(\frac\alpha2\right)^{n+l+1}.$$

Скорее всего, эти асимптотики можно написать и в случае, когда $l$ может расти вместе с $n$, но достаточно медленно, но меня что-то ломает это проверять.
Вроде бы так.