1
$\begingroup$

I'm reading an algorithm proof in which there is a passage I can't understand. Substantially we have 2 statistically independent random arrays $X$ and $Z$, and a third random array $Y$. It's known that $Y=XZ$ and $E[Z] = 1$. What the author provides are textually the following passages: \begin{align} VAR[Y] &= E[(Y -E[Y])^2]\\ &= E[(X(Z-1) + (X-E[X]))^2]\\ &= (VAR[X]+E[X^2])VAR[Z]+VAR[X] \end{align} where $E[X]$ and $VAR[X]$ are the expected value (i.e. mean) and the variance of $X$, respectively.

Trying to understand that proof, I'm getting a different result, as it is: \begin{align} VAR[Y] &= E[(Y -E[Y])^2]\\ &= E[(XZ - E[XZ])^2]\\ &= E[(XZ -X +X -E[X])^2]\\ &= E[(X(Z-1) + (X-E[X]))^2]\\ &= E[X^2(Z-1)^2 + (X - E[X])^2 + 2X(Z-1)(X - E[X])]\\ &= E[X^2]E[(Z-1)^2] + VAR[X] + 2E[X(Z-1)(X - E[X])]\quad \text{(then, as $E[Z] = 1$)}\\ &= E[X^2]VAR[Z] + VAR[X] + 2E[X^2Z - ZXE[X] - X^2 + XE[X]]\\ &= E[X^2]VAR[Z] + VAR[X] + 2E[X^2Z] - 2E[ZXE[X]] - 2E[X^2] + 2E[XE[X]]]\\ &= E[X^2]VAR[Z] + VAR[X] + 2E[X^2]E[Z] - 2E[XE[X]]E[Z] - 2E[X^2] + 2E[XE[X]]]\\ &= E[X^2]VAR[Z] + VAR[X] + 2E[X^2] - 2E[XE[X]] - 2E[X^2] + 2E[XE[X]]]\\ &= E[X^2]VAR[Z] + VAR[X] \neq (VAR[X]+E[X^2])VAR[Z]+VAR[X] \end{align}

Can you help me to understand where am I wrong? Thank you very much in advance for your attention.

EDIT: This is the original author proof algorithm proof

  • 0
    Removed tag (proof-theory).2012-08-25

1 Answers 1

4

I don't see in what sense $X$, $Y$ and $Z$ are arrays, especially given $E[Z]=1$; I'll assume that they're just random variables. (Also where you write "pass" it seems you mean "passage".)

Your calculation is correct. You can check this using a simple example, for instance $X$ and $Z$ both uniformly drawn from $\{0,2\}$.

You could considerably shorten your calculation by noting that the expected value of any term of the form $f(X)(Z-1)$ vanishes; that gets rid of the mixed term that the last few lines focus on.

  • 0
    @Alfatau: What you write about arrays and variables appears to indicate a confusion on your part. The *mean* of the values in a random array can be $1$, but the *expectation* of a random array is an array. You can have an array of samples drawn from a random variable, but that doesn't turn the random variable into an array, and it doesn't change the fact that $Z$ and $E[Z]$ necessarily have the same dimensions, so if $E[Z]$ is a number, then $Z$ is a random variable.2012-08-25