Solutions to Selected Exercises

Solution G.1 (Chapter 1, Predictability of White Noise vs an AR(1))

Problem. Chapter 1 introduces the entropy rate as a measure of how forecastable a stationary process is: the lower the entropy rate, the more of the next value is already determined by the past. Take a Gaussian white-noise process $x_t = \varepsilon_t$ with $\varepsilon_t \sim \mathcal{N}(0, \sigma^2)$ and a stationary Gaussian AR(1) process $y_t = \phi y_{t-1} + \varepsilon_t$ with $|\phi| < 1$ and the same innovation variance $\sigma^2$. Show that white noise is the least forecastable process at a given variance, and quantify exactly how much predictability the AR(1) buys as a function of $\phi$.

Reasoning. For a stationary Gaussian process the differential entropy rate is the entropy of the one-step prediction error, because the past collapses to a single sufficient predictor and only the residual remains uncertain. For a Gaussian variable with variance $v$ the differential entropy is $\tfrac{1}{2}\log(2\pi e\, v)$, so the entropy rate is governed entirely by the one-step-ahead prediction-error variance $v_{\text{pred}}$.

White noise has no usable past: the best predictor of $x_t$ is its mean, so the prediction error is $x_t$ itself and $v_{\text{pred}} = \sigma^2$. The AR(1) has a past that helps: the optimal one-step predictor is $\hat{y}_t = \phi y_{t-1}$, the prediction error is exactly the innovation $\varepsilon_t$, and so its prediction-error variance is also $\sigma^2$. The two processes share an entropy rate when matched on innovation variance, which is the precise statement that white noise is the worst case: the AR(1) only ever does as well, never worse, and it does strictly better once you match on the quantity a forecaster actually observes, the marginal variance.

A stationary AR(1) has marginal variance $\operatorname{Var}(y_t) = \sigma^2 / (1 - \phi^2)$, which exceeds $\sigma^2$ whenever $\phi \neq 0$. Fix the marginal variance of both processes to a common $\sigma_y^2$. White noise still spends all of it on unpredictable error, $v_{\text{pred}} = \sigma_y^2$. The AR(1) keeps only the fraction $(1-\phi^2)$ as prediction-error variance, $v_{\text{pred}} = (1-\phi^2)\,\sigma_y^2$, because the term $\phi y_{t-1}$ is already known. The entropy-rate gap, the bits per step the AR(1) saves, is therefore $$ \Delta H \;=\; \tfrac{1}{2}\log_2\!\frac{\sigma_y^2}{(1-\phi^2)\,\sigma_y^2} \;=\; -\tfrac{1}{2}\log_2\!\bigl(1-\phi^2\bigr), $$ which is zero at $\phi = 0$ and grows without bound as $|\phi| \to 1$. Equivalently the fraction of variance the AR(1) explains is the population $R^2 = \phi^2$.

import numpy as np
phi, sigma2 = 0.8, 1.0
var_marginal = sigma2 / (1 - phi**2)          # stationary marginal variance
var_pred_wn  = var_marginal                    # white noise: no usable past
var_pred_ar  = (1 - phi**2) * var_marginal     # AR(1): innovation variance only
delta_H_bits = -0.5 * np.log2(1 - phi**2)
print(f"marginal var        : {var_marginal:.4f}")
print(f"pred-err var (WN)   : {var_pred_wn:.4f}")
print(f"pred-err var (AR1)  : {var_pred_ar:.4f}   == sigma^2 = {sigma2}")
print(f"entropy-rate gap    : {delta_H_bits:.4f} bits/step")
print(f"population R^2       : {phi**2:.4f}")

Solution G.2 (Chapter 2, Finding and Fixing a Data-Leakage Bug)

Problem. Chapter 2 warns that the most damaging temporal bugs are silent ones that inflate validation scores. A practitioner standardizes a univariate series, then splits it into train and test, then fits a one-step forecaster, and reports a suspiciously low test error. The offending preprocessing is the snippet below. Identify the leak, explain the mechanism, and give the corrected pipeline.

# BUGGY pipeline
mu, sd = series.mean(), series.std()          # fit on the WHOLE series
scaled = (series - mu) / sd
train, test = scaled[:n_train], scaled[n_train:]

