16 Homework 5: RVs, Markov’s Inequality, Chebyshev’s Inequality, Biased Estimators

Markov’s Inequality and Consistency

Convergence in mean square implies convergence in probability. Let’s use Markov’s inequality to see why.

Markov’s Inequality

Markov’s inequality says that for a non-negative random variable \(X\) and any \(t > 0\), \[ P(X \ge t) \le \frac{\mathop{\mathrm{E}}[X]}{t}. \]

The usual proof of Markov’s inequality is based on a few simple observations.

The expectation of the indicator variable \(1_{\ge t}(X)\) is the probability that \(X\) exceeds \(t\), \(P(X \ge t)\).
If we have some function of \(u\) that’s always larger than \(1_{\ge t}\), i.e., one satisfying \(u_t(x) \ge 1_{\ge t}(x)\) for all \(x\), we know that \(\mathop{\mathrm{E}}[u_t(X)] \ge \mathop{\mathrm{E}}1_{\ge t}(X)\) for any random variable \(X\). If it’s always larger for non-negative \(x\), then \(\mathop{\mathrm{E}}[u_t(X)] \ge \mathop{\mathrm{E}}[1_{\ge t}(X)]\) for any non-negative random variable \(X\).
The function \(u_t(x)=x/t\) is such a function.¹

Proving Markov’s Inequality

Prove Markov’s inequality.

Often, instead of using this to bound the random variable we’re interested in directly, e.g. \(X=|\hat\theta - \theta|\), we use it to bound the random variable’s square. \(|X| \ge \epsilon\) if and only if \(X^2 \ge \epsilon^2\), so the probability that \(|X| \ge \epsilon\) is the same as the probability that \(X^2 \ge \epsilon^2\). Applying Markov’s inequality to the random variable \(X^2\) gives us a bound in terms of \(X\)’s mean square which, in the specific case that \(X\) is \(|\hat\theta-\theta|\), is the mean squared error of the estimator \(\hat\theta\), \(\RMSE(\hat\theta)^2=\mathop{\mathrm{E}}[(\hat\theta-\theta)^2]\)

\[ P(X \ge \epsilon) = P(X^2 \ge \epsilon^2) \leq \frac{\mathop{\mathrm{E}}[X^2]}{\epsilon^2} \qqtext{ e.g.} P(|\hat\theta - \theta| \ge \epsilon) = P((\hat\theta - \theta)^2 \ge \epsilon^2) \leq \frac{\mathop{\mathrm{E}}[(\hat\theta - \theta)^2]}{\epsilon^2} \]

This tells us that, if the root-mean-squared error of \(\hat\theta\) goes to zero, then the probability that \(\hat\theta\) is any distance \(\epsilon\) away from \(\theta\) goes to zero, i.e., consistency in mean-square implies consistency in probability.

Exercise 17.1 (Markov in Action)

Draw \(n=10{,}000\) observations from an \(\text{Exponential}(1)\) distribution (use rexp(10000)).

For \(\epsilon = 2, 3, 5\), compute the fraction of observations that exceed \(\epsilon\). These are estimates of \(P(X \ge \epsilon)\).
For each \(\epsilon\), compute the Markov bound \(\mathop{\mathrm{E}}[X]/\epsilon = 1/\epsilon\).
Compare your empirical tail probabilities to the Markov bounds. How conservative is the bound?
Now try the same thing with \(X^2\) in place of \(X\). That is, square your observations and compare the fraction exceeding \(\epsilon^2\) to \(\mathop{\mathrm{E}}[X^2]/\epsilon^2\). Is this version of the bound tighter or looser?

Markov’s Inequality and Interval Estimation

So far, when we’ve calibrated interval estimates using our estimator’s standard deviation, we’ve relied on normal approximation. In effect, we’ve been using a formula for \(P(\lvert\hat\theta - \theta\rvert \le \epsilon)\) that’s accurate when \(\hat\theta\) has a normal distribution and close enough when its distribution is close enough to normal. In this problem, we’re going to think about doing without this reliance on approximate normality.

Let’s consider \(\hat\theta\), an unbiased estimator of \(\theta\) with standard deviation \(\sigma\), so the normal approximation to the distribution of \(\hat\theta-\theta\) has the density \(f_{0,\sigma}(x)\) below.

