3.A. Random Walks

Appendix 3.A. Intro into project: Random Walks

  1. Walk Problem
  2. Absorption problem

Project: Walk Problem

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. 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$.

Remark 1. This is a correct scaling or we will not get any PDE.

Remark 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}

Remark 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).

Remark 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.

Task 2. (Main task) Multidimensional case. Solution (in due time when we study). BVP. More generalization (later).

Absorption problem

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. 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.

Remark 5. Here $p=p(x)$ is a probability and (\ref{eq-3.A.7}) does not hold.

Task 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.

$\Leftarrow$  $\Uparrow$  $\Rightarrow$