# Workbook 11 — Companion: three outcomes, two moments > [!abstract] What this page is for > Workbook 11 asks for the general statement once — $\mathrm{Var}[X]=\mathbb{E}[X^{2}]-\mu_{X}^{2}$, $\mathbb{E}[S_{n}]=S_{0}+n\,\mathbb{E}[X]$, $\mathrm{Var}[S_{n}]=n\,\mathrm{Var}[X]$ — and then its use on a three-outcome step with unequal probabilities. This page runs **the same calculation on a different step**: three outcomes, one of them a *pause*, chosen so the walk has no drift even though the step is lopsided. Follow it end to end and the sheet's numbers are still yours to compute. > > 📄 [[MATH310F26_WB11.pdf|Workbook 11 (blank, 1 page)]] · [[MATH310F26(Day 15) - The second moment, and the bands|Day 15 note]] · [[MATH310F26(Day 14) - Into stochasticity|Day 14 note]] > > 🎓 [Submit on Canvas](https://elearning.mines.edu/courses/81632/assignments/588368) --- ## 1. The given: a step that can stand still Write the three objects in the order the Day 14 board did. The **sample space**, in words: $\Omega=\{\text{move } 2L \text{ to the left},\ \text{stay put},\ \text{move } L \text{ to the right}\}$. The **event space**, the numbers those words become: $\mathcal{F}=\{-2L,\,0,\,L\}$. The **probability function**, in the same order: $P:\mathcal{F}\to\Big\{\tfrac{1}{4},\ \tfrac{1}{4},\ \tfrac{1}{2}\Big\}.$ Before anything else, check that $P$ *is* a probability function: the values are nonnegative and $\tfrac14+\tfrac14+\tfrac12=1$. (Do this on the sheet too — it is the one check that catches a mis-copied fraction before it poisons every number downstream.) Then $X$ is the random variable that reads the event space, and the walk is $S_{n}=S_{0}+\sum_{i=0}^{n-1}X_{i}$ with i.i.d. $X_{i}\sim X$ and $S_{0}=0$. ## 2. The step's first moment The expectation is the probability-weighted sum over the events — the delta-localized version of $\int x\rho_{X}(x)\,dx$ from Wednesday: $\mathbb{E}[X]=\mu_{X}=\sum_{i=1}^{3}x_{i}\,p(x_{i})=(-2L)\tfrac{1}{4}+(0)\tfrac{1}{4}+(L)\tfrac{1}{2}=-\tfrac{L}{2}+\tfrac{L}{2}=0.$ So this walk is **driftless**: the rare big step left is exactly balanced by the common small step right. Notice what that does *not* say — the step is not symmetric, and the walker is more often to the right of $0$ than to the left on any given tick. Zero drift is a statement about the *average*, nothing more. ## 3. The step's second moment, by both routes **Route one, the shortcut.** Compute $\mathbb{E}[X^{2}]$ the same way — square the events, keep the probabilities: $\mathbb{E}[X^{2}]=\sum_{i=1}^{3}x_{i}^{2}\,p(x_{i})=(4L^{2})\tfrac{1}{4}+(0)\tfrac{1}{4}+(L^{2})\tfrac{1}{2}=L^{2}+\tfrac{L^{2}}{2}=\tfrac{3}{2}L^{2},$ and then $\mathrm{Var}[X]=\mathbb{E}[X^{2}]-\mu_{X}^{2}=\tfrac{3}{2}L^{2}-0=\tfrac{3}{2}L^{2}$. **Route two, the definition.** $\mathrm{Var}[X]=\mathbb{E}[(X-\mu_{X})^{2}]$, which with $\mu_{X}=0$ is the same sum — but on a step *with* drift the two routes look different on paper and must agree, so it is worth seeing both once: $\mathrm{Var}[X]=\sum_{i=1}^{3}(x_{i}-\mu_{X})^{2}\,p(x_{i})=(-2L-0)^{2}\tfrac{1}{4}+(0-0)^{2}\tfrac{1}{4}+(L-0)^{2}\tfrac{1}{2}=\tfrac{3}{2}L^{2}.\ \checkmark$ Units: $L^{2}$, as a variance must be. The standard deviation of one step is $\sqrt{3/2}\,L\approx 1.22L$ — larger than the fair $\pm L$ coin's $1\cdot L$, because the occasional $-2L$ lunge spreads the step out more than the pause pulls it in. > [!note] Why the two-outcome shortcut does not apply here > Wednesday's board collapsed the two-outcome variance to $p_{1}p_{2}(L_{1}-L_{2})^{2}$. That formula used $p_{1}+p_{2}=1$ to turn $1-p_{1}$ into $p_{2}$; with three outcomes, $1-p_{1}=p_{2}+p_{3}$ and the clean factoring is gone. Go back to $\mathbb{E}[X^{2}]-\mu_{X}^{2}$ — it always works, for any number of outcomes. ## 4. The walk inherits the step Now push both moments through the sum. The expectation is linear and passes over the deterministic $S_{0}$: $\mathbb{E}[S_{n}]=S_{0}+\sum_{i=0}^{n-1}\mathbb{E}[X_{i}]=0+n\cdot 0=0.$ The variance is *not* linear in general — but the $X_{i}$ are independent of each other and of $S_{0}$, so the variance of the sum is the sum of the variances, and $\mathrm{Var}[S_{0}]=0$ because the start is not random: $\mathrm{Var}[S_{n}]=\mathrm{Var}[S_{0}]+\sum_{i=0}^{n-1}\mathrm{Var}[X_{i}]=0+n\cdot\tfrac{3}{2}L^{2}=\tfrac{3}{2}nL^{2},\qquad \text{sd}(S_{n})=\sqrt{\tfrac{3n}{2}}\,L .$ So after $n=400$ steps the walkers are centered at $0$ with a standard deviation of $\sqrt{600}\,L\approx 24.5L$ — not $400L$, and not even $\sqrt{400}\,L=20L$ (that was the coin's number; this step is wider). The $\sqrt{n}$ is the walk's doing; the $\sqrt{3/2}$ is the step's. ![[wb11_guide_walkers.png]] ## 5. Read the result against the sheet's Everything mirrors, with one difference. This step was built to have $\mu_{X}=0$, so the walkers' center stays at $S_{0}$ and only the band widens. The sheet's step is not balanced: its most probable event is also its largest, and all in one direction, so expect $\mathbb{E}[S_{n}]$ to be a **line with nonzero slope** — the ensemble's center *moves* at a constant rate, $n\,\mu_{X}$, while the band around it still widens like $\sqrt{n}$. The two moments answer two different questions — *where is the crowd?* and *how spread out is it?* — and on the sheet both answers depend on $n$. ## 6. Check yourself in code Everything above is two weighted sums and one multiplication by $n$. Running it is the fastest way to be sure you have the method rather than the answer — **change the two lists on the first lines to the sheet's events and probabilities** and the whole page recomputes. All four print the same numbers: ``` E[X] = 0.0 E[X^2] = 1.5 Var[X] = 1.5 (definition: 1.5 ) E[S_n] = 0.0 Var[S_n] = 600.0 sd(S_n) = 24.49489742783178 simulated mean = 0.28 simulated sd = 24.34 ``` > [!example]- Python — moments by formula, checked by simulation (run-verified) > ```python > # MATH 310 F26 - Workbook 11 companion. Moments of a step, moments of the walk. > # Worked example: steps {-2L, 0, L} with probabilities {1/4, 1/4, 1/2}, L = 1. > # Change the two lists on the first lines to do your own (they must have the same length). > import numpy as np > > x = np.array([-2.0, 0.0, 1.0]) # the event space: numbers a step can be > p = np.array([1/4, 1/4, 1/2]) # the probability function, same order > S0, n = 0.0, 400 # start and number of steps > > # --- step 1: is p a probability function? -------------------------------- > assert np.isclose(p.sum(), 1.0) and np.all(p >= 0), "p must be nonnegative and sum to 1" > > # --- step 2: the step's two moments, both routes --------------------------- > mu = np.sum(x * p) # E[X] > EX2 = np.sum(x**2 * p) # E[X^2] > var1 = EX2 - mu**2 # E[X^2] - mu^2 > var2 = np.sum((x - mu)**2 * p) # E[(X - mu)^2], the definition > print("E[X] =", mu, " E[X^2] =", EX2, " Var[X] =", var1, "(definition:", var2, ")") > > # --- step 3: the walk's moments after n steps ------------------------------ > ESn, VSn = S0 + n*mu, n*var1 > print("E[S_n] =", ESn, " Var[S_n] =", VSn, " sd(S_n) =", np.sqrt(VSn)) > > # --- step 4: check by simulation ------------------------------------------ > rng = np.random.default_rng(311) > walkers = 5000 > steps = rng.choice(x, p=p, size=(walkers, n)) > Sn = S0 + steps.sum(axis=1) > print("simulated mean =", round(Sn.mean(), 2), " simulated sd =", round(Sn.std(), 2)) > ``` > [!example]- MATLAB — moments by formula, checked by simulation > ```matlab > % MATH 310 F26 - Workbook 11 companion. Moments of a step, moments of the walk. > % Worked example: steps {-2L, 0, L} with probabilities {1/4, 1/4, 1/2}, L = 1. > x = [-2 0 1]; % the event space > p = [1/4 1/4 1/2]; % the probability function, same order > S0 = 0; n = 400; > > % --- step 1: is p a probability function? > assert(abs(sum(p) - 1) < 1e-12 && all(p >= 0), 'p must be nonnegative and sum to 1'); > > % --- step 2: the step's two moments, both routes > mu = sum(x .* p); > EX2 = sum(x.^2 .* p); > var1 = EX2 - mu^2; > var2 = sum((x - mu).^2 .* p); > fprintf('E[X] = %g E[X^2] = %g Var[X] = %g (definition: %g)\n', mu, EX2, var1, var2); > > % --- step 3: the walk's moments after n steps > ESn = S0 + n*mu; VSn = n*var1; > fprintf('E[S_n] = %g Var[S_n] = %g sd(S_n) = %g\n', ESn, VSn, sqrt(VSn)); > > % --- step 4: check by simulation > rng(311); walkers = 5000; > idx = randsample(numel(x), walkers*n, true, p); % Statistics Toolbox; see gotchas > steps = reshape(x(idx), walkers, n); > Sn = S0 + sum(steps, 2); > fprintf('simulated mean = %.2f simulated sd = %.2f\n', mean(Sn), std(Sn)); > ``` > [!example]- R — moments by formula, checked by simulation > ```r > # MATH 310 F26 - Workbook 11 companion. Moments of a step, moments of the walk. > # Worked example: steps {-2L, 0, L} with probabilities {1/4, 1/4, 1/2}, L = 1. > x <- c(-2, 0, 1) # the event space > p <- c(1/4, 1/4, 1/2) # the probability function, same order > S0 <- 0; n <- 400 > > # --- step 1: is p a probability function? > stopifnot(abs(sum(p) - 1) < 1e-12, all(p >= 0)) > > # --- step 2: the step's two moments, both routes > mu <- sum(x * p) > EX2 <- sum(x^2 * p) > var1 <- EX2 - mu^2 > var2 <- sum((x - mu)^2 * p) > cat("E[X] =", mu, " E[X^2] =", EX2, " Var[X] =", var1, "(definition:", var2, ")\n") > > # --- step 3: the walk's moments after n steps > ESn <- S0 + n*mu; VSn <- n*var1 > cat("E[S_n] =", ESn, " Var[S_n] =", VSn, " sd(S_n) =", sqrt(VSn), "\n") > > # --- step 4: check by simulation > set.seed(311); walkers <- 5000 > steps <- matrix(sample(x, walkers*n, replace = TRUE, prob = p), nrow = walkers) > Sn <- S0 + rowSums(steps) > cat("simulated mean =", round(mean(Sn), 2), " simulated sd =", round(sd(Sn), 2), "\n") > ``` > [!example]- Mathematica — moments by formula (exact), checked by simulation > ```mathematica > (* MATH 310 F26 - Workbook 11 companion. Moments of a step, moments of the walk. *) > (* Worked example: steps {-2L, 0, L} with probabilities {1/4, 1/4, 1/2}, L = 1. *) > x = {-2, 0, 1}; (* the event space *) > p = {1/4, 1/4, 1/2}; (* the probability function, same order *) > S0 = 0; n = 400; > > (* --- step 1: is p a probability function? *) > If[Total[p] != 1 || Min[p] < 0, Print["p must be nonnegative and sum to 1"]; Abort[]]; > > (* --- step 2: the step's two moments, both routes; exact arithmetic *) > mu = x . p; > EX2 = (x^2) . p; > var1 = EX2 - mu^2; > var2 = ((x - mu)^2) . p; > Print["E[X] = ", mu, " E[X^2] = ", EX2, " Var[X] = ", var1, " (definition: ", var2, ")"]; > > (* --- step 3: the walk's moments after n steps *) > ESn = S0 + n mu; VSn = n var1; > Print["E[S_n] = ", ESn, " Var[S_n] = ", VSn, " sd(S_n) = ", Sqrt[VSn], " = ", N[Sqrt[VSn]]]; > > (* --- step 4: check by simulation *) > SeedRandom[311]; walkers = 5000; > steps = RandomChoice[p -> x, {walkers, n}]; > Sn = S0 + Total[steps, {2}]; > Print["simulated mean = ", N[Mean[Sn], 3], " simulated sd = ", N[StandardDeviation[Sn], 4]]; > ``` > [!note]- Language gotchas worth knowing before you run these > - **Simulated numbers differ by language.** The formula lines agree exactly; the simulation lines agree only to about $\pm 0.5$ on the mean and $\pm 0.3$ on the sd, because each language's random generator draws a different sample even at the "same" seed. That scatter *is* the point of §4 — it is the $\text{sd}(S_{n})/\sqrt{\text{walkers}}\approx 0.35$ standard error of a 5000-walker average. > - **MATLAB** — `randsample` with weights needs the Statistics and Machine Learning Toolbox. Without it: `idx = sum(rand(walkers*n,1) > cumsum(p), 2) + 1;` does the same inverse-transform draw in one line. > - **R** — `sample(x, ..., prob = p)` normalizes `prob` for you, which is convenient and dangerous: a mis-copied probability that sums to $0.9$ runs silently. The `stopifnot` line is there to catch it. > - **Mathematica** — keep the probabilities as exact fractions and the moments come out exact (`3/2`, `600`, `10 Sqrt[6]`); `N[...]` only where a decimal is wanted. `RandomChoice[p -> x, {m, n}]` draws an $m\times n$ array directly. > - Source files live in `Workbook/code/wb11_guide/`. --- ## Before you hand it in - [ ] Item 1 — did you say **where independence was used**? It is needed exactly once (variance of the sum), and nowhere in the expectation line. - [ ] Item 1 — did you say why $\mathrm{Var}[S_{0}]=0$, rather than just dropping it? - [ ] Item 2 — did you check that the three probabilities **sum to 1** before computing anything? - [ ] Item 2 — do your step moments carry units of $L$ and $L^{2}$, and the walk's moments a factor of $n$ each? Is $\mathrm{Var}[X]$ **positive**? - [ ] Item 2 — if you computed $\mathrm{Var}[X]$ by the shortcut, does the definition $\mathbb{E}[(X-\mu_{X})^{2}]$ give the same number? (On the sheet $\mu_{X}\neq 0$, so this is a real check.) > [!success]- Numbers checked in one sandbox run > Exact arithmetic (sympy): $\mathbb{E}[X]=0$, $\mathbb{E}[X^{2}]=\tfrac{3}{2}L^{2}$, $\mathrm{Var}[X]=\tfrac{3}{2}L^{2}$ by both routes, $\text{sd}(S_{n})=\tfrac{\sqrt{6}}{2}L\sqrt{n}$. Simulation (5000 walkers, seed 311): at $n=100$ mean $-0.17$ and sd $12.34$ against $0$ and $12.25$; at $n=400$ mean $0.28$ and sd $24.34$ against $0$ and $24.49$, with $95.7\%$ of walkers inside $\pm 2\,\text{sd}$. The sheet's step was run the same way, and its formula and simulation agree to the same tolerance — those numbers stay off this page.