16
$\begingroup$

An ant is sitting in the middle of a circle of radius 3 meters. Every minute, the ant picks a random direction and moves straight 1 meter.

On average, how long does it take the ant to leave the circle? If it helps calculations, you can disregard the fact that the ant may technically leave prior to the end of the minute, in other words, if the ant is 0.5 meters from the edge of the circle and walks outwards, consider it a minute, not 30 seconds.

I'm normally quite good at these types of problems, but this one seems more statistical in nature and I'm not sure how to approach it. Obviously the ant could stay in the circle forever wandering around, but it's statistically impossible, meaning the average amount of time the ant spends in the circle is a limit which converges (answer is not "infinite time").

I'd love to hear any techniques on solving this problem.

  • 0
    http://en.wikipedia.org/wiki/Brownian_motion take a look at Smoluchowski model2012-04-19
  • 1
    Have you considered Monte Carlo simulation? I think that this problem would be ideally suited to such analysis.2012-04-19
  • 0
    @Norbert, interesting link. Thank you for sharing.2012-04-19
  • 0
    @Tpofofn, I'm not familiar with it. What does a Monte Carlo simulation do?2012-04-19
  • 0
    @Neil, a Monte Carlo Simulation is a brute force approach in which you simulate the ant some large 'N' number of time and count up the number of legs it takes him to leave the circle each time. See this link: http://en.wikipedia.org/wiki/Monte_Carlo_method2012-04-19
  • 0
    Not an answer, but I made a GeoGebra simulation that could help students visualize what's going on, or collect a limited amount of data. [http://www.geogebratube.org/material/show/id/8479](http://www.geogebratube.org/material/show/id/8479)2012-04-25

5 Answers 5

11

Calling $\mathbb{E}(d)$ the expected time for leaving the circle if you are at distance $d$, $\mathbb{E}(d)$ should have the following property: $$\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$.

This formula say that the expected leaving time is 1 (the cost of doing another step) + the mean of the expected time over each point at distance 1 from the current point ($\sqrt{d^2+1-2d\cos\alpha}$ is the cosine law applied at the triangle between the origin, the current point and next point).

I don't know how to explicit solve this equation (nor if is feasible to be done), but it can be used for iteratively approximate the solution.

edit: I've tried to solve with R, seem that the solution is $\mathbb{E}(0)\simeq11.42$, and this is the plot of the approximation of the function: enter image description here

  • 0
    Very nice work! Your $\alpha$ is my $\gamma$, and I give geometric formulas to solve the integral if you care to look at my post and cannibalize it for yours.2012-04-19
2

The ant's position at each time $n\in\mathbb{N}$ is a random variable which we could model in the complex plane as $Z_0=0$, $Z_n=Z_{n-1}+\Delta Z_n=\sum_{k-1}^n\Delta Z_k$ for moves $\Delta Z_n=e^{i\Theta_n}$ which are i.i.d. and which depend on uniform i.i.d. random variates $\Theta_n=2\pi\,U_n\sim\operatorname{Unif}\left(0,2\pi\right)$ . If we also let $$ R_n=|Z_n|\,, \qquad S_n=\sup\limits_{1\le k\le n}R_n \qquad \text{and} \qquad T=\inf\left\{n\mid R_n>R\right\} $$ be the first time $n$ for which $R_n>R=3$, then we are asking for $\mathbb{E}[T]$, which can be calculated as $$ \mathbb{E}[T]=\sum_{n=R}^{\infty}n\cdot\mathbb{P}[R_{n-1} < R < R_n]\,. $$ Now if we let $F_n(r)=\mathbb{P}[R_n < r]$ and let $f_n(r)=\mathbb{P}[R_n = r]$ be the PDF and CDF of $R_n$, we can see that $F_n(n)=1$, and we may be able to determine these functions inductively, with a recursion: $$ \eqalign{ F_n(r)&= \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_{r-1}^{r+1} f_{n-1}(s)\cdot \mathbb{P}[R_n<r|R_{n-1}=s] \,ds } $$ The latter integral can certainly be split into the two cases $s<r$ and $s>r$, for which the indeterminate probability inside the integrand can be evaluated using geometry by subtracting the area of sectors of circles (and triangles for $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. } $$ where the angles $\alpha,\beta,\gamma$ can be expressed using the law of cosines: $$ \eqalign{ \cos\alpha &=\frac{r^2+s^2-1}{2rs}\\ \cos\beta &=\frac{r^2-s^2-1}{2 s} \qquad\text{or}\qquad\sin\beta=r\,\sin\alpha\\ \cos\gamma &=\frac{-r^2+s^2+1}{2 s}=-\cos\beta\\ } $$ (or solved from the equations $re^{i\alpha}=s+e^{i\beta}$ & $\beta+\gamma=\pi$, from which one can infer the diagrams for each case) and $A_\alpha=2\alpha-\sin2\alpha$ is twice the area of $\{z\in\mathbb{C}:\,|z|>r,\,|z-s|<1\}$.

