A variation of the law of large numbers for random points in a square

Question

I uniformly mark $n^2$ points in $[0,1]^2$. Then I want to draw $cn$ vertical lines and $cn$ horizontal lines such that in each small rectangle there is at most one marked point. Surely, for a given constant c it is not always possible.

But it seems that for $c=100$ when n tends to infinity, the probability that such a cut exists should tend to one, as a variation of the law of the large numbers. Do you have any idea how to prove this rigorously?

Answer 1

Given $n^2$ i.i.d. uniform points in $[0,1]^2$, the goal is to draw a configuration of $cn$ vertical lines and $cn$ horizontal lines such that in each small rectangle there is at most one marked point.

We show below that $c$ must satisfy $c=\Omega(n^{1/3})$ for this to be typically possible:

In fact, $\Theta(n^{4/3})$ lines are necessary and sufficient for such a configuration to exist with substantial probability.

More precisely, denote by $p_n(k)$ the probability that a configuration of $k$ vertical lines and $k$ horizontal lines separate $n^2$ i.i.d. uniform points $\{x_j\}_{j=1}^{n^2}$ in $[0,1]^2$.

Claim: For suitable constants $0<c_1<c_2<\infty$, we have (omitting integer part symbols):

(a) $\; p_n(c_1 n^{4/3}) \to 0$ as $n \to \infty$, and

(b) $\; p_n(c_2 n^{4/3}) \to 1$ as $n \to \infty$.

This is proved below with $c_1=1/20$ and $c_2=3/2$; no attempt has been made to optimize these constants.

Proof: Consider an auxiliary grid of $L:=n^{4/3}$ uniformly spaced vertical lines and $L$ uniformly spaced horizontal lines in the unit square. This grid defines $L^2$ grid squares of side length $1/L$.

(a) Call a grid square $Q$ nice if it contains exactly two of the $n^2$ given points $\{x_j\}$. Observe that for two distinct grid squares, the events that they are nice are negatively correlated. Call a nice grid square $Q$ good if there is at most one other nice square in its row and at most one other nice square in its column. The probability that a specific grid square $Q$ is nice is $${n^2 \choose 2}L^{-4}(1-L^{-2})^{n^2-2}=(1/2+o(1))L^{-1}.$$
Given that $Q$ is nice, The conditional expectation of the number of nice squares (other than $Q$) in the row of $Q$ is $1/2+o(1)$ Thus, given that $Q$ is nice, Markov's inequality implies that the conditional probability that there are two or more additional nice squares in the row of $Q$ (besides $Q$ itself) is at most $1/4+o(1)$. The same applies to the column of $Q$, and we deduce that $$P(Q \; {\rm is \; good}\; | Q \; {\rm is \; nice}) \ge 1/2+o(1) \, ,$$ so $$P(Q \; {\rm is \; good} ) \ge (1/4+o(1))L^{-1} \, .$$ Let $G$ denote the number of good grid squares. Then the mean satisfies $$E(G) \ge (1/4+o(1))L \,.$$ Observe that if we replace one point $x_i$ by $x_i'$ then $G$ will change by at most 5, so Mcdiarmid's inequality, see [1, Theorem 3.1] or [2], implies that for $n$ large enough, $$P(G \le L/5) \le \exp(-\frac{(L/21)^2}{25n^2}) \to 0 \,. {\rm as} \; n \to \infty \,.$$ (Alternatively, one could invoke the Efron-Stein inequality or estimate the variance directly to verify this.) Now suppose that $S$ is a set of vertical and horizontal lines that separate the points $\{x_j\}_{j=1}^{n^2}$. For each good grid square $Q$, a line of $S$ is required to separate the two points $x_i, x_j$ in the square, and each such line can be used for at most two good squares. Thus $|S| \ge G/2$ so $$p_n(L/20) \le P(\exists \; {\rm separating } \; S \; {\rm with } \; |S| \le L/10) \le P(G \le L/5) \to 0 $$.

