У нас есть две последовательности независимых случайных величин:

...

и

...

Каждая случайная величина

и

может с равной вероятностью принимать значения

и

.
Длина

фиксирована.
Нужно найти вероятность того, что найдётся подпоследовательность длины k, присутствующая в обоих последовательностях. То есть:
![$P( \exists m: a_i = b_i, \forall i \in [m, m+k] ) = ?$ $P( \exists m: a_i = b_i, \forall i \in [m, m+k] ) = ?$](https://dxdy-02.korotkov.co.uk/f/1/e/1/1e12f39ed30397fef19c0e4478d6b93f82.png)
Казалось бы, простая задача, но никак не могу сообразить решение.
Пробовал выделить всевозможные пары подпоследовательностей из

и

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

. Думал, кроме фиксированных битов остаётся

произвольных битов, значение которых нам не важно. И они могут быть до и после фиксированной подпоследовательности. Но и тут потерпел неудачу, т. к. некоторые последовательности считались несколько раз.
Буду признателен за любую наводку!
Спасибо.