Reasoning. The leak is in the first line. The mean and standard deviation are computed over the entire series, test points included, and then used to scale the training data. Information from the test period (its level and its spread) flows backward into the features the model trains on, so the model is implicitly told something about the future it is later graded on predicting. The effect is usually small in magnitude but always optimistic, and it is invisible because the code runs without error and the leak only manifests as a test score that will not reproduce in deployment, where no future statistics exist.

The rule that prevents every variant of this bug is that any quantity estimated from data, a scaler, an imputation value, a feature-selection mask, a hyperparameter, must be fit on the training partition only and then applied unchanged to the test partition. The fix is to split first, fit the scaler on the training slice, and transform both slices with those training statistics. In a rolling or expanding-window evaluation the same discipline applies fold by fold: each fold refits its scaler on data strictly preceding its test window.

import numpy as np
rng = np.random.default_rng(0)
series = np.cumsum(rng.normal(size=400)) + 50.0   # a drifting series
n_train = 300

# CORRECT pipeline: split first, fit scaler on train only
train_raw, test_raw = series[:n_train], series[n_train:]
mu, sd = train_raw.mean(), train_raw.std()        # statistics from train alone
train = (train_raw - mu) / sd
test  = (test_raw  - mu) / sd                      # SAME mu, sd applied to test

# leakage diagnostic: do the two scalers disagree?
mu_all, sd_all = series.mean(), series.std()
print(f"train-only scaler : mu={mu:.3f}, sd={sd:.3f}")
print(f"whole-series scaler: mu={mu_all:.3f}, sd={sd_all:.3f}")
print(f"mean shift from leak: {abs(mu_all - mu):.3f}  (nonzero => leak would bias)")

Solution G.3 (Chapter 3, Reading ACF and PACF to Identify an AR(p) Order)

Problem. Chapter 3 teaches the Box-Jenkins identification heuristic: the autocorrelation function (ACF) and partial autocorrelation function (PACF) leave a fingerprint that distinguishes AR, MA, and ARMA structure. You are handed a stationary series whose sample ACF decays smoothly and geometrically toward zero, while its sample PACF is large at lags 1 and 2 and then drops abruptly inside the confidence band from lag 3 onward. Name the model and order, and justify the reading from first principles.

Reasoning. The two functions answer different questions. The ACF at lag $k$ measures the total correlation between $y_t$ and $y_{t-k}$, including everything that passes through the intermediate lags. The PACF at lag $k$ measures the correlation that remains after the linear effect of all shorter lags has been removed, which is exactly the coefficient on $y_{t-k}$ in a regression of $y_t$ on its first $k$ lags. For an AR($p$) process, $y_t$ is a linear function of precisely its first $p$ lags plus a fresh innovation, so once you condition on those $p$ lags there is no leftover correlation at lag $p+1$ or beyond: the PACF cuts off sharply after lag $p$. Meanwhile the ACF tails off geometrically, because correlation propagates indirectly through the recursion to every lag.

A PACF that is significant through lag 2 and negligible thereafter, paired with a smoothly decaying ACF, is the textbook signature of an AR(2). The mirror image, an ACF that cuts off after lag $q$ while the PACF tails off, identifies an MA($q$); a process where both functions tail off indicates a mixed ARMA. The confidence band, drawn at roughly $\pm 1.96/\sqrt{n}$ for $n$ observations, is the threshold for calling a coefficient negligible.

import numpy as np
from statsmodels.tsa.stattools import acf, pacf
rng = np.random.default_rng(7)
n = 600
a1, a2 = 0.5, 0.3                     # a true AR(2): roots inside unit circle
y = np.zeros(n)
e = rng.normal(size=n)
for t in range(2, n):
    y[t] = a1*y[t-1] + a2*y[t-2] + e[t]

band = 1.96 / np.sqrt(n)
p = pacf(y, nlags=6, method="ols")
sig = [k for k in range(1, 7) if abs(p[k]) > band]
print(f"95% band      : +/- {band:.3f}")
print(f"PACF lags 1..6: {np.round(p[1:7], 3)}")
print(f"significant PACF lags: {sig}  -> identifies AR({max(sig)})")
print(f"ACF lags 1..6 : {np.round(acf(y, nlags=6)[1:7], 3)}  (tails off smoothly)")

Solution G.4 (Chapter 5, The AR(1) Forecast Decays to the Mean)

Problem. Chapter 5 claims that the multi-step forecast of a stationary AR(1) decays geometrically toward the unconditional mean, and that its forecast variance grows to the unconditional variance. Starting from $y_t = c + \phi y_{t-1} + \varepsilon_t$ with $|\phi| < 1$, derive the $h$-step forecast $\hat{y}_{t+h}$ and its error variance, and identify both limits as $h \to \infty$.

