First time random sum exceeds value 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, 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.
 A: $\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.
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.
