I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the average minimum time it takes to visit all vertices?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ I hope you don't mind, I fixed the tags and added the question in the title. $\endgroup$– Gjergji ZaimiCommented Mar 22, 2011 at 23:03
-
8$\begingroup$ Exercise 11.3 in Levin, Peres and Wilmer (books.google.com/books?id=6Cg5Nq5sSv4C) is to show that the cover time of the m-dimensional hypercube is asymptotically $m2^m \log 2$. $\endgroup$– Steve HuntsmanCommented Mar 23, 2011 at 0:10
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
An additional reference:
Chapter 12 in Problems and Snapshots from the World of Probability by Blom, Holst, and Sandell is devoted to an elementary exposition of such cover problems.
A related problem:
The solution to Problem 6556 in the American Mathematical Monthly (Vol. 96, No. 9, Nov. 1989, pages 847-849) looks at the average number of steps for a random walk to visit all the edges on the cube in dimensions $d=2$, $3$, and $4$.
For $d=2$ the answer is easily computed to be 10.
For $d=3$ a system with 387 equations in 387 unknowns is solved to give an answer of about 48.5.
For $d=4$ the problem is declared hopeless.
$\begingroup$
$\endgroup$
6
Up to symmetry, there are very few ordered pairs (connected set of visited vertices, position of ant). We give each one a variable corresponding to the expected time from this ordered pair to the final state:
$A = B+1$
$B = (B + 2C_{1,1})/3 + 1$
$C_{1,1} = (C_{1,2} + D_1 + D_{2,1})/3 + 1, C_{1,2} = (2C_{1,1} + D_{3,1})/3 + 1$
$D_1 = (2D_1 + E_{1,1})/3 + 1$
$D_{2,1} = (D_{2,2} + E_{1,3} + E_{2,1})/3 + 1, D_{2,2} = (D_{2,1} + D_{2,2} + E_{1,3})/3 + 1$
$D_{3,1} = (D_{3,2} + 2E_{1,4})/3 + 1, D_{3,2} = D_{3,1} + 1$
$E_{1,1} = (E_{1,2} + 2F_{1,1})/3 + 1, E_{1,2} = (E_{1,1} + 2E_{1,3})/3 + 1$, $E_{1,3} = (E_{1,2} + E_{1,4} + F_{1,1})/3 + 1, E_{1,4} = (2E_{1,3} + F_{2,1})/3 + 1$
$E_{2,1} = (E_{2,2} + F_{1,2} + F_3)/3 + 1, E_{2,2} = (E_{2,1} + E_{2,3} + F_{2,3})/3 + 1, E_{2,3} = (2E_{2,2} + F_{1,2})/3 + 1$
$F_{1,1} = (F_{1,1} + F_{1,2} + G_{1,1})/3 + 1, F_{1,2} = (2F_{1,1} + F_{1,2})/3 + 1$
$F_{2,1} = (F_{2,2} + 2G_{1,2})/3 + 1, F_{2,2} = (F_{2,1} + 2F_{2,3})/3 + 1, F_{2,3} = (2F_{2,2} + G_{1,2})/3 + 1$
$F_3 = (2F_3 + G_{1,3})/3 + 1$
$G_{1,1} = (H + 2G_{1,2})/3 + 1, G_{1,2} = (2G_{1,1} + G_{1,3})/3 + 1, G_{1,3} = G_{1,2} + 1$
$H = 0$
Now we solve for $A$:
$H = 0$
$G_{1,1} = 7, G_{2,1} = 9, G_{1,3} = 10$
$F_{1,1} = 23/2, F_{1,2} = 13$
$F_{2,1} = 23/2, F_{2,2} = 27/2, F_{2,3} = 13$
$F_3 = 13$
$E_{1,1} = 527/38, E_{1,2} = 593/38, E_{1,3} = 569/38, E_{1,4} = 563/38$
$E_{2,1} = 89/6, E_{2,2} = 31/2, E_{2,3} = 47/3$
$D_1 = 641/38$
$D_{2,1} = 9529/570, D_{2,2} = 9887/570$
$D_{3,1} = 639/38, D_{3,2} = 677/38$
$C_{1,1} = 3517/190, C_{1,2} = 10799/570$
$B = 1901/95$
$A = 1996/95 \approx 21.010526316$
Corollary: I have too much spare time.
-
-
1$\begingroup$ Yup. Also, I'm not 100% certain that there are no calculation errors, since I did this by hand... $\endgroup$– zebCommented Mar 23, 2011 at 1:56
-
$\begingroup$ @zeb: if that's not a joke, all I can say is damn, you're good! $\endgroup$ Commented Mar 23, 2011 at 2:25
-
1$\begingroup$ The following MATLAB code for an M-file (reproduced from another comment) gives approximately 21 for n large ... function y=moq59244(n); c = zeros(1,n); for k = 1:n; x = [0,0,0]; t = 0; v = [1,0,0,0,0,0,0,0]; while sum(v) < 8; t = t+1; r = ceil(3*rand); x(r) = 1-x(r); ind = 4*x(1)+2*x(2)+x(3)+1; v(ind) = 1; end; c(k) = t; end; y = mean(c); $\endgroup$ Commented Mar 23, 2011 at 3:13
-
2$\begingroup$ $A$ is the expected time from the starting position to having covered the whole cube. $B$ is the expected time to having covered the cube after having moved one step. $C_{1,1}$ is the expected time to covering the cube if you have visited three vertices and are not currently at the middle vertex of those three vertices, while $C_{1,2}$ is the expected time if you have visited three vertices and are between the other two vertices you visited. The rest of the notation is left as an exercise to the reader... $\endgroup$– zebCommented Mar 27, 2011 at 5:13
$\begingroup$
$\endgroup$
5
More generally, you could ask this for any irreducible Markov chain and any starting state. For each nonempty set S of vertices not containing the starting state $s_0$, let $T_S$ be the time (in steps) it takes to reach S (i.e. if $X_t$ is the state after $t$ steps, the least $t$ such that $X_t \in S$). Then the expected time to visit all states is $\sum_S (-1)^{|S|-1} E[T_S]$. Each $E[T_S]$ is straightforward to calculate: if $P$ is the transition matrix, $P_{S^c}$ the submatrix for rows and columns not in $S$, and $I_{S^c}$ the corresponding submatrix of the identity matrix, $E[T_S] = \sum_{j \in S^c} ((I_{S^c} - P_{S^c})^{-1})_{s_0,j}$. For your problem I get a final answer of 1996/95 = 21.01052632.
answered Mar 23, 2011 at 0:23
-
$\begingroup$ While I haven't tried to understand your argument, my attempt to simulate the 3-cube in MATLAB give an estimate of about 21. This estimate agrees reasonably well with the asymptotic formula in my comment above, which gives roughly 17. MATLAB code follows ... function y=moq59244(n); c = zeros(1,n); for k = 1:n; x = [0,0,0]; t = 0; v = [1,0,0,0,0,0,0,0]; while sum(v) < 8; t = t+1; r = ceil(3*rand); x(r) = 1-x(r); ind = 4*x(1)+2*x(2)+x(3)+1; v(ind) = 1; end; c(k) = t; end; y = mean(c); $\endgroup$ Commented Mar 23, 2011 at 0:51
-
2$\begingroup$ Oops, I seem to have left out the $(-1)^{|S|-1}$ from my computation. That answer should be 1996/95 = 21.01052632. $\endgroup$ Commented Mar 23, 2011 at 3:28
-
$\begingroup$ Can you give a reference or details for these formulae? $\endgroup$ Commented Mar 23, 2011 at 4:09
-
2$\begingroup$ Let $A_S(t)$ be the event that set $S$ has not been visited by time $t$. The inclusion-exclusion formula says for a finite set $J$, ${\bf Pr}\bigcup_{j \in J} A_{\{j\}}(t) = \sum_S (-1)^{|S|-1} {\bf Pr}\{A_S(t)\}$, the sum being over all nonempty subsets of $J$ (note that $A_S(t) = \bigcap_{j \in S} A_{\{j\}}(t)$). Now the time until set $S$ is visited is $T_S = \sum_{t = 0}^\infty I(A_S(t))$ (where $I(E)$ is the indicator function of event $E$), and similarly the time until all states in $J$ have been visited is $V_J = \sum_{t=0}^\infty I(\bigcap_{j \in S} A_{\j\}(t))$. $\endgroup$ Commented Mar 23, 2011 at 18:34
-
$\begingroup$ Sorry, that should be $V_J = \sum_{t=0}^\infty I(\bigcap_{j \in S} A_{\{j\}}(t))$. Thus we get $E[V_J] = \sum_S (-1)^{|S|-1} E[T_S]$. The formula $E[T_S] = \sum_{j \in S^c} ((I_{S^c} - P_{S^c})^{-1} )_{s_0,j}$ is standard "first-step analysis". If you wish you can think of it as the time to absorption in a Markov chain where the states in S have been made absorbing. $\endgroup$ Commented Mar 23, 2011 at 18:57
$\begingroup$
$\endgroup$
Yet another reference: Some sample path properties of a random walk on the cube, by Peter Matthews (1989). This covers the asymptotic distribution of the time $T$ taken to visit all vertices, the distribution of the number of vertices not visited at times near to $\mathbb{E}[T]$, and the expected time taken for the walk to come within a distance $d$ of all vertices.
