Число траекторий случайного блуждания с двумя границами

[_hum_]

Столкнулся с тем, что нужно оценить асимптотику (при $n \rightarrow \infty$) числа всех возможных траекторий обычного блуждания на отрезке целых чисел с шагом $s_I\in \{ +1, -1\}$ для внутренних точек и $s_L\in \{ 0,+1\}$, $s_H\in \{ 0,-1\}$ - для нижней и верхних границ, соответственно (см. рис), выходящих из нуля и приходящих в заданную точку $(n,l)$. Как-то с наскоку решить не получилось, потому что всюду рассматриваются задачи с одной границей и к тому же без разрешения движения вдоль нее...

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

[svv]

Пусть $N_{n,\ell}$ — число траекторий из $(0,0)$ в $(n,\ell)$. Нижняя граница $\ell=0$, а верхняя $\ell=L$.
Вектор $\mathbf N_n:=\begin{bmatrix}N_{n,0}\\N_{n,1}\\\cdots\\N_{n,L-1}\\N_{n,L}\end{bmatrix}$

Для случая $L=4$, как на картинке:
$\mathbf N_{0}=\begin{bmatrix}1\\0\\0\\0\\0\end{bmatrix}\quad\quad\mathbf N_{n+1}=\begin{bmatrix}1&1&0&0&0\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\0&0&0&1&1\end{bmatrix} \mathbf N_{n}$
Индексы тут отсчитываются с нуля.

_hum_ в сообщении #1504749 писал(а):

было бы достаточно найти число всех возможных траекторий

На каждом шаге, в каждом узле у Вас развилка, выбор одного из двух вариантов.

[_hum_]

svv
Да, действительно, спасибо.
И, как я понимаю, можно, вынося множитель 2 из матрицы, получить матрицу переходов для симметричного случайного блуждания. А тогда собственный вектор (тут он будет, если не ошибаюсь $(1/L)_{i}$) умноженный на $2^n$ и будет описывать итоговую асимптотику числа траекторий.

И да, спасибо за замечание о том, что у нас всегда развилка из двух, даже на границах, а потому получается $2^n$ вариантов.

[Sinoid]

У Гнеденко в его Курсе теории вероятностей в начале тоже задача про очередь сводится к подобной схеме.

(Оффтоп)

Тоже мусолил, мусолил, так дочитать и не смог... Ну, понятно, еще не дорос до таких книг...$

[svv]

_hum_
Мне кажется, будет полезно ещё одно преобразование. Поясню на Вашем примере с $L=4$. Сейчас Ваш отрезок целых чисел, по которому происходит блуждание, состоит из точек $0,1,2,3,4$.
1) Пристыкуем к отрезку его «отражённую» копию, получим $0,1,2,3,4,4',3',2',1',0'$.
2) «Зациклим» то, что получилось, т.е. будем считать точки $0'$ и $0$ соседними.
3) Унифицируем правила: из каждой точки на следующем шаге можно попасть только в две соседних. Например,
из $\ell=4$ можно попасть в $\ell=3$ (шаг вниз) или в $\ell=4'$ (шаг вверх),
из $\ell=0$ можно попасть в $\ell=0'$ (шаг вниз) или в $\ell=1$ (шаг вверх).
Вначале Вы находитесь либо в $(0,0)$, либо в $(0,0')$. А попасть надо либо в $(n,\ell)$, либо в $(n,\ell')$.

Траектория из Вашего примера преобразуется в такую:

Чтобы вернуться к исходной траектории, надо просто игнорировать штрихи у значений $\ell$.

Смысл преобразования в унификации правил. Нет больше никаких границ и никаких особых точек.
На матричном языке выгода в том, что теперь матрица перехода — циркулянт. У неё очень хорошие свойства.

[DeBill]

_hum_
1. Замечательной идее svv можно придать еще более наглядный вид, если горизонтальные отрезки заменить на "галочки" (выпуклые вверх на верхней части, и вниз - внизу): тогда видно, что траектории "обрезанного" процесса получаются из траекторий честного симметричным переворачиванием (вылезающих за пределы полосы частей, многократным, вааще гря) относительно горизонтальных прямых на высоте $-\frac{1}{2}$ и $L+\frac{1}{2}$. Поэтому надо считать число траекторий, идущих в точки $(n,l)$, $(n,-l-1), $ а также во все точки, получаемые из этих двух сдвигами вверх-вниз на числа, кратные $T=2L+2$. Это сводится к вычислению сумм вида $S_m=\sum\limits_{k}^{}C_n^{m+kT}$. Ну, а такие суммы, в принципе, считаются.
Пример. $S_0=\frac{1}{T}\sum\limits_{s=0}^{T-1}(1+\varepsilon_s)^n$, где $\varepsilon_s=e^{\frac{2\pi is}{T}}$. Ну, а это по формулам Эйлера выражается через синусы-косинусы (и даже потом, вроде, сворачивается в компактный ответ).
2. Однако для асимптотики это все не надо. Действительно, исходная задача - это классическое случайное блуждание на отрезке с полуотражением на концах. Такая марковская цепь - равномерно транзитивна, и для нее существуют предельные вероятности состояний. И задача эта - одна из тех редких, где удается получить точный ответ (даже для асимметричного блуждания - с разными вероятностями "налево-направо"). Для симметричного же блуждания имеем очевидный ответ: все состояния равновероятны...

-- 14.02.2021, 12:05 --

Ну, собственно, ТС этот ответ уже получил.

[vicvolf]

DeBill в сообщении #1505011 писал(а):

Однако для асимптотики это все не надо.

Вот именно!

[_hum_]

svv
Спасибо, интересно. Но при рассмотрении обычного блуждания ведь тоже получается хорошая матрица - тридиагональная, или приведенный подход с "блужданием на окружности" может выручить и в каких-то более сложных, чем несимметричное блуждание, случаях?

[svv]

_hum_, не знаю.
Тут матрица совсем хорошая (все точки равноценны и в каждой точке оба направления равноценны). Понятно, что восстановить до такой симметрии можно не любую задачу.