\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}

\def\udcs{517.958:530.145} %Здесь автор определяет УДК своей работы
\def\mscs{82B20, 81T25} %Здесь автор определяет классификаторы AMS своей работы


%NEWSYMBOLS
\def\ZZ{{\mathbb Z}}

%NEWTHEOREMS
\newtheorem{thm}{Теорема}
\newtheorem{lem}{Лемма}
\newtheorem{prop}{Предложение}
\theoremstyle{definition} 
\newtheorem*{defn*}{Определение}
\newtheorem{rem}{Замечание}

\begin{document}

\thispagestyle{empty}




\title[Шашки Фейнмана с поглощением]{Шашки Фейнмана с поглощением}
\author{{М.Д. Дмитриев}}%
\date{}
\address{Mikhail Dmitrievich Dmitriev  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} National Research University Higher School of Economics,
\newline\hphantom{iii} Usacheva 6,
\newline\hphantom{iii} 119048, Moscow, Russia}%
\email{mddmitriev@edu.hse.ru}%


\maketitle

\begin{quote}
\noindent{\sc Abstract. } We give a new elementary proof of the theorem by Ambainis et al. that for a quantum walk, the probability amplitudes of absorption at the initial point after 4n steps are proportional to the Catalan numbers. We also calculate the absorption probabilities at points close to the initial one and prove a relation that connects the probability amplitudes along the diagonal. \medskip

\noindent{\bf Keywords:} Feynman checkers, quantum walks, Catalan numbers, reflection method
 \end{quote}



\section*{Введение}


''Шашки Фейнмана''--- это наиболнее элементарная модель движения электрона. Модель была предложена Ричардом Фейманом в 1965 году \cite{Feynman-Gibbs}. 
Она известна также как одномерное квантовое блуждание \cite{Ambainis}. Модель наиболее примечательна тем, что она наглядно иллюстрирует многие базовые идеи квантовой теории и является одной из архитектур универсального квантового компьютера \cite{Venegas-Andraca-12}. Актуальные обзоры приводятся в \cite{Kempe-09, Liu, Skopenkov, Venegas-Andraca-12}.
 
 В основу данной работы лег известный результат Амбаиниса и его коллег \cite{Ambainis} о том, что вероятность возвращения одномерного квантового блуждания в начальную точку равна $\frac{2}{\pi}$ (теорема \ref{tm}). Напомним, что для классического случайного блуждания эта вероятность равна $1$ (теорема Пойа).
  Мы приводим новое элементарное доказательство этого результата и обобщаем его на точки, близкие к начальной (теорема \ref{thm}).


Другие комбинаторные результаты об этой модели приводятся в \cite{K-v_S-v, Nov, Ozh, Skopenkov_Ustinov-2}.

\section*{Определение модели}


Мы начнем с неформального определения модели ''шашки Фейнмана'', а затем дадим точное. Этот раздел почти полностью заимствован из работы \cite{Skopenkov}.
	
\begin{figure}[h]
	\centering
	\includegraphics[scale = 0.70]{c1.png}
	\vspace{-.3cm}
	\caption{\cite{Skopenkov} Пути шашек}
	\label{Checker-paths}

\end{figure}	
	
	 На бесконечной шахматной доске шашка ходит на соседнюю по диагонали клетку влево-вверх или вправо-вверх (рис.\ref{Checker-paths}). Каждому пути $s$ шашки сопоставим вектор $a(s)$ на плоскости следующим образом. В начале движения этот вектор направлен вверх и имеет длину $1$.
Пока шашка движется вдоль прямой, вектор не меняется, а после каждого поворота шашки он поворачивается на $90^\circ$ по часовой стрелке (независимо от того, в какую сторону повернула шашка). В конце движения вектор сжимается $2^{(t-1)/2}$ раз, где $t$ --- общее число ходов шашки (т.е. заменяется на вектор такого же направления, но длины $1/2^{(t-1)/2}$). Полученный в итоге вектор и есть $a(s)$. Например, для пути на рис.\ref{Checker-paths} слева вектор $a(s)=(1/8,0)$.% направлен вправо и имеет длину $1/8$.




 Обозначим $a(x,t):=\sum_s a(s)$, где суммирование ведется по всем путям $s$ шашки из клетки $(0,0)$ в клетку $(x,t)$, \emph{начинающимся с хода вправо-вверх}. 
 
 Например, $a(1,3)=(0,-1/2)+(1/2,0)=(1/2,-1/2)$; рис.\ref{Checker-paths} справа.
 
 Число $P(x,t) = |a(x,t)|^2$ называется \emph{вероятностью обнаружения электрона в клетке $(x,t)$, если он испущен из клетки $(0,0)$}.




