*** Tell Stephen Waton when I'm finished ***
\section{Question}
Suppose you start at one vertex of a cube, and random walk along edges.
What is the expected time to get to the opposite corner?
(Assuming you stop once you arrive there.)
\section{Solution}
10 steps.
Divide the vertices into 4 classes:
\begin{itemize}
\item Starting vertex
\item Near vertices (those adjacent to the start)
\item Far vertices (those adjacent to the end)
\item End
\end{itemize}
FIXME: this really needs a picture.
Draw both as 3-D and flattened: 4 rows:
*
***
***
*
(with suitable connections; by symmetry, you just care about transition
probabilities going vertically - which exact node you're on doesn't
matter)
Your condition after the first few steps is:
After $0$ steps, you're at the starting vertex.
After $1$ step, you're at one of the near vertices
($1/3$ chance of each, but it's symmetric).
After $2$ steps, you're $1/3$ likely on the start, $2/3$ on the far vertices.
After $3$ steps, you're $\frac{2}{3}\cdot \frac{1}{3}=\frac{2}{9}$ likely to be at the end,
$1-\frac{2}{9}=\frac{1}{3}+\frac{2}{3}\cdot\frac{2}{3}=\frac{7}{9}$ likely to be on the
near vertices.
Thus after 3 steps, you're $2/9$ likely to be over, and otherwise you're back at step $1$:
after the first step, you have odds $2/9$ to end in $2$ steps, else you repeat.
Thus your expected time to reach the end is the mean lifetime of something that decays
with probability $2/9$ every $2$ units of time (plus $1$ for the first step).
The mean lifetime is reciprocal of the decay constant, so $\frac{2}{2/9} = 9$,
thus expected time to reach the opposite corner is $1+9=10$.
\section{Analysis of solution}
\emph{Why} does this have a good solution?
A key fact is that the graph is bipartite / parity
"Walk randomly and then stop" is decay.
your starting position is easily decomposed into eigenvectors
or something like that
\section{Solution techniques}
The basic solution techniques are:
\begin{itemize}
\item look at first few steps
\item recognize pattern / recurrence
\begin{itemize}
This much yields a tractible calculaction (a series or recurrence).
Less critical:
\begin{itemize}
\item see how symmetries simplify things: work on a \emph{quotient space}
\item recognize a decay equation
\end{itemize}
These make your life easier, but aren't strictly necessary.
\subsection{Symmetry / Quotient}
The fact that the near corners and far corners are individually indistinguishable
means that the ``random walk on cube'' graph simplifies to the following \emph{quotient
graph}:
* --1--> * -2/3-> * -1/3-> *
<-1/3- <-2/3-
You don't need to write this diagram -- you can work with the individual nodes,
or consider the near and far vertices as classes but not formally pass to the quotient
(as I did in this exposition) -- but it's implicit in the problem.
Similarly, the bipartite nature of the graph means that the \emph{two step}
transition probabilities break up into $2$ pieces:
* -2/9-> *
7/9 loop
* -?-> * (and 2 loops)
<-?-
(where we don't care about the other one)
This is again implicit and unspoken.
The point is that this analyses \emph{why} the problem simplifies:
\begin{itemize}
\item a rotational symmetry means that rather than $8$ vertices, there are $4$ classes
\item the bipartite graph reduces this to $2$ classes, hence simple decay
\item \dots since the starting position (and after $1$ step)
is concentrated on one vertex/class
\end{itemize}
\subsection{Decay equation}
Once you see the recurrance, you can mechanically write a series:
$$\frac{2}{9} \cdot 3 + \frac{7}{9}\frac{2}{9}\cdot 5
+ \left(\frac{7}{9}\right)^2\frac{2}{9}\cdot 7 + \dotsb $$
recognizing
$$\left(\frac{1}{(1-p)}\right)^2 = \sum kp^{k-1}$$
(say, by differentiation of the geometric series);
this is how I first solved it.
More elegantly, one can notice the recurrance:
$$E(X) = 2 + \frac{7}{9} E(X)$$
...where $X$ is ``number of steps after first one''.
The interpretation is: after the first step, you have $2$ more steps,
and $2/9$ of the time you're done, so $7/9$ of the time you do this again.
Expectation is linear, so you can sum and get the above recurrance.
This calculation is of independent interest,
and can be interpreted as mean lifetime of exponential decay:
the result is that mean lifetime if you decay with probability $p$ is $1/p$
(mean lifetime is reciprocal of decay constant, generally written $\lambda$).
I'd done this calculation a few months earlier, and was delighted by
the result, as it's elegant, and true both continuously and discretely
(and I had derived it myself).
Hence I was delighted to see this computation hidden within another problem:
it doesn't reduce to \emph{just any} calculation:
it reduces to an \emph{interesting} calculation.
\section{Context}
This was posed to me as a puzzle,
with the implication that it had a slick, elementary solution.
On a general graph, this is \emph{messy}.
(Note that if you start on a different vertex of the cube, it's still easy.)
I like this b/c the symmetry that simplifies this is not immediately
obvious: indeed, on higher dimensional cubes it also doesn't have a nice solution!
On a square, the answer is $4$, easily: you decay $1/2$ the time
every $2$ steps, yielding $\frac{2}{1/2}=4$.
\section{What's my interest?}
From a problem-solving point of view, this is a fun problem in that
you follow your nose, notice a trick (a recurrance), and reduce to a calculation.
Further, you might recognize the calculation.
I find it interesting because:
\begin{itemize}
\item It's surprising that it's (easily) solveable:
the structure that makes it tick (makes it easy to compute the solution)
is not obvious.
\item The solution breaks up nicely into steps.
\item The problem is simple enough to admit an exhaustive analysis,
but complicated enough that it is interesting.
\item The solution is \emph{principled}: it uses general concepts (diffusion, quotient),
and even the \emph{calculation} is not ad hoc. The only ``contigent'' part is
$2/9$ (and $2$ steps).
\item It's another discrete Laplacian problem, and I rather like these.
\end{itemize}
In general, it's a heat equation (duh: diffusion):
E(x) = 1 + avg(E(nbrs))
...where E(end) = 0
So: f = 1 + Delta f
...with boundary condition;
can solve however you like
(get (inhomogeneous) linear system of equations / constraints).
oh! on a line, you get d^2u = -1
...and du_start = -1
...so you get quadratic expected time:
4 3 0
9 8 5 0
(this is suspiciously like "quadratic drift",
but this integrates in the *other* direction:
time given distance, not distance given time.
Wonder about the connection...)
BTW, expectation *destroys* the delicate structure
that makes the cube trick work.