The Standard Deviation is Standard

Variance

Variance

0.0 0.1 0.2 0.3 0.4 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5
Figure 1
0.0 0.1 0.2 0.3 0.4 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5
Figure 2
0.0 0.1 0.2 0.3 0.4 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5
Figure 3
0.0 0.1 0.2 0.3 0.4 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5
Figure 4

Centered responses: \textcolor{EF476F}{Z_i}=Y_i-\mathop{\mathrm{E}}[Y_i].

Square each distance: \begin{aligned} \textcolor{EF476F}{0.5}&\longmapsto\textcolor{118AB2}{0.25}\\ \textcolor{EF476F}{-1.5}&\longmapsto\textcolor{118AB2}{2.25}. \end{aligned}

The distribution of \textcolor{118AB2}{Z_i^2}.

Average the squared distances: \textcolor{06D6A0}{\mathop{\mathrm{\mathop{\mathrm{V}}}}[Y_i]}=\mathop{\mathrm{E}}[\textcolor{118AB2}{Z_i^2}]. The standard deviation is \mathop{\mathrm{sd}}[Y_i]=\sqrt{\mathop{\mathrm{\mathop{\mathrm{V}}}}[Y_i]}.

Spread: Quick Practice

0.0 0.1 0.2 0.3 0.4 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5

Quick Practice

  • What is the variance of …
    1. X, a binary random variable that’s one with probability \theta
    2. 2X
    3. 2X-1
    4. X + Y where Y has the same distribution as X

Interpretation

  • Square each dot’s distance from the center.
  • Then average those squared distances.

Two Draws

With replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1 2 3 4 1 2 3 4

Without replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1 2 3 4 1 2 3 4

With replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1 2 3 4 1 2 3 4

Without replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1 2 3 4 1 2 3 4

With replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1 2 3 4 1 2 3 4

Without replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1 2 3 4 1 2 3 4

With replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1/16 1 2 3 4 1 2 3 4

Without replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1 2 3 4 1 2 3 4

What happens when we select two people? Consider a population of four. Let J_1 be the first person selected and J_2 the second. Rows in these tables identify the first person; columns identify the second.

With Replacement: Joint and Marginal Distributions

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 1/16 1/16 1/16 1/16 1/4
2 1/16 1/16 1/16 1/16 1/4
3 1/16 1/16 1/16 1/16 1/4
4 1/16 1/16 1/16 1/16 1/4

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Person J1 J2
1 1/4 1/4
2 1/4 1/4
3 1/4 1/4
4 1/4 1/4

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 1/16 1/16 1/16 1/16 1/4
2 1/16 1/16 1/16 1/16 1/4
3 1/16 1/16 1/16 1/16 1/4
4 1/16 1/16 1/16 1/16 1/4

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Person J1 J2
1 1/4 1/4
2 1/4 1/4
3 1/4 1/4
4 1/4 1/4

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 1/16 1/16 1/16 1/16 1/4
2 1/16 1/16 1/16 1/16 1/4
3 1/16 1/16 1/16 1/16 1/4
4 1/16 1/16 1/16 1/16 1/4

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Person J1 J2
1 1/4 1/4
2 1/4 1/4
3 1/4 1/4
4 1/4 1/4

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 1/16 1/16 1/16 1/16 1/4
2 1/16 1/16 1/16 1/16 1/4
3 1/16 1/16 1/16 1/16 1/4
4 1/16 1/16 1/16 1/16 1/4

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Person J1 J2
1 1/4 1/4
2 1/4 1/4
3 1/4 1/4
4 1/4 1/4

The joint distributions differ. Without replacement, we cannot select the same person twice. But sum across a row or down a column: the marginal distributions are the same. Each draw is uniformly distributed over the four people.

Without Replacement: Joint and Marginal Distributions

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 0 1/12 1/12 1/12 1/4
2 1/12 0 1/12 1/12 1/4
3 1/12 1/12 0 1/12 1/4
4 1/12 1/12 1/12 0 1/4

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Person J1 J2
1 1/4 1/4
2 1/4 1/4
3 1/4 1/4
4 1/4 1/4

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 0 1/12 1/12 1/12 1/4
2 1/12 0 1/12 1/12 1/4
3 1/12 1/12 0 1/12 1/4
4 1/12 1/12 1/12 0 1/4

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Person J1 J2
1 1/4 1/4
2 1/4 1/4
3 1/4 1/4
4 1/4 1/4

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 0 1/12 1/12 1/12 1/4
2 1/12 0 1/12 1/12 1/4
3 1/12 1/12 0 1/12 1/4
4 1/12 1/12 1/12 0 1/4

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Person J1 J2
1 1/4 1/4
2 1/4 1/4
3 1/4 1/4
4 1/4 1/4

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 0 1/12 1/12 1/12 1/4
2 1/12 0 1/12 1/12 1/4
3 1/12 1/12 0 1/12 1/4
4 1/12 1/12 1/12 0 1/4

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Person J1 J2
1 1/4 1/4
2 1/4 1/4
3 1/4 1/4
4 1/4 1/4

