Conditional variance of the absolute sum of zero-mean i.i.d. random variables

Question

Why does the following conditional variance formula hold, and does it hold in general?

$$\text{Var} \left( \left \vert \sum^n_{i=1} U_i \right \vert \, \middle | \,D_n \right) = n \text{Var}(U_i \vert D_n).$$

Here $U_i$ are zero-mean independent and identically distributed random variables, and nothing more about their distribution is stated. Further information on $U_i$ and $D_n$ is provided below.

I am comfortable with the standard result that for i.i.d. random variables $X_i$,

$$\text{Var} \left( \sum^n_{i=1} X_i \right) = \sum^n_{i=1} \text{Var}(X_i) = n \text{Var}(X_i),$$

but the presence of the absolute values in the formula of interest has thrown me.

---

Further information on $U_i$ and $D_n$.

In response to the helpful comments and answer by James Martin and Ben, it is clear that the equation does not hold in general, and that additional context on the $U_i$ and $D_n$ is required. Here is an extract of the proof where the equation is used:

Where $D_n = {(X_1, Y_1,), \dots, (X_n, Y_n)}$ and $D_n' = (X_1', Y_1'), \dots (X_n', Y_n')$ are two sets of i.i.d. random variables sampled from unknown joint distribution $D_n, D_n' \overset{i.i.d}{\sim} P(X, Y)$. The conditional expectation in $U_i$ is such that $\mathbb{E}_{D_n' | D_n}[\cdot \vert D_n]$. $f: \mathbb{R}^d \rightarrow \{0, 1 \}$ is a classifier function , while $\tilde{f}$ is a random classifier function, dependent on $D_n$.

The argument comes from the proof of the Vapnik-Chervonenkis inequality in an expository note by Robert Nowak (2009), following the strategy of Devroye, Györfi and Lugosi (1996) in their proof of Glivenko-Cantelli theorem.

Answer 1

$\newcommand{\Var}{\operatorname{Var}}$ In response to the edited version.

I think there's a glitch in that the "$=$" sign ought to be a "$\geq$" sign. With that change, everything seems to be (at least locally) OK.

A general fact is that $\Var(|X|)\leq \Var(X)$ for any random variable $X$. (Since $\Var(X)-\Var(|X|)=E(|X|)^2 - E(X)^2$, and $|E(X)|\leq E(|X|)$.)

So (applying the above conditional on $D_n$) we get that $\Var\left(|\sum_{i=1}^n U_i| \big| D_n\right) \leq \Var\left(\sum_{i=1}^n U_i \big| D_n\right)$.

Now we use the asserted fact (first line of the excerpt you quoted) that, conditional on $D_n$, the $U_i$ are i.i.d. (N.B. it's important that the $U_i$ are i.i.d. conditional on $D_n$; this is a different statement from saying that that $U_i$ are unconditionally i.i.d.)

That gives us that $\Var\left(\sum_{i=1}^n U_i \big| D_n\right) = \sum_{i=1}^n\Var\left( U_i \big| D_n\right) = n\Var\left(U_1\big|D_n\right)$.

Finally the next line is using the fact that $\Var(U_1\big| D_n)\leq 1/4$ (because conditional on $D_n$, $U_1$ is a shift of a Bernoulli random variable, and any Bernoulli random variable has variance at most $1/4$).

Answer 2

Your equation doesn't hold in general. As a simple counter-example, consider random variables that are conditionally IID with distribution $\mathbb{P}(U_i=-1|D_n) = \mathbb{P}(U_i=1|D_n)=\tfrac{1}{2}$.$^\dagger$ In this simple case you get:

$$\begin{align} \mathbb{E}(U_1 + U_2 | D_n) &= (-2) \cdot \frac{1}{4} + 0 \cdot \frac{1}{2} + 2 \cdot \frac{1}{4} = 0, \\[12pt] \mathbb{V}(U_1 + U_2 | D_n) &= (-2)^2 \cdot \frac{1}{4} + 0^2 \cdot \frac{1}{2} + 2^2 \cdot \frac{1}{4} = 2, \\[12pt] \mathbb{E}(|U_1 + U_2| | D_n) &= |-2| \cdot \frac{1}{4} + |0| \cdot \frac{1}{2} + |2| \cdot \frac{1}{4} = 1, \\[12pt] \mathbb{V}(|U_1 + U_2| | D_n) &= (|-2|-1)^2 \cdot \frac{1}{4} + (|0|-1)^2 \cdot \frac{1}{2} + (|2|-1)^2 \cdot \frac{1}{4} = 1, \\[12pt] \end{align}$$

so you have:

$$\mathbb{V}(|U_1 + U_2| | D_n) = 1 \neq 2 = \mathbb{V}(U_1 + U_2 | D_n).$$

In fact, as a general rule (stated here unconditionally but it also holds conditionally), you get:

$$\begin{align} \mathbb{V} \Bigg( \bigg| \sum_{i=1}^n U_i \bigg| \Bigg) &= \mathbb{E} \Bigg( \bigg| \sum_{i=1}^n U_i \bigg| ^2 \Bigg) - \mathbb{E} \Bigg( \bigg| \sum_{i=1}^n U_i \bigg| \Bigg)^2 \\[6pt] &\leqslant \mathbb{E} \Bigg( \bigg| \sum_{i=1}^n U_i \bigg| ^2 \Bigg) - \mathbb{E} \Bigg( \sum_{i=1}^n U_i \Bigg)^2 \\[6pt] &= \mathbb{E} \Bigg( \bigg( \sum_{i=1}^n U_i \bigg) ^2 \Bigg) - \mathbb{E} \Bigg( \sum_{i=1}^n U_i \Bigg)^2 \\[6pt] &= \mathbb{V} \Bigg( \sum_{i=1}^n U_i \Bigg) \\[6pt] &= \sum_{i=1}^n \mathbb{V}(U_i) + \sum_{i \neq j} \mathbb{C}(U_i,U_j). \\[6pt] \end{align}$$

In regard to your updated information, the result still does not hold with the additional information. (And indeed, the additional information shows that the situation is just a scaled version of what I have described above, so the result is generally false in that case.) It appears to me that this is probably just an error in the proof, using an invalid step. Substiting the correct inequality in the erroneous step still gives a valid proof, so the proof itself still works once corrected.

---

$^\dagger$ You haven't given us any information on what $D_n$ is, so it is essentially irrelevant here. Since you haven't told us anything about $D_n$ you can just posit that the values for $U_i$ are marginally IID and that $D_n$ is some irrelevant variable that is independent of these.

Answer 3

This is a new answer looking at the later question supplemented by your additional information. This new answer should be seen as augmenting my previous general observations in the other answer.

With the new information added to the question, you now have a specific distribution for the values under consideration. Suppose we define the parameter $\theta = \mathbb{P}(\tilde{f}(X_i') \neq Y_i'|D_n)$ and note that this quantity is fixed for all $i$.$^\dagger$ From the information specified in the excerpt, we have the conditional distribution:

$$U_1,...,U_n | D_n \sim \text{IID Bern}(\theta) - \theta,$$

which gives $\sum_{i=1}^n U_i | D_n \sim \text{Bin}(n, \theta) - n \theta$. Consequently, we get:

$$\begin{align} \mathbb{E} \Bigg( \bigg| \sum_{i=1}^n U_i \bigg| \Bigg| D_n \Bigg) &= \sum_{k=0}^n |k-n\theta| \cdot \text{Bin}(k|n, \theta) \\[6pt] &= \sum_{k=0}^{\lfloor n \theta \rfloor} (n\theta-k) \cdot \text{Bin}(k|n, \theta) + \sum_{k=\lfloor n \theta \rfloor+1}^n (k-n\theta) \cdot \text{Bin}(k|n, \theta), \\[6pt] \end{align}$$

and:

$$\begin{align} \mathbb{V} \Bigg( \bigg| \sum_{i=1}^n U_i \bigg| \Bigg| D_n \Bigg) &= \mathbb{E} \Bigg( \bigg( \sum_{i=1}^n U_i \bigg)^2 \Bigg| D_n \Bigg) - \mathbb{E} \Bigg( \bigg| \sum_{i=1}^n U_i \bigg| \Bigg| D_n \Bigg) ^2\\[6pt] &= n \theta (1-\theta + n\theta) \\[6pt] &\quad + \Bigg( \sum_{k=0}^{\lfloor n \theta \rfloor} (n\theta-k) \cdot \text{Bin}(k|n, \theta) + \sum_{k=\lfloor n \theta \rfloor+1}^n (k-n\theta) \cdot \text{Bin}(k|n, \theta) \Bigg)^2. \\[6pt] \end{align}$$

The latter quantity is not generally equivalent to:

$$\mathbb{V} \Bigg( \sum_{i=1}^n U_i \Bigg| D_n \Bigg) = n \mathbb{V}(U_i|D_n) = n \theta (1-\theta),$$

so this step in the paper appears to be wrong to me. Most likely, the author meant to assert the inequality $\mathbb{V}(| \sum U_i | |D_n) \geqslant n \mathbb{V}(U_i|D_n)$ here rather than asserting equivalence (which is wrong). The overall proof still works if you use the inequality relation instead, so this is just one of those cases where a step in the proof is written incorrectly, but the proof itself still works.

---

$^\dagger$ The information specifies that the values $U_1,...,U_n | D_n$ are IID, which can only be the case if the quantity $\theta$ is fixed over all $i=1,...,n$.