Random walk on a simple finite network - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T14:59:24Z http://mathoverflow.net/feeds/question/55991 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55991/random-walk-on-a-simple-finite-network Random walk on a simple finite network Michal Oszmaniec 2011-02-19T17:09:35Z 2011-02-19T22:55:35Z <p>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 <a href="https://picasaweb.google.com/Michal.Oszmaniec/Math#5575329195014288290" rel="nofollow">here</a> ).</p> <p>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 <a href="https://picasaweb.google.com/Michal.Oszmaniec/Math#5575329202844087522" rel="nofollow">here</a>. I want to find an easy proof of the following fact:</p> <blockquote> <p>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)&lt;\mathbb{P}(q)$.</p> </blockquote> <p>(In the above $\rho$ is a standard "Manhattan" metric on $\Delta_N$)</p> <p>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. </p> <p>A friend of mine suggested the following argument that is much simpler then that of mine (unfortunately it is not complete) :</p> <p>Consider sites in the interior of $\Delta_{N}$ lying on the bisection $\mathcal{B}$ of a line segment connecting $p$ and $q$ (see <a href="https://picasaweb.google.com/Michal.Oszmaniec/Math#5575329207588460018" rel="nofollow">here</a>). 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: </p> <p>$\mathbb{P}(p)=\sum_{i=1}^{i=k}\mathbb{P}^{(FP)}(p\rightarrow b_{i})\mathbb{P}(b_{i})$</p> <p>$\mathbb{P}(q)>\sum_{i=1}^{i=k}\mathbb{P}^{(FP)}(q\rightarrow b_{i})\mathbb{P}(b_{i})$</p> <p>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 <a href="https://picasaweb.google.com/Michal.Oszmaniec/Math#5575329209963352962" rel="nofollow">here</a>). 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}$).</p> <p>Without this problem one clearly have the inequality desired by me. Unfortunately, so far, I was unable to handle this problem properly.. </p> http://mathoverflow.net/questions/55991/random-walk-on-a-simple-finite-network/56018#56018 Answer by Omer for Random walk on a simple finite network Omer 2011-02-19T22:55:35Z 2011-02-19T22:55:35Z <p>Here's an argument based on coupling.</p> <p>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$.</p> <p>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:</p> <ul> <li><p>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$.</p></li> <li><p>They reach $D$ (together).</p></li> <li><p>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$.</p></li> </ul> <p>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.</p>