[Math] Mean distance between alternatively jumping frogs

markov chainsprobabilistic-methodprobability theoryrandom walk

Consider a bounded line in $\mathbb Z$, with the indices $a$ and $b$ as its end-points (with $|a-b| \geq 3$). We place two frogs on the line, starting at $i$ and $j$. At each time step $n$ (discrete) the frogs must alternatively (one jump per time step) make a random jump to one of their neighbours (so either +1 or -1 with equal probability, unless one neighbour is an end-point or the other frog, in which case the frog jumps to its only neighbour with probability one [1]). The only rule is: the frogs can never occupy the same position at the same time. So intuitively this implies that either frog at any given time is only able to explore a small span of the whole line, namely, from one end-point upto the position of the other frog.

[1]: small caveat, it can happen that the frog to jump has no empty neighbour, e.g. when next to an end-point with the other frog blocking its other side), in this case only the other frog can make a jump

Is it possible to determine the mean distance between the two frogs as a function of number of steps and size of the line? Can we establish whether that distance converges towards a stationary value? I'm mainly interested in learning about the methodology to tackle such probability theory questions. So any hints or sources (of similar problems) are welcome.

Best Answer

Let $L,R$ be resp. the Left and Right frog.

Let $n$ be the number of possible positions (for example $n=20$ in the picture at the bottom of this text).

Let $D_n$ be the random variable "distance between frogs". We have:

$$\tag{1}E(D_n)=\dfrac{n+1}{3}$$

enter image description here

Let us prove (1) by induction on the number $n$ of positions.

It is true for $n=4$ (see "Addendum 1" at the bottom of this text).

Let us assume (1) to be true at step $n$.

Let us prove that $E(D_{n+1})=\dfrac{n+1+1}{3}$, i.e., $E(D_{n+1})=E(D_{n})+\dfrac{1}{3}.$

To each configuration at step $n$ (that one can consider as a binary number with $n$ digits, two of them being "ones", $n-2$ being zero : vacant positions), one can associate 3 configurations at step $n+1$, by inserting a new position (a new zero):

  • either in region 1 defined to be on the left of L, or

  • in region 2, between L and R, or,

  • in region 3, i.e., on the right of R.

The mean width of region 2 is $(n+1)/3$ by the recursion assumption.

The two other regions, by an elementary consideration of symmetry, have the same mean width ; thus the mean width of each region is $(n+1)/3$. In other words, each region has an equal probability of being chosen for the insertion of a new place.

But it is only by inserting in region 2 that the mean distance increases by $1$. Insertion in the two others does not lead to an increase in the mean distance between L and R frogs.

Thus the mean distance increases by steps of $1/3$, proving (1).

Addendum:

1) The case $n=4$ is easily treated by enumeration. There are 6 possible pairs of position :

$$\begin{cases} 1 & 2 & \to & D_4=1\\ 1 & 3 & \to & D_4=2\\ 1 & 4 & \to & D_4=3\\ 2 & 3 & \to & D_4=1\\ 2 & 4 & \to & D_4=2\\ 3 & 4 & \to & D_4=1 \end{cases}$$

giving $E(D_4)=\tfrac{5}{3}.$

The important thing is that all these positions have the same stationary probability. For being convinced of that consider the diagram:

enter image description here

and the associated matrix:

$$\begin{matrix} (a) \\ (b) \\ (c) \\ (d) \\ (e) \\ (f) \end{matrix} \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ a & 0 & a & 0 & 0 & 0 \\ 0 & a & 0 & 0 & 0 & a \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \ \ \text{with} \ \ a=1/2.$$

This matrix has a unique eigenvalue $\lambda$ with $|\lambda|=1$ which is precisely $\lambda=1$, all the others being such that $|lambda|<1$. One can verify that, for any $V$, $lim_{n \to \infty} M^nV$ is a vector with identical components, proving the equiprobability of all events in the stationary state.

2) this result has been confirmed by the following Matlab program giving an exact value of $D_n$ by an exhaustive list of elementary events:

format rat
n=6;I=1:n;
U=nchoosek(I,2)
mean(diff(U'))

3) and, for large values of $n$, by the following simulation program that has also produced the graphical representation given upwards:

function frogs
clear all;close all;hold on;grid on
n=20;%number of places
nt=10000;%number of instants
M=[];   
LR=sort(ceil(n*(rand(1,2))));
L=LR(1);R=LR(2);
T=zeros(2,nt);
for k=1:nt
   T(:,k)=[L;R];
   L1=TestL(L,R,n);
   R1=TestR(L1,R,n);
   L=L1;R=R1;
end;
a=(nt-100):nt;
plot(T(1,a),a,'r','linewidth',1,'linesmoothing','on');
plot(T(2,a),a,'b','linewidth',1,'linesmoothing','on');
diff(T)
M=[M,mean(diff(T))];
mean(M)
%________________________
function Ls=TestL(L,R,n);
   if L==1
      if R>2
         Ls=2;
      else
         Ls=1;
      end;
   else
      if L+1<R
         Ls=L+sign(rand-0.5);
      else
         Ls=L-1;
   end
end;
%________________________
function Rs=TestR(L,R,n);
 if R==n
    if L<n-1
       Rs=n-1;
    else
       Rs=n;
    end;
 else
    if L+1<R
       Rs=R+sign(rand-0.5);
    else
       Rs=R+1;
    end
 end;

Assumptions: L jumps first (if possible), then R jumps (if possible), being understood that the jump of R can be influenced by the jump L just did.

Related Question