\begin{figure}
	\centering
	\includegraphics[scale = 0.6]{twoways.png}
	\vspace{-.3cm}
	\caption{Пути для модели с поглощением}
	\label{twoways}

\end{figure}

\emph{Вероятность обнаружения электрона в клетке $(x,t)$ при поглощении на прямой $x = x_0$} определяется аналогично вероятности $P(x,t)$, только суммирование производится по путям $s$, не проходящим через клетки вертикали $x=x_0$, за исключением, быть может, начальной и конечной клеток. Обозначим эту вероятность через $P(x,t \,|\, x_0)$.
 Например, на рис. \ref{twoways} красный путь мы не будем учитывать при суммировании, а зеленый будем. Соответственно, для модели с поглощением $a(1,3\,|\, 0)=(1/2,0).$ 



Резюмируем эту конструкцию в виде точного определения.

\begin{defn*} \label{def-basic} \emph{Путь шашки} --- это конечная последовательность целых точек плоскости такая, что вектор из каждой точки (кроме последней) к следующей равен либо $(1,1)$, либо $(-1,1)$. \emph{Поворот} --- это такая точка пути  (не первая и не последняя), что вектор, соединяющий эту точку с предыдущей, ортогонален вектору,  соединяющему её со следующей.
\emph{Стрелка} (или \emph{амплитуда вероятности}) --- это комплексное число
 $$
a(x,t \,|\, x_0):=2^{(1-t)/2}\,i\,\sum_s (-i)^{\mathrm{turns}(s)},
$$ 
где сумма берётся по всем путям $s$ шашки из точки $(0,0)$ в точку $(x,t)$, проходящим через точку $(1,1)$ и не проходящим через точки прямой $x=x_0$, кроме, быть может, начальной и конечной точки пути, а $\mathrm{turns}(s)$ обозначает общее число поворотов в $s$.
% \emph{turns} in $s$ (i.e., vertices with a right angle).
Здесь и далее пустая сумма по определению считается равной $0$.
Обозначим  $$P(x, t \,|\, x_0):=|{a}(x, t \,|\, x_0)|^2.
$$

Значения $a(x,t \,|\, 0)$ при малых $x$ и $t$ показаны на рис. \ref{Count}.
\end{defn*}

\begin{figure}[h]
	\begin{center}
	\includegraphics[scale = 0.15]{geogebra-export2222.png}
	\vspace{-.3cm}
	\caption{ Значения $a(x,t \, | \, 0)$ при $0\le x,t\le 5$}
	\label{Count}
	\end{center}
\end{figure}	


Исследование данной модели началось со следующего яркого результата.

\begin{thm}[Амбаинис и др., {\cite[теорема 8]{Ambainis}}]
\label{tm} Для любого целого $t > 0$ выполнено
 \begin{equation*}
a(0,t \,|\, 0)= 
 \begin{cases}
   \frac{1}{\sqrt{2}}, &t = 2;\\
    \frac{(-1)^k (^{2k}_k)}{(k+1)2^{2k + 3/2}},& t = 4k + 4, \, \text{где } k \in \ZZ ;\\
   0, &\text{иначе.}
 \end{cases}
\end{equation*} Более того, $$\sum_{t = 1}^\infty P(0,t \,|\, 0) = \frac{2}{\pi}.$$


\end{thm}


Последнее выражение -- это вероятность поглощения электрона в начальной точке. А длины стрелок $a(0,4k + 4 \,|\, 0)$ оказываются равны числам Каталана, деленным на некоторые степени двойки.


В следующем разделе мы докажем теорему \ref{tm} более простым способом, чем в статье \cite{Ambainis}. А именно, мы докажем, что стрелки  удовлетворяют реккурентному соотношению, очень похожему на соотношение для чисел Каталана, с аналогичным доказательством (ср. замечание \ref{Op}).


Теперь сформулируем основную теорему. Это утверждение было предложено в качестве гипотезы Г. Минаевым и И. Русских в 2019 (частное сообщение).


\begin{thm}
\label{thm}
$$\sum_{t = 1}^\infty P(3,t \,|\, 3) = 2\sum_{t = 1}^\infty P(-1,t \,|\, {-1}) = $$
$$ 4\sum_{t = 1}^\infty P(2,t \,|\, {2}) - 2 = \frac{8}{\pi} - 2.$$
\end{thm}

