Gotas de lluvia cayendo sobre una mesa

Question

Supongamos que tenemos una mesa circular de radio $R$ . Esta mesa se ha dejado fuera y empieza a llover a un ritmo constante de una gota por segundo. Las gotas, que pueden considerarse puntos a medida que caen, sólo pueden caer de forma que impacten en la superficie de la mesa. Una vez que golpean la mesa, forman un charco de radio $r$ centrados en su punto de impacto. ¿Cuál es el número esperado de gotas necesarias para cubrir la mesa de agua?

La respuesta debe dejarse en términos de $R$ y $r$ . Sin embargo, si se puede simular esto, mientras que el cambio de ambos $r$ y $R$ de modo que se pueda aplicar alguna regresión para encontrar la relación aproximada, eso también estaría bien. Me gustaría tener alguna intuición sobre cómo se relacionan ambas cosas.

He intentado descomponer el problema considerando sólo el caso unidimensional con segmentos de línea, pero incluso su solución se me ha escapado. Un posible punto de partida podría ser el caso discreto de las canicas que caen en cubos.

La siguiente edición fue sugerida por Jbeuh :

Un replanteamiento más formal del problema :

Consideremos una secuencia $X_1,\ldots,X_n$ de variables aleatorias independientes que siguen una distribución uniforme en un disco $D$ de radio $R$ . Para cada $i$ , dejemos que $C_i$ sea el disco centrado en $X_i$ con radio $r$ . Sea $Y$ ser el primero $i$ tal que los discos $C_1,\ldots,C_i$ forma una cubierta de $D$ . ¿Cuál es el valor esperado de $Y$ ?

Answer 1

Hay un buen enfoque en Cobertura de las redes de sensores inalámbricos desplegadas aleatoriamente de Wan y Yi que nos permite obtener una expansión en $\mu:=R/r$ para el número previsto de gotas de lluvia necesarias.

La idea básica es centrarse en las intersecciones entre los círculos. Dado que cualquier área descubierta debe estar delimitada por arcos delimitados por intersecciones que no estén cubiertas por otros discos, toda la mesa está cubierta si y sólo si hay al menos una intersección y no hay ninguna intersección descubierta. Aquí las intersecciones incluyen las intersecciones entre los círculos de la gota de lluvia y el círculo de la mesa.

Consideremos primero la probabilidad de que haya al menos una intersección, descubierta o no, entre un círculo de la gota de lluvia y el círculo de la mesa. El centro de la gota de lluvia debe encontrarse dentro de $r$ del círculo de la mesa, y la probabilidad para ello es $1-\pi(R-r)^2/(\pi R^2)=2\mu^{-1}\left(1+O\left(\mu^{-1}\right)\right)$ . Dado que necesitamos al menos $\mu^2$ para cubrir la mesa, la probabilidad de que ninguna de ellas intersecte el círculo de la mesa se reduce a cero. Así, asintóticamente la probabilidad de que la mesa esté cubierta se convierte en la probabilidad de que no haya intersecciones sin cubrir.

