Expected range of simple random walk in $\mathbb{Z^2}$

582 Views Asked by At

Let $(Y_k)_{k\geq0}$ be a simple random walk process. The range of an $n$-step random walk, $R_n$, is a random variable that characterizes the number of distinct points visited at time $n$: $$R_n=|\{Y_0, Y_1 \dots Y_n \}|$$ Prove that if $(Y_k)_{k\geq0}$ is a SRW on $\mathbb{Z^2}$ then $$ \mathbb{E}(R_n)\asymp \frac{n}{\log n},$$

where $f(n)\asymp g(n)$ means that $\exists c, C \in (0, \infty): c<\frac{f(n)}{g(n)}<C$.

The desired result is mentioned e.g. in this article:

'The simple random walk (SRW) in $\mathbb{Z^2}$visits about $n/ \log n$ points by time $n$.'

On the other hand unfortunately there is no explanation or reference to this assertion. Do you know a relatively simple (e.g. using Green's function, reflection principle, CLT etc.) proof to this claim?

Thank you very much for your help in advance!