1
$\begingroup$

I know that the expected value of a random variable X in a finite space S is $E(X) = \sum p(s)X(s)$ $\forall s \in S$, where $X(s)$ is the value of the random variable in the event $s$, and $p(s)$ is the probability of occurrence of $s$.

But I have seen in some recurrences with uniform distribution(for example quicksort algorithm) something like this:

$$ T(n) = \sum_{i=1}^{n} \frac{1}{n} ( f(i)+ T(i) + T(n-i) ) $$

where $f(i)$ is a function that depends on $i$, and $T(n)$ is the expected number of operations needed to perform some task with an array of size $n$. The part where I have my doubt is inside the parenthesis. This is not exactly the equivalent for $X(s)$ from above. The probability is $\frac{1}{n}$ for every term of the sum but the value of the implicit random variable is not precise. I mean that $X(s)$ is not $f(i) + T(i) + T(n-i)$ because $T(i)$ and $T(n-i)$ are expected values too, not values of random variables. $T(n)$ doesn't fit the definition of expected value given above.

Please help here. Thanks in advance.

$\endgroup$
  • $\begingroup$ This is just a different formula. $\endgroup$ – Qiaochu Yuan Nov 30 '17 at 16:55
  • $\begingroup$ Could it be that T(n) is an example of the law of total expectation? $\endgroup$ – Antonio González Borrego Dec 1 '17 at 14:05

Your Answer

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

Browse other questions tagged or ask your own question.