Основной интерес представляет первое равенство, так как второе и третье легко следуют из теоремы \ref{tm} и лемм \ref{l1} и \ref{l2}. Похожие числа возникают для простого случайного блуждания на $\mathbb{Z}^2$ \cite[таблица~2]{Pakharev-Skopenkov-Ustinov}.




\section*{Новое доказательство теоремы Амбаиниса и соавторов}

Для нового доказательства теоремы \ref{tm} нам потребуется слудующая лемма, аналогичная известному реккурентному соотношению для чисел Каталана.

 \begin{lem}
 \label{polovina}
 Для любого целого $n > 2$ выполнено:
 
 $$a(0,2n \,|\, 0) = \frac{-1}{\sqrt{2}}\sum_{j=2}^{n-2} a(0,2(n-j) \,|\, 0) a(0,2j \,|\, 0). $$
 \end{lem}

\begin{proof}

См. рис. \ref{piclem}. Рассмотрим путь $p$ шашки из точки $(0,0)$ в точку $(0,2n)$, который не имеет других точек пересечения с прямой $x=0$. Заметим, что при $n > 1$ такой путь пересекает прямую $x=2$ в точке $(2,2)$. Так как $p$ заканчивается на прямой $x=0$, то он пересекает прямую $x=1$ в еще хотя бы одной точке  $(1,2j + 1)$, отличной от $(1,1)$. Здесь $j$ может принимать значения от $1$ до $n-1$. Выберем среди этих $j$ наименьшее. Рассмотрим отображение, которое каждому пути $p$ сопоставляет пару путей $(m,l)$, стартующих из $(0,0)$, где путь $l$ повторяет все ходы  пути $p$ со второго и до $(2j+1)$-го, а путь $m$ начинается с хода вправо-вверх, а затем повторяет ходы пути $p$ с $(2j+2)$-го до последнего. 
 
\begin{figure}[ht]
	\centering
	\includegraphics[scale = 0.30]{last2.png}
	\vspace{-.3cm}
	\caption{Отображение путей (см. лемму \ref{polovina})}
	\label{piclem}
	

\end{figure} 
 
 
 
 
  Покажем, что это отображение --- биекция между множеством путей, дающими вклад в $a(0,2n \,|\, 0)$, и объединением множеств пар путей, дающих вклад в $a(0,2(n-j) \,|\, 0)$ и $a(0,2j \,|\, 0)$ соответственно, по всем $j$ от $1$ до  $n-1$. Для этого построим обратное отображение, т.е. по любой паре $(m,l)$ восстановим путь $p$. Сделаем из точки $(0,0)$ сначала ход вправо-вверх, затем все ходы пути $l$, а затем ходы пути $m$,  кроме первого. Легко видеть, что построенный путь приходит в точку $(0,2n)$ и он впервые пересекает прямую $x=1$ в точке $(1,2j+1)$. Ясно, что построенное отображение обратно исходному, а значит, они оба --- биекции.
  
  
  
  Тогда при $j <n-1$ имеем $$-\sqrt{2} \, a(p) = -i  (-i)^{\mathrm{turns}(p)}  2^{1 - n} =$$  $$= i  (-i)^{\mathrm{turns}(m)}  2^{1/2 - n+j}  i  (-i)^{\mathrm{turns}(l)}  2^{1/2 - j} = a(m)a(l), $$ так как путь $p$ имеет такую же длину и на один поворот больше, чем $l$ и $m$ в сумме.
  
   Если же $j = n-1$, то $\sqrt{2} \, a(p)= a(l)a(m),$ так как путь $p$ имеет такую же длину и на один поворот меньше, чем $l$ и $m$ в сумме.
   
    Тогда, суммируя по всем путям $p$, получаем:
 
 $$-\sqrt{2}\, a(0,2n \,|\, 0) = \sum_{j=1}^{n-2} a(0,2(n-j) \,|\, 0) a(0,2j \,|\, 0) - $$ $$ - a(0,2(n-1) \,|\, 0) a(0,2 \,|\, 0)  $$ 
 $$= \sum_{j=2}^{n-2} a(0,2(n-j) \,|\, 0) a(0,2j \,|\, 0).$$
 \end{proof}

Теперь мы можем легко доказать теорему \ref{tm}.

\begin{proof}[Первое доказательство теоремы \ref{tm}]

Достаточно доказать утверждение для четного $t=2n$. Сделаем это по индукции. 

