Теория вероятностей: блуждание без самопересечений

[marie-la]

Случайное блуждание на прямой строится следующим образом. На каждом шаге равновероятно выбирается направление (налево-направо) и размер скачка (1 или 2). Если попали в точку, посещенную ранее, то процесс прерывается. Найти вероятность, что процесс прервется через 7 шагов.

Я решила задачу сложно: Ясно, что данную вероятность можно выразить через вероятности того, что процесс не прервется за $n$ шагов. Траектории, которые не прерываются состоят из: траекторий одного знака без разрыва в значениях, то есть множество значений есть $0,1,2,...,n$, всех траекторий без разрыва в значениях, траекторий одного знака с разрывом в значениях и траекторий разных знаков с разрывом в значениях. Ну и рекуррентные соотношения можно написать на все эти количества. Очень уж мне такое решение не нравится, я сомневаюсь, что его в принципе читабельным можно сделать. Подскажите хорошее решение!

[waxtep]

Без компьютера мне только кустарный способ решения в голову приходит, разбиение траектории на $3+3+1$ шагов с группировкой по типам начального участка в три шага. Типа: рассмотрим только участки траекторий с первым шагом направо и без самопересечений за первые три шага; вариантов всего $15$, из них $9$ - "хорошие" (конечная точка правее начальной, остальные между ними), $3$ - "умеренные" (конечная точка правее начальной, но не правее всех точек участка) и $3$ - "проблемные" (конечная точка левее начальной). Теперь можно смотреть, какой следующий участок из $3$ шагов можно "пришить" к начальному (с учетом того, что следующий участок можно и в обратную сторону запустить - справа налево). Большое количество вариантов покрывается тем, что к любому "хорошему" участку можно пришить слева направо любой "хороший" или "умеренный"; остальные случаи придется рассматривать вручную один за одним, до конца я это не довел, все таки нудно очень.

Если не ошибся, количество траекторий, завершающихся за $n$ шагов для $n=1\ldots4$ есть $0,2,9,25$ (из тех, где первый шаг вправо), в OEIS есть несколько вариантов последовательностей с таким участком (а так же с умноженным на два), но их релевантность этой задаче у меня установить не получилось. Вот этот выглядит хоть как-то похоже - A005582

А точно в условии речь об отсутствии самопересечений, а не о возврате в исходную точку? Второе попроще