Even the second draw without replacement is uniform. Once we know the first person, only three possibilities remain. Before we know the first person, all four are equally likely to be second.

Horizontal Slice

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 With replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 Without replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 With replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 Without replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 With replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 Without replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 With replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 Without replacement

Vertical Slice

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 With replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 Without replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 With replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 Without replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 With replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 Without replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 With replacement

1 2 3 4 0 1/16 1/12 1 2 3 4 0 1/16 1/12 P(J1, J2) 0 1/16 1/12 Without replacement

Independence: Definition and Equivalent Condition

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

J1 (first person) J2 (second person) 1 2 3 4 1 2 3 4 0.0 0.1 0.2 0.3

Each joint probability is 1/16=(1/4)(1/4), the product of its two marginal probabilities. That is independence in this picture.

Definition. Random variables Y and Z are independent if \mathop{\mathrm{E}}[f(Y)g(Z)] = \mathop{\mathrm{E}}[f(Y)]\mathop{\mathrm{E}}[g(Z)] \qqtext{for all functions $f$ and $g$} Here we work with random variables taking finitely many values.

Equivalent. Their joint distribution is the product of their marginal distributions, P(Y=y,Z=z)=P(Y=y)P(Z=z). Knowing the value of one then does not change the probabilities for the other.

Calls, Two People

0 1 1 2

1 2 1 2 P(J1, J2) 0 1/4 9/16

p J_1 J_2
1/4 1 1
1/4 1 2
1/4 2 1
1/4 2 2

Responses, Two People

0 1 1 2

0 1 0 1 P(Y1, Y2) 0 1/4 9/16

Draw the joint distribution of two draws with replacement from this population.

p Y_1 Y_2 Y_1+Y_2
1/4 0 0 0
1/4 0 1 1
1/4 1 0 1
1/4 1 1 2

What is the distribution of the sum?

1/4 1/2 1/4 0 1/4 1/2 0 1 2

Responses, Four People (0, 0, 1, 1)

0 1 1 2 3 4

0 1 0 1 P(Y1, Y2) 0 1/4 9/16

p Y_1 Y_2 Y_1+Y_2
1/4 0 0 0
1/4 0 1 1
1/4 1 0 1
1/4 1 1 2

To find the distribution of Y_1, sum over Y_2. To find the distribution of Y_2, sum over Y_1.

1/4 1/2 1/4 0 1/4 1/2 0 1 2

What is the distribution of the sum?

Responses, Four People (0, 0, 0, 1)

0 1 1 2 3 4

0 1 0 1 P(Y1, Y2) 0 1/4 9/16

p Y_1 Y_2 Y_1+Y_2
9/16 0 0 0
3/16 0 1 1
3/16 1 0 1
1/16 1 1 2

9/16 6/16 1/16 0 1/4 1/2 0 1 2

What is the distribution of the sum?

Products: With Replacement

1/4 1/4 1/4 1/4 0 1 0 1/4 1/2 0 1 0 1/4 1/2 Z (second response) Y (first response) P(Y, Z) 0 1/4 1/2 With replacement

Y Z p f(Y)g(Z)
0 0 1/4 f(0)g(0)
0 1 1/4 f(0)g(1)
1 0 1/4 f(1)g(0)
1 1 1/4 f(1)g(1)

\begin{aligned} \mathop{\mathrm{E}}[f(Y)g(Z)] &=\sum_{y=0}^1\sum_{z=0}^1 f(y)g(z)P(Y=y,Z=z)\\ &\class{fragment=0}{=\sum_{y=0}^1\sum_{z=0}^1 f(y)g(z)\textcolor{ef476f}{\frac12}\textcolor{118ab2}{\frac12}}\\ &\class{fragment=1}{=\left(\sum_{y=0}^1 f(y)\textcolor{ef476f}{\frac12}\right)\left(\sum_{z=0}^1 g(z)\textcolor{118ab2}{\frac12}\right)}\\ &\class{fragment=2}{=\mathop{\mathrm{E}}[f(Y)]\mathop{\mathrm{E}}[g(Z)].} \end{aligned}

Return to the population with one 0 and one 1. Call the first response Y and the second Z.

Each joint probability is 1/4=(1/2)(1/2): the product of its two marginal probabilities.

Products: Without Replacement

0 1/2 1/2 0 0 1 0 1/4 1/2 0 1 0 1/4 1/2 Z (second response) Y (first response) P(Y, Z) 0 1/4 1/2 Without replacement

Y Z p f(Y)g(Z)
0 0 0 f(0)g(0)
0 1 1/2 f(0)g(1)
1 0 1/2 f(1)g(0)
1 1 0 f(1)g(1)

\begin{aligned} \mathop{\mathrm{E}}[f(Y)g(Z)] &=\sum_{y=0}^1\sum_{z=0}^1 f(y)g(z)P(Y=y,Z=z)\\ &\class{fragment=0}{=\frac12 f(0)g(1)+\frac12 f(1)g(0).} \end{aligned}

P(Y=0,Z=0)=0\ne\frac14=P(Y=0)P(Z=0).

