Let $n \in \mathbb{N}$, $x\_1, \ldots, x\_n \in (0,1)$ fix but arbitrary, s.t. $\sum\_{i=1}^n x\_i = 1$. Let $X\_i \sim \operatorname{Unif}(\{x\_1, \ldots, x\_n\})$ i.i.d., and $T\_n = \min\{t \in \mathbb{N} \, : \, \sum\_{i=1}^t X\_i \geq 1\}$.


I think there exists a constant $C$, which is independent of $n$, s.t.
$$\mathbb{E}[T\_n] \leq C \cdot n.$$


(At least, if we assume, that $x\_1 \geq \frac{1}{2}$, then $C \leq 2$.)


My question is the following: What is the smallest possible $C$, s.t. the estimate holds? Do you know, if there is any work regarding this problem?


I could show, that in a special case $C \approx 1.36$, and I think it is the worst case, but couldn't prove it up to now.



Upper bound of the waiting time of a sum process
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]


