Mean distance between alternatively jumping frogs

Question

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.

Answer 1

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}$$

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:

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.

Answer 2

This is not an answer, just a brute force method to solve for the simplest case.

Consider the possible position being $\{1, 2, 3, 4\}$ only. If we model the pair of positions of the frong like $(X, Y)$, then it is a markov chain. The possible positions of the two frogs is $\displaystyle \binom {4} {2} = 6$ and multiply by $2$ (for the cases whether it is the turn for the left frog or right frog to jump), the total number of states is $12$ in this case. Thus in general for the case with $a, b$ being the end point is $\displaystyle \binom {|a-b|+1} {2} \times 2 = |a-b|(|a-b|+1)$.

The transition matrix in this case is $$ P = \begin{matrix} (1,2,l) \\ (1,3,l) \\ (1,4,l) \\ (2,3,l) \\ (2,4,l) \\ (3,4,l) \\ (1,2,r) \\ (1,3,r) \\ (1,4,r) \\ (2,3,r) \\ (2,4,r) \\ (3,4,r) \end{matrix} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/2 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix}$$ where $l, r$ indicate it is the turn for left or right frog to jump.

Starting at the state $k$, the expected number of visits to state $m$ in $n$ steps (not counting the initial state) is $$ v_{km}^{(n)} = \sum_{q=1}^{n} p_{km}^{(q)}$$ where $p_{km}^{(q)}$ is the $(k, m)$ entries of $P^q$.

The distance between the two frogs, corresponding to the above $12$ states, are $$ D = (1, 2, 3, 1, 2, 1, 1, 2, 3, 1, 2, 1)$$ and thus the mean difference is $$ \frac {1} {n} \sum_{m=1}^{12} d_mv_{km}^{(n)}$$

So within finite time $n$, this value is affected by the initial state $k$. In long-term, the steady state distribution is just simply $1/12$ for all the states, and taking expectation we have the long run distance being $5/3$.