# random walk on the nonnegative integers

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.

-
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

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