20 votos

La probabilidad de que la mayor área permanece mayor que 1/2 en una unidad de corte cuadrado al azar líneas

El cuadrado de $[0,1]^2$ se corta en un número de regiones por $n$ líneas al azar. Podemos elegir estas líneas al azar por escoger al azar un punto en uno de los cuatro lados, cogiendo otro punto al azar de cualquiera de los otros tres lados y, a continuación, conectar los puntos. Hacemos esto $n$ veces.

¿Cuál es la probabilidad después de $n$ líneas que el más grande de la región tiene una superficie $1/2$ o más?

(Una pregunta de seguimiento: Es el círculo en el cuadrado mejor evitar líneas al azar?)

11voto

Will Sawin Puntos 38407

Aarón y fedja han señalado que el problema es equivalente a encontrar el lado convexo de la región en el plano con un área de $1/2$ con la más alta probabilidad de que un azar de la línea no se cruzan.

El óptimo convexa de la región de $\Delta$ tiene límite de una unión de ocho segmentos, cada uno la satisfacción de una ecuación diferencial a partir de una determinada familia de un parámetro, que por lo tanto son lisas.

Elige una esquina de la plaza, elegir las coordenadas de modo que la esquina es el punto de $(0,0)$, y considerar el segmento de la frontera $C$ de % de $\Delta$ cuya tangente a las líneas de contacto de los dos lados de la plaza adyacente a ese punto.

Si escribimos este segmento de $C$ como la gráfica de una función decreciente $y(x)$, entonces la recta tangente en el punto de $(x,y)$ conecta los puntos de $\left(x- \frac{y}{\dot{y}},0\right)$ e $\left(0, y+ \dot{y}x \right)$ en estas dos partes, en la $\dot{y}$ es la derivada con respecto al $x$. Así que si trazamos la región en la $a,b$ plano que consta de los $(a,b)$ de manera tal que la línea que conecta $(a,0)$ e $(b,0)$ no se cruzan $\Delta$, el límite de la región es la paramétricas de la curva de $\left(x- \frac{y}{\dot{y}}, y- \dot{y}x \right)$ y por lo tanto el área de la región es $$ - \int \left(x- \frac{y}{\dot{y}} \right) \frac{d}{dx} \left(y - \dot{y}x \right) dx$$

$$= - \int \left(x- \frac{y}{\dot{y}} \right) \left(\frac{dy}{x} - \ddot{y}x - \dot{y} \right) dx$$

$$= \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx$$

el signo negativo debido a $\left(y- \dot{y}x \right)$ es una función decreciente de $x$ por la convexidad.

Así que estamos optimizando $$ \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx$$ subject to an upper bound on $ \int y dx$ que por multiplicadores de Lagrange es equivalente a la optimización de

$$ \int x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) dx - \lambda \int y dx$$

para algunos $\lambda>0$.

Por el cálculo de variaciones, si fijamos $F(y, \dot{y}, \ddot{y}) = x \ddot{y} \left(x- \frac{y}{\dot{y}} \right) - \lambda y$, entonces el valor óptimo de $y$ satisface $$\frac{dF}{dy} - \frac{d}{dx} \left( \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \ddot{y}} \right) \right) =0$$

Podemos evaluar $$\frac{dF}{d \ddot{y}} = x^2 - \frac{xy}{\dot{y}}$$ $$\frac{d}{dx} \left(\frac{dF}{d\ddot{y}} \right)= 2x-\frac{y}{\dot{y}} - x + \frac{xy \ddot{y}}{\left(\dot{y}\right)^2}$$ $$ \frac{dF}{ d\dot{y}} =\frac{xy \ddot{y}}{\left(\dot{y}\right)^2}$$ $$ \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \ddot{y} }\right) = \frac{y}{\dot{y}} -x $$ $$ \frac{d}{dx} \left( \frac{dF}{d \dot{y}} - \frac{d}{dx} \left(\frac{dF}{d \frac{dy^2}{dx^2}}\right) \right) = 1 - \frac{y \ddot{y}}{\left( \dot{y}\right)^2} -1$$

$$\frac{dF}{dy} = - \lambda - x \frac{\ddot{y}}{\dot{y}}$$

de modo que la ecuación diferencial es

$$ - \lambda - x \frac{\ddot{y}}{\dot{y}} + \frac{y \ddot{y}}{\left( \dot{y}\right)^2} =0$$

