# Frog random walk on the vertices of the tetrahedron

At the beginning, 4 frogs sit in the vertices of the tetrahedron, one at each vertex - and then every second they start randomly jumping to adjacent vertices.

1. Find the average time until the moment when they all gather at one vertex.

2. Find the average time until the moment when all the frogs are at different vertices of the tetrahedron (there are no two frogs in one vertex)

3. Find the average time until the moment when all frogs return to their starting positions.

We can use Absorbing Markov chain.

We can use Monte Carlo approach.

 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 import random import numpy as np d = dict() d[1] = [2, 3, 4] d[2] = [1, 3, 4] d[3] = [1, 4, 2] d[4] = [1, 2, 3] start= [1,2,3,4] variant=[0,0,0,0] steps = [] dp=sorted(start) step=0 for i in range(20000000): k=-1 for m in start: k=k+1 variant[k]=random.choice(d[start[k]]) step += 1 start=variant dp=sorted(start) if dp[0]==dp[3]: steps.append(step) step=0 start=[1,2,3,4] print(len(steps),np.mean(steps)) 150150 66.5988

Note by Yuriy Kazakov
8 months, 2 weeks ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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.

- 8 months, 2 weeks ago

Beautiful. As simple as that. The same result give Absorbing Markov chain.

- 8 months, 2 weeks ago

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

- 8 months, 2 weeks ago

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

- 8 months, 2 weeks ago

Thanks for attention. It is new approach for me - generating functions. Very interesting.

- 8 months, 2 weeks ago

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

- 8 months, 1 week ago

We are interested in the first nontrivial return time... In other words, how long does it take the frogs to get back to the original position of all being on different vertices, once they have left that position?

- 8 months, 1 week ago

Good point.

- 8 months, 1 week ago

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

- 6 months ago