# Probability distribution for 1-dimensional random walk with pauses

The problem could be stated as follows : we have some random walker in an unbounded 1-dimensional lattice, such that there is a 50% chance the walker doesn't move at all, a 25 % chance the walker moves to the left, and 25% chance the walker moves to the right. What is the probability of the walker ending up at some point in the lattice in $N$ steps?

If we now denote the position of the walker as an integer i.e. $1$ would refer moving one site in the lattice to the right, and $-1$ would refer to moving to the left. Then what sort of a distribution would describe the probability that the in $N$ steps the walker would end up at some specific point on the lattice? My intuition says that I am looking for sums of the terms in an $N$-tuple that add up to the point in the site. For instance the tuple described by $(1,1,-1,0,...,0)$ would put the walker at $1$ for the end point.

• For the sake of clarity: since only left and right steps are allowed, are you referring to a unidimensional random walk? – Anatoly Dec 17 '15 at 15:24
• Yes, only motion in the x-axis allowed. This question is related to a 2-dimensional walk where the walk ends when the walker has exceeded some boundary on the x-axis. – Kayle of the Creeks Dec 17 '15 at 17:02
• Let $P_N:\mathbb{Z} \to \mathbb{Q} \cap [0,1]$ denote the probability you are looking for. Then $P_N(x) = |A_N(x)| / 4^N$ where $A_N(x)$ is the set of $\{-1,0,0',1\}$-strings of length $N$ which sum to $x$ (here $0'$ behaves the same as $0$ under addition). – JustAskin Dec 17 '15 at 17:12
• Yes, that is a good formal statement of what I desire. I'd like to find (if there exists) an explicit form for the size of the set $A_N (x)$. – Kayle of the Creeks Dec 17 '15 at 17:32
• Do you need an exact expression? Local CLT yields $P(S_n=m)=\frac 1{\sqrt{2\pi n}\sigma}e^{-(m-n\mu)^2/2n\sigma^2}+o(1/n^{1/2})$ and in your case $\mu=0, \sigma^2=\frac 1 2$. – A.S. Dec 17 '15 at 19:14

## 1 Answer

We consider independent steps in $\mathbb{Z}$ with three possible outcomes $\{-1,0,1\}$ and probabilities

\begin{align*} \mathbb{P}(X=-1)&=\mathbb{P}(X=1)=\frac{1}{4}\qquad\text{and}\qquad\mathbb{P}(X=0)=\frac{1}{2} \end{align*}

We look at walks with length $N\geq 0$ starting from $0$.

These walks follow a trinomial distribution, which is a specific instance of multinomial distributions. \begin{align*} \mathbb{P}(X_{-1}=a,X_{0}=b,X_{1}=c)&=\binom{N}{a,b,c}\left(\frac{1}{2}\right)^{2a+b+2c}\\ &=\frac{N!}{a!b!c!}2^{-2a-b-2c} \end{align*} with $a+b+c=N$ and $a,b,c\geq 0$

The probability to start at $0$ and stop at $K$ after $N$ steps is \begin{align*} \sum_{{a+b+c=N}\atop{{-a+c=K}\atop{a,b,c\geq 0}}}\binom{N}{a,b,c}\left(\frac{1}{2}\right)^{2a+b+2c}\qquad N\geq 0, -N\leq K \leq N \end{align*}

Note: This file presents some basic facts about the trinomial distribution.

• Very nice, thank you! – Kayle of the Creeks Dec 23 '15 at 14:48
• @KayleoftheCreeks: You're welcome! :-) – Markus Scheuer Dec 23 '15 at 14:50