\[ P\qty(|\hat\theta - \theta| \le \epsilon) \approx \int_{-\epsilon}^{\epsilon} f_{0,\sigma}(x) dx \qfor f_{0, \sigma}(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-x^2/2\sigma^2} \]

The reason we’ve been talking about interval estimators of the form \(\hat\theta \pm 1.96 \sigma\) is that, if this approximation were perfect, these interval estimators would have 95% coverage. That is, it’d be true that \(P(|\hat\theta-\theta| \le 1.96 \sigma) = .95\). And if the approximation is pretty good, we should still expect coverage close to that. But suppose we’re not confident that it is. Markov’s inequality allows us to calibrate interval estimates in terms of our estimator’s standard deviation without any caveats about its sampling distribution being approximately normal. Let’s give it a shot.

Exercise 18.1

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.

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\).

Exercise 18.2 (Markov vs Normal Intervals)

Consider estimating the mean of an \(\text{Exponential}(1)\) distribution using the sample mean \(\bar X\) from a sample of size \(n=25\).

Run 10,000 simulations. In each, draw a sample of size 25, compute \(\bar X\) and \(s = \text{sd}(X)/\sqrt{n}\), and construct two 95% intervals:
- Normal interval: \(\bar X \pm 1.96s\)
- Markov interval: \(\bar X \pm \sqrt{20}\, s\)
What fraction of each type of interval contains the true mean \(\theta=1\)? (This is the empirical coverage.)
How do the average widths compare?
Is the normal interval’s coverage close to 95%? If so, what does that tell you about whether the Markov interval’s extra width is “worth it” here?

Chebyshev’s Inequality

You’ve just derived a special case of Chebyshev’s inequality. The general statement: for any random variable \(X\) with finite variance, \[ P(|X - \mathop{\mathrm{E}}[X]| \ge t) \le \frac{\mathop{\mathrm{\mathop{\mathrm{V}}}}[X]}{t^2}. \] When you applied Markov’s inequality to \(|\hat\theta - \theta|^2\) above, you got exactly this with \(X = \hat\theta\).

Biased Estimators

Introduction

So far, we’ve exclusively talked about unbiased estimators. That is, estimators with the property that their expected value is equal to the estimation target. \[ \hat\theta \qqtext{ is called unbiased if } \mathop{\mathrm{E}}\qty[\hat{\theta}] = \theta. \] We say an estimator is biased if this isn’t true. In this homework, we’ll work with some biased estimators to get a sense of what bias does to our inference. The punchline: it messes up our interval estimates’ coverage. We’ll see exactly how much in next week’s lecture.

Using Prior Information

To get a sense of what bias means, let’s consider a simple example of a biased estimator. Suppose we’re estimating a population proportion \(\theta\) using a sample \(Y_1 \ldots Y_n\) drawn with replacement from a binary population. Instead of using the sample mean \(\bar{Y}\), we use this estimator. \[ \tilde{Y}_1 = \frac{1}{n+1}\cdot \qty{\frac{1}{2} + \sum_{i=1}^{n}Y_i} \]

What’s going on here? We’re mixing in a “prior observation” of \(1/2\) with our sample. It’s as if we’d seen one observation equal to \(1/2\) before collecting any data, and we’re averaging that with what we actually observe.

Exercise 20.1

Suppose that we’ve drawn a sample \(Y_1 \ldots Y_n\) with replacement from a binary population \(y_1 \ldots y_m\) in which the proportion of ones is \(\theta\). Calculate the expected value of the estimator \(\hat\theta =\tilde{Y}_1\). Then calculate its bias \(\mathop{\mathrm{E}}[\hat\theta] - \theta\) and its standard deviation \(\sqrt{\mathop{\mathrm{\mathop{\mathrm{V}}}}[\hat\theta]}\). Report all three.

This is a specific example of a more general estimator that integrates information from a prior study. Maybe a real study or maybe a study we’re imagining. Suppose we have \(\nprior\) observations \(\yprior_1 \ldots \yprior_{\nprior}\) from this study.² \[ \thetaprior = \frac{1}{\nprior}\sum_{i=1}^{\nprior}\yprior_i. \]

Averaging all our observations—from our current study and this prior one—gives us the following estimator. \[ \begin{aligned} \tilde{Y}_{\nprior} &= \frac{1}{\nprior + n} \qty{\sum_{i=1}^{\nprior}\yprior_i + \sum_{i=1}^{n} Y_i} \\ &= \frac{1}{\nprior + n} \qty{ \nprior\thetaprior + n\bar Y } \end{aligned} \]

