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$ – Robert Israel Jul 7 '16 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$ – Brendan McKay Jul 7 '16 at 2:13
  • $\begingroup$ check the robbins kallianpur law $\endgroup$ – user83457 Jul 7 '16 at 8:00
  • $\begingroup$ @RobertIsrael, it is well possible, but how to prove that? $\endgroup$ – maomao Jul 7 '16 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 '16 at 13:56

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, privacy policy and cookie policy

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