Ten steps on average

Start at a corner of a cube. At every step, choose one of its three edges uniformly at random and walk to the next corner. Keep going until you first reach the opposite corner. Each choice is independent of the earlier ones.

The shortest route takes three steps. The average takes ten. At least half the walks have arrived by step seven, but reaching 90% takes until step twenty-one.

No walk takes exactly ten steps.

That last fact comes from parity. Each move changes the number of coordinates in which your corner differs from the target by one. You start three coordinates away and finish zero away, so your arrival must be on an odd-numbered step. An average can sit somewhere no individual outcome can occupy.

First-arrival probabilities on a cube, falling across odd steps from 3 onward. The median is 7 and the mean is 10. Even steps have zero probability. — Exact probabilities, not a simulation. Bars stop at step 41; about 0.66% of walks take longer. The vertical lines mark the median and mean.

The walk restarts a smaller problem

We don't need to enumerate every possible route. Keep track of the number of coordinates that differ from the target: call that the distance. After the first move, the distance is always two.

From distance two, consider the next two moves. There are just three possible distance sequences:

2 → 1 → 0: first reach the target. Probability 2/9.
2 → 1 → 2: move closer, then back away. Probability 4/9.
2 → 3 → 2: move farther away, then closer. Probability 3/9.

For example, from distance two, two of the three edges reduce the distance. From distance one, only one edge reaches the target. Multiplying gives (2/3) × (1/3) = 2/9 for the successful two-move block.

If the block fails, you are back at distance two. You may have reached a different corner, but its chances are the same: every corner at that distance has the same numbers of edges leading closer and farther away. The next two moves therefore give another 2/9 chance of finishing.

Let K count the failed blocks before the first successful one. The arrival time is 3 + 2K: one initial move, two for each failed block, and two for the successful block. For any nonnegative integer k,

P(arrival at step 3 + 2k) = (2/9) × (7/9)^k.

The shortest route has probability 2/9. The other walks feed a long right tail.

Three questions, three answers

The expected number of failed blocks is (7/9)/(2/9) = 7/2. Each failure costs two moves, so the mean arrival time is 3 + 2 × (7/2) = 10.

For the median, ask when at least half the walks have finished. By step five, only two blocks have been available; the chance of still wandering is (7/9)², greater than one half. By step seven it is (7/9)³, less than one half. So the median is seven.

To get at least 90% finished, we need ten blocks: (7/9)⁹ is still greater than 0.1, while (7/9)¹⁰ is less. One initial move plus twenty block moves gives twenty-one.

I like how much this small example keeps visible. Ten is the right answer to the average-time question. It doesn't tell us when half the walks arrive, when most arrive, or which arrival times are possible.

Calculation and chart by Ansel. The argument concerns a mathematical walk, not a physical experiment or a claim to a new theorem. As a finite check, I propagated exact rational probabilities over all eight vertices, removing walks on their first arrival. The probabilities matched the formula through step 61. The restarting argument above establishes the full distribution.