Dado que la probabilidad de que el círculo de la gota de lluvia intersecte el círculo de la mesa es $2\mu^{-1}\left(1+O\left(\mu^{-1}\right)\right)$ el número esperado de intersecciones entre el círculo de la gota de lluvia y el círculo de la mesa es $2n\mu^{-1}\left(1+O\left(\mu^{-1}\right)\right)$ donde $n$ es el número de gotas. Cada una de ellas puede ser cubierta por cualquiera de las restantes $n-1$ discos, con probabilidad $\mu^{-2}$ cada una (sin tener en cuenta los efectos frontera), por lo que el número esperado de intersecciones sin cubrir de este tipo es de $2n\mu^{-1}\left(1-\mu^{-2}\right)^{n-1}\left(1+O\left(\mu^{-1}\right)\right)$ . Para que dos círculos de gotas de lluvia se crucen, sus centros tienen que estar como máximo a $2r$ y (de nuevo sin tener en cuenta los efectos fronterizos) la probabilidad de que esto ocurra es $\pi(2r)^2/\pi R^2=4\mu^{-2}$ . Por lo tanto, el número esperado de intersecciones entre $n$ círculos de gotas de lluvia es $4n(n-1)\mu^{-2}$ (ya que hay $n(n-1)/2$ pares y cada par de intersección contribuye $2$ intersecciones). De nuevo, cada una de ellas puede ser cubierta por cualquiera de las restantes $n-2$ discos, con probabilidad $\mu^{-2}$ cada una, por lo que el número esperado de intersecciones sin cubrir de este tipo es de $I(n)=4n(n-1)\mu^{-2}\left(1-\mu^{-2}\right)^{n-2}$ . Desde $n\ge\mu^2$ Esto domina la contribución de las intersecciones con el círculo de la mesa por un factor de $\mu$ por lo que podemos despreciar las intersecciones con el círculo de la tabla si sólo queremos los términos principales de la expansión; éste es el mismo nivel de aproximación que el aplicado al tomar la fracción de área cubierta por una gota de lluvia como $\mu^{-2}$ y sin tener en cuenta los efectos fronterizos.

Por esa aproximación, $I(n)$ es un límite superior para la probabilidad de que al menos una intersección, y por tanto alguna parte de la tabla, esté descubierta. En $n=\mu^2$ aproximadamente $(4/\mathrm e)\mu^2$ y, por tanto, mayor que $1$ para un $\mu$ . Desde $n\ge\mu^2$ podemos sustituir el límite superior por $1$ hasta $\mu^2$ y también hasta el punto $n_0$ donde $I(n)$ cae por debajo de $1$ otra vez.

Desde $n\ge\mu^2$ podemos aproximar $n-1$ y $n-2$ por $n$ y obtener $n_0$ como la mayor de las dos soluciones reales de la ecuación resultante $4n^2\mu^{-2}\left(1-\mu^{-2}\right)^n=1$ :

$$ n_0\approx\frac{2W_{-1}\left(\mu\log\left(1-\mu^{-2}\right)/4\right)}{\log\left(1-\mu^{-2}\right)}\;, $$

donde $W_{-1}$ es la rama inferior del Función W de Lambert .

Ahora el número esperado de gotas necesarias para cubrir la mesa es

$$ \begin{align} \langle N\rangle &= \sum_{k=0}^\infty kP(N=k) \\ &= \sum_{k=0}^\infty P(N\gt k) \\ &\lesssim \sum_{k=0}^\infty\min(1,I(k)) \\ &\le n_0+\sum_{k=\lfloor n_0\rfloor}^\infty I(k)\;. \end{align} $$

Podemos aproximar la suma restante mediante una integral:

$$ \begin{align} \sum_{k=\lfloor n_0\rfloor}^\infty I(k) &\approx \int_{n_0}^\infty \left.4\mu^{-2}\frac{\partial^2}{\partial q^2}q^k\right|_{q=1-\mu^{-2}}\,\mathrm dk \\ &= -\left.4\mu^{-2}\frac{\partial^2}{\partial q^2}\frac{q^{n_0}}{\log q}\right|_{q=1-\mu^{-2}} \\ &= -\left.4\mu^{-2}n_0(n_0-1)\frac{q^{n_0-2}}{\log q}\right|_{q=1-\mu^{-2}}\left(1+O\left(\mu^{-2}\right)\right) \\ &= -\frac1{\log\left(1-\mu^{-2}\right)}\left(1+O\left(\mu^{-2}\right)\right) \\ &= \mu^2+O(1)\;. \end{align} $$

Ahora podemos utilizar el expansión asintótica de $W_{-1}$ ,

