Expected range of simple random walk in $\mathbb{Z^2}$ 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!
 A: This is an old question, but as someone might stumble on it at some point, let me try to sketch the argument that can be found in details in this paper from Dvoretzky and Erdös.
First, we notice that we can write $\mathbb{E}(R_n) = \sum_{i=1}^n \gamma(i)$, where $\gamma(i)$ denotes the probability that $Y$ visits at time $i$ a point it has not yet visited.
We now compute:
\begin{align*}
\gamma(n) := P(Y_n \neq Y_i, 1 \leq i \leq n-1) &= P \left(\sum_{j=i+1}^n X_j \neq 0, 1 \leq i \leq n-1 \right) \\
&= P \left(\sum_{j=1}^{n-i} X_j \neq 0, 1 \leq i \leq n-1 \right) \\
&= P(Y_i \neq 0, 1 \leq i \leq n-1), \\
\end{align*}
using simple properties of the SRW (independence, symmetry).
Next, we compare $\gamma(i)$ with the probability to return to zero in $i$ steps:
\begin{align}
1 &= \sum_{i=0}^{n-1} P(Y_i=0, Y_j \neq 0 \; \forall j=i+1, \dots, n-1) \nonumber \\
&= \sum_{i=0}^{n-1} P(Y_i=0) P(Y_j-Y_i \neq 0 \; \forall j=i+1, \dots, n-1) \nonumber \\
&= \sum_{i=0}^{n-1} P(Y_i=0) \gamma(n-i). \tag{1}
\end{align}
For $i$ odd the summand is zero, and for the rest we estimate:
$$P(Y_{2i}=0)= \binom{2i}{i}^2 = \frac{1}{\pi i} + o \left(\frac{1}{i} \right).$$
Notice now that
$$\sum_{i=0}^{\lfloor (n-1)/2 \rfloor} P(Y_{2i}=0) = \pi \ln n + O(1)$$
(where the constant can be taken uniform on $n$).
From this we get the lower bound, as from the observation that $\gamma(i+1) \leq \gamma(i)$ we can get from $(1)$ that $\gamma(n) \leq \frac{(1 + o(1))\pi}{\ln n}$, resulting in
$$\mathbb{E}(R_n) = \sum_{i=1}^n \gamma(i) \leq \frac{(1 + o(1))\pi n}{\ln n}$$
when comparing the sum with an integral, for instance.
For the other direction, one can start again from $(1)$ and, for $k \leq n$ arbitrary, bound $\gamma(i) \leq \gamma(n-k)$ for $i \geq n-k$ and $\gamma(i) \leq 1$ for $i < n-k$:
\begin{align*}
1 \leq \sum_{i=0}^{k-1} P(Y_i=0) + \gamma(n-k) \sum_{i=k}^{n-1} P(Y_i=0).
\end{align*}
Then, a similar analysis allows to conclude.
Maybe it is worth mentioning that since $R_n$ is sub-additive, by Kingman's subadditive ergodic theorem there exists $\beta \geq 0$ such that $\mathbb{E}(R_n)/n \xrightarrow[n \to \infty]{}\beta$. In the case of $\mathbb{Z}^2$, this is zero, and the right rate of convergence is $1/\ln n$ as we have seen, but on graphs where the SRW is transient -- such as $\mathbb{Z}^d, d \geq 3$ -- it is strictly positive, which can be seen with an analysis similar to the one above.