Базу индукции ($n=1$ и $2$) легко проверить из определений. Докажем переход.


 
Если $n$ --- четное больше двух, то 

 $$a(0,2n \,|\, 0) = \frac{-1}{\sqrt{2}}\sum_{j=2}^{n-2} a(0,2(n-j) \,|\, 0) a(0,2j \,|\, 0) = $$ 
 $$ = \frac{-1}{\sqrt{2}}\sum_{\substack{j=2 \\ j \text{  четное}}}^{n-2}  \frac{(-1)^{(n-j)/2-1} \binom{n-j-2}{(n-j)/2-1}}{((n-j)/2)2^{n-j - 1/2}} \cdot   \frac{(-1)^{j/2-1} \binom{j-2}{j/2-1}}{(j/2)2^{j - 1/2}} = $$ $$ =  \frac{(-1)^{n/2-1}  \binom{n-2}{n/2-1}}{(n/2)2^{n - 1/2}}. $$

Здесь первое равенство следует из леммы \ref{polovina}, второе --- из предположения индукции, а последнее --- из рекурентной формулы для чисел Каталана.

Если же $n$ --- нечетное больше двух, то

 $$a(0,2n \,|\, 0) = \frac{-2}{\sqrt{2}}\sum_{j=2}^{n-2} a(0,2(n-j) \,|\, 0) a(0,2j \,|\, 0) = $$ 
 $$ = \frac{-2}{\sqrt{2}}\sum_{\substack{j=2 \\ j \text{  четное}}}^{n-2}  0 \cdot   \frac{(-1)^{j/2-1} \binom{j-2}{j/2-1}}{(j/2)2^{j - 1/2}}  =  0. $$

Равенство $\sum_{t = 1}^\infty P(0,t \,|\, 0) = \frac{2}{\pi}$ доказывается так же, как в \cite[доказательство теоремы 8]{Ambainis}.
\end{proof}
 
 Приведем также другое доказательство теоремы \ref{tm}, которое показывает, откуда берется формула.

 
\begin{proof}[Второе доказательство теоремы \ref{tm}]
Введем производящую функцию $A(q) = \sum_{n=1}^{\infty} a(0,2n \,|\, 0) q^n$. Тогда из леммы \ref{polovina} легко получить следующее соотношение для $A(q)$:

$$ A(q) =  \frac{-1}{\sqrt{2}}A(q)^2 + q A(q) + \frac{q}{\sqrt{2}} .$$

Решая полученное уравнение относительно $A(q)$, получаем:

$$A(q) = \frac{q-1 \pm \sqrt{1 + q^2}}{\sqrt{2}}.$$ 

Заметим, что нам подходит $A(q) = \frac{q-1 + \sqrt{1 + q^2}}{\sqrt{2}}$, так как $A(0) = 0$.

Раскладывая $A(q)$, получаем искомое равенство.
\end{proof}

\begin{rem}
\label{Op}
В статье  \cite[(19)]{Ambainis} использовалось более сложное соотношение  $ f(z) = z - z(zf(z) + zf(z)^2 + z f(z)^3 + ...)$, где $f(z) = \frac{- A(-2z^2)}{\sqrt{2}z}$. Для его получения использовалась похожая идея, но рассматривались все точки пересечения с вертикалью $x=1$ и путь разбивался на $k$ меньших путей, где $k$ - число точек пересечения. Для нахождения $f(z)$ из соотношения требовались дополнительные шаги, которые в нашей ситуации не понадобились.
\end{rem}


\section*{Доказательство основного результата}


Теперь докажем основной результат работы --- теорему \ref{thm}. Нам потребуется несколько лемм.




\begin{figure}[ht]
	\centering
	\includegraphics[scale = 0.75]{1.png}
	\vspace{-.3cm}
	\caption{Отображение путей (см. лемму \ref{l1})}
	\label{pic1}
	

\end{figure} 

 \begin{lem}
 \label{l1} При $t>2$ верно равенство $ a(-1,t \,|\, {-1}) = \sqrt{2}\,a(0,t+1 \,|\, 0) $.
 \end{lem}
 

 
 
