Skip to main content
2 of 5
added 303 characters in body
Michael
  • 544
  • 4
  • 11

This looks like a "Wald equality" question. Define $Y=\sum_{i=1}^{T_n} X_i$. Then: \begin{align} 1 + x_{max} \geq Y =\sum_{i=1}^{\infty} X_i1\{T_n\geq i\}\\ \end{align} where $1\{T_n\geq i\}$ is an indicator function that is $1$ if $T_n\geq i$, and 0 else. Taking expectations of both sides gives: $$ 1 + x_{max} \geq \sum_{i=1}^{\infty} E[X_i]Pr[T_n\geq i] $$ where we used the fact that $X_i$ is independent of the event $\{T_n \geq i\}$. Using the fact that $E[X_i]=1/n$ for all $i$ gives: $$ 1 + x_{max} \geq (1/n)\sum_{i=1}^{\infty}Pr[T_n\geq i] = (1/n)E[T_n] $$ Thus $E[T_n] \leq (1+x_{max})n \leq 2n$.

So you can use $C=1+x_{max}$ if you have a bound on $x_{max}$, or you can use $C=2$ else.


If you require this to hold for all $n$, then $C=2$ is the best you can do. Consider the case $n=1$ and $x_1=1-\epsilon$. Then $T_1 = 2-2\epsilon$ surely.

The James Martin observation looks interesting if you only require the condition to hold for large $n$.

Michael
  • 544
  • 4
  • 11