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
3 weeks, 1 day ago

No vote yet
1 vote

  Easy Math Editor

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.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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

[example link](https://brilliant.org)example link
> 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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

Let the vertices of the tetrahedron be labelled P0,P1,P2,P3P_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)(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 TT, 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)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)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)(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 34=813^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)(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)(3,1,0,0), it's possible to reach the state (1,1,1,1)(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)(2,1,1,0) in 4242 ways; (2,2,0,0)(2,2,0,0) in 1212 ways; (3,1,0,0)(3,1,0,0) in 1919 ways and (4,0,0,0)(4,0,0,0) in 22 ways. Putting all this together, we get T(3,1,0,0)=1+181(6T(1,1,1,1)+42T(2,1,1,0)+12T(2,2,0,0)+19T(3,1,0,0))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 8181 for neatness), we get 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)\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)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)=467170T(1,1,1,1)=\boxed{\frac{4671}{70}}

This comes out at around 66.766.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.

Chris Lewis - 3 weeks, 1 day ago

Log in to reply

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

Yuriy Kazakov - 3 weeks, 1 day ago

Log in to reply

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

Yuriy Kazakov - 3 weeks, 1 day ago

Log in to reply

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  =  181(3241836021912426216114481141147801212489) 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  =  118(1912426161144814114781212489) Q \; = \; \frac{1}{18}\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 PP.

Question 1 If EjE_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 (E2E3E4E5)  =  (1111)+Q(E2E3E4E5) \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 (E2E3E4E5)  =  (I4Q)1(1111)  =  (9099140227735184728467170) \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 E5=467170E_5 = \boxed{\frac{4671}{70}}

Question 2 The Markov chain has an invariant distribution π\mathbf{\pi}, such that πP=π \mathbf{\pi}P =\mathbf{\pi} and the coefficients in π\mathbf{\pi} add to 11. We calculate that π  =  (164    316    964    916    332) \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 πj1\pi_j^{-1}. We want π51=323\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 (011323) \left(\begin{array}{cc} 0 & 1 \\ \frac13 & \frac23 \end{array}\right) If pjp_j is the probability that a frog is at its Home vertex after jj jumps, then pj=13(1pj1)p_j = \tfrac13(1 - p_{j-1}), and hence pj  =  14(1+3(13)j)j0 p_j \; = \; \tfrac14\left(1 + 3(-\tfrac13)^j\right) \hspace{2cm} j \ge 0 Thus pj4p_j^4 is the probability that all four frogs are at their Home vertices after jj jumps, and we can calculate the generating function P(t)  =  j=0pj4tj  =  5904944469t15741t2+1425t3+16t4(81t)(9t)(1t)(3+t)(27+t) 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 fjf_j is the probability that the four frogs are back at their Home vertices for the first time after jj steps, and if F(t)  =  j=0fjtj F(t) \; = \; \sum_{j=0}^\infty f_jt^j is the generating function of the fjf_j, standard Markov chain theory tells us that P(t)  =  1+F(t)P(t) P(t) \; = \; 1 + F(t)P(t) and hence F(t)  =  11P(t) F(t) \; = \; 1 - \frac{1}{P(t)} Thus F(t)  =  P(t)P(t)2 F'(t) \; =\; \frac{P'(t)}{P(t)^2} While P(t)P(t) has a singularity at t=1t=1, F(t)F'(t) does not, and the expected first return time for all four frogs to be back on their Home vertices is F(1)  =  limt1P(t)P(t)2  =  256 F'(1) \; = \; \lim_{t \to 1} \frac{P'(t)}{P(t)^2} \; = \; \boxed{256}

Mark Hennings - 3 weeks, 1 day ago

Log in to reply

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

Yuriy Kazakov - 3 weeks, 1 day ago

Log in to reply

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

Elijah L - 2 weeks, 3 days ago

Log in to reply

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?

Mark Hennings - 2 weeks, 3 days ago

Log in to reply

Good point.

Elijah L - 2 weeks, 3 days ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...