Continuous time random walk on a cube - characteristic function

Question

A continuous time random walk on the corners of a cube spends a unit mean exponentially distributed random time at each corner after which it selects on of the three neighbor corners as its next position with equal probabilities 1/3.

Find the characteristic function for the random time it takes the random walk to move between two diametrically opposite corners.

Where are you even supposed to start? I know that we can re-interpret this cube as a Birth-Death process with four states and different probabilities, but where does the characteristic function even go?

Answer 1

Here is how I would do it.

1. Let $N$ be the number of steps it takes starting from $(0,0,0)$ to reach $(1,1,1)$. Compute the distribution for $N$.
2. Each step takes you $X_i \sim \mathcal{Exp}(1)$, so the total time taken is $$T = \sum_{k=1}^N X_i.$$ Note that the sum has a variable limit.
3. Find the distribution of $T$ by conditioning on $N$.
4. Use Fourier transform to convert distribution (pdf) into the characteristic function.

But maybe there is a more obvious shorter way.

Answer 2

I am not completely fond of gt6989b's answer, because computing the distribution on $N$ is about as complicated as finding directly the characteristic function of the hitting time. We may also miss a nice factorization which should be obvious from a more direct computation.

In the following, $f$ is the characteristic function of a step (so $f(\omega) = (1-i\omega)^{-1}$ for steps with a standard exponential distribution).

Let $A$ and $B$ be two opposite corners. Assume that the random walk starts from $A$. We can classify the corners into four types, according to their distance from $A$:

• Type $1$: the corner $A$.
• Type $2$: the three corners at distance $1$ from $A$.
• Type $3$: the three corners at distance $2$ from $A$.
• Type $4$: the corner $B$.

For any corner $C$, let $T_C$ be the first time that a random walk from $C$ hits $B$, and $\psi_C$ the characteristic function of $T_C$. Then we want to compute $\psi_A$. Note that, by rotational symmetry along the diagonal $[AB]$, the distribution of $T_C$, and thus $\psi_C$, depends only on the type of the corner. Let $\psi_i$ be the characteristic function of $T_C$ for a corner $C$ of type $i$.

Starting from $A$, the next corner is always of type $2$. Hence, $T_1=T_2+X$, where $X$ is the time of the first step from $A$, and $T_2$ is the hitting time from the corner at which we land. By Markov's property, $T_2$ and $X$ are independent, so:

$$\psi_1=\psi_2 f.$$

Starting from a corner of type $2$, the next corner is of type $1$ with probability $1/3$, and of type $3$ with probability $2/3$. Hence,

$$\psi_2=\frac{\psi_1+2\psi_3}{3}f.$$

For the same reason, we get:

$$\psi_3=\frac{2\psi_2+\psi_4}{3}f.$$

Finally, if we are in $B$, then we hit $B$ at time $0$, so:

$$\psi_4=1.$$

Now, only rote computation remains. I put in in spoiler, so that you can try it yourself if you want.

Going back, we get in order: $$\psi_3=\frac{2\psi_2+1}{3}f,$$ $$\psi_2=\frac{\psi_1+2\frac{2\psi_2+1}{3}f}{3}f = \frac{4\psi_2f^2}{9} + \frac{3\psi_1+2f}{9}f,$$ whence: $$\psi_2=\frac{3\psi_1f+2f^2}{9-4f^2},$$ and finally: $$\psi_1=\frac{3\psi_1f^2+2f^3}{9-4f^2}.$$

Finally, we get:

$$\psi_1=\frac{2f^3}{9-7f^2},$$

which is what is shown in the solutions.