o

$$ \lambda \left( \dot{y}\right)^2 +( x \dot{y} -y )\ddot{y} =0$$

Si dejamos $t= \dot{y} \frac{x}{y}$ ser la adimensional derivados, a continuación, $\dot{y} = t\frac{y}{dx}, \ddot{y} = \frac{d}{dx}\left( t\frac{y}{x}\right)= \dot{t}\frac{y}{x} + t^2 \frac{y}{x^2} - t \frac{y}{x^2} =\frac{y}{x^2} \left( \frac{dt}{d\log x} +t^2-t\right)$

así que podemos escribir la ecuación (haciendo caso omiso de los factores de $y$ o $x$) como

$$ \lambda t^2 + (t-1) \left( \frac{dt}{d\log x} + t^2-t \right) =0$$

$$\frac{dt}{d \log x} = - \lambda \frac{t^2}{t-1} + t -t^2 $$

así que ya tenemos $t$ una constante de la solución de $(t^2-t)(t-1) + \lambda t^2 =0$ con $y$ un número constante de veces $x^t$ o podemos expresar $\log x$ e $\log y$ como las integrales de funciones racionales de $t$.

$$\log x = \int \frac{1}{ - \lambda \frac{t^2}{t-1} + t -t^2} dt$$

$$\log y = \int \frac{t}{ - \lambda \frac{t^2}{t-1} + t -t^2} dt$$

Matt F. en los comentarios que hicieron los integrales y se encontró que las fórmulas, mientras explícita, son bastante desagradables. Tal vez esto se puede solucionar cambiando el parámetro, pero esto parece poco probable.

Debe ser posible hacer cálculos similares para los demás tipos de segmento, pero el siguiente paso sería calcular las diferentes maneras en que estos segmentos pueden ser cosidos juntos, lo que equivale a la solución de una ecuación con la participación de ocho de estas soluciones explícitas. Que parece difícil a menos que las soluciones son realmente agradable - aunque estoy seguro de que se puede hacer con la ayuda de un adecuado sistema de álgebra computacional.

7voto

Matthew Puntos 111

ACTUALIZADO de NUEVO Aquí hay algunos límites inferiores y los resultados de $10^6$ ensayos aleatorios. El $1$-dimensional caso es muy informativo y se discute al final.

Una forma de obtener una exponencial límite inferior es elegir un área de $1/2$ subconjunto y encontrar la probabilidad de que se mantiene intacta después de $n$ líneas. Inclinado, la plaza, la intacto isósceles triángulo rectángulo después de la primera línea (si hay uno), con una óptima octágono y centrada en el círculo (en ese orden) dar a tales límites que son cada vez más bueno. Sin embargo, un modelo exponencial no es el adecuado para el uso.

  • La posibilidad de que una sola línea evita el inclinada cuadrado con esquinas $(1/2,0),(1,1/2),(1/2,1),(0,1/2)$ (de área $1/2$) es $1/6:$ Con una probabilidad de $1$, el punto elegido no es una esquina de la original plaza o inclinada uno. wlog está en la mitad izquierda de la parte inferior. A continuación, el segundo punto tiene que estar en la mitad inferior del lado derecho. La posibilidad de que este es 1/6. Así que la probabilidad de que ninguno de $n$ líneas de corte inclinada cuadrado es $$\frac1{6^{n}}.$$

  • Esto puede ser mejorado para $$\frac4{6^n}=\frac2{3\cdot 6^{n-1}}$$ by considering instead isosceles right triangles. The chance that the first line crosses two adjacent sides is $2/3.$ If this does happen then one of the diagonals misses this line and splits the square into two isosceles right triangles with area $1/2.$ One is cut and the other intact. For every subsequent choice the first point is outside the intact half with probability $1/2$ and the second with probability $1/3.$

  • Aquí está una cierta octágono junto con el círculo con el centro $(\frac12,\frac12)$ y radio de $\frac1{\sqrt{2\pi}}.$ enter image description here Me parece que el octágono de arriba es el mejor de su clase. Me sale que la probabilidad de que se mantiene intacto es acerca de $$(\frac{2(0.4797667)}3)^n=0.31984^n.$$ The lower left corner is at about $(0.32606,0.11670).$

  • Para el octágono, y también el círculo, la probabilidad exacta de una línea de falta puede, en principio, se encuentran el uso de varias de las integrales. No son agradables, así que he evaluado numéricamente. La probabilidad de una línea que faltan el círculo es acerca de $.34470989$ por lo tanto $$0.34470989^n.$$

    Tal vez algunos de la forma de la forma $t$círculo+$(1-t)$octágono latidos del círculo. Sin embargo, otro de octagon podría hacerlo aún mejor para ese proceso.


