Random Variables & Expectation

Every number you ever read off a quantum computer is an estimate of an expectation value from a finite number of repetitions. This lesson builds the machinery — expectation, variance, concentration — that tells you exactly how good that estimate is, and how many shots you must pay for.

Learning Objectives

By the end of this lesson you will be able to:

1. Define discrete and continuous random variables and their PMF/PDF/CDF, and compute expectation and variance from each.
2. Use linearity of expectation and the variance of a sum to analyze estimators.
3. Identify and parameterize the Bernoulli, Binomial, Geometric, and Gaussian distributions and state their means and variances.
4. State the Law of Large Numbers and the Central Limit Theorem and explain the $1/\sqrt{M}$ standard-error scaling of a sample mean.
5. Apply Markov, Chebyshev, and Hoeffding inequalities to bound deviation probabilities and derive a shot count for a target confidence.
6. Simulate sample-mean convergence in NumPy and verify the $1/\sqrt{M}$ error scaling empirically.

Intuition

A random variable is a number attached to each outcome of an experiment — the measurement of the random world. Roll two dice; the sum is a random variable. Run a circuit and assign $+1$ to outcome $0$ and $-1$ to outcome $1$; that $\pm1$ reading is a random variable, and its expectation value is precisely $\langle Z\rangle$, the quantity variational algorithms minimize.

Two questions dominate everything downstream:

• Where is it centered? The expectation $\mathbb E[X]$ — the long-run average.
• How much does it wobble? The variance $\mathrm{Var}(X)$ — the spread around the center.

The punchline of the whole lesson is this. You cannot read $\mathbb E[X]$ off a quantum computer directly; you can only sample $X$ a finite number $M$ of times ("shots") and average. That sample average is itself random. The Law of Large Numbers says it converges to $\mathbb E[X]$; the Central Limit Theorem says its fluctuations shrink like $1/\sqrt M$; and concentration inequalities (Hoeffding) turn that into a hard promise: "with probability $\ge 1-\delta$, my estimate is within $\varepsilon$ of the truth, provided $M \ge \dots$". That inequality is, quite literally, the cost model for running on a QPU.

Theory

Random variables, PMF, PDF, CDF

Given a probability space $(\Omega, \mathcal F, \mathbb P)$, a random variable is a (measurable) function $X : \Omega \to \mathbb R$. Measurability means $\{\omega : X(\omega) \le x\} \in \mathcal F$ for every $x$, so we may assign it a probability. The cumulative distribution function (CDF) is

non-decreasing, right-continuous, with $F_X(-\infty)=0$, $F_X(+\infty)=1$.

A discrete RV takes values in a countable set; its probability mass function (PMF) is $p_X(x) = \mathbb P(X = x)$, with $p_X(x) \ge 0$ and $\sum_x p_X(x) = 1$.

A continuous RV has a probability density function (PDF) $f_X \ge 0$ with $\int_{-\infty}^{\infty} f_X(x)\,dx = 1$ and $\mathbb P(X \in [a,b]) = \int_a^b f_X(x)\,dx$. Note $f_X(x)$ is a density, not a probability — it can exceed $1$; only its integral over a set is a probability. The CDF and PDF are linked by $f_X = F_X'$ (where the derivative exists).

Expectation

The expectation (mean) of $X$ is its probability-weighted average:

when the sum/integral converges absolutely. For any (measurable) function $g$, the law of the unconscious statistician gives $\mathbb E[g(X)] = \sum_x g(x)p_X(x)$ — you do not need the distribution of $g(X)$, just that of $X$.

Quantum tie-in. For a Pauli-$Z$ measurement with outcomes $\pm1$, $\langle Z\rangle = \mathbb E[\text{reading}] = (+1)p_0 + (-1)p_1 = p_0 - p_1$. Estimating$\langle Z\rangle$ on hardware is estimating an expectation from samples. We meet $\langle A\rangle = \langle\psi|A|\psi\rangle$ formally in Term 1.3.

Linearity of expectation

For any random variables $X, Y$ (independent or not) and constants $a, b$,

