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:
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:
3) and, for large values of $n$, by the following simulation program that has also produced the graphical representation given upwards:
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.