For f(y)=y and g(z)=z, \mathop{\mathrm{E}}[YZ]=0\ne\frac14=\mathop{\mathrm{E}}[Y]\mathop{\mathrm{E}}[Z].

Draw from the same two-person population without replacement. The marginals are unchanged; the joint probabilities no longer factor.

What Is Special about the Binomial?

With replacement

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 1/16 1/16 1/16 1/16 1/4
2 1/16 1/16 1/16 1/16 1/4
3 1/16 1/16 1/16 1/16 1/4
4 1/16 1/16 1/16 1/16 1/4

Without replacement

J1 J2 = 1 J2 = 2 J2 = 3 J2 = 4 Row sum
1 0 1/12 1/12 1/12 1/4
2 1/12 0 1/12 1/12 1/4
3 1/12 1/12 0 1/12 1/4
4 1/12 1/12 1/12 0 1/4

Suppose two of our four people have response zero and two have response one. Under either sampling scheme, each response is equally likely to be zero or one. The sample average is unbiased under either scheme.

But the draws with replacement are independent. In the first table, learning which row we are in leaves the second person equally likely to be any of the four. In the second table, learning the row rules someone out.

What Is Special about the Binomial?

With replacement

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

Without replacement

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

The difference survives when we look at responses. With replacement, a first response of one leaves the probability of another one at 1/2. Without replacement, it falls to 1/3: only one of the remaining three people has response one.

The binomial counts ones in independent binary draws with the same success probability. Equal individual probabilities explain the expected count; independence is the additional property. We now need to understand what it lets us do with products, because calculating spread involves squaring a sum.

One Uniform Draw

0.0 0.1 0.2 0.3 0.4 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5

Sample uniformly with replacement from y_1\ldots y_m, with population mean \mu and variance \sigma^2. Recall the calculation for a function of a uniform draw: \mathop{\mathrm{E}}[f(Y_i)]=\frac1m\sum_{j=1}^m f(y_j). Choose f(y)=(y-\mu)^2 in the squared-distance picture, \mathop{\mathrm{E}}[\textcolor{118AB2}{Z_i^2}]=\frac1m\sum_{j=1}^m(y_j-\mu)^2=\textcolor{06D6A0}{\sigma^2}.

Centered Responses

0.0 0.1 0.2 0.3 0.4 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5

The centered responses have mean zero: \begin{aligned} \mathop{\mathrm{E}}[\textcolor{EF476F}{Z_i}] &\class{fragment=1}{\overset{\texttip{\small{\text{?}}}{definition of the centered response}}{=}\mathop{\mathrm{E}}[Y_i-\mathop{\mathrm{E}}[Y_i]]}\\ &\class{fragment=2}{\overset{\texttip{\small{\text{?}}}{linearity}}{=}\mathop{\mathrm{E}}[Y_i]-\mathop{\mathrm{E}}[Y_i]=0.} \end{aligned}

Centered Products

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

For distinct draws i\ne j, independence implies \begin{aligned} \mathop{\mathrm{E}}[\textcolor{EF476F}{Z_i}\textcolor{118AB2}{Z_j}] &\class{fragment=1}{\overset{\texttip{\small{\text{?}}}{independence}}{=}\textcolor{EF476F}{\mathop{\mathrm{E}}[Z_i]}\textcolor{118AB2}{\mathop{\mathrm{E}}[Z_j]}}\\ &\class{fragment=2}{\overset{\texttip{\small{\text{?}}}{centering.}}{=}0} \end{aligned}

When i=j, the product is a square: \mathop{\mathrm{E}}[Z_i^2]=\mathop{\mathrm{\mathop{\mathrm{V}}}}[Y_i]=\sigma^2. These are the two cases we will use when we square the sample mean.

The Variance of the Sample Mean

0.0 0.1 0.2 0.3 0.4 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 2.5

\hat\mu-\mu=n^{-1}\sum_i Z_i.1 \begin{aligned} \mathop{\mathrm{\mathop{\mathrm{V}}}}[\hat\mu] &\class{fragment=1}{\overset{\texttip{\small{\text{?}}}{center}}{=}\mathop{\mathrm{E}}\left[\left(\frac1n\sum_{i=1}^n Z_i\right)^2\right]}\\ &\class{fragment=2}{\overset{\texttip{\small{\text{?}}}{square}}{=}\frac1{n^2}\mathop{\mathrm{E}}\left[\textcolor{EF476F}{\sum_{i=1}^n Z_i}\textcolor{118AB2}{\sum_{j=1}^n Z_j}\right]}\\ &\class{fragment=3}{\overset{\texttip{\small{\text{?}}}{linearity}}{=}\frac1{n^2}\textcolor{EF476F}{\sum_{i=1}^n}\textcolor{118AB2}{\sum_{j=1}^n}\mathop{\mathrm{E}}[\textcolor{EF476F}{Z_i}\textcolor{118AB2}{Z_j}]}\\ &\class{fragment=4}{\overset{\texttip{\small{\text{?}}}{equal indices give a squared centered response; distinct indices give a product with expectation zero}}{=}\frac1{n^2}\textcolor{EF476F}{\sum_{i=1}^n}\textcolor{118AB2}{\sum_{j=1}^n}\begin{cases}\sigma^2 & \textcolor{EF476F}{i}=\textcolor{118AB2}{j}\\0 & \textcolor{EF476F}{i}\ne\textcolor{118AB2}{j}\end{cases}}\\ &\class{fragment=5}{\overset{\texttip{\small{\text{?}}}{only the equal-index terms remain}}{=}\frac1{n^2}\sum_{i=1}^n\mathop{\mathrm{E}}[Z_i^2]}\\ &\class{fragment=6}{\overset{\texttip{\small{\text{?}}}{there are n equal-index terms, each with expectation equal to the population variance}}{=}\frac{n\sigma^2}{n^2}=\frac{\sigma^2}{n}.} \end{aligned}

\mathop{\mathrm{sd}}[\hat\mu]=\frac{\sigma}{\sqrt{n}}.

Return to the Sampling Picture

Code 
m.frame = 100
theta.frame = .4
population.frame = c(rep(1, 40), rep(0, 60))
n.frame = c(5, 20, 80)

sampling.distribution = function(n, mechanism) {
  if(mechanism == "With replacement") {
    counts = 0:n
    probability = dbinom(counts, n, theta.frame)
    estimate = counts/n
  } else if(mechanism == "Without replacement") {
    counts = 0:n
    probability = dhyper(counts, 40, 60, n)
    estimate = counts/n
  } else {
    estimate = sapply(1:m.frame, function(start) {
      positions = ((start - 1 + 0:(n - 1)) %% m.frame) + 1
      mean(population.frame[positions])
    })
    tab = table(estimate)
    estimate = as.numeric(names(tab))
    probability = as.numeric(tab)/m.frame
  }
  data.frame(n, mechanism, estimate, probability)
}

design.distributions = purrr::map_dfr(
  n.frame,
  function(n) purrr::map_dfr(
    c("With replacement", "Without replacement", "Random-start cycle"),
    function(mechanism) sampling.distribution(n, mechanism)
  )
)

design.dots = design.distributions |>
  mutate(dot.count=round(400*probability)) |>
  tidyr::uncount(dot.count) |>
  group_by(n, mechanism, estimate) |>
  mutate(dot.height=row_number()/400) |>
  ungroup()
Random-start cycle With replacement Without replacement n = 5 n = 20 n = 80 0 0.5 1 0 0.5 1 0 0.5 1 0.0 0.2 0.4 0.0 0.1 0.2 0.3 0.4 0.0 0.1 0.2 0.3 0.4
Figure 5: Three sample sizes by three sampling mechanisms.

What Changes across the Columns?

Random-start cycle With replacement Without replacement n = 20 0 0.5 1 0 0.5 1 0 0.5 1 0.0 0.1 0.2 0.3 0.4

Each column uses the same population. Each draw position selects a uniformly distributed person, so its mean is \mu and its variance is \sigma^2. The columns differ in how the draws occur together.

The same expansion works without independence, but we must keep the cross terms: \begin{aligned} \mathop{\mathrm{\mathop{\mathrm{V}}}}[\hat\mu] &\class{fragment=1}{=\frac1{n^2}\sum_{i=1}^n\sum_{j=1}^n\mathop{\mathrm{E}}[\textcolor{EF476F}{Z_i}\textcolor{118AB2}{Z_j}]}\\ &\class{fragment=2}{=\frac1{n^2}\left\{n\sigma^2+\sum_{i\ne j}\mathop{\mathrm{E}}[\textcolor{EF476F}{Z_i}\textcolor{118AB2}{Z_j}]\right\}.} \end{aligned}

With replacement

n = 5 n = 20 n = 80 0 0.5 1 0 0.5 1 0 0.5 1 0.0 0.1 0.2 0.3 0.4 0.0 0.1 0.2 0.3 0.4 0.0 0.2 0.4

With replacement: independent draws make the cross terms zero. Quadrupling the sample size from 5 to 20, then from 20 to 80, halves the standard deviation each time.

Without replacement

With replacement

n = 20 0 0.5 1 0.0 0.1 0.2 0.3 0.4

Without replacement

n = 20 0 0.5 1 0.0 0.1 0.2 0.3 0.4

Which step is different? And how?

Solution

The step that used independence to replace the distinct-index terms by zero. The without-replacement distribution is narrower, so their contribution has to be negative.

Random-start cycle

n = 5 n = 20 n = 80 0 0.5 1 0 0.5 1 0 0.5 1 0.0 0.1 0.2 0.3 0.4 0.0 0.1 0.2 0.3 0.4 0.0 0.2 0.4

Random-start cycle: consecutive people in this ordered population often share the same response. The aggregate cross-term contribution is positive at these sample sizes, so the average remains more variable than with independent draws.

The cycle does not keep the same spread at every sample size. Sampling all 100 people leaves no variation. Here, the comparison is with the independent draws at the same sample sizes.

A Non-Binary Expectation

0.0 0.2 0.3 0.5 0 10 30
Figure 6

Exercise 1 (A Non-Binary Expectation)  

