Project Euler Problem 978

Solution

Answer: 254.54470757

Problem statement

Project Euler Problem 978 is titled “Random Walk Skewness”. The statement is:

In this problem we consider a random walk on the integers $\mathbb{Z}$, in which our position at time $t$ is denoted as $X_t$.

At time $0$ we start at position $0$. That is, $X_0=0$.

At time $1$ we jump to position $1$. That is, $X_1=1$.

Thereafter, at time $t=2,3,\dots$ we make a jump of size $|X_{t-2}|$ in either the positive or negative direction, with probability $1/2$ each way. If $X_{t-2}=0$ we stay put at time $t$.

At $t=5$ we find our position $X_5$ has the following distribution:

$$X_5=\begin{cases} > -1 & \text{with probability }3/8\ > 1 & \text{with probability }3/8\ > 3 & \text{with probability }1/8\ > 5 & \text{with probability }1/8 > \end{cases}$$

The standard deviation $\sigma$ of a random variable $X$ with mean $\mu$ is defined as

$$\sigma=\sqrt{\mathbb{E}[X^2]-\mu^2}$$

Furthermore the skewness of $X$ is defined as

$$\text{Skew}(X)=\mathbb{E}!\left[\left(\frac{X-\mu}{\sigma}\right)^3\right]$$

For $X_5$, which has mean $1$ and standard deviation $2$, we find

$$\text{Skew}(X_5)=0.75.$$

You are also given

$$\text{Skew}(X_{10})\approx2.50997097.$$

Find $\text{Skew}(X_{50})$. Give your answer rounded to eight digits after the decimal point.

---

Mathematical analysis

Define independent random signs $\varepsilon_t\in{-1,+1}$ for $t\ge2$, each with probability $1/2$.

The process is

$$X_t = X_{t-1} + \varepsilon_t |X_{t-2}|.$$

We need the skewness:

$$\text{Skew}(X_n) = \frac{\mathbb E[(X_n-\mu)^3]}{\sigma^3}.$$

So we need:

• the mean $\mu_n=\mathbb E[X_n]$,
• the variance,
• the third central moment.

---

Step 1: Mean

Conditioning on the past,

$$\mathbb E[\varepsilon_t]=0,$$

hence

$$\mathbb E[X_t] = \mathbb E[X_{t-1}] + \mathbb E[\varepsilon_t |X_{t-2}|] = \mathbb E[X_{t-1}].$$

Since $X_1=1$,

$$\boxed{\mathbb E[X_t]=1 \quad \forall t\ge1.}$$

So the mean is always $1$.

---

Step 2: Second moment

Let

$$a_t=\mathbb E[X_t^2].$$

Expand:

$$X_t^2 = X_{t-1}^2 + X_{t-2}^2 + 2\varepsilon_t X_{t-1}|X_{t-2}|.$$

Taking expectation kills the cross term:

$$a_t=a_{t-1}+a_{t-2}.$$

Initial values:

$$a_0=0,\qquad a_1=1.$$

Thus $a_t$ is exactly the Fibonacci sequence:

$$\boxed{a_t=F_t}.$$

Therefore

$$\operatorname{Var}(X_t)=F_t-1.$$

For $t=50$,

$$F_{50}=12586269025.$$

Hence

$$\sigma^2 = 12586269024.$$

---

Step 3: Third moment

Let

$$b_t=\mathbb E[X_t^3].$$

Expand:

$$(X_{t-1}+\varepsilon_t|X_{t-2}|)^3.$$

Odd powers of $\varepsilon_t$ vanish in expectation, giving

$$b_t = b_{t-1} + 3\mathbb E[X_{t-1}X_{t-2}^2].$$

Now define

$$c_t=\mathbb E[X_tX_{t-1}^2].$$

Using

$$X_t=X_{t-1}+\varepsilon_t|X_{t-2}|,$$

we get

$$c_t = \mathbb E[X_{t-1}^3] + \mathbb E[\varepsilon_t|X_{t-2}|X_{t-1}^2].$$

Again the second term vanishes, so

$$c_t=b_{t-1}.$$

Therefore

$$\boxed{b_t=b_{t-1}+3b_{t-2}}.$$

Initial conditions:

$$b_0=0,\qquad b_1=1.$$

Computing forward gives:

$$b_{50}=359426118413557441.$$

---

Step 4: Third central moment

Since the mean is $1$,

$$\mu_3 = \mathbb E[(X_{50}-1)^3].$$

Using

$$\mathbb E[(X-1)^3] = \mathbb E[X^3]-3\mathbb E[X^2]+3\mathbb E[X]-1,$$

and $\mathbb E[X]=1$,

$$\mu_3 = b_{50}-3F_{50}+2.$$

Substitute values:

$$\mu_3 = 359426118413557441 - 3(12586269025) + 2 = 359426080654750368.$$

---

Step 5: Skewness

$$\text{Skew}(X_{50}) = \frac{359426080654750368}{(12586269024)^{3/2}}.$$

Numerically,

$$\boxed{ \text{Skew}(X_{50}) \approx 254.54470756901193 }$$

Rounded to eight digits:

$$\boxed{254.54470757}$$

---

Python implementation

from math import sqrt

N = 50

# Second moments: a[n] = E[X_n^2]
a = [0] * (N + 1)
a[0] = 0
a[1] = 1

for n in range(2, N + 1):
    a[n] = a[n - 1] + a[n - 2]

# Third moments: b[n] = E[X_n^3]
b = [0] * (N + 1)
b[0] = 0
b[1] = 1

for n in range(2, N + 1):
    b[n] = b[n - 1] + 3 * b[n - 2]

mean = 1
variance = a[N] - 1
sigma = sqrt(variance)

third_central = b[N] - 3 * a[N] + 2

skewness = third_central / (sigma ** 3)

print(f"{skewness:.8f}")

---

Code walkthrough

• a[n] stores $\mathbb E[X_n^2]$.
• The recurrence

$$a_n=a_{n-1}+a_{n-2}$$

generates Fibonacci numbers.

• b[n] stores $\mathbb E[X_n^3]$.
• The recurrence

$$b_n=b_{n-1}+3b_{n-2}$$

comes from the cubic expansion.

• The variance is

$$\sigma^2=a_n-1.$$

• The third central moment is

$$b_n-3a_n+2.$$

• Finally:

$$\text{Skew}=\mu_3/\sigma^3.$$

The code also reproduces the provided check value:

$$\text{Skew}(X_{10})\approx2.50997097.$$

So the derivation is consistent.

---

Answer: 254.54470757