Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
Asking for general conditions is a bit too ambiguous. Are there specific networks in which you are interested, or certain types of conditions that would be of interest to you? –  Omer Feb 28 '11 at 18:24
I am interested mostly in finite sublattices of $mathbb{Z}^2$. In particular, lattices similar to the triangular one I presented in my previous question (see link above). Lattices in which all nodes (say, without sites laying at the "boundary") have the same degree (In general, I would like to know an easy way to compare $\mathbb{P}$ in sites fulfilling the condition mentioned. I want to avoid solving the full set of equations (explicit formulas are rarely available or even when if one is able to find an explicit solution it is often difficult to analyse). –  Michal Oszmaniec Feb 28 '11 at 21:14
add comment

1 Answer

up vote 3 down vote accepted

Your question is slightly ambiguous.

I think that there is almost no relation between $P(x), P(y)$ and $P_d(x),P_d(y)$.

Here is the reason: You can take any graph $G(V,E)$ and add two edges to it edge from $x$ to $O$ and edge from $y$ to $O$ such that $Pr(x\mapsto O)=\varepsilon_1$ and $Pr(y\mapsto O)=\varepsilon_2$. If $\varepsilon_i$ are small enough then it will not affect $P(x), P(y)$, but in this case $P_d(x)=\varepsilon_1$ and $P_d(y)=\varepsilon_2$. Therefore $P(x), P(y)$ are almost unrelated to $P_d(x),P_d(y)$.

Hope that this is helps.

share|improve this answer
Good point. I agree that the question is ambiguous. It can be stated differently : "Under what conditions we have a connection between $\mathbb{P}$ and $\mathbb{P}_d$ ? As far as I understand your argument says that all transition probabilities cannot differ too much. But what if all $\mathbb{P}(i\rightarrow j)$ are "close to" the inverse of a degree of appropriate node? –  Michal Oszmaniec Mar 3 '11 at 12:12
But what if all are "close to" the inverse of a degree of appropriate node? I do not believe it will help. The problem is that $P_d(x)$ is a function of a $d$ transaction probabilities while $P(x)$ in general will depend on whole graph. Thus you have hope that $P_d(x)$ will be related to $P(x)$ only if there is only "one path"(in some good definition) from $x$ to $O$. Possible definition for "one path": if removing one edge from the path will disconnect $x$ and $O$. –  Klim Efremenko Mar 3 '11 at 12:46
Actually, I hope that there might be some non trivial class of graphs for which relation between $P$ and $P_d$ would hold. I'm not saying that you are entirely wrong but notice that $P_d(x)$ in general on more than $d$ transition probabilities (there might be many paths between $x$ and $O$ that have length $d$). So $P_d$ encodes some information about sites that lay on closest connections between $x$ and $O$. –  Michal Oszmaniec Mar 3 '11 at 14:22
OK one of the examples layers graphs: $V=S_1\cup S_2 \cup \ldots S_d$ and all edges are from $S_i$ to $S_{i+1}$. In this case all paths are of the same length and thus $P_d(x)=P(x)$. –  Klim Efremenko Mar 3 '11 at 15:56
Could you please specify how $S_i$ is connected to $S_{i+1}$ and $S_{i-1}$?. Does every node from $S_i$ is linked to all nodes from $S_{i+1}$ and $S_{i-1}$? –  Michal Oszmaniec Mar 3 '11 at 16:36
show 1 more comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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