Reasoning. The unconditional mean is found by taking expectations of the stationary recursion: $\mu = c + \phi\mu$ gives $\mu = c/(1-\phi)$. Rewrite the process in deviations from the mean, $\tilde{y}_t = y_t - \mu$, so that $\tilde{y}_t = \phi\tilde{y}_{t-1} + \varepsilon_t$ with no constant. Iterating the recursion forward from the last observed value $\tilde{y}_t$ unrolls it into $$ \tilde{y}_{t+h} = \phi^h \tilde{y}_t + \sum_{j=0}^{h-1} \phi^{j}\,\varepsilon_{t+h-j}. $$ Taking the conditional expectation given information through time $t$ kills every future innovation (each has mean zero and is independent of the past), leaving the point forecast $$ \hat{y}_{t+h} = \mu + \phi^h\,(y_t - \mu). $$ Because $|\phi| < 1$, the factor $\phi^h \to 0$, so the forecast relaxes geometrically from the current value back to the unconditional mean $\mu$: the process forgets its starting point at rate $\phi$.

The forecast error is the discarded innovation sum, whose terms are uncorrelated, so its variance is a geometric series: $$ \operatorname{Var}(y_{t+h} - \hat{y}_{t+h}) = \sigma^2 \sum_{j=0}^{h-1}\phi^{2j} = \sigma^2\,\frac{1-\phi^{2h}}{1-\phi^2}. $$ At $h=1$ this is just $\sigma^2$, the innovation variance, and as $h \to \infty$ it climbs monotonically to $\sigma^2/(1-\phi^2)$, which is precisely the unconditional variance of the process. The forecast distribution therefore converges to the marginal distribution: far enough out, the best you can say about an AR(1) is its climatology.

import numpy as np
c, phi, sigma2 = 2.0, 0.7, 1.0
mu = c / (1 - phi)
y_t = 12.0                                  # last observed value
h = np.arange(1, 11)
forecast = mu + phi**h * (y_t - mu)
var_err  = sigma2 * (1 - phi**(2*h)) / (1 - phi**2)
print(f"unconditional mean mu     : {mu:.4f}")
print(f"unconditional var         : {sigma2/(1-phi**2):.4f}")
for hi, f, v in zip(h, forecast, var_err):
    print(f"h={hi:2d}  forecast={f:7.4f}  var={v:7.4f}")

Solution G.5 (Chapter 7, One Kalman Predict-Update Cycle by Hand)

Problem. Chapter 7 builds the Kalman filter as a predict step followed by an update step. Take the scalar local-level model $x_t = x_{t-1} + w_t$ with process variance $Q = 1$ and observation $z_t = x_t + v_t$ with measurement variance $R = 2$. The filter currently believes $x_{t-1} \sim \mathcal{N}(\hat{x} = 10,\, P = 4)$. A new measurement arrives, $z_t = 13$. Carry out one full predict-update cycle by hand and report the posterior mean and variance.

Reasoning. The scalar local-level filter is the Kalman filter with all matrices equal to one, so the equations reduce to arithmetic. The predict step rolls the belief forward through the dynamics. With unit transition the predicted mean is unchanged, $\hat{x}^- = \hat{x} = 10$, but the variance grows by the process noise because a step into the future is a step of added uncertainty: $P^- = P + Q = 4 + 1 = 5$.

The update step folds in the measurement. The innovation is the surprise in the observation, $y = z_t - \hat{x}^- = 13 - 10 = 3$, and its variance is the predicted variance plus the measurement noise, $S = P^- + R = 5 + 2 = 7$. The Kalman gain is the ratio that decides how much to trust the measurement, $K = P^-/S = 5/7 \approx 0.714$: it leans toward the sensor when $P^-$ dominates and toward the model when $R$ dominates. The posterior mean nudges the prediction toward the measurement in proportion to the gain, $$ \hat{x}^+ = \hat{x}^- + K\,y = 10 + \tfrac{5}{7}\cdot 3 = 10 + \tfrac{15}{7} \approx 12.143, $$ and the posterior variance shrinks because the measurement removed uncertainty, $$ P^+ = (1 - K)\,P^- = \bigl(1 - \tfrac{5}{7}\bigr)\cdot 5 = \tfrac{2}{7}\cdot 5 \approx 1.429. $$ The belief moved most of the way to the measurement (the sensor was only slightly noisier than the prior) and tightened from variance $5$ before the update to about $1.43$ after it.