No es tan difícil generar aleatoriamente líneas. Solo hay que seguir la pista de los vértices de la superficie máxima de la región. A continuación, una nueva línea o bien se pierde o se cruza con dos de los lados de la creación de dos nuevos vértices y dos regiones.

En $10^6$ random ensayos sucedió $4$ veces que solo el $20$th línea a la izquierda de todas las regiones con un tamaño inferior a $\frac12.$ curso De la primera línea está siempre bien. $187209$ los tiempos de la segunda línea fue fatal, el otro $812791$ no lo era. El recuento de

$$[1, 1000000], [2, 812791], [3, 580116], [4, 376623], [5, 228824], [6, 131445],$$$$ [7, 72077], [8, 38186], [9, 19805], [10, 10009], [11, 4852], [12, 2299],$$$$ [13, 1070], [14, 540], [15, 259], [16, 113], [17, 47], [18, 18], [19, 4]$$

Según lo sugerido por Emil, el modelo correcto es, posiblemente, de la forma $f(n) c^n$ para algunos $f(n)$ con sub-exponencial de crecimiento. Esto es apoyado por el siguiente:


Considere el problema similar en $1$-dimensión:

El intervalo de $[0,1]$ se divide en $n+1$ subintervalos por $n$ puntos al azar. ¿Cuál es la probabilidad de que la mayor subinterval tiene una longitud de, al menos, $\frac12?$

Resulta que la respuesta exacta es $\frac{n+1}{2^n}.$ es más fácil demostrar el más general de la forma: Dado que la más grande en la actualidad sobreviven intervalo de longitud de $\frac12+x,$ la probabilidad de sobrevivir a la próxima $n$ puntos al azar es $$\frac{n(2x-1)+1}{2^n}.$$

Dado este resultado exacto, no tenemos un límite superior. Pero conseguir una me ayudó a entender Cristiana del método: yo creo que un límite superior, válido para todas las $n$ es $$N\left(\frac12+\frac1N\right)^n.$$ Fix an integer $N>2$ and consider the $N$ intervals $I_t=[\frac{t}{2N},\frac{t}{2N}+\frac{N-1}{2N}]$ with $1 \leq t \leq N.$ A subinterval $[s,s+\frac12]$ contains one of these (move each endpoint inward to the nearest $\frac{a}{2n}.$) If some interval of length $\frac12$ stays undivided, so does at least one of the $I_t.$ The chance that any particular one stays undivided by $n$ random points is $(\frac12+\frac1N)^n.$ So the chance that at least one does is less than $N\left(\frac12+\frac1N\right)^n.$ Este es un límite superior a lo que buscamos.

6voto

Chris Amos Puntos 6

Esto es realmente un comentario a ChristianRemling que requiere de una figura, así que por favor, no hacia abajo votar.


Si "todas las líneas se conectan dos bordes adyacentes" (como se escriba), entonces la probabilidad de que una región de área mayor que $1/2$ sobrevive siempre es 1.0, como se ilustra en esta figura:

enter image description here

Tenga en cuenta que cada apretado obligado (por la plena problema con el arbitrario borde de conexiones) debe producir para $n=1$ que la probabilidad es $1.0$. (Varias propuestas de respuestas no tienen ese valor.) El menor límite inferior de $n=2$ es claramente $0$, como es posible que las dos líneas de dividir el área en regiones, cada uno con un área inferior a $1/2$.


Alguna información de fondo: ¿Cuál es el tamaño promedio de la restante más grande de la región después de que el primer corte?

Uno de los lados es elegido para el primer punto, y (sin pérdida de generalidad) que nos rotar la figura, de modo que esto es en la parte inferior. Llame a la posición de su extremo $x_1$. Hay tres lados restantes, cada uno elegido con una probabilidad de $1/3$. El punto en un lado adyacente (ver figura de la izquierda) es a las $x_2$ y el área de la porción más grande es $1 - x_1 x_2/2$. (Los cálculos para el otro lado adyacente son equivalentes). Por el lado opuesto (ver figura derecha) crea dos zonas, y se elige la más grande. El área de espera de los más grandes supervivientes de la región es por lo tanto:

