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.


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 '15 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$ – Robert Israel Jul 9 '15 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 '15 at 3:15
  • $\begingroup$ No, but in the limit as $T \to \infty$ you have the Elementary Renewal Theorem. $\endgroup$ – Robert Israel Jul 10 '15 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 '15 at 6:33

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.