You have a random variable $X$, which can take a value from $i = \{1,2,3,...\}$, where the probabilities are $p_i = 0.5^i$. Now you if we have a list $(x_1, ..., x_n)$ of independent observations of this variable $X$, the function $f$ counts how often $x_{i+1} > \max\{x_{1},...,x_{i}\}$. What is the expected value of $f$?

  • 1
    $\begingroup$ Add the self study tag. $\endgroup$ Aug 30, 2018 at 15:23

1 Answer 1


Hint: you're interested in the expected value: $E[\sum_{i}^{n-1}1_{\{x_{i+1}>\mbox{max}(x_1,\cdots,x_i)\}}]$, where $1$ is an indicator function. Then $E[1_{\{x_{i+1}>\mbox{max}(x_1,\cdots,x_i)\}}]=P(x_{i+1}>\mbox{max}(x_1,\cdots,x_i))= \prod_{k=1}^iP(x_{i+1}>x_k)$

so finish the problem by using linearity-of-expectation.

  • $\begingroup$ So you mean for the second expectation we have $\sum_{i=1}^{\inf} 0.5^i * (1- \sum_{k=1}^i 0.5^k) = 0.33$. We then have for the total expectation $n*0.33$. Is this correct? $\endgroup$ Aug 30, 2018 at 14:23
  • $\begingroup$ i made a mistake in the question i edit it. $\endgroup$ Aug 30, 2018 at 14:36
  • $\begingroup$ I've updated the answer given your new edit. $\endgroup$
    – Alex R.
    Aug 30, 2018 at 15:46
  • $\begingroup$ So i would say it is $\sum_{i}^{n-1} 0.33^i$ $\endgroup$ Aug 30, 2018 at 16:05

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.