How fast does the range of simple random walk grow?

Consider a discrete-time simple random walk $(X_t{)}_{t\ge 0}$ on an infinite, connected, locally finite simple graph $G$, and let $$R_t:=\mathrm{\mid }\{X_0,\dots ,X_t\}\mathrm{\mid }$$ denote its range. The main result of this revised note is that positive vertex isoperimetry already forces linear expected range, with no bounded-degree assumption: if $${\iota }_V(G):=\underset{0<\mathrm{\mid }S\mathrm{\mid }<\mathrm{\infty }}{\inf }\frac{\mathrm{\mid }{\mathrm{\partial }}_{V}S\mathrm{\mid }}{\mathrm{\mid }S\mathrm{\mid }}>0,$$ then ${\text{E}}_x{R}_t\ge c(G)(t+1)$ for every starting vertex $x$ and every $t\ge 0$. The proof is direct: vertex expansion implies an unweighted Dirichlet inequality, which in turn gives a uniform positive escape probability from every vertex. We also record a finite counterpart: in an $n$-vertex finite vertex expander, the expected hitting time of an independent stationary random target is $\mathrm{\Theta }(n)$, again with no restriction on degrees. We also record a chain of geometrically growing lollipops for which $${\text{E}}_o{R}_t\asymp t^{1\mathrm{/}3},$$ so the subdiffusive exponent $1\mathrm{/}3$ need not be accompanied by superdiffusive oscillations. In particular, for this graph the lower and upper logarithmic exponents of ${\text{E}}_o{R}_t$ are both equal to $1\mathrm{/}3$. Finally, since Barnes and Feige proved the sharp universal estimate $\text{E}{T}_n=O(n^3)$ for the $n$-th discovery time, we move our elementary proof of the weaker bound $\text{E}{T}_n=O(n^3\log n)$ to a later section as a short self-contained argument with a logarithmic loss. We close with a related bounded-degree mixing statement: if the lazy walk has worst-case mixing time $m$, then at least $c\sqrt{m}$ starting vertices are still noticeably unmixed at time $\lfloor m\mathrm{/}2\rfloor$. This final result uses the same commute-time/effective-resistance control of connected sets that appears throughout the paper.