Distribution of random walk on $\mathbb{N}$ with a reflective wall at -1 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?
 A: 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} $$
A: 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}
$$