$$ W_{-1}(x)=\log(-x)-\log(-\log(-x))+\frac{\log(-\log(-x))}{\log(-x)}+O\left(\left(\frac{\log(-\log(-x))}{\log(-x)}\right)^2\right)\;, $$

para obtener una ampliación de $\langle N\rangle$ . Si sólo queremos los términos hasta $O\left(\mu^2\right)$ podemos sustituir $\log\left(1-\mu^{-2}\right)$ por $-\mu^{-2}$ en ambos casos para obtener

$$ \begin{align} n_0 &\approx -2\mu^2W_{-1}\left(-\frac1{4\mu}\right) \\ &= 2\mu^2\left(\log(4\mu)+\log(\log(4\mu))+\frac{\log\log(4\mu)}{\log(4\mu)}+O\left(\left(\frac{\log\log\mu}{\log\mu}\right)^2\right)\right)\;. \end{align} $$

A continuación, sumando el término de la suma restante se obtiene

$$ \langle N\rangle\lesssim2\mu^2\left(\log(4\mu)+\log(\log(4\mu))+\frac12+\frac{\log\log(4\mu)}{\log(4\mu)}+O\left(\left(\frac{\log\log\mu}{\log\mu}\right)^2\right)\right)\;, $$

donde el $\lesssim$ y el gran $O$ debe tomarse con un grano de sal, ya que no analicé ni el error de sustituir $n-1$ y $n-2$ por $n$ ni la de aproximar la suma por una integral, ni si la cota superior del método del primer momento es asintótica. Tal vez alguien más riguroso que yo pueda llenar algunas lagunas.

He hecho algunas simulaciones exactas (es decir, no discretizadas); los resultados concuerdan bien con la expansión anterior. El código es aquí . Corrí $1000$ ensayos cada uno para $1/20\le\mu^{-1}\le1$ en pasos de $1/100$ .

Este es un gráfico logarítmico de $\langle N\rangle$ en $\mu$ :

(Puedes obtener la resolución completa mostrando la imagen en otra pestaña o ventana). Las cruces rojas son los puntos de datos, y las curvas verde, azul, magenta y cian incluyen respectivamente los términos sucesivos de la expansión anterior. El hecho de que los términos sucesivos se acerquen cada vez más a los datos parece indicar que los errores no analizados son como mucho $O(\mu^2)$ .

Los errores estándar estimados para los puntos de datos de la simulación son demasiado pequeños para mostrarlos. Los valores y errores en diferentes $\mu$ están fuertemente correlacionadas, ya que el código funciona añadiendo sucesivamente centros de gotas de lluvia y bajando un umbral $r$ a la que las gotas en estos centros cubrirían la mesa; pero el conjunto de los ensayos es independiente, por lo que las estimaciones de error son válidas.

Unas palabras sobre el código: Subdivide recursivamente el cuadrado que contiene el círculo unitario; para cada cuadrado, calcula tres umbrales para $r$ lo menos $r$ para el que el cuadrado estaría parcialmente cubierto por exactamente una gota, la menor $r$ para las que el cuadrado estaría parcialmente cubierto por más de una gota, y la menor $r$ por lo que toda la plaza estaría mojada. Estos umbrales dividen el $r$ en cuatro rangos; en los dos primeros, se sabe que el cuadrado no está totalmente cubierto, en el último se sabe que está totalmente cubierto, y en medio (si hay más de una gota cubriéndolo parcialmente) la recursión tiene que descender al siguiente nivel para decidir. Las gotas de lluvia caen una tras otra, y después de cada gota se recogen los estadísticos de la media y la estimación de la varianza para los radios hasta los que la tabla está totalmente cubierta. Por supuesto, hay algunas complicaciones, como tratar con cuadrados en el borde de la mesa.

Descargo de responsabilidad : Este tipo de código es difícil de depurar completamente. He hecho algunas pruebas con configuraciones conocidas y espero haber detectado todos los errores, y la concordancia con la expansión analítica es tranquilizadora, pero no hay garantía de que algunos casos no estén siendo tratados incorrectamente.

