Могу рассмотреть только случай когда ВСЕ буквы в подстроке различны. Это означает, что подстроки гарантированно не перекрываются. Т.е. невозможен случай слова "РАКОКОКШЫ" и подстроки "КОК"
Пусть 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)
Если же подстроки могут перекрываться, то там возникают сложные условные вероятности (корреляции) и вообще мутота начинается.
