Random walk on a two-dimensional uniform grid - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T17:37:18Z http://mathoverflow.net/feeds/question/38556 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38556/random-walk-on-a-two-dimensional-uniform-grid Random walk on a two-dimensional uniform grid Seb67 2010-09-13T10:35:49Z 2010-09-13T12:30:09Z <p>Hi,</p> <p>consider the following random walk on the lattice $\{0,\dots,n\}^2$. It starts at $(0,0)$ and then move either up or right, with probability respectively $p$ and $1-p$. Once it reaches the right border (respectively the up border), it goes up (respectively it goes right) to $(n,n)$. What properties do we know about this random walk ? Especially can we say anything about the times when it crosses the main diagonal ?</p> http://mathoverflow.net/questions/38556/random-walk-on-a-two-dimensional-uniform-grid/38559#38559 Answer by alext87 for Random walk on a two-dimensional uniform grid alext87 2010-09-13T10:54:39Z 2010-09-13T11:08:24Z <p>Firstly, I take the main diagonal to mean the diagonal from $(0,n)$ to $(n,0)$. We know that it takes exactly $n$ steps until the particle is at a position $(i,n-i)$ $0\leq i\leq n$. This is because after $k\leq n^2$ steps the particle must be at a position $(j,k-j)$ for $0\leq j\leq k$ since each step increases the first coordinate position by one or the second coordinate position by one but not both. </p> <p>Secondly take the main diagonal to be from $(0,0)$ to $(n,n)$. Let $N_k\sim\text{Bin}(k,p)$ be the number of up steps after $k$ steps. For the particle to be at the a point $(i,i)$ we must have $N_k=i$ and a total of $2i$ steps must have been taken. Thus the probability that after $k$ steps the particle is on the diagonal is $0$ if $k$ is odd and $$\binom{k}{k/2}p^{\frac{k}{2}}(1-p)^{\frac{k}{2}}$$ if $k$ is even.</p> http://mathoverflow.net/questions/38556/random-walk-on-a-two-dimensional-uniform-grid/38562#38562 Answer by Robin Chapman for Random walk on a two-dimensional uniform grid Robin Chapman 2010-09-13T11:25:21Z 2010-09-13T11:25:21Z <p>The probability that the walk meets the diagonal at $(k,k)$ where $0 &lt; k &lt; n$ is $${2k \choose k}p^k(1-p)^k$$ so the expected number of such meetings is $$\sum_{k=1}^{n-1}{2k \choose k}p^k(1-p)^k$$ which I don't think has a convenient closed form.</p> <p>If one insists a "crossing" must pass through the diagonal, this expectation becomes $$\sum_{k=1}^{n-1}{2k-1 \choose k}(p^{k+1}(1-p)^k+p^k(1-p)^{k+1}) =\sum_{k=1}^{n-1}{2k-1 \choose k}p^k(1-p)^k.$$</p> http://mathoverflow.net/questions/38556/random-walk-on-a-two-dimensional-uniform-grid/38563#38563 Answer by alext87 for Random walk on a two-dimensional uniform grid alext87 2010-09-13T11:29:14Z 2010-09-13T11:29:14Z <p>Now I understand a little more what you meant. The probability of crossing at $(i,i)$ occurs either from $(i,i-1)\rightarrow (i,i)\rightarrow (i,i+1)$ (occurs with probability $(1-p)^3$) or $(i-1,i)\rightarrow (i,i)\rightarrow (i+1,i)$ (occurs with proability $p^3$). We get to $(i,i-1)$ with probability $\binom{2i-1}{i}(1-p)^{i}p^{i-1}$ and we get to $(i-1,i)$ with probability $\binom{2i-1}{i}(1-p)^{i-1}p^i$. Thus the probability of the particle crossing at $(i,i)$ is $$\binom{2i-1}{i}(1-p)^{i}p^{i+1}+\binom{2i-1}{i}(1-p)^{i+1}p^{i} = \binom{2i-1}{i}(1-p)^{i}p^{i}$$</p> http://mathoverflow.net/questions/38556/random-walk-on-a-two-dimensional-uniform-grid/38564#38564 Answer by Benoît Kloeckner for Random walk on a two-dimensional uniform grid Benoît Kloeckner 2010-09-13T11:35:18Z 2010-09-13T11:47:11Z <p>Turn your square one fourth turn to the left and project it down.</p> <p>To give some details: consider a simple random walk $Y$ on $\mathbb{Z}$ that is constrained to go left when yours goes up, and to go right when yours goes right. When your walk is on the boundary, then draw randomly independently the direction of $Y$. Since $Y$ is a simple random walk, all the results you can dream of are available. The only issue is that the two walks decorelate as soon as yours hit the boundary, but this is no problem for your question on the diagonal. Indeed, if $Z$ is the walk that is equal to $Y$ for steps $\leq n$, and equals the projection of $Y$ to $[-n+k,n-k]$ at steps $n+k$, then up to a $\sqrt{2}$ factor $Z$ is the projection on the second diagonal of your random walk, and it hits $0$ at time $t$ (meaning that your walk hits the diagonal at that time) if and only if $Y$ does.</p> http://mathoverflow.net/questions/38556/random-walk-on-a-two-dimensional-uniform-grid/38567#38567 Answer by sleepless in beantown for Random walk on a two-dimensional uniform grid sleepless in beantown 2010-09-13T11:48:55Z 2010-09-13T12:30:09Z <p>The question as proposed is more like a random walk on a $C_{n+1}$, the cycle graph of size $n+1$, rather than a 1-dimensional random walk on $\mathbb{Z}^1$. This is because of the wrap-around conditions imposed by the way the problem is defined.</p> <p>This is a <strong>biased random walk on a graph</strong>, with the graph being $C_{n+1}$. For simplicity, label all of the vertices of this cycle graph clockwise from $0,1,...,n-1,n$. Start the random walk at the node labeled $0$ and proceed in the <em>negative</em> direction (CCW, counterclockwise) with the probability $1-p$ and proceed in the <em>positive</em> direction (CW, clockwise) with the probability $p$.</p> <p>If $p=1$ or $p=0$, then you have a deterministic process that will hit the boundary at $t=kn, k\in \mathbb{Z}$.</p> <p>It can also be seen that is $p = 0.5$, you can expect to hit the wrap-around boundary at a distance of $n$ on average at time $t=n^2$, or you can come back to the center "boundary" with the standard expectation of an unbiased random walk returning to $0$ before it hits distance $-n$ or $+n$. </p> <p>If $p\ne 0.5$, then there is a drift. If $p>0.5$ then there is a drift in the clockwise direction, if $p&lt;0.5$ then there is a drift in the counterclockwise direction. Now try to find the expected hitting time for the clockwise boundary, or counterclockwise boundary, or for returning to $0$. The <em>drift</em> is $p-(1-p)=2p-1$.</p> <p>Define the transitions of this system as the tri-diagonal stochastic matrix $T$ with $n+1$ rows and $n+1$ columns, where each element $T_{i,j}$ is</p> <ul> <li>$0$ if $i=j$ or if $|i-j| > 1$</li> <li>$p$ if ($i=j+1$) or ($i=1$ and $j=n+1$)</li> <li>$1-p$ if ($i=j-1$) or ($i=n+1$ and $j=1$)</li> </ul> <p>You can find the steady-state distibution over long periods of time to be stable: it is equally likely to be in any of the $n+1$ states with probability $1/(n+1)$. </p>