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](https://picasaweb.google.com/Michal.Oszmaniec/Math#5575329195014288290) ).


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](https://picasaweb.google.com/Michal.Oszmaniec/Math#5575329202844087522). 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](https://picasaweb.google.com/Michal.Oszmaniec/Math#5575329207588460018)). 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](https://picasaweb.google.com/Michal.Oszmaniec/Math#5575329209963352962)). 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.. 



Random walk on a simple finite network
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.


