A 4 dimensional random walk!

Probability Level 5

You start at the point $(x,y,z) = (1,1,1)$ in a Cartesian coordinate system, at time $t=0$ . If we consider time to be a fourth dimension, we start at coordinate $(x,y,z,t) = (1,1,1,0)$

Every turn you take you move randomly in one of eight (yes 8!) possible directions, six of them are the six directions available to you on the Cartesian coordinate system ( $\pm \widehat{x}$ , $\pm \widehat{y}$ , $\pm \widehat{z}$ ), and the remaining two are to move backward or forward in time by one second.

What is the expected value for the number of moves (either in space or time or both) that it will take for you to land on a point $(3a, 3b, 3c, 3d$ ) where $a$ , $b$ , $c$ and $d$ are integers . $(a,b,c)$ is your $(x,y,z)$ location, and $d$ is how many seconds from when you started. Remember, time only moves (forward or backward) when you travel in time, otherwise it remains still.

Clarification: On any move you can go one unit in either direction on any of the three axes, or you can go backward or forward in time by one second each with probability $1/8$ .

Note: If you end up moving in space, the move is instantaneous (i.e. time freezes), but if you move in time, you remain at a fixed location in space for that move.

Image credit: www.bbcamerica.com

The answer is 96.

1 solution

Geoff Pilling
Jun 11, 2016

By symmetry there are only four unique expectation values in the problem.

They are represented by the expectation values from the following points:

$(1,0,0,0), (1,1,0,0), (1,1,1,0), (1,1,1,1)$ (The fourth coordinate is time, the fourth dimension)

Let $E_1$ through $E_4$ be defined as the expected value for the number of moves it would take to get to $(3a,3b,3c,3d)$ for integral $a$ , $b$ , $c$ and $d$ from each of these locations respectively.

From each grid point the expectation value is given by $E = 1 + 1/8 *$ (sum of all eight neighboring expectation values)

So, we have the following set of linear equations:

$E_1 = 1 + (1/8)(E_1+6E_2)$ $E_2 = 1 + (1/8)(2E_1+2E_2+4E_3)$ $E_3 = 1 + (1/8)(3E_2+3E_3+2E_4)$ $E_4 = 1 + (1/8)(4E_3+4E_4)$

Sovling for $E_3$ , this gives, $E_3 = \boxed{96}$

I think we can generalise the result for $n$ dimensions with the recurrence relation:

$E_{n+1}=2 \times 3^n+E_n+\dfrac{E_n}{n} \quad \quad E_1=2$

Where $E_n$ is the expected number of moves to get to a point $\underbrace{(3a_1,3a_2, \cdots, 3a_{n-1},3a_n)}_{n}$ starting from a point $\underbrace{(1,1,\cdots,1,1)}_{n}$ . I haven't been able to prove this though.

Sam Bealing - 4 years, 11 months ago

Interesting observation... Lemme think about that one...

Geoff Pilling - 4 years, 11 months ago

A 4 dimensional random walk!

The answer is 96.

1 solution

0 pending reports