\begin{proof}

 Построим биекцию между путями, дающими вклад в $a(0,t+1 \,|\, 0)$, и путями, дающими вклад в $a(-1,t\,|\,{-1})$. Рассмотрим путь $s$, дающий вклад в $a(0,t+1\,|\,0)$, и построим по  нему путь $s'$, дающий вклад в $a(-1,t \,|\, {-1})$, сдвинув $s$ на вектор $(-1,-1)$ и удалив первый ход (как на рис. \ref{pic1}). Заметим, что для $t>2$ построенное отображение $s \mapsto s'$ --- биекция, так как если бы построенный путь $s'$ начинался с хода влево-вверх, то $s$ проходил бы через точку $(0,2)$ и не мог бы давать вклад в $a(0,t+1\,|\,0)$. Из того, что путь $s'$ короче на один шаг, следует равенство $\sqrt{2}a(s) = a(s')$. Суммируя по всем путям, получаем утверждение леммы.
 \end{proof}



 \begin{lem}
 \label{l2} При $t>2$ верно равенство $a(2,t \,|\, 2) = -i\, a(0,t \,|\, 0)$.
 \end{lem}




\begin{figure}[ht]
	\centering
	\includegraphics[scale = 0.75]{2.png}
	\vspace{-.3cm}
	\caption{Отображение путей (см. лемму \ref{l2})}
	\label{pic2}
	

\end{figure}



\begin{proof}
 Построим биекцию между путями, дающими вклад в $a(0,t \,|\, 0)$, и путями, дающими вклад в $a(2,t \,|\, 2)$. Рассмотрим путь $s$, дающий вклад в $a(0,t \,|\, 0)$, и построим по нему путь $s'$, дающий вклад в $a(2,t \,|\, 2)$, получающийся из $s$ отражением относительно прямой $x=1$, начиная со второго хода (как на рис. \ref{pic2}).
 
  Очевидно, что это биекция. Более того, верно $-i\, a(s) = a(s')$, если $s$ и $s'$ не заканчивались на горизонтали $t=2$. Суммирование по путям $s$ и $s'$ завершает доказательство леммы.
  \end{proof}


\begin{lem}
 \label{l3}
 При $t>3$ верно равенство $$a(3,t\,|\,3) = \sqrt{2} \, a(2,t-1 \,|\, 2) -i\,a(-1,t \,|\, {-1}).$$
\end{lem}


\begin{figure}[ht]
	\centering
	\includegraphics[scale = 0.75]{3.png}
	\vspace{-.3cm}
	\caption{Отображение путей (см. лемму \ref{l3})}
	\label{pic3}
	

\end{figure}



\begin{proof}

 Разобьем пути, дающие вклад в $a(3,t \,|\, 3)$, на два множества:

$R$ --- множество путей, которые начинаются с двух ходов вправо-вверх;

$L$ --- множество путей, которые начинаются с хода вправо-вверх, а затем идет ход влево-вверх.





Посторим биекцию множества $R$ и множества путей, дающих вклад в 
$a(2,t-1  \,|\, 2)$, убирая первый ход и сдвигая путь на вектор $(-1,-1)$.

Суммируя по всем таким путям, получаем $$\sum_{s\in R} a(s) = \frac{a(2,t-1 \,|\, 2)}{\sqrt{2}}.$$






Построим биекцию множества $L$ и множества путей, начинающихся двумя ходами вправо-вверх и дающими вклад в $a(-1,t \,|\, -1)$. Для этого отразим путь из $L$, начиная со второго хода, относительно прямой $x=1$ (Это отображение обатно изображенному на рис. \ref{pic2}). Для вычисления $\sum_{s\in L} a(s)$ остается посчитать сумму по путям, которые дают вклад в $a(-1,t \,|\, -1)$ и начинаются с хода вправо-вверх, а затем идет ход влево-вверх. Эти пути мы отобразим в пути, которые дают вклад в $a(2,t-1 \,|\, 2)$, убрав первый ход и сделав сдвиг на вектор $(-1,-1)$, а затем отражение относительно прямой $x=0$ (как на рис. \ref{pic3}). В результате получаем $$\sum_{s\in L} a(s) =  -i \,a(-1,t \,|\, {-1}) + \frac{1}{\sqrt{2}}a(2,t-1 \,|\, 2).$$

Прибавляя вычисленную ранее сумму по $s\in R$, получаем требуемое утверждение.
\end{proof}


\begin{prop}
 \label{prop}
 При $t>3$ верно следующее равенство $$a(3,t\,|\,3)  = -i \, \sqrt{2}\, a(0,t+1 \,|\, 0)  -i \, \sqrt{2}\, a(0,t-1 \,|\, 0).$$

\end{prop}

\begin{proof}  По леммам \ref{l1} -- \ref{l3} имеем $$a(3,t \,|\, 3) =  \sqrt{2}\, a(2,t-1 \,|\, 2) -i\,a(-1,t \,|\, {-1}) = $$
 
  $$ =  -i \,\sqrt{2} \, a(0,t+1 \,|\, 0)  -i \,\sqrt{2} \, a(0,t-1 \,|\, 0).$$ 
  \end{proof}



\begin{proof}[Доказательство теоремы \ref{thm}] Из теоремы \ref{tm} получаем, что $a(0,4k + 4 \,|\, 0) = \frac{(-1)^k (^{2k}_k)}{(k+1)2^{2k + 3/2}}$, а  $a(0,4k+2 \,|\, 0) = 0$ при целых $k>0$. Тогда из предложения \ref{prop} получаем $$P(3,4k+1 \,|\, 3) = 2|a(0,4k \,|\, 0)|^2$$, а $$P(3,4k+3 \,|\, 3) = 2|a(0,4(k+1) \,|\, 0)|^2.$$ Так как $$\sum_{t = 1}^\infty P(0,t \,|\, 0) = \frac{2}{\pi}$$ по теореме \ref{tm}, то $$\sum_{t \in \ZZ}P(3,t \,|\, 3) =$$ $$= \sum_{t > 3} 2|a(0,t+1 \,|\, 0)|^2 + \sum_{t > 3} 2|a(0,t-1 \,|\, 0)|^2 + P(3,3 \,|\, 3) = $$ $$= 2 \left(\sum_{t = 1}^\infty P(0,t \,|\, 0) - P(0,2\,|\, 0) - P(0,4\,|\, 0)\right)+$$ $$ +  2\left( \sum_{t = 1}^\infty P(0,t \,|\, 0) - P(0,2\,|\, 0)\right) + P(3,3 \,|\, 3)=$$ $$ = 2 \left( \frac{2}{\pi} - \frac{1}{2} - \frac{1}{8} \right) + 2\left( \frac{2}{\pi} - \frac{1}{2}\right) + \frac{1}{4} = \frac{8}{\pi} - 2.$$

Остальные равенства в теореме прямо следуют из теоремы 1 и лемм 2 и 3.
\end{proof}





\section*{Вариации}



В заключение докажем еще одну реккурентную формулу.

%\begin{thm}
%\label{t} Для любого $n>3$ выполнено
% $$a(0, 2n \,|\,  0)= \sum_{x = 2}^{2n-1} 2^{-x/2}\mathrm{Im}\,a(x,2n-x \,|\,  0))=$$ $$ = - \sum_{x = %2}^{2n-3}2^{-x/2 - 1 }  \mathrm{Re}\, a(x,2n-2-x\,|\,  %0).$$
%\end{thm}


\begin{thm} 
\label{t}
Для любых целых $x_0 \leq 0$ и $n > \max\{1 - x_0,2\}$ выполнено
 $$a(x_0, 2n + x_0 \,|\,  x_0)= \sum_{x = 2}^{n} 2^{-x/2}\mathrm{Im}\,a(x_0 + x, 2n-x + x_0 \,|\,  x_0)=$$ $$ = - \sum_{x =  2}^{n - 1}2^{-x/2 - 1 }  \mathrm{Re}\, a(x_0 + x, 2n - 2 - x + x_0\,|\,  x_0).$$
\end{thm} 
 
 
\begin{rem} 
Для модели без поглощения (см. начало раздела ''Определение модели'') численный эксперимент подсказывает похожее равенство, отличающееся лишь степенью двойки во второй сумме и пределами суммирования: $$a(0, 2n)= \sum_{x = 2}^{n} 2^{-x/2}\mathrm{Im}\,a(x,2n-x)) = - \sum_{x = 2}^{n-1}2^{-x/2}  \mathrm{Re}\, a(x,2n-2-x).$$ Это показывает, что теорема \ref{t} не может быть напрямую выведена из реккурентного соотношения \cite[Предложение 5]{Skopenkov}, так как это соотношения одинаково для моделей без поглощения и с поглощением. Здесь первое равенство доказывается аналогично лемме \ref{bug}, а второе мы не умеем доказывать.
\end{rem}

