@Magneto903

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

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

Как я могу посчитать это вероятность?
  • Вопрос задан
  • 94 просмотра
Решения вопроса 1
wataru
@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) по вермени и по памяти.

Замкнутой формулы, как в задаче в моей статье я тут не вижу. Может, если бы вероятности всех символов были бы одинаковы, то что-то можно было бы сократить.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@choupa
Архитектор (обычный, который строит)
Могу рассмотреть только случай когда ВСЕ буквы в подстроке различны. Это означает, что подстроки гарантированно не перекрываются. Т.е. невозможен случай слова "РАКОКОКШЫ" и подстроки "КОК"

Пусть 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)

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы