Given a sequence $\{X_n\}$ of iid non-negative (like exponential) r.v.'s with expectation $1$, we know from SLLN $$\sum_{n=1}^k X_n / k \rightarrow 1 \quad \text{ a.e. }.$$ Suppose $X_n$ is the wait time for the $n$th package to arrive, we can define a integer valued process $f(t)$ which tells us how many packages have arrived up to time $t$ $$f(t): =\max\left\{k : \sum_{n=1}^k X_n < t \right\}.$$ How can I show that $$\lim_{t\rightarrow \infty} f(t)/t = 1? $$ We know $\{f(t) < k\} = \left\{\sum_{n=1}^k X_n > t\right\}$. And intuitively I know $f(t)/t$ is just like $\frac{k}{\sum_{n=1}^k X_n}$ which goes to $1$. How can I make this rigorous.


(Note: There's a typo in your definition of $f$; you should write $\max$ instead of $\min$.)

Your $f(t)$ is an example of a renewal process.

To simplify notation, I write $T_k=\sum_{n=1}^kX_n$. By definition, we have $T_{f(t)}<t\leq T_{f(t)+1}$. Then $$\frac{T_{f(t)}}{f(t)}<\frac{t}{f(t)}\leq\frac{T_{f(t)+1}}{f(t)+1}\frac{f(t)+1}{f(t)},$$ so (since $f(t)\to\infty$ pointwise and we have by the SLLN that the left and right-hand sides converge to $\mu$ almost everywhere) $\lim_{t\to\infty}t/f(t)=1$ a.e. Then, by nice properties of limits, we have $$\lim_{t\to\infty}f(t)/t=1$$ a.e.

In general, the result $\lim_{t\to\infty}f(t)/t=1/\mu$ holds for any $\mu>0$. (By $\mu$, I mean the expectation of the $X_n$'s.) For reference, the "Asymptotic properties" section of the renewal theory Wikipedia page and pp.126-127 of Durrett's Essentials of Stochastic Processes (2016) have very similar proofs.

  • $\begingroup$ Thank you, I believe you want to say $f(t) \rightarrow \infty$ instead of $1$ :) $\endgroup$ – Xiao Apr 28 '18 at 2:36
  • $\begingroup$ Right; just fixed that. Also, I fixed another typo: $\lim_{t\to\infty}f(t)/t=1/\mu$ does not hold for $\mu=0$, with our definition of $f(t)$. $\endgroup$ – xFioraMstr18 Apr 28 '18 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.