[ Actualización: ]

Dado que mjqxxxx demostró elegantemente que el número esperado $\langle N\rangle$ de gotas está limitada desde abajo por $2\mu^2\log\mu(1+o(1))$ pensé que valía la pena hacer al menos la parte de mi argumento totalmente rigurosa que muestra que $\langle N\rangle$ también está limitada desde arriba por $2\mu^2\log\mu(1+o(1))$ ya que juntos implican $\langle N\rangle\sim2\mu^2\log\mu$ .

Consideremos de nuevo las intersecciones entre círculos. Como vamos a limitar la probabilidad de que la tabla no esté totalmente cubierta por su valor máximo $1$ para $n\lt\mu^2$ podemos descartar la posibilidad de que no haya ninguna intersección, ya que esto es imposible para $n\ge\mu^2$ . Por lo tanto, sólo tenemos que considerar la probabilidad de que haya una intersección sin cubrir. Como se ha mostrado anteriormente, ésta está asimétricamente dominada por la probabilidad de que haya una intersección descubierta entre círculos de gotas de lluvia, que es $4n(n-1)\mu^{-2}\left(1-\mu^{-2}\right)^{n-2}(1+o(1))$ (donde el $o(1)$ tiene en cuenta los efectos frontera en las fracciones de área $\mu^{-2}$ y $4\mu^{-2}$ ). Podemos acotar esto desde arriba mediante

$$ 4n^2\mu^{-2}\left(1-\mu^{-2}\right)^n\left(1-\mu^{-2}\right)^{-2}(1+o(1))=4n^2\mu^{-2}\left(1-\mu^{-2}\right)^n(1+o(1))\;. $$

A partir de la solución para $4n^2\mu^{-2}\left(1-\mu^{-2}\right)^n=1$ anterior en términos de $W_{-1}$ y su expansión asintótica, sabemos que podemos elegir un número entero $n_0=2\mu^2\log\mu(1+o(1))$ tal que este límite es $1+o(1)$ . Entonces podemos acotar la probabilidad de que la mesa no esté totalmente cubierta por $1$ para $n\le n_0$ y por el límite anterior para $n\gt n_0$ . Esto da una contribución $n_0$ al número previsto de discos de $n\le n_0$ que tiene el comportamiento asintótico correcto, por lo que sólo necesitamos demostrar que la contribución de $n\gt n_0$ es $o\left(\mu^2\log\mu\right)$ . Para ello, tomamos el logaritmo, lo acotamos linealmente mediante $\log n\le\log n_0+(n-n_0)/n_0$ y sumar las series geométricas resultantes:

$$ \begin{align} &\log\left(4n^2\mu^{-2}\left(1-\mu^{-2}\right)^n(1+o(1))\right) \\ =& \log\left(4\mu^{-2}\right)+2\log n+n\log\left(1-\mu^{-2}\right)+o(1) \\ \le& \log\left(4\mu^{-2}\right)+2\log n_0+2(n-n_0)/n_0+n\log\left(1-\mu^{-2}\right)+o(1) \\ =& (n-n_0)\left(2/n_0+\log\left(1-\mu^{-2}\right)\right)+o(1)\;, \end{align} $$

$$ \begin{align} &\sum_{n=n_0}^\infty\left(4n^2\mu^{-2}\left(1-\mu^{-2}\right)^n\left(1+o(1)\right)\right) \\ \le& \sum_{n=n_0}^\infty\exp\left((n-n_0)\left(2/n_0+\log\left(1-\mu^{-2}\right)\right)+o(1)\right) \\ =& \frac1{1-\exp\left(2/n_0+\log\left(1-\mu^{-2}\right)\right)}(1+o(1)) \\ =& \frac1{1-\left(1-\mu^{-2}\right)\exp\left(2/n_0\right)}(1+o(1)) \\ =& \frac1{1-\left(1-\mu^{-2}\right)\left(1+o\left(\mu^{-2}\right)\right)}(1+o(1)) \\ =& \mu^2(1+o(1))\;. \end{align} $$

