Random walk on a simple finite network

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

• That argument sounds rather tricky, but I think it is clear that letting $\mathbb{P}(X,Y)$ be the probability of hitting 0 from point (X,Y) then, for given Y, this is symmetric in X. That is is increasing for $X\le0$ should follow from the iterative definition of $\mathbb{P}(\cdot)$. – George Lowther Feb 19 '11 at 20:16
• It does follow if you can show that the boundary values are concave on each side. Unfortunately, I failed to show that so far. I'll think of it more in the evening. – fedja Feb 19 '11 at 20:44
• It's probably helpful to define $X$ and $Y$ (especially they're not the same as $x$ and $y$): $Y=x+y$. I would call this the level of the point. The top level is level 0 and the bottom level in $N-1$. $X$ is then given by $X=x-(x+y)/2$. The $X$ coordinate in level $i$ goes from $-i/2$ to $i/2$. – Anthony Quas Feb 19 '11 at 22:36

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.

• +1. Very nice argument! – George Lowther Feb 19 '11 at 23:11
• Thanks a lot! That is a rally cool argument! I was thinking about generalization of this result - consider a perturbation introduced into a network (see picasaweb.google.com/Michal.Oszmaniec/Math#5575684413855038498 ) that is located "directly above" considered points $p$ and $q$. Perturbation decreases transition probability of passage trough the edge it occupies (in both directions). Will the relation between $\mathbb{P}(p)$ and $\mathbb{P}(q)$ still hold? – Michał Oszmaniec Feb 20 '11 at 8:30
• I don't see right now a way to deal with the perturbed lattice. If we can show that the probability of hitting either end of the weak edge from before $D$ is larger from $q$ than from $p$ then it seems like a path decomposition argument might work. This in turn boils down to comparing values of the Green's function for the RW in the given domain, killed at $D$. – Omer Feb 20 '11 at 21:52