(b) Denote by $M$ the number of pairs $(i,j)$ such that $1 \le i<j \le n^2$ and $x_i,x_j$ fall in the same grid square. Then $E(M) = {n^2 \choose 2}L^{-2} \le L/2$, and another application of McDirarmid's inequality implies that $P(M \ge L) \to 0$ as $n \to \infty$.

Finally, construct a separating set of lines $S$ by combining the $2L$ lines of the auxiliary grid with one separating line for each pair $(i,j)$ counted in $M$ (we can take half of these lines vertical and half horizontal). Then $P(|S| \ge 3L) \to 1$ as $n \to \infty$ and $p_n(3L/2) \to 1$ as well.

[1] McDiarmid, Colin. "Concentration." In Probabilistic methods for algorithmic discrete mathematics, pp. 195-248. Springer, Berlin, Heidelberg, 1998.http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8B1FFFE4553B63543AFEA0706E686E65?doi=10.1.1.168.5794&rep=rep1&type=pdf

[2] McDiarmid, C. (1989). "On the method of bounded differences". Surveys in Combinatorics. London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Press. pp. 148–188. MR 1036755

Answer 2

Interestingly, if we allow the lines to have arbitrary directions, it still requires roughly n^{4/3} (up to a log correction) lines to separate all the points.

https://www.cambridge.org/core/journals/proceedings-of-the-london-mathematical-society/article/economical-covers-with-geometric-applications/486374A93F4351DF26C155F6C3FE35AE

Answer 3

Label your $N$ points as $(x_i,y_{\sigma(i)})$ with $x_1 < \cdots < x_N$ and $y_1 < \cdots < y_N$ ; this defines a uniform random permutation $\sigma \in \mathfrak{S}_N$, and all the information about the problem is encoded in $\sigma$.

Let $C$ be the number of axis-parallel cuts needed to scatter all the points. An easy lower bound is $C \geq L-1$, where $L$ is the length of the longest monotone subsequence of $\sigma$. It is well known that $L \sim 2 \sqrt{N}$ in probability, so if we could show that the above lower bound is typically sharp, this would solve the problem.

Answer 4

This is to show rigorously that the uniform rectangular grid does not work -- cf. the answer by mike. As in the answer by Dieter Kadelka, suppose that the $cn$ vertical lines and the $cn$ horizontal lines partition the unit square into $$N:=(cn+1)^2$$ small squares of equal area $1/N$, where $c\ge1$. Let $$K:=n^2.$$ Then the probability that each small square contains at most one random point is \begin{aligned} \frac{N(N-1)\cdots(N-K+1)}{N^K}&=\Big(1-\frac1N\Big)\cdots\Big(1-\frac{K-1}N\Big) \\ &<\exp\Big\{-\sum_{k=1}^{K-1}\frac kN\Big\} \\ &=\exp\Big\{-\frac{(K-1)K}{2N}\Big\}\to0\ne1 \end{aligned} as $n\to\infty$, as claimed.

