Distribution of random walk on $\mathbb{N}$ with a reflective wall at -1

Question

We consider a $n$ steps random walk on $\mathbb{N}$, starting at $X_0 = 0$.

Each step is:

• Uniformly sampled from $\{-1, 1\}$ if $X > 0$
• Uniformly sampled from $\{0, 1\}$ if $X = 0$.

The final position $X_n$ is given by the sum of all $n$ steps, and can only be positive as the walker can only stays at $0$ or go to $1$ when located at $0$. The main difference with a classical random walk is that, at the origin, the walker as a $\frac{1}{2}$ probability of not moving.

What is the probability distribution of such random walk?

Especially, what is the probability that the walker ends up at the origin $X_0 = 0$ after $n$ steps? And what is the probability that the walker ends up at any point $p \in \mathbb{N}$ after $n$ steps?

Answer 1

We can model the problem by a Markov chain with states $S = \{0, 1, 2, ..., n\}$. Each state of the Markov chain represent a position that the walker can reach, so we don't need more than $n$ states (its impossible to reach further with $n$ steps).

The transition matrix would be as follows:

$$ T = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 & 0 & ...\\ 0.5 & 0 & 0.5 & 0 & 0 & ... \\ 0 & 0.5 & 0 & 0.5 & 0 & ... \\ 0 & 0 & 0.5 & 0 & 0.5 & ... \\ ... & ... & ... & ... & ... & ... \end{pmatrix} $$

If we are interested in the location after $n$ steps, we can define this matrix with a size $n \times n$.

Then, to compute the probability $P_{ij}(n)$, the probability to reach the state $j$ from the state $i$ after $n$ steps, we can use the Chapman-Kolmogorov equation:

$$ P_{ij}(n) = T^n_{ij} $$

Answer 2

For $n\ge 0$ and $k \ge 0$, let $f(n,k)$ be the number of ways to end at position $k$ after $n$ steps.

For $n=0$, we have $f(0,0)=1$, and $f(0,k)=0$ if $k>0$.

So now assume $n>0$.

For $k>0$, to be at position $k$ after $n$ steps, we would have to be at $k-1$ or $k+1$ after $n-1$ steps, and then take a step in the correct direction. So $f(n,k)=f(n-1,k-1)+f(n-1,k+1)$ for $k>0$.

To be at position $0$ after $n$ steps, we would have to be at $0$ or $1$ after $n-1$ steps and then take a step in the correct direction (or not take a step at all). So $f(n,0)=f(n-1,0)+f(n-1,1)$.

Putting this together we have $$f(n,k)=\left\{\begin{array}{clr} 1 & {\rm if } \; n=k=0 \\ 0 & {\rm if} \; k>n \\ f(n-1,0)+f(n-1,1) & {\rm if} \; n>0, k=0 \\ f(n-1,k-1)+f(n-1,k+1)& {\rm if} \; n>0, 0<k\le n \end{array}\right.$$

One may note that the recursion here looks suspiciously similar to Pascal's triangle. And in fact if you make a table with $n$ down the side and $k$ along the top, you see the entries of Pascal's triangle coming out in each row, but in decreasing order (e.g. the $5$ row goes $10,10,5,5,1,1$).

This leads to the conjecture that $f(n,k)= \left( \begin{array}{c} n \\ \left\lfloor\frac{n-k}{2}\right\rfloor \end{array} \right) $

This conjecture may be established by induction, using the following (and leaving out some details): $$\begin{array}{ccl}f(n,k) & = & f(n-1,k-1)+f(n-1,k+1)\\ &=& \left( \begin{array}{c} n-1 \\ \left\lfloor\frac{n-k}{2}\right\rfloor \end{array} \right) + \left( \begin{array}{c} n-1 \\ \left\lfloor\frac{n-k}{2}\right\rfloor -1 \end{array} \right) \\ &=& \left( \begin{array}{c} n \\ \left\lfloor\frac{n-k}{2}\right\rfloor \end{array} \right) \end{array}$$

Putting this all together gives that the probability of being at position $k$ after $n$ steps is given by $$P(n,k)= \frac{ \left( \begin{array}{c} n \\ \left\lfloor\frac{n-k}{2}\right\rfloor \end{array} \right) }{2^n} $$

In particular, the probability of being at position $0$ after $n$ steps is given by

$$P(n,0)= \frac{ \left( \begin{array}{c} n \\ \left\lfloor\frac{n}{2}\right\rfloor \end{array} \right) }{2^n} $$