Una variación de la ley de los grandes números para puntos aleatorios en un cuadrado

Question

Yo marco uniformemente $n^2$ puntos en $[0,1]^2$ . Entonces quiero dibujar $cn$ líneas verticales y $cn$ líneas horizontales tales que en cada pequeño rectángulo haya como máximo un punto marcado. Seguramente, para una constante c dada no siempre es posible.

Pero parece que para $c=100$ cuando n tiende a infinito, la probabilidad de que exista ese corte debería tender a uno, como una variación de la ley de los grandes números. ¿Tienes alguna idea de cómo demostrar esto de forma rigurosa?

Answer 1

Dado $n^2$ puntos uniformes i.i.d. en $[0,1]^2$ el objetivo es dibujar una configuración de $cn$ líneas verticales y $cn$ líneas horizontales tales que en cada pequeño rectángulo haya como máximo un punto marcado.

A continuación mostramos que $c$ debe satisfacer $c=\Omega(n^{1/3})$ para que esto sea típicamente posible:

De hecho, $\Theta(n^{4/3})$ son necesarias y suficientes para que dicha configuración exista con una probabilidad sustancial.

Más concretamente, denotemos por $p_n(k)$ la probabilidad de que una configuración de $k$ líneas verticales y $k$ las líneas horizontales separan $n^2$ puntos uniformes i.i.d. $\{x_j\}_{j=1}^{n^2}$ en $[0,1]^2$ .

Reclamación: Para constantes adecuadas $0<c_1<c_2<\infty$ tenemos (omitiendo los símbolos de la parte entera):

(a) $\; p_n(c_1 n^{4/3}) \to 0$ como $n \to \infty$ y

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

Esto se demuestra a continuación con $c_1=1/20$ y $c_2=3/2$ no se ha intentado optimizar estas constantes.

Prueba: Consideremos una malla auxiliar de $L:=n^{4/3}$ líneas verticales uniformemente espaciadas y $L$ líneas horizontales uniformemente espaciadas en el cuadrado de la unidad. Esta cuadrícula define $L^2$ cuadrados de cuadrícula de lado $1/L$ .

(a) Llamar a un cuadrado de la cuadrícula $Q$ agradable si contiene exactamente dos de los $n^2$ puntos dados $\{x_j\}$ . Obsérvese que para dos cuadrados de la cuadrícula distintos, los eventos que son agradables están correlacionados negativamente. Llamamos a un cuadrado agradable $Q$ bueno si hay como máximo otro cuadrado bonito en su fila y como máximo otro cuadrado bonito en su columna. La probabilidad de que un cuadrado específico de la cuadrícula $Q$ es agradable es $${n^2 \choose 2}L^{-4}(1-L^{-2})^{n^2-2}=(1/2+o(1))L^{-1}.$$
Dado que $Q$ es agradable, La expectativa condicional del número de cuadrados agradables (que no sean $Q$ ) en la fila de $Q$ es $1/2+o(1)$ Así, dado que $Q$ es agradable, la desigualdad de Markov implica que la probabilidad condicional de que haya dos o más cuadrados agradables adicionales en la fila de $Q$ (además $Q$ ) es, como máximo, de $1/4+o(1)$ . Lo mismo ocurre con la columna de $Q$ y deducimos que $$P(Q \; {\rm is \; good}\; | Q \; {\rm is \; nice}) \ge 1/2+o(1) \, ,$$ así que $$P(Q \; {\rm is \; good} ) \ge (1/4+o(1))L^{-1} \, .$$ Dejemos que $G$ denotan el número de cuadrículas buenas. Entonces la media satisface $$E(G) \ge (1/4+o(1))L \,.$$ Obsérvese que si sustituimos un punto $x_i$ por $x_i'$ entonces $G$ cambiará como máximo en 5, por lo que la desigualdad de Mcdiarmid, véase [1, Teorema 3.1] o [2], implica que para $n$ lo suficientemente grande, $$P(G \le L/5) \le \exp(-\frac{(L/21)^2}{25n^2}) \to 0 \,. {\rm as} \; n \to \infty \,.$$ (Como alternativa, se podría invocar la desigualdad de Efron-Stein o estimar la varianza directamente para comprobarlo). Supongamos ahora que $S$ es un conjunto de líneas verticales y horizontales que separan los puntos $\{x_j\}_{j=1}^{n^2}$ . Para cada cuadrícula buena $Q$ , una línea de $S$ es necesario para separar los dos puntos $x_i, x_j$ en el cuadrado, y cada una de esas líneas puede utilizarse como máximo para dos cuadrados buenos. Así, $|S| \ge G/2$ así que $$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 por $M$ el número de pares $(i,j)$ tal que $1 \le i<j \le n^2$ y $x_i,x_j$ caen en la misma casilla de la cuadrícula. A continuación, $E(M) = {n^2 \choose 2}L^{-2} \le L/2$ y otra aplicación de la desigualdad de McDirarmid implica que $P(M \ge L) \to 0$ como $n \to \infty$ .

