# Probability distribution of the sum of 1 to n random integers

I apologize in advance if the title of this question was not clear, I do not know how to formalize this question myself, and therefore I need help. I will try to explain the problem as simple as possible, so as not to confuse myself, so please bear with me if it gets redundant.

Assume you have a random number $X$, which only takes on positive integer values, with a discrete probability distribution. The probability of $X$ taking on a value of $x$ is given by $P(X=x)$.

I would like to know the probability distribution $P(S=s)$, where $S$ is the sum of a varying number of consecutive, independent draws of $X$.

To give an example: If $s=1$, I would like to know the probability of observing an arbitrary number of consecutive draws of $X$ which add up to 1. Here, we can only consider a single draw of $X$, since $X$ takes on only positive integer values (the minimum possible value of $X$ is 1). In this case (I think)

$P(S=1) \propto P(X=1)$.

If $s=2$, we need to consider 2 cases. A single draw of $X$ with the outcome 2 OR two independent draws of $X$ both with the outcome 1, will both yield a sum of 2. So the probability of having a sum of 2 is given by (I think)

$P(S=2) \propto P(X=2)+P(X=1)^2$.

To make things more clear, I'd like to give examples for higher values of $s$. For simplicity, from here on I'll represent $P(X=x)$ as $p_x$.

$P(S=1) \propto p_1$

$P(S=2) \propto p_2+p_1^2$

$P(S=3) \propto p_3+2 p_1 p_2 + p_1^3$

$P(S=4) \propto p_4 + 2 p_1 p_3 + p_2^2 + 3 p_1^2 p_2 + p_1^4$

$P(S=5) \propto p_5 + 2p_1p_4 + 2p_2p_3 + 3 p_1^2 p_3+ 3p_1p_2^2+4p_1^3p_2+p_1^5$

In particular, I'd like to know:

1) whether I'm making a logical error here in the above formalization. I know the right hand sides above are not equal to the probabilities $P(S=s)$ on the left hand side, because they are not normalized (i.e. the sum of the right hand side terms as $s \rightarrow \infty$ will be bigger than 1), but I believe this can be solved with the proper choice of a normalization constant (or am I wrong?).

