show/hide this revision's text 2 added 491 characters in body

Consider a random walk on a connected graph $G=(V,E)$. That is, associate to each neighbouring nodes $a,b\in V\ $ transition probabilities $\mathbb{P}(a\rightarrow b), \mathbb{P}(b\rightarrow a) $ that define a Marcov process with the state space $V$. Fix one point $\mathcal{O}\in V$ and a set $D\subset V$. Define $\mathbb{P}(x)$ as the probability that a random walker that was initially in $x\in V$ will reach $\mathcal{O}$ before reaching any points from $D$ (for simplicity assume that it is possible to reach $\mathcal{O}$ from any point on a graph without passing trough $D$) . Let $d(.,.)$ denotes the "minimal path" metric on $V\setminus D$. Let $\mathbb{P}_{d}(x)$ denotes the probability that a walker starting from $x$ will reach $\mathcal{O}$ precisely in $d(x,\mathcal{O})$ steps. My question is the following:

Take two points $x,y\in V\setminus B$ such that $d(x,\mathcal{O})=d(y,\mathcal{O})$ and $\mathbb{P}_d(x) > \mathbb{P}_d(y)$. Under what conditions we can say that $\mathbb{P}(x)>\mathbb{P}(y)$?

Remark 1: It is easy to construct a counterexample for above statement when one considers a random walk on part of $\mathbb{Z}$ (in this situation $\mathcal{O}$ splits $V$ into two disjoint sets). Therefore one should certainly exclude the possibility that $\mathcal{O}$ splits $V$ into two independent parts.

Remark 2: This question is somewhat related to the one I previously asked. I give there a non trivial (I think) example in which above property holds.

Remark 3: Note that if there are some non trivial assumptions under which above assertion holds, this would give quite a lot information about $\mathbb{P}$ for relatively low cost. In particular, as there is a correspondence between "Kirchoff laws" and Marcov processes on graphs, it would give some information about discrete harmonic functions on network of interest.

Remark 4: Obviously, instead of the one "source point" $\mathcal{O}$, one can take some more general subset of $V$.

show/hide this revision's text 1

Probability of return vs. probability of return in minimal number of steps

Consider a random walk on a connected graph $G=(V,E)$. That is, associate to each neighbouring nodes $a,b\in V\ $ transition probabilities $\mathbb{P}(a\rightarrow b), \mathbb{P}(b\rightarrow a) $ that define a Marcov process with the state space $V$. Fix one point $\mathcal{O}\in V$ and a set $D\subset V$. Define $\mathbb{P}(x)$ as the probability that a random walker that was initially in $x\in V$ will reach $\mathcal{O}$ before reaching any points from $D$ (for simplicity assume that it is possible to reach $\mathcal{O}$ from any point on a graph without passing trough $D$) . Let $d(.,.)$ denotes the "minimal path" metric on $V\setminus D$. Let $\mathbb{P}_{d}(x)$ denotes the probability that a walker starting from $x$ will reach $\mathcal{O}$ precisely in $d(x,\mathcal{O})$ steps. My question is the following:

Take two points $x,y\in V\setminus B$ such that $d(x,\mathcal{O})=d(y,\mathcal{O})$ and $\mathbb{P}_d(x) > \mathbb{P}_d(y)$. Under what conditions we can say that $\mathbb{P}(x)>\mathbb{P}(y)$?

Remark 1: It is easy to construct a counterexample for above statement when one considers a random walk on part of $\mathbb{Z}$ (in this situation $\mathcal{O}$ splits $V$ into two disjoint sets). Therefore one should certainly exclude the possibility that $\mathcal{O}$ splits $V$ into two independent parts.

Remark 2: This question is somewhat related to the one I previously asked. I give there a non trivial (I think) example in which above property holds.