Does there exist a non-recurrent acyclic graph with sublinear expansion? Let $\Gamma$ be a simple, locally finite, acyclic graph. Let $v_0$ be some vertex in $\Gamma$.
We let $X_n$ denote the simple random walk on $\Gamma$ where $X_0 = v_0$. If we almost surely have $\limsup_{n\to\infty} \frac{d(X_0,X_n)}{n}=0$ (using the path metric), does it follow that almost surely $X_t = X_0$ for some $t> 0$?
 A: Here's another idea for a counterexample:
Start with an infinite $3$-regular tree $T$ and for every $d \in \mathbb N$ attach a set of $d$ leaves to every vertex at distance $d$ from $v_0$.
Simple random walk is transient because if we ignore detours (into and out of leaves) we are left with a simple random walk on $T$. On the other hand, the walk will get slower as it diverges: if we are at distance $d$ from $v_0$, it will on average take $O(d)$ steps until we take a step along an edge of $T$, so we expect to need $\Omega(d^2)$ steps to reach a vertex at distance $d$.
A: For a spherically symmetric tree (where all vertices at the same distance from the root have the same degree) it is well known that transience is equivalent to $ \sum_n |T_n|^{-1} <\infty$, (where $T_n$ is level $n$ of the tree) since that means the resistance from the root to infinity is finite. On the other hand, the Varopolous-Carne inequality (see e.g. [3]) implies the speed is zero if the tree has polynomial growth.
So if every vertex at a level which is a power of 2 has 4 children and all other vertices have a single child, then the tree is transient but the speed of SRW is zero.
[1] Lyons, Russell. "Random walks and percolation on trees." The annals of Probability (1990): 931-958.
[2] Benjamini, Itai, and Yuval Peres. "Random walks on a tree and capacity in the interval." In Annales de l'IHP Probabilités et statistiques, vol. 28, no. 4, pp. 557-592. 1992.
[3] Lyons, R., & Peres, Y. (2017). Probability on Trees and Networks (Cambridge Series in Statistical and Probabilistic Mathematics). Cambridge: Cambridge University Press. doi:10.1017/9781316672815 https://rdlyons.pages.iu.edu/prbtree/book_online.pdf
A: here is a suggestion for a counterexample.   To construct the graph, starting at the origin, heading right take a step and bifurcate.  On either branch, take 2 steps and bifurcate, on any branch take 3 steps and bifurcate, etc.  The distance from the origin is a birth and death process $\delta_n$  with transition probabilites, 2/3 to increase at any distance at which you bifurcate and 1/2 at any other. As such it should be easy to show that it is not recurrent, and I can prove that.  It can be imbedded in a 1-d brownian motion by looking in only at the  points 0,1,3/2, 2, 2.25,.2.5,2.75,2.75  + 1/8   etc.  Note, form 2.75 you have a probability 2/3 of increasing and 1/3 of decreasing.  There are n increments of size 2^(-2), so the points I have written down never get bigger that $\Sigma n*2^{-n} < 1000000$.  The brownian motion starting from 1 has positive probability of reaching 1000000 before it reaches 0, and on those paths $\delta_n$ never reaches 0. $$$$
As to $\delta_n/n$, I don't have a rigorous argument , but I argue as follows:  When you are in the middle of the $j^{th}$ flat stretch, you expect a time about $j^2$ to get out of it, and therefore at least an expected time $ 1 + 4 + 9 + ... n^2 \approx n^3$  until you have reached the end of the $n^{th}$ flat stretch.  Your distance from the origin when you have reached the end of the $n^{th}$ flat stretch is $1 + 2 + 3 + ... + n \approx n^2$, and therefore you expect the  the process is at about $n^{\frac 2 3}$ at time n.
