Hormiga en un círculo

Question

Una hormiga que está sentado en el medio de un círculo de radio de 3 metros. Cada minuto, la hormiga elige una dirección al azar y se mueve en línea recta de 1 metro.

En promedio, ¿cuánto tiempo tarda la hormiga para abandonar el círculo? Si ayuda a los cálculos, puede ignorar el hecho de que la hormiga puede técnicamente salir antes de la final de los minutos, en otras palabras, si la hormiga es de 0,5 metros desde el borde del círculo y camina hacia fuera, considere la posibilidad de un minuto, no de 30 segundos.

Normalmente soy bastante bueno en estos tipos de problemas, pero este parece más estadísticos en la naturaleza y no estoy seguro de cómo se enfoque. Obviamente la hormiga podría permanecer en el círculo por siempre vagando por todo, pero es estadísticamente imposible, es decir, la cantidad de tiempo promedio que la hormiga pasa en el círculo es un límite que converge (respuesta no es "tiempo infinito").

Me encantaría escuchar cualquier tipo de técnicas en la solución de este problema.

Answer 1

Llamar a $\mathbb{E}(d)$ el tiempo de espera para salir del círculo si usted está en la distancia $d$, $\mathbb{E}(d)$ debe tener la siguiente propiedad: $$\mathbb{E}(d)=1+\frac{1}{2\pi}\int_0^{2\pi}\mathbb{E}(\sqrt{d^2+1-2d\cos\alpha})d\alpha$$ with the constraint $\mathbb{E}(d)=0$ if $d>3$.

Esta fórmula de decir que la espera de la salida es 1 (el costo de hacer otro paso) + la media del tiempo de espera en cada punto en la distancia 1 desde el punto actual ($\sqrt{d^2+1-2d\cos\alpha}$ es el coseno de la ley aplicada en el triángulo entre el origen, el punto actual y el siguiente punto).

No sé cómo explícita resolver esta ecuación (ni si es factible hacer), pero puede ser utilizado de forma iterativa para aproximar la solución.

edit: he tratado de resolver con R, parece que la solución es $\mathbb{E}(0)\simeq11.42$, y este es el argumento de la aproximación de la función:

Answer 2

La hormiga de la posición en cada momento $n\in\mathbb{N}$ es una variable aleatoria que podríamos modelo en el plano complejo como $Z_0=0$, $Z_n=Z_{n-1}+\Delta Z_n=\sum_{k-1}^n\Delta Z_k$ para los movimientos $\Delta Z_n=e^{i\Theta_n}$ que se yo.yo.d. y que dependen de uniforme que yo.yo.d. al azar varia $\Theta_n=2\pi\,U_n\sim\operatorname{Unif}\left(0,2\pi\right)$ . Si nosotros también vamos a $$R_n=|Z_n|\,, \qquad S_n=\sup\limits_{1\le k\le n}R_n \qquad \text{y} \qquad T=\inf\left\{n\mediados de R_n>R\right\}$$ la primera vez que los $n$ que $R_n>R=3$, entonces estamos pidiendo $\mathbb{E}[T]$, que puede calcularse como $$\mathbb{E}[T]=\sum_{n=R}^{\infty}n\cdot\mathbb{P}[R_{n-1} < R < R_n]\,.$$ Ahora, si nos deje $F_n(r)=\mathbb{P}[R_n &lt r]$ y deje $f_n(r)=\mathbb{P}[R_n = r]$ ser el PDF y el CDF de $R_n$, podemos ver que $F_n(n)=1$, y podemos ser capaces de determinar estas funciones de manera inductiva, con una recursividad: $$\eqalign{ F_n(r) y= \mathbb{P}[R_n < r]\\&= \mathbb{P}[R_{n-1} < r-1]+ \mathbb{P}[R_n<r\,|\,r-1< R_{n-1}< r+1] \\&= F_{n-1}(r-1)+ \int_{i-1}^{i+1} f_{n-1}(s)\cdot \mathbb{P}[R_n<r|R_{n-1}=s] \,ds }$$ El último integral, ciertamente, puede ser dividido en los dos casos $s&ltr$ $s>r$ , por lo que la probabilidad indeterminada dentro de el integrando puede ser evaluado usando la geometría restando el área de los sectores de círculos y triángulos para $s>r$):

