0
$\begingroup$

I got asked this for an assignment but I ran out of time and had to guess. I thought about it after and still not sure about the right approach.

Imagine the corners of a cube. Each second you move to a random neighboring corner (with equal probability). What is the expected number of seconds before you reach the opposite corner?

I couldn't ask clarifying questions but I assume that "neighbouring corner" means you can move one spot up, down, left, right or diagonally.

Here's my attempt: I thought about how the cube is 3D and labelled all the coordinates.

Opposite corner would mean going from (0,0,0) ---> (1,1,1). That means you have a 4 corners to choose from every second.

It's possible to reach the opposite in 3, 4 or 5 steps/seconds. Would you then take how many outcomes for each of those and multiply by 1/4 every time it moves a corner, then averaged out to find the "expected number"?

I tried visualizing this problem below.

Here is one way of reaching an opposite end: enter image description here

Please help! Thanks!

$\endgroup$
2
  • 2
    $\begingroup$ Given it says every second, I think it should travel same distance - which means at any point, there are $3$ possible neighbouring corners to move to and not diagonally. $\endgroup$
    – Math Lover
    Commented Sep 29, 2020 at 20:32
  • $\begingroup$ Ah i see, that makes more sense. I think adding the diagonal as a possibility made me more confused in my calculations. Now it's reduce probability to 1/3 for every move. $\endgroup$
    – Mathie102
    Commented Sep 29, 2020 at 20:42

1 Answer 1

3
$\begingroup$

To begin, let's clear up the assumptions in the problem you made.

Moving from one corner to a "neighboring corner" would involve traveling along an edge. That would be moving left or right, moving up or down, and moving forward or backward. Reworded, if you treat your position as a binary triple, it involves flipping exactly one of the three bits from $1$ to $0$ or vice versa from $0$ to $1$.

Now... notice that we can describe any position on the cube by its "distance" to the goal. Starting from distance $3$ away from the goal (i.e. starting at the starting corner) you will always move to a corner which is distance $2$ away from the goal. Moving from a distance $2$ away you will either move to a distance $3$ away with probability $\frac{1}{3}$ or get closer to a distance $1$ away with probability $\frac{2}{3}$, and so on... If you are already at the goal you stop moving.

Let $f(n)$ be the expected remaining number of moves to get to the end when you begin at a distance $n$ away.

We arrive at the following system of equations:

$$\begin{cases}f(0)=0\\f(1)=\frac{1}{3}f(0)+\frac{2}{3}f(2)+1\\f(2)=\frac{2}{3}f(1)+\frac{1}{3}f(3)+1\\f(3)=f(2)+1\end{cases}$$

Solving the system of equations for $f(3)$ yields the answer you are after as being $10$

$\endgroup$
4
  • $\begingroup$ Thank you! this is very helpful. Could you clarify why you added the "+1" to the end of the equations? Is it because of it adds one more second in total? $\endgroup$
    – Mathie102
    Commented Sep 29, 2020 at 20:54
  • 1
    $\begingroup$ @Mathie102 yes. For instance if you are at distance $2$, then the motion to the "next" spot, whichever spot that might be, adds an additional one second to the overall clock. Then, in addition to that one additional second required because of that move, you will also require an additional $f(1)$ seconds in the event that you moved to distance $1$ away which occurs with probability $\frac{2}{3}$ or you will require an additional $f(3)$ seconds in the event that you moved further away. $\endgroup$
    – JMoravitz
    Commented Sep 29, 2020 at 20:59
  • 2
    $\begingroup$ The point to take away from this is... we don't care about finding the probability of ending after exactly $3$ seconds or ending after exactly $5$ seconds, etc... that wasn't needed. The approach taken here uses the language and theory of Markov Chains. The analysis of the situation I happened to use a system of equations this time, though you could just as easily have used matrices as you'll often see me do in other answers to similar questions. $\endgroup$
    – JMoravitz
    Commented Sep 29, 2020 at 21:01
  • $\begingroup$ It would be interesting to know the answers to the analogous questions for octohedra, dodecahedra and icosahedra. And easy enough to find out using the same method. $\endgroup$
    – Big Al
    Commented Sep 29, 2020 at 22:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .