<link href="../markdown.css" rel="stylesheet"></link>

<title>3.A. Random Walks</title>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_HTML">
    MathJax.Hub.Config({
        tex2jax: {
            inlineMath: [ ['$','$'], ["\\(","\\)"] ],
            displayMath: [ ['$$','$$'], ["\\[","\\]"] ],},
        TeX: {equationNumbers: {
            autoNumber: "AMS"
          },Augment: {  Definitions: {
           macros: {
             overbracket:  ['UnderOver','23B4',1],
             underbracket: ['UnderOver','23B5',1],
           }
         }}},
    });
</script>

##[Appendix 3.A. Intro into project: Random Walks](id:sect-3.A.)
----------------


> 1.  [Walk Problem](#sect-S3.A..1)
> 2.  [Absorption problem](#sect-S3.A.2)

###[Project: Walk Problem](id:sect-3.A.1)

Consider a 1D-grid with a step $h\ll 1$ and also consider grid in time with a step $\tau\ll 1$. So, $x\_n=nh$ and $t\_m=m\tau$.

Assume that probabilities to move to the left and right (to the next point) for one time tick are $q\_L$ and $q\_R$ respectively.

Then denoting by $p^m\_n$ the probability to be at time  $t\_m$ at point $x\_n$ we get equation
\begin{equation}
p^m\_n = p^{m-1}\_{n-1}q\_R + p^{m-1}\_n (1-q\_L-q\_R)+p^{m-1}\_{n+1}q\_L.
\label{eq-3.A.1}
\end{equation}
One can rewrite it as
\begin{multline}
p^m\_n-p^{m-1}\_n = p^{m-1}\_{n-1}q\_R - 2p^{m-1}\_n (q\_L+q\_R)+p^{m-1}\_{n+1}q\_L=\\\\[3pt]
K\bigl(p^{m-1}\_{n-1}-p^{m-1}\_n+p^{m-1}\_{n-1}\bigr)-
L \bigl(p^{m-1}\_{n+1} -  p^{m-1}\_{n-1} \bigr)
\qquad\label{eq-3.A.2}
\end{multline}
where we used notations $K=\frac{1}{2} (q\_L+q\_R)$ and $L=\frac{1}{2} (q\_R-q\_L)$.

**[Task 1.](id:task-3.A.1)**
Using Taylor formula and assuming that $p(x,t)$ is a smooth function prove that
\begin{gather}
\Lambda p:= \frac{1}{h^2}\bigl(p \_{n+1} -2 p \_n + p\_{n-1} \bigr)=
 \frac{\partial^2 p}{\partial x^2}+O(h^2),\label{eq-3.A.3}\\\\[3pt]
 D p:= \frac{1}{2h}\bigl(p \_{n+1} - p\_{n-1} \bigr)=
 \frac{\partial  p}{\partial x}+O(h^2),\label{eq-3.A.4}\\\\[3pt]
 \frac{1}{\tau}\bigl(p ^{m} - p\_{m-1} \bigr)=
 \frac{\partial  p}{\partial t}+O(\tau).\label{eq-3.A.5}
\end{gather}
Then (\ref{eq-3.A.2}) becomes after we neglect small terms
\begin{equation}
\frac{\partial  p}{\partial t} =
\lambda \frac{\partial^2 p}{\partial x^2} -\mu \frac{\partial p}{\partial x} \label{eq-3.A.6}
\end{equation}
where $K=\lambda \tau/h^2$, $L= \mu \tau/2h$.
<!--\end{task}-->

**[Remark 1.](id:remark-3.A.1)**
This is a correct scaling or we will not get any PDE.
<!--\end{remark}-->

**[Remark 2.](id:remark-3.A.2)**
 Here $p=p(x,t)$ is not a probability but *a probability density*: probability to be at moment $t$ on interval $(x,x+dx)$ is
$\mathsf{P}(x< \xi(t)\< x+dx)=p(x,t)\,dx$. Since
$\sum\_{-\infty\< n \< infty} p^m_n=1$ we have
\begin{equation}
\int\_{-\infty}^\infty p(x,t)\,dx=1.
\label{eq-3.A.7}
\end{equation}
<!--\end{remark}-->

**[Remark 3.](id:remark-3.A.3)** The first term on the right of (\ref{eq-3.A.6}) is *a diffusion term*; in the case of symmetric walk $q\_L=q\_R$ only it is present:
\begin{equation}
\frac{\partial  p}{\partial t} =
\lambda \frac{\partial^2 p}{\partial x^2}.
\label{eq-3.A.8}
\end{equation}
The second term on the right of (\ref{eq-3.A.6}) is *a convection term*; moving it to the left and making change of coordinates $t\_{new}=t$, $x_{new}=x-\mu t$ we get in this new coordinates equation (\ref{eq-3.A.8}). So this term is responsible for the shift with a constant speed $\mu$ (on the top of diffusion).
<!--\end{remark}-->

**[Remark 4.](id:remark-3.A.4)**
(\ref{eq-3.A.2}) is a *finite difference equation* which is a *finite difference approximation* for PDE (\ref{eq-3.A.7}). However this approximation is *stable* only if $\tau \le \frac{h^2}{2\lambda}$. This is a fact from *numerical analysis*.
<!--\end{remark}-->

**[Task 2.](id:task-3.A.2)** (Main task)
Multidimensional case. Solution (in due time when we study). BVP. More generalization (later).
<!--\end{task}-->

###[Absorption problem](id:sect-S3.A.2)

Consider $1D$-walk  (with the same rules) on a segment $[0,l]$ with both *absorbing* ends. Let $p\_n$ be a probability that our walk will end up at $l$ if started from $x\_n$. Then
\begin{equation}
p\_n = p\_{n-1}q\_L + p\_{n+1}q\_R + p\_n (1-q\_L-q\_R).
\label{eq-3.A.9}
\end{equation}

**[Task 3.](id:task-3.A.3)**
Prove limiting equation
\begin{equation}
0 =
\lambda \frac{\partial^2 p}{\partial x^2} -\mu \frac{\partial p}{\partial x}.
\label{eq-3.A.10}
\end{equation}
Solve it under boundary conditions $p(0)=0$, $p(l)=1$. Explain these boundary conditions.
<!--\end{task}-->


**[Remark 5.](id:remark-3.A.5)**
Here $p=p(x)$ is a probability and (\ref{eq-3.A.7}) does not hold.
<!--\end{remark}-->

**[Task 4.](id:task-3.A.4)**  (Main task)
Multidimensional case: in the domain with the boundary. Boundary conditions (there is a part $\Gamma$ of the boundary and we are interested in the probability to end up here if started from given point). May be: Generalization: part of boundary is reflecting.
<!--\end{task}-->

---------------

[$\Leftarrow$](S3.2.html)&nbsp;&nbsp;[$\Uparrow$](../contents.html)&nbsp;&nbsp;[$\Rightarrow$](../Chapter4/S4.1.html)
