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.
Best Answer
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.