9
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Omer
    Feb 28, 2011 at 18:24
  • $\begingroup$ 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). $\endgroup$
    – Michał Oszmaniec
    Feb 28, 2011 at 21:14

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Michał Oszmaniec
    Mar 3, 2011 at 12:12
  • $\begingroup$ 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$. $\endgroup$
    – Klim Efremenko
    Mar 3, 2011 at 12:46
  • $\begingroup$ 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$. $\endgroup$
    – Michał Oszmaniec
    Mar 3, 2011 at 14:22
  • $\begingroup$ 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)$. $\endgroup$
    – Klim Efremenko
    Mar 3, 2011 at 15:56
  • $\begingroup$ 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}$? $\endgroup$
    – Michał Oszmaniec
    Mar 3, 2011 at 16:36

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.