A random payment R is \textcolor{EF476F}{0} with probability \textcolor{EF476F}{.5}, \textcolor{118AB2}{10} with probability \textcolor{118AB2}{.3}, and \textcolor{06D6A0}{30} with probability \textcolor{06D6A0}{.2}.

  1. Calculate \mathop{\mathrm{E}}[R] from the probability-weighted average.
  2. Simulate 10,000 independent copies R_1 \ldots R_{10000} and compare their sample mean with your calculation.
  3. The variance of an average of n independent copies is the variance of one copy divided by n. Use that fact to explain why the simulation should get closer to your calculation as the number of copies grows, without naming the distribution of R.
  4. Calculate the variance of R. What are the expectation and standard deviation of the average of n independent copies?

A Non-Binary Expectation: Solution

0.0 0.2 0.3 0.5 0 10 30
Figure 7

Solution

The probability-weighted average is \mathop{\mathrm{E}}[R]=\textcolor{EF476F}{0(.5)}+\textcolor{118AB2}{10(.3)}+\textcolor{06D6A0}{30(.2)}=9. One simulation is mean(sample(c(0,10,30), 10000, replace=TRUE, prob=c(.5,.3,.2))). The sample mean averages many independent copies whose common expectation is 9.

For independent copies R_1\ldots R_n, \begin{aligned} \mathop{\mathrm{\mathop{\mathrm{V}}}}[R]&=\textcolor{EF476F}{.5(0-9)^2}+\textcolor{118AB2}{.3(10-9)^2}+\textcolor{06D6A0}{.2(30-9)^2}=129,\\ \mathop{\mathrm{E}}\sb*{\frac1n\sum_{i=1}^nR_i}&=9,\\ \mathop{\mathrm{sd}}\sb*{\frac1n\sum_{i=1}^nR_i}&=\sqrt{\frac{129}{n}}. \end{aligned}

Binary Variance

0.00 0.25 0.50 0.0 0.5 1.0
Figure 8

The picture uses \theta=1/2. For a binary Y that equals one with probability \theta, its mean is \theta, and direct substitution into the definition implies \mathop{\mathrm{\mathop{\mathrm{V}}}}[Y] =\textcolor{EF476F}{\theta(1-\theta)^2}+\textcolor{118AB2}{(1-\theta)\theta^2} =\theta(1-\theta).

For a binary population, \textcolor{06D6A0}{\mu}=\theta and \sigma^2=\theta(1-\theta).

A Binary Application

0.00 0.01 0.02 0.03 0.60 0.65 0.70 0.75 0.80
Figure 9

This explains a picture we already know. The three Binomial sampling distributions above have the same sample size and success probabilities \theta=\textcolor{EF476F}{.68},\textcolor{118AB2}{.70},\textcolor{06D6A0}{.72}. Their centers move with \theta; their widths are governed by \sqrt{\theta(1-\theta)/n}.

Sampling without Replacement

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1 2 3 4 1 2 3 4
Figure 10

When we sample without replacement, the calculation is almost the same. Centering, squaring, and linearity go through unchanged. The difference is in the distinct-index terms.

When j=i, we still get \mathop{\mathrm{\mathop{\mathrm{V}}}}[Y_i] = \theta(1-\theta).

When j \neq i, we can no longer factor the expectation—our observations aren’t independent. Instead, we get a small negative term. Why negative? Because if your first call reached a 1, there’s one fewer 1 in the population, so your second call is slightly less likely to reach a 1. This negative covariance is why sampling without replacement gives us better precision.

Covariance

1 2 3 4 1 2 3 4 P(J1,J2) 0 1/16 1/12

The cross-term we have already been calculating has a name. The covariance of X and Y is the mean of the product after centering both variables: \mathop{\mathrm{Cov}}(X,Y)=\mathop{\mathrm{E}}[(X-\mathop{\mathrm{E}}X)(Y-\mathop{\mathrm{E}}Y)]. That is the whole move: center and multiply. When we center and square out a sum, the diagonal terms are variances and the off-diagonal terms are covariances. Under independence the covariances vanish. Without replacement they need not vanish.

The covariance works out to \mathop{\mathrm{E}}[Z_iZ_j] = -\frac{\theta(1-\theta)}{m-1} when j \neq i.

Finishing the Calculation

1/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 J2 margins J1 margins 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1/12 1/12 1/12 1/12 0 1 2 3 4 1 2 3 4
Figure 11

With this in hand, we can finish the calculation. There are n diagonal terms (when j=i) and n(n-1) off-diagonal terms (when j \neq i).

What do all n^2 terms sum to?

\begin{aligned} \mathop{\mathrm{\mathop{\mathrm{V}}}}[\hat\theta] &\class{fragment=1}{\overset{\texttip{\small{\text{?}}}{one-draw variance and covariance}}{=} \frac{1}{n^2} \cb*{ n \cdot \theta(1-\theta) + n(n-1) \cdot \cb*{-\frac{\theta(1-\theta)}{m-1}} }}\\ &\class{fragment=2}{\overset{\texttip{\small{\text{?}}}{simplify}}{=} \frac{\theta(1-\theta)}{n} \cb*{1 - \frac{n-1}{m-1}} = \frac{\theta(1-\theta)}{n} \times \frac{m-n}{m-1}} \end{aligned}

