Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have probability distribution function of $x$: $P(x)$, where $x\in[1,2,...N]$.

I also have the sum: $$S = \sum_{j=1}^Kx_j$$ where $K$ is unknown.

Given $S$, is it possible to calculate probability distribution function of $K$: $P(K)$?

In other words, the probability: $P(K = i|S)$?

Thank you.

share|cite|improve this question
No, it is not possible without assumptions concerning the joint distribution of the $x_i$ given $K$, as well as a prior distribution for $K$. – r.e.s. Nov 23 '11 at 18:07
up vote 1 down vote accepted

Suppose $g(z) = \sum_{x=1}^N z^x \mathbb{P}(X=x)$ is the probability generating function of $x$. Then, assuming i.i.d. $x_j$, the probability generating function for the sum of $S_k = \sum_{j=1}^k x_j$ for a fixed is simply the power: $$ g_{S_k}(z) = g(z)^k $$ The probability you seek: $$ \mathbb{P}(K=i | S=m) = [z]^m g(z)^i = \binom{i}{j_1,j_2,\ldots,j_N} \mathbf{1}_{j_1+2j_2+\ldots+N j_N = m} \prod_{s=1}^N \left(\mathbb{P}(X=s)\right)^{j_s} $$

Example: Let's assume that $X$ follows $\mathrm{Bin}(N-1,p)$ distribution shifted by +1. Then $g(z) = z (1-p+p z)^{n-1}$. Therefore $g(z)^i = z^i \left( 1-p+ p z\right)^{i (n-1)}$. In this case: $$ \mathbb{P}(K=i|S=m) = \binom{i(n-1)}{m-i} p^{m-i} (1-p)^{ i n - m} \mathbb{1}_{n \cdot i \ge m \ge i} $$

share|cite|improve this answer
Thank you Sasha. I will try to apply this method and return to you. – Serg Nov 23 '11 at 21:53
This helped a lot. Thank you! – Serg Nov 29 '11 at 19:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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