4
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ For the sake of clarity: since only left and right steps are allowed, are you referring to a unidimensional random walk? $\endgroup$ – Anatoly Dec 17 '15 at 15:24
  • $\begingroup$ 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. $\endgroup$ – Kayle of the Creeks Dec 17 '15 at 17:02
  • $\begingroup$ 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). $\endgroup$ – JustAskin Dec 17 '15 at 17:12
  • $\begingroup$ 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)$. $\endgroup$ – Kayle of the Creeks Dec 17 '15 at 17:32
  • $\begingroup$ 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$. $\endgroup$ – A.S. Dec 17 '15 at 19:14
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.