$n$-fold convolution of a CDF with itself

Question

Problem: Suppose that $X_1,X_2,\dots$ are i.i.d. nonnegative integer-valued random variables with common CDF $F(x)$. Assume that $F(0)<1$ and let $F^{(n)}$ denote th $n$-fold convolution of $F$. (This is the convolution of $n$ copies of $F$.)
Show that $\displaystyle\sum_{n=1}^\infty F^{(n)}(x)$ is finite for all $x\geq0.$
We want to find random variables $Y_i$ which depend on $x$ such that $E\lbrack Y_i\rbrack=F^{(n)}(x)$ and then show that the sum of $Y_i$'s is also a random variable with finite expectation.
The issue we are having is that we are not sure that our understanding of the $n$-fold convolution of $F$ with itself is correct. We think that $$F^{(n)}(x)=\int_{0}^{x}\cdots\int_{0}^{x}F(x-x_1-\cdots-x_n)F(x_1)F(x_2)\cdots F(x_n)\,dx_1\cdots dx_n.$$ From this, we think that the $Y_i$'s should be $$Y_i(x_1)=\int_{0}^{x}\cdots\int_{0}^{x}F(x-x_1-\cdots-x_n)F(x_1)F(x_2)\cdots F(x_n)\,dx_2\cdots dx_n.$$

---

Could anyone help us clearing the smoke out in this problem?
Thank you for your time and feedback.

Answer 1

What you should know is the fact that if $Y$ and $Z$ are independent random variables, then the distribution function of $Y+Z$ is the convolution of the distribution functions of $Y$ and $Z$. So the convolution of two independent random variables(or distributions) represents their sum.

With that in mind, the sum $\sum_{n=1}^\infty F^{n}(x) = \sum_{n=1}^\infty P(X_1+...+X_n \leq x)$ where $X_1,...,X_n$ are iid with distribution $F$.

To show that this sum is finite, we basically need to focus on large $n$, and showing that for large $n$, the terms are very small. How? Well, the $X_i$ are non-negative integer valued : so if $n$ is an integer much larger than $x$, then for $X_1+...X_n \leq x$ to happen, a lot of the $X_i$ will have to be zero. The condition $F(0)<1$ guarantees that this can only happen with a certain probability, and by independence we will get a bound that should work.

---

More precisely : if $X_1+...+X_n \leq x$ for some $n > \lceil x\rceil$, then at least $n-\lceil x \rceil$ of the $X_i$ are zero. So, we bound : $$ P(X_1+...+x_n \leq x) \leq P(\text{at least $n-\lceil x\rceil$ of the $X_i$ are zero}) \\ \leq \sum_{j=n-\lceil x\rceil}^n P(\text{at least $j$ of the $X_i$ are zero})\\ \leq\sum_{j=n - \lceil x \rceil}^n\binom{n}{j} F(0)^{n-j} (1-F(0))^{j} \\ = \sum_{j=0}^{\lceil x \rceil} \binom{n}{j} F(0)^j (1-F(0))^{n-j} $$

This is the probability that $Bin(n,F(0)) \leq \lceil x \rceil$, where $Bin(n,p)$ is a binomial random variable. Look up tail bounds for the binomial random variable like Hoeffding etc. and see if you can finish this off by yourself.

Answer 2

This is easiest shown by noting that we can consider the $X_i$ as interarrival times to a renewal point process (arrival times) in which $t_n=X_1+\cdots + X_n$ is the time on $(0, \infty)$ of the $n^{th}$ point in time.

Thus the cumulative number of points in the interval $(0,t]$ is the counting process $N(t)=\sum_{n=1}^{\infty} I\{t_n\le t\},$ where $I\{A\}$ denotes the indicator function for the event $A$ ($=1$ if A occurs, $=0$ if $A$ does not occur); here $A=\{t_n\le t\}$. Taking expected values (Tonelli's Theorem allows) yields exactly the desired computation (let $t=x$): $$E(N(t))=\sum_{n=1}^{\infty} P(t_n\le t)$$.

To see why this is always finite: Choose $a>0$ such that $0<F(a)<1$ and define new iid interarrival times ${\hat X}_n$ via ${\hat X}_n=a I\{X_n>a\}$ ($=0$ then if $X_n\le a$)

Then the new counting process (using these interarrival times) is ${\hat N}(t)$ and we have the upper bound $N(t)\le {\hat N}(t)$. But in this bounding point process, arrivals occur in batches at times $\{na: n\ge 0\}$, and the batch sizes have a geometric distribution with success probability $p=1-F(a)=P(X>a)$; hence a mean of $1/p$. Up to time t there are at most $[t/a]$ such batches and so $E(N(t))\le E ({\hat N}(t))\le [t/a]/p <\infty$.