Random walk on a simple finite network

2011-02-19T17:09:35Z

Consider a graph $\Delta_N = \lgroup (x,y)\in\mathbb{Z}^2| x+y\leq N-1, x\geq 0,\ y\geq 0 \rgroup$ (set of edges is defined in a natural way): see here ).

Take a random walker that wonders around this network (transition probabilities are given as an inverse of the degree of a given node) . I am interested in the probability $\mathbb{P}(q)$ that a walker starting at point $p\in\Delta_N$ would reach point $\mathcal{O}=(0,0)$ before reaching the "bottom" of the network : $D=\lgroup (x,y)\in\Delta_N| x+y= N-1 \rgroup$. I introduce new pair of coordinates (X,Y) on $\Delta_N$ - see here. I want to find an easy proof of the following fact:

Let $p,q\in(\Delta_N\setminus D)$ be such that $\rho(p,\mathcal{O})=\rho(q,\mathcal{O})$, >$\rho(p,q)=2$ and $|X|(p)>|X|(q)$. Under those conditions $\mathbb{P}(p)<\mathbb{P}(q)$.

(In the above $\rho$ is a standard "Manhattan" metric on $\Delta_N$)

I managed to prove this property. Yet, proof is very long, difficult and "ugly". I want to use above result in a physics article so I want it to be as simple and concise as possible.

A friend of mine suggested the following argument that is much simpler then that of mine (unfortunately it is not complete) :

Consider sites in the interior of $\Delta_{N}$ lying on the bisection $\mathcal{B}$ of a line segment connecting $p$ and $q$ (see here). We label these points as $b_{1},b_{2},\ldots,b_{k}$. By definition of $p$ , all trajectories leading from $p$ to $\mathcal{O}$ , without touching $D$ , must touch one of b 's at one point. This is clearly not the case for trajectories that start from $q$ . Let $\mathbb{P}^{(FP)}(p\rightarrow b_{i})$ ($\mathbb{P}^{(FP)}(q\rightarrow b_{i})$ ) denotes the probability that a random walker that was initially in $p$ (respectively in $q$ ) will reach $b_{i}$ before reaching any other b 's or points laying on $D\cup \mathcal{O}$. Therefore one can write:

$\mathbb{P}(p)=\sum_{i=1}^{i=k}\mathbb{P}^{(FP)}(p\rightarrow b_{i})\mathbb{P}(b_{i})$

$\mathbb{P}(q)>\sum_{i=1}^{i=k}\mathbb{P}^{(FP)}(q\rightarrow b_{i})\mathbb{P}(b_{i})$

Each $\mathbb{P}^{(FP)}(p\rightarrow b_{i})$ ($ \mathbb{P}^{(FP)}(q\rightarrow b_{i}) $) is a sum of probabilities corresponding to different trajectories $\gamma(p\rightarrow b_{i})$ ($\gamma(q\rightarrow b_{i}) $) that connect $p$ ($q$ ) with $b_{i}$ without touching other b 's and and $D$. Probability of a given $\gamma(p\rightarrow b_{i})$ is a product of probabilities that correspond to choices that a random walker makes on its trajectory. For every $\gamma(p\rightarrow b_{i})$ of this type we can find $\tilde{\gamma}(q\rightarrow b_{i})$ - trajectory connecting $q$ with $b_{i}$ being a mirror reflection of $\gamma(p\rightarrow b_{i})$ with respect to the bisection $\mathcal{B}$ (see here). Yet, converse is not true - there are trajectories connecting $p$ and $b_{i}$ (without touching $D$, $\mathcal{O}$ or otther b's) that cannot be obtained in this way. As long as $\gamma(p\rightarrow b_{i})$ does not touch the "edge" of $\Delta_N$ (i.e. as long as all nodes on the path have degree 4) we have equality of probabilities that correspond to $\gamma(p\rightarrow b_{i})$ and $\gamma(q\rightarrow b_{i})$. Yet, this is not the case when $\gamma(p\rightarrow b_{i})$ touches the edge and for such points one encounters bigger transition probabilities (they are equal $\frac{1}{3}$) then for points laying on the mirror reflection of this trajectory (they are equal $\frac{1}{4}$).

Without this problem one clearly have the inequality desired by me. Unfortunately, so far, I was unable to handle this problem properly..

Answer by Omer for Random walk on a simple finite network

2011-02-19T22:55:35Z

Here's an argument based on coupling.

First, note that $\mathbb{P}$ does not change if we consider instead the random walk that is lazy along the edges of $\Delta$, moving in each direction with probability $1/4$, and staying in place with probability $1/4$.

Couple the random walks from $p$ and $q$ so that (initially) they move in the same direction at every step. Eventually one of the following happens:

They reach a position where $X(p)=1$ and $X(q)=-1$. In this case obviously they have the same probability of reaching $0$ before $D$.
They reach $D$ (together).
There is a time at which $p$ is on the boundary and $q$ moves towards the boundary. In this step $p$ is lazy, so after the step $p$ and $q$ are two adjacent points along the boundary with $q$ nearer to $0$ then $p$. Thus it suffices to show that $\mathbb{P}$ is decreasing along the boundary when moving away from $0$. This is done by continuing the coupling in exactly the same way, and now $p$ can only reach $0$ after $q$.

In short, the coupling is that $p,q$ move in the same direction until either one reaches $0$ or $D$ or until they become symmetric, in which case they preserve the symmetry henceforth, or one of them reaches $0$ or $D$. With this coupling, $q$ reaches $0$ no later than $p$, and $p$ reaches $D$ no later than $q$ does.

Random walk on a simple finite network - MathOverflow

Random walk on a simple finite network

Answer by Omer for Random walk on a simple finite network