Markov’s Inequality and Concentration

Recall: Indicators

1 0.1 0.2 0.3 0 1 2 3 4 5 6
Figure 12

The indicator is 1 for the points inside the blue region and 0 for the points outside.

The mean of the indicators is the fraction of points inside: \frac{0+0+1+1+1}{5}=\frac35.

Recall: Expectations of Indicators

The expected value of any binary random variable Z is just the probability that it’s one: \mathop{\mathrm{E}}[Z]=0P(Z=0)+1P(Z=1)=P(Z=1).

For the indicator 1_{\ge t}(X), this means \mathop{\mathrm{E}}[1_{\ge t}(X)]=P(X\ge t).

How Much Can Lie Above t?

1 0.1 0.2 0.3 0 1 2 3 4 5 6
Figure 13

Suppose X\ge0 and we know \mathop{\mathrm{E}}[X]. For t>0, how large can P(X\ge t) be?

Bound the Indicator

1 0.1 0.2 0.3 0 1 2 3 4 5 6
Figure 14
1 0.1 0.2 0.3 0 1 2 3 4 5 6
Figure 15

The indicator counts the tail. Can we bound it using a multiple of x?

For x\ge0, the ramp u_t(x)=x/t stays above the indicator: 1_{\ge t}(x)\le u_t(x).

The Same Values as Heights

0.0 0.5 1.0 1.5 0 1 2 3 4 5 6
Figure 16
0.0 0.5 1.0 1.5 0 1 2 3 4 5 6
Figure 17

The horizontal axis still shows x. Height now shows the value represented by shade and dot area.

For every nonnegative x, \begin{aligned} x\ge t &: \quad 1_{\ge t}(x)=1\le x/t,\\ 0\le x<t &: \quad 1_{\ge t}(x)=0\le x/t. \end{aligned}

Markov’s Inequality

1 0.1 0.2 0.3 0 1 2 3 4 5 6
Figure 18
1 0.1 0.2 0.3 0 1 2 3 4 5 6
Figure 19
1 0.1 0.2 0.3 0 1 2 3 4 5 6
Figure 20

For every nonnegative random variable X and t>0, \begin{aligned} P(X\ge t) &\class{fragment=0}{\overset{\texttip{\small{\text{?}}}{probability as expectation}}{=}\mathop{\mathrm{E}}[1_{\ge t}(X)]}\\ &\class{fragment=1}{\overset{\texttip{\small{\text{?}}}{the ramp bounds the indicator}}{\le}\mathop{\mathrm{E}}[u_t(X)]}\\ &\class{fragment=2}{\overset{\texttip{\small{\text{?}}}{the bounding ramp}}{=}\mathop{\mathrm{E}}\sb*{\frac Xt}}\\ &\class{fragment=3}{\overset{\texttip{\small{\text{?}}}{linearity}}{=}\frac{\mathop{\mathrm{E}}[X]}t.} \end{aligned}

Why Must X Be Nonnegative?

-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 observations Z 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 Z proportion
Figure 21

Draw a distribution showing why Markov’s inequality needs X\ge0.

For this centered variable Z, \mathop{\mathrm{E}}[Z]=0,\qquad P(Z\ge1)=\frac{36}{240}>0=\frac{\mathop{\mathrm{E}}[Z]}1.

A Hint for Chebyshev’s Inequality

-1.5 -1 -t -0.5 0 0.5 t 1 1.5 2 2.5 observations Z 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -t -0.5 0 0.5 t 1 1.5 2 2.5 Z proportion
Figure 22
-1.5 -1 -0.5 0 0.5 t 1 1.5 2 2.5 observations |Z| 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -0.5 0 0.5 t 1 1.5 2 2.5 |Z| proportion
Figure 23
-1.5 -1 -0.5 0 t² 1 1.5 2 2.5 observations Z² 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -0.5 0 t² 1 1.5 2 2.5 Z² proportion
Figure 24

Let Z=X-\mathop{\mathrm{E}}[X]. How can we use Markov to bound P(|Z|\ge t)?

Fold the left mass onto the right. Keep both contributions in the stack.

Squaring moves the cutoff from t to t^2. The events |Z|\ge t and Z^2\ge t^2 select exactly the same observations.

Chebyshev’s Inequality: Your Turn

-t 0 t 2 observations Z 0.0 0.1 0.2 0.3 0.4 -t 0 t 2 Z proportion -1 0 t 2 observations |Z| 0.0 0.1 0.2 0.3 0.4 -1 0 t 2 |Z| proportion -1 0 t² 1 2 observations Z² 0.0 0.1 0.2 0.3 0.4 -1 0 t² 1 2 Z² proportion
Figure 25

For a random variable X with finite variance and t>0, prove P(|X-\mathop{\mathrm{E}}[X]|\ge t)\le\frac{\mathop{\mathrm{\mathop{\mathrm{V}}}}[X]}{t^2}.

Chebyshev’s Inequality: Visual Solution

