This could go on forever

Probability Level 5

Suppose we have a circle, centered at the origin, with a circumference of 12 units. Both of the $x$ -intercepts serve as the starting point for a particle, each of which, each second, moves (independently) a distance of one unit either clockwise or counterclockwise around the circle with equal probability.

What is the expected number of seconds to elapse until the two particles simultaneously occupy the same point on the circle for the first time?

Clarifications:

The particles move at the end of each second.
To reiterate, the particles move independently of one another.

The answer is 18.

3 solutions

Daniel Ploch
Aug 11, 2014

Let $E(x)$ be the expected number of seconds to pass until a collision, when the particles are $x$ units apart presently. Note that $x \leq 6$ at all times, for a circle of circumference $12$ .

$E(6) = 1 + \frac{1}{2} E(6) + \frac {1}{2} E(4)$

$E(4) = 1 + \frac{1}{2} E(4) + \frac{1}{4} E(6) + \frac{1}{4} E(2)$

$E(2) = 1 + \frac{1}{2} E(2) + \frac{1}{4} E(4) + \frac{1}{4} E(0)$

$E(0) = 0$

Simple algebra yields $E(2) = 10$ , $E(4) = 16$ , and $E(6) = 18$ , for an answer of $\boxed {18}$ .

More generally, for a circle of circumference $4n$ , it takes an average of $2n^2$ seconds for the first collision to occur. Here's the proof:

We postulate $E(2k) = 2(n^2 - (n-k)^2)$ for all k, given a circle of circumference $4n$ . We check the cases of $k = 0$ , $0 < k < n$ , and $k = n$ separately.

$E(0) = 2(n^2 - (n-0)^2) = 2(n^2 - n^2) = 0$

$E(2k, 0 < k < n) = 1 + \frac{1}{2} E(2k) + \frac{1}{4} E(2(k+1)) + \frac{1}{4} E(2(k-1))$

$= 1 + \frac{1}{2} 2\left( n^2 - (n-k)^2 \right) + \frac{1}{4} 2\left( n^2 - (n-(k+1))^2 \right) + \frac{1}{4} 2\left( n^2 - (n-(k-1))^2 \right)$

$= 1 + n^2 - n^2 + 2kn - k^2 + \frac{1}{2} \left( n^2 - n^2 + 2kn + 2n - k^2 - 2k - 1 + n^2 - n^2 + 2kn - 2n - k^2 + 2k - 1 \right)$

$2E(2k, 0 < k < n) = 2 + 2n^2 - 2n^2 + 4kn - 2k^2 + n^2 - n^2 + 2kn + 2n - k^2 - 2k - 1 + n^2 - n^2 + 2kn - 2n - k^2 + 2k - 1$

$2E(2k, 0 < k < n) = 8kn - 4k^2$

$E(2k, 0 < k < n) = 2(2kn - k^2)$

$= 2k(2n-k) = 2(n - (n-k))(n + (n-k))$

$= 2(n^2 - (n-k)^2)$

$E(2n) = 1 + \frac{1}{2} E(2n) + \frac{1}{2} E(2(n-1))$

$E(2n) = 1 + (n^2 - (n-n)^2) + (n^2 - (n-(n-1))^2) = 1 + n^2 - 0^2 + n^2 - 1^2 = 2n^2$

Q.E.D.

It would be nice if there were a simpler, more elegant way to prove this, though. Probably something involving random walk theory.

Excellent solution, Daniel. Thanks for taking the time to do this and for going the extra mile with the analysis of the general case.

As for a "more elegant" proof, I do have one thought. For one particle, treating it as a one-dimensional simple random walk, starting at the origin, the expected number of steps before hitting either a or -b, (where a and b are positive integers), is just ab. In this case, to reach the other x-intercept, we would have a = b = 6, giving an expected value of 36. However, since we have the two independent particles on the move, and since the circumference is a multiple of 4, it seems intuitive to divide the 36 by 2 to get an expected value of 18 seconds before the first encounter occurs. I'll have to review my random walk theory to see if this is reasonable, but I just thought I'd mention it in case you have any further insights. Thanks again. :)

Brian Charlesworth - 6 years, 10 months ago

Yes, the expected time to n or -n being n^2 certainly seems to be a step in the right direction. However, given the two particles, and the fact that the walking space is finite and modular, as opposed to the infinite number line, I have qualms about getting the results correctly and rigorously from it :(

Can't be too far though. Keep posting excellent problems!

Daniel Ploch - 6 years, 10 months ago

I solved the problem using a monte-carlo approach! Here is the code I wrote in matlab to solve

count=zeros(100000,1); for i=1:100000 x=1; y=7; while(x~=y) a=floor(10*rand(1,1)); if(rem(a,2)==0) x=x+1;

         else
             x=x-1;
         end


       b=floor(10*rand(1,1));
         if(rem(b,2)==0)
             y=y+1;
         else
             y=y-1;
         end

         if(x==13)
             x=1;
         end

         if(x==0)
             x=12;
         end

         if(y==13)
             y=1;
         end


         if(y==0)
             y=12;
         end

         count(i)=count(i)+1;


     end
    end

the solution gave a mean of 17.9625 ~ 18 !!

Nice problem!

Aaditya Rcs - 6 years, 10 months ago

Thanks for running the program, Aaditya. It's always good to have some computational confirmation. :)

Brian Charlesworth - 6 years, 10 months ago

Agnishom Chattopadhyay
Sep 5, 2014

Mathematica Code:

Table[Block[{a = 3, b = 9, n = 0}, 
    While[a != b, 
     a = RandomChoice[{Mod[(a + 1), 12], Mod[(a - 1), 12]}];
     b = RandomChoice[{Mod[(b + 1), 12], Mod[(b - 1), 12]}];
     n = n + 1];
    n], {10000}] // Mean // N

Matt McNabb
May 12, 2015

We can use Markov Chain theory to solve this too. Letting the possible states be $x=6$ , $x=4$ , $x=2$ , $x=0$ then the transition matrix $P$ is:

$P = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \\ 0.25 & 0.5 & 0.25 & 0 \\ 0 & 0.25 & 0.5 & 0.25 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$

Let $Q$ be the non-absorbing part of it. Then Markov chain theory tells us that the sum of each row of the matrix $(I - Q)^{-1}$ gives the expected time to absorption of the state corresponding to that row. We have:

$I - Q = \begin{pmatrix} 0.5 & -0.5 & 0 \\ -0.25 & 0.5 & -0.25 \\ 0 & -0.25 & 0.5 \\ \end{pmatrix}$

I used an online calculator to invert this, although Gauss-Jordan elimination would be straightforward too:

$(I - Q)^{-1} = \begin{pmatrix} 6 & 8 & 4 \\ 4 & 8 & 4 \\ 2 & 4 & 4\\ \end{pmatrix}$

Reading off the sums of the rows, we get $E(6) = \boxed{18}$ , $E(4) = 16$ , $E(2) = 10$ .

This could go on forever

The answer is 18.

3 solutions

0 pending reports