Well, that's a start. There is surely a more elegant recursion; perhaps @carlop has found it.

  • 0
    I'm having a hard time wrapping my head around that. What is E[T]? Time it takes for the ant to leave a circle of radius T?2012-04-19
  • 0
    $\mathbb{E}[T]$ is the [expected value](http://en.wikipedia.org/wiki/Expected_value) of the time of first passage outside the circle of radius $R$.2012-04-19
2

Just for fun and simplicity, here's the results if the ant were constrained to 1 dimension (can only move left or right). Also note that I considered the ant out when he reaches 3 from the center:

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 

Chance of being at 2E after (1 + 2*n) moves: $$(3/4)^n$$ Chance of being out at (1 + 2*n) moves: $$1 - (3/4)^n$$ Chance of an ant getting out on the (1 + 2*n)th move: $$(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)}$$

Whose final value turns out to be 9, which will clearly be lower than the average time for the 2-dimensional problem.

It would also be interesting to consider a fly in a sphere with similar constraints :)

2

I developed code using Monte Carlo Method as show below. I used Java because that is what I had available, but it could be translated to Matlab or other code:

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

The PDF of the ant leaving the circle on leg $i$ looks like this:

PDF of ant leaving the circle on leg i

Note that the plot has modes at $i=4$ and $i=6$. The expected value is 11.4.

1

I think one way to solve this would be to consider the direction in which the ant ends up leaving. We can now look at this as a one-dimensional problem, namely, when is: $$\sum_n{cos(\theta_n)}>3$$ Where $\theta$ is distributed uniformly.

  • 0
    Hmm, I think that's an accurate representation of the problem, but how can you determine when the absolute value of the sum of a random number between -1 and 1 will exceed 3?2012-04-19
  • 0
    The sum of a set of identical random variables is just the convolution. So you could calculate the chances for each $n$ and then sum over that.2012-04-19
  • 0
    so what would that be? $\sum_n{sin(\pi) - sin(0)}$? That's 0, so the $\sum_n{0}$ is never going to be 3 or greater. Maybe I don't yet see it.2012-04-19
  • 0
    No. you would first need to write the the distribution given by $\cos(\theta)$, say $f(x), x \in [-1,1]$. Once you have that you can calculate the convolution of this distribution $n$ times to obtain a series of distributions $f_n$. Finally, your answer is: $$\sum{nP(f_n>3)}$$2012-04-19
  • 0
    Doesn't that give you the time to leave an infinite strip of width 6?2012-04-19
  • 2
    Or rather, a semi-infinite plane bounded by the line $x=3$.2012-04-19
  • 0
    Perhaps I need to multiply the result by $2\pi$, since for each the probability of leaving the circle is the the integral over all probabilities of leaving the "line".2012-04-19
  • 0
    @TonyK, those were my thoughts as well. An "average" move would take you farther away from the center point, even if by a little bit (consider the ant turning 90 degrees with respect to center point and moving.. ant moves farther away).2012-04-19
  • 0
    I think this approach is a dead end.2012-04-19