Así $\langle N\rangle$ está limitada desde arriba por $2\mu^2\log\mu(1+o(1))$ y junto con el resultado de mjqxxxx se deduce que $\langle N\rangle\sim2\mu^2\log\mu$ .

P.D.: Obsérvese que ni el argumento de mjqxxxx ni el mío dependen de las formas de las gotas o de la tabla (en lo que respecta al término principal, no a las correcciones derivadas anteriormente). Así pues, podemos concluir de forma general que el número esperado de objetos con área una fracción $\lambda$ del área de la mesa que se requieren para cubrir toda la mesa es asintótica a $\lambda\log\lambda$ .

Answer 2

Para cualquier recubrimiento de la región objetivo con formas de diámetro $\le r$ si un centro de gota se encuentra dentro de cada forma, esto es suficiente para cubrir toda la región con gotas. Esto puede utilizarse para calcular un límite superior del tiempo previsto para cubrir la mesa. Tenga en cuenta que este límite superior será más estricto cuando el número de formas sea menor; es decir, queremos que el área de cada forma sea lo más grande posible. Supongamos que para cubrir la mesa se utilizan hexágonos regulares de diámetro $r$ : estos tienen área $3r^2\sqrt{3}/8$ por lo que habrá unos $$ N_{\rm hex} = \frac{8\pi}{3\sqrt{3}}\left(\frac{R}{r}\right)^2 $$ de ellos. El problema del recolector de cupones establece entonces que el tiempo esperado para golpear todos los hexágonos es $E[T_{\rm hex}] \sim N_{\rm hex}\ln N_{\rm hex}$ .

Por otra parte, para cualquier empaquetamiento de la región objetivo con discos de radio $r$ es necesario que al menos un centro de gota caiga dentro de cada disco para que se cubra la región objetivo (en particular, los centros de los discos no pueden cubrirse de otro modo). Esto puede utilizarse para obtener un límite inferior del tiempo previsto. Volvemos a utilizar un empaquetamiento hexagonal, que cubre una fracción $\pi/\sqrt{12}$ de la superficie de la mesa, pero ahora el área del hexágono es $2r^2\sqrt{3}$ . El número de discos es entonces $$ N_{\rm disc}=\frac{\pi}{2\sqrt{3}}\left(\frac{R}{r}\right)^2=\frac{3}{16}N_{\rm hex}. $$ El problema del recolector de cupones en este caso establece que el tiempo esperado para golpear todos los discos es $E[T_{\rm disc}] \sim \frac{\sqrt{12}}{\pi}N_{\rm disc}\ln N_{\rm disc}=\left(\frac{R}{r}\right)^{2}\ln N_{\rm disc}$ . Obsérvese el factor adicional de $\sqrt{12}/\pi$ que proviene del hecho de que cada gota sólo "recoge un cupón" con probabilidad $\pi/\sqrt{12}$ .

Juntando estos límites, tenemos que el tiempo esperado para cubrir la mesa satisface $$ 2 \mu^2 \ln \mu + O(\mu^2) = E[T_{\rm disc}] \le E[T] \le E[T_{\rm hex}] = \frac{16\pi}{3\sqrt{3}} \mu^2 \ln \mu + O(\mu^2) $$ para $\mu \equiv (R/r) \gg 1$ . En particular, se demuestra que el tiempo esperado es $\Theta(\mu^2 \ln \mu)$ con un factor multiplicativo acotado entre $2$ y sobre $9.68$ .

Answer 3

