4
$\begingroup$

Imagine turning the square grid defined by $\mathbb{N}^2$ in the plane into a directed graph. The vertices are $\mathbb{N}^2$ and for each vertex $(x,y)$, there is an edge pointing from it to $(x+1, y)$ and another pointing to $(x,y+1)$.

Turn it into a random graph, by letting the edges appear independently at random with probability $p$. Let $p_n$ be the probability that there is a directed path from (0,0) to the set of points of taxi-cab distance $n$ to the origin. Then we see that $p_n$ is a decreasing sequence, whose limit is the probability that there is an infinite directed path.

Take $n$. I want to know how close $p_n$ is to the limit. Let $r_n=p_{n+1}/p_n$. If I know tha t $r_n, r_{n+1}, \dots$ are "large", then somehow, I know I am "close" to the limit. I am trying to come up with a lower bound for $r_n$. The easiest thing, is to argue that, this equals the probability that there is a path reaching points at taxi-cab distance $n+1$ given that there is a path reaching those at distance $n$. This conditional probability is at least $(1-(1-p)^2)$, which is the probability that at one vertex there are edges pointing out from it.

But this is not a good lower bound, because ideally I want to obtain a lower bound that depends on $n$ converging to $1$. Can anyone point out something useful?

$\endgroup$
  • 1
    $\begingroup$ What's your more general aim here? (It's hard to point out "something useful"). Have you read Grimmett? $\endgroup$ – Tim Apr 30 '13 at 21:49
  • $\begingroup$ @Tim My main aim is to know whether my $p_n$ is close to $\lim p_n$. If I know that at some stage $p_n$ starts to decrease "very slowly", it may tell me that $p_n$ is close to the limit. As for the book, I cannot find a copy of this book right now. $\endgroup$ – Spook Apr 30 '13 at 21:53
  • 1
    $\begingroup$ It sounds like you are estimating $p_n$ for some large $n$ with a lot of random samples and then trying to get a bound on how close you are. I wouldn't recommend that. There are some pretty good estimates for the percolation probabililty for $p>\frac 12$. There should be a copy of the book in your university library. $\endgroup$ – Tim Apr 30 '13 at 22:15
  • $\begingroup$ Is $p_n$ the probability there exists a path to one of the points a distance $n$ away or the probability there exists a path to each of the points a distance $n$ away? $\endgroup$ – John Douma May 1 '13 at 0:18
  • $\begingroup$ @user69810 it is the probability that there exists one path to a point of distance $n$. $\endgroup$ – Spook May 1 '13 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.