Как правильно отметил @Anton
нам достаточно решить задачу “какова вероятность того, что в последовательности из 99 нуклеотидов не будет подряд идущих двух G”.
Давайте решим более общую задачу – какова вероятность того, что в последовательности из n нуклеотидов не будет подряд идущих двух G. Для этого найдем количество последовательностей из n нуклеотидов, таких, что в них нет GG, потом поделим на 4^n – на количество всех возможных последовательностей из n нуклеотидов. Так и получим вероятность.
Чтобы это найти, введем две вспомогательные функции: пусть f(n) – количество последовательностей длины n в которых нет GG и в которой последний нуклеотид G; g(n) – количество последовательностей длины n в которых нет GG и последний нуклеотид не G. Тогда ответом к нашей задаче будет число
Попробуем найти рекуррентную зависимость этих двух функций.
С одной стороны, мы можем получить последовательность длины n которая не заканчивается на G, если к последовательности длины n-1 заканчивающееся на G припишем нуклеотид A,C,T (3 способа) или к последовательности длины n-1 не заканчивающееся на G припишем нуклеотид A,C,T (3 способа). Следовательно
С другой стороны, мы можем получить последовательность длины n которая заканчивается на G, если к последовательности длины n-1 не заканчивающееся на G припишем нуклеотид G (1 способ). Тогда имеем
Соединим два равенства и распишем базовые случаи для n=1,n=2. Получаем
Выпишем явную форму данного рекуррентного уравнения (можно сделать через характеристические уравнения, а можно через вольфрам). Получается вот такое несложное выражение ![]()
Далее выражаем f(n) = g(n-1) .
Выходит, что ответ равен