-1.5 -1 -t -0.5 0 0.5 t 1 1.5 2 2.5 observations Z 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -t -0.5 0 0.5 t 1 1.5 2 2.5 Z proportion
Figure 26
-1.5 -1 -0.5 0 0.5 t 1 1.5 2 2.5 observations |Z| 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -0.5 0 0.5 t 1 1.5 2 2.5 |Z| proportion
Figure 27
-1.5 -1 -0.5 0 t² 1 1.5 2 2.5 observations Z² 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -0.5 0 t² 1 1.5 2 2.5 Z² proportion
Figure 28
-1.5 -1 -0.5 0 t² 1 1.5 2 2.5 observations Z² 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -0.5 0 t² 1 1.5 2 2.5 Z² proportion
Figure 29
-1.5 -1 -0.5 0 t² 1 1.5 2 2.5 observations Z² 0.0 0.1 0.2 0.3 0.4 -1.5 -1 -0.5 0 t² 1 1.5 2 2.5 Z² proportion
Figure 30

Write Z=X-\mathop{\mathrm{E}}[X]. For t>0, \begin{aligned} P(Z\le-t\text{ or }Z\ge t) &\class{fragment=0}{=P(|Z|\ge t)}\\ &\class{fragment=1}{=P(Z^2\ge t^2)}\\ &\class{fragment=2}{=\mathop{\mathrm{E}}[1_{\ge t^2}(Z^2)]}\\ &\class{fragment=3}{\le\mathop{\mathrm{E}}\sb*{\frac{Z^2}{t^2}}}\\ &\class{fragment=4}{=\frac{\mathop{\mathrm{E}}[Z^2]}{t^2}=\frac{\mathop{\mathrm{\mathop{\mathrm{V}}}}[X]}{t^2}.} \end{aligned}

The Standard Deviation is Standard

-k mean k

Write \sigma=\mathop{\mathrm{sd}}(X). If \sigma>0, then for every k>0, Chebyshev’s inequality says P(|X-\mathop{\mathrm{E}}X|\ge k\sigma)\le \frac1{k^2}. If \sigma=0, then X=\mathop{\mathrm{E}}X with probability one, so there is no positive departure from the mean to bound.

The statement contains no density, no named distribution, and no approximation. Two standard deviations means a tail probability no larger than 1/4 for every distribution with finite variance. Four standard deviations means no larger than 1/16. The exact tail probability changes from one distribution to another; the guarantee does not.

Two Moments Give You an Interval

θ − t σ θ θ + t σ

Exercise 2  

Let \hat\theta be an unbiased estimator of \theta with standard deviation \sigma. By applying Markov’s inequality to |\hat\theta-\theta|^2, find a lower bound on P(|\hat\theta-\theta| \le t\sigma) as a function of t. For what choice of t is this bound equal to .95? Explain how you can use this to get an interval estimate \hat\theta \pm t\sigma with a coverage probability of at least 95%.

From Upper Bounds to Lower Bounds

θ − t σ θ θ + t σ

From Upper Bounds to Lower Bounds.

If you have an upper bound on P(X > \epsilon), then you have a lower bound on P(X \le \epsilon). P(X \le \epsilon)=1-P(X > \epsilon) because X > \epsilon if and only if it is not the case that X \le \epsilon, so if P(X > \epsilon) \le u, then P(X \le \epsilon) = 1-P(X > \epsilon) \ge 1-u. And if you’re troubled that Markov’s inequality says \ge instead of >, don’t be. You have a bound on P(X > \epsilon) too. P(X > \epsilon) \le P(X\ge \epsilon) because X \ge \epsilon whenever X > \epsilon.

Bounding the Error

θ − t σ θ θ + t σ

Solution

For t>0 and \sigma>0, apply Markov’s inequality to |\hat\theta-\theta|^2, which has mean-square \sigma^2 because \hat\theta is unbiased:

P(|\hat\theta-\theta|^2 \ge (t\sigma)^2) \le \frac{\mathop{\mathrm{E}}[(\hat\theta-\theta)^2]}{(t\sigma)^2} = \frac{\sigma^2}{(t\sigma)^2} = \frac{1}{t^2}. The probability that |\hat\theta-\theta| > t\sigma is also no larger than 1/t^2 because this happens only if |\hat\theta-\theta|^2 \ge (t\sigma)^2. And it follows that the probability that |\hat\theta-\theta| \le t\sigma is at least 1-1/t^2.

A Guaranteed 95% Interval

θ − t σ θ θ + t σ

Solution

To find the value of t that makes this lower bound equal to .95, we solve 1-1/t^2=.95 to find t=\sqrt{1/(1-.95)}= \sqrt{20} \approx 4.5. And because \theta \in [\hat\theta - t\sigma, \hat\theta + t\sigma] if (and only if) |\hat\theta-\theta| \le t\sigma, it follows that this interval has a coverage probability of at least .95.

If \sigma=0, unbiasedness implies \hat\theta=\theta with probability one.

Binomial: Exact and Guaranteed

