7
$\begingroup$

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 ?

$\endgroup$
  • 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$ – Ilya Aug 21 '12 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 '12 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 '12 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$ – Seyhmus Güngören Aug 21 '12 at 10:08
  • $\begingroup$ @did on popular demand I reverted back to the original question. $\endgroup$ – Geek Aug 21 '12 at 10:10
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What does same probability space mean ? $\endgroup$ – Geek Aug 21 '12 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$ – Ilya Aug 21 '12 at 10:21
4
$\begingroup$

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

$$af_1(x_1)+bf_1(x_2)=f_1(ax_1+bx_2)$$

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

$$\frac{1}{N}\sum_iE[X_i]=\mu$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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