Consider the following problem: Let $X,X_1,X_2,...$ be i.i.d. random variables. We execute the following experiment. One samples $X$. Then, one samples $X_1$,$X_2$ and so on until the first time the initial value $X$ was surpassed (or at least repeated).

Denote by $T$ the number of tries needed until this experiment is terminated. I wish to find out what the expectancy of $T$ is.

It is clear that, conditioned on ${X=x}$, $T$ is a geometric random variable with expectation $\frac{1}{\Pr\{X\ge x\}}$.Thus, if $X$ was absolutely continuous with density $f_X$, its expectation could be written as an integral: $$ \int_{-\infty}^{\infty} {\frac{f_X(x)}{1-F_X(x)}dx} $$ where $F_X(x)=\Pr\{X\le x\}$. Noting that $\frac{d}{dx}F_X=f_X$ yields a formula for a primitive function which is -$\log(1-F_X(x))$, which diverges as $x\rightarrow \infty$, so the expecation is infinite.

Similarly, if $X$ was discrete then we could assume WLOG that it is supported on the integers. Letting $\Pr\{X=n\}=p_n$, we have the following formula for the expectation: $$ \mathbb{E}T=\sum_{n=-\infty}^{\infty} {\frac{p_n}{\sum_{k=n}^{\infty} p_k}} $$


  1. Suppose $X$ is supported on a finite set. It is clear that $T$ has finite expectation in this case. Can one provide a nicer form of the expression above?

  2. It's easy to see that the limit $n\rightarrow -\infty$ "behaves nicely" in the sum above (as the denominator goes to $1$ and the numerator converges). If one assumes that $p_n$ does not vanish for large enough values of $n$, is it true that the series diverges?

  3. What happens if $X$ is continuous but not absolutely continuous? Is there a unified theory all random variables?


  • 2
    $\begingroup$ Indeed, if $(p_n)_{n\geqslant0}$ is such that $p_n\ne0$ for infinitely many $n$ then the series $\sum\limits_n\frac{p_n}{q_n}$ diverges, where $q_n=\sum\limits_{k\geqslant n}p_k$, since, for every $N$, $\sum\limits_{n\geqslant N}\frac{p_n}{q_n}\geqslant\sum\limits_{n\geqslant N}\frac{p_n}{q_N}=1$. The same applies as soon as the support of $X$ contains countably many intervals $I_i=[a_i,a_{i+1})$ with positive measure $p_i$ (compare $T$ for $X$ with $T$ for the discrete random variables $Y$ such that $P(Y=a_i)=p_i$). $\endgroup$
    – Did
    Jan 31 '15 at 11:15
  • $\begingroup$ The answer does not depend on the distribution. You could ask what is the expected value of i such that the quantile of $X_i$ is the first quantile to exceed the quantile of $X$, and you get the same answer. Therefore, work a simple distribution, say uniform on (0,1), and see what you get. $\endgroup$
    – Paul
    Jan 31 '15 at 17:58
  • $\begingroup$ Paul, it must depend on the distribution in some way - if the RV is a constant function, then $\mathbb{E}T=1$. However, if the RV is, say, uniform on (0,1), then the calculation above suggests that $\mathbb{E}T=\infty$ $\endgroup$
    – Miel Sharf
    Jan 31 '15 at 18:09
  • $\begingroup$ That's true. I need to think more here about why the symmetry argument fails. $\endgroup$
    – Paul
    Jan 31 '15 at 18:22
  • $\begingroup$ Thought about it some more. As long as the cdf is continuous (no finite mass points), my argument works, and yes you get $\infty$ in this case. $\endgroup$
    – Paul
    Jan 31 '15 at 18:44

@Did answered (2) for you.

Ill try (1):

Let $X(\omega) \in I,\;|I|=M<\infty,\;\text{ and } P(X=i)=p_i\; \forall i\in I$:

Lets say $X=j: j\in I$ then:

$$E[T|X=j]=\frac{1}{\sum\limits_{i\in I:i\geq j}p_j}$$

By the tower property of conditional expectation:

$$E[E[T|X]]=E[T]$$ so

$$E[T]=\sum_{i\in I} \left\{P(X=i)E[T|X=i]\right\}=\sum_{i\in I}\frac{p_i}{\sum\limits_{j\in I:j\geq i}p_j}\leq \sum_{i\in I} \left\{p_i\cdot \frac{1}{p_i}\right\}=|I|=M<\infty$$


For (3): Yes, it is called measure theory.

  • $\begingroup$ I am aware to the existence of measure theory, but I asked for a general argument which calculates $\mathbb{E}T$ which does is not separated to cases based on $X$ being a.c., discrete or continuous but not a.c. $\endgroup$
    – Miel Sharf
    Feb 8 '15 at 5:37

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.