Random points in a rectangular grid defining a closed path

2011-03-03T11:39:46Z

Suppose we have a $n\times m$ rectangular grid (namely: $nm$ points disposed as a matrix with $n$ rows and $m$ columns).

We randomly pick $h$ different points in the grid, where every point is equally likely.

If only horizontal or vertical movements between two points are allowed, what is the probability that the points define at least one closed path?

ps: we can suppose $m=n$ to simplify

For example, let $n=m=4$ and $h=6$. 1 denotes a selected point, 0 a non-selected one.

These $6$ points define a closed path:

1 0 0 1

0 0 0 0

1 1 0 0

0 1 0 1

as these $6$ do (the $4$ in the bottom-right corner):

1 0 0 1

0 0 0 0

0 1 0 1

while the following $6$ points do not:

1 0 0 0

0 0 0 1

1 1 0 0

0 1 0 1

Substantially, the $h$ points define a closed path if and only if there exist a subset of these $h$ points such that every point in the subset has one other point of the subset on the same row and one on the same column.

Thanks for your help.

ALTERNATIVE DEFINITION:

Someone cleverly suggested me that my problem is equivalent to another one on graph-theory, which is more likely to have been solved.

Suppose you have a complete bipartite graph $K_{n,m}$. Randomly choosing $h$ edges, what is the probability that these $h$ edges generate at least one cycle?

Thanks very much for any help. Also a reference to some interesting work in the literature would be very appreciated.

Answer by Peter Shor for Random points in a rectangular grid defining a closed path

2011-03-03T12:51:12Z

Having screwed up the answer by getting the wrong answer for a really simple calculation the first time, I'm now going to try to redeem myself.

First, to make things easier, let each point be present with probability $h/(mn)$, and let these random variables be independent. This won't change the probabilities much.

You can calculate explicitly the expected number of squares. The expected number of squares is ${m \choose 2}{n \choose 2}(h/mn)^4$, since there are ${m \choose 2}{n \choose 2}$ possible squares, and each point is present with probability $h/mn$. This is roughly $1/4 (h^2/mn)^2$ (for large $mn$, and fixed $h^2/mn$).

Now, let's calculate the expected number of six-cycles. You can assume a $2k$-cycle lies in $k$ different columns and $k$ different rows (otherwise there is a smaller cycle), so we have ${m \choose 3}{n \choose 3}\alpha_3 (h/(mn))^6$ ways of getting a six-cycle. Here, $\alpha_3$ is the ways of getting a six-cycle in a 3 by 3 square, and it is easy to check that there are six of them.

There are four ways that it can look like this:

1.1
.11
11.

and two ways it can look like this:

11.
1.1
.11

Now, if we can compute $\alpha_k$, where $\alpha_k$ is the number of ways we can get a minimal $2k$-cycle in a $k\times k$ grid, we can get an infinite series for the expected number of cycles. For $\alpha_k$, we need to find a cycle which covers every row twice and every column twice. Let $\pi_1$ be the order that we visit the rows, and $\pi_2$ the order we visit the columns. We can assume that $\pi_1$ starts with $1$, and we can traverse each cycle in $2$ directions. This means that there are $(k-1)!$ possible $\pi_1$, $k!$ possible $\pi_2$, and we have to divide by $2$ because otherwise we count each cycle twice. Thus, the expected number of cycles when $m,n\rightarrow \infty$ is $$ \sum_{k=2}^\infty \frac{1}{2}(k-1)! k!{m \choose k}{n \choose k}\left(\frac{h}{mn}\right)^{2k},$$ which simplifies in the limit to $$ \sum_{k=2}^\infty \frac{1}{2k}\left(\frac{h^2}{mn}\right)^k,$$ or $$-1/2 \ln(1 - x) - x/2, \mathrm{\ \ where\ }x=h^2/(mn).$$ If objects are distributed with a Poisson distribution with expectation $r$, then the probability that there is an object is $1-e^{-r}$. Thus, if we assume that the closed paths are distributed according to the Poisson distribution, the probability that a closed path exists is $$1-(1-x)^{1/2}e^{x/2}.$$ As Kevin Costello remarks in the comments, you may be able to use Janson's theorem (also covered in Alon and Spencer's book) to prove that these closed paths obey Poisson statistics.

And below, another argument that the probability of a closed path rises to 1 when $h^2 =mn$, salvaged from my first attempt at solving the problem.

Let's start at a single point $P_0$, and look at the tree of paths that results. The tree of paths is obtained by looking for points in the same row as $P_0$, then points in the same column as these points, and then rows, etc. (Also do the same procedure, but starting with columns.) If any two points in this tree are equal (that is, there are two distinct paths leading from the starting point to the same point) then there is a closed path. So we want to know the probability that this tree of paths is fairly large. In particular, if the tree of paths has size $\sqrt{h}$, then by the birthday paradox there should be a reasonable chance that two of these points are equal.

But, assuming all the points are different, this tree of paths is a Galton-Watson branching process, and we can calculate the probability that it's large. (You can calculate lots of properties of Galton-Watson branching processes.) In particular, if the expected number of children is greater than 1, there is a finite probability that the tree is infinite. Using this is a rough criterion, you will start to get closed paths when $mn \approx h^2$. You should be able to a much better approximation by analyzing the associated Galton-Watson branching process more carefully.

The Galton-Watson tree has two branches. On the first branch, the number of children on odd levels are distributed approximately as a Poisson process with expectation $h/m$, and the number of children on even levels as a Poisson process with expectation $h/n$. On the second branch, distributions on the odd and even levels are reversed.

Random points in a rectangular grid defining a closed path - MathOverflow

Random points in a rectangular grid defining a closed path

Answer by Peter Shor for Random points in a rectangular grid defining a closed path