(I don't think any choice -- even a random one, depending on the random points -- of $cn$ lines in both the vertical and horizontal directions is enough, for any real $c>0$. I think, instead of $cn$, one needs at least something like $n\ln^a n$ for some real $a>0$.)

Answer 5

If we draw the horizontal lines to have $p$ rows with $n^2/p$ points each, then finding where to put the vertical lines becomes a birthday problem : we take the points from left to right and find in wich row they belong. When the row is already taken, we must draw a vertical line and start a new column. Set $X_i$ the number of points in column $i$. The repartition function of $X_1$ converges to $\exp(-x^2/p)$.

If we can suitably control the law of the other $X_i$, this would give an order of $n^2/\sqrt{p}$ columns. For $p\sim n^{4/3}$, this means around $n^{4/3}$ columns.

This provides as upper bound an order of $n^{4/3}$ horizontal lines and vertical lines. If some form of concentration occur for the size of the columns, we would get a critical value at $c_{crit}n^{4/3}$, with proba 1 of having a solution for constants larger than $c_{crit}$.

Answer 6

Nikita Kalinin, you were right, this problem indeed reduces to a rather general form of the law of large numbers, namely subadditive ergodic theorem! This theorem is used, e.g., to prove the result on the length of the largest increasing subsequence mentioned by Guillaume Aubrun (thanks for hinting the direction). So I just mimic its proof due to Hammersley (see, e.g. Example 7.5.2 in Durrett's "Probability: Theory and Examples").

First of all, as noted above, instead of the original setting with $n^2$ points in $[0,1]^2$ we can consider your question for a Poisson point process (PPP) of unit intensity on the positive quadrant restricted to $[0,n]^2$.

For any integer $0 \le m <n$, let $C_{m,n}$ be the minimal positive integer number such that it is possible to cut the rectangle $[[m,n]]:=\{(x,y) \in [0, \infty)^2: m \le x, y \le n\}$ with the points of the PPP using $C_{m,n}$ horizontal and $C_{m,n}$ vertical cuts to satisfy the condition. The key observation is that $$C_{0,m} + C_{m, n} \le C_{0,n}.$$ Indeed, just use optimal cuts to cut $[[0,m]]$ and $[[m,n]]$; then more cuts may be needed.

By the subadditive ergodic theorem, $$\lim_{n \to \infty}\frac{C_{0,n}}{n} = \sup_{n \ge 1} \frac{E C_{0,n}}{n}:=c, \qquad a.s.$$

Now the problem is to figure out whether $c$ is finite or not, which is the most interesting bit. I did not succeed so far.

One way to prove finiteness is to show that $E C_{0, n+1} - E C_{0,n}$ is bounded. This appears to be wrong on a first sight, but apparently this is not so trivial. On the other hand, finiteness would mean that cutting $[[0,n]]$ and $[[n, 2n]]$ in a nearly optimal way would automatically fix the two remaining subsquares of $[[0,2n]]$. This should not be true, but not simple to prove as well.

The last comments are that the same argument goes through if replace $C_{m,n}$ by the total number of horizontal and vertical cuts. And the sequence $E C_{0,n}/n$ is strictly increasing.

Answer 7

Not and answer, but a long comment: I don't think a uniform rectangular grid works. Take a planar poisson process with intensity 1 and look at (0,n)x(0,n). This is your setup except I have replaced the uniforms with a poisson process with an expected n^2 events in the space. Divide it into a rectangular grid with (cn)^2 rectangles of area 1/c^2 each. The number of points in each rectangle is poisson with parameter 1/c^2,and different rectangles are independent. You wonder if any have of the (cn)^2 rectangles have two points in them. As the parameter is fixed there is a probability going to 1 that at least one of them does.

Answer 8

It is sufficient to assume that the $cn$ vertical and $cn$ horizontal lines are at $\frac{1}{cn}, \frac{2}{cn+1}, \ldots$, so that we have $N := (cn+1)^2$ small rectangles each with area $p^{(n)} := \frac{1}{N}$. Let $X_1,\ldots,X_N$ be random variables with $X_i$ the random number of points in rectangle $i$. Then $X := (X_1,\ldots,X_N)$ has the multinomial (sometimes called polynomial) distribution $\cal{M}(n; p^{(n)},\ldots,p^{(n)})$ ($N$ parameters $p^{(n)}$). As far as I understand your problem you want an estimation for $\mathbb{P}(X_1 \leq 1, \ldots, X_N \leq 1)$. But $q^{(n)} := 1 - \mathbb{P}(X_1 \leq 1, \ldots, X_N \leq 1) \leq \sum_{i=1}^N \mathbb{P}(X_i \geq 2)$, where each $X_i$ has Binomial distribution $Bin(n,p^{(n)})$. Thus $q^{(n)} \leq N \cdot \left(1 - (1 - p^{(n)})^n - n \cdot p^{(n)} \cdot (1 - p^{(n)})^{n-1}\right)$, which goes to $0$ when $c > 1$.

Edit: The estimation above only works for $n$ points, not for $n^2$ points, as required.