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

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

share|improve this question
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
add comment

1 Answer

up vote 12 down vote accepted

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.

share|improve this answer
+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? –  Michal 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
add 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.