Por último, construye un conjunto de líneas de separación $S$ combinando el $2L$ líneas de la cuadrícula auxiliar con una línea de separación para cada par $(i,j)$ contados en $M$ (podemos tomar la mitad de estas líneas en vertical y la otra mitad en horizontal). A continuación, $P(|S| \ge 3L) \to 1$ como $n \to \infty$ y $p_n(3L/2) \to 1$ también.

[1] McDiarmid, Colin. "Concentración". En Probabilistic methods for algorithmic discrete mathematics, pp. 195-248. Springer, Berlín, 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). "Sobre el método de las diferencias acotadas". Surveys in Combinatorics. London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Press. pp. 148-188. MR 1036755

Answer 2

Curiosamente, si permitimos que las líneas tengan direcciones arbitrarias, todavía se necesitan aproximadamente n^{4/3} (hasta una corrección logarítmica) líneas para separar todos los puntos.

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

Answer 3

Etiquetar su $N$ puntos como $(x_i,y_{\sigma(i)})$ con $x_1 < \cdots < x_N$ y $y_1 < \cdots < y_N$ esto define una permutación aleatoria uniforme $\sigma \in \mathfrak{S}_N$ y toda la información sobre el problema se codifica en $\sigma$ .

Dejemos que $C$ sea el número de cortes paralelos al eje necesarios para dispersar todos los puntos. Un límite inferior fácil es $C \geq L-1$ , donde $L$ es la longitud de la subsecuencia monótona más larga de $\sigma$ . Es bien sabido que $L \sim 2 \sqrt{N}$ en probabilidad, así que si pudiéramos demostrar que el límite inferior anterior es típicamente agudo, esto resolvería el problema.

Answer 4

Se trata de demostrar rigurosamente que la rejilla rectangular uniforme no funciona - véase la respuesta de mike. Como en la respuesta de Dieter Kadelka, supongamos que la $cn$ líneas verticales y el $cn$ Las líneas horizontales dividen el cuadrado de la unidad en $$N:=(cn+1)^2$$ pequeños cuadrados de igual superficie $1/N$ , donde $c\ge1$ . Sea $$K:=n^2.$$ Entonces la probabilidad de que cada cuadrado pequeño contenga a lo sumo un punto aleatorio es \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} como $n\to\infty$ como se ha reclamado.

(No creo que ninguna elección -incluso una al azar, según los puntos aleatorios- de $cn$ líneas en dirección vertical y horizontal es suficiente, para cualquier $c>0$ . Creo que, en lugar de $cn$ se necesita al menos algo así como $n\ln^a n$ para un verdadero $a>0$ .)

Answer 5

Si dibujamos las líneas horizontales para tener $p$ filas con $n^2/p$ puntos cada uno, entonces encontrar dónde poner las líneas verticales se convierte en un problema de cumpleaños: tomamos los puntos de izquierda a derecha y encontramos a qué fila pertenecen. Cuando la fila ya está ocupada, debemos trazar una línea vertical y empezar una nueva columna. Establece $X_i$ el número de puntos de la columna $i$ . La función de reparto de $X_1$ converge a $\exp(-x^2/p)$ .

Si podemos controlar adecuadamente la ley del otro $X_i$ Esto daría un orden de $n^2/\sqrt{p}$ columnas. Para $p\sim n^{4/3}$ Esto significa que alrededor de $n^{4/3}$ columnas.

Esto proporciona como límite superior un orden de $n^{4/3}$ líneas horizontales y verticales. Si se produce alguna forma de concentración para el tamaño de las columnas, obtendríamos un valor crítico en $c_{crit}n^{4/3}$ , con proba 1 de tener una solución para constantes mayores que $c_{crit}$ .