# Expected value of counting function over infinite set

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

• Add the self study tag. Aug 30, 2018 at 15:23

## 1 Answer

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.

• 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? Aug 30, 2018 at 14:23
• i made a mistake in the question i edit it. Aug 30, 2018 at 14:36
• I've updated the answer given your new edit. Aug 30, 2018 at 15:46
• So i would say it is $\sum_{i}^{n-1} 0.33^i$ Aug 30, 2018 at 16:05