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.
Find the average time until the moment when they all gather at one vertex.
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)
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 

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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Sort by:
Top NewestHere'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 MonteCarlo 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.
Log in to reply
Beautiful. As simple as that. The same result give Absorbing Markov chain.
Log in to reply
Markov chain with absorbing states
Here Python code for calculation probabilities.
Log in to reply
Let us take the @Chris Lewis ideas further. There are effectively five states:
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}{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 $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 twostate 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_{j1})$, 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}{(81t)(9t) (1t) (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}$
Log in to reply
Thanks for attention. It is new approach for me  generating functions. Very interesting.
Log in to reply
Isn't the answer to the second question $t = 0$, since the frogs are already at different vertices to start off?
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?
Log in to reply
Good point.
Log in to reply