# Non-independence of bootstrap samples

## Background

Suppose we have a dataset that consists of $$n$$ iid random variables represented as $$X_j$$, where $$j \in \{1,\ldots,n\}$$. We know $$\forall i,\, \operatorname{E}\left(X_i\right) = \mu$$, and that $$\operatorname{Var}\left(X_i\right) = \sigma^2$$.

Suppose further that we generate $$B$$ bootstrap samples from this data, with the $$i$$th element of the $$b$$th bootstrap sample denoted by $$X_i^{∗b}$$.

We want to show that $$\operatorname{Cov}\left(X_i^{∗b},\,X_j^{∗b}\right) = \frac{\sigma^2}{n}$$.

We already know $$\operatorname{E}\left(X_i^{∗b}\right) = \mu$$ and $$\operatorname{Var}\left(X_i^{∗b}\right) = \sigma^2$$ (refer to this question for these computations).

## Current attempt

My instinct is to consider any two constituents of a given bootstrap sample as independent, meaning their covariance should be 0.

But I understand why this instinct may be taking me in the wrong direction: I assumed an implicit condition when I stated that two "sample constituents" should be independent:

Namely, I assumed that the data the bootstramp sample was being created from has already been "realized".

In mathematical terms, what I was referring to is:

$$\operatorname{Cov}\left(X_i^{∗b},\,X_j^{∗b}\bigg|X_1,\ldots,\,X_n\right) = 0$$

And while this is true, it is not what we want to compute -- $$\operatorname{Cov}\left(X_i^{∗b},\,X_j^{∗b}\right)$$ is an unconditional covariance.

For some $$i,\,j \in \{1,\ldots,n\}$$ s.t. $$i \ne j$$: \begin{equation*} \begin{aligned} \operatorname{Cov}\left(X_i^{∗b},\,X_j^{∗b}\right) &= \operatorname{E}\left[\left(X_i^{∗b} - \operatorname{E}\left(X_i^{∗b}\right)\right)\left(X_j^{∗b} - \operatorname{E}\left(X_j^{∗b}\right)\right)\right]\\ & = \operatorname{E}\left[\left(X_i^{∗b} - \mu\right)\left(X_j^{∗b} - \mu\right)\right]\\ & = \operatorname{E}\left(X_i^{∗b} X_j^{∗b} - \mu X_i^{∗b} - \mu X_j^{∗b} + \mu^2\right)\\ & = \operatorname{E}\left(X_i^{∗b} X_j^{∗b}\right) - \mu \operatorname{E}\left(X_i^{∗b} - X_j^{∗b}\right) + \mu^2\\ & = \operatorname{E}\left(X_i^{∗b} X_j^{∗b}\right) + \mu^2\\ & = \sum_{i = 1}^n \sum_{j = 1}^n X_i X_j \operatorname{Pr}\left(X_i^{∗b} = X_i,\,X_j^{∗b} = X_j\right) + \mu^2\\ \end{aligned} \end{equation*}

And this is where I get stuck.

## Question

I am not sure how to show $$\operatorname{E}\left(X_i^{∗b} X_j^{∗b}\right) = \frac{\sigma^2}{n} - \mu^2$$.

• You seem to use "$\operatorname{Cov}$" in several different ways. If you're going to condition on the sample, please notice that because it's a sample it has no property that is directly relatable to $\sigma^2$: the covariance of the sample could literally be any number mathematically consistent with the range of the underlying distribution of the $X_i.$ How, then, have you any hope of proving what you want if you use the definition you provide after "mathematical terms"? – whuber Oct 5 '18 at 18:22
• @whuber Thank you for your comment. "[B]ecause it's a sample it has no property that is directly relatable to $\sigma^2$": this is new to me, and I see your point. In this context I also see why I got stuck in the last line of my computation of the covariance. With this, I'll work on the computation again and post my conclusions if I can reach what I desire. – Nurmister Oct 5 '18 at 18:37