Consider a simple random walk $S_n$ on one dimension, starting at $0$. In this case, $S_n$ fluctuates between $-\infty$ and $\infty$, but intuition says that it might stay more often in an interval surrounding the origin. To formulate this, consider an interval $A=[-d, d]$, and introduce a random variable $1_A(S_n)=1$ if $S_n\in A$ and $0$ otherwise.

Consider for some $f\in [0,1]$, the probability

$$Pr[\lim_{n\rightarrow \infty} \frac{\sum_{j=0}^n 1_A(S_j)}{n}\geq f]$$

I am not quite sure whether the definition is sensible, as the limit might not exist, but in that case, one could replace by $\lim\sup$ or $\lim\inf$.

The question is, what's the property of this probability?

Note that for finite ergodic Markov chains, similar problems can be answered easily by looking at stationary distributions, but for here, essentially we have a null-recurrent Markov chain.

  • 2
    $\begingroup$ This is not what you want to consider, because $\dfrac{\sum_{j=0}^n 1_A(S_j)}{n+1}$, which is the fraction of time $\le n$ the process spends in the interval $A$, goes to $0$ a.s. as $n \to \infty$. $\endgroup$ Jul 7, 2016 at 0:59
  • 1
    $\begingroup$ Your intuition is wrong. Just wait until the walk reaches some other interval $B$ of the same length as $A$ and then forget the past. It can only be that in the limit the walk spends as much time in $B$ as it does in $A$, as $n\to\infty$. $\endgroup$ Jul 7, 2016 at 2:13
  • $\begingroup$ check the robbins kallianpur law $\endgroup$
    – user83457
    Jul 7, 2016 at 8:00
  • $\begingroup$ @RobertIsrael, it is well possible, but how to prove that? $\endgroup$
    – maomao
    Jul 7, 2016 at 13:20
  • $\begingroup$ I saw an answer but not it is deleted now, could someone explain why it is deleted? thanks. $\endgroup$
    – maomao
    Jul 7, 2016 at 13:56

1 Answer 1


This is an answer to the reformulation of the problem in comments. Using Markov's inequality for $x>0$, we obtain \begin{align*} \mathbb P\left(\frac{\sum_{j=0}^n I_A(S_j)}{n}>x\right) &\le \mathbb E\frac{\sum_{j=0}^n I_A(S_j)}{nx} = \frac{1}{nx}\sum_{j=0}^n \mathbb P(S_j\in A )\le \frac{1}{nx}\sum_{j=0}^n \frac{C}{\sqrt {j+1}}\\ &\le C_1\frac{\sqrt n}{nx}\to 0, \quad n\to \infty. \end{align*} Here, I used an estimate for concentration function $\mathbb P(S_j\in [-d,d])\le C(2d+1)/\sqrt{j}$ for all $j$ and a constant $C$ that does not depend on $j$ and $d$, see Theorem 9 in Chapter 3 of Petrov's book "Sums of independent random variables".

Clearly, $\sum_{j=0}^n I_A(S_j)$ is of order $\sqrt n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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