5
$\begingroup$

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

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.

$\endgroup$
7
  • $\begingroup$ It may be usefull to know that $h$ is small related to $mn$. Say $h$ is of the same order of magnitude of $m$ or $n$, so around $\sqrt{mn}$. I'm particularly interested in the case $nm\sim 2^{14}$ and $h\leq 150$ $\endgroup$
    – Stefano
    Mar 3, 2011 at 11:44
  • $\begingroup$ If you are talking directed graph, then I might believe in your statement about it being an equivalent problem. However, it is still an interesting question for an undirected bipartite graph. Gerhard "Got My y Key Back" Paseman, 2011.03.03 $\endgroup$ Mar 3, 2011 at 19:30
  • $\begingroup$ @Stefano Amazingly, I've been thinking about the same problem recently, and I'm curious if your motivation is similar to mine? In the language of my problem, you are looking for the probability of finding "redundant" edges with respect to the rigidity of a regular square lattice graph reinforced with random "next nearest neighbor" diagonal edges. (The probability of finding a circuit in the 2D rigidity matroid of this random graph, in more technical language). $\endgroup$
    – j.c.
    Mar 3, 2011 at 19:45
  • $\begingroup$ To answerers: I'm very interested in how to generalize the results of the Erdos-Renyi random graph model to random graphs on the complete bipartite graph (in particular, the growth and properties of the giant component, as I believe I understand the connectivity threshold in this model), as those notions have a direct interpretation in my problem, so I for one would appreciate an answer along those lines. I was going to ask that as a question once I had a chance to look over Alon and Spencer's book in more detail, actually, but Stefano has saved me the trouble.. $\endgroup$
    – j.c.
    Mar 3, 2011 at 19:51
  • 1
    $\begingroup$ A useful reference might be section 7 of Janson's "Poisson convergence and Poisson processes with applications to random graphs", where he considers related questions in the non-bipartite case. The intuition there is that the first cycle to show up is probably not going to be too large, so you can restrict your attention to looking at short cycles. In the non-bipartite case, the number of cycles of each short length behave like independent Poisson variables, so you can then estimate the mean (e.g. as in his corollary 7.4). It would make sense for the same to hold in the bipartite case. $\endgroup$ Mar 3, 2011 at 20:55

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ Thanks for the fast and very usefull answer, I'm working on it. Btw, someone suggested me a different point of view, that I added to the definition of the problem. In this alternative form, I guess the problem is likely to have been already faced and (probably) solved. Do you have any suggestion on literature? Thanks very much. $\endgroup$
    – Stefano
    Mar 3, 2011 at 18:58
  • 3
    $\begingroup$ I beg to differ, Peter. If h is near \sqrt(mn). then (h/mn)^4 is near m^2n^2, giving the probability of a square near 1/4. Unless small means something less than 1/2, you might take another look. Or perhaps I am misreading something, in which case an explanation would be appreciated. Gerhard "Ask Me About Sstem Design" Paseman, 2011.03.03 $\endgroup$ Mar 3, 2011 at 19:09
  • $\begingroup$ Also, one might consider the combinatorial problem of enumerating path configurations in small rectangles. For example, the unique interesting closed path for 3x3 looks like a 0-1 matrix with det 2, so one can try Peter's suggestion for 2x2 squres on a slightly larger scale and see how that proceeds. My feeling is the same as Peter's suggestion though, that the probability is near 1 that $\sqrt(mn)$ chose at random will form a closed (possibly self-intersecting when drawn in the plane) path. Gerhard "The Missing _ Ke_ M_ster_" Paseman, 2011.03.03 $\endgroup$ Mar 3, 2011 at 19:19
  • $\begingroup$ Here is another model that suggests a closed path will be likely. Of the 512 3x3 0-1 matrices, I count more than 1/4 of them which have closed paths. Assuming every configuration is likely, the gives odds of less than 3/4 for not having a local path. Now you can partition the rectangle up into disjoint 3x3 squares and scale to see how likely it is to avoid a nonlocal path. I'm starting to think that h= e*min(m,n) points chosen at random will have a > 1/2 chance of having a path. Doing a count by computer for 4x4 or 5x5 may help. Gerhard "Ask Me About System Design" Paseman, 2011.03.03 $\endgroup$ Mar 3, 2011 at 21:32
  • $\begingroup$ Gerhard: You're right ... I messed up my calculation. Sorry about that. $\endgroup$
    – Peter Shor
    Mar 3, 2011 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.