Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a simple random walk on the integers with a reflecting barrier at $0$. What is the expected time the walk spends in the set $\{0, \ldots, k\}$ in the first $n$ steps?

I'm curious about how the answer scales with $n,k$, and don't really care about the constants.

share|improve this question
If I understand right your problem, it's equivalent to a symmetric random walk, in which we are instered in counting the instants in which the walk has a value in the {-k.. k} range... agree? –  leonbloy Jan 13 '11 at 2:47
add comment

1 Answer

up vote 5 down vote accepted

As a commenter noted, this is the same as the total time spent in $[-k,k]$ by a symmetric random walker in the first $n$ steps. The probability distribution for large $n$ becomes $P(x) = \frac{2}{\sqrt{2\pi n}}\exp\left(-\frac{x^2}{2n}\right)$ for $x$ with the same parity as $n$, and is always $P(x) = 0$ for $x$ with opposite parity. The probability of being in a fixed interval $[-k,k]$ after exactly $n$ steps is therefore $\Theta\left(k/\sqrt{n}\right)$ as $n \rightarrow \infty$, as the exponential term becomes irrelevant. Summing this probability over steps $1, 2, ... , n$ gives the desired result, which is $\Theta\left(k\sqrt{n}\right)$.

share|improve this answer
add comment

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.