Welcome to MathOverflow

Question

10

6

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?

edited May 11 2011 at 18:52

asked Mar 22 2011 at 22:39

Bob
109●11

1

I hope you don't mind, I fixed the tags and added the question in the title. – Gjergji Zaimi Mar 22 2011 at 23:03

8

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$. – Steve Huntsman Mar 23 2011 at 0:10

Byron Schmuland · Accepted Answer · 2011-03-23 15:22:27Z UTC

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.

Steve Huntsman · Answer 2 · 2011-03-23 15:14:27Z UTC

12

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.

edited Mar 23 2011 at 15:14

Steve Huntsman

answered Mar 23 2011 at 0:23

Robert Israel
10.8k●8●22

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); – Steve Huntsman Mar 23 2011 at 0:51

2

Oops, I seem to have left out the $(-1)^{|S|-1}$ from my computation. That answer should be 1996/95 = 21.01052632. – Robert Israel Mar 23 2011 at 3:28

Can you give a reference or details for these formulae? – Steve Huntsman Mar 23 2011 at 4:09

2

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))$. – Robert Israel Mar 23 2011 at 18:34

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. – Robert Israel Mar 23 2011 at 18:57

zeb · Answer 3 · 2011-03-23 01:38:10Z UTC

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.

Stephen Connor · Answer 4 · 2011-05-11 08:37:32Z UTC

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.

john · Answer 5 · 2013-01-27 01:10:31Z UTC

0

Can you share your matlab (mathematica, or what you were using) code, for calculation of the expected value using your great formula? I have problems writing the code.

answered Jan 27 at 1:10

john
1

john · Answer 6 · 2013-01-27 12:55:21Z UTC

Hello, I have managed to programe a code for your formula. But is this even computable for chains, with more states. Already 30 states, are a problem, if we wish to calculate the expected time to visit al states, starting at state 1.

What is the cover time of a random walk on a cube?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

6 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.