x, P, Q, R, z = 10.0, 4.0, 1.0, 2.0, 13.0
# predict
x_pred = x
P_pred = P + Q
# update
y = z - x_pred                 # innovation
S = P_pred + R                 # innovation variance
K = P_pred / S                 # Kalman gain
x_post = x_pred + K * y
P_post = (1 - K) * P_pred
print(f"predict: x-={x_pred:.4f}, P-={P_pred:.4f}")
print(f"gain   : K ={K:.4f}")
print(f"update : x+={x_post:.4f}, P+={P_post:.4f}")

Solution G.6 (Chapter 19, Conformal-Interval Coverage Under Drift)

Problem. Chapter 19 introduces split conformal prediction, which guarantees marginal coverage $1-\alpha$ when the calibration and test data are exchangeable. The exercise asks you to demonstrate, by simulation, that this guarantee fails when the test distribution drifts away from calibration, and to confirm that the failure is a coverage shortfall rather than a coding error. Build a split-conformal interval for a regression residual, calibrate it under one noise scale, evaluate it under a larger noise scale, and report the empirical coverage against the nominal $90\%$.

Reasoning. Split conformal forms an interval by taking the $\lceil (1-\alpha)(n+1)\rceil$-th smallest absolute residual on a held-out calibration set as the half-width $q$, then predicting $\hat{y}\pm q$. The finite-sample guarantee is $\Pr(|y - \hat{y}| \le q) \ge 1-\alpha$, and it rests entirely on exchangeability: calibration and test residuals must be draws from the same distribution. When the test errors are drawn from a heavier-tailed or larger-scale distribution than calibration, the quantile $q$ calibrated on the quiet regime is too narrow for the noisy regime, and empirical coverage falls below nominal. The shortfall is not a bug; it is the precise price the method documents for the broken assumption, which is why Chapter 19 and Chapter 20 develop adaptive conformal methods that re-estimate $q$ online as drift is detected.

The check below calibrates $q$ on residuals of scale $\sigma=1$, then measures coverage on a clean test set (which should sit at or just above $90\%$, confirming the implementation) and on a drifted test set of scale $\sigma=2.5$ (which should fall well short). Seeing both outcomes from one $q$ isolates drift as the cause.

import numpy as np
rng = np.random.default_rng(1)
alpha = 0.10
n_cal = 1000
cal = np.abs(rng.normal(0, 1.0, n_cal))                 # calibration residuals, sigma=1
k = int(np.ceil((1 - alpha) * (n_cal + 1)))            # conformal rank
q = np.sort(cal)[k - 1]                                 # interval half-width

clean   = np.abs(rng.normal(0, 1.0, 20000))            # exchangeable test
drifted = np.abs(rng.normal(0, 2.5, 20000))            # drifted test, sigma=2.5
cov_clean   = np.mean(clean   <= q)
cov_drifted = np.mean(drifted <= q)
print(f"half-width q            : {q:.4f}")
print(f"nominal coverage        : {1 - alpha:.2%}")
print(f"empirical (no drift)    : {cov_clean:.2%}   (>= nominal: guarantee holds)")
print(f"empirical (under drift) : {cov_drifted:.2%}   (< nominal: guarantee broken)")

Solution G.7 (Chapter 24, Q-Learning vs SARSA on the Same Transition)

