Frog random walk on the vertices of the tetrahedron

Here's a way to find the expected time until they meet at a single vertex.

Let the vertices of the tetrahedron be labelled $P_0,P_1,P_2,P_3$. We can classify a state by the number of frogs on each vertex; for instance $(1,1,0,2)$.

The expected time until all the frogs meet only depends on the current state (this is why a Markov chain method also works). Say the expected time is $T$, a function of the current state.

Symmetry reduces the number of states we need to consider. Since $T(2,0,0,0)=T(0,2,0,0)=T(0,0,2,0)=T(0,0,0,2)$, we only need to find the value of $T(2,0,0,0)$, and so on.

So the starting states we're interested in are $(1,1,1,1),(2,1,1,0),(2,2,0,0),(3,1,0,0)$.

At any given step, each frog has three choices of where to jump; so there are a total of $3^4=81$ distinct new configurations after the jump. These can then be classified per the list of states above. Once we reach the (ordered) state $(4,0,0,0)$, they're all at the same vertex and we stop.

Working out the transitions by hand is pretty tedious, so I wrote some simple code to help. As an example, from the state $(3,1,0,0)$, it's possible to reach the state $(1,1,1,1)$ in a total of six ways (the three frogs on the same vertex jump to each of the three other vertices; the remaining frog jumps to the vertex the three started on).

Similarly, we can reach the state $(2,1,1,0)$ in $42$ ways; $(2,2,0,0)$ in $12$ ways; $(3,1,0,0)$ in $19$ ways and $(4,0,0,0)$ in $2$ ways. Putting all this together, we get $T(3,1,0,0)=1+\frac{1}{81}(6T(1,1,1,1)+42T(2,1,1,0)+12T(2,2,0,0)+19T(3,1,0,0))$

Repeating this for each starting state (and multiplying both sides by $81$ for neatness), we get $\begin{aligned} 81T(1,1,1,1)&=81+9T(1,1,1,1)+48T(2,1,1,0)+12T(2,2,0,0)+12T(3,1,0,0) \\ 81T(2,1,1,0)&=81+8T(1,1,1,1)+47T(2,1,1,0)+11T(2,2,0,0)+14T(3,1,0,0) \\ 81T(2,2,0,0)&=81+8T(1,1,1,1)+44T(2,1,1,0)+11T(2,2,0,0)+16T(3,1,0,0) \\ 81T(3,1,0,0)&=81+6T(1,1,1,1)+42T(2,1,1,0)+12T(2,2,0,0)+19T(3,1,0,0) \end{aligned}$

We're after $T(1,1,1,1)$, ie the expected time it takes for the frogs to meet after starting from one frog on each vertex. We can solve the system of equations to get $T(1,1,1,1)=\boxed{\frac{4671}{70}}$

This comes out at around $66.7$, which is much quicker than I expected. I've written a Monte-Carlo simulation too and this value seems to agree with that. As you might expect, there isn't much difference between the times for each of the starting states; intuitively this is because the frogs shuffle themselves very quickly.

Markov chain with absorbing states

Here Python code for calculation probabilities.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

a=[]

for m in [[1,1,1,1],[2,2,1,1],[1,1,1,2],[1,2,3,4]]:
  [k1,k2,k3,k4]=m
  t13=0
  t112=0
  t1111=0
  t4=0
  t22=0
  for p1 in range(1,4):
   for p2 in range(1,4):
     for p3 in range(1,4):
       for p4 in range(1,4):

         a=[0,0,0,0]

         s1=(p1+k1)%4
         s2=(p2+k2)%4
         s3=(p3+k3)%4
         s4=(p4+k4)%4

         a[s1] = a[s1]+ 1
         a[s2] = a[s2]+ 1
         a[s3] = a[s3]+ 1
         a[s4] = a[s4]+ 1
         sa=sorted(a)
         if sa==[0, 0, 1, 3]:
            t13=t13+1
         if sa==[0, 1, 1, 2]:
            t112=t112+1
         if sa==[1, 1, 1, 1]:
            t1111=t1111+1
         if sa==[0, 0, 0, 4]:
            t4=t4+1 
         if sa==[0, 0, 2, 2]:
           t22=t22+1   
  print ('start=', m,'t13=',t13,'t22=',t22,'t112=',t112,'t1111=', t1111,'t4=', t4 )

start= [1, 1, 1, 1] t13= 24 t22= 18 t112= 36 t1111= 0 t4= 3
start= [2, 2, 1, 1] t13= 16 t22= 11 t112= 44 t1111= 8 t4= 2
start= [1, 1, 1, 2] t13= 19 t22= 12 t112= 42 t1111= 6 t4= 2
start= [1, 2, 3, 4] t13= 12 t22= 12 t112= 48 t1111= 9 t4= 0