${1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 (1 - x_1, x_2/2)\ dx_1\ dx_2 \\ + {1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 (1 - x_1, x_2/2)\ dx_1\ dx_2 \\ + {1 \over 3} \int\limits_{x_1=0}^1 \int\limits_{x_2=0}^1 \max({1 \over 2} |x_2-x_1| + x_1, 1 - {1 \over 2} |x_2-x_1| + x_1)\ dx_1 dx_2 \\ = {1 \over 3}{7 \más de 8} + {1 \over 3}{7 \más de 8} + {1 \over 3}{2 \más de 3} = {29 \más de 36}$.

enter image description here

Ahora uno podría hacer el muy simplificada supuesto de que las formas de estas regiones en los sucesivos recortes son independientes (no!) y calcular la espera "sobrevivir" más grande de la zona de intersección de las áreas, a continuación, calcular la probabilidad de este área es mayor que $1/2$ como una función de la $n$.

6voto

Chad Okere Puntos 3181

Un crudo, pero es fácil de comprobar, dado fedja del comentario de Aaron respuesta) límite superior es $(2/3+\epsilon)^n$ para todos los $\epsilon>0$ y para un gran $n$.

De esta manera se sigue por la observación de que, si reparamos cualquier punto sobre la línea de frontera y conectarlo a uno o dos arcos cuya longitud combinada es más que $2/3$ de los tres lados restantes, el área cubierta es siempre $>1/2$. Así que para cualquier área convexa $|A|\ge 1/2$ cualquiera, la probabilidad de no golpear a $A$ con una muestra aleatoria de la línea de es $p_A\le 2/3$.

Para un determinado $\delta>0$, podemos encontrar un número finito de conjuntos de $A_1,\ldots , A_N$ (polígonos convexos, digamos), $|A_j|\ge 1/2-\delta$, de tal forma que cada convexo $|A|\ge 1/2$ contiene un $A_j$. (Esto parece intuitivamente claro, pero para ser perfectamente honesto, yo no creo mucho sobre esto; es similar en espíritu a los subconjuntos compactos de ser un espacio compacto de sí mismos con respecto a la distancia de Hausdorff.)

Como se discutió anteriormente, la probabilidad de que un azar de la línea de intersección no $A_j$ es $\le 2/3+\epsilon$, por lo que la demanda de la siguiente manera.

6voto

Tobias Puntos 126

El pensamiento de los números en un reloj de la cara, decir que una de estas líneas es:

  • un 8-2 barra iff va de $(0,L)$ a $(1,R)$ con $0<L<3/7<4/7<R<1$.
  • un 11-5 barra iff va de $(T,1)$ a $(B,0)$ con $0<T<3/7<4/7<B<1$.

enter image description here

Cada una de estas figuras se muestra un 8-2 barra (en rojo), un 11-5 barra (en azul), y de los rangos aceptables para los extremos (en verde).

Un 8-2 barra y un 11-5 slash juntos dividir el cuadrado en piezas de área en la mayoría de los 227/455, que es menor que 1/2, y que es el caso que se muestra en la segunda figura. Así que la probabilidad de que $n$ líneas de salir de una única región de área mayor que 1/2 es en la mayoría de los

$$P(\text{no 8-2 slashes}) + P(\text{no 11-5 slashes}) - P(\text{no 8-2 slashes & no 11-5 slashes}).$$

Ahora consideran que la probabilidad de un 8-2 de slash. La probabilidad de que un elegido al azar de la línea que va desde la parte superior hasta la parte inferior es $1/6$. La probabilidad de que una línea es un 8-2 slash es $(3/7)^2$, por lo que la probabilidad total de un 8-2 slash es $3/98$. Esta es la misma que la probabilidad de un 11-5 barra.

Por lo tanto la probabilidad de una ininterrumpida región de área mayor que 1/2 es en la mayoría de los $$\left(1-\frac{3}{98}\right)^n + \left(1-\frac{3}{98}\right)^n - \left(1-\frac{6}{98}\right)^n = 2\left(\frac{95}{98}\right)^n - \left(\frac{92}{98}\right)^n .$$

Esto es suficiente para establecer una exponencial límite superior.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X