4
$\begingroup$

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$?

$\endgroup$

3 Answers 3

5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ this makes sense. to prove the last part, we could consider the graph where the bifurication edges are only directed outwards. we can easily couple random paths to so that $d(X_0,X_n)\le d(X_0',X_n')$ always holds. (where $X$ is the path on your graph, and $X'$ is the modified one) suppose, there was $\epsilon > 0$ such that whp $\limsup d(X_0,X_n)/n > \epsilon$. let $t_k$ be the time of our $k$-th bifurication. if $\limsup d(X_0,X_n)/n > \epsilon$, then there must be infinitely many $k$ such that $t_k-t_{k-1} <k/\epsilon$. we get a contradiction by borel cantelli and chebyshevs. $\endgroup$ Feb 1, 2021 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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