Первое равенство теоремы \ref{t} почти очевидно.

\begin{lem} 
\label{bug}
Для любого $x_0 \leq 0$ и $n> -x_0$ выполнено $$a(x_0, 2n + x_0 \,|\,  x_0)= \sum_{x = 2}^{n} 2^{-x/2}\mathrm{Im}\,a(x_0 + x, 2n-x + x_0 \,|\,  x_0).$$
 \end{lem}
 
 \begin{proof}
 Назовём \emph{главной диагональю} множество точек, из которых можно попасть в точку $(x_0, 2n + x_0)$, двигаясь все время влево-вверх, то есть множество точек с координатами $(x_0 + x,2n-x + x_0)$, где $x$ пробегает целые неотрицательные числа. Для доказательства достаточно заметить, что путь шашки, дающий вклад в $a(x_0, 2n + x_0 \,|\,  x_0)$ приходит в точку $(x_0, 2n + x_0)$ справа-снизу, а значит он обязан проходить по главной диагонали. Легко видеть, что как только путь попадает на главную диагональ, он движется в точку $(x_0, 2n + x_0)$ в одном направлении. При этом очевидно, что в точку $(x_0 + 1, 2n + x_0 - 1)$ описанный путь прийти слева-снизу не может, так как в таком случае он проходит через точку $(x_0 , 2n + x_0 - 2)$. Остается заметить, что при $x>n$ путей через точку $(x_0 + x, 2n-x + x_0)$ не существует, а при $x \leq n$ и $n > -x_0$ все слагаемые в правой части определены.
 \end{proof}


