5
$\begingroup$

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:

enter image description here enter image description here

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.

$\endgroup$
3
  • 1
    $\begingroup$ The right-hand side doesn't seem well-defined, without further assumptions on the joint distribution of the random variables involved. Do you want to assume that given $D_n$, the variables $U_i$ are exchangeable, or something like that? Otherwise you don't have e.g. Var$(U_1|D_n)$=Var$(U_2|D_n)$ in general. Or you could replace the right-hand side by $\sum_{i=1}^n \operatorname{Var}(U_i|D_n)$. $\endgroup$ Sep 1, 2021 at 10:37
  • 1
    $\begingroup$ In the case $n=1$, it's not true unless (loosely speaking) $D_1$ tells you the sign of $U_1$. That's because $\text{Var}(|X|)=\text{Var}(X)$ is equivalent to $E(X)=\pm E(|X|)$, which needs $X$ to be either non-negative with probability 1, or non-positive with probability 1. $\endgroup$ Sep 1, 2021 at 10:43
  • $\begingroup$ @James Martin. From your comment and Ben's answer, it's clear that the equation doesn't hold in general. On whether one can assume that given $D_n$, the $U_i$ are exchangeable, I have added additional context directly from the source. My understanding of the author's exposition is that perhaps there is an assumption that $U_i$ are conditionally i.i.d. given $D_n$, but to be honest, I'm not sure. I would appreciate your input on the matter. $\endgroup$
    – microhaus
    Sep 2, 2021 at 17:06

3 Answers 3

2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ +1. Thanks again Ben, this is really useful for me pedagogically. In particular, the tacit reminder that I should try and construct counter-examples when faced with a questionable expression rather than staring blankly at it. I have edited my question to remedy the absence of context which you have brought up, rather than asking a new question with updated context, as another member has enquired for this. $\endgroup$
    – microhaus
    Sep 2, 2021 at 16:45
  • 1
    $\begingroup$ Yeah, in fairness though, constructing counter-examples is easier said than done sometimes. I have a fair bit of "intuition" (read: long experience) for these types of problems so the counter-example comes immediately to mind. Without that experience it can be hard to intuitve how to form a counter-example, and staring blankly then becomes the de facto method. $\endgroup$
    – Ben
    Sep 2, 2021 at 18:06
  • 1
    $\begingroup$ Actually, in term of methodological approach, the first important thing here was to recognise that with the information given, conditioning on $D_n$ was irrelevant, and so you are essentially asking a simpler problem --- i.e., the question would be exactly the same without the conditioning. Sometimes if you can simplify the statement of a problem then that helps to see possible pathways to a solution. $\endgroup$
    – Ben
    Sep 2, 2021 at 18:08
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.