Consider a one-dimensional random walk on the positive integers with:

(1) - A fully reflecting boundary at "x = 0".

(2) - Initiation of the walker at "x = 1".

(3) - A P[+1 Step] / P[RHS Step] probability for the walker less than or equal to the P[-1 Step] / P[LHS Step] probability.

What's the average distance of the walker from the origin and the probability distribution of the walker?

  • $\begingroup$ Do you want the steady state distribution (which doesn't exist by parity, but there is a steady state distribution for odd times and for even times) or the distribution after $n$ steps? $\endgroup$ – Douglas Zare Apr 2 '11 at 0:02
  • $\begingroup$ More correctly, there is a fixed distribution, but the distribution after $n$ steps does not approach the fixed distribution. It oscillates between an even and an odd distribution. $\endgroup$ – Douglas Zare Apr 2 '11 at 0:28
  • $\begingroup$ @Douglas Thanks, I hadn't noticed that the chain is periodic. $\endgroup$ – user940 Apr 2 '11 at 0:33

Added: As Douglas Zare points out, there is no limiting distribution. There are two different limits as time runs over even or odd values. The distribution I describe below is the average of these two, and hence my $\pi_n$ means the long run average probability that the walk finds itself in state $n$.

More formally, I mean that $$\pi_n=\lim_{t\to\infty} {1\over 2} \left(\mathbb{P}(X(t)=n)+\mathbb{P}(X(t+1)=n)\right)$$ where $X(t)$ is the position of the walk at time $t$.

Suppose that the walk has been running for a long time and has reached its equilibrium. We need the probability of a negative step (which I'll call $q$) to be strictly greater than probability of a positive step (which I'll call $p$), otherwise the equilibrium doesn't exist.

The steady state probabilities are $$\pi_n=\cases{{q-p\over 2q} & $n=0$\\[8pt] {q-p\over 2pq} \left({p\over q}\right)^n & $n\geq 1$}$$

Therefore, the average position of the walk (in the long run) is $$\sum_{n=0}^\infty n \pi_n ={1\over 2(q-p)}.$$

When $p$ and $q$ are close together, this number is very large. But as $q$ gets close to 1, the walk spends most of its time jumping back and forth between positions 0 and 1, and its average position is close to $1/2$.


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.