Derivation (discrete, finite $\Omega$). Expectation can be written as a sum over outcomes, $\mathbb E[X] = \sum_{\omega} X(\omega)\,\mathbb P(\{\omega\})$. Then

The power of linearity is that it needs no independence — it is the single most useful identity in applied probability.

Variance and standard deviation

The variance measures spread about the mean:

where the second form follows by expanding the square and using linearity: $\mathbb E[(X-\mu)^2] = \mathbb E[X^2] - 2\mu\mathbb E[X] + \mu^2 = \mathbb E[X^2] - \mu^2$ with $\mu = \mathbb E[X]$. The standard deviation is $\sigma_X = \sqrt{\mathrm{Var}(X)}$, in the same units as $X$. Scaling: $\mathrm{Var}(aX+b) = a^2\,\mathrm{Var}(X)$ (shifts don't change spread; scales square).

For the sum of random variables,

When the $X_i$ are pairwise uncorrelated (in particular, independent), the covariance terms vanish and variances add: $\mathrm{Var}(\sum_i X_i) = \sum_i \mathrm{Var}(X_i)$. This single fact drives the $1/\sqrt M$ scaling below.

Key distributions

Bernoulli variance derivation. $X^2 = X$ for a $0/1$ variable, so $\mathbb E[X^2] = \mathbb E[X] = p$and$\mathrm{Var}(X) = p - p^2 = p(1-p)$, maximized at$p=\tfrac12$ (a fair coin / an equal superposition is the noisiest single bit). A Binomial$(n,p)$ is a sum of $n$ independent Bernoulli$(p)$, so by linearity and additivity of variance its mean is $np$ and variance $np(1-p)$ — no binomial-coefficient sums required.

Law of Large Numbers (LLN)

Let $X_1, X_2, \dots$ be i.i.d. with mean $\mu = \mathbb E[X_i]$ and finite variance $\sigma^2$. Define the sample mean $\bar X_M = \frac1M\sum_{i=1}^M X_i$. The (weak) law of large numbers states that for every $\varepsilon > 0$,

Derivation via Chebyshev. By linearity, $\mathbb E[\bar X_M] = \mu$. By additivity of variance for independent terms,

Chebyshev's inequality (below) gives $\mathbb P(|\bar X_M - \mu| \ge \varepsilon) \le \sigma^2/(M\varepsilon^2) \to 0$.$\blacksquare$ This is why averaging more shots works.

The $1/\sqrt M$ standard error — derived

The line $\mathrm{Var}(\bar X_M) = \sigma^2/M$ is the most important formula in this whole course for practical work. The standard error of the sample mean — the standard deviation of the estimator — is its square root:

So to halve your statistical error you must quadruple your shots. To estimate a Pauli expectation $\langle Z\rangle$ with outcomes $\pm1$, the per-shot variance is $\sigma^2 = 1 - \langle Z\rangle^2 \le 1$, so$\mathrm{SE} \le 1/\sqrt M$. This$1/\sqrt M$ wall is fundamental: it governs runtime and dollar cost of every expectation-value estimation on a QPU, and it is the reason variational algorithms are shot-hungry.

Central Limit Theorem (CLT)

The LLN says $\bar X_M \to \mu$; the CLT says how the fluctuations are shaped. For i.i.d. $X_i$ with mean $\mu$ and finite variance $\sigma^2$, the standardized sample mean converges in distribution to a standard Gaussian:

Equivalently, $\bar X_M \approx \mathcal N(\mu, \sigma^2/M)$ for large $M$. Two consequences we use constantly: (i) the error bars on a sampled expectation are Gaussian, so a $\pm 1.96\,\sigma/\sqrt M$ interval is an approximate $95\%$ confidence interval; (ii) the width of that interval is $\propto 1/\sqrt M$, consistent with the standard error above.

Concentration inequalities

These bound the probability of large deviations and let us choose $M$ before running.

Markov's inequality. For a non-negative RV $Y \ge 0$ and $a > 0$,

Derivation. $a\,\mathbf 1\{Y\ge a\} \le Y$ pointwise (check both cases $Y\ge a$ and $Y<a$). Take expectations: $a\,\mathbb P(Y\ge a) \le \mathbb E[Y]$. $\blacksquare$

Chebyshev's inequality. Apply Markov to $Y = (X-\mu)^2 \ge 0$ with $a = \varepsilon^2$:

Weak (polynomial) but assumption-light — only finite variance needed.

Hoeffding's inequality. For independent $X_i$ with $X_i \in [a_i, b_i]$ almost surely, and $\bar X_M = \frac1M\sum_i X_i$ with mean $\mu = \mathbb E[\bar X_M]$,

For identically bounded variables, $X_i \in [a,b]$ with range $R = b-a$, this simplifies to the form we will use:

This is exponentially stronger than Chebyshev for bounded variables (Chernoff-type bound). It is the right tool for shot counting because measurement readings are bounded (a $\pm1$ Pauli reading has range $R = 2$).

Shot count for a target confidence (the QPU cost model). Demand $\mathbb P(|\bar X_M - \mu| \ge \varepsilon) \le \delta$. Set the Hoeffding bound equal to $\delta$ and solve for $M$:

For a $\pm1$ Pauli observable ($R=2$): $M \ge \dfrac{2}{\varepsilon^2}\ln\dfrac{2}{\delta}$. Want $\langle Z\rangle$ to $\varepsilon = 0.01$ with $99\%$ confidence ($\delta = 0.01$)? Then $M \ge \frac{2}{10^{-4}}\ln 200 \approx 2\times10^4 \times 5.298 \approx 1.06\times10^5$ shots. That number — over a hundred thousand shots for two decimal places — is exactly why estimating many expectation values is the dominant cost in variational quantum algorithms, and why shot budgeting is a first-class design concern in Term 5.

Worked Examples

Example 1 — Expectation and variance of a Pauli reading

A qubit measured in the $Z$-basis yields outcome $0$ with probability $p_0$ and $1$ with probability $p_1 = 1-p_0$. Assign the observable value $z = +1$ to outcome $0$ and $z = -1$ to outcome $1$. Compute $\mathbb E[z]$ and $\mathrm{Var}(z)$ in terms of $\langle Z\rangle$.

Since $z^2 = 1$ always, $\mathbb E[z^2] = 1$, hence

The per-shot variance is largest ($=1$) when $\langle Z\rangle = 0$, i.e. $p_0 = p_1 = \tfrac12$ — the equal-superposition state is the hardest to estimate, needing the most shots. By the standard error formula, an $M$-shot estimate of $\langle Z\rangle$ has $\mathrm{SE} = \sqrt{(1-\langle Z\rangle^2)/M} \le 1/\sqrt M$.

Example 2 — How many shots for a target precision?

You want to estimate $\langle Z\rangle$ for an unknown state to within $\varepsilon = 0.02$ with $95\%$ confidence ($\delta = 0.05$). The reading is bounded in $[-1, +1]$ so $R = 2$. Use Hoeffding:

So $\sim 18{,}400$ shots guarantee (with $95\%$ confidence) the estimate is within $0.02$ — worst-case, distribution-free. The CLT gives a typical-case estimate that's often smaller: setting $1.96\,\sigma/\sqrt M = \varepsilon$ with the worst-case $\sigma = 1$ gives $M = (1.96/0.02)^2 = 9604$. Hoeffding is the conservative promise; the CLT is the realistic expectation. Engineers quote both.

Hands-on (Python)

We simulate the sample mean of a $\pm1$ Pauli reading, watch it converge to the true $\langle Z\rangle$, and confirm the empirical error scales as $1/\sqrt M$.

import numpy as np

rng = np.random.default_rng(42)

# A qubit with P(outcome 0)=p0; reading z=+1 for outcome 0, z=-1 for outcome 1.
p0 = 0.7
true_expectation = (+1) * p0 + (-1) * (1 - p0)        # <Z> = p0 - p1 = 0.4
per_shot_var      = 1 - true_expectation**2            # = 1 - 0.16 = 0.84

def sample_readings(M, rng, p0):
    """Return M samples of the +/-1 reading for a qubit with P(0)=p0."""
    bits = rng.random(M) < p0          # True (outcome 0) with prob p0
    return np.where(bits, +1.0, -1.0)  # map 0 -> +1, 1 -> -1

# Sample-mean convergence: estimate <Z> at increasing shot counts.
print(f"true <Z> = {true_expectation:.4f}\n")
print(f"{'M':>9} {'estimate':>10} {'|error|':>10} {'SE = sqrt(var/M)':>18}")
for M in (10, 100, 1_000, 10_000, 100_000, 1_000_000):
    est = sample_readings(M, rng, p0).mean()
    se  = np.sqrt(per_shot_var / M)                    # predicted standard error
    print(f"{M:>9} {est:>10.4f} {abs(est-true_expectation):>10.4f} {se:>18.5f}")

# Verify the 1/sqrt(M) scaling: estimate the EMPIRICAL standard error by repeating
# the whole experiment many times at each M and taking the std of the estimates.
# A clean 1/sqrt(M) law means error * sqrt(M) is (approximately) constant.
Ms     = np.array([16, 64, 256, 1024, 4096, 16384])
trials = 2000
emp_se = np.empty(len(Ms))
for i, M in enumerate(Ms):
    estimates = np.array([sample_readings(M, rng, p0).mean() for _ in range(trials)])
    emp_se[i] = estimates.std(ddof=1)                  # spread of the estimator

theory_se = np.sqrt(per_shot_var / Ms)
print(f"\n{'M':>7} {'empirical SE':>14} {'theory SE':>12} {'SE*sqrt(M)':>12}")
for M, e, t in zip(Ms, emp_se, theory_se):
    print(f"{M:>7} {e:>14.5f} {t:>12.5f} {e*np.sqrt(M):>12.5f}")

# The last column ~ sqrt(per_shot_var) = sqrt(0.84) ~ 0.9165 for every M,
# confirming SE ∝ 1/sqrt(M).
print(f"\nsqrt(per-shot var) = {np.sqrt(per_shot_var):.5f}  (the 1/sqrt(M) constant)")

Plot description. Plot emp_se against Ms on log–log axes: the points fall on a straight line of slope $-\tfrac12$, the signature of $1/\sqrt M$ decay. Overlaying theory_se gives a line the empirical points sit on. (To render: plt.loglog(Ms, emp_se, 'o'); plt.loglog(Ms, theory_se, '-'); plt.xlabel("shots M"); plt.ylabel("standard error").) Equivalently, the rightmost column of the table is flat at $\sqrt{0.84}\approx 0.9165$ — error times $\sqrt M$ is constant, which is the $1/\sqrt M$ law restated.

# Sanity-check the Hoeffding shot count from Example 2.
def hoeffding_shots(eps, delta, R=2.0):
    return (R**2) / (2 * eps**2) * np.log(2 / delta)

print(f"\nShots for eps=0.02, delta=0.05 (95% conf): {hoeffding_shots(0.02, 0.05):.0f}")
print(f"Shots for eps=0.01, delta=0.01 (99% conf): {hoeffding_shots(0.01, 0.01):.0f}")

Expected output (abridged; reproducible under the seed):

true <Z> = 0.4000

        M   estimate    |error|   SE = sqrt(var/M)
       10     0.0000     0.4000            0.28983
      100     0.4600     0.0600            0.09165
     1000     0.3900     0.0100            0.02898
    10000     0.4080     0.0080            0.00917
   100000     0.3977     0.0023            0.00290
  1000000     0.4005     0.0005            0.00092

      M   empirical SE    theory SE   SE*sqrt(M)
     16        0.22689      0.22913      0.90756
     64        0.11403      0.11456      0.91227
    256        0.05776      0.05728      0.92421
   1024        0.02923      0.02864      0.93545
   4096        0.01445      0.01432      0.92453
  16384        0.00692      0.00716      0.88535

sqrt(per-shot var) = 0.91652  (the 1/sqrt(M) constant)

Shots for eps=0.02, delta=0.05 (95% conf): 18444
Shots for eps=0.01, delta=0.01 (99% conf): 105966

This is the simulated version of running a circuit with shots=M on Braket and computing an expectation value from the counts — the convergence you see here is the convergence you pay for there.

Exercises

1. (Easy) Mean and variance of a die. Let $X$ be the result of a fair six-sided die. Compute $\mathbb E[X]$ and $\mathrm{Var}(X)$.

2. (Easy) Binomial via linearity. A circuit is run $n=1000$ times; each shot reads $1$ with probability $p=0.3$ independently. Let $K$ be the number of $1$s. Give $\mathbb E[K]$ and $\mathrm{Var}(K)$ without summing any binomial coefficients.

3. (Medium) Geometric mean. Shots are repeated until the first $1$ appears; each shot is $1$ with probability $p$. Let $N$ be the shot index of the first $1$. Show $\mathbb E[N] = 1/p$.

4. (Medium) Chebyshev vs. Hoeffding shot counts. You estimate the mean of a $[0,1]$-bounded reading to within $\varepsilon = 0.05$ with failure probability $\delta = 0.05$. (a) Use Chebyshev with the worst-case variance for a $[0,1]$ variable to bound $M$. (b) Use Hoeffding ($R=1$). Compare.

5. (Hard) Variance reduction by negation/antithetic pairing. Suppose you can sample a reading $X\in[-1,1]$ and also its "mirror" $X'$ with the same mean but $\mathrm{Cov}(X, X') < 0$. Show the average $\frac{X+X'}{2}$ has variance strictly less than $\frac12\mathrm{Var}(X)$, and explain why negatively correlated samples beat independent ones for fixed shot count.

6. (Hard) CLT confidence interval coverage. Simulate (in NumPy) the estimation of $\langle Z\rangle$for$p_0 = 0.6$using$M = 500$shots, repeated$10{,}000$ times. For each repetition form the $95\%$ CLT interval $\bar X \pm 1.96\,\hat\sigma/\sqrt M$ (using the sample std $\hat\sigma$). What fraction of intervals contain the true $\langle Z\rangle = 0.2$? Should it be near $0.95$?

import numpy as np
rng = np.random.default_rng(7)
p0, M, reps = 0.6, 500, 10_000
true_Z = 2*p0 - 1                      # = 0.2
covered = 0
for _ in range(reps):
    x = np.where(rng.random(M) < p0, 1.0, -1.0)
    xbar, s = x.mean(), x.std(ddof=1)
    half = 1.96 * s / np.sqrt(M)
    if xbar - half <= true_Z <= xbar + half:
        covered += 1
print(covered / reps)                  # ~0.95

Checkpoint

1. State linearity of expectation. Does it require independence? What about additivity of variance?
2. Write the standard error of a sample mean of $M$ i.i.d. samples, and explain in one sentence why halving the error costs $4\times$ the shots.
3. For a $\pm1$ Pauli reading, what is the per-shot variance in terms of $\langle Z\rangle$, and which state maximizes it?
4. Contrast what the LLN and the CLT each tell you about $\bar X_M$.
5. When is Hoeffding's bound preferable to Chebyshev's, and why is it so much tighter there?
6. Give the Hoeffding shot count $M$ to reach precision $\varepsilon$ with confidence $1-\delta$ for a $\pm1$ observable.

Further Reading

• [CT, §2.1, 3.1] Cover & Thomas — expectation, AEP, and the LLN as a warm-up to entropy.
• [NC, §2.2.5–2.2.6, Box 2.1] Nielsen & Chuang — expectation values of observables and measurement statistics.
• [Pre, Ch. 10] Preskill — sampling, estimation, and the role of shot noise in quantum experiments.
• Hoeffding's original: W. Hoeffding, "Probability inequalities for sums of bounded random variables", J. Amer. Statist. Assoc. 58 (1963) — the source of the concentration bound used here.

← Prev: Probability Spaces · Up: Term 0 · Next: Classical Information Theory →