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$

1 Answer 1

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$
3
  • $\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$
    – Snoop Catt
    Commented May 16, 2017 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$
    – Snoop Catt
    Commented May 16, 2017 at 16:26
  • $\begingroup$ Interesting question. I'll think about it. $\endgroup$ Commented May 16, 2017 at 18:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .