Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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? – Douglas Zare Apr 2 '11 at 0:02
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. – Douglas Zare Apr 2 '11 at 0:28
@Douglas Thanks, I hadn't noticed that the chain is periodic. – Byron Schmuland Apr 2 '11 at 0:33
up vote 1 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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