0

This weekend my SO and I were trying to analyze a problem which boiled down to a 1-dimensional random walk with a floor at 0. That is, starting at 0, move $\{-1, +1\}$ with probability $\frac 1 2$ each, but anything which would go to -1 instead remains at 0, without hindering a later move to 1.

What are the properties of this form of walk? Specifically, after $n$ steps, what does the probability distribution look like? Expected value?

We worked out (by hand) the results for $n=3$ thru $n=6$, but ideally we'd like to see what it looks like when $n=52$.

Omar Shehab
  • 539
Bobson
  • 113

1 Answers1

2

Calculating a few values by hand, it seems that the probability of being at $m$ after $n$ steps is $$ p_{n,m}=\frac1{2^n}\binom{n}{\lfloor(n-m)/2\rfloor} $$ for $m\leq n$. Indeed we can verify this inductively using the recurrence $$ p_{n+1,m}=\begin{cases} (p_{n,m-1}+p_{n,m+1})/2&\text{if }m>0,\\ (p_{n,m}+p_{n,m+1})/2&\text{if }m=0. \end{cases} $$

stewbasic
  • 6,131