4
$\begingroup$

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.

  • 2
    If I understand right $y$our $p$roblem, it's equivalent to a s$y$mmetric random walk, in which we are instered in counting the instants in which the walk has a value in the `{-k.. k}` range... agree?2011-01-13

1 Answers 1

5

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