Как посчитать вероятность того, что конкретная подстрока встретится во всей строке только 1 раз?

Question

[Magneto903]

В алфавите у меня 4 буквы (пусть А, Б, В, Г)
Для каждой буквы есть своя вероятность пусть это p1, p2, p3, p4.
Далее у меня есть слово, длины N.
И в нём есть какая-то подстрока длины M. Мне нужно найти вероятность, что эта подстрока встречается в строке ровно один раз.

Как я могу посчитать это вероятность?

Comments

[Wataru]

Непонятно.
Подстрока вам дана заранее в виде фиксированных букв? Или вам нужна вероятность, что в случайной строке, допустим, подстрока с 3-его по 10-ый символы не повторяется нигде больше?

Считаются ли пересекающиеся вхождения? Вроде как "aba" входит в строку "ababa" 2 раза? Или в вашей постановке это 1 раз?

[Magneto903]

Илья Николаевский, Да, подстрока фиксированная. Что касается пересечений, то в моей постановке "aba" входит 2 раза в "ababa"

Answer 1

[Wataru]

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

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

Вот построили вы автомат. Теперь задача состоит в том, чтобы найти вероятность, что случайный путь в этом автомате длины n пройдет через конечное состояние ровно один раз. Для этого подсчитайте 2 вероятности: что путь из начала длины k дойдет до конечного состояния один раз, и что путь из конечного состояния длины n-k не вернется в него.

Обе эти вероятности можно подсчитать динамическим программированием:
P1(i, k) - вероятность того, что путь начиная с состояния i (i < n) за k шагов дойдет до состояния n первый раз. Это просто сумма по всем возможным переходам:

P1(i, k) = sum_{c - все символы} P1(next(i, c), k-1) * p(c)

База:

P1(m, 0) = 1
P1(m, k>0) = 0
P1(i < m, 0) = 0

Вторая вероятность: сделать k шаговиз состояния i и ни разу не войти в конечное состояние:

P2(i, k) = sum_{c - все символы, next(i,c) < m} P2(next(i, c), k-1) * p(c)

База:
P1(i, 0) = 1

Ответ к задаче - сумма по всем возможным длинам первой части пути:
sum_{k=m..n} P1(0, k) * P2(m, n-k)

Это решение через динамическое программирование будет O(n*m) по вермени и по памяти.

Замкнутой формулы, как в задаче в моей статье я тут не вижу. Может, если бы вероятности всех символов были бы одинаковы, то что-то можно было бы сократить.

Comments

[Magneto903]

И снова Вы выручаете!)

[Wataru]

Можно как в статье расписать все формулы и немного поколдавать, тогда получится такая формула для P1(n, 0):

P1(n, 0) = 1 - sum_{i = 1..n-m} P1(i, 0) - sum_{j>0, PI^j(m) > 0} P1(PI^j(m) + n -m, 0) / (Prob(s[1])*Prob(s[2])*...*Prob(s[PI^j(m)])

Тут PI^j(m) - это j раз применить префикс функцию к строке. Похожую формулу можно составить для P2(m, k). Этот метод тоже работает за O(nm), но чуть быстрее, потому что более точная оценка O(nl), где l - сколько раз нужно применить префикс функцию к строке, пока не получится пустая 0. Для строки из одних и тех же символов l=m, но обычно сильно меньше. А еще он требует лишь O(n+m) памяти.

Answer 2

[Николай Чуприк]

Могу рассмотреть только случай когда ВСЕ буквы в подстроке различны. Это означает, что подстроки гарантированно не перекрываются. Т.е. невозможен случай слова "РАКОКОКШЫ" и подстроки "КОК"

Пусть Pw(x) = p1*p2*p3*p4*p5*...*pM — вероятность, что с позиции номер x начинается подстрока длины M, где pi — вероятность каждой конкретной буквы в подстроке (на своём месте). Все Pw(x) равны от x = 1 до x = N-M+1 (для больших x подстрока просто не уместится до конца слова по длине). Однако условная вероятность Pw(y) = 0, если подстрока действительно начинается в позиции x, и при этом позиция y отстоит от x менее чем на M (подстроки не перекрываются).

Пусть ^Pw(x) = (1 - Pw(x)) — вероятность НЕ встреть подстроку, начинающуюся с позиции x.

Тогда вероятность, что подстрока начинается в позиции 1 и больше нигде не встречается:
Pw(1) * [ ^Pw(M+1) * ^Pw(M+2) * ... ^Pw(N-M+1) ]= Pw * (N-2M+2) * ^Pw

для 2-й позиции:
^Pw(1) * Pw(2) * [ (N-2M+1) * ^Pw ], что то же самое, что и для первой позиции, просто множитель ^Pw перекочевал из скобок [ ] вперёд.

аналогично для i-ой позиции:
^Pw * (i-1) * [ Pw(i) * (N-2M+3-i) * ^Pw ] = Pw * ^Pw * (N-2M+2)

Теперь просуммируем эту вероятность для всех позиций от 1 до N-M+1

P = Pw*^Pw*(N-2M+2)*(N-M+1),

но для случая N < 2M всё ещё проще (дважды подстрока в слове просто не поместится при всём желании):

P = Pw*(N-M+1)

Если же подстроки могут перекрываться, то там возникают сложные условные вероятности (корреляции) и вообще мутота начинается.

Comments

[Magneto903]

Николай Чуприк, а для случая когда в подстроке есть повторяющиеся буквы в Pw(x) будут одинаковые множители? т.е. грубо говоря если подстрока из 4 символов: АБАВ, то Pw(x) = p1 * p2 * p1 * p3?

[Wataru]

Николай Чуприк, так нельзя считать вообще. Вы перемножаете вероятности ^Pw(M+1) * ^Pw(M+2), как будто они независимые, а они очень даже зависимые.
Вот пример: строка "AB". Пусть всего 2 символа в алфавите с одинаковыми вероятностями. Она не всречается с позиции 1 с вероятностью 3/4. С позиции 2 она не всречается с вероятностью 3/4. Но в строке из трех символов она не встречается на обеих позициях с вероятностю 1/2, а не 9/16 (встречается в четырех строках AAB ABA ABB BAB).

[Николай Чуприк]

Илья Николаевский, согласен.