# Expected time until beating an initial try

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

Questions:

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?

Thanks.

• 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$).
– Did
Jan 31 '15 at 11:15
• 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.
– Paul
Jan 31 '15 at 17:58
• 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$ Jan 31 '15 at 18:09
• That's true. I need to think more here about why the symmetry argument fails.
– Paul
Jan 31 '15 at 18:22
• 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.
– Paul
Jan 31 '15 at 18:44

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

$\square$

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

• 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. Feb 8 '15 at 5:37