Для доказательства второго равенства в теореме \ref{t} нам потребуется несколько новых обозначений. Каждому пути $s$ шашки мы сопоставим последовательность из нулей и единиц, записывая "$1$"$ $ после каждого хода вправо-вверх и "$0$"$ $ после хода влево-вверх. Назовем сопоставленную пути $s$ последовательность его \emph{двоичной записью}.

Обозначим через $M(x,t)$ множество путей шашки, начинающихся в точке $(0,0)$ с хода вправо-вверх, заканчивающихся в точке $(x,t)$ и не пересекающих прямую $x=x_0$, кроме быть может, начальной и конечной точки, двоичная запись которых не содержит подпоследовательностей $11000$ или $10100$.

\begin{lem}
\label{lM}
 При любыx $x,t > 0$ и $x_0 \leq 0$ верно, что $a(x,t \,|\, x_0 ) =  \sum_{s \in M(x,t)} a(s).$
 \end{lem}
 


 
\begin{proof}
 Обозначим через $A_1$ множество путей шашки, начинающихся в точке $(0,0)$ с хода вправо-вверх, заканчивающихся в точке $(x,t)$ и не пересекающих прямую $x=x_0$, кроме быть может, начальной и конечной точки, в двоичной записи которых встречается подпоследовательность $11000$, причём впервые она встречается не позже $10100$, если читать слева направо. Аналогично  обозначим через $A_0$ множество путей, в двоичной записи которых встречается подпоследовательность $10100$, причём впервые она встречается не позже $11000$. 
 
 Построим биекцию множества  $A_1$ и множества $A_0$. Пусть путь $s \in A_1$ имеет двоичную запись $ a_1 ... a_i 11000 a_{i+6} ... a_t$, и последовательность  $ a_1 ... a_i$ не содержит подпоследовательности $11000$ или $10100$. Тогда отобразим $s$ в путь $s'$, имеющий запись $ a_1 ... a_i 10100 a_{i+6} ... a_t$. Легко понять, что $s' \in A_0$. Покажем, что это сопоставление --- биекция. Предположим, что пути $s_1$ с записью $ a_1 ... a_i 11000 a_{i+6} ... a_t$ и $s_2$ с записью $ b_1 ... b_k 11000 b_{k+6} ... b_t$ отобразились в один путь $s'$, причём $i<k$. Тогда в записи пути $s'$ есть две пересекающихся подпоследовательности $10100$, иначе $ b_1 ... b_k$ содержит $11000$, что противоречит построению. Однако очевидно, что две подпоследовательности $10100$ в одной двоичной записи пересекаться не могут. Также из того что $x_0<0$ очевидно, что в каждый путь содержащий $10100$ переходит какой-либо путь содержащий $11000$. Значит, полученное сопоставление --- биекция. Для доказательства леммы остается заметить, что $a(s) = -a(s')$, так как $s'$ содержит на два поворота больше, а значит, $$a(x,t,\,|\, ,x_0) =  \sum_{s \in M(x,t)} a(s) + \sum_{s \in A_1} a(s) + \sum_{s \in A_0} a(s) = \sum_{s \in M(x,t)} a(s).$$
\end{proof}




 
\begin{lem}
\label{notM}
 Для любого $x_0 > 0$ и $n > 1 - x_0$ или $n>2$ при $x_0 = 0$ двоичная запись любого пути из множества $M(x_0,2n + x_0)$ заканчивается последовательностью $0010...0$, в конце которой два или больше нулей . 
\end{lem}





 \begin{proof}
 
 Заметим, что если путь пришел в точку $(x_0,2n + x_0)$, то, так как $x_0<0$, он пришел справа, а значит имеет конец $0..0$ содержащий хотя бы два $0$, иначе путь проходил бы через точку  $(x_0,2n + x_0 - 2)$. Если путь заканчивается хотя бы тремя $0$ и при этом лежит в $M(x_0,2n + x_0)$, то его конец имеет вид $0010...0$, иначе он содержал бы $11000$ или $10100$, что противоречило бы построению множества $M(x_0,2n + x_0)$, или имел бы вид $10...0$, но тогда $n = 1 -x_0$, что противоречило бы условию леммы. Остается рассмотреть случай, когда путь заканчивается двумя $0$. Тогда его конец не может иметь вид $1100$, так как в таком случае путь проходит через точку $(x_0,2n + x_0 - 4)$. Также путь не может заканчиваться $10100$, а значит, заканчивается $00100$. Мы полагаем, что все рассматриваемые выше точки отличны от $(0,0)$, что верно при $x_0 \not = 0$ или $n>2$.
\end{proof}
 
  \begin{proof}[Доказательство теоремы \ref{t}] По лемме \ref{lM} имеем $$a(x_0,2n + x_0 \,|\, x_0) =  \sum_{s \in M(x_0,2n + x_0)} a(s),$$ а по лемме \ref{notM} двоичная запись любого пути из $M(x_0,2n + x_0)$ заканчивается последовательностью $0010...0$. Тогда пути $s \in M(x_0,2n + x_0)$ с двоичной записью $a_1 ... a_{2n-x_0-x-3} 0 0 1 0 .. 0$ сопоставим путь $s' \in M(x_0 + x,2n-x_0-x-2)$ с двоичной записью $a_1 ... a_{2n-x_0-x-3} 0 $. Суммируя по всем путям, получаем второе равенство из теоремы. Первое равенство следует из леммы \ref{bug}. 
\end{proof}

\section*{Благодарности}

 Работа поддержана грантом Фонда развития теоретической физики и математики ''Базис'' № 21-7-2-19-1. 


\begin{thebibliography}{5}


\bibitem{Ambainis}
A.~Ambainis, E.~Bach, A.~Nayak, A.~Vishwanath, J.~Watrous,   One-dimensional quantum walks, Proc. of the 33rd Annual ACM Symposium on Theory of Computing (2001), 37--49.


\bibitem{Feynman-Gibbs} R.P.~Feynman,  A.R.~Hibbs, Quantum mechanics and path integrals, New York, McGraw-Hill, 1965. %pp. 34.

\bibitem{Kempe-09} J.~Kempe, Quantum random walks: an introductory overview, Contemp. Phys. 50:1 (2009), 339-359. %DOI: 10.1080/00107510902734722

\bibitem{K-v_S-v}
F. Kuyanov, A. Slizkov, Feynman checkers: number-theoretic properties, submitted (2022), arXiv:2210.07306.


\bibitem{Liu} C. Liu, N. Petulante, Weak limits for quantum walks on the half-line, International Journal of Quantum Information, 11.06(2013): 1350054.

\bibitem{Nov}
I. Novikov, Feynman checkers: the probability to find an electron vanishes nowhere inside the light
cone, Rev. Math. Phys. 34:07 (2022), 2250020, arXiv:2010.05088.

\bibitem{Ozh}
F. Ozhegov, Feynman checkers: external electromagnetic field and asymptotic properties, submitted (2022), arXiv:2209.00938.

\bibitem{Pakharev-Skopenkov-Ustinov}  M.~Skopenkov, A.~Pakharev, A.~Ustinov, Through the resisting net, Mat. Prosv. 3rd ser., 18 (2014), 33--65.


\bibitem{Skopenkov_Ustinov-2}
M. Skopenkov, A. Ustinov, Feynman checkers: lattice quantum field theory with real time, submitted (2022), arXiv:2208.14247.

\bibitem{Skopenkov}
M. Skopenkov, A. Ustinov, Feynman checkers: towards algorithmic quantum theory, Russian Math. Surveys 77:3(465) (2022), 73-160.


\bibitem{Venegas-Andraca-12}
S.E.~Venegas-Andraca, Quantum walks: a comprehensive review, Quantum Inf. Process. 11 (2012), 1015--1106. %https://doi.org/10.1007/s11128-012-0432-5







\end{thebibliography}

\end{document}