2) whether there is a general expression for the above given series on the right hand side. What immediately stands out of course is that the first terms are all $p_s$, which corresponds to the situation in which in a single draw of $X$ we immediately obtain $s$ (let's call it $d=1$). Also, the last terms are all $p_1^s$, which corresponds to the situation in which we obtain the sum $s$ by drawing the minimum possible value of 1 in $s$ independent draws of $X$ (here $d=s$).

As an attempt at obtaining a general expression for the right hand side, I started out by thinking that for each $s$ we need a sum over the number of draws $d$. Since the minimum number of draws we need is 1, and the maximum $d$ we can have is $s$:

$P(S=s) \propto \sum_{d=1}^s \ldots$

If we go back to the example, we also see that the number of terms we add for each value of $d$ follow the binomial coefficient, specifically, \begin{equation} P(S=s) \propto \sum_{d=1}^s \sum_{i=1}^{\binom{s-1}{d-1}} \ldots \end{equation} where the upper limit for the second sum $\binom{s-1}{d-1}$ is just the binomial coefficient.

What I mean by this representation is that if we consider, for example the case for $s=5$, then for $d=1$ we add one term, $p_5$, and for $d=2$ we add 4 terms, $p_1p_4+p_4p_1+p_2p_3+p_3p_2$, for $d=3$ 6 terms and so on.

This is, I guess, because we can alternatively think of this problem as how to distribute $s$ balls into $d$ bins, with the condition that each bin must get at least 1 ball. What complicates this problem for me is that, I do not just want to know how many possible ways there are in which I can place $s$ balls into $d$ bins, but I'd like to have a series representation in which all the possibilities are spelled out, e.g. for $s=5$ and $d=2$ I'd like to have $p_1p_4+p_4p_1+p_2p_3+p_3p_2$, because I can put 1 ball in bin 1 and 4 in bin 2, or 4 balls in bin 1 and 1 in bin 2, or 2 balls in bin 1 and 3 in bin 2 etc.

At this point, I have attempted several different solutions and repeatedly failed. Any solutions, help, nudges and keywords in the right direction will be very much appreciated. Thank you in advance.

EDIT: I have given some more thought to the question, and I still don't know whether it would be possible to have a closed expression to represent $P(S=s)$ as a function of $p_x$, i.e. to have a general solution for any random variable $X$ with an arbitrary distribution. However, in general there seems to be solutions for random variables $X$ with discrete uniform or Poisson distributions. Nevertheless, I'd be interested in a general solution as a function of $p_x$ or in any other insights regarding this question. Thank you.

• Somewhere in the middle of your question, you state "I know the right hand sides above are not equal to the probabilities $P(S=s)$ on the left hand side, because they are not normalized (i.e. the sum of the right hand side terms as $s\rightarrow\infty$ will be bigger than $1$)". So do you think that $\sum_k=1^\inftyP(S = s) = 1?$ I think that's not entirely true. This also depends on the probability space we're using. Let me elaborate. We have this random variable $X$ which takes values in $\mathbb N$ with $P(X = k) = p_k$ and $\sum p_k = 1.$ So far so good. – jflipp Dec 3 '14 at 11:04
• [continued] Now you want to add up repeated values of $X$. So we construct a sequence of random variables $X_n$ with $n \in \mathbb N$ with $X_n \in \mathbb N,$ the $X_n$ are independent and each $X_n$ has the same distribution as $X.$ This can be done. Then our elementary events are sequences $\alpha = (X_1 = y_1, X_2 = y_2, \ldots).$ Then the event $\{S = k\}$ is "the set of all sequences $\alpha$ such that for some $m\in \mathbb N$ we have $y_1+\cdots y_m = k$". But then the events $\{S = k\}$ and $\{S = k'\}$ with $k\neq k'$ are not necessarily disjoint ... – jflipp Dec 3 '14 at 11:11
• [continued] because for one particular sequence $\alpha$ we can have that one partial sum equals $k$ while another partial sum equals $k',$ so $\alpha \in \{S = k\} \cap \{S = k'\}.$ So it's not necessarily true that $\sum_{k=1}^\infty P(S = k) = 1.$ – jflipp Dec 3 '14 at 11:13
• Thank you (I can't upvote comments, otherwise I would). I can see how $\{ S=k\}$ and $\{ S=k′\}$ with $k \neq k'$ are not necessarily disjoint, and this was one of the reasons why I initially asked whether such a probability distribution $P(S=s)$ can be 'easily' normalized with some normalization constant, or whether I'm making a logical error here. I think for my purposes I actually don't need to care about this fact (i.e. the events $\{ S=k\}$ with $k<k'$ possibly being subsets of the events $\{ S=k'\}$) or about the sum being (not) equal to 1. Thanks for formally putting it down though. – sirona Dec 3 '14 at 14:08

What I understand from the question is that one is given an i.i.d. sequence $(X_n)_{n\geqslant1}$, with positive integer values, and that one is interested in $P(A_s)$ for every $s$, where $$A_s=[\exists n\geqslant0,X_1+X_2+\cdots+X_n=s].$$ Then, the classical approach to compute every $P(A_s)$ in one strike is to consider the series $$u(x)=\sum_{s\geqslant0}P(A_s)x^s,$$ with the convention that $P(A_0)=1$, and to note that $$u(x)=\sum_{n\geqslant0}\sum_{s\geqslant0}P(X_1+X_2+\cdots+X_n=s)x^s=\sum_{n\geqslant0}E(x^{X_1+X_2+\cdots+X_n}).$$ The sequence $(X_n)_{n\geqslant1}$ is i.i.d. hence $$u(x)=\sum_{n\geqslant0}E(x^{X_1})^n=\frac1{1-E(x^{X_1})}.$$ In principle, this identity allows to extract every $P(A_s)$ as the coefficient of $x^s$ in the expansion of the RHS. For example, if $X_1$ is uniform on $\{1,2\}$, then $$E(x^{X_1})=\frac{x+x^2}2,\qquad1-E(x^{X_1})=(1-x)\left(1+\frac{x}2\right),$$ and $$u(x)=\frac{\frac23}{1-x}+\frac{\frac13}{1+\frac12x}=\frac23\sum_{s\geqslant0}x^s+\frac13\sum_{s\geqslant0}\frac{(-1)^s}{2^s}x^s,$$ hence, for every $s\geqslant0$, $$P(A_s)=\frac13\left(2+\frac{(-1)^s}{2^s}\right).$$ Finally, note that, for every aperiodic distribution of $X_1$, one can show that $$\lim_{s\to\infty}P(A_s)=\frac1{E(X_1)}.$$ This framework is called renewal theory, and we just scratched the tip of the iceberg...
• This was very helpful, thank you, although it will take some time until I can wrap my head around why this makes sense. Just out of curiosity, I realize that when you define $u(x)$, $x$ has the constraint $0 \geq x \geq 1$. This works very well for our purposes (for defining $u(x)=\frac{1}{1-E(\ldots)}$), but is there a reason for this choice of $x$ in the context of renewal theory? Does $u(x)$ represent some property (it looks like it should be proportional to the expected value of $x^s$) of a renewal process? – sirona Dec 3 '14 at 18:20
• If you like, $u$ is the generating function of the random occupation measure $\mu$ of the increasing process $(S_n)$ defined by $S_0=0$ and $S_{n+1}=S_n+X_{n+1}$ for every $n\geqslant0$, in the sense that $$u(x)=E\left(\int_0^\infty x^s\mathrm d\mu(s)\right),\qquad \mu=\sum_{n\geqslant0}\delta_{S_n},$$ but I doubt this is more enlightening than to see $u(x)$ as the formal generating function of the quantities $P(A_s)$ of interest. – Did Dec 3 '14 at 18:28