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

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

Вот построили вы автомат. Теперь задача состоит в том, чтобы найти вероятность, что случайный путь в этом автомате длины 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) по вермени и по памяти.

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

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

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