In reading about the average case analysis of randomized quick sort I came across linearity of expectations of indicator random variable I know indicator random variable and expectation. What does linearity of Expectation mean ?

  • 2
    $\begingroup$ I do not think it is a good idea to update your question adding new meaning to it, rather than clarifying the first version. Especially, after you got answers to the first version already. Especially, since you are not new to MSE. $\endgroup$
    – SBF
    Aug 21, 2012 at 10:06
  • $\begingroup$ @Ilya These two properties are used together to analyze the running time of algorithms . So I put them both in one place and I think it makes sense like this . $\endgroup$
    – Geek
    Aug 21, 2012 at 10:07
  • 3
    $\begingroup$ @Geek: Please return to the original version of your question (the one to which you received two answers). If you have another question, ask it on a different post. $\endgroup$
    – Did
    Aug 21, 2012 at 10:08
  • $\begingroup$ @Geek your question turned into a new question. I have never heart about independence of expectation. Ilya is right in his comment. $\endgroup$ Aug 21, 2012 at 10:08
  • $\begingroup$ @did on popular demand I reverted back to the original question. $\endgroup$
    – Geek
    Aug 21, 2012 at 10:10

2 Answers 2


Let $\xi_1,\xi_2:\Omega\to\mathbb R$ be two random variables on the same probability space $(\Omega,\mathscr F,\mathsf P)$ . The expectation of either is defined by $$ \mathsf E\xi_i:= \int_\Omega \xi_i(\omega)\mathsf P(\mathrm d\omega). $$ The linearity of the expectation means that for any constants $\alpha_1,\alpha_2\in\Bbb R$ it holds that $$ \mathsf E[\alpha_1\xi_1+\alpha_2\xi_2] = \alpha_1\mathsf E\xi_1+\alpha_2 \mathsf E\xi_2 $$ which follows directly from the linearity of the Lebesgue integral in the definition of the expectation. Hence, the functional $\mathsf E$ defined over the space of random variables on the probability space $(\Omega,\mathscr F,\mathsf P)$ is linear.

For the independence over the product, yet again if $\xi_1,\xi_2,\dots,\xi_n$ are random variables on the same probability space as above, and they are mutually independent then $$ \mathsf E\left[ \prod_{i=1}^n\xi_i\right] = \prod_{i=1}^n\mathsf E\xi_i $$

  • $\begingroup$ What does same probability space mean ? $\endgroup$
    – Geek
    Aug 21, 2012 at 10:18
  • $\begingroup$ Well, you may consider it as a technical condition saying that the notion of the expectation (of a sum/product of several random variables) and independence of random variables are well-defined. $\endgroup$
    – SBF
    Aug 21, 2012 at 10:21

The expectaion is a linear operator. This means it satisfies the linearity properties of a function/operator. The linearity is defined as


As an example to Expectaion

$$E[\frac{1}{N}\sum_iX_i]=\frac{1}{N}\sum_iE[X_i]$$ and assume that $E[X_i]=\mu$ $\forall i$ then you get



You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .