We have a set of positive random variables $\boldsymbol X=\{X_1, X_2,\ldots\}$, where $X_1, X_2,\ldots$, are independent and identically distributed (i.i.d.). The CDF $F(x)$ and PDF $f(x)$ for $X_i$ are known in advance.

Define $S_n=\sum_{i=1}^nX_i$.

As we can see $\boldsymbol X$ can be viewed as inter-arrival times for a renewal process, and $S_n$ denotes each arrival epoch.

Next we define a variable $K$: $K=\inf\, \{n\mid S_n>T\}$ (or $K=\min\, \{n\mid S_n > T\}$), where $T$ is a constant.


  1. what is the distribution of $K$?
  2. what is the distribution of $S_K$?

I already know that the PDF for $S_n$, denoted by $f_n$, can be computed by $f_n=f^{*n}=f*f*\cdots *f$, the $n$-fold convolution power of $f(x)$. By Laplace Transform, we can convert the convolution to multiplication.


1 Answer 1


The CDF of $K$ is $$ P(K \le n) = P(S_n > T) = \int_{T}^\infty dt\; f_n(t)$$ The CDF of $S_K$ (for $s > T$) is $$\eqalign{P(S_K \le s) &= \sum_{n=1}^\infty P(K = n, S_n \le s) = \sum_{n=1}^\infty P(S_{n-1} \le T, T < S_n \le s)\cr &= \sum_{n=1}^\infty \int_0^T dt\; f_{n-1}(t) \int_T^s dr\; f(r-t)}$$

EDIT: the $n=1$ term needs to be modified since $S_0 = 0$ doesn't have a density. So (assuming of course $T > 0$) it's $$P(S_K \le s) = \int_T^s dr\; f(r) + \sum_{n=2}^\infty \int_0^T dt\; f_{n-1}(t) \int_T^s dr\; f(r-t)$$

  • $\begingroup$ The CDF of $K$ is straightforward to understand, but since $f_n(t)$ involves convolution, 1) is there any way to reduce the computational complexity for computers? 2) the values of $K$ are actually discrete, should this be considered while deriving the CDF for $S_K$? 3) why $f(r-t)$ rather than $f_n(r)$ is at the end of $P(S_k\leq s)$? $\endgroup$
    – Bloodmoon
    Jul 9, 2015 at 16:53
  • $\begingroup$ 1) memoization. 2) Thats why it's a sum over $n$ rather than an integral. 3) Because $S_n = S_{n-1} + X_n$. $\endgroup$ Jul 9, 2015 at 19:20
  • $\begingroup$ Thanks! It's clear that I can compute the expectation of $K$ $E[K]$ according to its CDF. But this still involves convolution. Is there any simpler way to derive $E[K]$? Is $E[K]=\lceil {T/E[X]} \rceil$ correct? $\endgroup$
    – Bloodmoon
    Jul 10, 2015 at 3:15
  • $\begingroup$ No, but in the limit as $T \to \infty$ you have the Elementary Renewal Theorem. $\endgroup$ Jul 10, 2015 at 5:35
  • $\begingroup$ $T$ will not has a limit in my case. Why $E[K]=\lceil {T/E[X]} \rceil$ is incorrect? This seems straightforward based on the definition of $K$. $\endgroup$
    – Bloodmoon
    Jul 10, 2015 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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