$$\eqalign{ \mathbb{P}[R_n<r|R_{n-1}=s]&= \left\{ \begin{align} 1-\frac{\beta -r^2 \alpha}{2\pi} && s \le r\\ \frac{A_\gamma+r^2A_\alpha}{2\pi} && s \gt r\\ \end{align} \right. }$$ donde los ángulos $\alpha,\beta,\gamma$ puede ser expresado usando la ley de cosenos: $$\eqalign{ \cos\alpha &=\frac{r^2+s^2-1}{2rs}\\ \cos\beta &=\frac{r^2-s^2-1}{2} \qquad\text{o}\qquad\sin\beta=r\,\sin\alpha\\ \cos\gamma &=\frac{-r^2+s^2+1}{2}=-\cos\beta\\ }$$ (o resuelto a partir de las ecuaciones $re^{i\alpha}=s+e^{i\beta}$ & $\beta+\gamma=\pi$, de los cuales uno se puede inferir que los diagramas para cada caso) y $A_\alpha=2\alpha-\sin2\alpha$ es dos veces el área de $\{z\in\mathbb{C}:\,|z|>r,\,|z-s|&lt1\}$.

Bueno, es un comienzo. Seguramente hay una forma más elegante de recursividad; tal vez @carlop ha encontrado.

Answer 3

Sólo por diversión y sencillez, he aquí los resultados si la hormiga se vieron limitados a 1 dimensión (sólo puede moverse a la izquierda o a la derecha). También tenga en cuenta que yo consideraba la hormiga, cuando él llega a 3 del centro:

1E:  1 from edge
  Move Out: Exit and stop considering ant
  Move In: Goto 2E
2E:  2 from edge
  Move Out: Goto 1E
  Move In: Goto C
C:  Center
  Move Right or Left: Goto 2E

After Move 1: 1:1 at 2E
After Move 2: 1:2 at 1E, 1:2 at C
After Move 3: 1:4 out, 3:4 at 2E
After Move 4: 1:4 out, 3:8 at 1E, 3:8 at C
After Move 5: 7:16 out, 9:16 at 2E

Posibilidad de estar en 2E después de (1 + 2*n) movimientos: $$(3/4)^n$$ Oportunidad de estar en los puntos (1 + 2*n) movimientos: $$1 - (3/4)^n$$ Probabilidad de que una hormiga en el (1 + 2*n)th mover: $$(1 - (3/4)^n) - (1 - (3/4)^{n-1}) = (3/4)^{n-1}-(3/4)^n$$

Thus, the average time it takes an ant to get out is: $$\sum_{n=1}^{\infty}{(1 + 2n)*((3/4)^{n-1}-(3/4)^n)}$$

Cuyo valor final resulta ser 9, que será claramente inferior a la media de tiempo para el 2-dimensional del problema.

También sería interesante considerar la posibilidad de una mosca en una esfera con similares restricciones :)

Answer 4

Desarrollo de código utilizando el método de Monte Carlo como muestro a continuación. He usado Java porque eso es lo que tenía disponible, pero podría ser traducido a otro código o Matlab:

import java.util.Random;
import static java.lang.Math.* ;

public class RandomWalk {
static int N = 100000 ; // Number of iterations
static double R = 3.0 ; // Radius of circle
static int L = 200 ;

public static void main(String[] args) {
    int countArr[] = new int[L] ;
    for (int ci : countArr) countArr[ci]=0 ;
    Random rGen = new Random();   
    rGen.setSeed(856) ;

    for (int i=0 ; i<N ; i++)
    {
        int c = 0 ; // Count number of legs
        double d=0 ; // distance from center ;
        double xt=0.0, yt=0.0 ; // Total x,y distance from 0

        while (d <= R)
        {
            double ang = 2*PI*rGen.nextDouble() ;
            xt += cos(ang) ;
            yt += sin(ang) ;
            d = sqrt(xt*xt + yt*yt) ;
            c++ ;
        }
        countArr[c]++ ;
    }
    for (int i=0 ; i<L ; i++)
        System.out.println(i + ", " + countArr[i]/(double)N) ;
 }
}

El PDF de la hormiga dejando el círculo en $i$ de la pierna se ve así:

Nota que la trama tiene modos $i=4$ y $i=6$. El valor esperado es 11,4.

Answer 5

Creo que una manera de solucionar esto sería considerar la dirección en la que la hormiga termina dejando. Ahora veamos esto como un problema unidimensional, es decir, cuando es: %#% $de #% donde$$\sum_n{cos(\theta_n)}>3$ se distribuye uniformemente.