Problem. Chapter 24 contrasts Q-learning (off-policy) and SARSA (on-policy) by the single line that differs in their update. Both observe the same transition $(s, a, r, s')$. The current action-value estimates at $s'$ are $Q(s', a_1) = 5$ and $Q(s', a_2) = 2$. The behavior policy actually takes $a_2$ next (an exploratory move), the reward is $r = 1$, the step size is $\eta = 0.5$, the discount is $\gamma = 0.9$, and the current estimate is $Q(s, a) = 3$. Compute one update under each algorithm and explain why they differ.

Reasoning. Both algorithms share the form $Q(s,a) \leftarrow Q(s,a) + \eta\,[\,\text{target} - Q(s,a)\,]$, and differ only in the bootstrap target. Q-learning is off-policy: its target uses the greedy value at $s'$, $r + \gamma\max_{a'}Q(s',a')$, evaluating the best the agent could do regardless of what it actually does next. SARSA is on-policy: its target uses the value of the action the policy actually takes, $r + \gamma Q(s', a_{\text{next}})$, so it accounts for the cost of its own exploration.

Here the greedy action at $s'$ is $a_1$ with value $5$, but the behavior policy explores into $a_2$ with value $2$. Q-learning's target is $1 + 0.9\cdot 5 = 5.5$, giving the TD error $5.5 - 3 = 2.5$ and the update $Q(s,a) \leftarrow 3 + 0.5\cdot 2.5 = 4.25$. SARSA's target is $1 + 0.9\cdot 2 = 2.8$, giving the TD error $2.8 - 3 = -0.2$ and the update $Q(s,a) \leftarrow 3 + 0.5\cdot(-0.2) = 2.9$. The two land on opposite sides of the starting value: Q-learning revises upward toward the optimistic greedy continuation, while SARSA revises downward because the exploratory step it actually took was poor. This is the mechanism behind their classic divergence (the cliff-walking example), where SARSA learns a safer, exploration-aware path and Q-learning learns the optimal but riskier one.

Q_sa = 3.0
Q_s2 = {"a1": 5.0, "a2": 2.0}
r, eta, gamma, a_next = 1.0, 0.5, 0.9, "a2"   # behavior policy explores into a2

target_q = r + gamma * max(Q_s2.values())     # Q-learning: greedy
target_s = r + gamma * Q_s2[a_next]           # SARSA: action actually taken
update_q = Q_sa + eta * (target_q - Q_sa)
update_s = Q_sa + eta * (target_s - Q_sa)
print(f"Q-learning target={target_q:.2f}  TD-err={target_q-Q_sa:+.2f}  Q<-{update_q:.3f}")
print(f"SARSA      target={target_s:.2f}  TD-err={target_s-Q_sa:+.2f}  Q<-{update_s:.3f}")

Solution G.8 (Chapter 28, Computing a Return-to-Go Along a Trajectory)

Problem. Chapter 28 casts reinforcement learning as a sequence-modeling problem, and the Decision Transformer conditions each action on the return-to-go, the sum of rewards still to come from that step onward. Given the reward sequence along a five-step trajectory, $r = (1,\, 0,\, 2,\, -1,\, 3)$, compute the discounted return-to-go at every timestep for discount $\gamma = 0.9$, and state how the conditioning target at the start of the trajectory is set at test time.

Reasoning. The return-to-go at step $t$ is the discounted sum of all rewards from $t$ to the end of the episode, $R_t = \sum_{k=t}^{T} \gamma^{\,k-t} r_k$. It satisfies the backward recursion $R_t = r_t + \gamma R_{t+1}$ with $R_{T+1} = 0$, which is the efficient way to compute the whole vector in one right-to-left sweep. Working from the last step inward with $\gamma = 0.9$:

$R_5 = 3$. Then $R_4 = -1 + 0.9\cdot 3 = 1.7$. Then $R_3 = 2 + 0.9\cdot 1.7 = 3.53$. Then $R_2 = 0 + 0.9\cdot 3.53 = 3.177$. Finally $R_1 = 1 + 0.9\cdot 3.177 = 3.8593$. The return-to-go sequence is therefore $(3.8593,\, 3.177,\, 3.53,\, 1.7,\, 3)$, and notice it is not monotone: it dips wherever a future reward is negative, because return-to-go looks forward, unlike the cumulative reward that looks back.

At training time these returns-to-go are read directly off logged trajectories and fed to the model as conditioning tokens. At test time there is no future to sum, so the first token is set to a desired return, an aspiration the policy is asked to achieve, and after each executed step it is decremented by the reward just received ($R_{t+1} = (R_t - r_t)/\gamma$, or simply $R_t - r_t$ in the undiscounted case). Conditioning on a high desired return steers the transformer toward the high-reward behaviors it saw in the data, which is how a model trained by pure supervised sequence prediction is made to act like a controller.

import numpy as np
rewards = np.array([1.0, 0.0, 2.0, -1.0, 3.0])
gamma = 0.9
rtg = np.zeros_like(rewards)
acc = 0.0
for t in reversed(range(len(rewards))):       # one right-to-left sweep
    acc = rewards[t] + gamma * acc
    rtg[t] = acc
print(f"rewards         : {rewards}")
print(f"return-to-go    : {np.round(rtg, 4)}")
print(f"start conditioning target R_1 = {rtg[0]:.4f}")