3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jflipp Dec 3 '14 at 11:04
  • $\begingroup$ [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 ... $\endgroup$ – jflipp Dec 3 '14 at 11:11
  • $\begingroup$ [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.$ $\endgroup$ – jflipp Dec 3 '14 at 11:13
  • $\begingroup$ 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. $\endgroup$ – sirona Dec 3 '14 at 14:08
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – sirona Dec 3 '14 at 18:20
  • $\begingroup$ (On a different note, I have too little reputation to upvote your answer, so I'll do it once I get more reputation.) $\endgroup$ – sirona Dec 3 '14 at 18:24
  • $\begingroup$ 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. $\endgroup$ – Did Dec 3 '14 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.