Suppose $X\_n$ $n = 1, 2, \ldots$ are i.i.d random variables with $\mu := \mathbb{E}[X\_n]$ > 0. (although they are not necessarily non-negative). Then if $S\_n = \sum\_{k=1}^n X\_k$ and $\tau\_a$ = $\inf \{n \geq 1 : S\_n \geq a\}$ - so that $\tau$ is the first time that the random sum exceeds the value a. Does there exist some $b,c$ independent of $a$ such that $\mathbb{E}[\tau\_a] \leq b+c a$? (or is there even just some way to bound $\mathbb{E}[\tau\_a]$ in expectation?)


Additionally we may assume that all moments of $X\_n$ exist if needed.


I tried a naive bound using Chebyshev's inequality on $S\_n$ to say that it should be close to $n \mu$, and then $\mathbb{E}[\tau\_a] = \sum\_{k=1}^{\infty} \mathbb{P}[\tau\_a \geq k] \leq \sum\_{k=1}^{\infty}\mathbb{P}[S\_k \leq a]$ - however the details don't quite work out.


I also tried considering $M\_n = S\_n - n\mu$ as a martingale and trying to use optional stopping, but since $M\_{n \land \tau}$ isn't bounded from below I also can't quite see how to make it work.


Another idea is trying to use [Walds theorem](https://en.wikipedia.org/wiki/Wald%27s_equation#Example_with_dependent_terms), but assumption 3 in the wikipedia page gives me the exact same difficulties as trying to use optional stopping


I believe this should be possible, since if we view $S\_k$ as the martingale $M\_k$ and some drift, then we are in a similar case to Brownian Motion with drift,although our case is discreet. Then the hitting times $\rho\_a$ of Brownian motion with drift (which are now continuous) satisfy $\mathbb{E}[\rho\_a] \leq c a$, and an explicit pdf can be found.



First time random sum exceeds value
$\newcommand\al\alpha$Your desired bound is easy to get if we assume that $\alpha\_p:=E|X\_1-\mu|^p<\infty$ for some real $p\in(2,3)$.


Indeed,
$$E\tau\_a=E\sum\_{n=0}^{\tau\_a-1} 1=E\sum\_{n=0}^\infty 1(\tau\_a>n)=\sum\_{n=0}^\infty P(\tau\_a>n). \tag{1}\label{1}$$
Next, if $n\ge2a/\mu$, then
$$P(\tau\_a>n)\le P(S\_n<a)=P(S\_n-n\mu<a-n\mu)
\le\frac{E|S\_n-n\mu|^p}{|n\mu-a|^p}
\le2^p\frac{E|S\_n-n\mu|^p}{n^p\mu^p}
\le C\_1\frac{n\al\_p+n^{p/2}\al\_2^{p/2}}{n^p\mu^p}
\le\frac{C\_2}{n^{p/2}\mu^p};$$
here, $C\_1$ is a universal positive real constant, $C\_2$ is a positive real number depending only on $\al\_p$, and the penultimate inequality is an application of [Rosenthal's inequality](https://mathoverflow.net/a/298563/36721).


So, by \eqref{1},
$$E\tau\_a\le\sum\_{0\le n<2a/\mu}1+\sum\_{n\ge2a/\mu}\frac{C\_2}{n^{p/2}\mu^p}
\le\frac2\mu\,a+1+\frac{C\_3}{\mu^p}, \tag{2}\label{2}$$
where $C\_3$ is a positive real number depending only on $\varepsilon:=p/2-1>0$ and $\al\_p$. $\quad\Box$


One can replace the factor $\dfrac2\mu$ in the upper bound on $E\tau\_a$ in \eqref{2} by $\dfrac{1+\delta}\mu$, for any real $\delta>0$, but then $C\_3$ will have to depend on $\delta$ as well.


