$N$-Fold Convolution of a Cdf with Itself
$\Begingroup$ 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)
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.
2 Answers
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$.
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.
David Miller brings 15 years of experience in global economics, personal finance strategy, and market dynamics. He specializes in turning complex economic trends into actionable insights for everyday readers.
