Let's consider a one-dimensional Random Walk. At each time the walker moves of one step to the right with probability $p$ and to the left with probability $q$, with $p+q=1$. The walk is not symmetric, then $p \neq q$

How can I find the explicit formula of the probability to hit for the first time one of the two walls located in $x=n$ and $x=-n$ at time $t$, given that the walk started from $x=0$ at time $t=0$?

  • $\begingroup$ Is time t the sane as the number of steps? $\endgroup$ – DJohnM Mar 14 '13 at 19:32
  • $\begingroup$ yes, every time the walker moves, time increases of one unit. $\endgroup$ – QuantumLogarithm Mar 14 '13 at 19:37

In order for the walker to reach position $x$ at time $t$. A necessary condition is $x \equiv t \pmod 2$. Assume this is true, the walker have make $s = \frac{t+x}{2}$ steps forward and $t - s = \frac{t-x}{2}$ steps backward.

In the absence of walls, the probablity for the walker to be at position $x$ is given by

$$P_{free}(x,t) = \operatorname{Prob}\left[\,X(t) = x\,\right] =\binom{t}{\frac{t+x}{2}} p^{\frac{t+x}{2}} q^{\frac{t-x}{2}} $$

In the presence of walls, the probability for the walker at position $x$ and never hit the walls before will be modified to: $$\begin{align} P(x,t) &= \operatorname{Prob}\left[\,X(t) = x : -n < X(t') < n,\,\forall t' < t\,\right] \\&=\sum_{r = \lceil\frac{x-t}{2n}\rceil}^{\lfloor\frac{x+t}{2n}\rfloor} (-1)^{r} \binom{t}{\frac{t+x-2rn}{2}} p^{\frac{t+x}{2}} q^{\frac{t-x}{2}} \end{align}$$

The formula can be derived using reflection principle. It is equivalent to start the random walk at time $t = 0$ with $(-1)^r$ phantom walker at position $\pm 2rn$ for each $r \in \mathbb{N}$. The range of summation over $r$ in above formula is limited to those which will actually contribute to $P(x,t)$ at time $t$.

For the walker to hit the wall $\pm n$ at time $t$, we again require $t \equiv n \pmod 2$. Furthermore, the walker must be at position $\pm (n-1)$ at time $t - 1$. In next move,

  • (case $X(t-1) = n - 1$) the walker has a probability $p$ to turn right and hit the right wall.
  • (case $X(t-1) = 1 - n$) the walker has a probability $q$ to turn left and hit the left wall.

This implies the probability for first hit (assume $t \equiv n \pmod 2$) is given by:

$$\begin{align} P_{hit}(t) &= p P(n-1,t-1) + q P(-n+1,t-1)\\ &= \sum_{r = \lceil\frac{n-t}{2n}\rceil}^{\lfloor\frac{n+t-2}{2n}\rfloor} (-1)^{r} \binom{t-1}{\frac{n+t-2rn}{2} - 1} \left( p^{\frac{t+n}{2}} q^{\frac{t-n}{2}} + q^{\frac{t+n}{2}} p^{\frac{t-n}{2}} \right) \end{align}$$ For $t = n + 2k$, we can simplify this to:

$$P_{hit}(n+2k) = \sum_{-\lfloor\frac{k}{n}\rfloor}^{\lceil\frac{k}{n}\rceil}(-1)^r\binom{n+2k-1}{nr+k}(p^n + q^n) (pq)^k$$

  • $\begingroup$ @Did thanks, answer updated. $\endgroup$ – achille hui Mar 15 '13 at 7:31
  • $\begingroup$ +1 on the great answer. I wish to ask for a clarification on the r values. As I understand, we want to include all paths to x that started from zero but want to exclude those that hit the barrier. The reflection principle tells us those could have just as well have come from x=2n. But if we subtract out all the paths that came from 2n, we are over-subtracting. To correct this, any path that touched 2n, we reflect it and start it at 4n and add these back into the sum. We’re again adding too many. So subtract some by reflecting what touched 3n by starting at 6n and so on. Is that the idea? $\endgroup$ – Mathemagical Dec 10 '17 at 14:23
  • $\begingroup$ And another question: there can be paths starting from 0 that would have breached both the upper barrier and the lower barrier. Which way are they getting reflected? As I see it, the negative r values correspond to the lower barrier and positive ones to the upper. Is that right? $\endgroup$ – Mathemagical Dec 10 '17 at 14:28
  • $\begingroup$ What happens in the case where the barriers are not symmetrical, but at n and -m. In that case, start phantom walks at -4m, -2m,0,2n,4n,6n? $\endgroup$ – Mathemagical Dec 10 '17 at 14:30
  • $\begingroup$ @Mathematical 1) About the "subtraction/over-subtraction and add it back", it may be as what you say but I'm not 100% sure. In any event, if one exclude the effect of the boundary, the probability distribution over time satisfies some linear recurrence relation. The key is the relation is translation invariant over space/time. What the reflection principle does is find suitable linear combination of translated copies of the free distribution to fulfill the boundary condition. $\endgroup$ – achille hui Dec 10 '17 at 15:01