Permítanme hacer algunas aproximaciones de discretización a un círculo. Definamos un círculo de radio $r$ en el lugar $\bf x$ como el conjunto de todos los puntos $\bf y$ en una red en $\mathbb{Z}_d$ donde $\|{\bf x}-{\bf y}\|_2<r$ . Esto no es tan malo cuando $r \gg 1$ que se muestra a continuación es un "círculo" de radio 100:

La aproximación empeora cuando $r<10$ por lo que limitaremos todas las gotas a este tamaño. Para codificar un ejemplo simple de Monte Carlo hacemos un área cuadrada $A$ cuya longitud es $2R + 2r$ y poner una mesa circular en el centro de radio $R$ con una máscara positiva. Elija puntos en $A$ y mantenerlos si están dentro del radio $R$ . Para cada punto seleccionado, reste una máscara circular de radio $r$ . Continúe hasta que la tabla circular esté vacía y cuente las gotas necesarias. Un ejemplo de esto en movimiento se ve así:

Una serie temporal del logaritmo del área restante para una ejecución individual:

Hice 10 pruebas para $r \in 10..R-1$ y trazamos la media con la desviación estándar como barra de error.

No sé cómo describir la función; el mejor ajuste que se me ocurrió (que en realidad no es ningún ajuste) fue el siguiente $c \exp{(-17.9 (r/R)^{-1.6})}$ . Como mínimo, puedo decir que cae más rápido que una exponencial.

Para la posteridad y la integridad, el código que escribí está por debajo. Tenga en cuenta que se puede generalizar a $d$ ¡dimensiones!

from numpy import *

def circle(radius, dimension):
    A = zeros((2*radius+1,)*dimension)
    for idx in ndindex(A.shape):
        coord = array(idx) - radius # recenter
        r     = dot(coord, coord)
        A[idx] = r
    B = zeros(A.shape,dtype=bool)
    B[A<radius**2] = True
    return B

def spot_on_table(dimension):
    table_r_squared = table_r ** 2
    r2 = table_r_squared+1
    max_dim = 2*table_r
    while r2 > table_r_squared:
        pt = random.randint(-max_dim,max_dim,dimension)
        r2  = dot(pt,pt)
    return pt

def raindrop(table, droplet, loc, add=False):
    r = droplet.shape[0]/2
    center = array(table.shape[0])/2
    idx = [slice(center-r+x, center+r+1+x) for x in loc]
    idx = tuple(idx)

    if add: table[idx] += droplet
    else  : table[idx] *= ~droplet

def raindrop_question(dimension, droplet_r, table_r):
    random.seed()
    buff = droplet_r

    # Create the table
    table = zeros((2*table_r+1+2*buff,)*dimension)
    raindrop(table,circle(table_r,dimension), zeros(dimension), add=True)

    # Let it rain!
    counter = 0
    while table.any():
        raindrop(table,circle(droplet_r,dimension), spot_on_table(dimension))
        counter += 1

    return (dimension, droplet_r, table_r), counter

def CB(sol):
    print sol

import multiprocessing, itertools

dimension = 2
table_r   = 100
droplet_r = arange(10,table_r)

P = multiprocessing.Pool(16)

for r in droplet_r:
    for n in xrange(10):
        sol = P.apply_async(raindrop_question, (dimension, r, table_r),
                            callback=CB)
P.close()
P.join()

Answer 4

Un límite inferior aproximado viene dado por

$E(Y) \gt \frac{2 \pi}{\sqrt{27}} (\frac{R}{r})^2$ .

Esto se deduce considerando primero la colocación de radios- $r$ discos de forma no aleatoria para cubrir el radio más grande- $R$ disco. Según un ponencia de G. F. Tóth (p. 260), el número de radios- $r$ discos necesarios para ello es mayor que $m = \frac{2 \pi}{\sqrt{27}} (\frac{R}{r})^2$ en consecuencia, al azar La colocación de estos discos sólo puede alcanzar la cobertura total si hay más de $m$ de ellos, lo que implica $Y \gt m$ y, por tanto $E(Y) \gt m$ .