3
$\begingroup$

Let $G$ be a bounded degree graph and fix a vertex $v_0$. Suppose that the simple random walk on $G$ is transient, and let $g:G\to\mathbb{R}$ be defined by $$g(v)=\mathbb{P}_v[T_{v_0}<\infty].$$ That is, $g(v)$ is the probability that a simple random walk starting at $v$ will ever hit $v_0$.

Now consider $g(G)$, the image of $g$ in $[0,1]$.

Can $g(G)$ have an accumulation point other than $0$?

$\endgroup$
3
$\begingroup$

The answer is yes. To see this, take a transient graph $G$ (say $\mathbb{Z}^3$) and glue a copy of $\mathbb{N}$ to some vertex (say $v_0$). The vertices of $\mathbb{N}$ now all have $g(v)=1$.

If you want infinitely many vertices with distinct values of $g$, all greater then some $a>0$, take a ladder instead of $\mathbb{N}$. That is, take two copies of $\mathbb{N}$, call them $U^0=\{u^0_0,u^0_1,\ldots\}$ and $U^1=\{u^1_0,u^1_1,\ldots\}$ and connect each $u^0_k$ with $u^1_k$. Connect $u^0_0$ with $v_0$ and connect $u^1_0$ with a neighbour of $v_0$, call it $v_1$. In the resulting graph, vertices of the ladder will have distinct values of $g$, all greater then $g(v_1)$.

$\endgroup$
  • $\begingroup$ Hi Ori! By accumulation point, I meant a sequence of distinct elements that has a limit point, so the first example is not relevant. The second example however, is spot on! Just to clarify: instead of $v_1$ a neighbor of $v_0$, I guess you meant any $v_1$ with $g(v_0) \neq g(v_1)$. Thanks! $\endgroup$ – Melafefon Chamutz May 16 '17 at 12:47
  • $\begingroup$ A follow up question: does any transient graph $G$ contains a transient subgraph $H$ such that $g(H)$ does not contain accumulation points? Thanks! $\endgroup$ – Melafefon Chamutz May 16 '17 at 16:26
  • $\begingroup$ Interesting question. I'll think about it. $\endgroup$ – Ori Gurel-Gurevich May 16 '17 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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