Return to Answer

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.

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

The Lorden inequality (link in comment above) shows that $E[T_n]/n \leq 1 + \frac{E[X^2]}{E[X]}$. However, intuitively I would expect the overshoot for large $n$ to be $\approx \frac{E[X^2]}{2E[X]}$, which can be arbitrarily close to $1/2$ (so $C \approx 1.5$) by choosing $\{x_1, \ldots, x_n\} = \{\epsilon, \ldots, \epsilon, 1-(n-1)\epsilon\}$.

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.

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

The Lorden inequality (link in comment above) shows that $E[T_n]/n \leq 1 + \frac{E[X^2]}{E[X]}$. However, intuitively I would expect the overshoot for large $n$ to be $\approx \frac{E[X^2]}{2E[X]}$, which can be arbitrarily close to $1/2$ (so $C \approx 1.5$) by choosing $\{x_1, \ldots, x_n\} = \{\epsilon, \ldots, \epsilon, 1-(n-1)\epsilon\}$. [See comment below by James Martin on why this conjecture is not correct due to the threshold "1" being too small]

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

The Lorden inequality (link in comment above) shows that $E[T_n]/n \leq 1 + \frac{E[X^2]}{E[X]}$. However, intuitively I would expect the overshoot for large $n$ to be $\approx \frac{E[X^2]}{2E[X]}$, which can be arbitrarily close to $1/2$ (so $C \approx 1.5$) by choosing $\{x_1, \ldots, x_n\} = \{\epsilon, \ldots, \epsilon, 1-(n-1)\epsilon\}$.

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.

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

The Lorden inequality (link in comment above) shows that $E[T_n]/n \leq 1 + \frac{E[X^2]}{E[X]}$. However, intuitively I would expect the overshoot for large $n$ to be $\approx \frac{E[X^2]}{2E[X]}$, which can be arbitrarily close to $1/2$ (so $C \approx 1.5$) by choosing $\{x_1, \ldots, x_n\} = \{\epsilon, \ldots, \epsilon, 1-(n-1)\epsilon\}$.

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

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

The Lorden inequality (link in comment above) shows that $E[T_n]/n \leq 1 + \frac{E[X^2]}{E[X]}$. However, intuitively I would expect the overshoot for large $n$ to be $\approx \frac{E[X^2]}{2E[X]}$, which can be arbitrarily close to $1/2$ (so $C \approx 1.5$) by choosing $\{x_1, \ldots, x_n\} = \{\epsilon, \ldots, \epsilon, 1-(n-1)\epsilon\}$.