Let us take the @Chris Lewis ideas further. There are effectively five states:

• State 1 - four frogs at one vertex
• State 2 - three frogs at one vertex, one at another
• State 3 - two frogs at each of two vertices
• State 4 - two frogs at one vertex. and one frog at another two vertices
• State 5 - one frog at each vertex,

and these states are subject to the transition probability matrix $P \; = \; \frac{1}{81}\left(\begin{array}{ccccc} 3 & 24 & 18 & 36 & 0 \\ 2 & 19 & 12 & 42 & 6 \\ 2 & 16 & 11 & 44 & 8 \\ 1 & 14 & 11 & 47 & 8 \\ 0 & 12 & 12 & 48 & 9 \end{array}\right)$

Also consider the submatrix $Q \; = \; \frac{1}{81}\left(\begin{array}{cccc} 19 & 12 & 42 & 6 \\ 16 & 11 & 44 & 8 \\ 14 & 11 & 47 & 8 \\ 12 & 12 & 48 & 9 \end{array}\right)$ obtained by deleting the first row and the first column of $P$.

Question 1 If $E_j$ is the expected number of jumps to reach State 1, given that we start in State j, then standard conditional probability thinking tells us that $\left(\begin{array}{c} E_2 \\ E_3 \\ E_4 \\ E_5 \end{array}\right) \; = \; \left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array}\right) + Q\left(\begin{array}{c} E_2 \\ E_3 \\ E_4 \\ E_5 \end{array}\right)$ Solving this matrix equation gives $\left(\begin{array}{c} E_2 \\ E_3 \\ E_4 \\ E_5 \end{array}\right) \; = \; \big(I_4 - Q\big)^{-1}\left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array}\right) \; = \; \left(\begin{array}{c} \frac{9099}{140} \\[1ex]\frac{2277}{35} \\[1ex] \frac{1847}{28} \\[1ex] \frac{4671}{70} \end{array}\right)$ and the desired answer is $E_5 = \boxed{\frac{4671}{70}}$

Question 2 The Markov chain has an invariant distribution $\mathbf{\pi}$, such that $\mathbf{\pi}P =\mathbf{\pi}$ and the coefficients in $\mathbf{\pi}$ add to $1$. We calculate that $\mathbf{\pi} \; = \; \left(\tfrac{1}{64}\;\;\tfrac{3}{16}\;\;\tfrac{9}{64}\;\;\tfrac{9}{16}\;\;\tfrac{3}{32}\right)$ and standard Markov chain theory tells us that the expected return time to State j is $\pi_j^{-1}$. We want $\pi_5^{-1} = \boxed{\frac{32}{3}}$.

Question 3 Each frog can be seen as following a two-state Markov chain (Home vertex or Away vertex), with transition matrix $\left(\begin{array}{cc} 0 & 1 \\ \frac13 & \frac23 \end{array}\right)$ If $p_j$ is the probability that a frog is at its Home vertex after $j$ jumps, then $p_j = \tfrac13(1 - p_{j-1})$, and hence $p_j \; = \; \tfrac14\left(1 + 3(-\tfrac13)^j\right) \hspace{2cm} j \ge 0$ Thus $p_j^4$ is the probability that all four frogs are at their Home vertices after $j$ jumps, and we can calculate the generating function $P(t) \; = \; \sum_{j=0}^\infty p_j^4 t^j \;= \; \frac{59049 - 44469 t - 15741 t^2 + 1425 t^3 + 16 t^4}{(81-t)(9-t) (1-t) (3 + t) (27 + t)}$ If $f_j$ is the probability that the four frogs are back at their Home vertices for the first time after $j$ steps, and if $F(t) \; = \; \sum_{j=0}^\infty f_jt^j$ is the generating function of the $f_j$, standard Markov chain theory tells us that $P(t) \; = \; 1 + F(t)P(t)$ and hence $F(t) \; = \; 1 - \frac{1}{P(t)}$ Thus $F'(t) \; =\; \frac{P'(t)}{P(t)^2}$ While $P(t)$ has a singularity at $t=1$, $F'(t)$ does not, and the expected first return time for all four frogs to be back on their Home vertices is $F'(1) \; = \; \lim_{t \to 1} \frac{P'(t)}{P(t)^2} \; = \; \boxed{256}$

Isn't the answer to the second question $t = 0$, since the frogs are already at different vertices to start off?

What in min value of |z1|^2+|z2|^2+re(z1z2) given that im(z1z2)=0