I initialize a biased one-dimensional random walk on the positive integers at the origin, $x = 0$, which also serves as a reflecting boundary blocking steps onto the negative integers. Let's say that a $+1$ step for the walker has probability $p$, and an $-1$ step (away from the origin) has probability $q$, where $(p+q) \leq 1$ allowing the walker to stay in place with probability $r = 1 - (p+q)$.

If $p < q$, what is the probability distribution for the walker on the positive integers? What are the implications if $p = q$ provided that a 1D random walk shouldn't be transient?

I've always appealed to simulations when problems like this arise, however, the formulation of this system seems simple enough that I'd imagine an analytic solution should exist (beyond the generalization that we should have exponential increasing hitting times as we linearly increase the distance to the origin)? Is there a formulation of, say, Gambler's ruin that deals with this problem? We can of course eliminate the reflecting boundary by making $p$ the probability of stepping away from the origin, $q$ the probability of stepping towards the origin, etc.

Some additional questions that come to mind: how long would it take a randomly placed walker to achieve this distribution? If we place a walker at the origin, how fair or unfair would it be to assume that the hitting time at some site $x_{t}$ would be proportional to its occupancy probability from the distribution? And, in the case that this is unfair, what does the probability distribution look like for initial hitting times on the positive integers conditioned on the walker being initialized at the origin?

Clarification - A walker can occupy the origin, though here, we have a $-1$ step probability of $q = 0$, the same $+1$ step probability $p$, and a probability of remaining at the origin for a step of $r = (1 - p)$.


For your stable distribution try $$P(X=n) = \left(\frac{p}{q}\right)^n \left(1-\frac{p}{q}\right)$$ which satisfies $P(X=n)= p P(X=n-1) +(1-p-q) P(X=n) + q P(X=n+1)$ and sums to $1$.

If $p=q$ you are in a similar situation to a standard random walk, in that the probability of a return to the origin is $1$, but there is no stable distribution as any initial distribution widens over time.

  • $\begingroup$ How does your solution account for the influence of the reflecting barrier at the origin? $\endgroup$ – PlacidLake Dec 13 '12 at 17:52
  • $\begingroup$ Or is the influence of the reflecting barrier insignificant? $\endgroup$ – PlacidLake Dec 13 '12 at 17:52
  • $\begingroup$ @PlacidLake If the reflecting barrier was not there and $p \lt q$ then the walk would drift negative, eventually permanently. The reflecting barrier does not have much of a substantial effect for $p=q$ beyound an absolute value type of impact. $\endgroup$ – Henry Dec 13 '12 at 17:57
  • $\begingroup$ Shouldn't we expect a positive increase in the probability of occupying states near the reflecting barrier since, by the definition I provide, a walker should have a larger average residency time at the origin? $\endgroup$ – PlacidLake Dec 14 '12 at 4:02
  • $\begingroup$ You can calculate the probability of each position using $P(X_{k+1}=n)= p P(X_k=n-1) +(1-p-q) P(X_k=n) + q P(X_k=n+1)$ and $P(X_{k+1}=0)= (1-q) P(X_k=0) + q P(X_k=1)$ starting for example at $P(X_0=0)=1$ and $P(X_0=n)=0$ for $n\gt 0$ and see what happens as $k$ increases. $\endgroup$ – Henry Dec 14 '12 at 7:13

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.