We treat these prior observations, and therefore their mean \(\thetaprior\), as deterministic. The simple example we started with, \(\tilde{Y}_1\), is a special case where we have a single prior observation \(\yprior_1 = \frac{1}{2}\).

Exercise 20.2

Repeat Exercise 20.1 for \(\tilde{Y}_{\nprior}\).

Visualizing the Impact of Prior Information

Let’s get a sense of how using prior information like this impacts our inference. The plot below shows the sampling distributions of three estimators of a population proportion \(\theta\) at three sample sizes \(n\): 10, 40, and 160. These are the estimators.

The estimator \(\hat\theta_1 = \tilde{Y}_{\nprior}\) for \(\thetaprior=3/4\) and \(\nprior=10\) prior observations.
The estimator \(\hat\theta_2 = \tilde{Y}_{n}\) for \(\thetaprior=3/4\) and \(\nprior=n\) prior observations. The bigger the sample, the more prior observations we use.
The sample mean, \(\hat\theta_3 = \bar Y\).

As usual, the estimation target \(\theta\) is indicated by a green line, the sampling distribution’s mean by a solid blue line, and its mean plus and minus two standard deviations by dotted blue lines.

A three-by-three grid of sampling distributions compares three estimators at sample sizes 10, 40, and 160. Green lines mark the target; blue solid and dotted lines mark each estimator's mean and two-standard-deviation range. — Figure 20.1: Sampling distributions of three estimators at three sample sizes.

Exercise 20.3

What is the correspondence between \(\hat\theta_1\), \(\hat\theta_2\), and \(\hat\theta_3\) described above and ‘estimator a’, ‘estimator b’, and ‘estimator c’ from the plot?

Bias, Variance, and Mean Squared Error

We call an estimator consistent if, when our sample size \(n\) is large enough, it converges to the thing we intend to estimate. One way to talk about this is convergence in mean square: \(\mathop{\mathrm{E}}[(\hat\mu - \mu)^2] \to 0\) as \(n \to \infty\). The quantity \(\mathop{\mathrm{E}}[(\hat\mu - \mu)^2]\) is the estimator’s mean squared error. It decomposes as \[ \underset{\text{mean squared error}}{\mathop{\mathrm{E}}\qty[(\hat\mu - \mu)^2]} = \underset{\text{bias}^2}{\qty(\mathop{\mathrm{E}}[\hat\mu] - \mu)^2} + \underset{\text{variance}}{\mathop{\mathrm{\mathop{\mathrm{V}}}}\qty[\hat\mu]}. \] This is called the bias/variance decomposition. Since \(\text{bias}^2\) and \(\text{variance}\) are both positive, an estimator is consistent if and only if both its bias and its variance go to zero.

Using the bias and standard deviation formulas you calculated above, write a formula for the mean squared error of \(\tilde{Y}_{\nprior}\). At what value of \(\nprior\) is the mean squared error minimized? Does the answer depend on \(\theta\)?

Comparing Interval Calibration Methods

Now let’s compare bootstrap, normal approximation, and Markov-calibrated intervals in practice. We’ll use our GA turnout data.

For each of two point estimators — (1) the sample mean \(\hat\theta = \bar{Y}\) and (2) the prior-observations estimator \(\tilde{Y}_{100}\) with \(\thetaprior = 1/2\) and \(\nprior=100\) —

Plot the bootstrap sampling distribution and a 95% confidence interval calibrated using it.
Plot an estimate of the normal approximation to the estimator’s sampling distribution and a second 95% confidence interval calibrated using that.
Plot a third 95% confidence interval, this time calibrated using Markov’s inequality.
Taking advantage of your knowledge of the population, plot the estimator’s actual sampling distribution and calculate the coverage probability of your three interval estimators.

Referring to your plots, comment on the behavior of your six³ interval estimators. If you had to do something like this again, which would you choose? Why? Would it make a difference if your sample size were larger, e.g. \(n=2500\) instead of \(n=625\)?

If you’re not convinced, sketch the two functions on the same axes. Sketching usually helps.↩︎
Sometimes we call these pseudo-observations. This particular interpretation, in which we think of them as coming from a prior study, can be used to derive this estimator from Bayesian principles.↩︎
\(2\ \text{point estimators} \times 3\ \text{interval calibration methods}=6\ \text{interval estimators}\)↩︎