The idea is to compute $u(s,x)=\mathbb E_x(s^T)$ for every integer $|x|\leqslant n$ and complex number $|s|\leqslant1$, where $T$ is the first hitting time of $\pm n$. Then $u(s,0)$ is the generating function of the sequence of general term $\mathbb P_0(T=k)$, that is, $u(s,0)=\sum\limits_k\mathbb P_0(T=k)s^k$.

Each family $(u(s,x))_{|x|\leqslant n}$ solves a recursion based on the Markov property of the random walk after one step. More precisely, $u(s,x)=s(pu(s,x+1)+qu(s,x-1))$ for every $|x|\leqslant n-1$. For each fixed $s$ this is a second order linear recursion hence $u(s,x)=av^x+bw^x$ for every $|x|\leqslant n$, where $v$ and $w$ solve the characteristic equation $\xi=s(p\xi^2+q)$. Using the boundary conditions $u(s,\pm n)=1$, one gets $$ a=\frac{w^{-n}-w^n}{v^nw^{-n}-v^{-n}w^n}, \quad b_n=\frac{v^{n}-v^{-n}}{v^nw^{-n}-v^{-n}w^n}. $$ Thus, $u(s,0)=a+b$, that is, after some simplifications, $$ \sum\limits_k\mathbb P_0(T=k)s^k=\frac{1+v^nw^n}{v^n+w^n}=\frac{1+(q/p)^n}{v^n+w^n},\quad v,w=\frac{1\pm\sqrt{1-4pqs^2}}{2ps}. $$ Thus, $$ \sum\limits_k\mathbb P_0(T=k)s^k=s^n\frac{p^n+q^n}{x_n(4pqs^2)}, $$ with $$ x_n(t)=\frac1{2^n}\left(\left(1+\sqrt{1-t}\right)^n+\left(1-\sqrt{1-t}\right)^n\right). $$ Note that $x_n$ is a polynomial with degree $\lfloor n/2\rfloor$ and constant term $1$, hence expanding $1/x_n(t)$ as a series yields every coefficient $\mathbb P_0(T=n+2k)$ for $k\geqslant0$ (the others being zero). More explicitly, $$ x_n(t)=\frac1{2^{n-1}}\sum_{i\geqslant0}{n\choose 2i}(1-t)^i=\sum_{j\geqslant0}(-1)^j\left(\sum_{i\geqslant j}\frac1{2^{n-1}}{n\choose 2i}{i\choose j}\right)t^j=1-z_n(t), $$ hence $$ \mathbb P_0(T=n+2k)=(p^n+q^n)(4pq)^k\times\text{the coefficient of $t^k$ in}\sum_{\ell=0}^kz_n(t)^\ell. $$

  • $\begingroup$ Thanks a lot. Then the coefficients of $t^k$ in $\sum_l^k z_n(t)^l$ should be the same in the formula provided by achille... $\endgroup$ – QuantumLogarithm Mar 15 '13 at 10:04
  • $\begingroup$ @Lorenzo, I've checked. Did's coefficients and my formula generate same set of numbers (at least for $n = 3$ or $5$ and $0 \le k \le 100$). $\endgroup$ – achille hui Mar 15 '13 at 13:18
  • $\begingroup$ @achillehui Thanks for the checking. $\endgroup$ – Did Mar 15 '13 at 15:01
  • $\begingroup$ @Did It is always useful to cross check one's answer against another one derived from completely different approach. This actually helps me to discover a typo in the original formula I wrote down. $\endgroup$ – achille hui Mar 15 '13 at 15:38

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.