Code 
# Model parameters (explicit; change them here). Hypergeometric population
# m chosen so its proportion matches theta (m*theta must be an integer
# count); FPC = (m-n)/(m-1) enters its actual variance.
intcomp.n = 625
intcomp.theta = 0.7
intcomp.m = 2000
intcomp.samples.binom = with_seed(
  rbinom(10000, intcomp.n, intcomp.theta)/intcomp.n)
intcomp.samples.hyper = with_seed(
  rhyper(10000, intcomp.m*intcomp.theta,
         intcomp.m*(1-intcomp.theta), intcomp.n)/intcomp.n)
# Actual PMFs and true SDs.
intcomp.pmf.binom = dbinom(0:intcomp.n, intcomp.n, intcomp.theta)
intcomp.pmf.hyper = dhyper(0:intcomp.n, intcomp.m*intcomp.theta,
                           intcomp.m*(1-intcomp.theta), intcomp.n)
intcomp.sigma.binom = sqrt(intcomp.theta*(1-intcomp.theta)/intcomp.n)
intcomp.sigma.hyper =
  sqrt(intcomp.theta*(1-intcomp.theta)/intcomp.n *
       (intcomp.m-intcomp.n)/(intcomp.m-1))
# Exact central-95 half-widths from SHARED width_binom/width_hyper only.
intcomp.hw.exact.binom = width_binom(intcomp.theta, intcomp.n)/2
intcomp.hw.exact.hyper = width_hyper(intcomp.theta, intcomp.n, intcomp.m)/2
# Chebyshev 95% half-widths: 1/t^2 = .05 gives t = sqrt(20); each estimator
# uses its ACTUAL true model sigma, never a sample plug-in.
intcomp.hw.cheb.binom = sqrt(20)*intcomp.sigma.binom
intcomp.hw.cheb.hyper = sqrt(20)*intcomp.sigma.hyper
# Measured integer-support coverage of those widths (measurement only: sums
# the pmf over counts inside each interval; finds no widths).
intcomp.measured.coverage = function(pmf, hw) {
  k = 0:intcomp.n
  inside = k >= ceiling(intcomp.n*(intcomp.theta - hw)) &
           k <= floor(intcomp.n*(intcomp.theta + hw))
  sum(pmf[inside])
}
intcomp.cov.exact.binom = intcomp.measured.coverage(intcomp.pmf.binom,
                                                    intcomp.hw.exact.binom)
intcomp.cov.exact.hyper = intcomp.measured.coverage(intcomp.pmf.hyper,
                                                    intcomp.hw.exact.hyper)
intcomp.cov.cheb.binom = intcomp.measured.coverage(intcomp.pmf.binom,
                                                   intcomp.hw.cheb.binom)
intcomp.cov.cheb.hyper = intcomp.measured.coverage(intcomp.pmf.hyper,
                                                   intcomp.hw.cheb.hyper)
0.60 0.65 0.70 0.75 0.80
Figure 31

Each dot is one sample mean. The paired intervals use that same sample: exact central 95% and guaranteed Chebyshev 95%. The green line is \textcolor{00FF00}{\theta}.

Without Replacement: Exact and Guaranteed

0.60 0.65 0.70 0.75 0.80
Figure 32

The same comparison without replacement: exact central 95% and guaranteed Chebyshev 95%, using this estimator’s variance.

Independence was used in the variance calculation, not in the probability-bound argument.

Algebra Reference

Squaring Sums

\cb*{\sum_{i=1}^n Z_i}^2 = \sum_{i=1}^n \sum_{j=1}^n Z_i Z_j

This is a generalization of the identity (a+b)^2 = a^2 + 2ab + b^2 to more terms. You may be so used to that you don’t even think about what’s really happening. Here’s a version where I’m very explicit: it’s a product of two copies of (a+b), one pink and one teal.

(a+b)^2 = \textcolor{EF476F}{(a+b)}\textcolor{118AB2}{(a+b)} = \textcolor{EF476F}{a}\textcolor{118AB2}{a} + \textcolor{EF476F}{a}\textcolor{118AB2}{b} + \textcolor{EF476F}{b}\textcolor{118AB2}{a} + \textcolor{EF476F}{b}\textcolor{118AB2}{b} = a^2 + 2ab + b^2

Squaring Sums: More Terms

How do we generalize this to more terms? We’ll use the same color-coded-copies trick. It helps to count out the terms in our pink copy using i and in our teal copy using j.2 When we multiply out our sums, we get a product term for each pair of terms in the sum. Each product term involves one term in the pink sum and one term in the teal one.

\cb*{\sum_{i=1}^n Z_i}^2 = \textcolor{EF476F}{\sum_{i=1}^n Z_i} \textcolor{118AB2}{\sum_{j=1}^n Z_j} = \textcolor{EF476F}{\sum_{i=1}^n} \textcolor{118AB2}{\sum_{j=1}^n} \textcolor{EF476F}{Z_i} \textcolor{118AB2}{Z_j}

Footnotes

  1. See Slide 3.1 for the squaring step beginning with (a+b)^2.

  2. If we used i to count terms in both sums, we’d wind up with two different things we call i: one pink and one teal. Using i and j keeps the two copies distinct.

App