# Distribution of bounded summation of i.i.d random variables

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.

Then

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)$$

• 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)$? – Bloodmoon Jul 9 '15 at 16:53
• 1) memoization. 2) Thats why it's a sum over $n$ rather than an integral. 3) Because $S_n = S_{n-1} + X_n$. – Robert Israel Jul 9 '15 at 19:20
• 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? – Bloodmoon Jul 10 '15 at 3:15
• No, but in the limit as $T \to \infty$ you have the Elementary Renewal Theorem. – Robert Israel Jul 10 '15 at 5:35
• $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$. – Bloodmoon Jul 10 '15 at 6:33